17

我想知道是否unordered_map使用类型擦除来实现，因为unordered_map<Key, A*>andunordered_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
4

2 回答 2

10

既然有人特别要求我发表评论，我会的，尽管我不确定我要补充的内容比已经说过的要多。（对不起，我花了 8 天才到这里）

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

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

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

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

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

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

于 2012-07-03T22:20:20.883 回答
-1

当你有一个 void* 参数时，编译时没有类型检查。

您提出的此类映射将是程序中的一个缺陷，因为它们将接受 A*、B* 类型的值元素，甚至更难以想象的与该映射无关的花哨类型。（例如 int*、float*；std::string*、CString*、CWnd*...想象一下您的地图中的混乱情况...）

您的优化还为时过早。过早的优化是万恶之源。

于 2012-06-25T11:17:21.073 回答