5 ms·

If I remember correctly you couldn't do this by just re-linking with another manual memory manager though because the application could hold pointers to things

If I remember correctly you couldn't do this by just re-linking with another manual memory manager though because the application could hold pointers to things in ways you don't understand and then you can't move them, so there has to be some additional indirection on every pointer access that resolves the real location of data in memory. So I would think this requires some compiler support or some sort of runtime. If you know more about this or know any cool implementations of it please elaborate!

chrisseaton 7y ago
> so there has to be some additional indirection on every pointer access We already have this - almost all modern computers have something called virtual memory, that allows you to de-couple your memory addresses from where the memory actually is. This allows you to 'move' memory without changing the addresses that you use to refer to it. You can then defragment memory by mapping two sets of addresses to the same memory physical memory, as long as the holes in the two sets overlap. In order words, if you have two pages, one with only the first half used, the other with only the second half used, you can copy the used part of the second page into the gap in the first page, and map the old addresses of the second page to the location of the first, now shared, page. You are using twice the address space (which costs just a few bytes in bookkeeping) but have defragmented so you're only using half the physical memory. You can then completely return the second page, now un-used, to the kernel.
- deleted 7y ago
  [deleted]
- mschwaig 7y ago
  Are there implementations that actually do this? I would think the page level granularity of virtual memory makes it not that useful for this purpose, since the used and unused parts of the two pages would have to line up nicely and larger objects tend to cause less fragmentation.
  - chrisseaton 7y ago
    I first saw this done in 2009 in the Hound memory allocator. I think it's been tried in or implemented in recent Glibc, but wouldn't swear to that. I think it's been shown to be useful in practice in real applications in a couple of papers. Fragmentation is often just one pesky object holding onto a whole page. If you have many such pages all with one object it's likely you can map them all together and release most of them.
  - chenglou 7y ago
    There are, for example: https://www.youtube.com/watch?v=VMP2w5o4Yco https://www.youtube.com/watch?v=VMP2w5o4Yco Their algorithm also addresses your concern of how to make pages “line up”. This method’s likely subject to the criticisms around this post.
- thedance 7y ago
  Double-mapping memory is almost always the wrong choice, since TLB entries are a critical resource for software performance. The only time it makes sense to double-map is when your are trying to make the CPU blind to what you are sharing, as seen in some high-performance ring buffer implementations. But this is double-black-diamond stuff, not something that has wide applicability.
  - chrisseaton 7y ago
    But it's only using as many mappings in total as the memory would be if it had not been compacted.

chrisseaton 7y ago

> so there has to be some additional indirection on every pointer access We already have this - almost all modern computers have something called virtual memory, that allows you to de-couple your memory addresses from where the memory actually is. This allows you to 'move' memory without changing the addresses that you use to refer to it. You can then defragment memory by mapping two sets of addresses to the same memory physical memory, as long as the holes in the two sets overlap. In order words, if you have two pages, one with only the first half used, the other with only the second half used, you can copy the used part of the second page into the gap in the first page, and map the old addresses of the second page to the location of the first, now shared, page. You are using twice the address space (which costs just a few bytes in bookkeeping) but have defragmented so you're only using half the physical memory. You can then completely return the second page, now un-used, to the kernel.

deleted 7y ago
[deleted]
mschwaig 7y ago
Are there implementations that actually do this? I would think the page level granularity of virtual memory makes it not that useful for this purpose, since the used and unused parts of the two pages would have to line up nicely and larger objects tend to cause less fragmentation.
- chrisseaton 7y ago
  I first saw this done in 2009 in the Hound memory allocator. I think it's been tried in or implemented in recent Glibc, but wouldn't swear to that. I think it's been shown to be useful in practice in real applications in a couple of papers. Fragmentation is often just one pesky object holding onto a whole page. If you have many such pages all with one object it's likely you can map them all together and release most of them.
- chenglou 7y ago
  There are, for example: https://www.youtube.com/watch?v=VMP2w5o4Yco https://www.youtube.com/watch?v=VMP2w5o4Yco Their algorithm also addresses your concern of how to make pages “line up”. This method’s likely subject to the criticisms around this post.
thedance 7y ago
Double-mapping memory is almost always the wrong choice, since TLB entries are a critical resource for software performance. The only time it makes sense to double-map is when your are trying to make the CPU blind to what you are sharing, as seen in some high-performance ring buffer implementations. But this is double-black-diamond stuff, not something that has wide applicability.
- chrisseaton 7y ago
  But it's only using as many mappings in total as the memory would be if it had not been compacted.