任何在性能关键代码中使用过“双端队列”的人可能已经注意到(至少在 VS2010 附带的 STL 中) block 大小为 16 字节。这是 VS2010 附带的头文件的实际片段:
#define _DEQUESIZ (sizeof (value_type) <= 1 ? 16 \
: sizeof (value_type) <= 2 ? 8 \
: sizeof (value_type) <= 4 ? 4 \
: sizeof (value_type) <= 8 ? 2 \
: 1) /* elements per block (a power of 2) */
这不是新信息,请参阅 About deque<T>'s extra indirection有关此声明为何导致性能问题的更多详细信息。
我想在各种算法中使用双端队列,但如果我受限于此实现则不会。规避此问题的最佳方法是什么?
1) 使用另一个没有这个问题的容器。如果是这样,谁能给我指一个没有 GNU 许可限制的软件?
2) 创建一个新的容器类来解决这个限制。这个新的容器类不会成为 std 命名空间的一部分。
3) 编辑“deque”头文件中的_DEQUESIZ 定义。 IMO,我认为这是合法的,因为 _DEQUESIZ 的确切规范不是由 STL 定义的双端队列概念的一部分。
4) 向双端队列(以及关联的迭代器类)添加一个额外的模板参数,以允许在编译时指定 block 大小。此参数将默认为 _DEQUESIZ 的当前定义。我几乎拒绝这个解决方案,因为现在我使用这个 SCSS STL 的代码不可移植。
5) 游说大会更改 STL,这样我就可以愉快地使用“双端队列”而不会出现性能问题。 IMO,这可能比当前的财政悬崖辩论更成功。顺便说一句,我是加拿大人,所以整个众议院 + 参议院 + 总统的冗长乏味令人困惑。
最佳答案
不是真正的答案,但评论太长了:
如果您担心性能,我不建议您编写新的容器类。通常,STL 实现基于它们所针对的特定编译器的实现细节使用不可移植的优化,而您通常无法这样做。我曾经尝试自己重写一些非常简单的 STL 算法,并获得了大约一半的 STL 算法的执行速度。
更改 _DEQUESIZ
可能会在不可预见的地方导致性能问题,因为其他代码可能针对原始值进行了优化。再一次,当你为特定的编译器编写代码时,你可以做的那种不可移植的优化。不仅如此:您甚至可能会破坏一些取决于 _DEQUESIZ
的实际值的代码。
总而言之,在我看来,只有您的选项 1 是可行的。不幸的是,我不知道有什么好的选择;这就是为什么我写道这不是您问题的真正答案。
关于c++ - 处理导致性能问题的双端队列 block 大小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13989835/