模板代码与unordered_map

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (200)

我想知道是否unordered_map使用类型擦除来实现,因为unordered_map<Key, A*>unordered_map<Key, B*>可以使用完全相同的代码(除了投射,这是机器代码中的禁用操作)。也就是说,两者的实现都可以基于unordered_map<Key, void*>保存代码大小。

所以我写了这个小测试:

#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是广告的完全相反的效果?

我重复了测量,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
提问于
用户回答回答于

对于某些容器,我已经实现了精简模板语法,即vector,deque和list。我目前没有将它用于libc ++中的任何容器。我从来没有为无序容器实现它。

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

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

我目前的立场是,这个特定的优化是最好的支付和实现的连接器,而不是在模板容器。虽然我知道这在连接器中并不容易实现,但我听说过成功的实现。

话虽如此,我仍然尝试在模板中进行代码大小优化。例如,在libc ++帮助程序结构中,例如__hash_map_node_destructor在尽可能少的参数上进行模板化,因此,如果任何代码被概括,那么帮助程序的一个实例化可能服务多个实例化的可能性更大unordered_map。这种技术对调试器友好,并且不太难以正确。当应用于迭代器(N2980)时,甚至可以为客户端带来一些积极的副作用。

总之,我不会违反代码来进行额外的工作并实施这种优化。但我也不会将它列为十年前的高优先级,这既是因为链接器技术已取得进展,代码大小与应用程序大小的比例趋于相当大幅下降。

用户回答回答于

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

你提出的这些地图在程序中会是一个缺陷,因为它们会接受A *,B *类型的价值元素,甚至更难以想象的花式类型,这些类型在该地图中无关紧要。(例如int *,float *; std :: string *,CString *,CWnd * ...想象地图中的混乱......)

扫码关注云+社区

领取腾讯云代金券