Код шаблона вздувается с unordered_map

Я задавался вопросом, реализуется ли unordered_map с использованием стирания типа, поскольку unordered_map<Key, A*> и unordered_map<Key, B*> могут использовать точно такой же код (кроме кастинга, который не является оператором в машинный код). То есть реализация обоих может быть основана на unordered_map<Key, void*> для сохранения размера кода.

Обновление: Этот метод обычно называют Thin Template Idiom (спасибо комментаторам ниже для указав это).

Обновление 2: Я был бы особенно заинтересован в Говарде Хиннанте. Пусть он надеется, что он это прочитает.

Итак, я написал этот небольшой тест:

#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:

Как предложил Никол Болас, я повторил измерения с помощью 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

Ответ 1

Поскольку меня специально попросили прокомментировать, я буду, хотя я не уверен, что добавить гораздо больше, чем уже было сказано. (извините, мне потребовалось 8 дней, чтобы добраться сюда)

Я реализовал тонкую идиому шаблона раньше, для некоторых контейнеров, а именно vector, deque и list. В настоящее время я не реализовал его для любого контейнера в libС++. И я никогда не применял его для неупорядоченных контейнеров.

Он сохраняет размер кода. Это также добавляет сложности, намного больше, чем предполагает ссылка на ссылку wikibooks. Можно также сделать это не только для указателей. Вы можете сделать это для всех скаляров, имеющих одинаковый размер. Например, почему существуют разные экземпляры для int и unsigned? Даже ptrdiff_t можно сохранить в том же экземпляре, что и T*. В конце концов, это всего лишь мешочки на дне. Но очень сложно получить шаблоны-члены, которые при использовании этих трюков принимают ряд итераторов.

Есть недостатки, хотя (помимо сложности реализации). Он не играет почти так же хорошо с отладчиком. По крайней мере, для отладчика гораздо сложнее отображать внутренние контейнеры. И хотя экономия размера кода может быть значительным, я бы не стал критиковать экономию размера кода. Особенно по сравнению с памятью, необходимой для хранения фотографий, анимаций, аудиоклипов, уличных карт, лет электронной почты со всеми приложениями от ваших лучших друзей и семьи и т.д. I.e. важно оптимизировать размер кода. Но вы должны принять во внимание, что во многих приложениях сегодня (даже на встроенных устройствах), если вы сократите размер своего кода пополам, вы можете сократить размер вашего приложения на 5% (статистика, по общему признанию, вытягиваемая из воздуха).

Моя текущая позиция заключается в том, что эта конкретная оптимизация - одна из лучших, которую заплатили и внедрили в компоновщик вместо контейнера шаблона. Хотя я знаю, что это непросто реализовать в компоновщике, я слышал об успешных реализациях.

При этом я все еще пытаюсь сделать оптимизацию размера кода в шаблонах. Например, в вспомогательных структурах libС++, таких как __hash_map_node_destructor, шаблоны на как можно меньше параметров, поэтому, если какой-либо из их кодов обрисован в общих чертах, более вероятно, что один экземпляр хелпера может служить более чем одним экземпляром unordered_map, Этот метод является отладчиком дружественным, и не так сложно получить право. И может даже иметь некоторые положительные побочные эффекты для клиента при применении к итераторам (N2980).

В общем, я бы не стал придерживаться этого кода для перехода на лишнюю милю и реализации этой оптимизации. Но я также не стал бы классифицировать его как приоритетный, как это было десять лет назад, и потому, что технология линкеров продвигалась, и соотношение размеров кода и размера приложения, как правило, значительно уменьшалось.

Ответ 1

Ответ 2