2011-03-28

Woopsi 1.1 Released

A new version of Woopsi is now available:

If you’ve been following the threads on the forum, you’ll have a good idea of the changes in this latest release. A new Woopsi user - carpfish - has contributed some neat features to Woopsi, such as natural string sorting, string splitting and formatting, and many others. Most of the changes in this release are either based on his work or solely his work. He has also contributed a number of bugfixes.

So, many thanks to carpfish for his contributions. Thanks also to MBMax who I believe introduced him to Woopsi.

The full changelog can be found in the archive, as usual.

2010-11-01

Woopsi 0.99.6 Released

Woopsi 0.99.6 is now available from the Woopsi website:

Other than a few minor enhancements to the Debug class, this release just contains bug fixes.

There are a couple of points to note about this release. First of all, it is built with the latest versions of devKitARM and libnds (r32 and 1.4.8 respectively). Due to changes in the FIFO system, the current version of desmume is not compatible with this release. You’ll either have to wait for the next version of desmume or compile it yourself from the SVN repository before you upgrade your release of devKitARM.

If you’re running Windows and don’t want to compile your own version of desmume, here’s one I made earlier:

It’s a few weeks old now, but it works.

libnds 1.4.8 includes a bug in line 661 of nds/arm9/videoGL.h. See the following link for the fix:

Note that you can still use Woopsi with older versions of devKitARM; you’ll just need to compile the library yourself. This is very simple; just open a command line to the Woopsi/Woopsi/libwoopsi folder, type “make clean” and then type “make”.

Secondly, one of the new features in the Debug class is a vsnprintf() method. This method triggers a GCC warning about va_list mangling changes in GCC 4.4. This is neither a problem in Woopsi or in devKitARM; it’s actually the result of a bizarre decision by the GCC team to include news items as compiler warnings:

Wintermute intended to fix this for devKitARM r27, but this obviously never happened:

The full changelog is available in the source archive.

2010-09-16

Woopsi 0.99.5 Released

The 0.99.x series marches on! Get it from the main Woopsi site:

This release includes the rendering changes discussed recently and a large number of bug fixes. The other big change is yet another slider logic rewrite. This time I admitted defeat and looked around to see what others had done. I’ve re-implemented the formula that the Qt toolkit uses, which has finally eliminated all scrollbar problems.

The full changelog is in the main source archive.

Oh, and one more thing. According to the changelog, tomorrow is the third anniversary of Woopsi’s first release.

2010-09-10

Performance Problems - Not Where You'd Expect

The new rendering system in Woopsi is coming along nicely. In most areas it increases rendering speed and reduces flicker. In one area, though, it hasn’t been an improvement at all. Scrolling has become a problem.

In the old system, scrolling regions were extremely quick, mainly because most of the scrolling is done by just using the DMA to copy the existing pixels to a new location. In the new system, however, scrolling is sluggish and annoying. It seems to take more than one frame to perform a single scroll operation, which results in the display lagging behind the stylus and the system appearing to be, well, a bit rubbish.

I’ve already made one major optimisation. Instead of asking every gadget to draw every damaged rectangle until there are no rectangles left (which results in dozens of pointless, complex clipping operations), Woopsi uses the hierarchy of the gadgets to its advantage. If a parent gadget does not intersect a damaged rectangle, there is no way for its children to intersect it either. In avoiding trying to draw those children we save a lot of time.

However, this did not solve the scrolling problem. So what could it be? More to the point, how can it have happened, as the scrolling code hasn’t actually changed?

I had a few guesses. Perhaps the scrolling operation was running more than once. Putting break points into the Xcode version of Woopsi quickly killed that idea. Perhaps I need to cache the contents of ScrollingPanels in some sort of off-screen bitmap - maybe it’s all the redrawing that is a problem. But it couldn’t be that - there weren’t any problems before. Perhaps the list of newly-revealed rectangles that need to be redrawn that is returned by the scrolling routine is inaccurate. Testing it overturned that idea.

So I turn to Xcode’s “Instruments”, something that I wish Visual Studio would copy. Running Woopsi through the CPU Sampler suggests that the only thing Woopsi is doing is creating Rect objects. Creating rectangles is making Woopsi’s scrolling rubbish? That makes no sense.

