I've always thought that one of the biggest tiny mistakes in the history of this industry. It means, more or less, that you're forcing the memory allocator to keep track of these sizes when it shouldn't have to. There's virtually no sensible case where the person calling free() doesn't know the size of the allocation, so now we're keeping that book-keeping twice, in "user-space" and inside the memory allocator. Like, think about the cases when you'd call malloc:
* For allocating a single object of type T, the size is just `sizeof(T)`, so you can just pass that to free()
* For allocating an array of objects, the size is `count * sizeof(T)`, and I can't think of a single time where you DON'T know what `count` is. It's either statically sized (in which case it's just a constant), or if you have a dynamically growing array, you need to keep track of the reserved space to know when you reallocate. If nothing else, you need it for bounds-checking.
* For chunks of raw memory, you also presumably know when deallocating what the size of the raw memory you allocated is, for the same reasons as the previous point. Like, just having a raw char* pointer lying around with no size information is just terrible C practice.
If you truly don't know the size of your allocation (very hard to imagine when this would ever happen), you should be forced on the user-side to keep track of it somehow, not delegate that to the allocator.
It's a tiny amount of overhead, but it's for EVERY SINGLE MEMORY ALLOCATION since like 1975. Imagine how many times malloc() and free() has called since then! How much electricity, CPU usage, and memory has been wasted! It boggles the mind!
[–] adrian_b 4 days ago
[–] OskarS 4 days ago
And wouldn't it be nice to just make them keep one number! That's a size_t and a couple of cycles saved for every malloc()!
I will say, this is not some far-out niche idea of mine, it's basically universal for all "new" implementations of memory allocators to require exactly this information for deallocation. There's a reason Zig allocators take a slice and not a pointer [0], why std::pmr::polymorphic_allocator::deallocate takes a size [1] and why Rust allocators require it as well (in the layout param) [2]. It's just a better API design.
EDIT: for C++, the better reference is the Allocator named requirement, which the polymorphic allocator is just one example of. But you can see it there as well in the deallocate() method [3]
[0]: https://ziglang.org/documentation/master/std/#std.mem.Alloca...
[1]: https://en.cppreference.com/cpp/memory/polymorphic_allocator...
[2]: https://doc.rust-lang.org/std/alloc/trait.GlobalAlloc.html#t...
[–] Sesse__ 4 days ago
You can make them keep basically zero numbers per allocation; most modern mallocs use size classes, and can pack objects of the same size class tightly with no metadata inbetween. (You still need some numbers per page/span and such.)
[–] Veserv 3 days ago
You have a fixed number of small-size block allocators (say 8-256 bytes) and then a sequence of exponentially-sized large block allocators.
For small-size block allocators you want limited allocator overhead, limited over-allocation, high speed, and likely the ability to support certain alignments like 8, 16, and 64 (cache line). Attaching a requested size and actual size (or even just one) to every block would be tremendous overhead.
For large blocks you care less about allocator overhead and over-allocation since it is less overhead as a percentage. So, attaching requested size and actual size to every block is a small cost. However, you likely also want the ability to support certain alignments like 4K, 16K, 2MB, etc. (natural hardware or OS sizes).
So, you generally want two distinct strategys and bookkeeping mechanisms based on the size of the allocation. If deallocation does not take the requested size, then your very first problem is figuring out which mechanism you are using. The problem with this is that you want small-size allocations to have small overhead, so the discrimination mechanism must also be small-overhead.
If you pass in the requested size, then it becomes trivial to distinguish with zero allocator overhead. Is it less than 256 bytes (or whatever small size you choose)? Cool, it is small-size. Round up to the nearest small-size block. Release the memory to the identified small-size block allocator. This has zero per-block overhead, is totally trivial, extremely fast, and preserves alignment.
If the allocated size is in the large-block regime, then you know you can use a per-block overhead scheme. Except, this is still better. If you do not know the requested block size, then you are limited to either a header at negative offset or a auxiliary data structure keyed on the pointer value to determine the actual size. The former messes with your alignments and the latter requires the allocator to be stealing unrelated memory for its own data structures. If deallocation tells you the requested size, then you can easily use a footer scheme instead. Just always over-allocate enough space for a footer and then you can always just jump forward by the requested block size to find the footer and you do not mess up your alignments.
Getting the requested size, which the caller is basically always already remembering via type information, gives you a lot of advantages and optimization levers.
[–] senderista 4 days ago
Source: I have implemented allocators.
[–] mrheosuper 3 days ago
If sized parameter helps optimization, why allocator just not put it in the header block already ?
[–] mpyne 4 days ago
We already have enough memory-unsafety bugs going around without making free() more difficult to use correctly as well.
[–] StilesCrisis 4 days ago
[–] senderista 4 days ago
[–] dragontamer 4 days ago
Polymorphism in C++?
A* blah = new B();
[–] 1718627440 4 days ago
[–] dragontamer 4 days ago
Consider:
void f(){
A* tmp = someFunction(stuff);
foo(tmp);
delete tmp;
}
void g(){
A tmp; // destructor will be called, but no free/delete
}
And secondly, the destructor cannot tell if it's f() or g()
[–] adev_ 4 days ago
You could easily go around it.
The compiler knows when creating the destructor for B.
In your example, to have correct C++, you need to have declared a virtual destruct-or for B. You could encode the size of B in a static offset from the virtual destructor or simply as a return value from it.
This is not how it is done now, mainly because how free was designed in C.
free() design is a terrible mistake. Probably one of the worst design mistake of C with the null terminated / no-length specified string and the preprocessor.
[–] dgrunwald 4 days ago
The way this works under the hood is that every polymorphic class has two destructors (so two destructor entries in the vtable): the "complete object destructor" is the ~A() you know from C++, and then there's also the "deleting destructor" which combines ~A() + delete.
So the deleting destructor can call free() while knowing the derived object size, even for a delete-via-base-class-pointer.
[–] cowlevel 3 days ago
[–] JoeAltmaier 3 days ago
I don't do that; I like to have the allocation and free in the same code module so I can ensure there's no leak, double deletion, null deletion etc. But I know it happens, routinely. In a library for instance.
[–] jimis 4 days ago
[–] wahern 3 days ago
It also adds free_aligned_sized as the counterpart to C11's aligned_alloc. Though while you can pass memory from aligned_alloc to free, you can't use free_sized or free_aligned_sized with aligned_alloc'd or malloc'd memory respectively, a potential (and unavoidable?) foot gun.
[–] dooglius 3 days ago
[–] wahern 3 days ago
But, yeah, it's not an ideal situation from the perspective of free_aligned advocates.
[–] 1718627440 3 days ago
[–] dark-star 3 days ago
Sounds much safer to me than have every single developer, program or library keep track of those sizes properly... I mean that way it's at least only done in 1 place and done correctly, instead of forcing every developer to suddenly keep track of yet another value
[–] fasterik 4 days ago
[–] OskarS 4 days ago
[–] fasterik 4 days ago
[–] OskarS 4 days ago
BTW, when malloc() takes 10,000 cycles, you've either hit some weird edge case in an allocator or (much more likely) malloc() has run out pages it can use to hand over to the application and has to ask the kernel for more memory. I measured malloc() for a recent change in one of our products, and in my test the median time was less than 100ns. malloc() is usually very fast. But with a better API, it could be faster. Multiplied by every memory allocation on every computer in the world (more or less) for the last half-century, it's becomes a very big number.
[–] 0c3ca83 4 days ago
[–] fasterik 4 days ago
[–] 0c3ca83 4 days ago
[–] cowlevel 3 days ago
And yet, they can't all not be in cache. As soon as the cache is accessed for one instruction, a bunch more are pulled in too.
Any given vector.push call could reallocate the vector, but it's amortized O(1).
[–] teo_zero 3 days ago
A string created by strdup().
[–] cowlevel 3 days ago
[–] teo_zero 3 days ago
[–] NekkoDroid 3 days ago
Basically, the issue is C having unsized allocations and related not tracking string length.
[–] im3w1l 4 days ago
That's not a 10% overhead, java is like 2x, and a script language could be even 100x.
[–] 0xdeafbeef 4 days ago
I tried using TCMalloc with rustc, and it segfaulted. Rust knows the sizes of its allocations, but things can still go wrong at the allocator boundary.
Size should be an optimization hint, not a correctness requirement. Otherwise, it's just another security pitfall
[–] OskarS 4 days ago
[–] 0xdeafbeef 4 days ago
And there also bugs for zig. So hint - fine. Trust it? Not sure. Every allocator is different and can be swapped
[–] SkiFire13 4 days ago
But _somewhere_ you need to know what it represents, otherwise it's useless.
> I tried using TCMalloc with rustc, and it segfaulted. Rust knows the sizes of its allocations, but things can still go wrong at the allocator boundary.
Things can go wrong, doesn't mean they will go wrong due to the reasons you're thinking of.
Some allocators keep other extra information for each object. Thus they need all that information and if the "memory free" function gives them only the size of the object, that is not enough.
Since the size is not enough, it is superfluous for the user program to provide it. When given a pointer to an object, the memory allocator will know where to find all the associated data. It might be in the cache line that is immediately before the pointed memory, or it might be in an array, at an index that can be deduced somehow from the value of the pointer, or all the information might be implicit, e.g. when objects are allocated from stacks of objects of the same size, when the size can be deduced from the pointer value, so it is not stored anywhere.
Therefore the correct definition for a memory free function is to have only a pointer as parameter, to give freedom to the allocator to use whichever strategy is deemed better.