c++ - 带有 unordered_map 的模板代码膨胀

Question

我想知道 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

Answer 1

因为有人特别要求我发表评论，所以我会发表评论，但我不确定我要补充的内容比已经说过的要多。 (对不起，我花了 8 天才到这里)

我之前已经为一些容器实现了瘦模板习语，即 vector 、双端队列和列表。我目前没有为 libc++ 中的任何容器实现它。而且我从来没有为无序的容器实现它。

它确实节省了代码大小。它还增加了复杂性，比引用的 wikibooks 链接所暗示的要复杂得多。人们也可以这样做，而不仅仅是指针。您可以对所有具有相同大小的标量执行此操作。例如，为什么 int 和 unsigned 有不同的实例化？甚至 ptrdiff_t 也可以存储在与 T* 相同的实例中。毕竟，这只是底部的一个袋子。但是在玩这些技巧时，要让使用一系列迭代器的成员模板正确是非常棘手的。

虽然有缺点(除了实现困难)。它在调试器中的表现几乎没有那么好。至少它使调试器更难显示容器内部。虽然代码大小的节省可能很重要，但我不会将代码大小的节省称为戏剧性的。尤其是与存储照片、动画、音频剪辑、街道 map 、多年电子邮件以及来自您最好的 friend 和家人的所有附件等所需的内存相比时。即优化代码大小很重要。但是您应该考虑到，在当今的许多应用程序中(甚至在嵌入式设备上)，如果您将代码大小减半，您的应用程序大小可能会减少 5%(诚然，统计数据是凭空而来的)。

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

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

总而言之，我不会反对代码加倍努力并实现此优化。但我也不会像十年前那样把它归为高优先级，因为链接器技术已经取得了进步，而且代码大小与应用程序大小的比率也趋于显着降低。