Except, perhaps it does.

All of the new rendering functions create WoopsiArrays of Rect objects. As the inital size of a WoopsiArray is 100, and as they store objects, not pointers to objects, that means that each function call to one of these methods creates hundreds of Rect objects. Worse, these functions are recursive. There are probably tens of thousands of Rect objects being created every time the screen redraws.

I tried switching to arrays of pointers-to-rect objects, but quickly got bogged down in recursive memory allocation hell. Instead, I altered the WoopsiArray class so that it accepts an initial reserved size parameter. In most cases, none of the methods needs more than 4 rects in a list, so I’ve gone with that as the initial size. I’ve also changed the way that the array class resizes itself; it now doubles in size every time it needs to allocate more space instead of increasing by 100 elements. I believe this is the behaviour of the STL’s vector class.

Surprisingly enough, these very minor changes fixed the scrolling problems and boosted the speed of Woopsi everywhere else. I’m not sure I can remember it being this quick.

It’s a very old programmer’s cliche, but it’s true. Performance problems aren’t always where you’d expect.

2010-09-08

So What Else is New?

I’ve made a few changes in addition to the damaged rectangle stuff. There were a few memory leaks dotted around the code, most of which were the result of early-exiting functions so that string iterators weren’t deleted. Xcode’s “Leaks” instrument is absolutely indispensable when trying to track memory leaks down.

I’ve removed AmigaWindow::redrawBorder() because it wasn’t used and didn’t appear to do anything. In its place I’ve added markBorderDirty(), which uses the new damaged rectangle system to redraw just the borders. This speeds things up a little when windows gain or lose focus - only the borders change, so why redraw the entire window?

The Text class is now called “Document”. It no longer inherits from the WoopsiString class, but contains one instead. The Text class always emanated a nasty code smell. What does “Text” mean, anyway? Is it a string? Sort of… It’s a string that has a font attached and a width within which it wraps itself. Kind of like a Word document. Ahhh, that makes sense: It’s a document.

Gadget::checkCollision() works correctly. I think I broke it a couple of releases ago.

ScrollingPanel::scroll() works correctly when the panel is on the top DS screen. Lakedaemon spotted this bug. The fix involved converting between co-ordinate systems.

The ListData class’ destructor no longer fires list changed events when it runs.

Finally, Woopsi will no longer ship with Lakedaemon’s freetype classes or the freetype library. Instead, they can be downloaded as part of Lakedaemon’s suite of DS libraries and Woopsi classes, “ndsToolKit”:

It includes Woopsi, the XmlBox gadget, and the freetype classes and library, in addition to DS ports of libjpeg, libpng, libsqlite3 and others. Sounds very powerful.

2010-09-08

Redrawing with Damaged Rects

The Problem: Bad APIs and Suboptimal Redrawing

The existing gadget redrawing system in Woopsi sucks. It’s inefficient and makes the API ugly.

For example, here is a completely bare-bones startup method that will get Woopsi into a usable (but empty) state:

void SomeApp::startup() {
    enableDrawing();
    redraw();
}

The two function calls in the startup() method ensure that the Woopsi instance is visible. When an instance of the Woopsi class is created, its redraw system is disabled. This allows the initial set of gadgets to be added without them appearing on-screen one at a time. Once the initial state has been set up, drawing can be enabled, and the initial state can be drawn.

You might notice that these two lines of code aren’t required in any other UI framework you’ve used. Neither winforms, AWT, Swing, GTK, KDE or anything else requires that you manually enable redrawing and redraw the display once you’ve finished adding UI components to your application.

The reason for this is the way that Woopsi handles redrawing. In Woopsi, each gadget is responsible for redrawing itself. All gadgets know which portions of themselves are visible, and they also know when their appearance has been changed. When a gadget is created it knows that it must redraw itself, and does so. Likewise, when a gadget moves, or is resized, or is clicked, it will redraw itself. So, when we add gadgets to Woopsi, they will draw themselves to the screen one at a time instead of the entire screen being drawn in a single operation. This piecemeal redraw looks odd and wastes CPU time, so drawing is initially disabled. Users must re-enable drawing themselves when the UI is ready.

The problem of wasted CPU cycles is more onerous in other situations. Consider the TextBox gadget. This redraws itself every time its text is changed. If we run the following code, the textbox will redraw four times:

