Re: Pre-alloc ListCell's optimization

* Alvaro Herrera (alvherre(at)commandprompt(dot)com) wrote:
> I think what this patch is mainly missing is a description of how the
> new allocation is supposed to work, so that we can discuss the details
> without having to reverse-engineer them from the code.

Sure, sorry I didn't include something more descriptive previously.

Basically, I added a ListCell array into the List structure and then
added a bitmap to keep track of which positions in the array were
filled. I added it as an array simply because makeNode() assumes the
size of a List is static and doesn't call through new_list() or
anything. When a new ListCell is needed, it'll check if there's an
available spot in the array and use it if there is. If there's no
more room left, it'll just fall back to doing a palloc() for the
ListCell. On list_delete(), it'll free up the spot that was used by
that cell. One caveat is that it won't try to clean up the used spots
on a list_truncate (since you'd have to traverse the entire list to
figure out if anything getting truncated off is using a spot in the
array). Of course, if you list_truncate to zero, you'll just get NIL
back and the next round through will generate a whole new/empty List
structure for you.

An alternative approach that I was already considering would be to
just allocate ListCell's in bulk (kind of a poor-man's slab allocator, I
believe). To do that we'd have to make the bitmap be a variable length
array of bitmaps and then have a list of pointers to the ListCell block
allocations. Seems like that's probably overkill for this, however.
The idea for doing this was to address the case of small lists having to
go through the palloc() process over and over. We'd be penalizing those
again if we add a lot of complexity so that vary large lists don't have
to palloc() as much.

Thanks

Stephen