gc

gc copied to clipboard

Forgive me if this is already addressed in the proposal, but I was wondering whether there's wider interest in supporting array allocation specifically as a means of achieving spatial locality for otherwise-independent objects.

Here's a concrete example: I want to allocate a linked list with a known initial length. The simplest way to do that would be to allocate each node struct individually, link them together, and return the head.

Allocating each node individually imposes no constraints on the memory layout, so in order to ensure spatial locality of nodes, it could be advantageous to instead allocate all the nodes in a contiguous array, then link them together as if they were independent, and return the head node, such that on function return there are no remaining references to the array itself; just references to individual elements. Unless / until the list is re-arranged post-allocation, it should have caching performance more similar to an array during traversal, while retaining linked list semantics.

I don't see any details in the proposal about how the GC should handle this situation. Ideally, it would be able to independently recycle nodes (as they are dropped from the linked list) that were originally allocated as part of the array (which is no longer referenced). This would prevent the pathological edge case where a massive initial array only has a single remaining node in use, but the GC cannot recycle all the unused nodes until the last node is unreferenced.

Would it make sense to spec this behavior? I suppose it would be tantamount to requiring that the elements of an array do not implicitly reference their container, and that an array can be garbage-collected without collecting it's elements.

Under the current spec, allocating an array of references doesn't imply that the objects that the array refers to are allocated in a contiguous block, just that the pointers to those objects are in a contiguous block. There's not currently any way to allocate a contiguous array of structs, although we have discussed that after the MVP we might allow allocating structs-of-arrays and arrays-of-structs: https://github.com/WebAssembly/gc/blob/main/proposals/gc/Post-MVP.md#nested-data-structures.

That won't quite be the transparent performance improvement you want, though, because the interior pointers to the individual structs will be a different type than normal non-interior references.

I think it's best if we leave locality, at least as far as this example goes, up to the GC allocation and reclamation algorithms. In particular, many GCs will use bump-pointer allocation, so allocating N structs of type S in quick succession will result in them being next to each other in memory. A non-moving collector will leave them in-place and moving collectors (evacuation) will often use breadth-first traversal (i.e. a queue) for this reason, relocating the referent objects in an array will result in them being together, in order (provided they weren't reached and relocated by another path).

As Thomas says, we might have nested aggregates in the future, but barring that, I could imagine a struct.multi_new instruction that allocates a big contiguous block of structs that are nevertheless referred to by an array of references; sort of a bulk-allocation. Such an instruction would be a performance hint and not introduce any new semantics.

Closing this because we won't address it in the MVP, but PRs adding ideas to the post-MVP doc would be very welcome.