Thread

1. Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Merlin Moncure <mmoncure@gmail.com> — 2011-04-26T13:43:30Z

   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 helpful since ispell can allocate a lot of small nodes.
    *
    * We currently pre-zero all data allocated this way, even though some of it
    * doesn't need that.  The cpalloc and cpalloc0 macros are just documentation
    * to indicate which allocations actually require 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
   
   

2. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-04-26T16:28:20Z

   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
   
   

3. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-04-26T16:46:02Z

   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
   
   

4. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Merlin Moncure <mmoncure@gmail.com> — 2011-04-26T16:58:03Z

   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
   
   

5. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-04-26T17:41:04Z

   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
   
   

6. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-04-26T18:48:08Z

   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
   
   

7. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Merlin Moncure <mmoncure@gmail.com> — 2011-04-26T20:19:35Z

   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
   
   

8. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Merlin Moncure <mmoncure@gmail.com> — 2011-04-26T21:19:02Z

   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
   

9. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

   Tom Lane <tgl@sss.pgh.pa.us> — 2011-05-02T16:09:54Z

   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
   
   

10. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

    Merlin Moncure <mmoncure@gmail.com> — 2011-05-02T19:38:44Z

    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
    
    

11. Re: Bad COMPACT_ALLOC_CHUNK size in tsearch/spell.c?

    Tom Lane <tgl@sss.pgh.pa.us> — 2011-05-02T20:02:34Z

    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