Обсуждение: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

I was poking around in the allocator code out of curiosity after
reading the thread 'Improving the memory allocator', and noticed the
following in spell.c:

/** "Compact" palloc: allocate without extra palloc overhead.** Since we have no need to free the ispell data items
individually,there's* not much value in the per-chunk overhead normally consumed by palloc.* Getting rid of it is
helpfulsince ispell can allocate a lot of small nodes.** We currently pre-zero all data allocated this way, even though
someof it* doesn't need that.  The cpalloc and cpalloc0 macros are just documentation* to indicate which allocations
actuallyrequire zeroing.*/
 
#define COMPACT_ALLOC_CHUNK 8192        /* must be > aset.c's allocChunkLimit */
#define COMPACT_MAX_REQ         1024    /* must be < COMPACT_ALLOC_CHUNK */

In aset.c, we have,

#define ALLOC_MINBITS           3       /* smallest chunk size is 8 bytes */
#define ALLOCSET_NUM_FREELISTS  11
#define ALLOC_CHUNK_LIMIT       (1 << (ALLOCSET_NUM_FREELISTS-1+ALLOC_MINBITS))

1 << 13 gives 8192 if my math is correct.

Note the comment, 'must be > aset.c's allocChunkLimit'.  Is the
comment wrong or the assumption wrong?

merlin

Merlin Moncure <mmoncure@gmail.com> writes:
> I was poking around in the allocator code out of curiosity after
> reading the thread 'Improving the memory allocator', and noticed the
> following in spell.c:

> #define COMPACT_ALLOC_CHUNK 8192        /* must be > aset.c's allocChunkLimit */

> In aset.c, we have,

> #define ALLOC_MINBITS           3       /* smallest chunk size is 8 bytes */
> #define ALLOCSET_NUM_FREELISTS  11
> #define ALLOC_CHUNK_LIMIT       (1 << (ALLOCSET_NUM_FREELISTS-1+ALLOC_MINBITS))

> 1 << 13 gives 8192 if my math is correct.

> Note the comment, 'must be > aset.c's allocChunkLimit'.  Is the
> comment wrong or the assumption wrong?

Hmm ... the idea behind that comment is evidently that it's best if the
blocks allocated by this code form independent malloc blocks in aset.c;
but right offhand I can't see why that'd be important.  It's obviously
not functionally necessary, since the code works as-is, and I don't
immediately see a reason to think that it'd be more efficient.  If
anything it might be best the way it is, with the allocation
corresponding to the largest allowable small-chunk size.

I'm thinking the comment is just brain fade ... which is annoying
because I have a feeling it's my own comment :-( ... but I'm darned
if I can reconstruct the reasoning for it now.
        regards, tom lane

I wrote:
> Hmm ... the idea behind that comment is evidently that it's best if the
> blocks allocated by this code form independent malloc blocks in aset.c;
> but right offhand I can't see why that'd be important.  It's obviously
> not functionally necessary, since the code works as-is, and I don't
> immediately see a reason to think that it'd be more efficient.  If
> anything it might be best the way it is, with the allocation
> corresponding to the largest allowable small-chunk size.

> I'm thinking the comment is just brain fade ... which is annoying
> because I have a feeling it's my own comment :-( ... but I'm darned
> if I can reconstruct the reasoning for it now.

After a bit longer, the reasoning came back to me ...

The key point here is that alloc requests larger than ALLOC_CHUNK_LIMIT
don't affect aset.c's other allocation behavior: it hands you out a
block gotten directly from malloc, end of story.  However, if you keep
on asking for chunks <= ALLOC_CHUNK_LIMIT, those will come out of larger
and larger malloc'd blocks.  That means larger and larger potential
wastage when you stop asking for chunks.  In normal usage this doesn't
matter a whole lot because if you stop asking for space in a context,
you're probably going to release it not long after that.  But ispell
is building a dictionary that will likely live for the duration of the
process, so if it wastes space comparable to the useful size of the
dictionary, that's a tad more annoying.

In short: the property suggested by the comment is meant to minimize
wasted memory, and we're not doing it right to achieve that.

