关于deque< T>的额外间接 [英] About deque<T>'s extra indirection

问题描述

想知道为什么我的内存访问比我预期的慢，我终于弄明白了 deque 的Visual C ++实现确实有一个额外的 层间接内置，破坏我的内存区域。

ie它似乎持有 T * 的数组，而不是 T 的数组。

有没有另一个实现，我可以使用VC ++没有这个功能，或者有一些方法（虽然我认为不太可能）能够避免在这个实现？ p>

我基本上在寻找一个向量，在前面也有O（1）push / pop。 >
我想我可以自己实现，但是处理 allocator ，这是一个痛苦，它需要一段时间才能正确，

解决方案

不管什么原因，至少在MSVC 2010年， std :: deque 实现似乎使用一个令人难以置信的小块大小（最大16字节或1单个元素，如果我没有错误！）。

根据我的经验，这可能会导致非常显着的性能问题，因为数据结构中的每个块基本上只会存储一个元素，各种额外的开销（时间和记忆）。

我不知道为什么这样做。据我所知，用这么小的块大小建立一个 deque 就是不应该这样做

。

查看 gcc stdlib 实现。

编辑：试图解决其他问题：

• std :: deque 应该有额外的间接层。它经常被实现为阻塞数据结构 - 即存储节点的阵列，其中每个节点本身是数据元素的阵列。它不像一个链表 - 节点数组从来没有遍历像一个列表，它总是直接索引（即使在每个块1个元素的情况下）。




• 当然，您可以滚动自己的数据结构，在前面保留一些额外的空间。它不会有最坏的情况下 O（1）push / pop前/后c / c>行为，因此它不满足 std :: deque的要求容器。但是如果你不在乎任何...




Wondering why my memory accesses were somewhat slower than I expected, I finally figured out that the Visual C++ implementation of deque indeed has an extra layer of indirection built-in, destroying my memory locality.

i.e. it seems to hold an array of T*, not an array of T.

Is there another implementation I can use with VC++ that doesn't have this "feature", or is there some way (although I consider it unlikely) to be able to avoid it in this implementation?

I'm basically looking for a vector that has also O(1) push/pop at the front.
I guess I could implement it myself, but dealing with allocators and such is a pain and it would take a while to get it right, so I'd rather use something previously written/tested if possible.

解决方案

For whatever reason, at least as of MSVC 2010, the std::deque implementation appears to make use of an unbelievably small block size (the max of 16 bytes or 1 single element if I'm not mistaken!).

This, in my experience, can result in very significant performance issues, because essentially each "block" in the data structure only ends up storing a single element, which leads to all kinds of additional overhead (time and memory).

I don't know why it's done this way. As far as I understand it setting up a deque with such a small block size is exactly how it's not supposed to be done.

Check out the gcc stdlib implementation. From memory they use a much larger block size.

EDIT: In an attempt to address the other issues:

• std::deque should have an extra layer of indirection. It is often implemented as a "blocked" data structure - i.e. storing an array of "nodes" where each node is itself an array of data elements. It's not ever like a linked-list - the array of nodes is never "traversed" like a list, it's always directly indexed (even in the case of 1 element per block).

• Of course you can roll your own data structure that keeps some extra space at the front. It wont have worst case O(1) push/pop front/back behaviour, and as such it wont satisfy the requirements of the std::deque container. But if you don't care about any of that...

这篇关于关于deque< T>的额外间接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！