realloc is not your friend?

[KarlisRepsons]

So the contents of a vector get ALL copied when a memory reallocation happens. I wonder, why exactly did my book say, that realloc isn't my friend and for what reason it's not attempted to avoid copying, which takes time?

[Galik]

If you want to avoid copying you can pre-allocate your vector to be as large as it will become. Otherwise you could use a std::deque which does not copy elements when allocating more space.

[helios]

realloc() only offers the possibility of resizing, maybe. For example, according to C99, this is the correct realloc() implementation:

void *realloc(void *p,size_t s){
    void *r;
    r=malloc(s);
    if (!r)
        return r;
    memcpy(r,p,/*old size*/);
    free(p);
    return r;
}

[KarlisRepsons]

So there is no commonly used function in C/C++, which would in some way avoid copying contents when reallocation happens? Somehow it seems very credible, that some OS could provide something like that. Is it the case? (Or do I simply don't quite understand how memory gets assigned to a program, hmm...)

[karthick88]

I have a question here..

memcpy(r,p,/*old size*/);

why is this old size in comments?/

[firedraco]

Because you don't know how big the void* p is (or how to get it), but the OS does.

[karthick88]

@firedraco..

I agree but why is it given as a comment??

Question 1
========

And moreover if malloc is implented this way, what would happen if a programmer does this

int* p = malloc(5*sizeof(int))
realloc(p,3*sizeof(int))


Question 2
========

Where is the old size obtained before using it in memcpy??? should the comment replaced by
sizeof(p);

[helios]

I agree but why is it given as a comment?

I wrote it as a comment because a) the implementation details of how and where malloc() stores buffer sizes are irrelevant to the discussion and b) the standard doesn't define them, either way, so if I had put there anything in particular, I'd have been lying.

1. Memory leaks if the internal call to malloc() didn't fail. Aside from that, I see your point. That's something I overlooked while typing the post.

void *realloc(void *p,size_t s){
    size_t old;
    void *r;
    old=/*old size*/;
    if (old>=s)
        return p;
    r=malloc(s);
    if (!r)
        return r;
    memcpy(r,p,old);
    free(p);
    return r;
}

2. Depends on the implementation of malloc().

[kbw]

realloc really is not your friend

Steve Maguire's Writing Solid Code explains why realloc is horrible. The real problem is it does so much, and any combination of parameters is valid; you can pass zero and non-zero in any combination.

It does: malloc, free, shrink and relocate, where shrink would make an allocated block smaller and relocate would move to a new block.

His conclusion was that it was such a common source of error (because it is misunderstood) that it shouldn't be used directly. And I have to say, I agree.

[KarlisRepsons]

Still, why there doesn't seem to be any useful functions, which could shrink some buffer or add more space to it without making copy? It's too useless in practice because of, say, memory fragmentation or something else?

[helios]

Because memory doesn't work that way.

Suppose you have a buffer A that starts at 0x01 and another B that starts at 0x101. A can be enlarged only until its size reaches 0x100, at which point it will be adjacent to B. A cannot be further enlarged without moving B somewhere else, but that's impossible:
1. There's almost certainly pointers in the program that point to B. Moving it would make them invalid.
2. There's no telling whether there's enough room to move B somewhere else, even by a single byte.
3. Even if there is room, moving B might imply moving a third buffer C.
So the only solution when A needs to be bigger than 0x100 is to copy it somewhere else.

A possible, but highly impractical solution would be to give buffers their own address space, but this is incompatible with the C machine model. The environment would have to give out handles instead of actual pointers. Pointer arithmetic would be impossible because there would be no pointers, only handles and offsets to their buffers. Buffers would basically become in-memory files.
The whole thing would be even less efficient than what we have now. Mostly because accessing a buffer would no longer be an O(1) operation (or at least it would involve one or two extra levels of indirection). To have freely resizable buffers, the memory manager would have to turn memory into a virtual file system, and buffers would really be linked lists of smaller buffers (think files and clusters).

[KarlisRepsons]

Ok, thanks for that. However, it would need to be written for completion about why it's (apparently) impractical to have some advantages from the case when A's new enlarged size isn't larger than 0x100 or when it shrinks.