|  | Internal implementation of realloc | | |
| | | Kislay |  |
|  Posted: Wed Sep 03, 2008 4:26 am Post subject: Internal implementation of realloc |  |
How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ? |
| |
| | | Ian Collins | |
| | Posted: Wed Sep 03, 2008 4:26 am Post subject: Re: Internal implementation of realloc | |
Kislay wrote:
| Quote: | How is realloc implemented internally ?
|
The same answers that were given to the earlier thread 'printf' apply.
--
Ian Collins. |
| |
| | | pete | |
| | Posted: Wed Sep 03, 2008 4:26 am Post subject: Re: Internal implementation of realloc | |
Kislay wrote:
| Quote: | How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ?
|
Copied.
| Quote: | In the second case , wouldn't this method be inefficient if the old
region was large ?
|
It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.
Expanding a linked list to N nodes,
would more likely be an O(N) operation.
--
pete |
| |
| | | Malcolm McLean | |
| | Posted: Wed Sep 03, 2008 5:41 pm Post subject: Re: Internal implementation of realloc | |
"Kislay" <kislaychandra@gmail.com> wrote in message
| Quote: | How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?
Pseudo code |
get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block
You can implement a rather inefficient realloc() with simply a
getblocksize() function. If you can peek into the internals of the malloc(0
system, you can extend the blocks if possible, which avoids the copy.
--
Free games and programming goodies.
LINK |
| |
| | | Richard Tobin | |
| | Posted: Wed Sep 03, 2008 8:35 pm Post subject: Re: Internal implementation of realloc | |
In article <VpidnTREQMMtvSPVnZ2dnUVZ_gednZ2d@earthlink.com>,
pete <pfiland@mindspring.com> wrote:
| Quote: | In the second case , wouldn't this method be inefficient if the old
region was large ?
It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.
|
If you can find any real implementation with this behaviour,
I'll be very surprised.
-- Richard
--
Please remember to mention me / in tapes you leave behind. |
| |
| | | Guest | |
| | Posted: Wed Sep 03, 2008 10:32 pm Post subject: Re: Internal implementation of realloc | |
| |  | |
On Sep 3, 3:41 pm, "Malcolm McLean" <regniz...@btinternet.com> wrote:
| Quote: | "Kislay" <kislaychan...@gmail.com> wrote in message
How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?
Pseudo code
get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block
You can implement a rather inefficient realloc() with simply a
getblocksize() function. If you can peek into the internals of the malloc(0
system, you can extend the blocks if possible, which avoids the copy.
--
Free games and programming goodies.http://www.personal.leeds.ac.uk/~bgy1mm
|
It has been a long, long time since I looked at the code but I believe
that some sort of realloc is the basic mechanism for buffer managment
in emacs-- I could be wrong |
| |
| | | pete | |
| | Posted: Wed Sep 03, 2008 10:43 pm Post subject: Re: Internal implementation of realloc | |
| | | |
Richard Tobin wrote:
| Quote: | In article <VpidnTREQMMtvSPVnZ2dnUVZ_gednZ2d@earthlink.com>,
pete <pfiland@mindspring.com> wrote:
In the second case , wouldn't this method be inefficient if the old
region was large ?
It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.
If you can find any real implementation with this behaviour,
I'll be very surprised.
|
I was thinking of a situation where the array becomes
expanded as the data comes in, ultimately to N elements;
not a situation where realloc is called only once.
That's the situation with the typical use of
Richard Heathfield's fgetline function at
LINK
That's also the situation with the typical use of my get_line function
LINK
and also with the evil Dr. Sosman's getline function,
LINK
It makes sense to me that as the array grows,
each subsequent realloc should take proportionally longer.
And that when you have K*N allocations,
the total building of the N element array
becomes an O(N*N) operation.
--
pete |
| |
| | | Eric Sosman | |
| | Posted: Thu Sep 04, 2008 12:14 am Post subject: Re: Internal implementation of realloc | |
Malcolm McLean wrote:
| Quote: |
"Kislay" <kislaychandra@gmail.com> wrote in message
How is realloc implemented internally ? If there is not enough memory
in place to allocate , is new memory allocated somewhere else and the
2 regions linked via a pointer , OR , is the old region copied to a
place where there is enough memory to fit both old and new region ? In
the second case , wouldn't this method be inefficient if the old
region was large ?
Pseudo code
get block size
get space after block
if(blocksize + space < new blocksize)
adjust block
else
allocate new block
copy data
free old block
|
It's true that realloc() *could* be implemented this way,
but I've never seen such an implementation. Market forces
seem to favor a higher QoI.
--
Eric Sosman
esosman@ieee-dot-org.invalid |
| |
| | | Gene | |
| | Posted: Thu Sep 04, 2008 1:43 am Post subject: Re: Internal implementation of realloc | |
| | | |
On Sep 3, 8:43 pm, pete <pfil...@mindspring.com> wrote:
| Quote: | Richard Tobin wrote:
In article <VpidnTREQMMtvSPVnZ2dnUVZ_gedn...@earthlink.com>,
pete <pfil...@mindspring.com> wrote:
In the second case , wouldn't this method be inefficient if the old
region was large ?
It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.
If you can find any real implementation with this behaviour,
I'll be very surprised.
I was thinking of a situation where the array becomes
expanded as the data comes in, ultimately to N elements;
not a situation where realloc is called only once.
That's the situation with the typical use of
Richard Heathfield's fgetline function LINK
That's also the situation with the typical use of my get_line LINK
and also with the evil Dr. Sosman's getline function,http://www.cpax.org.uk/prg/portable/c/libs/sosman/index.php
It makes sense to me that as the array grows,
each subsequent realloc should take proportionally longer.
And that when you have K*N allocations,
the total building of the N element array
becomes an O(N*N) operation.
|
This is why nearly all code for expanding an array "on demand"
_multiplies_ the size of the array by a factor greater than 1 (2 being
very popular) rather than adding a constant. It isn't hard to prove
that the amortized cost of copying with this method is O(N) for an
array that has grown to size N. |
| |
| | | Richard Tobin | |
| | Posted: Thu Sep 04, 2008 12:02 pm Post subject: Re: Internal implementation of realloc | |
In article <DaadnTMMO6iBsiLVnZ2dnUVZ_szinZ2d@earthlink.com>,
pete <pfiland@mindspring.com> wrote:
| Quote: | It could be.
It could make expanding an array to N elements,
into an O(N*N) operation.
If you can find any real implementation with this behaviour,
I'll be very surprised.
I was thinking of a situation where the array becomes
expanded as the data comes in, ultimately to N elements;
not a situation where realloc is called only once.
|
So was I.
You would get your N^2 behaviour if every realloc() required copying,
or if a fixed fraction of them did. But a sensible implementation
will not work like that. It will allocate in such a way that there is
more spare space with large allocations.
If the block sizes it uses increase by a constant factor (power-of-two
is a special case of this), then the copying required will be such
that it's still O(N).
-- Richard
--
Please remember to mention me / in tapes you leave behind. |
| |
| Page 1 of 3 .:. Goto page 1, 2, 3 Next | |
|
|
