6 ms·

I've heard this as an argument for GC being faster/using less memory in some cases than manual memory management. You can asynchronously return memory to the O

I've heard this as an argument for GC being faster/using less memory in some cases than manual memory management. You can asynchronously return memory to the OS in a separate thread. Boehm GC in particular is really easy to link into an app and use instead of malloc and friends.

chrisseaton 7y ago
It’s the fact that automatic memory memory management can defragment through moving that is key. But there are also some manual memory managers that can defragment through moving as well - even some compatible with the malloc interface.
- mschwaig 7y ago
  I fully agree that moving is key. Just to further clarify the terms if someone is looking for more info on this: In the context of system memory people mostly refer to this as compaction and not defragmentation.
- mschwaig 7y ago
  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.
- camgunz 7y ago
  Oh yeah, I mean anything you can do automatically you can do manually. A core benefit of GC is you can have pretty complex memory management techniques that run more or less totally transparently. You can leverage generations (or defragmentation) to keep allocation latency low, etc.
- astrobe_ 7y ago
  How does this work? Is the application required to call realloc() on its object in order to let the defragmentation happen (and the the application has to update all of its references manually)?
  - chrisseaton 7y ago
    As described on the other side of this thread, it’s done through virtual memory - the virtual address of the object doesn’t need to change, so no need to realloc.
scott_s 7y ago
Memory allocators for manual memory management could return memory asynchronously in a separate thread as well. The call to free() is only required to update some internal bookkeeping in the memory allocator's internal data structures. A separate thread could easily monitor when the data structures that hold raw pages from the OS are completely free, and return them to the OS.
- thedance 7y ago
  That's what tcmalloc does, at least if you set TCMALLOC_RELEASE_RATE.
  - scott_s 7y ago
    I don't think that's completely true. The value TCMALLOC_RELEASE_RATE controls how often tcmalloc returns memory back to the OS, but I don't believe it uses a separate thread for that task.
    - thedance 7y ago
      Hrmm, you’re right. This seems to be among the gratuitous differences between internal and open source tcmalloc.
      - alexhutcheson 7y ago
        Have you seen the recently updated GitHub project: https://github.com/google/tcmalloc https://github.com/google/tcmalloc
ahartmetz 7y ago
About Boehm GC, somebody told me a story about using it at his job for a highly technical simulation program that they sell... it worked unless the customer had data that fooled the GC into thinking it was seeing pointers in data that wasn't pointers, so it never freed memory. I guess it was in 32 bits with much smaller address space. They ended up switching to manual memory management, which wasn't significantly more complicated (in C++). Such are the tradeoffs with a conservative garbage collector. I would avoid Boehm GC (and other conservative GCs) in almost all situations.
- DmitryOlshansky 7y ago
  Have been writing in D that has conservative GC for years. Yes, on 32-bit platform false pointers are a problem esp as you get closer to 1g for instance. On the other hand on 64-bit I’ve never seen it at all. The chance of arbitrary long/double to point to some object in the heap area is 1/2^32 smaller and that turns the problem from common nuisance to purely theoretical problem.
- throwaway_pdp09 7y ago
  I agree. @camgunz' post is very naive. I never use a tool unless I understand it, and having read up on various GCs, conservative GCs are not something I could ever trust in production. False pointers cause leaks, and if the pointer graph is highly interconnected as happens with functional programs, then boom. In non-FP programs there's less risk but it's just not worth it I feel.
kllrnohj 7y ago
GCs by and large are tuned to have a very high amount of spare free memory that they don't return to the OS because GC'd languages by & large churn through memory allocations at a much higher rate. There are arguments that GCs can be faster, yes, but that speed almost always comes with an increase in memory usage not a reduction. After all asynchronous periodic collection must necessarily increase the transient working set of memory used over immediate synchronous collection. The advantages of a GC here in typical contexts are that GC'd languages usually allow for compaction which can reduce fragmentation. But this isn't an inherent benefit of a GC. You can have a GC'd language where you don't get this benefit, though, it's not an inherent property of the GC itself. For example D is a GC'd language, but because D's allocations are allowed to interop with C libraries you can no longer do compaction. There's thoughts on how you could do it with automatic pining but it's not done currently. But either way it's really the lack of raw pointers that make compaction possible, not whether or not you have a GC.

