Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
Жесть. А 10 секунд на это же самое терпимо.

Здравствуйте, GarryIV, Вы писали:

GIV>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>Жесть. А 10 секунд на это же самое терпимо.

Я право не знаю даже как автору удалось получить такой удивительный результат.

#include <windows.h>
#include <list>
#include <string>
#include <stdio.h>

class foo
{
public:
    foo(int x, int y)
    {
        m_x = x;
        m_y = y;
        m_s = "test";
        m_f = "test";
        m_o = "test";
        m_i = "test";
        m_r = "test";
        m_b = "test";
        m_a = "test";
    }

private:
    int m_x;
    int m_y;
    std::string m_s;
    std::string m_f;
    std::string m_o;
    std::string m_i;
    std::string m_r;
    std::string m_b;
    std::string m_a;
};

int main ()
{
    std::list<foo> lst;

    DWORD ticks = GetTickCount ();

    for (int i=0;i<8000;i++)
        lst.push_back (foo(i,i));

    ticks = GetTickCount () - ticks;

    printf("%i, %i\n", ticks, lst.size());
}

вывод:

16, 8000

16 миллисекунд.
C2D 2.2Gz

Здравствуйте, GarryIV, Вы писали:

GIV>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>Жесть. А 10 секунд на это же самое терпимо.

Там дан код к примеру:

[...]что то типа так[...]

Для этого же кода без оптимизации 8000 элементов для списка у меня лично обрабатываются мгновенно.
Возможно в оригинале или полей на порядок больше, или там не std::string, а объекты со сложной инициализацией или... А, гадать долго можно

Что C++ тут непричём...

Очевидно, что код, приведенный по ссылке эквивалентен следующему коду на C:

int len1 = strlen("test");
m_s = malloc(len1 + 1);
strcpy(m_s, "test");
//Аналогично еще 10 раз

ДА, ДА, ДА, std::string использует HEAP. Для большей гибкости компактности синтаксиса ценой производительности. Не нравится — делаем так:

template <int _Len> class FixedSizeString
{
private:
    char Data[_Len];

public:
   //Объявляем необходимые методы, аналогичные std::string
}

Всё, меняем std::string на FixedSizeString<Необходимый_Размер> и имеем стопроцентный сиплюсплюсный аналог char szXXX[размер] = "test".

Здравствуйте, пыщьх, Вы писали:

П>Всё, меняем std::string на FixedSizeString<Необходимый_Размер> и имеем стопроцентный сиплюсплюсный аналог char szXXX[размер] = "test".
Плюс, если там вектор поюзан с поэтапным добавлением элементов без вызова reserve()...

Здравствуйте, GarryIV, Вы писали:

GIV>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>Жесть. А 10 секунд на это же самое терпимо.

Тут С++ ни при чем. Дело в реализации стандартной библиотеки. Хороших реализаций я не видел. Хотите быстро, пишите свою реализацию строки (ну и списка). Контейнеры в STL сделаны поразительно голимо. Хотя бы потому что там куча грязных хаков, макросов, где можно спокойно обойтись без них.

Здравствуйте, Aleх, Вы писали:

A>Здравствуйте, GarryIV, Вы писали:

GIV>>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>>Жесть. А 10 секунд на это же самое терпимо.

A>Тут С++ ни при чем. Дело в реализации стандартной библиотеки. Хороших реализаций я не видел. Хотите быстро, пишите свою реализацию строки (ну и списка). Контейнеры в STL сделаны поразительно голимо. Хотя бы потому что там куча грязных хаков, макросов, где можно спокойно обойтись без них.
Когда писалась стандартная библиотека, оптимизаторы не то что ILP для allocation/scheduling решить, элементарно неиспользуемые переменные убирать не умели. По хорошему, после GCC 4.X (точно не помню, с какой версии появились IRA и прочие подобные фичи) и VS2005 стандартные библиотеки надо переписывать с нуля, дабы не выбирать между читаемостью и скоростью, а переложить весь гимор на оптимизатор...

если это что то значит
в оригинале скорее так

for (int i=0;i<8000;i++)
        lst.push_back (new foo(i,i));

и еще — проблемы не с листом и т.д., а именно с инициализацией.
конечно это код утрированный — реальный отличается всякими ифами и т.п., но тормаза в инициализации.

Здравствуйте, Alex Dav, Вы писали:

AD>в оригинале скорее так
AD>

AD>for (int i=0;i<8000;i++)
AD>        lst.push_back (new foo(i,i));

AD>

AD>и еще — проблемы не с листом и т.д., а именно с инициализацией.
AD>конечно это код утрированный — реальный отличается всякими ифами и т.п., но тормаза в инициализации.

