Do you have some benchmarks demonstrating your claim?
> ...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 shows the change adding prefetching to the marking phase (https://github.com/ocaml/ocaml/pull/9934 was done earlier for sweeping). There are some benchmarks in the thread/linked from the thread.
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.
A copying collector has to trace through the whole graph to find everything reachable. The tracing order is usually going to be depth first. (It's the easiest to code if you're using recursion and therefore maintaining state with the runtime's stack, but even with an explicit stack you'll want to push and pop the end for locality.) Which means that objects arranged into a linked list will be visited in list order, and you generally copy as you visit an object for the first time. So... reordering live objects relative to each other "just happens". Even if it's a doubly-linked list, since the back pointers have already been visited and so don't matter.
This is less true if your objects have a lot of other pointers in them. But that's just saying that if your object graph isn't a list, then it won't end up laid out in list order. It'll still end up in DFS order according to the true graph.