Re: Pre-alloc ListCell's optimization

On Thu, May 26, 2011 at 11:57 AM, Stephen Frost <sfrost(at)snowman(dot)net> wrote:
> * Tom Lane (tgl(at)sss(dot)pgh(dot)pa(dot)us) wrote:
>> I'm worried that this type of approach would
>> bloat the storage required in those cases to a degree that would make
>> the patch unattractive.
>
> While I agree that there is some bloat that'll happen with this
> approach, we could reduce it by just having a 4-entry cache instead of
> an 8-entry cache.  I'm not really sure that saving those 64 bytes per
> list is really worth it though.

First off this whole direction seems a bit weird to me. It sounds like
you're just reimplementing palloc inside the List data structure with
its allocator and everything. Why not just improve the memory
allocator in palloc instead of layering a second one on top of it?

But assuming there's an advantage I've missed there's another
possibility here: Are most of these small lists constructed with
list_makeN? In which case maybe the trick would be to special case the
initial contents by hard coding a variable sized array which
represents the first N elements and is only constructed when the list
is first constructed with its initial values. So a list make with
list_make3() would have a 3 element array and then any further
elements added would be in the added cons cells. If any of those were
removed we would decrement the count but leave the array in place.

This would reduce the overhead of any small static lists that aren't
modified much which is probably the real case we're talking about.
Things like operator arguments or things constructed in the parse
tree.

The cost would be the risk of bugs that only occur when something is
passed a 2-element list that was made with list_make2() but not one
made by list_make1() + list_append() or vice versa.

This has the side benefit of allowing an arbitrarily large initial
array (well, as large as the length field for the array size allows)
if we wanted to have something like list_copy_static() which made a
list that was expected not to be modified a lot subsequently and might
as well be stored in a single large array.

But all this seems odd to me. The only reason for any of this is for
api convenience so we can pass around lists instead of passing arrays.
If the next links are really a big source of overhead we should just
fix our apis to take arrays of the right length or arrays with a
separate length argument.

Or if it's just palloc we should fix our memory allocator to behave
the way the callers need it to. Heikki long ago suggested adding a
stack allocator for the parser to use for its memory context to reduce
overhead of small allocations which won't be freed until the context
is freed for example.

--
greg