Re: Buffer growing strategy?

On Sep 17, 6:02 pm, "christian.bau" <christian....@xxxxxxxxxxxxxxxxxx>
wrote:
On Sep 18, 1:38 am, websnarf <websn...@xxxxxxxxx> wrote:
Exercise to the reader: a) Show that this solution is can be as bad as
O(MAXLENGTH**2) in terms of memory copy performance.  b) Why would a
system vendor implement a tight and "chop-and-reliquish" strategy for
realloc()?  Is it possible for a compiler vendor to implement a realloc
() that guarantees a O(log(MAXLENGTH)) performance for this sort of
problem while making efficient use of memory?

There's a simple rule for optimisation: Don't optimise unless you have
measured it and found that optimising is needed.

Indeed, but that's just a corollary for what H.L. Mencken said: "For
every complex problem, there is an answer that is clear, simple--and
wrong." And you definitely got that last part as I will explain:

[...] In my test, I did one
billion realloc's, with the size growing from one byte to one billion
byte, and the time was 55 ns per realloc (time printed every 1 million
iterations, so it could easily be that a few reallocs took
significantly longer), with no apparent growth as the block size got
bigger.

Not surprising; most memory allocator strategies will behave well in
view of trivial scenarios. But if you do a *sequence* of mallocs and
then try to resize them at random, then tell me what kind of
performance you get.

Anyway, if _you_ can find a clever strategy to choose sizes for
allocations, why shouldn't the author of the library?

The library author doesn't know which trade off the application
developer has in mind. If the system library favors performance then
it *cannot* favor memory tightness, and does not allow the application
developer to work around the system's implementation. On the other
hand if the system library provider provides a memory efficient
implementation, then either of Jef Driesen's first two strategies
works very well no matter what kind of realloc implementation has been
provided. In other words, the app developer can deal with performance
on his own.

[...] He's in a much better position.

How can a position of ignorance be a better position? The system
library provider can never know which trade off the application
developer wants.

[...] For example, he can allocate more memory than needed
for a malloc block to make realloc faster, but cut away from that
block when needed.

That is rarely relevant. You just have to implement a next block
pointer and see if the adjacent block is unallocated and contains
enough space to be extended into. That's not the issue. The issue is
how often the next block is really going to be allocated or not. With
tight allocation strategies, which are the norm, you can never know.
If you preallocate too much space, then you will just run out of space
faster (as if you had less ram in your system than you actually paid
for and installed). That's not something that can ever be worked
around, and I would never want to use a system that implemented such a
trade off.

Even as an app developer, if you want to use a strategy where you are
willing to eat excess memory to improve allocation performance, you
are going to want to use a pool based system, which is a totally
different strategy (that is very bad for re-use but good for
allocation speed) and needs to be custom developed by the app
developer anyways.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
.

Relevant Pages

  • Re: malloc
    ... If I use both the calls ie. malloc and realloc together, how the allocated memory will be ... Again, an old pointer value, valid for the first allocation of p, will ...
    (comp.lang.c)
  • Re: resizing an array, is there a better way?
    ... >> a large virtual memory space such that they can be trivially extended. ... > when realloc() is called with a size of 13; ... > allocation is done just after the existing block, ...
    (comp.lang.c)
  • Re: realloc, copy and VM
    ... > When you realloc for more size, it may be necessary to allocate a new block, ... > copy memory and deallocate the old, for example if there is not enough free ... That *is* extending the original block. ... via lazy allocation and copy-on-write.) ...
    (comp.lang.c)
  • Re: when can realloc fail?
    ... will the allocation of ptr be freed? ... about what the Standard requires/allows. ... memory pointed to by p, basing the claim on the deallocation ... Don't call realloc() with the second ...
    (comp.lang.c)
  • Re: How to get the memory block size which allocated by new operator?
    ... memory that not released.When allocate memory by new operator,I will ... set of memory management routines that are far superiour to malloc, realloc, ... Programmers know when they're combining multiple outputs into a single ... NULL is stuffed into pbBuf when realloc returns, destroying the only pointer ...
    (microsoft.public.vc.language)