Есть ли документация, сравнивающая / противопоставляющая реализации стандартной библиотеки C ++? [закрыто]

16

(Это не программирование игры само по себе, но я уверен, что если бы я спросил об этом на ТАК, мне сказали бы не преждевременно оптимизировать, хотя история говорит нам, что каждая большая игра заканчивает тем, что беспокоится об этих вещах.)

Существует ли документ, в котором обобщены различия в производительности и, в частности, в использовании памяти между различными реализациями стандартной библиотеки C ++? Детали некоторых реализаций защищены NDA, но сравнение между даже STLport против libstdc ++ против libc ++ против MSVC / Dinkumware (против EASTL?) Кажется очень полезным.

В частности, я ищу ответы на такие вопросы, как:

  • Сколько накладных расходов памяти связано со стандартными контейнерами?
  • Какие контейнеры, если они есть, выполняют динамическое распределение, просто будучи объявленными?
  • Делает ли std :: string копирование при записи? Оптимизация коротких строк? Канаты?
  • Использует ли std :: deque кольцевой буфер или это дерьмо?

источник
У меня сложилось впечатление, что dequeвсегда было реализовано в STL с вектором.
Тетрад
@Tetrad: Еще несколько недель назад я тоже был, но потом я прочитал, что это часто реализовывалось в виде веревочной структуры - и это похоже на то, что есть в STLport.
STL имеет открытый рабочий проект , который можно использовать для поиска информации о различных структурах данных (как последовательных, так и ассоциативных), алгоритмах и реализованных вспомогательных классах. Тем не менее, похоже, что в этом случае накладные расходы памяти зависят от реализации, а не от спецификации.
Томас Рассел
3
@Duck: Разработка игр - это единственное место, о котором я знаю, что регулярно использует высокоуровневые функции C ++, но при этом необходимо тщательно отслеживать распределение памяти, поскольку оно работает в системах с малой памятью и без виртуальной памяти. Каждый ответ на SO будет «не преждевременно оптимизировать, STL в порядке, используйте его!» - 50% ответов здесь до сих пор таковы - и тем не менее тест Майка явно показывает серьезную озабоченность играми, желающими использовать std :: map, и путаницу Тетрада и моих мнений по поводу общих реализаций std :: deque аналогичным образом.
2
@Joe Wreschnig Я не хочу голосовать, чтобы закрыть, потому что я заинтересован в результате этого. : p
Коммунистическая утка

Ответы:

6

В случае, если вы не найдете такой диаграммы сравнения, альтернативой является добавление собственного распределителя в рассматриваемые классы STL и добавление некоторой регистрации.

Реализация, которую я тестировал (VC 8.0), не использует выделение памяти, просто объявляя строку / вектор / deque, но для него есть список и отображение. Строка имеет короткую строковую оптимизацию, так как добавление 3 символов не вызывает выделения. Вывод добавляется под кодом.

// basic allocator implementation used from here
// http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <map>

template <class T> class my_allocator;

// specialize for void:
template <> 
class my_allocator<void> 
{
public:
    typedef void*       pointer;
    typedef const void* const_pointer;
    // reference to void members are impossible.
    typedef void value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };
};

#define LOG_ALLOC_SIZE(call, size)      std::cout << "  " << call << "  " << std::setw(2) << size << " byte" << std::endl

template <class T> 
class my_allocator 
{
public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U> 
    struct rebind 
    { 
        typedef my_allocator<U> other; 
    };

    my_allocator() throw() : alloc() {}
    my_allocator(const my_allocator&b) throw() : alloc(b.alloc) {}

    template <class U> my_allocator(const my_allocator<U>&b) throw() : alloc(b.alloc) {}
    ~my_allocator() throw() {}

    pointer       address(reference x) const                    { return alloc.address(x); }
    const_pointer address(const_reference x) const              { return alloc.address(x); }

    pointer allocate(size_type s, 
               my_allocator<void>::const_pointer hint = 0)      { LOG_ALLOC_SIZE("my_allocator::allocate  ", s * sizeof(T)); return alloc.allocate(s, hint); }
    void deallocate(pointer p, size_type n)                     { LOG_ALLOC_SIZE("my_allocator::deallocate", n * sizeof(T)); alloc.deallocate(p, n); }

