Товарищи после обновления с 4.7 на 4.8.1 получили жуткие тормоза и набор всяческих странных спецэффектов. Причем в 4.7 все работало отлично. Пришлось вооружиться профайлером и дебаггером, убить пару часов чтобы найти постине феерический баг [C++0x] std::list::size complexity

Оказывается, эти гении в GNU специально сломали совместимость со стандартом C++ 11, где английским по пустому листу сказано — size() должен иметь complexity O(1), на что у нас во многих местах заложена логика. Причина, которую там называют — мол, с C++98 size() был O(n), и чтобы не ломать бинарную совместимость (и не добавлять счетчик в std::list) эти гении тупо считают size() как distance(being(), end())

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

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

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

И этот кто-то -- комитет, так как менять сложность метода между версиями --

Впрочем вы тоже молодцы, заложились на такое тонкое место.
В любом случае это повод заменить list на самописный...

E>И этот кто-то -- комитет, так как менять сложность метода между версиями --

Не то чтобы меняли... В C++98 допускалось для list иметь O(n) или O(1) (implementation defined), начиная, кажется, с C++03 уже было O(1). Как минимум про 4.7 я точно могу сказать, что работало как надо. Привыкли, расслабились, и получили.

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

SD>Не то чтобы меняли... В C++98 допускалось для list иметь O(n) или O(1) (implementation defined), начиная, кажется, с C++03 уже было O(1). Как минимум про 4.7 я точно могу сказать, что работало как надо. Привыкли, расслабились, и получили.

Ну это всё демонстрирует одно из свойств стандарта, из-за чего юзать stl опасно. Там слишком много неопределённостей...

Если мне не изменяет память, то в 03 ещё было можно и так и сяк. Но какая разница в какой момент комитет поменял правила? Вот я например, придерживаюсь политики "поменял семантику -- поменяй и идентификатор", а они, похоже, нет...

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

SD>Товарищи после обновления с 4.7 на 4.8.1 получили жуткие тормоза и набор всяческих странных спецэффектов. Причем в 4.7 все работало отлично. Пришлось вооружиться профайлером и дебаггером, убить пару часов чтобы найти постине феерический баг [C++0x] std::list::size complexity

SD>Оказывается, эти гении в GNU специально сломали совместимость со стандартом C++ 11, где английским по пустому листу сказано — size() должен иметь complexity O(1), на что у нас во многих местах заложена логика. Причина, которую там называют — мол, с C++98 size() был O(n), и чтобы не ломать бинарную совместимость (и не добавлять счетчик в std::list) эти гении тупо считают size() как distance(being(), end())

ну насколько я помню там терки были о все сводилось к тому, что или size() константный и splice() становится линейным вместо константного, каким он был когда size() был O(n), ... или одно из двух...

мне лично "по душе", как все было -- т.е. size() у листа O(n) как и положено иметь list'у (будучи тупой структурой данных), но вот константность splice() мне лично кучу раз пригоджалась (в отличии от size(), о котором я с универа не думал как о константной операции), чем и был для меня привлекателен std::list...

а сейчас я испытываю ровно противоположные эмоции про комитетчиков, которые, наверное ориентируясь на стоны java программистов сделали size() константным (в ущерб splice())...

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

аналогично, но применительно к комитетчикам

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

E>В любом случае это повод заменить list на самописный...

Скорее это повод работать на кондовом C++ обр. 98 г., предоставляя более молодым и нетерпеливым пасюкам почетное право первыми сунуть башку в крысоловку

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

SD> на что у нас во многих местах заложена логика.

Что за логика, если не секрет?

SD> Причина, которую там называют — мол, с C++98 size() был O(n), и чтобы не ломать бинарную совместимость (и не добавлять счетчик в std::list) эти гении тупо считают size() как distance(being(), end())

Я согласен со Степановым:

size() used to be linear time in case of STL lists. It was the right decision since if a user wants to keep a count it is easy to do, but usually you do not need it and it makes splice linear time (it used to be constant). But the standard committee insisted that I change it to constant time. I had no choice. We will have to change this requirement eventually.

splice у списка должен быть константным. У std::forward_list вообще нет size().

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

Там где важно, я использую Boost.Container — получается единообразно на всех платформах.

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

E>Если мне не изменяет память, то в 03 ещё было можно и так и сяк. Но какая разница в какой момент комитет поменял правила? Вот я например, придерживаюсь политики "поменял семантику -- поменяй и идентификатор", а они, похоже, нет...

Не вижу смысла в этом конкретном случае — сам же говоришь что можно было и O(1) и O(N).
В C++11 просто сузили допустимые варианты, причём новые варианты являются подмножеством старых
Тот кто в старых версиях закладывался на одно из проведений — ССЗБ.
В этой ситуации формально виновата libstdc++

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

EP>В C++11 просто сузили допустимые варианты, причём новые варианты являются подмножеством старых
Ну и вынудили авторов популярных обеих двух реализаций поменять семантику не меняя идентификаторов...

EP>Тот кто в старых версиях закладывался на одно из проведений — ССЗБ.
Ну, я бы даже расширил, тот, кто вообе закладывался на какие-то особенности поведения stl -- ССЗБ.
Только беда тут в том, что в большом проекте единственный путь не закладываться состоит в том, что не надо вообще в подобных алгоритмах контейнеры из stl юзать...
EP>В этой ситуации формально виновата libstdc++
Либа виновата быть не может, всегда виноваты люди...

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

EP>>В C++11 просто сузили допустимые варианты, причём новые варианты являются подмножеством старых
E>Ну и вынудили авторов популярных обеих двух реализаций поменять семантику не меняя идентификаторов...