textbox->appendText('t');
textbox->appendText('e');
textbox->appendText('x');
textbox->appendText('t');

The textbox redraws every time a character is added to its text. If we were to add one hundred characters, the textbox would redraw one hundred times. Now suppose that the textbox fills the entire bottom DS screen. Changing the text in the textbox changes roughly 8x8, or 64 pixels, per update. That means we’ve changed 6,400 pixels. However, we’ve redrawn every pixel on the screen one hundred times. We’ve redrawn 256x192, or 49,152 pixels, per update. We’ve redrawn 4,195,200 pixels when we only needed to redraw at most 6,400. 99.87% of the redrawing was just wasted CPU time.

Woopsi offers a workaround in the form of the enableDrawing() and disableDrawing() methods of the Gadget class:

textbox->disableDrawing();
textbox->appendText('t');
textbox->appendText('e');
textbox->appendText('x');
textbox->enableDrawing();
textbox->appendText('t');

However, this is a nasty hack. It requires that the developer knows enough about Woopsi’s internals to be able to predict when it will redraw and when it is safe to prevent the automated redraws from running. In the above code, it isn’t particularly obvious why drawing is re-enabled before the last character is added (so that the final append triggers a redraw) and it isn’t something that developers should need to care about.

The Competition: What Everyone Else Does

In the majority of other UI kits, redrawing is handled by tracking damaged rectangles. These are areas of the screen that have been modified and therefore need redrawing. In these systems, instead of our textbox redrawing itself, it would notify an object responsible for tracking these damaged rectangles that its visible areas had changed. The tracking object would store any of those rectangles that it hadn’t been previously notified of in a list. At frequent intervals (every VBL, say) the tracker would order the gadget hierarchy to redraw all of the damaged rectangles in its list. Using this system, the textbox would only be drawn once no matter how many times it was changed.

Justifying Woopsi’s Behaviour: DMA and Bad Code

Woopsi doesn’t use a damaged rectangle system for two reasons. Firstly, it makes extensive use of the DS’ DMA hardware to copy areas of the framebuffer around. It is especially important to the scrolling system that everything on-screen is up-to-date. If redrawing was postponed until a later time it is likely that the scrolling system would be working with out-of-date data. The second reason is the complexity of the rectangle splitting algorithm discussed here and here. Trying to get the code that splits up rectangles to do anything slightly different would be horribly complicated because, well, the code itself is horrible.

Potential Benefits of Changing Woopsi

But what if Woopsi could use the damaged rectangle system for redrawing? How would that affect the API and the framework? It would instantly obsolete about a dozen of the most complicated methods, and it would make a bare-bones Woopsi setup function look like this:

void SomeApp::startup() { }

Adding one hundred characters to a textbox would require a single redraw without any extra developer effort. Even actions such as moving gadgets would be more efficient - they are currently entirely erased from one location and redrawn at another, even if they move by just one pixel. A damaged rectangle system would reduce the number of rendered pixels in such a situation by almost 50% because there wouldn’t be an erasing step.

Fixing the Rectangle Splitter

The existing code used to split up rectangles into intersecting and non-intersecting sub-rectangles is 207 lines long. At times, it has nested if statements and for loops nearly a dozen deep.

(I’d originally intended to add the code in here, except my current WordPress theme breaks the “more” tag, making the post far too long for the front page of the blog. Additionally, trying to force the code into a smaller div by adding a “style” attribute breaks the syntax highlighter and causes angle brackets to be interpreted as HTML tags. I really need to get a new theme that’s less cluttered and easier to read, but nothing I’ve found so far fits.)

Anything nested that deeply is in dire need of refactoring. I looked at it the other day and realised that the entire algorithm was vastly overengineered. A far more efficient approach presented itself to me and I set about rewriting it. The replacement method is 74 lines long and contains just 4 if statements with no nesting at all.

The new method is a massive improvement over the original code. It is considerably smaller and easier to understand, it is faster and best of all, it produces the optimal result each time.

In all situations where there is an intersection, the original code produced (2n-1) rectangles, where n is the optimum number of rectangles. The larger the number of rectangles produced by this method, the more clipping the renderer will have to do later, so having a function that always produces the optimal result is a very good thing.