chrisseaton 7y ago

It’s the fact that automatic memory memory management can defragment through moving that is key. But there are also some manual memory managers that can defragment through moving as well - even some compatible with the malloc interface.

mschwaig 7y ago
I fully agree that moving is key. Just to further clarify the terms if someone is looking for more info on this: In the context of system memory people mostly refer to this as compaction and not defragmentation.
mschwaig 7y ago
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.
camgunz 7y ago
Oh yeah, I mean anything you can do automatically you can do manually. A core benefit of GC is you can have pretty complex memory management techniques that run more or less totally transparently. You can leverage generations (or defragmentation) to keep allocation latency low, etc.
astrobe_ 7y ago
How does this work? Is the application required to call realloc() on its object in order to let the defragmentation happen (and the the application has to update all of its references manually)?
- chrisseaton 7y ago
  As described on the other side of this thread, it’s done through virtual memory - the virtual address of the object doesn’t need to change, so no need to realloc.

scott_s 7y ago

Memory allocators for manual memory management could return memory asynchronously in a separate thread as well. The call to free() is only required to update some internal bookkeeping in the memory allocator's internal data structures. A separate thread could easily monitor when the data structures that hold raw pages from the OS are completely free, and return them to the OS.

thedance 7y ago
That's what tcmalloc does, at least if you set TCMALLOC_RELEASE_RATE.
- scott_s 7y ago
  I don't think that's completely true. The value TCMALLOC_RELEASE_RATE controls how often tcmalloc returns memory back to the OS, but I don't believe it uses a separate thread for that task.
  - thedance 7y ago
    Hrmm, you’re right. This seems to be among the gratuitous differences between internal and open source tcmalloc.
    - alexhutcheson 7y ago
      Have you seen the recently updated GitHub project: https://github.com/google/tcmalloc https://github.com/google/tcmalloc

ahartmetz 7y ago

About Boehm GC, somebody told me a story about using it at his job for a highly technical simulation program that they sell... it worked unless the customer had data that fooled the GC into thinking it was seeing pointers in data that wasn't pointers, so it never freed memory. I guess it was in 32 bits with much smaller address space. They ended up switching to manual memory management, which wasn't significantly more complicated (in C++). Such are the tradeoffs with a conservative garbage collector. I would avoid Boehm GC (and other conservative GCs) in almost all situations.

DmitryOlshansky 7y ago
Have been writing in D that has conservative GC for years. Yes, on 32-bit platform false pointers are a problem esp as you get closer to 1g for instance. On the other hand on 64-bit I’ve never seen it at all. The chance of arbitrary long/double to point to some object in the heap area is 1/2^32 smaller and that turns the problem from common nuisance to purely theoretical problem.
throwaway_pdp09 7y ago
I agree. @camgunz' post is very naive. I never use a tool unless I understand it, and having read up on various GCs, conservative GCs are not something I could ever trust in production. False pointers cause leaks, and if the pointer graph is highly interconnected as happens with functional programs, then boom. In non-FP programs there's less risk but it's just not worth it I feel.

kllrnohj 7y ago

GCs by and large are tuned to have a very high amount of spare free memory that they don't return to the OS because GC'd languages by & large churn through memory allocations at a much higher rate. There are arguments that GCs can be faster, yes, but that speed almost always comes with an increase in memory usage not a reduction. After all asynchronous periodic collection must necessarily increase the transient working set of memory used over immediate synchronous collection. The advantages of a GC here in typical contexts are that GC'd languages usually allow for compaction which can reduce fragmentation. But this isn't an inherent benefit of a GC. You can have a GC'd language where you don't get this benefit, though, it's not an inherent property of the GC itself. For example D is a GC'd language, but because D's allocations are allowed to interop with C libraries you can no longer do compaction. There's thoughts on how you could do it with automatic pining but it's not done currently. But either way it's really the lack of raw pointers that make compaction possible, not whether or not you have a GC.