On Wed, Jan 13, 2010 at 10:04 AM, Marvin Humphrey <mar...@rectangular.com> wrote:
> Both mild and aggressive over-allocation solve that problem, but aggressive > over-allocation also involves significant RAM costs. Where the best balance > lies depends on how bad the reallocation performance is in relation to the > cost of insertion. An eighth seems pretty good. Doubling seems too high. > 1.5, dunno, seems like it could work. According to this superficially > credible-seeming comment at stackoverflow, that's what Ruby does: > > http://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array/1100449#1100449 Yeah I guess between 1.125 and 1.5 seems acceptable? 1.5 feels a bit high to me though. If forced to pick, in general, I tend to prefer burning CPU not RAM, because the CPU is often a one-time burn, whereas RAM ties up storage for indefinite amounts of time. >> But, you have to do something different when targetSize < 8, else that >> formula doesn't grow. > > That's right, it was by design. For small sizes, things get tricky. > > If it's a byte array, you definitely want to round up to the size of a > pointer, and as we enter the era of ubiquitous 64-bit processors, rounding up > to the nearest multiple of 8 seems proper. > > But what about arrays of objects? Would we really want every two-element > array to reserve space for 8 objects? I suppose we could pass in the expected element size... but that's probably over complicating things. > The way I've got this handled in a forthcoming patch to Lucy is to trust the > user about the size they want in most cases and count on them to add the logic > for small sizes (as was done in TermBufferImpl.java). The Grow() methods of > CharBuf, ByteBuf, and VArray obey the exact amount -- if you want an > overallocation, you'll invoke the over-estimator on the argument you supply to > Grow(). It's just the incremental appends like VArray's Push(), or CharBuf's > Cat_Char() that trigger the automatic over-allocation internally. > >> Also, I think for smallish sizes we want faster than 12.5% growth, >> because the constant-time cost of the mechanics of doing a >> reallocation are at that point relatively high (wrt the cost of >> copying the bytes over to the new array). > > But is that important if in most cases where it will grow incrementally, > you've already overallocated manually? I think this function should still aim to handle the smallish values, ie, we shouldn't require every caller to have to handle the small values themselves. Callers that want to override the small cases can still do so... I do agree that we should at least round up to 4 or 8 byte boundary, but perhaps make it optional so we can turn it off for the array-of-pointers cases. Mike --------------------------------------------------------------------- To unsubscribe, e-mail: java-dev-unsubscr...@lucene.apache.org For additional commands, e-mail: java-dev-h...@lucene.apache.org
