Hacker News Reader

Many allocators must keep 2 sizes for every allocated object: the size of the allocated memory and the size actually occupied by the requested object.

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.

> Many allocators must keep 2 sizes for every allocated object

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...

[3]: https://en.cppreference.com/cpp/named_req/Allocator

> 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()!

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.)

No, having the size would be immensely useful. Consider the standard allocator design.

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.

But sized deallocation gives the allocator implementation more freedom to optimize, not less. More information from clients = more optimization opportunities for the implementation. I don't understand how you can claim the opposite is true.

Source: I have implemented allocators.

I don't see the point

If sized parameter helps optimization, why allocator just not put it in the header block already ?

> There's virtually no sensible case where the person calling free() doesn't know the size of the allocation

We already have enough memory-unsafety bugs going around without making free() more difficult to use correctly as well.

Don't worry, the allocator almost never dedicates actual heap space towards storing your allocation sizes. Instead, allocations get bucketed by size, and you can derive the size by working out which bucket the allocation is in. This is cheap and the bucketing is a good strategy anyway.

Unfortunately, "boundary tags" containing allocation size are still pretty common in dlmalloc-derived implementations like glibc, although slab allocators like you described are the preferred approach for most new implementations.

In any abstract allocation, it is entirely possible that the place the object is freed has little knowledge of how it was created. This is object abstraction at it's basic definition.

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.

Indeed, this baffled me since moving from Pascal to C. In Pascal you could use getmem()/freemem(), both accepting the size of the object. As a result the allocator should be simpler and more performant. In C the allocator has to track that size, in addition to your program tracking it separately. And the complexity of allocators in C can go into black-arts territory.

> There's virtually no sensible case where the person calling free() doesn't know the size of the allocation

Polymorphism in C++?

A* blah = new B();

You already need a virtual destructor here anyway, because it needs to know about the actual type B, which includes it's size.

In C++, the destructor doesn't call free() because the destructor doesn't know if it's on the stack or heap.

Consider:

    void f(){
        A* tmp = someFunction(stuff);
        foo(tmp);
        delete tmp;
    }

    void g(){
        A tmp; // destructor will be called, but no free/delete
    }

What is the size of A? Answer: you never know in C++ due to polymorphism. It might be a B or other subclass. It is truly a variable length operation.

And secondly, the destructor cannot tell if it's f() or g()

> What is the size of A? Answer: you never know in C++ due to polymorphism. It might be a B or other subclass. It is truly a variable length operation.

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.

But it's possible for `delete tmp;` to call a user-defined `operator delete()` in the derived class! https://godbolt.org/z/hvePa6jMP

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.

At least in the MSVC implementation, "delete tmp;" calls "operator delete" polymorphically, through a hidden virtual function. I think this is because derived classes may override "operator delete"?

C2y has already added free_sized, FWIW, which is symmetrical with malloc. See 7.25.4.7 in the latest draft at https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3998.pdf

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.

But if you still have to support the plain free functions it doesn't help because you'd still have to track the information anyway.

The degree to which it helps or not depends on the implementation. For example, free could be a slow path that does extra bookkeeping lookups the sized variants wouldn't need to. Large allocations and non-default aligned allocations often use different bookkeeping data structures from how most allocations are handled internally anyhow. In such cases that check needs to be done up front, and at least on virtual memory systems (where it's relatively easy to segregate allocations types by VM range) it doesn't much matter whether you're indexing that first level directory based on pointer or size.

But, yeah, it's not an ideal situation from the perspective of free_aligned advocates.

At load time, you do know whether a program is going to use plain free, so you can select the implementation then.

I think this is missing the forest for the trees. The potential savings of one extra size_t per allocation are miniscule compared to the overhead of using malloc() in the first place, with a potential syscall on every allocation. If you care about waste, you should ask for those pages from the OS directly, once at init, and use arenas.

If you think you can convince the entire computer industry to stop using malloc(), I wish you the best of luck. In actuality, your computer likely calls malloc() somewhere thousands of times per second in low use, probably millions of times during intensive use. Wouldn't it be nice if all those calls were just a bit less resource intensive?

I'm curious, what do you expect the performance improvement to be, in terms of CPU cycles per allocation? malloc() costs on the order of 10,000 cycles on the slow path.

I don't know what the exact impact would be, but it's certainly not zero, and multiplied by every malloc, it adds up. My point is mostly that the API for malloc()/free() is designed in such a way to both limit the kind of implementations you can make for it, and make most implementations a tiny bit slower than they need to be.

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.

There's no syscall on every allocation. With many allocators, the common case is popping a node off a linked list.

That's why I put the word "potential" in there. Every allocation potentially needs to go to the OS for more pages.

And every memory access potentially enters the kernel via a page fault.

Any given CPU instruction potentially isn't in cache.

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).

> I can't think of a single time where you DON'T know what `count` is

A string created by strdup().

Then you know it's strlen+1

So you don't know it: you must calculate it, via an expensive strlen().

To be fair, that is a downstream effect of C's worst mistake (NUL terminated strings). Also, if every allocation you'd get is ptr+size you could just derive it by also copying the size.

Basically, the issue is C having unsized allocations and related not tracking string length.

It's tricky. The harder you make it to use the lower layers the more people will say fuck it and use a higher layer. How many people decided move to java or even script languages because they were scared of undefined behavior security issues?

That's not a 10% overhead, java is like 2x, and a script language could be even 100x.

> you're forcing the memory allocator to keep track of these sizes when it shouldn't have to

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

"void*" sadly exists, and there are a lot of edge cases.

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

I don't agree. Zig allocators require the size of the allocation (technically they take a slice, but a slice is ptr + size), as does the C++ polymorphic allocator, as does many allocator interfaces in many libraries (see for instance the allocator interface in Lua, my personal favorite C interface for memory allocation [0]). Clearly having it as a correctness requirement works just fine.

[0]: https://www.lua.org/manual/5.4/manual.html#lua_Alloc

https://github.com/microsoft/mimalloc/issues/1423 https://github.com/microsoft/mimalloc/issues/1400

And there also bugs for zig. So hint - fine. Trust it? Not sure. Every allocator is different and can be swapped

> "void*" sadly exists

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.

This is just 100% wrong. The API should be designed to prevent mistakes. You're arguing in favor have having more memory safety bugs.

That isn't the C and C++ philosophy, especially now that if you want to use Rust, you can just use Rust.