5 ms·

The point about memory allocation is similar to Walter Bright's explanation of D compiler performance [1]. There, the issue was deallocation; Walter "cheated" b

The point about memory allocation is similar to Walter Bright's explanation of D compiler performance [1]. There, the issue was deallocation; Walter "cheated" by never deallocating any memory since the compiler is a short-lived process. As a complement in this Mozilla test, Kannan Vijayan believes that Asm.js ran so fast in the Binary Trees test because there is a single large allocation at process startup, much like a memory pool. The moral of the story is always be aware of what malloc() and free() are doing to your code. [1] https://news.ycombinator.com/item?id=6103883 https://news.ycombinator.com/item?id=6103883

tehwalrus 13y ago
I once made a C python extension considerably faster by being more careful with malloc and free - I can recommend it as an easy-ish way to speed up a C/C++ program.
- duaneb 13y ago
  Anyone who has implemented a memory allocator knows how expensive it can be. If you have a simpler algorithm that works with your data, allocate a huge chunk and manage it yourself. EDIT: Looks like the author of the native benchmarks needs to learn this lesson: https://github.com/kannanvijayan/benchdalvik/blob/master/nsieve/nsieve.cc#L38 https://github.com/kannanvijayan/benchdalvik/blob/master/nsi...
  - Peaker 13y ago
    And use so-called "intrusive" data structures and APIs to avoid more allocations.
  - deleted 13y ago
    [deleted]
  - vidarh 13y ago
    My favourite example of memory allocation anti-patterns: 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)
    - antihero 13y ago
      As someone with basic C experience, could you link me to some resources about how to use malloc properly (ie, allocating a block of RAM and managing it yourself)? I find the whole thing fascinating.
      - tehwalrus 13y ago
        If you need both malloc and realloc, then these are not the droids you're looking for - the system implementation won't be that much slower than something you can hack together. If you are using heap RAM for persistence over a long lived application, then again the system version is going to be helpful (you're going to allocate something like a 4KB chunk, and then you'll have to hang on to that as long as >= 1 byte is still needed from it, which will dramatically increase the RAM used by your process compared to what it requires.) If your particular problem is just "I need to allocate some heap RAM because my arrays might be too big for the stack," then allocating one big chunk at the start of your function (of a size tailored to your particular problem) will save you a bunch of slow system calls. Similarly, if your process is short lived, then you can also forget about free() calls, and just use one big buffer and your own allocator on it - see "everyone thinks about garbage collection the wrong way (2010)" http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047586.aspx http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047... (recent HN discussion: https://news.ycombinator.com/item?id=6131786 https://news.ycombinator.com/item?id=6131786 )
Sharlin 13y ago
Practically the first thing to do in any serious game development project is to pick an allocator other than malloc.
- munificent 13y ago
  Or better: more than one. Most games I worked on had a few different allocators specialized for different uses.
- ancarda 13y ago
  As someone who has never touched C/C++ or managed their own memory, can you explain how other allocators work and how the performance differs from malloc?
  - aaronblohowiak 13y ago
    The complexity of malloc comes from the fact that the objects can be of variable size and have unknown lifespans. Faster allocators usually work on "pools" of objects that have the SAME size and/or lifespan. Using "pools" lets you avoid the extra overhead. If you can be sure that your allocator is only called in one thread, you can also avoid expensive memory fences.
    - marshray 13y ago
      I don't know this for a fact, but some implementations of malloc() seem to allow realloc() the possibility of later growing the memory in-place. A custom allocator may gain efficiency by optimizing explicitly for or against the realloc() scenario.
      - spc476 13y ago
        If you are following the C standard for malloc(), then realloc() comes along. In fact, according to the C standard, malloc(size) is the same as realloc(NULL,size) and free(ptr) is the same as realloc(ptr,0). realloc() can also shrink a previous allocation, in addition to growing it (but you must be aware that you might get back an entirely new pointer).

tehwalrus 13y ago

I once made a C python extension considerably faster by being more careful with malloc and free - I can recommend it as an easy-ish way to speed up a C/C++ program.

duaneb 13y ago
Anyone who has implemented a memory allocator knows how expensive it can be. If you have a simpler algorithm that works with your data, allocate a huge chunk and manage it yourself. EDIT: Looks like the author of the native benchmarks needs to learn this lesson: https://github.com/kannanvijayan/benchdalvik/blob/master/nsieve/nsieve.cc#L38 https://github.com/kannanvijayan/benchdalvik/blob/master/nsi...
- Peaker 13y ago
  And use so-called "intrusive" data structures and APIs to avoid more allocations.
- deleted 13y ago
  [deleted]
- vidarh 13y ago
  My favourite example of memory allocation anti-patterns: 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)
  - antihero 13y ago
    As someone with basic C experience, could you link me to some resources about how to use malloc properly (ie, allocating a block of RAM and managing it yourself)? I find the whole thing fascinating.
    - tehwalrus 13y ago
      If you need both malloc and realloc, then these are not the droids you're looking for - the system implementation won't be that much slower than something you can hack together. If you are using heap RAM for persistence over a long lived application, then again the system version is going to be helpful (you're going to allocate something like a 4KB chunk, and then you'll have to hang on to that as long as >= 1 byte is still needed from it, which will dramatically increase the RAM used by your process compared to what it requires.) If your particular problem is just "I need to allocate some heap RAM because my arrays might be too big for the stack," then allocating one big chunk at the start of your function (of a size tailored to your particular problem) will save you a bunch of slow system calls. Similarly, if your process is short lived, then you can also forget about free() calls, and just use one big buffer and your own allocator on it - see "everyone thinks about garbage collection the wrong way (2010)" http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047586.aspx http://blogs.msdn.com/b/oldnewthing/archive/2010/08/09/10047... (recent HN discussion: https://news.ycombinator.com/item?id=6131786 https://news.ycombinator.com/item?id=6131786 )

Sharlin 13y ago

Practically the first thing to do in any serious game development project is to pick an allocator other than malloc.

munificent 13y ago
Or better: more than one. Most games I worked on had a few different allocators specialized for different uses.
ancarda 13y ago
As someone who has never touched C/C++ or managed their own memory, can you explain how other allocators work and how the performance differs from malloc?
- aaronblohowiak 13y ago
  The complexity of malloc comes from the fact that the objects can be of variable size and have unknown lifespans. Faster allocators usually work on "pools" of objects that have the SAME size and/or lifespan. Using "pools" lets you avoid the extra overhead. If you can be sure that your allocator is only called in one thread, you can also avoid expensive memory fences.
  - marshray 13y ago
    I don't know this for a fact, but some implementations of malloc() seem to allow realloc() the possibility of later growing the memory in-place. A custom allocator may gain efficiency by optimizing explicitly for or against the realloc() scenario.
    - spc476 13y ago
      If you are following the C standard for malloc(), then realloc() comes along. In fact, according to the C standard, malloc(size) is the same as realloc(NULL,size) and free(ptr) is the same as realloc(ptr,0). realloc() can also shrink a previous allocation, in addition to growing it (but you must be aware that you might get back an entirely new pointer).