CppCon 2015: Andrei Alexandrescu “std::allocator...”

Naysayer crap. What a crap talk. Nobody has any need for this crap. Pools cause extreme delusions of grandeur. Some jackass discovers bump allocators and thinks they are a badass.

am here because I wanted to implement my own std containers (fake std), and didn't knew how vector managed to realloc because new/delete operators can't be combined with realloc/calloc/malloc/free operations. Now I know a byte more about allocators-

It looks to me like the freelist allocator has the fallback allocator baked in.

I would think the whole point of designing for composition is that you can separate those two parts.

The simpler free list allocator then becomes:

allocate(size) { if (size is wrong or free list is empty) return null; else return head of free list }
owns(p) { p.size == mysize }
deallocate(p) { assert(p.size == mysize); prepend p onto the free list; }

When combined with a fallback allocator, you should get Andrescu's free list allocator.

Still haven't seen anything interesting from Andrei.

This was great high level info but I think I missed something crucial/obvious. How do I actually allocate the memory without malloc or new? Those functions don't look like they do much to me.

I had to implement such allocators in C for a "standard" library for embedded systems in my company and man I wish I had C++ templates for that. I had to use macro-based templates instead which I wish on no enemy.

Insane

free without size is a good thing - consider it with size and you have yet another sort of UB when deallocation size is not equal allocation - do you want more UBs in C/C++? don't think so

Creator of DLang

Is it advisable to have all these template instantiations of the same code that only differs in template parameters that are integers? Won't your code get bloated?

Actually looking at the what it would take to implement something, and it seems like there is a crucial part missing. Pointer comparisons are not well-formed expressions in C++, unless the pointers come from the same object or array. That some of the owns operations use this comparison does not seem at first look to be a path down cross-platform or compiler use. Perhaps something like the StackAllocator may work frequently, since the stack addresses are more well ordered, but even then it is not guaranteed it seems. For more complex allocators, the owns functions or any comparisons may not work too well.

Anybody have any thoughts on this?

This guy is hilarious! :D A joy to watch and learn from.

Can I avoid manually doing alignment if I take type information in the template argument?

All those compositions incur extra overhead as all the checking as to which allocator owns a pointer or what allocator to use happen at runtime. This kind of stuff should be done during compile time , but that makes it impossible to allocate arrays whose length is only known at runtime.

Thank you very much Dr Andrei Alexandrescu

It is a good exercise for a brain, but also it has so many misleading points.

First of all, why free function work this way? Because you can't trust user. It can send you correct pointer and wrong size (or vice versa, or both wrong), consequences of this are unpredictable and probably will lead to really strange bugs in allocator.

Also free is not taking pointer to the beginning of allocated block, any address within this block is accepted. Without the latter you simply could not deallocate by pointer to superclass of an object (unless it is the first superclass), or does the speaker suggest to use dynamic type lookup to deallocate?

Modern malloc do many of the mentioned optimizations. Why would you need to reinvent it in your code?

I cannot imagine situation when you really need such an universal allocator. Is it going to be a shared allocator for certain objects? Well, what about multithreading then? Adding mutex there will make this allocator slower than direct call to malloc.

Usually what you neeed is allocator of the fixed size. It can be done without these composition tricks which are not free.

This is interesting and all, but how do I actually use these? Without reinventing STL, I mean.

Doesn't the Freelist allocator violate the strict aliasing rules if you use the returned pointer as something other than a Freelist::Node?

std::alligator(); //probably useful

My opinion is that I don't like this talk. Because he takes way to long to make his point and share his knowledge what he recommends programmers to do and why that is.

'allocators should only care about size, alignment' ... but the type could give hints as to useage, or lifetime (as defaults, and you could override that with explicit hints)

I read two of his books and I had no idea he was hilarious in front of an audience. Frankly I expected the opposite!

This was one of my favorite talks, and I've seen a lot! He is very informative and at the same time pretty funny. And he is also the first person who successfully tought me that int is a type. The brainfk was huge when I finally realized it. xD

Best man!

On the slide on minute 10, I don't understand what is meant by "no communication with the constructor". A call to new with a user-defined type calls the appropriate constructor of that type. Does anybody understand what Andrei wants to convey with this point?

"Its a pain in the peripherals" -great saying I'm probably gonna use that.

So, such allocator, as described by Andrei, does it exist? Or it's yet just an idea for future C++?

allocators: a memory allocator that gives me memory has no state

eu queria e compriende o que voce falar mas nao me ajudou

I really enjoy your talks, not only informative but sometimes fun as well :)

Such a talent wasted in such a crappy evil company like Facebook (which is now implementing measures to destroy freedom of speech and opinion).

Can anyone answer me a question? I'm not very experienced in c++ and this talk left me a doubt...
Say that I implement all of these allocators...however I could have a class that contains an std::list...this will be probably allocated with mallocs, how are these allocator going to help me with that?

operator new is a function essentially the same as malloc. No type information. It does not call constructors. You mean to refer to a "new expression" which uses the keyword and has complex behavior implemented by the compiler, which includes calling operator new, checking the result, and calling the constructors.

In 1983, the C programming language did not have a void* type. We used char* and at least some of us used a typedef to indicate I really had unspecified stuff (I used 'ambi'). The void and void* types, along with features like allowing different structures to have members of the same name, were added later.

There are errors in slide 28. It should be struct Node { Node* next; } *root_; And later on root_ = root_->next;

This talk is mad interesting, yo.

Good talk; maybe write a book about this.

1:12 - you don't need to keep the file and line number, it is enough to keep the return address (__builtin_return_address on gcc), you can then get the source/line number from debug information (addr2line).

great talk : )

std::allocator(s) is the hell in the paradise of low programming world

16:33 - "It was 20 years after the fact, and it was 'Making Allocators Work'. There's no talk like 'Making Sort Work.'" hahaha

Andrei makes it sound like goodSize is useful for wrapping the argument to allocate, but why not just have allocators return the good size (the actually allocated size, and not the requested size) in Blk, which callers can read to find out how much they really got? Is there any other use for goodSize? Any reason to know goodSize without calling allocate?

On slide 29 the `owns` should have && instead of ||, no? The size needs to be the same and it needs to come from the parent allocator. Also, this assumes that no two FreeList for the same size will be created with the same parent allocator.

It was as if he was dodging a sniper. Agreed. The camera operator nailed it!

The things he describes do not integrate well with the current STL implementation. In fact, that is one of the keystone statements. The next iteration of the STL (aka. STL2) is currently being designed which will be a complete revamp of everything. The STL has many historic garbage in it that are rooted too deeply into the entire system. Allocators for one is one such entity. You cannot change its API without having to touch just about everything.

just found the hole in my argumentation: you don't get size_t as an input in free() in an std::allocator, do you? so you'd have to keep track of that seperately. This sucks >.<

You'd have to write wrapper code to "unpack" the struct Blk into size_t and void*. Maybe some day std::allocator will be gone and something like this will be added to the standard, but until then, you'd have to write a wrapper. You could also write a std::allocator that does only one thing: pass stuff on to an instance of YourComposableAllocatorType (YCAT). You actually use the YCAT instance for your code, but "dumb" code like std::something can use the std::allocator as a shim.

This is great! I'm a huge fan of Andrei. He gave a similar talk about allocators in D. I was hoping for a C++ treatment of the same topic. What's with the comments about no profilers on OS X? I don't know why he would think that. Does Instruments not fit the bill?