Palapeli: Multithreading, memory usage and interface

April 2, 2011

The Blue Wonder Meeting last week was an excellent opportunity to do some work on Palapeli. One thing that I wanted to do for at least a year was to rewrite the multithreading code around the (fairly central) Palapeli::Puzzle class. The new class has an aspect-oriented design, where single components of the puzzle (like the metadata or the contents) are always made available by worker threads, by casting existing components. For example, a puzzle file can be casted into metadata by reading the latter from the puzzle file. The possible casting paths are actually so convoluted that I documented them in an image inside the source code directory:

Yet there are still areas where Palapeli’s concurrency needs to improve. Much of the puzzle loading is done in the GUI thread, which causes the loading animation to freeze frequently. But that’s for another day. Moving back from what I should do to what I actually did, I noticed that Palapeli’s memory usage is awful. During the sprint, I wanted to demo Palapeli’s performance with big piece counts, and created a puzzle with the maximum of 2000 pieces from a 5000×5000 px image. It actually rendered fluently, but only because I upgraded my notebook’s RAM to 2 GB last year. Palapeli used an enormous 1.6 gigabytes of memory.

I figured that’s a bit much, and looked yesterday evening into how this can be optimized. I was testing with a 30 pieces puzzle from a 4000x4000px image. After having started Palapeli and having loaded the puzzle, the application used about 800 MB memory. The first, and simple, optimization was to remove some intermediary images which are only used while loading the image. That saved something like 100 MB of memory. But wait! Shouldn’t a 4000×4000 pixel image need only 61 MB (four bytes per pixel)? Yes, that’s true, but actually we’re not talking about one big image, but about 30 images, one for each piece. While pieces might have an arbitrary shape, their image must internally be rectangular all the time, even if big parts (e.g. around the plugs) are fully transparent. This means that the memory usage for the 30 pieces is bigger than what one might expect from the complete image.

A randomly chosen piece was 855×1098 pixels big, so by a rough approximation, all 30 pieces take 30*855*1098*4 bytes = 107 MB in memory. That still does not explain why the process still occupies 700 MB. But what’s that?

There’s a shadow around the pieces! This shadow is not added by the slicer when the puzzle is created, but by the engine when the puzzle is loaded. And because we need to control how shadows cover other pieces, we cannot render the shadows into the piece image, but must store them as separate images! And to make matters even worse, we need different shadow images for selected and unselected pieces (note the difference between blue and black shadows). The shadow size for the test image is 0.15 * (width + height) = 300 pixels on each side. Putting everything together, the memory usage of piece images + normal shadows + selected shadows is about 700 MB, i.e. everything can be explained by the pure size of the displayed images. The second optimization therefore was to restrict the shadow size to 50 pixels. This reduces the memory consumption to 380 MB, and allows to play even 5000×5000 px (i.e. 25 megapixel) images with below 1 GB of RAM.

More sophisticated optimizations are certainly possible, but let’s stop at this 50% improvement for now. There’s another thing I want to show: Palapeli’s mainwindow has been cleaned up. I really liked the old tab interface. It had its time and justification, but I want to move forward and need a cleaner, more standard interface for that. So now Palapeli has only a menubar and toolbar, just like all the other apps:

This change was possible after I realized that all toolbar actions for the collection also make sense on the puzzle table: Delete and Export work on the current puzzle. Newly created or imported puzzled will be loaded into the puzzle table afterwards. The “Back to collection” button replaces the “My collection” and “Puzzle table” tabs.


14 Responses to “Palapeli: Multithreading, memory usage and interface”

  1. […] 2, 2011 My last post was quite big, so I’ve split out the news part to ensure that it gets some attention. […]

  2. TheBlackCat Says:

    Is there a reason you can’t use compression, like png, on the shadows? Since the area underneath the piece can be blank I would think there would be relatively little non-100% transparent content, which I would think would be relatively easy to compress.

    Also, it looks like the shadows are more or less the same, but different colors. Would it be possible to have one shadow, but either render it in color or in black-and-white? Perhaps you could even make do with a single color channel that controls the lightness and transparency (which at least superficially appear closely linked).

    • Ian Monroe Says:

      You can’t display compressed images. Think about it. 🙂

      • TheBlackCat Says:

        You can’t display them, but why can’t you store them before combining them for the single image rendered on-screen?

        What is actually displayed isn’t all the individual images, it is a single image, after things like clipping, zoom, and scrolling have been taken into account. So why can’t you store the images in compressed format, then use those compressed images to render the one final image that is actually displayed?

  3. Santiago Says:

    How about using OpenGL for the canvas? That way you could use shader programs for the shadows instead of using an image.
    I know that a lot of graphics cards have shitty drivers, but it would be nice to see more programs use GPU acceleration.

    • Stefan Majewsky Says:

      That’s the obvious solution, but I don’t know any OpenGL or GLSL, so someone must step up.

      • Ian Monroe Says:

        or use the QML + Scenegraph Qt branch. I don’t know opengl either, but there’s no time like the present eh? I know I need to dig into it at some point.

  4. Vladislav Blanton Says:

    very cool to read about it; it has been interesting seeing your work show up in the commit digest.

  5. damian Says:

    Very nice work, can shadows be disabled?, if ram usage went from 800mb to 100mb just for shadows, I think I would disable it (at least on the netbook).
    Also are all the pieces 100% unic? or the same sides are repeted but mixed (right side 1 with top side 34,etc.) If they are, what about rendering each side of the shadow independently so that only the unic sides are loaded on ram, and the combinatios are made on the run.

    • Stefan Says:

      Question 1: Shadows can be disabled since day one.

      Question 2: The old slicer worked just in the way which you describe, but the new Slicer Collection (since 4.6) generates unique parts with very different tesselation schemes.

      Actually, Palapeli does not make any assumptions about how puzzle pieces actually look, so it’s impossible to apply these optimizations.

  6. bks Says:

    What format are you storing the shadows as? Could you just save _one_ copy of the shadow as a QImage::Format_Indexed8 image and then use QImage::setColorTable() to control what color the shadow is rendered as? Since color table entries _can_ have alpha values, AFAIK…

  7. shirishag75 Says:

    Any point/update on making on say 100 puzzles (bulk puzzles) in the game. Explore the directory and tell the slicer to do some extreme random slicing rather than the user doing the boring job of doing so.

    If already it is there please tell/share how one can do that? I did try the new version of Palapeli of 4.6 and at first glance doesn’t seem to be anything new in there (atleast in the GUI) . Looking forward to updates.

    • Stefan Majewsky Says:

      The random slicing from a directory is a good idea. Could you put this into b.k.o, please?

      The 4.6 release most prominently cleans up the puzzle creator dialog and adds a new set of slicers.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s