使用unordered_map的模板代码膨胀

Question

我想知道是否unordered_map使用类型擦除实现,因为unordered_map<Key, A*>并且unordered_map<Key, B*>可以使用完全相同的代码(除了强制转换,这是机器代码中的无操作).也就是说,两者的实现可以基于unordered_map<Key, void*>保存代码大小.

更新:此技术通常被称为精简模板成语(感谢下面的评论者指出这一点).

更新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

Answer 1

由于我已被特别要求发表评论,我会尽管,但我不确定我还有更多要补充的内容.(对不起我花了8天才到这里)

我之前为一些容器实现了瘦模板习语,即vector,deque和list.我目前没有为libc ++中的任何容器实现它.我从来没有为无序容器实现它.

它确实节省了代码大小.它还增加了复杂性,远远超过引用的wikibooks链接所暗示的内容.人们也可以做的不仅仅是指针.您可以为具有相同大小的所有标量执行此操作.例如,为什么有不同的实例int和unsigned？甚至ptrdiff_t可以存储在同一个实例中T*.毕竟,它只是底部的一个袋子.但是,在播放这些技巧时,获取使一系列迭代器正确的成员模板非常棘手.

但是存在缺点(除了实施的困难).它与调试器的效果差不多.至少它使调试器更难以显示容器内部.虽然代码大小的节省可能很大,但我还是会停止调用代码大小的节省.特别是与存储照片,动画,音频剪辑,街道地图,多年电子邮件以及最好的朋友和家人的所有附件等所需的内存相比.即优化代码大小非常重要.但是你应该考虑到今天的许多应用程序(甚至在嵌入式设备上),如果你将代码大小减少一半,你可能会将你的应用程序大小减少5%(统计数据确实从空气中消失).

我目前的立场是,这种特殊的优化是在链接器中而不是在模板容器中最好的付费和实现.虽然我知道在链接器中实现起来并不容易,但我听说过成功的实现.

话虽这么说,我仍然尝试在模板中进行代码大小优化.例如,在libc ++帮助器结构中,例如__hash_map_node_destructor在尽可能少的参数上进行模板化,因此如果它们的任何代码被概述,则更有可能的是,助手的一个实例可以提供多个实例化unordered_map.这种技术对调试器很友好,而且难以理解.当应用于迭代器时,甚至可以为客户端产生一些积极的副作用(N2980).

总而言之,我不会反对代码来加倍努力并实现这种优化.但我也不会像十年前那样将其归类为优先级,因为链接器技术已经取得进展,并且代码大小与应用程序大小的比率趋于相当大幅度下降.