Re: Proposal: block-based vector allocator

[Stefan Monnier]

>> The cost (CPU or memory, it doesn't matter much here, and we ignore
>> fragmentation) of allocating a vector is something like:
>> and CPU costs alike, ignores fragmentation):
>> - outside of a vector-block: malloc + mem_node
>> - inside a vector-block: vector-block + frac * (malloc + mem_node + 
>> a-bit-more)
>> where "frac" is a fraction that's more or less vector-size /
>> VECTOR_BLOCK_BYTES.
>> So for small vectors, "frac" is small and since we expect the
>> vector-block overhead to be significantly smaller than malloc+mem_node
>> we win.  But past a certain value of "frac", we're better off allocating
>> outside of a vector-block.  As I said, I don't know exactly where that
>> threshold is, but using VECTOR_BLOCK_BYTES / 2 should be good enough.

> OK.  This is a bit more complicated since we need some tricks to
> manage free space larger than (approx.) VECTOR_BLOCK_BYTES / 2.

I do not know what you're referring to.  Could you explain what you mean
by that? ....aahhh.... right, I see what you mean now.
I don't think fragmenting the left-over space is a good idea.  Just keep
your free lists for free chunks of size [VECTOR_BLOCK_BYTES/2
... VECTOR_BLOCK_BYTES], even if you never allocate a vector of that
size from those free lists.  I.e. keep the old code, just change the part
that chooses between "allocate via vector-block or allocate directly" to
use a VECTOR_BLOCK_BYTES/2 threshold.

> +    roundup_size = COMMON_MULTIPLE (sizeof (Lisp_Object),
> +#ifdef USE_LSB_TAG
> +    8 /* Helps to maintain alignment constraints.  */
> +#else
> +    1 /* If alignment doesn't matter, should round up
> +      to sizeof (Lisp_Object) at least.  */
> +#endif
> +    )

All I wanted was a comment explaining the choice of 8.  I think using
8 for all cases is perfectly fine (I don't know of any significant case
where the above expression will give something smaller anyway).

> +/* If VECTOR is too large to join a free list at once,
> +   this function splits it to smaller fragments. Next,
> +   all fragments are set up to appropriate free lists.  */
> +
> +static inline void
> +setup_free_space (struct Lisp_Vector *vector)
> +{
> +  ptrdiff_t index, usedbytes, restbytes;
> +
> +  for (restbytes = vector->header.next.nbytes;
> +       restbytes >= VBLOCK_BYTES_MIN; restbytes -= usedbytes)
> +    {
> +      eassert (restbytes % roundup_size == 0);
> +      usedbytes = min (restbytes, VBLOCK_BYTES_MAX);
> +
> +      /* Do not create too small fragments.  */
> +      if (restbytes - usedbytes > 0)
> +     while (restbytes - usedbytes < VBLOCK_BYTES_MIN)
> +       usedbytes -= roundup_size;
> +
> +      SETUP_ON_FREE_LIST (vector, usedbytes, index);
> +      vector = ADVANCE (vector, usedbytes);
> +    }
> +
> +  /* Make sure all space is used.  */
> +  eassert (restbytes == 0);
> +}

This should not have any loop and should not fragment.  I.e. it should
be barely more than SETUP_ON_FREE_LIST (vector, restbytes, index).

The rest looks good now.  Feel free to install it,


        Stefan