Thread: 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
Attachment
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