Compacting the Uncompactable: The Mesh Compacting Memory Allocator

[@fobef]

Interesting talk and very good production

[@dakrontu]

You do not need many people in a room before by chance you find 2 with the same birthday. On that basis, you have little chance of meshing 2 pages unless they are very close to empty. So you run with a lot of very empty pages a lot of the time surely. How is that good? I have a different approach which depends on the distribution of packet sizes tending to be fairly consistent over time (and will not work well otherwise). It works as follows: 1. All allocations are in power-of-2 sizes. Each allocated packet therefore may end up not being fully used. On average, 75 % usage. 2. For each packet size, free() just adds to a chained list of pointers to packets of that size. (The packets being free, they have room to hold the 'next' pointers.) So the packets are never truly freed. 3. When another packet of a particular size is wanted, the relevant chained list is examined. If it is not empty, a packet is popped off the chain and used. If not, an actual allocation is done, and that can be purely sequential within the available memory space reserved for the heap. This scheme works well and I use it a lot in an interpretive language that I wrote which is similar to Python. It does not require any weird tricks with virtual memory mappers. The only thing that gives it a headache is the same thing that might give any heap allocator a headache, which is when some part of the code happens to want to allocate packets that are unusually large. This is because, when it is done with them, it does not truly release them, it just pushes them onto the chained list of free packets for their particular size, and resists the temptation to offer them for breaking up into smaller packets, even when smaller packets are needed. When a packet is allocated, it must have enough room for the object, and be a power of 2 in size, so it inevitably has wasted space that is between 50 % and 0 %, ie average 25 %, hence average 75 % usage.

[@EmeryBerger]

The allocation scheme you describe is essentially Chris Kingsley's allocator from early versions of BSD. Mesh certainly will save an enormous amount of space vs. that allocator, which is famously memory inefficient.

[@frenchmarty7446]

Your statistical intuition is wrong. Firstly, you don't get to directly control how fragmented virtual memory pages are. The Mesh algorithm fixes mostly empty pages, the authors don't advocate making pages more empty (whatever that would even look like). Secondly, your idea isn't original. You're just describing static allocation and memory pools. These ideas are orthogonal to what Mesh accomplishes anyways.

[@dakrontu]

Is it better to try to mesh near-empty pages into near-full pages? Or do you not bother with the near-full pages, and just try to mesh near-empty pages?

[@EmeryBerger]

The point of compaction is to reduce the amount of wasted empty space, so it doesn't make sense to try to mesh nearly full pages (which are unlikely to be meshable anyway).

[@parkatip]

Put speaker names in titles

[@EmeryBerger]

Good point! Speaker is me, Emery Berger (emeryberger.com/)

[@swetLive]

i donot speack english but please i need the work in start up in california of the united states

[@danielsmith5626]

it's a Linux paging hack. The answer to better memory management is not migrating to a new OS lmfao

[@frenchmarty7446]

1.) Remapping virtual pages is a feature of almost every operating system. 2.) How would this involve migrating to a "new" operating system?