Now on the other hand, it probably takes more cycles to build it using
a number of individual malloc calls than the way we're doing it now.
But since it's a once-per-process overhead, I'm thinking that's probably
a good tradeoff.

So now I think the comment is right and we need to bump up the value of
the constant.
        regards, tom lane

On Tue, Apr 26, 2011 at 11:46 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
>> Hmm ... the idea behind that comment is evidently that it's best if the
>> blocks allocated by this code form independent malloc blocks in aset.c;
>> but right offhand I can't see why that'd be important.  It's obviously
>> not functionally necessary, since the code works as-is, and I don't
>> immediately see a reason to think that it'd be more efficient.  If
>> anything it might be best the way it is, with the allocation
>> corresponding to the largest allowable small-chunk size.
>
>> I'm thinking the comment is just brain fade ... which is annoying
>> because I have a feeling it's my own comment :-( ... but I'm darned
>> if I can reconstruct the reasoning for it now.
>
> After a bit longer, the reasoning came back to me ...
>
> The key point here is that alloc requests larger than ALLOC_CHUNK_LIMIT
> don't affect aset.c's other allocation behavior: it hands you out a
> block gotten directly from malloc, end of story.  However, if you keep
> on asking for chunks <= ALLOC_CHUNK_LIMIT, those will come out of larger
> and larger malloc'd blocks.  That means larger and larger potential
> wastage when you stop asking for chunks.  In normal usage this doesn't
> matter a whole lot because if you stop asking for space in a context,
> you're probably going to release it not long after that.  But ispell
> is building a dictionary that will likely live for the duration of the
> process, so if it wastes space comparable to the useful size of the
> dictionary, that's a tad more annoying.
>
> In short: the property suggested by the comment is meant to minimize
> wasted memory, and we're not doing it right to achieve that.
>
> Now on the other hand, it probably takes more cycles to build it using
> a number of individual malloc calls than the way we're doing it now.
> But since it's a once-per-process overhead, I'm thinking that's probably
> a good tradeoff.
>
> So now I think the comment is right and we need to bump up the value of
> the constant.

right -- spell.c was deliberately trying to influence allocator
behavior.  Should it really do that though without direct
participation of some form? (like, exposing the allocation chunk size
macro?)  It seems a bit dodgy as it stands...

merlin

Merlin Moncure <mmoncure@gmail.com> writes:
> On Tue, Apr 26, 2011 at 11:46 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> After a bit longer, the reasoning came back to me ...

> right -- spell.c was deliberately trying to influence allocator
> behavior.  Should it really do that though without direct
> participation of some form? (like, exposing the allocation chunk size
> macro?)  It seems a bit dodgy as it stands...

Yeah, it's at the very least inadequately documented, because after
further poking around I remembered that there's a reason why the comment
says allocChunkLimit and not ALLOC_CHUNK_LIMIT.  Namely, that the
dictionary context that this stuff is being built in uses
ALLOCSET_SMALL_MAXSIZE which is only 8K, causing the active value of
allocChunkLimit to be less than that, which means the code actually *is*
operating as designed.  The chunks it gets will be separate malloc
blocks.

This means the relevant space-wastage danger is not the one I explained
earlier, but something else entirely.  There isn't a risk from wasting
leftover space in large malloc requests, because the small maxBlockSize
specified for dictionary contexts prevents that.  But suppose for
example that spell.c were using 4K instead of 8K here.  Because of
per-chunk overhead, those requests would consume just over half of each
malloc block made by aset.c, and it would never enlarge them because of
the small maxBlockSize.  So 4K requests would result in wasting almost
half the space in each malloc block.  Using a larger value guards
against that behavior.

So: code does what it's supposed to, but the comment sucks, and there's
definitely a lot of action-at-a-distance here considering that the
memory context creation with the use of ALLOCSET_SMALL_MAXSIZE is in
still a third file.

We could certainly stand to improve the comment.  I'm not sure whether
there's any good way to expose these considerations more directly in
the code.  Any ideas?

A different angle of attack on the issue is that aset.c's use of
exact-power-of-2 sizes for both malloc requests and the available space
in chunks is inefficient when maxBlockSize is constrained to be not much
larger than common chunk request sizes.  Maybe we should try to fix that
instead of asking other code to choose request sizes to dodge the
inefficiency.
        regards, tom lane