    size_type max_size() const throw()                          { return alloc.max_size(); }

    void construct(pointer p, const T& val)                     { alloc.construct(p, val); }
    void destroy(pointer p)                                     { alloc.destroy(p); }

    std::allocator<T> alloc;
};

int main(int argc, char *argv[])
{

    {
        typedef std::basic_string<char, std::char_traits<char>, my_allocator<char> > my_string;

        std::cout << "===============================================" << std::endl;
        std::cout << "my_string ctor start" << std::endl;
        my_string test;
        std::cout << "my_string ctor end" << std::endl;
        std::cout << "my_string add 3 chars" << std::endl;
        test = "abc";
        std::cout << "my_string add a huge number of chars chars" << std::endl;
        test += "d df uodfug ondusgp idugnösndögs ifdögsdoiug ösodifugnösdiuödofu odsugöodiu niu od unoudö n nodsu nosfdi un abc";
        std::cout << "my_string copy" << std::endl;
        my_string copy = test;
        std::cout << "my_string copy on write test" << std::endl;
        copy[3] = 'X';
        std::cout << "my_string dtors start" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "vector ctor start" << std::endl;
        std::vector<int, my_allocator<int> > v;
        std::cout << "vector ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            v.push_back(i);
        }
        std::cout << "vector dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "deque ctor start" << std::endl;
        std::deque<int, my_allocator<int> > d;
        std::cout << "deque ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "deque insert start" << std::endl;
            d.push_back(i);
            std::cout << "deque insert end" << std::endl;
        }
        std::cout << "deque dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "list ctor start" << std::endl;
        std::list<int, my_allocator<int> > l;
        std::cout << "list ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "list insert start" << std::endl;
            l.push_back(i);
            std::cout << "list insert end" << std::endl;
        }
        std::cout << "list dtor starts" << std::endl;
    }

    {
        std::cout << std::endl << "===============================================" << std::endl;
        std::cout << "map ctor start" << std::endl;
        std::map<int, float, std::less<int>, my_allocator<std::pair<const int, float> > > m;
        std::cout << "map ctor end" << std::endl;
        for(int i = 0; i < 5; ++i)
        {
            std::cout << "map insert start" << std::endl;
            std::pair<int, float> a(i, (float)i);
            m.insert(a);
            std::cout << "map insert end" << std::endl;
        }
        std::cout << "map dtor starts" << std::endl;
    }

    return 0;
}

На данный момент VC8 и STLPort 5.2 протестированы, вот сравнение (включено в тест: строка, вектор, deque, list, map)

                    Allocation on declare   Overhead List Node      Overhead Map Node

VC8                 map, list               8 Byte                  16 Byte
STLPort 5.2 (VC8)   deque                   8 Byte                  16 Byte
Paulhodge's EASTL   (none)                  8 Byte                  16 Byte

Выходная строка VC8 / вектор / deque / list / map:

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    128 byte
my_string copy
  my_allocator::allocate    128 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  128 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    12 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate  12 byte
  my_allocator::allocate    24 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  24 byte

===============================================
deque ctor start
deque ctor end
deque insert start
  my_allocator::allocate    32 byte
  my_allocator::allocate    16 byte
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
  my_allocator::allocate    16 byte
deque insert end
deque dtor starts
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  16 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
  my_allocator::allocate    12 byte
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
  my_allocator::allocate    24 byte
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

STLPort 5.2. вывод скомпилирован с VC8

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::deallocate   0 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
deque ctor start
  my_allocator::allocate    32 byte
  my_allocator::allocate    128 byte
deque ctor end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque insert start
deque insert end
deque dtor starts
  my_allocator::deallocate  128 byte
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte

Результаты EASTL , нет доступной deque

===============================================
my_string ctor start
my_string ctor end
my_string add 3 chars
  my_allocator::allocate     9 byte
