C: realloc behavior

Xyne · 2010-08-06 16:47:05

From http://www.gnu.org/s/libc/manual/html_n … -Size.html

documenter wrote:

void * realloc (void *ptr, size_t newsize)
The realloc function changes the size of the block whose address is ptr to be newsize.
Since the space after the end of the block may be in use, realloc may find it necessary to copy the block to a new address where more free space is available. The value of realloc is the new address of the block. If the block needs to be moved, realloc copies the old contents.
If you pass a null pointer for ptr, realloc behaves just like 'malloc (newsize)'. This can be convenient, but beware that older implementations (before ISO C) may not support this behavior, and will probably crash when realloc is passed a null pointer.

(The emphasis is my own.)

When increasing the size of a block of memory using realloc, it obviously checks if there is enough contiguous space after the current block and if there is, it just expands it, otherwise it allocates a new block of the desired size then copies over the elements of the existing block before freeing the old block.

Is there any way to implement a custom version of realloc that would do the following instead:
* check if the current block can be expanded
* if yes, expand it and return the current address
* if no, allocate a new block and return the new address, without copying the data or freeing the old block

The reason that I would want to do this is to avoid unnecessary copying. I've created a circular buffer and when expanding the buffer size. I need to use a circular shift to align the existing elements to the beginning of the linear memory block. If the block is simply expanded then there is no issue as I have to shift them in situ anyway, but if a new block is allocated, I would want to handle the copying myself so that I can both copy and align the data in the same operation. Let me try to make it clear with an example:

#################
# Initial State #
#################

# 5-element memory block containing elements a-e
[d|e|a|b|c] 
     ^         # current position in circular buffer, i.e. the "beginning"


###############################################
# Expansion To 10 Elements By Expanding Block #
###############################################
[d|e|a|b|c]

# step 1: circular-shift in situ
[a|b|c|d|e]

# step 2: realloc
[a|b|c|d|e|?|?|?|?|?]

# a-e are copied once during the circular shift.
# Steps 1 & 2 are invertible.


####################################################
# Expansion To 10 Elements By Allocating New Block #
####################################################
[d|e|a|b|c]

# step 1: circular-shift in situ
[a|b|c|d|e]

# step 2: realloc
[a|b|c|d|e]   [?|?|?|?|?|?|?|?|?|?]

# step 3: copy to new block (done by realloc)
[a|b|c|d|e]   [a|b|c|d|e|?|?|?|?|?]

# a-e are copied twice: once during the circular shift, then again when moving them to the new block.
# What I would want to do instead is this:

[d|e|a|b|c]

# step 1: realloc
[d|e|a|b|c]   [?|?|?|?|?|?|?|?|?|?]

# step 2: combined circular shift and copy to the new address
[d|e|a|b|c]   [a|b|c|d|e|?|?|?|?|?]

Admittedly I have no working knowledge of how the system does with this behind the scenes. Maybe it just remaps the memory itself without copying the elements, in which case there would be no need to do this. I found some implications of this while searching but just as many that suggest that it really does flip all those bits around.

drcouzelis · 2010-08-06 18:49:45

I was going to suggest you download the GCC source code, copy the "realloc" function, and remove the "copy" part.

Then I tried to do that myself. I downloaded the GCC source code and searched through it. My goodness, I can hardly find any C code in all of that C code.

I don't think my idea would work anyway, because the realloc function may be implemented differently on different architectures and operating systems.

tavianator · 2010-08-06 18:55:35

The real question is, are you absolutely sure you need this much efficiency? Does copying twice actually cause any measurable slowdown, and if so, is it a noticeable slowdown? Implementing this optimization will increase your code complexity, possibly for no good reason.

However, to see if there is a slowdown with the normal realloc() method, you have to implement the optimized way anyway (to get a baseline). So, here's how you do it:

Don't use malloc/realloc for the buffer, as there is no way to get realloc to not move your buffer. Instead, use mmap() with MAP_ANONYMOUS, and the linux-specific mremap() call to determine if the mapping can grow in-place. This call will fail (by returning MAP_FAILED) if the memory mapping needs to be moved. In that case, do another mmap() to get a larger buffer, and do the copying yourself.

mremap() also supports an MREMAP_MAYMOVE flag, which will cause it to behave like realloc(). Importantly, I'm pretty sure that all this will change is the virtual address of the mapping, while keeping the physical pages in the same place, thus avoiding doing any actual copying. The kicker is that for large areas of allocated memory (above MMAP_THRESHOLD, which defaults to 128kB), realloc() will call mremap() anyway, so you may undertake this whole exercise and find that performance didn't change very much, because the implementation never really changed .

tom5760 · 2010-08-06 19:06:19

drcouzelis wrote:

I was going to suggest you download the GCC source code, copy the "realloc" function, and remove the "copy" part.
Then I tried to do that myself. I downloaded the GCC source code and searched through it. My goodness, I can hardly find any C code in all of that C code.
I don't think my idea would work anyway, because the realloc function may be implemented differently on different architectures and operating systems.

Kinda off-topic, but the function would be defined in glibc not gcc.

EDIT: Its on line 3746 of malloc/malloc.c

Last edited by tom5760 (2010-08-06 19:10:27)

Xyne · 2010-08-06 19:23:28

@drcouzelis
I tried to find the underlying code too without success (I gave up after a few minutes as it seemed that anything I found would be implementation-specific and thus non-portable).

@tavianator
I don't need it and I doubt that the change would even be noticeable (for what I have in mind at least). It is mostly just to satisfy my own curiosity. As for complexity, I think that if it's modularized properly then it won't matter

I'll look into mmap & co. as suggested.

Thanks for the replies.

drcouzelis · 2010-08-06 19:47:01

tom5760 wrote:

Kinda off-topic, but the function would be defined in glibc not gcc.
EDIT: Its on line 3746 of malloc/malloc.c

Good find! I'm always mixing up "glibc" and "Glib". Maybe now I won't be able to forget the difference between the two.

That function isn't too hard to understand.

I have never seen such mangled name mangling. O_o

saline · 2010-08-06 20:30:26

I think I just gave myself some homework.

Arch Linux

#1 2010-08-06 16:47:05

C: realloc behavior

#2 2010-08-06 18:49:45

Re: C: realloc behavior

#3 2010-08-06 18:55:35

Re: C: realloc behavior

#4 2010-08-06 19:06:19

Re: C: realloc behavior

#5 2010-08-06 19:23:28

Re: C: realloc behavior

#6 2010-08-06 19:47:01

Re: C: realloc behavior

#7 2010-08-06 20:30:26

Re: C: realloc behavior

Board footer