How does std::list allocate its items?
Author
How does std::list allocate its items?
I'm quite sure that they ain't using new or malloc every time you use push_back, because then it would be 5 times slower (as slow as my own double linked list). Is it allocating double as much space each time it needs it, just like std::vector or what?
I would really like the 5x increase in my own list ;)
I'm pretty sure someone in here knows, so any comments will be appreciated...
Just to ensure you, I've tried to comment out the new or malloc function in my Append function, and then it's only using 1/10 of the time std::list uses, so the allocation must be the bottleneck (the rest is just simple moves and ALU instructions).
Instantiations of std::list by default use the associated instantiations of the default allocator (the std::allocator template). It is required that the default allocator uses global new, however, continuously getting memory from an instantiation of the allocator doesn't necessarily always use new. In otherwords, while it is required that the default allocator uses new, it can potentially allocate memory in larger blocks and manage that memory for your specific types so that a call to new doesn't happen ever single time the allocator's allocation functions are used (which can give you faster allocations and less overall memory fragmentation).
So when you push_back on a list with a default allocator, new may or may not be called every time single time, though it probably is not, which is why push_back works faster on std::list than your own rolled linked list class.
If you want even more control over the allocations, you can make your own allocator types and use them with std::list (the allocator type is the second template parameter when instantiating an std::list).
If you really want to use your own list, you can use the default allocator (or other allocators) instead of new and delete.
So when you push_back on a list with a default allocator, new may or may not be called every time single time, though it probably is not, which is why push_back works faster on std::list than your own rolled linked list class.
If you want even more control over the allocations, you can make your own allocator types and use them with std::list (the allocator type is the second template parameter when instantiating an std::list).
If you really want to use your own list, you can use the default allocator (or other allocators) instead of new and delete.
Author
Okay thanks for the answer.. It got me to think - how does the allocator know if there is more memory to allocated than what it's currently allocating?
I've heard about std beeing optimized a lot at compile-time, so is that a part of it (recognizing where it should be allocating larger chunks) or does it wait to allocate (like 1 microsecond) to see if there's more to be allocated or does it have another method?
I've heard about std beeing optimized a lot at compile-time, so is that a part of it (recognizing where it should be allocating larger chunks) or does it wait to allocate (like 1 microsecond) to see if there's more to be allocated or does it have another method?
How std::list works? I presume it depends by specific implementations!
If you have multiple allocation and deletion you can speed up the process by using two list : a primary and a garbage.
When you remove an element from the primary list move in the garbage, when you need a new element move from garbage to the primary.
Something like this
If you derive your own list from std::list and add a private member list to use as garbage you have a list with garbage collector compatible with your own code.
If you have multiple allocation and deletion you can speed up the process by using two list : a primary and a garbage.
When you remove an element from the primary list move in the garbage, when you need a new element move from garbage to the primary.
Something like this
void RemoveElement(iterator i){ garbage_list.splice(garbage_list.begin(),primary_list, i);};void NewElement(const T& t){ if(garbage_list.empty()){ primary_list.push_back(t); } else{ T* p = &(*garbage_list.begin()); // -> ListAllocator is an istance to the allocator (A) ListAllocator.construct(p, t); splice(primary_list.end(), garbage_list, garbage_list.begin()); }};If you derive your own list from std::list and add a private member list to use as garbage you have a list with garbage collector compatible with your own code.
Quote:Original post by nife
Okay thanks for the answer.. It got me to think - how does the allocator know if there is more memory to allocated than what it's currently allocating?
I've heard about std beeing optimized a lot at compile-time, so is that a part of it (recognizing where it should be allocating larger chunks) or does it wait to allocate (like 1 microsecond) to see if there's more to be allocated or does it have another method?
It doesn't, it just guesses. If it is wrong, then subsequent allocations will be faster at the expense of a tiny bit of memory going unused.
Author
Thanks for that reply, that will keep me busy for a time, because now I have to start implement that brilliant idea into my other allocation-bottlenecked functions ;-)
Well, for first allocations, I think I'm just going to make a Resize function that could do it for me in a single malloc, and then use the garbage list for further allocations... That should be fast enough.
Well, for first allocations, I think I'm just going to make a Resize function that could do it for me in a single malloc, and then use the garbage list for further allocations... That should be fast enough.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
