Hacker News Reader

Comment by nly | Hacker News Reader

Actually it is C's malloc and free that is "broken". malloc() takes a size parameter, but free() doesn't. This imbalance means it can never be maximally efficient. Whatever GNU stdlibc++ is doing is probably, on balance, a net win for most programs.

It's not exactly roses in C++ either of course. You can do better than the standard library facilities. Andrei Alexandrescu gave a great, entertaining, and technically elegant talk on memory allocation in C and C++ at Cppcon 2015 that is well worth watching

https://www.youtube.com/watch?v=LIb3L4vKZ7U

View on HN

Most allocators will be able to pretty efficiently recover the size of the block you are freeing. And you can count on developers not getting the size right, for that to be a common error, and for everyone to cobble together their own, wildly different and probably slower ways of tracking sizes. So it doesn't really help.

malloc/free aren't a great API, but for other reasons (namely, that you want things like multiple arenas, good control over synchronization, decent debugging and introspection, leak-tracking, tagging for figuring out what a block really is when things get smashed, block enumeration, small block pools, placement for cache alignment, and . . . you get the idea).

> you can count on developers not getting the size right, for that to be a common error, and for everyone to cobble together their own, wildly different and probably slower ways of tracking size

You have to do this anyway. You either know the size of the thing you allocated the memory for or, if it's a block, you need to keep track of the size for bounds checking purposes.

There are no circumstances in which you call malloc() in which you don't need to know the keep the size in your application.

It's not just about C. In C++, for example, you might be deleting a base-typed pointer to a derived instance, that can be one of several options that you don't know at compile time.

Doesn't matter, since you call the destructor for the derived class through the vtable. The function you end up calling knows the size of your object and its exact layout. The size at this point is compiled statically in to your program.

The destructor does not deallocate memory in C++, since it is called just the same for objects allocated in other ways.

It's also not a given that such an object even has a vtable. It's perfectly legal for it to not have one, and the memory is still supposed to be deallocated in full (only the base class dtor is invoked then, but if derived class additions are trivial, it's not necessarily a problem).

Now, yes, you could add a separate vtable slot for the deallocation function. Or just store the object size directly in the type info (that's usually attached to the vtable). But this is really just a way to optimize size storage for objects that already have a word utilized for shared type descriptor like a vtable.

Hmm:

1) There doesn't have to be a vtable.

2) If there is a vtable available, it's the wrong one (look carefully at the treatment of vtable pointers in destructors when inheritance is involved).

2) The object has been completely destroyed before the deallocator is called, and it's unclear whether the vtable pointer is available (the standard doesn't seem to make this guarantee). In any event, the deallocator is statically determined and cannot be a virtual call.

I will note that vtables are just an implementation detail, and that you can successfully implement virtual calls with other mechanisms, which are also not required (by the C++ standard) to remember object sizes. So you can replace the concept 'vtable' with 'abstract mechanism by which the set of members appropriate for this class is determined' -- use token-based dispatch, for example -- and still have a compliant implementation.

[I helped write a few object runtimes in the late 80s and early 90s -- and man, C++ gets gnarly -- and I've shipped 8 to 10 allocators of various types in commercial products over the years]

Knowing a size and being forced to retain a size are different things. Here's a trivial example (imagine a system to process compressed audio data):

(1) receive packet: compute actual size, allocate buffer, expand data into it, start DMA to a speaker or something

(2) DMA-done: free the buffer

There, I didn't need the size on the free. There are many, many many similar cases, in fact these cases probably dominate.

Both your speaker driver and your application code still needed to keep track of the buffer size. calling free(size) on your buffer would require no extra overhead

The C++ delete[] operator doesn't take a size parameter either. This is neither here nor there, and unrelated to the problem the blog post is talking about.

> The C++ delete[] operator doesn't take a size parameter either

Yes it does. See overload 6 here

http://en.cppreference.com/w/cpp/memory/new/operator_delete

Note that the size parameter is ignored by the standard library implementation. It is intended for use by user-defined implementations.

> Note that the size parameter is ignored by the standard library implementation

Only because they all call malloc() and free() under the covers. It was however an ABI break, and one the C++ community thought worth doing.

If you replace your malloc with jemalloc you can easily wire this up to sdallocx(). The C++ standard library obviously can't do this out of the box because it can't assume you are using jemalloc

I believe that if you malloc/free so much that those 120 cycles become a major issue, then perhaps doing dynamic allocation in this context isn't a good idea.

Furthermore, with Alexandrescu's solution, I'm not so sure that the 120 cycles that you gain here are not burned over there because your allocator has to construct a two-members structure and your program has to go through an extra indirection to access the actual memory block.

If free() took a size, what would that buy you?

You are aware that malloc implementations tend to stick the size just before the part returned to the caller, right? eg. let's say you store size at p, return p+4 to caller, then have free() subtract 4 again to get at this "header"... So I'm guessing that's not your suggestion because free() wouldn't work at all without that kind of hack. Or more broadly, free() or realloc() and others already need to have some way to determine the size of the allocation based on the pointer, so they track that somehow in a way opaque to the caller.

So then what...? You want programs to be able to give back a prefix of the buffer? or...?

With the status quo, say you call malloc() once. After a long while you call free(). Now the first thing free() needs to do is figure out the size, which is stored "before" the pointer. Until that load is complete, it can't know how large the allocation was, so it can't prefetch other necessary data, e.g. the free list for a given chunk size. This could add 120 cycles of latency to get a value that the caller probably already had in L1 cache or could compute with a single multiply.

Or a call to strlen() which makes your 120 cycles of latency start to look good ...

Edit to add: I've used both malloc()/free() and a custom memory allocation API that required the size to be passed in. I found the second API to be much more of a pain to use over the long term. Besides, it wastes memory because the memory API will have to track the size anyway to detect misuse of the API (or else blindly trust that the right size is passed in and hilarity ensues when it's not ...).

Well you could use free() whenever it's practical and free_sz () when you can get the performance.

I actually added this line:

> Or more broadly, free() or realloc() and others already need to have some way to determine the size of the allocation based on the pointer

When I remembered I'd read a malloc implementation somewhere which actually didn't store the size in a header, but bakes in assumptions that you can determine the size of an allocation based on its address. So my naive thing isn't the only option, and I think if you have the kinds of concerns you raise there could be mitigations to be had.

They only store the size in a header because free() needs to know the size on deallocation. Think about all the C string functions that take buffer length parameters and what an outcry there would be if we eliminated all the size parameters and placed string lengths as headers before the buffer itself.

It's terrible for performance because you're giving up control, even if it is a little safer overall.

That'd be silly. Among many other problems, it would mean you can't do things like take a substring of a const buffer via pointer arithmetic, because you'd need to add a header in the middle.

It's better to pick exactly one of: (1) embrace the true nature of allocations and figure out lengths yourself or (2) if you are less comfortable with that, use some other language which doesn't expose any of this.

> That'd be silly. Among many other problems, it would mean you can't do things like take a substring of a const buffer via pointer arithmetic, because you'd need to add a header in the middle

Right, and now you understand why free should have always accepted a size parameter, just like malloc.

No, I don't. Doing zero-copy substrings of a read only buffer and an allocator chopping up a writable buffer into multiple chunks are very different scenarios.

Not for this purpose. It's all about knowing where the boundaries are.

I take it you didn't read the fine article.

Yes I did. My point is the C++ standard library has more information about your allocations than malloc() or free() does so it makes sense for it to attempt to do something smarter.

Since the 'fine article' didn't really get in to any interesting details, i'll leave it at that.

Reply on news.ycombinator.com