А какая вторая?

EP>>Тот кто в старых версиях закладывался на одно из проведений — ССЗБ.
E>Ну, я бы даже расширил, тот, кто вообе закладывался на какие-то особенности поведения stl -- ССЗБ.

На особенности _реализации_.

E>Только беда тут в том, что в большом проекте единственный путь не закладываться состоит в том, что не надо вообще в подобных алгоритмах контейнеры из stl юзать...

Если нужны какие-то особенности, то нужно использовать одну конкретную реализацию. Помимо тех что идут из коробки, есть и stand-alone.

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


EP>Помимо тех что идут из коробки, есть и stand-alone.

Тут тоже легко нарваться, особенно в библиотечном коде...
ей-ей, намного проще написать свой какой-то список, не std::list, а что-то_другое::list и не морочится

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

EP>>Помимо тех что идут из коробки, есть и stand-alone.
E>Тут тоже легко нарваться

Но это ведь не проблема STL, а вообще любых сторонних библиотек, на любую тему

E>ей-ей, намного проще написать свой какой-то список, не std::list, а что-то_другое::list и не морочится

1. Всё-таки есть уже готовые: boost::container::list, boost::intrusive::list
2. Если свой, то лучше не list, а что-то типа list_pool — когда несколько list'ов живут в одном vector'е: например.

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

EP>Но это ведь не проблема STL, а вообще любых сторонних библиотек, на любую тему

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


EP>1. Всё-таки есть уже готовые: boost::container::list, boost::intrusive::list
Ну если буст вообще юзать, то можно и их взять.

EP>2. Если свой, то лучше не list, а что-то типа list_pool — когда несколько list'ов живут в одном vector'е: например.

Ну это уже от целей и задач зависит, однако.

Мда, вот и выросло поколение, не помнящее кипеж вокруг std::vector<bool> , спецификаций исключений, перегрузки по целому и указателю, экспорта шаблонов и прочих ныне легендарных гоч "старого" C++. А сколько новых граблей рассыпано по новому стандарту щедрой, так сказать, рукой, отцов, так сказать, основателей

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

SD>Товарищи после обновления с 4.7 на 4.8.1 получили жуткие тормоза и набор всяческих странных спецэффектов. Причем в 4.7 все работало отлично. Пришлось вооружиться профайлером и дебаггером, убить пару часов чтобы найти постине феерический баг [C++0x] std::list::size complexity

SD>Оказывается, эти гении в GNU специально сломали совместимость со стандартом C++ 11, где английским по пустому листу сказано — size() должен иметь complexity O(1), на что у нас во многих местах заложена логика. Причина, которую там называют — мол, с C++98 size() был O(n), и чтобы не ломать бинарную совместимость (и не добавлять счетчик в std::list) эти гении тупо считают size() как distance(being(), end())

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

Отрывать руки надо тем, кто бездумно пользуется стандартной библиотекой в серьёзных проектах.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

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

SD>Товарищи после обновления с 4.7 на 4.8.1 получили жуткие тормоза и набор всяческих странных спецэффектов. Причем в 4.7 все работало отлично. Пришлось вооружиться профайлером и дебаггером, убить пару часов чтобы найти постине феерический баг [C++0x] std::list::size complexity

SD>Оказывается, эти гении в GNU специально сломали совместимость со стандартом C++ 11, где английским по пустому листу сказано — size() должен иметь complexity O(1), на что у нас во многих местах заложена логика. Причина, которую там называют — мол, с C++98 size() был O(n), и чтобы не ломать бинарную совместимость (и не добавлять счетчик в std::list) эти гении тупо считают size() как distance(being(), end())

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

т.е. все грабли и тормоза, из-за единственного list::size()? я все правильно понял?
да, это действительно ужасно.

EP>Что за логика, если не секрет?

Не секрет — есть (большой) пул соединений, и в паре мест брался их size(), чтобы определить, надо еще запуливать, или пока хватит.

boost по ограничениям нетехнического характера использовать в этом проекте не можем.

E>Ну, я бы даже расширил, тот, кто вообе закладывался на какие-то особенности поведения stl -- ССЗБ.

Это не особенности поведения STL, а таки стандарт C++. Как раз на implementation defined особенности у нас нигде не было закладок.

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

EP>>Что за логика, если не секрет?
SD>Не секрет — есть (большой) пул соединений, и в паре мест брался их size(), чтобы определить, надо еще запуливать, или пока хватит.

А подробней. Может там достаточно vector'а или deque'и?

EP>А подробней. Может там достаточно vector'а или deque'и?

vector при insert/erase инвалидирует все итераторы и ссылки.
аналогично, deque инвалидирует итераторы при erase не из начала/конца.

Попробую объяснить, почему это важно. Пул соединений реализован следующим образом: внутри есть два списка, pending и connected. Новые соединения (которые находятся в неблокирующем connect()) попадают в первый список, и по завершению handshake соединение двигается из pending в connected, где и сидит в ожидании, когда его вынут для совершения полезной работы.

Примерно вот так:

pending_.emplace_back(new connection(service_, endpoint_));
connection_list_t::iterator it = pending_.end();

(*it)->async_connect([this, it](int _errno)
    {
        std::unique_ptr<connection> c = std::move(*it);
        pending_connect_.erase(it);

        if (_errno == 0)
            ready_conn = ready_.insert(ready_.end(), std::move(c));
    });

Конечно, код на самом деле чуть сложнее, но общую идею должно быть видно. Не исключаю, что есть способы сделать это более удобно или эффективно. Если вы их знаете, подсказывайте.