Re: Proposal: block-based vector allocator

[Stefan Monnier]

>> Then I suggest you leave the code alone: we have no evidence that the
>> allocation pattern of vectors is any different than what malloc was
>> designed for, and the malloc library has seen many years of engineering
>> and tweaking, so you're very unlikely to do better than it does.
> At least for the vector allocation, I did it in a few days, if you believe
> in my numbers and byte-force-recompile as a representative benchmark.

I'm not convinced your result is because your code does better than
malloc.  Instead I expect it's because it avoids the mem_node overhead.
Recompiling and trying again without conservative stack scanning should
factor out this effect.

I'm still curious why you have a "order608" for 4KB blocks, since
dividing the 4KB block into 608 would leave you with a lot of padding at
the end and reducing the number of distinct "orders" should
reduce fragmentation.

>> Then you're doing it wrong: do it the way Lisp_Strings are handled
>> (i.e. with compaction).
> Although some designs makes it pretty hard, compaction is orthogonal to
> an allocation, and allocator I'm proposing can be enhanced to support
> compaction.

You can't do compaction without changing the Lisp_Vector's layout
(adding an indirection, as is done for Lisp_Strings).

>> None of this is related to the GC speed anyway.
> Wrong. Among others, good design might (and should) try to improve the
> spatial locality of allocated objects, thus giving less data cache misses
> and so better speed. It's very hard to predict how marking traversal
> accesses the memory, and locality of this procedure is known to be very
> poor. But, for example, sweeping of block-packed data is definitely
> faster than sweeping the same amount of data randomly dispersed
> among the heap.

I thought we agreed that GC performance is not a concern here.
Of course, every change to the layout can impact the performance of the
GC.  Have you measured the impact of your code on GC performance?



        Stefan