3 ms·

Even if memory was packed by a GC, linked lists still have to pay the cost of allocating and garbage collecting every cell of memory individually. I doubt a GC

Even if memory was packed by a GC, linked lists still have to pay the cost of allocating and garbage collecting every cell of memory individually. I doubt a GC would solve linked lists’ woes. Do you have some benchmarks demonstrating your claim?

throwawaymaths 4y ago
Erlang GC is pretty good, plus there are some nice highly local allocators
- josephg 4y ago
  Be that as it may, it'll still take a benchmark to convince me.
Jach 4y ago
There are also prefetch instructions. I listened to https://www.youtube.com/watch?v=SetLtBH43_U https://www.youtube.com/watch?v=SetLtBH43_U recently (transcript: https://signalsandthreads.com/memory-management/ https://signalsandthreads.com/memory-management/), part of it talked about some work in OCaml's GC. > ...each individual memory request that’s not in cache still has to wait the full 300 cycles. But if we can get 10 of them going at the same time, then we can be hitting a new cache line every 30 cycles. I mean, that’s not as good as getting one every 16 cycles, but it’s close. You’re actually able to get to a reasonable fraction of the raw memory bandwidth of the machine while just traversing randomly over this huge one gigabyte heap https://github.com/ocaml/ocaml/pull/10195 https://github.com/ocaml/ocaml/pull/10195 shows the change adding prefetching to the marking phase (https://github.com/ocaml/ocaml/pull/9934 https://github.com/ocaml/ocaml/pull/9934 was done earlier for sweeping). There are some benchmarks in the thread/linked from the thread.
- deleted 4y ago
  [deleted]
tsimionescu 4y ago
I don't have a benchmark, but it's important to remember that GCs only scan live objects, and they always have to scan all live objects; while allocation is normally an extremely simple instruction (bump the memory pointer). It's true though that scanning a live linked list would be expected to be slower than scanning a live array (though some optimized scanning strategies may be possible). Overall I couldn't tell what the impact on overall performance would be, but I can tell you for sure that de-allocating an N-element linked list or array are both O(1) operations for a copying garbage collector (which are the most common kinds of compacting GCs), since they simply will never reach nor copy any of the elements.

throwawaymaths 4y ago

Erlang GC is pretty good, plus there are some nice highly local allocators

josephg 4y ago
Be that as it may, it'll still take a benchmark to convince me.

Jach 4y ago

There are also prefetch instructions. I listened to https://www.youtube.com/watch?v=SetLtBH43_U https://www.youtube.com/watch?v=SetLtBH43_U recently (transcript: https://signalsandthreads.com/memory-management/ https://signalsandthreads.com/memory-management/), part of it talked about some work in OCaml's GC. > ...each individual memory request that’s not in cache still has to wait the full 300 cycles. But if we can get 10 of them going at the same time, then we can be hitting a new cache line every 30 cycles. I mean, that’s not as good as getting one every 16 cycles, but it’s close. You’re actually able to get to a reasonable fraction of the raw memory bandwidth of the machine while just traversing randomly over this huge one gigabyte heap https://github.com/ocaml/ocaml/pull/10195 https://github.com/ocaml/ocaml/pull/10195 shows the change adding prefetching to the marking phase (https://github.com/ocaml/ocaml/pull/9934 https://github.com/ocaml/ocaml/pull/9934 was done earlier for sweeping). There are some benchmarks in the thread/linked from the thread.

deleted 4y ago
[deleted]

tsimionescu 4y ago

I don't have a benchmark, but it's important to remember that GCs only scan live objects, and they always have to scan all live objects; while allocation is normally an extremely simple instruction (bump the memory pointer). It's true though that scanning a live linked list would be expected to be slower than scanning a live array (though some optimized scanning strategies may be possible). Overall I couldn't tell what the impact on overall performance would be, but I can tell you for sure that de-allocating an N-element linked list or array are both O(1) operations for a copying garbage collector (which are the most common kinds of compacting GCs), since they simply will never reach nor copy any of the elements.