我想知道unordered_map
是否是使用类型擦除实现的,因为unordered_map<Key, A*>
和unordered_map<Key, B*>
可以使用完全相同的代码(除了强制转换,这在机器代码中是无操作的)。也就是说,两者的实现都可以基于unordered_map<Key, void*>
来节省代码大小。
更新:这种技术通常被称为Thin Template Idiom (感谢下面的评论者指出了这一点)。
更新2:我对Howard Hinnant的观点非常感兴趣,希望他能读到这篇文章。
所以我写了这个小测试:
#include <iostream>
#if BOOST
# include <boost/unordered_map.hpp>
using boost::unordered_map;
#else
# include <unordered_map>
using std::unordered_map;
#endif
struct A { A(int x) : x(x) {} int x; };
struct B { B(int x) : x(x) {} int x; };
int main()
{
#if SMALL
unordered_map<std::string, void*> ma, mb;
#else
unordered_map<std::string, A*> ma;
unordered_map<std::string, B*> mb;
#endif
ma["foo"] = new A(1);
mb["bar"] = new B(2);
std::cout << ((A*) ma["foo"])->x << std::endl;
std::cout << ((B*) mb["bar"])->x << std::endl;
// yes, it leaks.
}
并确定具有各种设置的编译输出的大小:
#!/bin/sh
for BOOST in 0 1 ; do
for OPT in 2 3 s ; do
for SMALL in 0 1 ; do
clang++ -stdlib=libc++ -O${OPT} -DSMALL=${SMALL} -DBOOST=${BOOST} map_test.cpp -o map_test
strip map_test
SIZE=$(echo "scale=1;$(stat -f "%z" map_test)/1024" | bc)
echo boost=$BOOST opt=$OPT small=$SMALL size=${SIZE}K
done
done
done
事实证明,在我尝试的所有设置中,unordered_map
的许多内部代码似乎被实例化了两次:
With Clang and libc++:
| -O2 | -O3 | -Os
-DSMALL=0 | 24.7K | 23.5K | 28.2K
-DSMALL=1 | 17.9K | 17.2K | 19.8K
With Clang and Boost:
| -O2 | -O3 | -Os
-DSMALL=0 | 23.9K | 23.9K | 32.5K
-DSMALL=1 | 17.4K | 17.4K | 22.3K
With GCC and Boost:
| -O2 | -O3 | -Os
-DSMALL=0 | 21.8K | 21.8K | 35.5K
-DSMALL=1 | 16.4K | 16.4K | 26.2K
(使用Apple的Xcode的编译器)
现在来看问题:是否有一些令人信服的技术原因使实现者选择省略这个简单的优化?
还有:为什么-Os
的效果与宣传的完全相反?
更新3
根据Nicol Bolas的建议,我用shared_ptr<void/A/B>
而不是裸指针(用make_shared
创建,用static_pointer_cast
转换)重复了测量结果。结果中的趋势是相同的:
With Clang and libc++:
| -O2 | -O3 | -Os
-DSMALL=0 | 27.9K | 26.7K | 30.9K
-DSMALL=1 | 25.0K | 20.3K | 26.8K
With Clang and Boost:
| -O2 | -O3 | -Os
-DSMALL=0 | 35.3K | 34.3K | 43.1K
-DSMALL=1 | 27.8K | 26.8K | 32.6K
发布于 2012-07-04 06:20:21
既然我已经被特别要求发表评论,我会的,尽管我不确定我有更多的东西要比已经说的更多。(抱歉,我花了8天才到这里)
我之前已经为一些容器实现过瘦模板习惯用法,即向量、双端队列和列表。我目前还没有为libc++中的任何容器实现它。而且我从来没有为无序容器实现过它。
它确实节省了代码大小。它还增加了复杂性,比引用的维基图书链接所暗示的要复杂得多。一个人也可以这样做,而不仅仅是为了指针。您可以对所有大小相同的标量执行此操作。例如,为什么int
和unsigned
有不同的实例化?甚至可以将ptrdiff_t
存储在与T*
相同的实例化中。毕竟,这一切都只是底部的一小部分。但在玩这些花招时,要让成员模板正确地使用一系列迭代器是非常棘手的。
但是也有缺点(除了实现困难之外)。它几乎不能很好地与调试器配合使用。至少,它使调试器更难显示容器内部。虽然代码大小的节省可以是显著的,但我不会把代码大小的节省称为戏剧性的。特别是与存储照片、动画、音频片段、街道地图、多年的电子邮件以及来自最好的朋友和家人的所有附件等所需的内存相比,即优化代码大小是很重要的。但你应该考虑到,在今天的许多应用程序中(甚至在嵌入式设备上),如果你将代码大小减半,你的应用程序大小可能会减少5% (诚然,统计数据是凭空得出的)。
我目前的立场是,这种特殊的优化是在链接器而不是模板容器中进行的最好的支付和实现。虽然我知道在链接器中实现这并不容易,但我听说过一些成功的实现。
话虽如此,我仍然尝试在模板中进行代码大小优化。例如,在libc++中,像__hash_map_node_destructor
这样的帮助器结构是在尽可能少的参数上模板化的,因此,如果它们的任何代码都被列出,那么更有可能的是,帮助器的一个实例化可以服务于多个unordered_map
的实例化。这种技术对调试器是友好的,并且不是很难掌握。当应用于迭代器(N2980)时,甚至可以对客户端产生一些积极的副作用。
总而言之,我不会反对代码走得更远,实现这种优化。但我也不会把它归类为十年前那样高的优先级,这是因为链接器技术已经进步,代码大小与应用程序大小的比率已经趋于相当显著的下降。
发布于 2012-06-25 19:17:21
当你有一个void*参数时,在编译时不会进行类型检查。
您提出的这些映射将是程序中的一个缺陷,因为它们将接受类型A*、B*的值元素,甚至更难以想象的与该映射无关的奇特类型。(例如int*,float*;std::string*,CString*,CWnd*...想象一下地图上的乱七八糟的东西…)
你的优化还为时过早。过早的优化是万恶之源。
https://stackoverflow.com/questions/11188204
复制相似问题