Re: Proposal: block-based vector allocator

[Dmitry Antipov]

On 12/07/2011 05:52 PM, Stefan Monnier wrote:

> 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.

> Yes.  And the design I propose is one that has proved to be such a good
> balance.

The design itself can't prove anything. The devil is in the details, and
implementation is the only thing that matters. My favorite GC textbook
(http://www.amazon.com/gp/product/1420082795) describes a tens of
very good designs, but doesn't provide any ready-to-use recipes to help
us solve memory usage issues.

> 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.

> 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.

Dmitry