my_string add a huge number of chars chars
  my_allocator::allocate    115 byte
  my_allocator::deallocate   9 byte
my_string copy
  my_allocator::allocate    115 byte
my_string copy on write test
my_string dtors start
  my_allocator::deallocate  115 byte
  my_allocator::deallocate  115 byte

===============================================
vector ctor start
vector ctor end
  my_allocator::allocate     4 byte
  my_allocator::allocate     8 byte
  my_allocator::deallocate   4 byte
  my_allocator::allocate    16 byte
  my_allocator::deallocate   8 byte
  my_allocator::allocate    32 byte
  my_allocator::deallocate  16 byte
vector dtor starts
  my_allocator::deallocate  32 byte

===============================================
list ctor start
list ctor end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list insert start
  my_allocator::allocate    12 byte
list insert end
list dtor starts
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte
  my_allocator::deallocate  12 byte

===============================================
map ctor start
map ctor end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map insert start
  my_allocator::allocate    24 byte
map insert end
map dtor starts
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
  my_allocator::deallocate  24 byte
Майк Земдер
источник
Это полезно для получения подробной информации о базовых распределениях, но, к сожалению, ничего не говорит нам о накладных расходах и ожидаемой производительности кэша.
@ Хорошо, трудно ответить на все ваши вопросы в одном ответе. Я не уверен, что именно вы имеете в виду под «накладными расходами» и более того, по сравнению с чем? Я думал, что накладные расходы вы имеете в виду потребление памяти.
Майк Земдер
Под «накладными расходами» я понимал больше размер пустых экземпляров структур и всех связанных с ними итераторов, а также то, как более сложные обрабатывают распределение - например, выполняет ли std :: list внутренне выделение более одного узла за раз, или я оплатить базовую стоимость размещения для каждого узла и т. д.?
1
Вопрос не столько в том, «пожалуйста, сделайте это сравнение», сколько в «где ресурс для этого сравнения» - я не думаю, что SO - это хорошее место, чтобы «поддерживать» его. Возможно, вы должны начать выкидывать это на сайте Google или вики или что-то.
1
@ Хорошо, теперь он здесь: p Я не очень заинтересован в перемещении его на другой сайт, меня просто интересуют результаты.
Майк Земдер
8

std::stringне делает копирование при записи. Раньше CoW был оптимизацией, но как только несколько потоков входят в изображение, это выходит за рамки пессимизации - это может замедлить код из-за огромных факторов. Это так плохо, что стандарт C ++ 0x активно запрещает это как стратегию реализации. Не только это, но вседозволенностьstd::string изменчивых итераторов и ссылок на символы означает, что «запись» для std::stringвлечет за собой почти каждую операцию.

Я полагаю, что оптимизация коротких строк составляет около 6 символов или что-то в этом регионе. Канаты не допускаются - std::stringдолжны хранить непрерывную память для c_str()функции. Технически, вы могли бы поддерживать непрерывную нить и веревку в одном классе, но никто никогда не делал этого. Более того, из того, что я знаю о веревках, сделать их поточнобезопасными для манипуляции было бы невероятно медленно - возможно, так же плохо или хуже, чем CoW.

Ни один контейнер не выполняет выделение памяти, будучи объявленным в современных STL. Контейнеры на основе узлов, такие как list и map, использовали для этого, но теперь они имеют встроенную конечную оптимизацию и не нуждаются в ней. Обычно выполняется оптимизация, называемая «swaptimization», когда вы меняете местами пустой контейнер. Рассмотреть возможность:

std::vector<std::string> MahFunction();
int main() {
    std::vector<std::string> MahVariable;
    MahFunction().swap(MahVariable);
}

Конечно, в C ++ 0x это избыточно, но в C ++ 03 тогда, когда это обычно используется, если MahVariable выделяет память при объявлении, тогда это снижает эффективность. Я точно знаю, что это было использовано для более быстрого перераспределения контейнеров, таких какvector в MSVC9 STL, что избавило от необходимости копировать элементы.

