The lost malloc()
napcakes.nekoweb.org
napcakes.nekoweb.org
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!
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
And there also bugs for zig. So hint - fine. Trust it? Not sure. Every allocator is different and can be swapped
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.
We already have enough memory-unsafety bugs going around without making free() more difficult to use correctly as well.
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.
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).
Polymorphism in C++?
A* blah = new B();
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()
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.
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.
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.
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...
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.)
Source: I have implemented allocators.
If sized parameter helps optimization, why allocator just not put it in the header block already ?
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.
That's not a 10% overhead, java is like 2x, and a script language could be even 100x.
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.
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, yeah, it's not an ideal situation from the perspective of free_aligned advocates.
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
A string created by strdup().
Basically, the issue is C having unsized allocations and related not tracking string length.
In November 1965, C.A.R. Hoare published an extremely influential paper: "Record Handling". This was a proposed extension for the successor of ALGOL 60.
Almost all of the features that were added in SIMULA 67 over its predecessor, the SIMULA language, come directly from the paper of Hoare, with two big exceptions: class inheritance and the "virtual" procedures, which were invented by the SIMULA 67 creators (Kristen Nygaard & Ole-Johan Dahl) and which are essential for object-oriented programming.
The SIMULA 67 keywords "class" and "new" were taken from Hoare's paper (Hoare actually had taken "class" from COBOL 60, which used a very different terminology in comparison with ALGOL 60, among the many differences being the use of "class" instead of the "type" used by ALGOL 60).
Hoare's paper discussed a lot of programming language features, most of which were new, including defining structured types with constructors and destructors, discriminated unions (taken from John McCarthy), enumerations, the NULL pointer and many others.
SIMULA 67 was one of the first languages which implemented many of the features proposed by Hoare. Other languages that implemented some of the proposed features were IBM PL/I, ALGOL 68, then a couple of years later, in 1970-11, Pascal.
The keyword "new" had already been used for the first time by Niklaus Wirth, but at Wirth it had a different meaning than at Hoare. It declared a variable that was local to a block, which would hide any old variable with the same name that had been declared outside that block. So "new" at Wirth was equivalent with "auto" and "register" of the language C.
Later, in the language Pascal, Wirth abandoned his original use of "new", replacing it with the "new" introduced by Hoare.
Also 'arena allocators' (this meant something different like 20 years ago so I think the name just got rebranded) are not that good, they make some things easier and improve performance sometimes, they also are liable to use more memory and cause more fragmentation if not used with care. That is one of the many reasons why we slowly evolved away from the old linear allocators, but also because we just wanted a simple and flexible interface to hide complexity.
A thing appears simple when it allows you to make distinctions you care about and avoid making distinctions you do not care about. C is weak with the latter, but Python with the former.
It's amazing that a method like the Bump Allocator was already tried.
How were the senior programmers able to do all of this? I'm just amazed.
> How were the senior programmers able to do all of this? I'm just amazed.
Secondly the systems in that time where less complex meaning it was easier to understand and experiment with fundamental parts of the computer.
Lastly at that time "programming" was closer to the metal so a average computer scientist at that time would likely have more knowledge of the deep internals compared to an average programmer today.
> C seems like a language that is simple but can really do a lot
most people open an ide and start coding, or write some basic diagrams to get an overview/mental model. Back in the day any bitnlarge program would take hours to compile so really u did not want to have any bug or typo just to sit for hours until a compile error or logic mistake. Take it even further back to days before C and that is even more needed.
a lot of high level modern languages seem to alleviate that need, likely so that enterprise software can be written a bit faster because the features need to arrive faster.
still in more modern languages i'd recommend starting with pencil and paper, write most of it if not the whole thing out. u'll find much nicer patterns and will save yourself a bunch of refactoring. even for small programs.
It helps me to print it in a different font/color and without syntax highlighting to force my brain to read it as new code, instead of simply assuming it's the same as I already know.
i never use syntax highlighting. one day someone told me it was very distracting, i turned it off and suddenly things were calm. Maybe its just taste but i do find it helpful. you really read stuff rather than assuming some color happening means its correct or incorrect subconsciously
The old saying "Necessity is the mother of invention" applies. Smart people + system constraints => ingenuity.
But it's voluntary. Actually course curricula basically just drop hints at the history as part of a short perfunctory narrative. Along with the deeper conceptual instruction (framed according to the then-current beliefs), that's better than vocational instruction, but definitely falls short of the idealized liberal education. Ideally you survey the entire historical progression of a field, like St John's College does where, e.g., you start learning geometry by reading Pythagoras, or calculus by reading Newton, and then having vigorous discussion to suss how how thinking changed or didn't change between eras and how that might inform today's thinking. Not sure how much marginal benefit is had by going all-in like that, though, as a practical matter, except for very serious students.
> you start learning geometry by reading Pythagoras, or calculus by reading Newton
You can do that, if you actually care about the history of mathematics, but normally it's enough if someone introduces you to a combined theory of e.g. Pythagoras and Newton.
So in a way you are saying, university is often not actually teaching temporal genesis, which I agree with, but my point is that it does teach causal genesis, with citations on the temporal aspect.
The article claims the term first appear in V6 Unix though I couldn't tell you why it's called that.
It does help prevent confusion, though, a memory "arena" and a memory "area" don't both mean the same thing.
It was catapulted to 8th rank while its "raw" was around 50th give or take.