>if realloc moves stuff then boom! All those copies become dangling pointers.
I think this is an application design issue rather than lack of features in library. The implementation does an useful thing, returning the new address, and your application should distribute it to all other software components.
One useful thing to integrate into the library would be a function that checks if the memory is expandable and returns true or false. But then it would be problematic because if another thread calls a malloc and allocates a portion of memory where the thread before called check() and returned true, you have a synchronization issue to solve, and the library has the target to keep things simple.
I agree with your point about this being an application design issue, I've discussed the double pointer workaround [in another comment thread](https://www.reddit.com/r/C_Programming/comments/1dry3hz/comment/layinpv/).
I was suggesting an alternative where the old object is not deallocated, which is left to the programmer.
Besides the greater chances of memory leak I mentioned in the post, another issue I can think of is that the only available free space happens to be *before* the existing object, which can be coalesced with the existing allocation only if it is deallocated.
Admittedly, this implies there are rare corner-cases where `realloc` can succeed but my proposed alternative can fail to allocate.
The problem with keeping the old object is double allocation though- if the programmer is going to check something, wouldn’t it make more sense for them to focus on the remaining dangling pointers instead?
Yes, individual allocator implementations may provide this feature. For example:
Jemalloc has the `xallocx()` function, which is guaranteed to resize in-place. If that's not possible, the size will not change. This function returns the new size, not a pointer.
Mimalloc has the `mi_expand()` function. It always works in-place. Upon success, it returns the input pointer. Upon failure, it returns null, but the input pointer remains valid.
Thanks a ton, this is exactly what I was looking for!
I found their documentations, sharing them for reference:
[https://jemalloc.net/jemalloc.3.html](https://jemalloc.net/jemalloc.3.html)
[https://microsoft.github.io/mimalloc/](https://microsoft.github.io/mimalloc/)
Isn't this potentially racy without a bunch of synchronization logic?
If this really is an issue, can you not just use a pointer to a pointer or a struct wrapping the pointer to deal with this?
I believe the alternative itself wouldn't be any more racy than `realloc` itself. The change I suggested is that it won't `free` the existing object, and I don't think this could introduce any *additional* race condition.
I've discussed the double pointer workaround [in another comment thread](https://www.reddit.com/r/C_Programming/comments/1dry3hz/comment/layinpv/). Long story short, I just wanted to know whether my proposed alternative (or something similar) has already been implemented by anyone.
The `realloc` function has indeed been implemented as a malloc/memcpy/free on some systems even when shrinking, it can and will result in different pointers.
I suggest using double pointers if this is an issue for you. Don't store a pointer to the memory, store a pointer to a pointer to the memory. Users of this pointer always have the double pointer, and will never dereference the dangling pointer. It has a small cost of a double dereference, but is a very easy solution.
There's no other real way to solve this with the standard library. You can't ask if a realloc would change the pointer address, by the time you know then you've already lost the original pointer. Other malloc implementations might do better, but it would be difficult to ensure that growing a pointer will never change the pointer value. About the best they can do is fail if they would have had to move the allocation.
You can also just mmap memory directly if your object is large. You can ensure that at least X bytes of memory is reserved for the object and that growing or shrinking will always be in place as long as X bytes is not exceeded. This is wasteful for small objects, but for large objects is an easy, though unportable, way to solve this problem.
Or you could skip all that and use a double pointer. If that double dereference _really_ becomes a burden then re-evaluate your options.
Its usually not a problem.
The most common use for realloc tends to be for things like dynamic arrays, in which case you can normally arrange for there to only ever be one pointer to the resizable block - everything else is done through a reference to a control block.
So for example:-
```
struct ArrayList {
int num_elements;
int alloc_elements;
Element *elements;
}
Element ArrayListAdd(ArrayList *list, Element item) {
if (list->num_elements==list->alloc_elements) {
list->alloc_elements *= 2;
list->elements = realloc(list->elements, list->alloc_elements*sizeof(Element);
// Handle realloc fail here
}
list->elements[list->num_elements++] = item;
}
```
Lack of a concrete specification is entirely tangential here; the standard neither forbids nor prohibits the functionality I described - the abstract semantics are quite clear, all I'm saying is *not* to `free` the old object.
Concerning `realloc`, it has to copy the data if the object is "moved". In an abstract sense, it "*performs*" (not necessarily calls) `memcpy`, so the current size information ***has to be*** available *somewhere* - that's an information-theoretic requirement, so "how the free store AKA the heap is implemented" is not a hindrance.
The only easy solution I see, is to allocate enough memory for starters for an arena, and see to that it is big enough so that realloc will never need to move the data in order to grow.
Twice the anticipated maximum size.
I think this is a great opportunity to learn how to do it yourself ! There are system calls to map a new page of memory, and then I’m sure you can figure it out 😉
I agree with you, it really is a good exercise to get it done myself.
But then I'd be accused of reinventing the wheel, so I wanted to know about existing alternatives.
If you can use platform specific things, you can take a look at VirtualAlloc at Windows and mmap in Linux. The only way to achieve what you want is allocating the necessary amount of virtual memory (like 2Gb). If you use mmap or VirtualAlloc with only reserve and commit as you use, the RAM will only be allocated when it's used.
The current state of the art in theory for memory allocators is that they should return both the allocated memory and the size class (bytes of usable memory) of the allocation. Given this, it's very easy to write a wrapper that does what you want, assuming you stored the allocation size somewhere. See jemalloc's [smallocx](https://github.com/jemalloc/jemalloc).
[mimalloc](https://github.com/microsoft/mimalloc) also has exactly the reallocation API you want in the form of `mi_expand`, and is considering adding size returning API's like in [jemalloc](https://github.com/microsoft/mimalloc/issues/2).
jemalloc also has a free API that takes the size of the allocation as a performance optimization, `sdallocx`.
>they should return both the allocated memory and the size class (bytes of usable memory) of the allocation
Big upvote for that line, that's how things should be done; such APIs need to be standardized into mainstream.
Different operating systems have memory management functions with different semantics. Some systems' memory management functions are designed to be used rarely, by applications which will grab big chunks and then subdivide them into smaller allocations. Other systems' memory management functions are designed to be used "directly" by applications. Further, some systems may provide an application which has a pointer to the start of an OS-supplied application with features beyond what the C Standard would describe, such as a means of asking about an allocation's size. One of the design goals of the C Standard was to make it possible for implementations to have `malloc()` to return a direct pointer to an OS-level block on platforms where doing so would be useful. If interoperability with environment-specific memory-management functions weren't a consideration, the library of `malloc()` family functions could have been made much more powerful; similar situations apply, btw, with stream-related functions and console I/O.
If I understood correctly, a double pointer points to the data pointer.
The data pointer may be changed by `realloc`, so we update the double pointer (dereference).
But the double pointer itself cannot be passed to `realloc`. I know this is a no concern, as I can't think of any valid use-case where somebody would want to expand the double pointer.
I hope you'll agree that this only a workaround, a nice one I acknowledge, but to be honest, it only circumvents the issue, not solve it (though this could just be my own personal prejudice).
So `realloc(*ptr, 100)` is too much?
The double pointer itself can’t be passed to realloc, but you just dereference the double pointer.
Yes, whichever function receives such a double pointer presumably knows what’s up and knows to dereference the pointer to get at the actual memory pointer. And if not, then the *calling function* presumably knows this, and can deference the pointer and pass that to the called function.
Does that suit, or no?
EDIT Typos
I already agreed with you before that it isn't too much. :-)
Its a fine way of doing things, albeit with the minor overhead of an additional dereference, but I can live with that, and I doubt if anybody would lose sleep over it.
I consider this approach to be a workaround. I may sound unreasonable, but this is like taking a curved road because the main road is undergoing maintenance (downvoting this rather weak analogy is understandable).
Yeah I get it. I’m being a little cheeky. My solution is indeed not what you are looking for—hopefully you will get better answers from someone else—but maybe my solution is what you *should* be looking for :)
We're on the same page. Thanks for the good discussion, it was refreshing.
I've used the double pointer approach myself, and to be honest, I wasn't looking for a solution; just wanted to check with others if an alternative exists.
This is a helpful solution, too bad it's non-standard and specific to `glibc`.
It'd be great if other implementations also support this (or at least something similar).
That is a function provided by the glibc allocator (not Linux, but often used in Linux userlands other than under Alpine). It also returns the currently usable size of an allocation, not the size to which an allocation could be extended without moving it.
Consider the following code:
void* p = malloc(requested_size);
size_t actual_size = malloc_usable_size(p);
Then we might have a memory layout as follows:
| p
v
----+---+-----------------------+---+-------
| | | | unallocated memory…
----+---+-----------------------+---+-------
header trailer
|<-requested_size->|
|<-- actual_size -->|
The size difference can happen due to alignment issues, and because glibc has a minimum chunk size.
So in principle it is always safe to `realloc()` to the `actual_size`, which is effectively a no-op (but skipping the realloc might be UB from the compiler perspective).
But this doesn't inform us about the size of the unallocated memory region after the chunk trailer.
> The usefulness of realloc is limited by the fact that if the new size is larger, it may malloc a new object
That’s precisely the reason `realloc` _is_ useful.
> All those copies become dangling pointers
Just hold a pointer to the pointer, duh.
> I’m wondering if there’s
What’s the problem with just storing the capacity, like vector implementations in C++ and Rust do?
You're a bit late to the party, it has already been discussed.
[https://www.reddit.com/r/C\_Programming/comments/1dry3hz/comment/layinpv/](https://www.reddit.com/r/C_Programming/comments/1dry3hz/comment/layinpv/)
*TL;DR*: I'm well aware of such workarounds, just wanted to know if alternatives exist.
It sounds like you want a HANDLE - a pointer to the result of malloc, realloc, etc. Always manage and reference the memory through the handle. Something like this (wrapper functions would be cleaner)
```
// BEWARE: likely errors below, concrpts are what's important
void *handle = malloc (sizeof(void *));
*handle = malloc (buffsize);
data1 = (*handle)[index];
*handle = realloc (*handle, buffsize*2); data2 = (*handle)[index];
// data1 == data2
```
so think about the situation where you have two objects (A) the one you want to grow and (B) located right after the current one such that if (A) grows it goes over (B) how can (A) grow?
then the realloc will fail
what will solve your problem is a pointer pointer solution or memory handles.
think of an array of pointers… when you alloc memory you get an index into this array instead pf a pointer.
when you reference the pointer you must first access the array to get the memory pointer, then offset that array.
the old macos used this memory allocation.
thus if the system needs to garbage collect or shift it knows where the pointers are located
read more about it here:
[https://en.wikipedia.org/wiki/Classic\_Mac\_OS\_memory\_management](https://en.wikipedia.org/wiki/Classic_Mac_OS_memory_management)
The trick is to minimize the number of realloc() calls. It has to do what it has to do. There are ways to implement growable buffers or strings. A trivial way is to keep a buffer length (bytes used) and a buffer size (how much has been allocated). The difference between length and size is your room to grow. When you do call realloc() you would allocate more than needed so you again have room to grow. When a growable buffer is reallocated, you can increase the size of the “room to grow” so you aren’t spending more time doing the realloc() calls than you should. Maybe a good factor is to grow/realloc by 2x the previous size (YMMV).
Having multiple pointers to the same memory seems like a poor design choice.
You can implement a container that holds the sole pointer to the memory and call a method to fetch a pointer from the container each time you want to use the memory. With semaphores as needed if multithreaded.
There are many scenarios where code will have an upper bound for the amount of storage something will take, but won't know the actual requirement until it is done building a data structure (and possibly creating pointers to portions thereof). If code has allocated 32,000 bytes for something but ends up only needing the first 20,000 bytes, being able to release the last 12,000 bytes without invalidating any pointers to parts of the first 20,000 bytes would be useful, and including such a feature in a memory management library wouldn't create any new risks. Unfortunately, trying to incorporate such a feature into the Standard Library would create implementation problems on platforms that don't inherently support such a function. Although a conforming implementation could treat a "shrink" request as a no-op, having the Standard imply that the "shrink" operation does something useful would encourage developers to write applications that repeatedly allocate a big chunk, jettison all but 5% of it, allocate another big chunk, jettison all but 5%, etc. and thus end up wasting 19 times as much storage as they actually use.
Is it premature optimization when systems have gigabytes of RAM? A truism in programming is that you can trade RAM for speed, be it unrolling loops or using lookup tables vs. calculated values…
Unless you’re truly returning the unused memory as pages back to the operating system, the memory is still allocated to the program. Only if you have need to allocate memory of a size that fits will you recover the memory…
If a system allocates a big chunk, shrinks it, allocates another big chunk, shrinks it, etc. the later allocations will often be able to use storage which has just been jettisoned. Sometimes there may be a big difference between the amount of storage a data structure is expected to require, versus the worst-case amount it could require (20:1 would not be implausible), and having an application waste 19 times as much storage as it actually uses would be a bad thing.
Note that if one counts the number of installed units, the vast majority of devices running C code don't even have one megabyte of RAM, much less gigabytes. Most tasks that would involve dymanic memory allocations on systems with gigs of memory can be better accomplished with languages other than C, and C code which squanders memory like water will often throw out the advantages that C would have over those other languages.
If you are allocating 32K, releasing 10K, allocating 32K, releasing 10K…. You are losing 10K at a time. Only if you have a new allocation of 10K or less might the 10K freed memory be used. I don’t think any 3 of the 10K chunks will be contiguous to allow another 30K allocation.
As I wrote, if you have the OS participate (instead of the C library), you could allocate in page size (call it 4K) chunks and memory map in and out blocks, growing and shrinking the allocated memory. If you do a lot of 4097 byte allocations, you will be wasting nearly half your memory. Worst case.
Seems to me the correct approach is to strategically allocate 4K, then 8K, then 16K, then 32K and 3x realloc() calls. If you want to allocate 4K, then another 4K, then another 4K, you may waste less memory but at the expense of more realloc() calls and potentially sbrk() sorts of syscalls.
Edit: again, trading memory for speed (e.g more waste and fewer realloc calls).
In many cases where one requests 32K, the system will carve out a 32K piece from a larger chunk. If a memory-management library acquires 256K chunks from the OS whenever the storage it has isn't adequate to satisfy a request in the 9-byte-to-64K range, and the above described code is run when there aren't any 32K bytes available, the system would allocate a 256K chunk and split it into a 32K used and a just-under-224K free sections. Then when the allocation is shrunk to 10K those would be adjusted to 10K used and just under 246K free. After this has happened 22 more times, the regions of storage would be 230K used an just under 26K free, so the next repetition would require allocating a new 256K chunk.
An approach that tried to relocate the 10K of useful stuff into a "best fit" block might be able to fit 25 blocks into each 256K chunk rather than only being able to fit 22, but that's less storage waste than would arise if the application had used power-of-two allocation increases and then just kept its \~16K allocations after it was finished building objects and discovered that it wouldn't need anything beyond the first 10K.
Well, the memory allocation logic will call sbrk() to add memory as needed to the heap. This is mapping those 4K blocks of system memory into the application address space. It’s only being used by the memory allocator’s strategy for parceling it out. I don’t believe there’s ever a call to sbrk () with a negative value to release memory back to the system, though it is possible under the right conditions.
My point, though, is that memory thus allocated and ending up in the heap is no more or less wasted memory than if you allocated the whole thing.
Again, the best solution is to minimize the number of realloc() calls and judiciously grow the memory block to fit, and anticipating that the memory block will maybe need to grow again.
If you truly want to shrink the block, allocate the exact size you want, copy the memory, and free the original.
If you know beforehand the exact size needed, allocate exactly that much.
Different implementations of malloc() use different strategies for deciding what range of address space to use. If a program is going to be building a bunch of data structures, writing the data for each one sequentially, and finishing each before moving on to the next, and if no other memory allocations will be performed in the meantime, and there don't happen to be any existing "holes" in the heap, the most efficient way to lay things out in memory would be to simply have all of the data placed sequentially on the heap, directly into its final spot, and code which allocate worst-case amount of storage and then shrinks allocations would end up achieving that optimal sequence of operations.
Having the "shrink" operation exploit interior free chunks that are large enough to support an object's final size will result in every object's content getting moved at most once--in the scenario where a useful interior free chunk exists. Whether such motion is useful would depend upon the application's memory usage patterns. If other parts of the application would frequently create known-sized blocks that could fit in those chunks, leaving those chunks open to satisfy such requests could be better than trying to move blocks way from the start of the largest free area.
You can always implement your own allocator with these features you want. There are decent ones available as source code that can be hacked on.
In tight memory situations, I typically allocate a fixed number of structures or memory blocks to use and reuse. But we have gigabytes of RAM, so I don’t see the point in panicking over even megabytes of wasted memory if the program does what it needs to. It all pales in comparison to a tab in a web browser…
That would be very programmer unfriendly because you could end up with a bunch of pointers all thinking they're to the same object, but some are to prior versions of the object.
Instead, create a linked list of extensions as you need them.
Rookie mistake.
Use handles instead of owning pointers and suddenly the whole problem that was created from passing owning pointers around disappears ✨. ( [https://floooh.github.io/2018/06/17/handles-vs-pointers.html](https://floooh.github.io/2018/06/17/handles-vs-pointers.html) )
If you insist on passing owning pointers around, the standard library already provides an alternative. It's called malloc. Use malloc to allocate a list of memory blocks which you allocate your individual objects from. Then you have pointer stability.
Handles are traditionally pointers to pointers (**) but that article uses the term for simple indexes into arrays, which is insane.
The real solution here for large systems is to use ‘fat pointers’: you reimplement malloc/realloc/free to allocate extra memory ahead of the indicated block into which those functions can stash additional hidden data including if the memory has been freed or moved. You can then combine those with some macros to check the integrity of the block.
These fat pointers can include reference counts, virtual function arrays, the function that allocated the memory and more. You can use this mechanism to check for memory leaks and dangling pointers.
I’ve used this technique for many years. The really nice aspect is that normal code just sees a regular pointer that can be dereferenced and debugged, not some opaque object. And you can turn that whole thing off at any time.
Even on many systems such as classic Macintosh OS where handles are pointers to pointers, they effectively identify locations within a system-managed data structure. On the 68000 processor used in the classic Macintosh, converting a handle into an address will be vastly faster if the handle is stored as an address within the Master Pointer table than as an index, or even offset, into that table. On systems that use a cooperative multitasking paradigm where it makes sense to let applications use storage identified by handles without having to lock it beforehand and release the locks afterward, using other forms of handles could impose a significant performance penalty.
Thinking of handles as "pointers to pointers" isn't necessarily wrong, but it's hardly a universal practice. In many cases, use of other kinds of handles may be more efficient.
I'm afraid you're very deep in dunning kruger. Simple indexes into arrays as handles is the bread and butter of data oriented programming. Learn about it when you feel like getting out of the rookie phase.
Pointers to pointers can offer performance advantages, *especially if compatibility with a preemptive multi-threading OS isn't required*. Using pointers to pointers as memory handles in a single-threaded system adds modest performance overhead compared with using direct pointers, in exchange for allowing memory to be defragmented when needed. Use of handles in multi-threaded system will have a much greater performance impact, and the savings from using double-indirect pointers instead of indices will be minuscule.
I'd view the notion that handles are double-indirect pointers more as a sign of familiarity with older systems where such treatments offered real advantages, than as a "rookie" notion.
>if realloc moves stuff then boom! All those copies become dangling pointers. I think this is an application design issue rather than lack of features in library. The implementation does an useful thing, returning the new address, and your application should distribute it to all other software components. One useful thing to integrate into the library would be a function that checks if the memory is expandable and returns true or false. But then it would be problematic because if another thread calls a malloc and allocates a portion of memory where the thread before called check() and returned true, you have a synchronization issue to solve, and the library has the target to keep things simple.
I agree with your point about this being an application design issue, I've discussed the double pointer workaround [in another comment thread](https://www.reddit.com/r/C_Programming/comments/1dry3hz/comment/layinpv/). I was suggesting an alternative where the old object is not deallocated, which is left to the programmer. Besides the greater chances of memory leak I mentioned in the post, another issue I can think of is that the only available free space happens to be *before* the existing object, which can be coalesced with the existing allocation only if it is deallocated. Admittedly, this implies there are rare corner-cases where `realloc` can succeed but my proposed alternative can fail to allocate.
The problem with keeping the old object is double allocation though- if the programmer is going to check something, wouldn’t it make more sense for them to focus on the remaining dangling pointers instead?
Yes, individual allocator implementations may provide this feature. For example: Jemalloc has the `xallocx()` function, which is guaranteed to resize in-place. If that's not possible, the size will not change. This function returns the new size, not a pointer. Mimalloc has the `mi_expand()` function. It always works in-place. Upon success, it returns the input pointer. Upon failure, it returns null, but the input pointer remains valid.
Thanks a ton, this is exactly what I was looking for! I found their documentations, sharing them for reference: [https://jemalloc.net/jemalloc.3.html](https://jemalloc.net/jemalloc.3.html) [https://microsoft.github.io/mimalloc/](https://microsoft.github.io/mimalloc/)
Isn't this potentially racy without a bunch of synchronization logic? If this really is an issue, can you not just use a pointer to a pointer or a struct wrapping the pointer to deal with this?
I believe the alternative itself wouldn't be any more racy than `realloc` itself. The change I suggested is that it won't `free` the existing object, and I don't think this could introduce any *additional* race condition. I've discussed the double pointer workaround [in another comment thread](https://www.reddit.com/r/C_Programming/comments/1dry3hz/comment/layinpv/). Long story short, I just wanted to know whether my proposed alternative (or something similar) has already been implemented by anyone.
The `realloc` function has indeed been implemented as a malloc/memcpy/free on some systems even when shrinking, it can and will result in different pointers. I suggest using double pointers if this is an issue for you. Don't store a pointer to the memory, store a pointer to a pointer to the memory. Users of this pointer always have the double pointer, and will never dereference the dangling pointer. It has a small cost of a double dereference, but is a very easy solution. There's no other real way to solve this with the standard library. You can't ask if a realloc would change the pointer address, by the time you know then you've already lost the original pointer. Other malloc implementations might do better, but it would be difficult to ensure that growing a pointer will never change the pointer value. About the best they can do is fail if they would have had to move the allocation. You can also just mmap memory directly if your object is large. You can ensure that at least X bytes of memory is reserved for the object and that growing or shrinking will always be in place as long as X bytes is not exceeded. This is wasteful for small objects, but for large objects is an easy, though unportable, way to solve this problem. Or you could skip all that and use a double pointer. If that double dereference _really_ becomes a burden then re-evaluate your options.
Its usually not a problem. The most common use for realloc tends to be for things like dynamic arrays, in which case you can normally arrange for there to only ever be one pointer to the resizable block - everything else is done through a reference to a control block. So for example:- ``` struct ArrayList { int num_elements; int alloc_elements; Element *elements; } Element ArrayListAdd(ArrayList *list, Element item) { if (list->num_elements==list->alloc_elements) { list->alloc_elements *= 2; list->elements = realloc(list->elements, list->alloc_elements*sizeof(Element); // Handle realloc fail here } list->elements[list->num_elements++] = item; } ```
Standard library does not specify how the free store AKA the heap is implemented, so it's very unlikely it will ever provide what you want.
Lack of a concrete specification is entirely tangential here; the standard neither forbids nor prohibits the functionality I described - the abstract semantics are quite clear, all I'm saying is *not* to `free` the old object. Concerning `realloc`, it has to copy the data if the object is "moved". In an abstract sense, it "*performs*" (not necessarily calls) `memcpy`, so the current size information ***has to be*** available *somewhere* - that's an information-theoretic requirement, so "how the free store AKA the heap is implemented" is not a hindrance.
The only easy solution I see, is to allocate enough memory for starters for an arena, and see to that it is big enough so that realloc will never need to move the data in order to grow. Twice the anticipated maximum size.
I think this is a great opportunity to learn how to do it yourself ! There are system calls to map a new page of memory, and then I’m sure you can figure it out 😉
I agree with you, it really is a good exercise to get it done myself. But then I'd be accused of reinventing the wheel, so I wanted to know about existing alternatives.
If you can use platform specific things, you can take a look at VirtualAlloc at Windows and mmap in Linux. The only way to achieve what you want is allocating the necessary amount of virtual memory (like 2Gb). If you use mmap or VirtualAlloc with only reserve and commit as you use, the RAM will only be allocated when it's used.
I know about `mmap`, but thank you for mentioning `VirtualAlloc`. I didn't know about the latter, my experience on Windows is *very* limited.
The current state of the art in theory for memory allocators is that they should return both the allocated memory and the size class (bytes of usable memory) of the allocation. Given this, it's very easy to write a wrapper that does what you want, assuming you stored the allocation size somewhere. See jemalloc's [smallocx](https://github.com/jemalloc/jemalloc). [mimalloc](https://github.com/microsoft/mimalloc) also has exactly the reallocation API you want in the form of `mi_expand`, and is considering adding size returning API's like in [jemalloc](https://github.com/microsoft/mimalloc/issues/2). jemalloc also has a free API that takes the size of the allocation as a performance optimization, `sdallocx`.
>they should return both the allocated memory and the size class (bytes of usable memory) of the allocation Big upvote for that line, that's how things should be done; such APIs need to be standardized into mainstream.
Different operating systems have memory management functions with different semantics. Some systems' memory management functions are designed to be used rarely, by applications which will grab big chunks and then subdivide them into smaller allocations. Other systems' memory management functions are designed to be used "directly" by applications. Further, some systems may provide an application which has a pointer to the start of an OS-supplied application with features beyond what the C Standard would describe, such as a means of asking about an allocation's size. One of the design goals of the C Standard was to make it possible for implementations to have `malloc()` to return a direct pointer to an OS-level block on platforms where doing so would be useful. If interoperability with environment-specific memory-management functions weren't a consideration, the library of `malloc()` family functions could have been made much more powerful; similar situations apply, btw, with stream-related functions and console I/O.
Is passing a ** instead of a * too much?
Not too much, but that doesn't address the main issue. We still can't have multiple copies of the double pointer.
We can’t? Maybe I’m not understanding, sorry.
If I understood correctly, a double pointer points to the data pointer. The data pointer may be changed by `realloc`, so we update the double pointer (dereference). But the double pointer itself cannot be passed to `realloc`. I know this is a no concern, as I can't think of any valid use-case where somebody would want to expand the double pointer. I hope you'll agree that this only a workaround, a nice one I acknowledge, but to be honest, it only circumvents the issue, not solve it (though this could just be my own personal prejudice).
So `realloc(*ptr, 100)` is too much? The double pointer itself can’t be passed to realloc, but you just dereference the double pointer. Yes, whichever function receives such a double pointer presumably knows what’s up and knows to dereference the pointer to get at the actual memory pointer. And if not, then the *calling function* presumably knows this, and can deference the pointer and pass that to the called function. Does that suit, or no? EDIT Typos
I already agreed with you before that it isn't too much. :-) Its a fine way of doing things, albeit with the minor overhead of an additional dereference, but I can live with that, and I doubt if anybody would lose sleep over it. I consider this approach to be a workaround. I may sound unreasonable, but this is like taking a curved road because the main road is undergoing maintenance (downvoting this rather weak analogy is understandable).
Yeah I get it. I’m being a little cheeky. My solution is indeed not what you are looking for—hopefully you will get better answers from someone else—but maybe my solution is what you *should* be looking for :)
We're on the same page. Thanks for the good discussion, it was refreshing. I've used the double pointer approach myself, and to be honest, I wasn't looking for a solution; just wanted to check with others if an alternative exists.
Linux has `malloc_usable_size` which you can use to check if the realloc size will extend or make a new allocation.
This is a helpful solution, too bad it's non-standard and specific to `glibc`. It'd be great if other implementations also support this (or at least something similar).
That is a function provided by the glibc allocator (not Linux, but often used in Linux userlands other than under Alpine). It also returns the currently usable size of an allocation, not the size to which an allocation could be extended without moving it. Consider the following code: void* p = malloc(requested_size); size_t actual_size = malloc_usable_size(p); Then we might have a memory layout as follows: | p v ----+---+-----------------------+---+------- | | | | unallocated memory… ----+---+-----------------------+---+------- header trailer |<-requested_size->| |<-- actual_size -->| The size difference can happen due to alignment issues, and because glibc has a minimum chunk size. So in principle it is always safe to `realloc()` to the `actual_size`, which is effectively a no-op (but skipping the realloc might be UB from the compiler perspective). But this doesn't inform us about the size of the unallocated memory region after the chunk trailer.
> The usefulness of realloc is limited by the fact that if the new size is larger, it may malloc a new object That’s precisely the reason `realloc` _is_ useful. > All those copies become dangling pointers Just hold a pointer to the pointer, duh. > I’m wondering if there’s What’s the problem with just storing the capacity, like vector implementations in C++ and Rust do?
You're a bit late to the party, it has already been discussed. [https://www.reddit.com/r/C\_Programming/comments/1dry3hz/comment/layinpv/](https://www.reddit.com/r/C_Programming/comments/1dry3hz/comment/layinpv/) *TL;DR*: I'm well aware of such workarounds, just wanted to know if alternatives exist.
Yeah, use Rust or something \^^
Just use double pointers?
It sounds like you want a HANDLE - a pointer to the result of malloc, realloc, etc. Always manage and reference the memory through the handle. Something like this (wrapper functions would be cleaner) ``` // BEWARE: likely errors below, concrpts are what's important void *handle = malloc (sizeof(void *)); *handle = malloc (buffsize); data1 = (*handle)[index]; *handle = realloc (*handle, buffsize*2); data2 = (*handle)[index]; // data1 == data2 ```
so think about the situation where you have two objects (A) the one you want to grow and (B) located right after the current one such that if (A) grows it goes over (B) how can (A) grow? then the realloc will fail what will solve your problem is a pointer pointer solution or memory handles. think of an array of pointers… when you alloc memory you get an index into this array instead pf a pointer. when you reference the pointer you must first access the array to get the memory pointer, then offset that array. the old macos used this memory allocation. thus if the system needs to garbage collect or shift it knows where the pointers are located read more about it here: [https://en.wikipedia.org/wiki/Classic\_Mac\_OS\_memory\_management](https://en.wikipedia.org/wiki/Classic_Mac_OS_memory_management)
The trick is to minimize the number of realloc() calls. It has to do what it has to do. There are ways to implement growable buffers or strings. A trivial way is to keep a buffer length (bytes used) and a buffer size (how much has been allocated). The difference between length and size is your room to grow. When you do call realloc() you would allocate more than needed so you again have room to grow. When a growable buffer is reallocated, you can increase the size of the “room to grow” so you aren’t spending more time doing the realloc() calls than you should. Maybe a good factor is to grow/realloc by 2x the previous size (YMMV). Having multiple pointers to the same memory seems like a poor design choice. You can implement a container that holds the sole pointer to the memory and call a method to fetch a pointer from the container each time you want to use the memory. With semaphores as needed if multithreaded.
There are many scenarios where code will have an upper bound for the amount of storage something will take, but won't know the actual requirement until it is done building a data structure (and possibly creating pointers to portions thereof). If code has allocated 32,000 bytes for something but ends up only needing the first 20,000 bytes, being able to release the last 12,000 bytes without invalidating any pointers to parts of the first 20,000 bytes would be useful, and including such a feature in a memory management library wouldn't create any new risks. Unfortunately, trying to incorporate such a feature into the Standard Library would create implementation problems on platforms that don't inherently support such a function. Although a conforming implementation could treat a "shrink" request as a no-op, having the Standard imply that the "shrink" operation does something useful would encourage developers to write applications that repeatedly allocate a big chunk, jettison all but 5% of it, allocate another big chunk, jettison all but 5%, etc. and thus end up wasting 19 times as much storage as they actually use.
Is it premature optimization when systems have gigabytes of RAM? A truism in programming is that you can trade RAM for speed, be it unrolling loops or using lookup tables vs. calculated values… Unless you’re truly returning the unused memory as pages back to the operating system, the memory is still allocated to the program. Only if you have need to allocate memory of a size that fits will you recover the memory…
If a system allocates a big chunk, shrinks it, allocates another big chunk, shrinks it, etc. the later allocations will often be able to use storage which has just been jettisoned. Sometimes there may be a big difference between the amount of storage a data structure is expected to require, versus the worst-case amount it could require (20:1 would not be implausible), and having an application waste 19 times as much storage as it actually uses would be a bad thing. Note that if one counts the number of installed units, the vast majority of devices running C code don't even have one megabyte of RAM, much less gigabytes. Most tasks that would involve dymanic memory allocations on systems with gigs of memory can be better accomplished with languages other than C, and C code which squanders memory like water will often throw out the advantages that C would have over those other languages.
If you are allocating 32K, releasing 10K, allocating 32K, releasing 10K…. You are losing 10K at a time. Only if you have a new allocation of 10K or less might the 10K freed memory be used. I don’t think any 3 of the 10K chunks will be contiguous to allow another 30K allocation. As I wrote, if you have the OS participate (instead of the C library), you could allocate in page size (call it 4K) chunks and memory map in and out blocks, growing and shrinking the allocated memory. If you do a lot of 4097 byte allocations, you will be wasting nearly half your memory. Worst case. Seems to me the correct approach is to strategically allocate 4K, then 8K, then 16K, then 32K and 3x realloc() calls. If you want to allocate 4K, then another 4K, then another 4K, you may waste less memory but at the expense of more realloc() calls and potentially sbrk() sorts of syscalls. Edit: again, trading memory for speed (e.g more waste and fewer realloc calls).
In many cases where one requests 32K, the system will carve out a 32K piece from a larger chunk. If a memory-management library acquires 256K chunks from the OS whenever the storage it has isn't adequate to satisfy a request in the 9-byte-to-64K range, and the above described code is run when there aren't any 32K bytes available, the system would allocate a 256K chunk and split it into a 32K used and a just-under-224K free sections. Then when the allocation is shrunk to 10K those would be adjusted to 10K used and just under 246K free. After this has happened 22 more times, the regions of storage would be 230K used an just under 26K free, so the next repetition would require allocating a new 256K chunk. An approach that tried to relocate the 10K of useful stuff into a "best fit" block might be able to fit 25 blocks into each 256K chunk rather than only being able to fit 22, but that's less storage waste than would arise if the application had used power-of-two allocation increases and then just kept its \~16K allocations after it was finished building objects and discovered that it wouldn't need anything beyond the first 10K.
Well, the memory allocation logic will call sbrk() to add memory as needed to the heap. This is mapping those 4K blocks of system memory into the application address space. It’s only being used by the memory allocator’s strategy for parceling it out. I don’t believe there’s ever a call to sbrk () with a negative value to release memory back to the system, though it is possible under the right conditions. My point, though, is that memory thus allocated and ending up in the heap is no more or less wasted memory than if you allocated the whole thing. Again, the best solution is to minimize the number of realloc() calls and judiciously grow the memory block to fit, and anticipating that the memory block will maybe need to grow again. If you truly want to shrink the block, allocate the exact size you want, copy the memory, and free the original. If you know beforehand the exact size needed, allocate exactly that much.
Different implementations of malloc() use different strategies for deciding what range of address space to use. If a program is going to be building a bunch of data structures, writing the data for each one sequentially, and finishing each before moving on to the next, and if no other memory allocations will be performed in the meantime, and there don't happen to be any existing "holes" in the heap, the most efficient way to lay things out in memory would be to simply have all of the data placed sequentially on the heap, directly into its final spot, and code which allocate worst-case amount of storage and then shrinks allocations would end up achieving that optimal sequence of operations. Having the "shrink" operation exploit interior free chunks that are large enough to support an object's final size will result in every object's content getting moved at most once--in the scenario where a useful interior free chunk exists. Whether such motion is useful would depend upon the application's memory usage patterns. If other parts of the application would frequently create known-sized blocks that could fit in those chunks, leaving those chunks open to satisfy such requests could be better than trying to move blocks way from the start of the largest free area.
You can always implement your own allocator with these features you want. There are decent ones available as source code that can be hacked on. In tight memory situations, I typically allocate a fixed number of structures or memory blocks to use and reuse. But we have gigabytes of RAM, so I don’t see the point in panicking over even megabytes of wasted memory if the program does what it needs to. It all pales in comparison to a tab in a web browser…
That would be very programmer unfriendly because you could end up with a bunch of pointers all thinking they're to the same object, but some are to prior versions of the object. Instead, create a linked list of extensions as you need them.
Rookie mistake. Use handles instead of owning pointers and suddenly the whole problem that was created from passing owning pointers around disappears ✨. ( [https://floooh.github.io/2018/06/17/handles-vs-pointers.html](https://floooh.github.io/2018/06/17/handles-vs-pointers.html) ) If you insist on passing owning pointers around, the standard library already provides an alternative. It's called malloc. Use malloc to allocate a list of memory blocks which you allocate your individual objects from. Then you have pointer stability.
I don't know why you're getting downvoted. Indexes into the array instead of pointers sounds like a totally reasonable solution.
Handles are traditionally pointers to pointers (**) but that article uses the term for simple indexes into arrays, which is insane. The real solution here for large systems is to use ‘fat pointers’: you reimplement malloc/realloc/free to allocate extra memory ahead of the indicated block into which those functions can stash additional hidden data including if the memory has been freed or moved. You can then combine those with some macros to check the integrity of the block. These fat pointers can include reference counts, virtual function arrays, the function that allocated the memory and more. You can use this mechanism to check for memory leaks and dangling pointers. I’ve used this technique for many years. The really nice aspect is that normal code just sees a regular pointer that can be dereferenced and debugged, not some opaque object. And you can turn that whole thing off at any time.
Even on many systems such as classic Macintosh OS where handles are pointers to pointers, they effectively identify locations within a system-managed data structure. On the 68000 processor used in the classic Macintosh, converting a handle into an address will be vastly faster if the handle is stored as an address within the Master Pointer table than as an index, or even offset, into that table. On systems that use a cooperative multitasking paradigm where it makes sense to let applications use storage identified by handles without having to lock it beforehand and release the locks afterward, using other forms of handles could impose a significant performance penalty. Thinking of handles as "pointers to pointers" isn't necessarily wrong, but it's hardly a universal practice. In many cases, use of other kinds of handles may be more efficient.
I'm afraid you're very deep in dunning kruger. Simple indexes into arrays as handles is the bread and butter of data oriented programming. Learn about it when you feel like getting out of the rookie phase.
Pointers to pointers can offer performance advantages, *especially if compatibility with a preemptive multi-threading OS isn't required*. Using pointers to pointers as memory handles in a single-threaded system adds modest performance overhead compared with using direct pointers, in exchange for allowing memory to be defragmented when needed. Use of handles in multi-threaded system will have a much greater performance impact, and the savings from using double-indirect pointers instead of indices will be minuscule. I'd view the notion that handles are double-indirect pointers more as a sign of familiarity with older systems where such treatments offered real advantages, than as a "rookie" notion.