* Alvaro Herrera (alvhe...@commandprompt.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
signature.asc
Description: Digital signature