Switching to Damaged Rectangles

With the rectangle splitting routine rewritten and moved into the Rect class, where it should have been from the start, switching to a damaged rectangle-based rendering system starts to become feasible. The last problem to solve is the issue of scrolling. The scroll routines must be working with the latest bitmap data, which means rendering cannot be deferred.

I don’t know how much thought I’ve put into into solving this during the course of Woopsi’s development, but I’d never managed to hit on a solution until a couple of days ago. The answer is painfully obvious once you know it: make any functions that use the scrolling abilities of Woopsi flush any pending damaged rectangle redraws before they start. That way, the screen will be up-to-date before any scrolling is done.

Simple, obvious.

The upshot of all this is that Woopsi’s rendering engine is now based on damaged rectangles. Instead of the TextBox calling redraw() when its text changes, it now calls markRectsDirty(). It sends its list of visible rectangles to a new DisplayManager class (I might change the name of that class at some point), which works out which parts of the damaged rectangles it knows about (and discards them) and which are new (and remembers them). Once every VBL the DisplayManager redraws the display.

Redrawing is achieved by splitting the damaged rectangles into intersections with the gadgets. The DisplayManager performs a depth-first walk of the gadget tree in order to redraw in front-to-back order. Any rectangles that are redrawn are removed from the damaged rects list. Once that list is empty, the redraw method ends.

What has changed?

So, what has changed? There’s no need to call enableDrawing() or redraw() in the startup() method, for a start. In fact, both enableDrawing() and disableDrawing() no longer exist. The redraw() method has gone too, as well as the following:

  • Gadget::erase()
  • Gadget::eraseGadget()
  • Gadget::redrawDirty()
  • Gadget::drawChildren()
  • Gadget::redrawDirtyChildren()
  • Woopsi::eraseRect()

As previously mentioned, these were some of the cludgiest, most unpleasant functions in the system. I’m glad to have chucked them out.

There’s always a Catch

Unfortunately, the hack that the DimmedScreen class exploited no longer works. That class has had to be deleted.

2010-09-02

Woopsi 0.99.4 Released

Woopsi 0.99.4 is now out, but in a break from tradition, you can’t download it from SourceForge. As I said in the last post, Woopsi development has moved to BitBucket.

At Lakedaemon’s suggestion, I’ve created a new website for Woopsi. All releases - including this one - will be available there from now on. The new site can be found here:

This release mainly fixes bugs. Additionally, I’ve fiddled with the fonts and font generation tools a little, mainly to accommodate basic functionality required for Lakedaemon’s “XmlBox” gadget.

The woopsi.org website’s source code is itself hosted by BitBucket, and can be found here:

However, there’s very little PHP behind this site, so there’s not much to see that you can’t find by looking that the HTML behind the pages.

2010-08-26

Farewell to SourceForge

SourceForge has been Woopsi’s source code host since October 2007. They’ve been a great host. They offer some excellent features, and haven’t charged me a thing for nearly 3 years of diligently caring for my code. However, both technology and “social” coding techniques have improved since I adopted Subversion. I’ve found modern distributed version control systems to be faster and more flexible than Subversion, whilst the forking capabilities provided by sites such as GitHub and BitBucket make collaborating with other coders incredibly easy.

A request from Lakedaemon that I move Woopsi to a DVCS finally convinced me that it was time to move on, so I’ve switched from Subversion to Mercurial. Woopsi and its associated sub projects are now hosted on BitBucket:

The SourceForge page remains in place as it’s impossible to close a SourceForge site that has code committed to it. It now includes a notice indicating that the project has moved.

2010-08-26

Woopsi 0.99.3 - A Belated Release Announcement

Woopsi 0.99.3 was released a week ago:

http://www.sourceforge.net/projects/woopsi

This is what I said about it on the GBADEV forum:

This release fixes a number of bugs. Some of the code has been tidied up. The only change that could have an impact on user code is the removal of drawHorizLine(), drawVertLine(), drawCircle() and drawFilledCircle() from the GraphicsPort class. The drawLine(), drawEllipse() and drawFilledEllipse() methods will now automatically call the optimised form if it is available.

The full list of changes is available in the ChangeLog.txt file within the archive.