Staring at the Sun: Dalvik vs. Asm.js vs. Native

The creation of big typed array simulating a memory pool is a construction of Emscripten. asm.js in that context is simply the vehicle / language.

A decade or so ago I worked on a GUI and we needed a Type 1 font parser. Freetype was not a good fit to our (very memory constrained, slow) platform. I was suprised though, how slow the library was, and did some profiling. First thing I noticed was a huge number of malloc() calls. And they were all small. A huge portion of them were only 4 bytes. The malloc() implementation on our platform had an overhead of at least 12 bytes per allocation, so not only was it slow, it also wasted a ludicrous amount of memory.

All in all there were multiple allocations per glyph despite the fonts being loaded and unloaded as a single unit. Yikes.

Since we were in a rush, my hacky fix was a search/replace for malloc()/free() to special a special version of malloc that would just grab the next free chunk from a pool, or if the pool was full allocate another 4KB block and start allocating from that, and nothing for free, and then I added code to initialise the pool and free it to the open/close parts of the font API.

The result was drastically reduced memory usage and at least an order of magnitude speedup on our platform.

(The library in question was t1lib, a library originally released by Adobe, and the stupid memory handling is still in there as of today despite sporadic updates over the last decade; I guess it's not used much any more with FreeType, but I'm almost tempted to do a cleaner fix and submit it - the fix we did was not suitable for general usage as it explicitly assumed a single set of fonts would be loaded and unloaded in the same order, as it didn't keep pools per loaded font)

If you can be sure that your allocator is only called in one thread, you can also avoid expensive memory fences.

Take a fixed-size pool of memory and divide it into a fixed number of equally-sized regions. Say, if your game's entities take up a maximum of 32 bytes of memory each, and you are ok with imposing a hard limit of 256 entities in the world at once, you could allocate an 8 kilobyte memory buffer and manage it yourself. Already there are apparent benefits in this scheme in reducing memory fragmentation (all of the game entities are in this 8 kilobyte region, and not scattered all throughout memory) and thus cache coherency (it's quicker to sequentially access memory in a small region of memory than it is to "hop around" all over the place).

How might we manage this memory? We really just need a way of allocating regions ("I want to create a new entity, please give me a free region to store it in") and freeing them when we're done with them (enemy died or whatnot). Because we have a fixed number of fixed-size regions, it's very straightforward (well under a 100 lines of C) to use a bitmap for doing so. Well, bitmap is the common terminology for this data structure, but I prefer to think of it as a binary set: you have a bunch of bits in RAM, and a 1 bit at some integer index indicates that the index is in the set, and a 0 bit indicates that it isn't. For example, if you have the byte 00010011, then 0, 1, and 4 would be in the set, while 2, 3, 5, 6, and 7 would not. [EDIT] Er, I guess "set of integers under some limit" is a more accurate description, but I like the way that "binary set" sounds.

So, dividing the 256 regions of the example by 32 bits in an x86 machine word, you would need 8 machine words to store this binary set, which take up 32 bytes total. All we need to keep track of is whether or not each region is free, so it's a suitable data structure for this purpose.

Most modern machine architectures have instructions for finding the index of the first set (1) bit in a machine word in a single, very quick operation.[1] So, we can use that to our advantage by representing a free region as a set bit, and an allocated region as a clear bit. Then, when you need to allocate a new entity, we can very quickly iterate over the bitmap like so: for each machine word, skip it if it is equal to 0 (all bits are clear, ie the region is fully allocated anyway), and otherwise call find-first-set to find the index of the next free region. Clear that bit (to indicate that it is now in use), and return the index of that bit to the caller (who can then use it like an index into an array, or convert it to a pointer). Freeing regions is even simpler: You just set the bit in the bitmap corresponding to the index in the memory buffer.

We also get another very useful operation for free with this scheme: Iterating over every object in the set. Say, we want to call "update" on every entity in our buffer. Make a copy of the binary set, and invert it, so that now a set bit indicates an allocated region. Then, it's very simple to create an iterator that can traverse every entity in existence: Call find-first-set to find allocated entities, call their update function, then clear the associated bit in the inverted binary set. Keep doing so until you reach the end of the set.

That's a very simple scheme to implement, but you can only really use it when it fits your memory allocation patterns well, or when you can tailor your memory allocation patterns to fit the memory management scheme. In a game, it can be acceptable to impose a hard limit on, say, the number of entities on screen (you could easily have a rule somewhere that stops spawning enemies if a certain limit has been reached, or start despawning less important entities when memory gets tight), but this probably wouldn't fly if you were maintaining a data structure for handling website requests: "Sorry, this site only supports up to 1K concurrent users, please come back later"

Now, think about the kind of changes you might have to make to make this manager more "flexible": How could you make it handle regions of various sizes? How could you make it handle growing the memory buffer (so that you can create more than the "maximum" number of entities)? How would you make it handle various types of objects that just happen to take the same amount of space? How about handling extremely large swaths of memory? Can we reasonably predict how the memory manager will be used in the program, or is that entirely out of our hands? The closer you get to malloc's use case, the less useful this data structure becomes, and by the same token, you should be starting to see how a manager that is expected to perform as best as possible under arbitrary usage patterns can be sub-optimal for a specialized use case.

Lastly, it's perfectly acceptable to use different memory management techniques at different levels of memory granularity. Consider that that is essentially what you'd be doing if you malloc a buffer that you then manage with the bitmapped memory allocator I described.

[1] https://en.wikipedia.org/wiki/Find_first_set

If we treat them appropriately and carefully (i.e. we don't look at two scores and use it to make an absolute judgement, but simply as a starting point for investigation and thinking about what it implies about the platform), they are of some use.

Even with the transcendental-heavy benches, it might still have been the case that there was some other implementation issue that slowed down asm.js on those benches. It's good to confirm that there aren't.

NBodies suggests asm.js costs associated with double-indirection. NSieve suggest that asm.js ARM codegen could be improved relative to x86. Binary-trees suggests that Dalvik may have an issue with highly recursive code. Binary-trees also suggests that there may be a perf issue with the default NDK libc's malloc (or free, or both) implementation.

All of these things are useful to think about, as long as we avoid the pitfall of using the benchmark as a judgement tool, and remember to use it as a starting point for analysis.

Lastly, I felt the exercise was useful in confirming that across a set of commonly accepted microbenches, asm.js was generally able to hold its own. It's good to confirm these things empirically, instead of assuming them.

emcc -O2 nsieve.cpp

for example.

Yes, I also had to increase the runtime, they were quite short on a laptop - they were meant for a phone I think.

In the actual SunSpider benchmark (in Javascript), a new Array object is allocated within that same loop, so I wrote the C++ and Java code to mimic that behaviour.

I could have pulled the Array allocation out across all of the implementations, but I tried to avoid making any changes to the benchmarks unless there was a correctness-issue involved (e.g. moving makeCumulative in the fasta benchmark out to the prelude was a correctness issue.. since it's wrong to run it more than once on the same array).