Re: Proposal: block-based vector allocator

[Paul Eggert]

On 05/31/2012 06:44 AM, Dmitry Antipov wrote:
> Awaiting for more comments on this.

Thanks for looking into this.  Here's a brief low-level
review.  I have only read the patch; I haven't tried to
build or run it, or to think through the high-level
stuff.

Have you done some performance analysis on
typical 64- and 32-bit hosts?  Has this been published
somewhere?  Should be in the ChangeLog entry or whatnot.

> +#define VECTORS_PER_BLOCK_MAX \
> +  (VECTOR_BLOCK_BYTES / sizeof (struct vectorlike_header))

This macro is never used.  And surely the value is wrong, since
empty vectors are never put into blocks; it would be
(VECTOR_BLOCK_BYTES / sizeof (struct Lisp_Vector)).

Check to see whether there are other macros not used.
Configure with --enable-gcc-warnings; you may find other stuff.

> +/* Round up X to nearest mult-of-Y, assuming Y is a power of 2.  */
> +
> +#define roundup_powof2(x,y) (((x) + (y) - 1) & ~((y) - 1))

Need parentheses around "(y) - 1", in case x+y overflows but
x+(y-1) does not.

> +    /* On a 32-bit system, rounding up vector size (in bytes) up
> +       to mult-of-8 helps to maintain mult-of-8 alignment.  */
> +    roundup_size = 8

This alignment is needed only if USE_LSB_TAG, right?  If so, the
roundup should occur only on such hosts.

> +#define VECTOR_BLOCK_BYTES \
> +  (VECTOR_BLOCK_SIZE - roundup_powof2 (sizeof (void *), roundup_size))

A simpler and clearer way to state this might be (VECTOR_BLOCK_SIZE -
sizeof (void *) & (roundup_size - 1)), or perhaps round_down
(VECTOR_BLOCK_SIZE - sizeof (void *)) if you'd rather encapsulate that
into a macro.  Here I'm assuming roundup_size is 1 if USE_LSB_TAG is
not defined.

The above suggests that "roundup_size" should be renamed to
"vector_alignment" or something like that, since it can be used
to round down as well as up.

> +#define VECTOR_MAX_FREE_LIST_INDEX ((VECTOR_BLOCK_BYTES / roundup_size) + 1)

Surely this should be ((VECTOR_BLOCK_BYTES + (roundup_size - 1)) / 
roundup_size).

> +/* When the vector is on a free list, vectorlike_header.SIZE is set to
> +   this special value ORed with vector's memory footprint size.  */
> +
> +#define VECTOR_FREE_LIST_FLAG \
> +  (((ptrdiff_t) ~0) & ~(ARRAY_MARK_FLAG | PSEUDOVECTOR_FLAG | \
> +                     (VECTOR_BLOCK_SIZE - 1)))

The "(ptrdiff_t) ~0) &" is a no-op and should be removed.

> +#define ADVANCE(v,nbytes) \
> +  (struct Lisp_Vector *) ((unsigned char *) (v) + (nbytes))

No need for the "unsigned char" here, or elsewhere in the code.
Since the code doesn't char whether signed or unsigned char is used
just use "char".

> +
> +/* Common shortcut to setup vector on a free list.  */
> +
> +#define SETUP_ON_FREE_LIST(v,nbytes,index) do { \
> +  (v)->header.size = VECTOR_FREE_LIST_FLAG | (nbytes); \
> +  eassert ((nbytes) % roundup_size == 0); \
> +  (index) = (nbytes) / roundup_size; \
> +  eassert ((index) < VECTOR_MAX_FREE_LIST_INDEX); \
> +  (v)->header.next.vector = vector_free_lists[(index)]; \
> +  vector_free_lists[(index)] = (v); } while (0)

Space after comma.  Reindent the do { ... }, e.g., like CHECK_RANGED_INTEGER.
Since roundup_size is a power of 2, it looks like the code should be
using its log base 2, so that the division can be turned into a shift.
No need for parentheses in "[(index)]".

> +  large_vectors = NULL;

Can't this be removed?  large_vectors must be NULL here.

> +  for (i = 0; i < VECTOR_MAX_FREE_LIST_INDEX; i++)
> +    vector_free_lists[i] = NULL;

Likewise.

> +  eassert (nbytes > sizeof (struct vectorlike_header) &&
> +        nbytes <= VECTOR_BLOCK_BYTES);

Put && at start of line, and use "<" rather than ">" so that
it looks like "A < N && N <= B".

Be consistent about putting binary operators at the start of the next
line.


> +  /* First, try to allocate from a free list
> +     contains vectors of the requested size.  */

"contains"?  I can't parse that.  Maybe you meant "containing"?

> +  /* Next, check free lists contains larger vectors.  Since we will
> +     split the result, we should have remaining space large enough
> +     to use for one-slot vector at least.  */

Likewise.


> +  for (index = (nbytes + sizeof (struct Lisp_Vector)) / roundup_size;
> +       index < VECTOR_MAX_FREE_LIST_INDEX; index++)
> +    if (vector_free_lists[index])
> +      {
> +     /* This vector is larger than it was requested.  */

Remove "it was".

> +     /* Excessive bytes are used for the smaller vector,
> +        which should be set on an appropriate free list.  */

"Excessive" -> "Excess"

> +#define VECTOR_SIZE(v) ((v)->header.size & PSEUDOVECTOR_FLAG ? \
> +  (PSEUDOVECTOR_SIZE_MASK & (v)->header.size) : (v)->header.size)

Put "?" at start of next line, and use proper indentation.
No need for parentheses around if-part.

> +#define VECTOR_IN_BLOCK(vector,block) \
> +  (unsigned char *) (vector) <= (block)->data + \
> +    VECTOR_BLOCK_BYTES - sizeof (struct Lisp_Vector)

Put "+" at start of next line.  Parenthesize the entire definiens.

> +  for (i = 0; i < VECTOR_MAX_FREE_LIST_INDEX; i++)
> +    vector_free_lists[i] = NULL;

Use memset.

> +           if ((vector->header.size & VECTOR_FREE_LIST_FLAG) == 
> +               VECTOR_FREE_LIST_FLAG)

"==" at start of next line (here, and in other places).

> +       if (bprev)
> +         bprev->next = block->next;
> +       else
> +         vector_blocks = block->next;

Change bprev's type to be of struct vector_block **, and have it
point to the address of the pointer to be stepped on, rather than
to the block containing the 'next' field.  I.e., bprev is initially
&vector_blocks, and thereafter it's &block->next.  Then the above code
can be simplified to:

      *bprev = block->next;

Use the same trick in the two or three other places that there is a
'prev' pointer.

> +  if (nbytes > VECTOR_BLOCK_BYTES)
> +    {
> +      p = (struct Lisp_Vector *) lisp_malloc (nbytes, MEM_TYPE_VECTORLIKE);
> +      p->header.next.vector = large_vectors;
> +      large_vectors = p;
> +    }
> +  else
> +    /* Rounding is to preserve alignment.  */
> +    p = allocate_vector_from_block (roundup_powof2 (nbytes, roundup_size));

Reverse the condition and swap the then-and-else.

> +    /* When the vector is allocated from a vector block, NBYTES is used
> +       if the vector is not on a free list, and VECTOR is used otherwise.
> +       For large vector-like objects, BUFFER or VECTOR is used as a pointer
> +       to the next vector-like object.  It is generally a buffer or a 
> +        Lisp_Vector alias, so for convenience it is a union instead of a
> +        pointer: this way, one can write P->next.vector instead of ((struct
> +        Lisp_Vector *) P->next).  */

Indent consistently.