Re: resizing an array, is there a better way?
Jens.Toerring_at_physik.fu-berlin.de
Date: 08/05/04
- Next message: Mabden: "Re: What is the Point of Pointer's"
- Previous message: Mabden: "Re: Null pointers"
- In reply to: Keith Thompson: "Re: resizing an array, is there a better way?"
- Next in thread: Keith Thompson: "Re: resizing an array, is there a better way?"
- Reply: Keith Thompson: "Re: resizing an array, is there a better way?"
- Reply: CBFalconer: "Re: resizing an array, is there a better way?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 4 Aug 2004 22:58:06 GMT
Keith Thompson <kst-u@mib.org> wrote:
> mwojcik@newsguy.com (Michael Wojcik) writes:
>> In article <cem5in$4pe$2@news6.svr.pol.co.uk>, "Malcolm"
>> <malcolm@55bank.freeserve.co.uk> writes:
>> >
>> > "Jack Klein" <jackklein@spamcop.net> wrote in message
>> > >
>> > > > However this is not really much improvement, because
>> > > > internally realloc() usually allocates a new area of memory
>> > > > and then copies.
>> > >
>> > > Maybe it does, maybe it does not. In any case, even if it does
>> > > require copying it is quite possible that it will use a mechanism more
>> > > efficient than the OP's for loop.
>> > >
>> > In practise realloc() will usually be obliged to perform a copy.
>>
>> That's a dubious assumption. There are allocation schemes which
>> over-allocate areas (typically rounding them up to a power of two);
>> realloc under such a scheme might well be able to simply extend the
>> "in use" portion of the block in many cases.
>>
>> In some implementations, allocated blocks might be scattered through
>> a large virtual memory space such that they can be trivially extended.
>>
>> In short, you *don't know* what realloc does.
> I just did an experiment. I wrote a small program that initially sets
> a pointer to the result of malloc(1), then repeatedly sets to the
> result of realloc with successively larger values (1, 2, 3, ...).
> When I iterate from 1 to 1000000, the pointer value only changes a few
> times for small values. On one implementation, the value changes only
> when realloc() is called with a size of 13; on another, it changes at
> 9, 17, 25, and 33. For all other sizes, all the way up to a megabyte,
> it just extends the existing region of memory; presumably no copying
> is done.
> If I add a call to malloc(1) before each realloc() (with no
> corresponding free()), the pointer value changes much more often on
> one implementation, but not on the other. Probably the small
> allocation is (at least sometimes) done just after the existing block,
> preventing it from being expanded; on the other implementation, it
> looks like the small allocation happens to be done just *before* the
> existing block, allowing it to expand.
> All this is, of course, extremely system-specific. Michael is quite
> correct: you *don't know* what realloc does.
System-specific or not, would you be prepared to tell which implemen-
tations you were testing that with?
Using your program on gcc (on Linux) exhibits the interesting property
that as the number of bytes you realloc() increases the less often it
needs to move the block. And when it gets slightly above 128 kB it does
not move the block anymore - that's probably due to, as I learned just
recently, its switching the method for memory allocation above 128 kB
(from sbrk() to mmap()).
> Here's the program. One caveat: the "ptr != prev" comparison probably
> invokes undefined behavior when realloc() moves the memory block and
> ptr becomes invalid.
As far as I understand the constraints, comparing pointers for equality
or inequality is absolutely ok, only trying to establish a relation like
that one is larger than the other gets you into muddy waters.
Regards, Jens
-- \ Jens Thoms Toerring ___ Jens.Toerring@physik.fu-berlin.de \__________________________ http://www.toerring.de
- Next message: Mabden: "Re: What is the Point of Pointer's"
- Previous message: Mabden: "Re: Null pointers"
- In reply to: Keith Thompson: "Re: resizing an array, is there a better way?"
- Next in thread: Keith Thompson: "Re: resizing an array, is there a better way?"
- Reply: Keith Thompson: "Re: resizing an array, is there a better way?"
- Reply: CBFalconer: "Re: resizing an array, is there a better way?"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
