Strategy around memory fragmentation

[Dieter Weidenbrück]

Hi all,
I'm working on a graphics authoring app. Naturally, there are lots of primitives stored in variable size mem blocks. The quantity can easily exceed a couple of hundred thousand blocks.
Loading such content into fresh memory is not the problem, however, after editing/changing the content the heap will be cluttered with small blocks.

It is not really feasible to load a new instance and reorganize all blocks there, although that might be a last effort solution.

Is there any recommendation on how to overcome this problem? I thought about reserving a large chunk of memory (approx 1.7 GB to leave room for other allocations) using malloc at startup time and then manage all small blocks myself. Looks a bit like brute force though. (I'm not caring about mobile phone usage)

On 68k-Macs Handles were used (int**) where a pointer was stored in a master block, and the code would access the location in the master block only. That made it possible to move mem blocks around and compact the heap. Could that be a solution?

Thanks for your ideas!

Coming from long years of C development I am thrilled with emscripten and the options it offers for new kinds of web apps!

[Emil Dotchevski]

On Wed, Feb 24, 2021 at 9:46 AM Dieter Weidenbrück <die...@weidenbrueck.eu> wrote:
> I'm working on a graphics authoring app. Naturally, there are lots of primitives stored in variable size mem blocks. The quantity can easily exceed a couple of hundred thousand blocks.
> Loading such content into fresh memory is not the problem, however, after editing/changing the content the heap will be cluttered with small blocks.
>
> It is not really feasible to load a new instance and reorganize all blocks there, although that might be a last effort solution.
>
> Is there any recommendation on how to overcome this problem? I thought about reserving a large chunk of memory (approx 1.7 GB to leave room for other allocations) using malloc at startup time and then manage all small blocks myself. Looks a bit like brute force though. (I'm not caring about mobile phone usage)

My method for fighting fragmentation and performance issues with memory is to use shared_ptr-based factories for everything. It has a type-erased deleter so that you can organize your data in different pools and caches not only based on type but even per-instance. Of course this may not be practical in case you're dealing with a mature code base that does not use shared_ptr.

[Dieter Weidenbrück]

Thanks for the hint, Zajo.

I will have a look at it. It looks like a bit of work, especially in a C environment.

[Floh]

If your memory blocks are roughly in the same "size classes" and fit into jemalloc's bucket sizes, then jemalloc (which AFAIK is used as emscripten's default allocator) should be fairly effective in avoiding memory fragmentation because allocations of similar size are already grouped into bigger pool allocations and then reused.

Fragmentation might then become a problem on the next level, when jemalloc is trying to allocate memory for new buckets, but can't find a big enough gap in the 32-bit address range (I'm actually not sure if WASM even uses the full 4 GB range, or is limited to 2 GB, in that case, 1.7 GB might be too close to the maximum, and no clever "fragmentation strategy" might help, because there's too little "wiggle room").

You can read up on jemalloc allocation strategy by searching here for "IMPLEMENTATION NOTES": http://jemalloc.net/jemalloc.3.html.

[Dieter Weidenbrück]

Hi Flow,

thanks for your answer.

Unfortunately, sizes vary a lot. Most primitives share a common section (doubly-linked list links plus up and down, metadata etc), then follows graphical data.  A polyline, for example may then have two points or 2 hundred. So I could use similar sized blocks for the common part but would then need another pointer to add the individual portion.

I will have a look at jemalloc anyway, thanks for the link.