I wrote:
> A different angle of attack on the issue is that aset.c's use of
> exact-power-of-2 sizes for both malloc requests and the available space
> in chunks is inefficient when maxBlockSize is constrained to be not much
> larger than common chunk request sizes.  Maybe we should try to fix that
> instead of asking other code to choose request sizes to dodge the
> inefficiency.

After chewing on that thought for a bit, it seems like an easy fix is to
modify AllocSetContextCreate (around line 390 in HEAD's aset.c) so that
allocChunkLimit is not just constrained to be less than maxBlockSize,
but significantly less than maxBlockSize --- say an eighth or so.  When
using ALLOCSET_SMALL_MAXSIZE this would result in requests of 1K or more
being treated as separate malloc blocks, in turn guaranteeing that not
more than 1K of each 8K request block could go to waste in the face of a
stream of allocChunkLimit-sized requests.

Of course, this might just result in the fragmentation problem getting
tossed over the fence into malloc's playground ... but offhand it seems
that it would remove the issue that spell.c is concerned about.
        regards, tom lane

On Tue, Apr 26, 2011 at 1:48 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
>> A different angle of attack on the issue is that aset.c's use of
>> exact-power-of-2 sizes for both malloc requests and the available space
>> in chunks is inefficient when maxBlockSize is constrained to be not much
>> larger than common chunk request sizes.  Maybe we should try to fix that
>> instead of asking other code to choose request sizes to dodge the
>> inefficiency.
>
> After chewing on that thought for a bit, it seems like an easy fix is to
> modify AllocSetContextCreate (around line 390 in HEAD's aset.c) so that
> allocChunkLimit is not just constrained to be less than maxBlockSize,
> but significantly less than maxBlockSize --- say an eighth or so.  When
> using ALLOCSET_SMALL_MAXSIZE this would result in requests of 1K or more
> being treated as separate malloc blocks, in turn guaranteeing that not
> more than 1K of each 8K request block could go to waste in the face of a
> stream of allocChunkLimit-sized requests.
>
> Of course, this might just result in the fragmentation problem getting
> tossed over the fence into malloc's playground ... but offhand it seems
> that it would remove the issue that spell.c is concerned about.

well, +1 on any solution that doesn't push having to make assumptions
about the allocator from the outside.  your fix seems to nail it
without having to tinker around with the api which is nice. (plus you
could just remove the comment).

Some perfunctory probing didn't turn up any other cases like this.

merlin

On Tue, Apr 26, 2011 at 3:19 PM, Merlin Moncure <mmoncure@gmail.com> wrote:
> On Tue, Apr 26, 2011 at 1:48 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I wrote:
>>> A different angle of attack on the issue is that aset.c's use of
>>> exact-power-of-2 sizes for both malloc requests and the available space
>>> in chunks is inefficient when maxBlockSize is constrained to be not much
>>> larger than common chunk request sizes.  Maybe we should try to fix that
>>> instead of asking other code to choose request sizes to dodge the
>>> inefficiency.
>>
>> After chewing on that thought for a bit, it seems like an easy fix is to
>> modify AllocSetContextCreate (around line 390 in HEAD's aset.c) so that
>> allocChunkLimit is not just constrained to be less than maxBlockSize,
>> but significantly less than maxBlockSize --- say an eighth or so.  When
>> using ALLOCSET_SMALL_MAXSIZE this would result in requests of 1K or more
>> being treated as separate malloc blocks, in turn guaranteeing that not
>> more than 1K of each 8K request block could go to waste in the face of a
>> stream of allocChunkLimit-sized requests.
>>
>> Of course, this might just result in the fragmentation problem getting
>> tossed over the fence into malloc's playground ... but offhand it seems
>> that it would remove the issue that spell.c is concerned about.
>
> well, +1 on any solution that doesn't push having to make assumptions
> about the allocator from the outside.  your fix seems to nail it
> without having to tinker around with the api which is nice. (plus you
> could just remove the comment).
>
> Some perfunctory probing didn't turn up any other cases like this.

patch attached -- I did no testing beyond make check though.  I
suppose changes to the allocator are not to be take lightly and this
should really be tested in some allocation heavy scenarios.

merlin

Merlin Moncure <mmoncure@gmail.com> writes:
> On Tue, Apr 26, 2011 at 3:19 PM, Merlin Moncure <mmoncure@gmail.com> wrote:
>> On Tue, Apr 26, 2011 at 1:48 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>> After chewing on that thought for a bit, it seems like an easy fix is to
>>> modify AllocSetContextCreate (around line 390 in HEAD's aset.c) so that
>>> allocChunkLimit is not just constrained to be less than maxBlockSize,
>>> but significantly less than maxBlockSize --- say an eighth or so.

>> well, +1 on any solution that doesn't push having to make assumptions
>> about the allocator from the outside. �your fix seems to nail it
>> without having to tinker around with the api which is nice. (plus you
>> could just remove the comment).
>> 
>> Some perfunctory probing didn't turn up any other cases like this.

> patch attached -- I did no testing beyond make check though.  I
> suppose changes to the allocator are not to be take lightly and this
> should really be tested in some allocation heavy scenarios.

I did a bit of testing of this and committed it with minor adjustments.
        regards, tom lane

On Mon, May 2, 2011 at 11:09 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Merlin Moncure <mmoncure@gmail.com> writes:
>> On Tue, Apr 26, 2011 at 3:19 PM, Merlin Moncure <mmoncure@gmail.com> wrote:
>>> On Tue, Apr 26, 2011 at 1:48 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>>>> After chewing on that thought for a bit, it seems like an easy fix is to
>>>> modify AllocSetContextCreate (around line 390 in HEAD's aset.c) so that
>>>> allocChunkLimit is not just constrained to be less than maxBlockSize,
>>>> but significantly less than maxBlockSize --- say an eighth or so.
>
>>> well, +1 on any solution that doesn't push having to make assumptions
>>> about the allocator from the outside.  your fix seems to nail it
>>> without having to tinker around with the api which is nice. (plus you
>>> could just remove the comment).
>>>
>>> Some perfunctory probing didn't turn up any other cases like this.
>
>> patch attached -- I did no testing beyond make check though.  I
>> suppose changes to the allocator are not to be take lightly and this
>> should really be tested in some allocation heavy scenarios.
>
> I did a bit of testing of this and committed it with minor adjustments.

Thanks for the attribution -- I hardly deserved it.  One question
though: ALLOC_CHUNK_FRACTION was put to four with the language 'We
allow chunks to be at most 1/4 of maxBlockSize'.

further down we have:
"+    * too.  For the typical case of maxBlockSize a power of 2, the chunk size
+    * limit will be at most 1/8th maxBlockSize, so that given a stream of
+    * requests that are all the maximum chunk size we will waste at most
+    * 1/8th of the allocated space."

Is this because the divide by 2 right shift halves the amount of
wasted space, so that the maximum waste is in fact half again the
fraction?

merlin

Merlin Moncure <mmoncure@gmail.com> writes:
> On Mon, May 2, 2011 at 11:09 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I did a bit of testing of this and committed it with minor adjustments.

> Thanks for the attribution -- I hardly deserved it.  One question
> though: ALLOC_CHUNK_FRACTION was put to four with the language 'We
> allow chunks to be at most 1/4 of maxBlockSize'.

> further down we have:
> "+    * too.  For the typical case of maxBlockSize a power of 2, the chunk size
> +    * limit will be at most 1/8th maxBlockSize, so that given a stream of
> +    * requests that are all the maximum chunk size we will waste at most
> +    * 1/8th of the allocated space."

> Is this because the divide by 2 right shift halves the amount of
> wasted space, so that the maximum waste is in fact half again the
> fraction?

No, it's the overhead.  The patch as you submitted it was forcing
allocChunkSize down to 512, because after subtracting off the
per-malloc-block overhead and the per-palloc-chunk overhead, it came to
the (correct) conclusion that 1024 didn't quite fit 8 times into 8192.
I thought that was probably excessive, so I backed off the fraction.
        regards, tom lane