dequeиспользует что-то, что называется развернутым связанным списком. Это в основном список массивов, обычно в узле фиксированного размера. Таким образом, для большинства применений он сохраняет преимущества как смежного доступа к структурам данных, так и удаления амортизированного O (1), а также возможность добавления как к передней, так и к задней части, и лучшей аннулирования итераторов, чем vector. dequeникогда не может быть реализовано вектором из-за его алгоритмической сложности и гарантий недействительности итераторов.

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

DeadMG
источник
«Это так плохо, что стандарт C ++ 0x активно запрещает это как стратегию реализации». И они запрещают это, потому что предыдущие реализации использовали это, или пытались использовать это. Вы, очевидно, живете в мире, где все постоянно используют новейшие оптимально реализованные STL. Этот ответ совсем не полезен.
Мне также любопытно, какие свойства std :: deque, по вашему мнению, предотвращают смежное базовое хранилище - итераторы действительны только после удаления в начале / конце, а не в середине или после каких-либо вставок, что легко сделать с помощью вектора. И использование циклического буфера, кажется, отвечает всем алгоритмическим гарантиям - амортизированные O (1) вставляют и удаляют на концах, O (n) удаляют в середине.
3
@Joe: Я думаю, что CoW считается плохой вещью с конца 90-х годов. Существуют строковые реализации, которые использовали это, в частности, CString, но это не значит, что так было std::stringраньше. Для этого вам не нужно использовать новейшие и лучшие реализации STL. msdn.microsoft.com/en-us/library/22a9t119.aspx говорит: «Если элемент вставлен спереди, все ссылки остаются действительными». Не уверен, как вы собираетесь реализовать это с циклическим буфером, так как вам нужно будет изменить размер, когда он будет заполнен.
DeadMG
gotw.ca/publications/optimizations.htm . Июль 1999 г.
DeadMG
Я, конечно, не собираюсь защищать COW как метод реализации, но я также не наивен относительно того, как часто программное обеспечение продолжает внедряться, используя плохие методы, даже после того, как они определены как плохие. Например, приведенный выше тест Майка обнаруживает современный stdlib, который выделяет при объявлении. Спасибо за указатель на правильность ссылки deque. (К слову, вектор может отвечать всем гарантиям недействительности итераторов и сложности алгоритма; это требование не является ни тем, ни другим.) Во всяком случае, я рассматриваю это как дальнейшую потребность в документе, подобном моему вопросу.
2

Вопрос не столько в том, «Пожалуйста, сделайте это сравнение», сколько в том, «где находится ресурс для этого сравнения».

Если это действительно ваш вопрос (который, безусловно, нет тому, что вы сказали в тексте вашего фактического вопроса, который закончился 4 вопросами, ни один из которых не спрашивал, где вы можете найти ресурс), тогда ответ будет простым:

Там нет ни одного.

Большинству программистов на C ++ не нужно сильно беспокоиться о накладных расходах стандартных библиотечных структур, о производительности их кеша (что очень любом случае зависит от компилятора) или подобных вещах. Не говоря уже о том, что вы обычно не выбираете стандартную реализацию библиотеки; вы используете то, что поставляется с вашим компилятором. Так что, даже если он делает некоторые неприятные вещи, варианты альтернатив ограничены.

Конечно, есть программисты, которым не безразличны подобные вещи. Но все они давным-давно клялись в использовании стандартной библиотеки.

Итак, у вас есть одна группа программистов, которым просто все равно. И еще одна группа программистов, которым было бы все равно, если бы они ее использовали, но, поскольку они ею не пользуются, им все равно. Поскольку никто не заботится об этом, нет никакой реальной информации об этом. Здесь и там есть неофициальные участки информации (в Effective C ++ есть раздел, посвященный реализациям std :: string и огромным различиям между ними), но они не являются исчерпывающими. И, конечно, ничего не обновлялось.

Николь Болас
источник
Спекулятивный ответ. +1, вероятно, правда, -1, если нет способа доказать это.
замедленная
Я видел много очень хороших и подробных сравнений в прошлом, но все они устарели. Все, что было до введения переезда, в настоящее время не имеет большого значения.
Питер - Унбан Роберт Харви