Do STL containers always move memory?
Author
Hey,
This is not an important question, but if I do a push_back/reserve on a std::vector, how will it reallocate? For example, if I do a C-style realloc on a memory block, and there's enough empty space after that memory block, it doesn't copy that memory block to another location. It just changes its size (needed for realloc/free). But C++ only has new and delete, so how is it done in the STL? It's not very efficient to always allocate a new block with the new size, copy the whole data and delete the previous block when that's not needed in most of the cases. So does anyone know how that's done in the STL?
Quote:Original post by beun
Hey,
This is not an important question, but if I do a push_back/reserve on a std::vector, how will it reallocate?
It depends on the allocator.
Quote:For example, if I do a C-style realloc on a memory block, and there's enough empty space after that memory block, it doesn't copy that memory block to another location. It just changes its size (needed for realloc/free).
You seem to know this is not correct, if there is not enough space its need another different block and then copies the first block into the second.
Quote:This the behaviour of the default allocator.
But C++ only has new and delete, so how is it done in the STL? It's not very efficient to always allocate a new block with the new size, copy the whole data and delete the previous block when that's not needed in most of the cases. So does anyone know how that's done in the STL?
Standard describes basic characteristics of each container, which affect how memory is allocated.
Each container has allocator parameter, which allows user to determine how/where memory is allocated. The role of realloc is taken over by implementation of this allocator.
You have the source, look at it.
If should be noted that if appropriate containers are chosen for operations, then algorithms performed on them in combination with appropriate allocator will result in optimal code.
Vector behaves similar to realloc. It will perform minimum number of allocations/moves required by a sequence of operations - but it cannot guess programmer's intention. That is algorithmic problem, using wrong one will result in sub-optimal behavior, even with realloc.
This is why it's recommended to pre-allocate certain containers to the maximum number of elements to minimize the number of redundant resizes.
Each container has allocator parameter, which allows user to determine how/where memory is allocated. The role of realloc is taken over by implementation of this allocator.
Quote:So does anyone know how that's done in the STL?
You have the source, look at it.
If should be noted that if appropriate containers are chosen for operations, then algorithms performed on them in combination with appropriate allocator will result in optimal code.
Quote:It's not very efficient to always allocate a new block with the new size
Vector behaves similar to realloc. It will perform minimum number of allocations/moves required by a sequence of operations - but it cannot guess programmer's intention. That is algorithmic problem, using wrong one will result in sub-optimal behavior, even with realloc.
This is why it's recommended to pre-allocate certain containers to the maximum number of elements to minimize the number of redundant resizes.
Author
Quote:This the behaviour of the default allocator.
Thanks for the reply. I guess that's all I wanted to know.
Quote:You have the source, look at it.
Well, in all the allocation functions in "vector", the following is called (MSVC 9):
this->_Alval.(de)allocateThat's the allocator (default or user-defined)
template<class _Ty, class _Alloc> class _Vector_val : public _CONTAINER_BASE_AUX_ALLOC<_Alloc> { // base class for vector to hold allocator _Alvalprotected: _Vector_val(_Alloc _Al = _Alloc()) : _CONTAINER_BASE_AUX_ALLOC<_Alloc>(_Al), _Alval(_Al) { // construct allocator from _Al } typedef typename _Alloc::template rebind<_Ty>::other _Alty; _Alty _Alval; // allocator object for values };But I don't have the source for the default allocator.
Thanks for the replies, and as I said, this was just a little question that popped in my mind, I don't want to flame std::vector, and I won't stop using std::vector for these things.
Quote:Original post by beun
But I don't have the source for the default allocator.
It's std::allocator<T>, so source is present. But even without it, it calls new/delete, and nothing more.
Quote:Thanks for the replies, and as I said, this was just a little question that popped in my mind, I don't want to flame std::vector, and I won't stop using std::vector for these things.
Allocators tend to be somewhat randomly supported in not necessarily compatible ways. As such, there might be a lack of solid information on how to implement them.
Another issue when dealing with them is that to support them in a generic manner, code becomes convoluted. For example, to handle generic string:
template < class C, class T, class A >void foo(const std::basic_string<C, T, A> & s);Valuable read(ppt).
Quote:Original post by beun
It's not very efficient to always allocate a new block with the new size, copy the whole data and delete the previous block when that's not needed in most of the cases.
Surprisingly, it is. Part of the explanation for that is to be found in the amortized analysis of resizing, the upshot of which is that it happens so seldom that even if it did take a long time, the long-term performance of std::vector would still be good. The other important point is that under the circumstances in which std::vector resizes, realloc would nearly always be forced to move the memory anyway, because the size is increasing by a fixed multiplier (often 1.5 or 2).
Well, glibc does zero-copy realloc for large blocks by using memory mapping tricks. And I wouldn't be surprised if other standard libraries or replacement allocators do the same thing but I haven't looked into it. A nice consequence of this is that you can reduce the growth factor without taking much of a performance hit (if you can rely on the feature that is..).
Do any std::vector implementations use similar tricks for POD types? Obviously the standard allocator interface doesn't support this kind of thing, but presumably it could be done with some weird partial specialization hack.
Do any std::vector implementations use similar tricks for POD types? Obviously the standard allocator interface doesn't support this kind of thing, but presumably it could be done with some weird partial specialization hack.
Quote:Original post by implicit
Well, glibc does zero-copy realloc for large blocks by using memory mapping tricks. And I wouldn't be surprised if other standard libraries or replacement allocators do the same thing but I haven't looked into it. A nice consequence of this is that you can reduce the growth factor without taking much of a performance hit (if you can rely on the feature that is..).
To quote Daffy Duck: "I know, I know, but I can only do it once." The tricky thing about using virtual memory mapping in this manner is that your local address space is still linear. So if you want to be able to grow a 3 byte buffer to 16 megabytes later on, you don't actually have to allocate 16 megabytes of RAM just yet, but you do have to reserve a 16 MB hole in the local address space for later growth, which becomes problematic if you have a whole bunch of buffers. So it's a cool trick--hell, it's almost a magic trick--, but its applicability is limited.
As for whether std::vector uses it? Unlikely. The allocator interface is badly designed and too weak for, well, pretty much anything except standard or pool allocation. EASTL's allocator stuff is much nicer. I doubt they use this trick either, though, due to the lack of virtual memory on consoles.
Quote:Original post by SneftelActually glibc's realloc() uses mremap to move physical memory within the virtual address space. You still have to worry about virtual memory fragmentation, but that's no different from normal relocation.
To quote Daffy Duck: "I know, I know, but I can only do it once." The tricky thing about using virtual memory mapping in this manner is that your local address space is still linear. So if you want to be able to grow a 3 byte buffer to 16 megabytes later on, you don't actually have to allocate 16 megabytes of RAM just yet, but you do have to reserve a 16 MB hole in the local address space for later growth, which becomes problematic if you have a whole bunch of buffers. So it's a cool trick--hell, it's almost a magic trick--, but its applicability is limited.
Of course reserving a fixed-size chunk of address space has some nice advantages as well (not invalidating references for one) but that'd have to be used very carefully for memory hungry applications on 32-bit machines, though for say a 64-bit console game I'd use it all over the place.
Or don't modern consoles use virtual memory? I remember some N64 games using it at least (awesome for code, what with the N64 having little memory and fast random-access ROM memory) but perhaps you can save some silicon by cutting out that particular feature, or perhaps all that extra indirection has more of a performance impact then I would have thought.
Actually now that I think about it the STL allocators not having a concept of reallocation has some other annoying consequences in addition to lost optimization opportunities, e.g. using more memory (well duh.. but it's easy to forget that worst-case overhead is two thirds for a size-doubling vector) as well as increased fragmentation. Of course not every vector contains POD, though the really large ones tend to, but you could often write some relocation fixup code manually instead.
The "yasli_vector" from Loki is the smartest implementation I've seen.
beun: The vector is not completely reallocated for each push_back. The underlying array it uses is only reallocated when the extra amount is allocatd last time becomes used up. The size grows by a constant multiple e.g. times 2, not by a constant amount. This is actually good enough speedwise that it covers for the fact that this even occurs at all, due to the amortised constant time taken. Don't worry about it.
beun: The vector is not completely reallocated for each push_back. The underlying array it uses is only reallocated when the extra amount is allocatd last time becomes used up. The size grows by a constant multiple e.g. times 2, not by a constant amount. This is actually good enough speedwise that it covers for the fact that this even occurs at all, due to the amortised constant time taken. Don't worry about it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