Этот вариант (без оптимизации) тоже не получилось сделать хотя бы 5 секунд, хотя я ставил и 100`000 элементов (g++ 4.4.0). В оригинале поля были вида int и std::string или потяжелее?

А всякие _SECURE_SCL выключены?

Здравствуйте, GarryIV, Вы писали:

GIV>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>Жесть. А 10 секунд на это же самое терпимо.

Вот поэтому я и не люблю эти ваши STL и Boost. List, deque, string и прочие начинают терзать и рвать в клочья аллокатор, из за чего производительность просаживается в тысячи раз, а оверхед по памяти возрастает в десятки. String вообще использовать категорически нельзя. std::vector<char> — более-менее терпимо. А списки и дерева должны быть интрузивными.

Здравствуйте, Alex Dav, Вы писали:

AD>если это что то значит
AD>в оригинале скорее так
AD>

AD>for (int i=0;i<8000;i++)
AD>        lst.push_back (new foo(i,i));

AD>

Почему? Так у тебя только одна аллокация на хипе и несколько копирований указателя
В случае аллокации на стеке получаем помимо создания ещё конструктор копироания, а потом и деструктор. Имхо, это более тяжкий случай.

Здравствуйте, McSeem2, Вы писали:

MS>Здравствуйте, GarryIV, Вы писали:

GIV>>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>>Жесть. А 10 секунд на это же самое терпимо.

MS>Вот поэтому я и не люблю эти ваши STL и Boost. List, deque, string и прочие начинают терзать и рвать в клочья аллокатор, из за чего производительность просаживается в тысячи раз, а оверхед по памяти возрастает в десятки. String вообще использовать категорически нельзя. std::vector<char> — более-менее терпимо. А списки и дерева должны быть интрузивными.
Напиши свой шустрый аллокатор. Или свой string. C++ позволяє

Здравствуйте, Aleх, Вы писали:

GIV>>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>>Жесть. А 10 секунд на это же самое терпимо.

A>Тут С++ ни при чем. Дело в реализации стандартной библиотеки. Хороших реализаций я не видел. Хотите быстро, пишите свою реализацию строки (ну и списка). Контейнеры в STL сделаны поразительно голимо. Хотя бы потому что там куча грязных хаков, макросов, где можно спокойно обойтись без них.

Да это как бы не сильно важно. Компилятор или стандартная библиотека — результат все равно жесткий.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, GarryIV, Вы писали:

GIV>>Наткнулся на http://rsdn.ru/forum/cpp/3873455.1.aspx

Автор: Alex Dav
Дата: 10.07.10

и малость офигел — это вот так вот легко можно получить 80 сек на банальнейшей инициализации листа всего-то 8000 элементами.
GIV>>Жесть. А 10 секунд на это же самое терпимо.

CC>Я право не знаю даже как автору удалось получить такой удивительный результат.
Может он конечно умолчал о чем то...

CC>вывод:
CC>

CC>16, 8000

CC>16 миллисекунд.

Ага. Это то что я и ожидал бы по скорости.

Здравствуйте, пыщьх, Вы писали:

П>Что C++ тут непричём...

Угу, конечно. Я даже на скиптовых языках не знаю как такой результат получить.

А то, что тут есть что оптимизировать даже тому топикстартеру понятно.

Здравствуйте, frogkiller, Вы писали:

F>В случае аллокации на стеке получаем помимо создания ещё конструктор копироания, а потом и деструктор. Имхо, это более тяжкий случай.
Нормальный компилер это всё выкинет задействовав RVO.

Здравствуйте, пыщьх, Вы писали:

П>>Всё, меняем std::string на FixedSizeString<Необходимый_Размер> и имеем стопроцентный сиплюсплюсный аналог char szXXX[размер] = "test".
П>Плюс, если там вектор поюзан с поэтапным добавлением элементов без вызова reserve()...
Автор утверждает что там list

Здравствуйте, Aleх, Вы писали:

A>Тут С++ ни при чем. Дело в реализации стандартной библиотеки. Хороших реализаций я не видел. Хотите быстро, пишите свою реализацию строки (ну и списка). Контейнеры в STL сделаны поразительно голимо. Хотя бы потому что там куча грязных хаков, макросов, где можно спокойно обойтись без них.

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

Вы говорите про какие конкретно реализации STL ? Dinkumware, STLPort или SGI ?

Здравствуйте, CreatorCray, Вы писали:

CC>Автор утверждает что там list
Тогда минус последняя фраза; все остальное подходит для любого контейнера.

Здравствуйте, GarryIV, Вы писали:

П>>Что C++ тут непричём...
GIV>Угу, конечно. Я даже на скиптовых языках не знаю как такой результат получить.
Скомпилировать интерпретатор без оптимизации. Будет тот же результат. Не в языке дело, а в способе использования.

GIV>А то, что тут есть что оптимизировать даже тому топикстартеру понятно.
В любой нетривиальной программе всегда есть, что оптимизировать.