5

My understanding of realloc was that, if memory was available contiguously beyond the point allocated, it can try to extend the current allocation without copying.

While reading this https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md I came to know that most allocators avoid inplace reallocation

. Many memory allocators do not support in- place reallocation, although most of them could. This comes from the now notorious design of realloc() to opaquely perform either in-place reallocation or an allocate-memcpy-deallocate cycle. Such lack of control subsequently forced all clib-based allocator designs to avoid in-place reallocation, and that includes C++'s new and std:allocator.

As answered in another question (Why is there no reallocation functionality in C++ allocators?) about the lack of reallocators in C++ where the accepted answer mentions that such an allocator would have prohibited realloc use form C library but does not answer why not try to make realloc that expands the current memory if possible?

Community
  • 1
  • 1
sukunrt
  • 1,523
  • 10
  • 20
  • 5
    Probably because it's a whole lot of work for not much benefit, and it makes things more confusing, especially when you have constructors and destructors in the mix (for example, you'd get two different behaviors depending on whether it reallocated or not, because under one scenario a bunch of copy constructors and destructors would get invoked, whereas in the other they wouldn't). – Michael Aaron Safyan Aug 31 '14 at 20:59
  • @MichaelAaronSafyan So is the fact that realloc is a C library function which doesn't ensure that destructors would be called if the data was completely copied to some other place the reason that for resizing we do something like call malloc for appropriate sized data, copy the objects and call destructors on the previous allocation? – sukunrt Aug 31 '14 at 21:07
  • I don't know the definitive reason behind why things were designed the way they were. I am merely speculating on it and some obvious difficulties / obstacles that might have prevented it. – Michael Aaron Safyan Aug 31 '14 at 21:12
  • @MichaelAaronSafyan: If only I had a penny for every time someone answered a "Why does X not do Y?" with a knee-jerk "Because it's a lot of work for no benefit"... – user541686 Sep 01 '14 at 03:29
  • possible duplicate of [Why is there no reallocation functionality in C++ allocators?](http://stackoverflow.com/questions/3105001/why-is-there-no-reallocation-functionality-in-c-allocators) – M.M Sep 01 '14 at 06:21
  • If you have a comment about an accepted answer from another question, post it as a comment to that answer. I don't see how this question is substantially different to the linked question. – M.M Sep 01 '14 at 06:22

3 Answers3

9

Why not make one? Actually, there are proposals to do exactly that:

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • 2
    +1 for not trying to justify the status quo the way everyone does. – user541686 Sep 01 '14 at 03:35
  • @Mehrdad The question title is "Why do C++ allocators avoid in-place reallocation" , the other answers are answering this question. – M.M Sep 01 '14 at 06:19
0

There's really very little advantage to attempting to perform "in-place reallocation", because the common case is for there to be no room to expand an allocated memory block in-place. Any good allocator will aim to avoid fragmentation as one of its top priorities - failure to do so can result in catastrophic explosion of memory requirements and quickly lead to allocation failure, which most programs are poorly equipped to handle, especially in a 32-bit address space. And in order to avoid fragmentation, an allocator needs to follow a best-fit strategy.

So, for a good real-world allocator, the main case where in-place expansion is possible is when there were no previously-freed blocks available, and allocation took place at the "top of the heap". For very simple programs, where only a single allocation is being resized with no other allocations taking place in between those resizings, there is a potentially serious performance advantage to be had from in-place expansion. This is plausible in single-threaded programs written in C, but not so much for C++ programs where there's hidden dynamic allocation going on in almost everything you do.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
  • If there's so little advantage then why do you think there are proposals for adding the feature? – user541686 Sep 01 '14 at 04:31
  • 1
    Do you honestly think something has to be a good idea in order for somebody to propose it? – R.. GitHub STOP HELPING ICE Sep 01 '14 at 04:37
  • 1
    @R..: Check the names on the proposals and the discussion thereof before you jump to conclusions. – Ben Voigt Sep 01 '14 at 05:13
  • @BenVoigt: But do you have an objection to my reasoning rather than just an appeal to authority? Perhaps there's something I'm missing, but my experience working on allocation has been that opportunities for in-place expansion are rare except under artificial conditions or when the overall allocator strategy is bad. – R.. GitHub STOP HELPING ICE Sep 01 '14 at 05:18
  • @R..: Depends on the person? Some people *do* have a tendency to propose better ideas than others. Your objection is just a handwavy "that's not the common case" when in reality it seems like people have had enough of a problem with it for them to think it's worth fixing, so evidently it's common enough to matter. Unless you think those people don't know how to measure performance correctly, you can't really claim they're wrong. – user541686 Sep 01 '14 at 06:10
  • @R.. My point is when you say it's not the common case that you get an extension, does allowing it come as a cost to common case. If yes, could you please link to some resource? – sukunrt Sep 01 '14 at 06:42
  • @sukunrt: The main cost is that adding such a feature precludes having the C++ allocator (`new`/etc.) run on top of the existing C allocator API (`malloc`) unless a new function (`tryrealloc`) is added. And adding new functions to the underlying C allocator API is costly because it breaks everything for people who are using custom `malloc` implementations, until they go add the new function. For example if you're using a custom `malloc` and it doesn't have the new `tryrealloc` needed for this new proposed C++ feature, the original `tryrealloc` in libc will get called, ... – R.. GitHub STOP HELPING ICE Sep 01 '14 at 21:21
  • ...and horrible memory corruption will result when memory allocated by one allocator implementation gets passed to the other one's functions. Note that the reason `tryrealloc` would be needed is that, if you're trying to expand an array in-place, you need to know whether to make copies and call the dtors **before** the old array ceases to exist. But with `realloc`, success is atomic with invalidating the old allocation (aside: this is the case even if it happens to get the same address for the new one!). – R.. GitHub STOP HELPING ICE Sep 01 '14 at 21:24
  • Well a common pattern of allocation for `std::vector` is that many elements are being added in a loop, with all the resizes that implies: in this case the allocated block is very often the "top of the heap", so it isn't that unusual. Furthermore, modern multi-threaded allocators usually use a thread-local cache, so multi-threading doens't really break this: from a performance angle the allocators work mostly as if they had independent allocators per-thread (with the occasional request to the "global" allocator for more memory). – BeeOnRope Oct 19 '17 at 18:55
-1

The problem with extending the current memory block is that the allocator needs to know the state of the adjacent memory block.

Supposed the allocator manages blocks of a fixed size. Let's say all managed blocks are powers of 2. In that case, the allocator would extend a block to the nearest power of two. Anything else would require copying.

Supposed that the allocator manage variable sized blocks using queues? Then it would be very difficult to find the adjacent block.

As indicates above, reallocs are not needed that frequently. It is generally more efficient just to grab a new block and copy.

user3344003
  • 20,574
  • 3
  • 26
  • 62
  • -1 this isn't a reason. If an allocator can't reallocate in place then it won't. There's no need to disallow a feature just because it might not be used. – user541686 Sep 01 '14 at 03:35
  • I did not say it would be disallowed. I am saying that under some methods of memory allocation, reallocating is impracticable to they simply don't do it. – user3344003 Sep 01 '14 at 03:38
  • lol it looks like I accidentally upvoted you instead of downvoting you. – user541686 Sep 01 '14 at 04:29
  • What? I only see one upvote, and that's mine. Not sure what "others" you're referring to. – user541686 Sep 01 '14 at 06:07
  • 1
    You're saying if you use queues supporting such a feature would be difficult, while you can do so with something like a buddy system. So is there a reason to prefer queues? – sukunrt Sep 01 '14 at 06:36
  • Most allocators use a strategy of calling something like `mmap` (or `VirtualAlloc` on Windows) for large blocks - in this case it is straightforward to ask the OS to extend the mapping, so `realloc` tends to at least have a reasonable implementation for large blocks. – BeeOnRope Oct 19 '17 at 18:53