5 ms·

Speaking of garbage collectors, I had a thought the other day, wondering if performance could have a huge linear speed up if the graph of object pointers was st

Speaking of garbage collectors, I had a thought the other day, wondering if performance could have a huge linear speed up if the graph of object pointers was stored compactly in memory, separated from the rest of an application's memory. The object graph could be stored in a succinct compressed format to reduce it's size as much as possible, compared to actual 64 bit pointers. Then the GC algorithm could crawl the graph much much faster by virtue of needing to access far fewer memory pages, and increased likelihood that those pages will be in a fast cpu cache most of the time.

smaddox 7y ago
Luajit does something vaguely like this: http://wiki.luajit.org/New-Garbage-Collector#arenas_block-mark-bitmaps http://wiki.luajit.org/New-Garbage-Collector#arenas_block-ma... It doesn't need to access the actual data when sweeping.
- ufo 7y ago
  The latest version of LuaJIT is still using the old GC. As far as I know the new GC design is in limbo, with no plan to implement it in the near future.
- tom_mellior 7y ago
  IIUC that only moves the mark bits out of the objects. It still has to access the objects while marking. I think the parent proposed moving pointers out of the objects, so you wouldn't even have to touch the user's objects while marking.
tom_mellior 7y ago
How do you envision compressing the graph? One thing you can do, if you know that all your objects will live in one arena, and the maximum size of that arena is <= 2^N objects for some N, is to store "pointers" as N-bit rather than 64-bit values. Java does this for N = 32: https://wiki.openjdk.java.net/display/HotSpot/CompressedOops https://wiki.openjdk.java.net/display/HotSpot/CompressedOops
- etaioinshrdlu 7y ago
  Yes storing them as just smaller integers is a main thing. Frequently referenced pointers could also be given an even shorter coding, kind of like entropy coding.
  - abecedarius 7y ago
    I thought about tackling this while visiting Recurse Center last year. My angle was that this could probably be most practical for a language like Erlang which comes closest to never mutating any runtime datastructure. (You might think of languages like Haskell first, but lazy evaluation cashes out to mutations in the implementation.) I seem to have misplaced my notes, or I'd link to them. Haven't gotten to trying to do this yet. Someone at RC suggested using succinct data structures and I spent a little while studying them, but they seemed to me like they'd have more niche-y properties than a more obvious approach would.
kjeetgill 7y ago
This is a really cool idea. Just spitballing, but I suspect the issue would be that you now lose the objects locality when reading/following/writing references in conjunction with data. The GC algorithm will be crawling much less than your program will hopefully so it might be a net loss. Just speculation!
- etaioinshrdlu 7y ago
  Yes I agree. Perhaps the pointers should be stored twice in memory? With the updates to the compact graph being done asynchronously buffered by a shared lock-free queue? This is a mouthful and starting to sound like an obnoxious design.
- CoolGuySteve 7y ago
  Presumably the compact representation would be hot in the cache all the time due to frequent access but it would take up otherwise available cache space.

smaddox 7y ago

Luajit does something vaguely like this: http://wiki.luajit.org/New-Garbage-Collector#arenas_block-mark-bitmaps http://wiki.luajit.org/New-Garbage-Collector#arenas_block-ma... It doesn't need to access the actual data when sweeping.

ufo 7y ago
The latest version of LuaJIT is still using the old GC. As far as I know the new GC design is in limbo, with no plan to implement it in the near future.
tom_mellior 7y ago
IIUC that only moves the mark bits out of the objects. It still has to access the objects while marking. I think the parent proposed moving pointers out of the objects, so you wouldn't even have to touch the user's objects while marking.

tom_mellior 7y ago

How do you envision compressing the graph? One thing you can do, if you know that all your objects will live in one arena, and the maximum size of that arena is <= 2^N objects for some N, is to store "pointers" as N-bit rather than 64-bit values. Java does this for N = 32: https://wiki.openjdk.java.net/display/HotSpot/CompressedOops https://wiki.openjdk.java.net/display/HotSpot/CompressedOops

etaioinshrdlu 7y ago
Yes storing them as just smaller integers is a main thing. Frequently referenced pointers could also be given an even shorter coding, kind of like entropy coding.
- abecedarius 7y ago
  I thought about tackling this while visiting Recurse Center last year. My angle was that this could probably be most practical for a language like Erlang which comes closest to never mutating any runtime datastructure. (You might think of languages like Haskell first, but lazy evaluation cashes out to mutations in the implementation.) I seem to have misplaced my notes, or I'd link to them. Haven't gotten to trying to do this yet. Someone at RC suggested using succinct data structures and I spent a little while studying them, but they seemed to me like they'd have more niche-y properties than a more obvious approach would.

kjeetgill 7y ago

This is a really cool idea. Just spitballing, but I suspect the issue would be that you now lose the objects locality when reading/following/writing references in conjunction with data. The GC algorithm will be crawling much less than your program will hopefully so it might be a net loss. Just speculation!

etaioinshrdlu 7y ago
Yes I agree. Perhaps the pointers should be stored twice in memory? With the updates to the compact graph being done asynchronously buffered by a shared lock-free queue? This is a mouthful and starting to sound like an obnoxious design.
CoolGuySteve 7y ago
Presumably the compact representation would be hot in the cache all the time due to frequent access but it would take up otherwise available cache space.