Чтобы не рассуждать отвлечённо, рассмотрим две конкретные реализации:
void vector8_inc(std::vector<uint8_t>& v)
{
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
}
void vector32_inc(std::vector<uint32_t>& v)
{
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
}Попробуем угадать
На этот вопрос легко ответить, используя бенчмарк, и чуть позже мы так и сделаем, но для начала попробуем угадать (это называется «рассуждением на основе базовых принципов» – так звучит более наукообразно).
Во-первых, стоит задать вопрос: Каков размер этих векторов?
Что ж, давайте выберем какое-нибудь число. Пусть будет 20 000 элементов в каждом.
Далее, известно, что тестировать мы будем на процессоре Intel Skylake, – посмотрим характеристики команд сложения для 8-битных и 32-битных операндов при непосредственной адресации. Оказывается, основные показатели у них одинаковые: 1 операция на такт и задержка 4 такта на обращение к памяти (1). В данном случае задержка не имеет значения, поскольку каждая операция сложения выполняется независимо, так что расчётная скорость – 1 элемент на такт при условии, что вся остальная работа по выполнению цикла будет проходить в параллельном режиме.
Можно также заметить, что 20 000 элементов соответствуют набору данных размером 20 Кбайт для версии с uint8_t и целых 80 Кбайт для версии с uint32_t. В первом случае они идеально умещаются в кэш уровня L1 современных компьютеров с архитектурой x86, а во втором – нет. Получается, 8-битная версия получит фору благодаря эффективному кэшированию?
Наконец, отметим, что наша задача очень напоминает классический случай автоматической векторизации: в цикле с известным числом итераций выполняется арифметическая операция над элементами, последовательно расположенными в памяти. В таком случае 8-битная версия должна иметь колоссальное преимущество по сравнению с 32-битной версией, так как одна векторная операция будет обрабатывать вчетверо больше элементов и в целом процессоры Intel выполняют векторные операции над однобайтовыми элементами с той же скоростью, что и над 32-битными элементами.
Ладно, хватит разглагольствовать. Пора обратиться к тесту.
Бенчмарк
Я получил следующие тайминги для векторов из 20 000 элементов на компиляторах gcc 8 и clang 8 с разными уровнями оптимизации:
Получается, что, за исключением уровня -O1, вариант с uint32_t быстрее варианта с uint8_t, причём в некоторых случаях значительно: в 5,4 раза на gcc на уровне -O3 и ровно в 8 раз на clang на обоих уровнях, -O2 и -O3. Да-да, инкремент 32-битных целых чисел в std::vector выполняется до восьми раз быстрее, чем инкремент 8-битных целых чисел на популярном компиляторе при стандартных настройках оптимизации.
Как обычно, обратимся к листингу ассемблера в надежде, что он прольёт свет на происходящее.
Вот листинг для gcc 8 на уровне -O2, где 8-битная версия «всего лишь» в 1,5 раза медленнее 32-битной версии (2):
8-bit:
.L3:
inc BYTE PTR [rdx+rax]
mov rdx, QWORD PTR [rdi]
inc rax
mov rcx, QWORD PTR [rdi+8]
sub rcx, rdx
cmp rax, rcx
jb .L332-bit:
.L9:
inc DWORD PTR [rax]
add rax, 4
cmp rax, rdx
jne .L932-битная версия выглядит именно так, как мы и ожидали от неразвёрнутого (3) цикла: инкремент (4) с указанием адреса, затем три команды управления циклом: add rax, 4 – инкремент индуктивной переменной (5) и пара команд cmp и jne для проверки условия выхода из цикла и условного перехода по нему. Выглядит всё здорово – разворачивание компенсировало бы затраты на инкремент счётчика и проверку условия, и наш код почти достиг бы максимально возможной скорости 1 элемент на такт (6), но для приложения с открытым кодом и так сойдёт. А что же в 8-битной версии? Помимо команды inc с указанием адреса выполняются две дополнительные команды чтения из памяти, а также команда sub, взявшаяся непонятно откуда.
Вот листинг с комментариями:
8-bit:
.L3:
inc BYTE PTR [rdx+rax] ; инкремент по адресу v[i]
mov rdx, QWORD PTR [rdi] ; загрузка v.begin
inc rax ; i++
mov rcx, QWORD PTR [rdi+8] ; загрузка v.end
sub rcx, rdx ; end - start (т.е. vector.size())
cmp rax, rcx ; i < size()
jb .L3 ; след. итерация если i < size()Здесь vector::begin и vector::end – это внутренние указатели std::vector, которые он использует для указания на начало и конец последовательности элементов, содержащихся внутри выделенной для него области (7), – это, по сути, те же значения, которые используются для реализации vector::begin() и vector::end() (хотя они и имеют другой тип). Выходит, все дополнительные команды – лишь следствие вычисления vector.size(). Вроде ничего необычного? Но ведь в 32-битной версии, разумеется, тоже вычисляется size(), однако в том листинге этих команд не было. Вычисление size() произошло только один раз – за пределами цикла.
Так в чём же дело? Краткий ответ – алиасинг указателей. Развёрнутый ответ я дам ниже.
Развёрнутый ответ
Вектор v передаётся функции по ссылке, которая, по сути, есть замаскированный указатель. Компилятор должен обратиться к членам v::begin и v::end вектора, чтобы вычислить его размер size(), а в нашем примере size() вычисляется на каждой итерации. Но компилятор не обязан слепо подчиняться исходному коду: он вполне может вынести результат вызова функции size() за пределы цикла, но только если точно знает, что семантика программы от этого не изменится. С этой точки зрения единственным проблемным местом цикла является инкремент v[i]++. Запись происходит по неизвестному адресу. Может ли такая операция изменить значение size()?
Если запись происходит в std::vector<uint32_t> (т.е. по указателю uint32_t *), то нет, она не может изменить значение size(). Запись в объекты типа uint32_t может модифицировать только объекты типа uint32_t, а указатели, задействованные при вычислении size(), имеют другой тип (8).
Однако в случае с uint8_t, по крайней мере на распространённых компиляторах (9), ответ будет таким: да, теоретически значение size() может измениться, так как uint8_t – это псевдоним для unsigned char, а массивы типа unsigned char (и char) могут алиаситься с любым другим типом. Это значит, что, по мнению компилятора, запись по указателям на uint8_t способна модифицировать содержимое памяти неизвестного происхождения по любому адресу (10). Поэтому он предполагает, что каждая операция инкремента v[i]++ может изменить значение size(), и потому вынужден вычислять его заново на каждой итерации цикла.
Мы-то с вами знаем, что запись в память, на которую указывает std::vector, никогда не изменит его собственный size(), ведь это означало бы, что вектор сам каким-то образом был выделен внутри собственной кучи, а это практически невозможно и сродни проблеме курицы и яйца (11). Но компилятору это, к сожалению, неведомо!
Что насчёт остальных результатов?
Хорошо, мы выяснили, почему версия с uint8_ немного медленнее версии uint32_t на gcc на уровне -O2. Но чем объяснить громадную разницу – до 8 раз – на clang или том же gcc на -O3?
Тут всё просто: в случае с uint32_t clang может выполнить автовекторизацию цикла:
.LBB1_6: ; =>This Inner Loop Header: Depth=1
vmovdqu ymm1, ymmword ptr [rax + 4*rdi]
vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 32]
vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 64]
vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 96]
vpsubd ymm1, ymm1, ymm0
vpsubd ymm2, ymm2, ymm0
vpsubd ymm3, ymm3, ymm0
vpsubd ymm4, ymm4, ymm0
vmovdqu ymmword ptr [rax + 4*rdi], ymm1
vmovdqu ymmword ptr [rax + 4*rdi + 32], ymm2
vmovdqu ymmword ptr [rax + 4*rdi + 64], ymm3
vmovdqu ymmword ptr [rax + 4*rdi + 96], ymm4
vmovdqu ymm1, ymmword ptr [rax + 4*rdi + 128]
vmovdqu ymm2, ymmword ptr [rax + 4*rdi + 160]
vmovdqu ymm3, ymmword ptr [rax + 4*rdi + 192]
vmovdqu ymm4, ymmword ptr [rax + 4*rdi + 224]
vpsubd ymm1, ymm1, ymm0
vpsubd ymm2, ymm2, ymm0
vpsubd ymm3, ymm3, ymm0
vpsubd ymm4, ymm4, ymm0
vmovdqu ymmword ptr [rax + 4*rdi + 128], ymm1
vmovdqu ymmword ptr [rax + 4*rdi + 160], ymm2
vmovdqu ymmword ptr [rax + 4*rdi + 192], ymm3
vmovdqu ymmword ptr [rax + 4*rdi + 224], ymm4
add rdi, 64
add rsi, 2
jne .LBB1_6Цикл был развёрнут 8 раз, и это в общем-то максимальная производительность, какую только можно получить: один вектор (8 элементов) на такт для кэша L1 (больше не получится из-за ограничения в одну операцию записи на такт (12)).
Для uint8_t векторизация не производится, потому что ей препятствует необходимость вычислять size() для проверки условия цикла на каждой итерации. Причина отставания всё та же, а само отставание гораздо больше.
Самые низкие тайминги объясняются автовекторизацией: gcc применяет её только на уровне -O3, а clang – и на уровне -O2, и на уровне -O3 по умолчанию. Компилятор gcc на уровне -O3 генерирует несколько более медленный код, чем clang, потому что он не разворачивает автовекторизованный цикл.
Исправляем ситуацию
Мы выяснили, в чём проблема – как же её исправить?
Для начала попробуем один способ, который, правда, не будет работать, – а именно, напишем более идиоматический цикл, основанный на итераторе:
for (auto i = v.begin(); i != v.end(); ++i)
{
(*i)++;
}Код, который сгенерирует gcc на уровне -O2, будет несколько лучше варианта с size():
.L17:
add BYTE PTR [rax], 1
add rax, 1
cmp QWORD PTR [rdi+8], rax
jne .L17Две лишние операции чтения превратились в одну, так как i мы теперь сравниваем с указателем end вектора, а не вычисляем заново size(), вычитая из указателя конца указатель начала вектора. По количеству команд этот код догнал код с uint32_t, поскольку дополнительная операция чтения слилась с операцией сравнения. Однако проблема никуда не делась и автовекторизация по-прежнему недоступна, так что uint8_t всё ещё значительно отстаёт от uint32_t – более чем в 5 раз как на gcc, так и на clang на тех уровнях, где предусмотрена автовекторизация.
Попробуем что-нибудь другое. У нас снова ничего не получится, а точнее, мы найдём ещё один неработающий способ.
В этом варианте мы вычисляем size() только один раз до цикла и помещаем результат в локальную переменную:
for (size_t i = 0, s = v.size(); i < s; i++)
{
v[i]++;
}Вроде бы должно сработать? Проблема была в size(), а теперь мы велели компилятору зафиксировать результат size() в локальной переменной s в начале цикла, а локальные переменные, как известно, не пересекаются с другими данными. Мы фактически сделали то, чего не мог сделать компилятор. И код, который он сгенерирует, действительно будет лучше (по сравнению с первоначальным):
.L9:
mov rdx, QWORD PTR [rdi]
add BYTE PTR [rdx+rax], 1
add rax, 1
cmp rax, rcx
jne .L9Здесь только одна лишняя операция чтения и нет команды sub. Но что делает эта лишняя команда (rdx, QWORD PTR [rdi]), если она не участвует в вычислении размера? Она считывает указатель data() из v!
Выражение v[i] реализуется как *(v.data() + i), а член, возвращаемый data() (и являющийся, по сути, обычным указателем begin), порождает ту же проблему, что и size(). Правда, я эту операцию не заметил в исходном варианте, потому что там она была «бесплатной», ведь её все равно нужно было выполнить, чтобы вычислить размер.
Потерпите ещё чуть-чуть, мы почти нашли решение. Нужно просто убрать из нашего цикла все зависимости от содержимого std::vector. Проще всего это сделать, если немного модифицировать нашу идиому с итератором:
for (auto i = v.begin(), e = v.end(); i != e; ++i)
{
(*i)++;
}Теперь всё круто изменилось (здесь мы сравниваем только версии с uint8_t – в одной мы сохраняем итератор end в локальной переменнойперед циклом, в другой – нет):
Это небольшое изменение дало нам 20-кратный прирост скорости на уровнях с автовекторизацией. Причём код с uint8_t не просто догнал код с uint32_t – он обогнал его почти ровно в 4 раза на gcc -O3 и clang -O2 и -O3, как мы и ожидали в самом начале, полагаясь на векторизацию: в конце концов, именно вчетверо больше элементов может быть обработано векторной операцией и вчетверо меньшая пропускная способность нам требуется – независимо от уровня кэша (13).
Если вы дочитали до этого места, то, должно быть, всё это время восклицали про себя:
А как же for-цикл с обходом диапазона, появившийся в C++11?
Спешу вас обрадовать: он работает! Это, по сути, синтаксический сахар, за которым скрывается почти в том же виде наша версия с итератором, где мы фиксировали указатель end в локальной переменной до начала цикла. Так что быстродействие у него то же.
Если бы нам вдруг вздумалось вернуться в древние, пещерные времена и написать C-подобную функцию, то такой код тоже замечательно сработал бы:
void array_inc(uint8_t* a, size_t size)
{
for (size_t i = 0; i < size; i++)
{
a[i]++;
}
}Здесь указатель на массив a и переменная size передаются в функцию по значению, поэтому они не могут быть изменены в результате записи по указателю a (14) – совсем как локальные переменные. Производительность у этого кода такая же, как у предыдущих вариантов.
Наконец, на тех компиляторах, где эта опция доступна, вы можете объявить вектор с __restrict (15):
void vector8_inc_restrict(std::vector<uint8_t>& __restrict v)
{
for (size_t i = 0; i < v.size(); i++)
{
v[i]++;
}
}Ключевое слово __restrict не входит в стандарт C++, но входит в стандарт C начиная с C99 (как restrict). Если в компиляторе оно реализовано как расширение C++, то, скорее всего, оно будет подчиняться семантике C. Разумеется, в C нет ссылок, поэтому можете мысленно заменить ссылку на вектор указателем на вектор.
Обратите внимание, что restrict не обладает транзитивным свойством: действие спецификатора __restrict, с которым объявлена ссылка на std::vector, распространяется только на члены самого вектора, но не на область кучи, на которую ссылается v.data(). В нашем случае большего не требуется, потому что (как в случае с локальными переменными) достаточно лишь убедить компилятор, что сами по себе члены, указывающие на начало и конец вектора, ни с чем не пересекаются. Оговорка по поводу restrict, однако, всё равно актуальна, так как запись через v.data() может по-прежнему привести к изменению других объектов в вашей функции из-за алиасинга.
Разочарование
Тут мы приходим к последнему – и весьма неутешительному – выводу. Дело в том, что все показанные выше решения применимы только к этому конкретному случаю, когда вектор теоретически может помешать сам себе. Решение заключалось в том, чтобы вынести за пределы цикла или изолировать результат вызова size() или end() вектора, а не в том, чтобы втолковать компилятору, что запись в данные вектора не затрагивает другие данные. Такой код будет сложно масштабировать по мере роста функции.
Проблема алиасинга никуда не делась, и команды записи по-прежнему могут попасть «куда угодно» – просто в этой функции нет других данных, которые могут быть затронуты… пока. Как только в ней появится новый код, всё повторится. Вот пример навскидку. Если в малых циклах у вас происходит запись в массивы из элементов типа uint8_t, придётся воевать с компилятором до конца (16).
Комментарии
Буду рад любым отзывам. У меня пока ещё нет системы комментирования (17), поэтому, как обычно, обсуждение будем вести в этом треде на HackerNews.
- Под обращением к памяти здесь подразумевается, что цепочка зависимостей проходит через память: команды записи по одному и тому же адресу должны считать последнее записанное туда значение, поэтому такие операции являются зависимыми (на практике будет использоваться перенаправление для загрузки (STLF), если запись происходит достаточно часто). Зависимости команды add при обращении к памяти могут проявляться и другими способами, например, через вычисление адреса, но для нашего случая это неактуально.
- Здесь показан только малый цикл; код установки прост, и работает он быстро. Чтобы увидеть листинг целиком, загрузите код в godbolt.
- Может быть, его следует назвать просто «свёрнутым»? Как бы то ни было, компилятор gcc обычно не разворачивает циклы даже на уровнях -O2 и -O3 за исключением особых случаев, когда число итераций невелико и известно на этапе компиляции. Из-за этого gcc показывает более низкие результаты в тестах по сравнению с clang, но зато он существенно экономит на размере кода. Заставить gcc разворачивать циклы можно, применяя профильную оптимизацию или включив флаг -funroll-loops.
- На самом деле команда inc DWORD PTR [rax] в gcc – это упущенная оптимизация: почти всегда лучше использовать команду add [rax], 1, так как она состоит всего лишь из 2 объединённых микроопераций против 3 для inc. В данном случае разница составляет всего лишь около 6%, но, если бы цикл был немного развёрнут – так, чтобы повторялась только операция записи, –разница оказалась бы существеннее (дальнейшее разворачивание уже не играло бы роли, так как мы достигли бы предела в 1 операцию записи на такт, который не зависит от общего числа микроопераций).
- Эту переменную я называю индуктивной, а не просто i, как в исходном коде, потому что компилятор преобразовал единичные операции инкремента i в 4-байтовые инкременты указателя, хранящегося в регистре rax, и соответственно с этим подправил условие цикла. В исходном виде наш цикл адресует элементы вектора, а после этого преобразования он инкрементирует указатель/итератор, что является одним из способов снижения стоимости операций.
- На самом деле, если включить -funroll-loops, на gcc скорость составит 1,08 такта на элемент при 8-кратном разворачивании. Но даже с этим флагом он не будет разворачивать цикл для версии с 8-битными элементами, так что отставание в скорости будет ещё заметнее!
- Эти члены имеют модификатор private, и имена их зависят от реализации, но в stdlibc++ они на самом деле не называются start и finish, как в gcc. Они называются соответственно _Vector_base::_Vector_impl::_M_start и _Vector_base::_Vector_impl::_M_finish, т.е. входят в структуру _Vector_impl, которая является членом _M_impl (причём единственным) класса _Vector_base, а тот, в свою очередь, является базовым классом для std::vector. Ну и ну! К счастью, компилятор легко справляется с этим нагромождением абстракций.
- Стандарт не предписывает, какими должны быть внутренние типы членов std::vector, но в библиотеке libstdc++ они определены просто как Alloc::pointer (где Alloc – это аллокатор для вектора), и для выделенного по умолчанию объекта std::allocated они будут просто указателями типа T*, т.е. обычными указателями на объект – в данном случае uint32_t *.
- Эту оговорку я делаю не просто так. Есть подозрение, что uint8_t может расцениваться как тип, отличный от char, signed char и unsigned char. Поскольку алиасинг работает с символьными типами, это по идее не относится к uint8_t и он должен вести себя как любой другой несимвольный тип. Однако ни один из известных мне компиляторов так не считает: в них всех typedef uint8_t является псевдонимом unsigned char, так что компиляторы не видят между ними разницы, даже если бы они хотели ею воспользоваться.
- Под «неизвестным происхождением» я здесь подразумеваю лишь то, что компилятор не знает, куда указывает содержимое памяти или как оно появилось. Сюда относятся произвольные указатели, переданные в функцию, а также глобальные и статические переменные. Локальные переменные, напротив, хранятся по известным адресам и не пересекаются с другими данными в памяти, поэтому проблемы, связанные с алиасингом, их обычно не затрагивают (разве что локальная переменная каким-то образом покинет свою область видимости). Указатели, созданные с помощью вызовов malloc или new, которые компилятор видит в момент их использования, во многом ведут себя так же, как локальные переменные, по крайней мере с точки зрения некоторых компиляторов: они знают, что такие вызовы выделяют участки памяти, которые больше ни с чем не пересекаются. Впрочем, компиляторы обычно не видят исходный вызов malloc или new.
- Может быть, в случае std::vector это всё-таки возможно? Скажем, мы создали вектор std::vector<uint8_t> a подходящего размера и затем внутри массива a.data() с помощью оператора placement new разместили с соответствующим выравниванием новый вектор b. Теперь вызовем std::swap(a, b), чтобы поменять местами области хранения векторов – получается, вектор b будет находится внутри собственного участка памяти? Вместо перестановки можно напрямую вызвать конструктор перемещения, когда будем размещать вектор b. Практической ценности такой вектор не будет иметь: он сломается при первой же попытке произвести с ним какое-нибудь действие (например, расширить его за счёт добавления нового элемента), что приведёт к очищению выделенной памяти, а значит и к уничтожению самого вектора.
- За один такт можно нормально выровнять только 8 элементов, т.е. на 32 позиции. В данном тесте мне повезло, и объекты std::vector были выравнены именно так по умолчанию.
- Вообще-то можно получить прирост и более чем в 4 раза: это возможно в том случае, если меньший элемент умещается в кэш нижнего уровня, а больший – нет. Именно это и наблюдается в нашем примере: 8-битные элементы вектора умещаются в кэш L1, а 32-битные длиннее его более чем в два раза – зато кэш L2 явно обладает достаточной ёмкостью, поэтому дополнительного прироста скорости не происходит.
- Хотя вектор теоретически может размещаться внутри собственной кучи, указатель – не может: запись по указателю не может изменить сам указатель. У вектора есть дополнительный уровень косвенности, что и делает возможным такой эффект, как в фильме «Начало».
- Цикл в этом примере основан на индексации v[i], но данное решение также работает и с циклом на основе итератора.
- Есть и более радикальные решения. Например, можно создать «непрозрачный» псевдоним, который фактически является просто структурой и служит обёрткой для uint8_t. В сочетании с перегрузкой операторов и, возможно, неявными приведениями типов он будет вести себя, как uint8_t, будучи при этом совсем другим типом с точки зрения компилятора. Примечательно, что это решение прекрасно работает в clang, но совсем не работает в gcc, где даёт тот же код, что и обычный uint8_t. Где-то в недрах своего оптимизатора gcc воспринимает этот тип как символьный вместе со всеми вытекающими проблемами, связанными с алиасингом. Другое решение заключается в том, чтобы завести собственный вектороподобный тип, члены-указатели которого будут объявлены как __restrict.
- Если кто-нибудь может подсказать, где найти быструю и бесплатную систему комментирования, которая работает со статическими сайтами (только не предлагайте Disqus), не имеет рекламы и предоставляет пользователю доступ к данным комментариев (или хотя бы позволяет экспортировать их в нормальном формате), я готов вас выслушать.
Перевод статьи публикуется с разрешения автора. Оригинальная публикация: Travis Downs. Incrementing vectors.
Комментарии (65)
lamerok
13.11.2019 12:27-2Похоже Travis Downs хотел что-то написать для микроконтроллера, потому что там такие вещи уже давно исследованы. И никто в здравом уме не будет делать проверку на границу цикла через вызов функции, всегда так и делали, задаешь константу и потом с ней уже сравниваешь.
Справедливости ради, стоит заметить, что вектор для микроконтроллеров редко используют, вместо этого array, у которого size() это constexpr выражение, поэтому там таких проблем и нет.
И да лучше использовать вообще цикл с обходом диапазона.
anonymous
00.00.0000 00:00
vamireh
13.11.2019 15:03+2никто в здравом уме не будет делать проверку на границу цикла через вызов функции, всегда так и делали, задаешь константу и потом с ней уже сравниваешь
Это проистекает не из здравости ума, а из святой до наивности убеждённости этих разработчиков в том, что если написан вызов функции, то он будет на каждой итерации. Хотя здесь проблема вовсе не в том, что компилятор не умеет оптимизировать, а в том, что не имеет права. Про алиасинг большинство людей, вводящих константу, не только не подумает, а даже и не знает. Как следствие, это выстрелит в другом месте их кода.
PyerK
14.11.2019 12:50В старом с++ на некоторых контейнерах size() имел линейную сложность. Это была жизненная необходимость выносить его из тела цикла.
vamireh
14.11.2019 13:45В «старом» C++ только у std::list метод size мог быть линейным, а мог быть и константным — реализациям предоставлялся выбор. Это сейчас комитет (очевидно, под давлением M$) принял гени
тальное решение сделать std::list::size константным — в результате в стандартной библиотеке у нас больше нет такого абстрактного типа данных как «двусвязный список».
0xd34df00d
14.11.2019 16:36Поддержание константной длины не влияет на асимптотику.
vamireh
14.11.2019 16:58+1Ой, правда что ли? :)
Скажите, а почему тогдаsplice(const_iterator pos, list& other, const_iterator first, const_iterator last)
для случая this != &other даёт линейную сложность от std::distance(first, last)?0xd34df00d
14.11.2019 18:01+1Прошу прощенья, мне стоило уточнить, что речь о типичных для двусвязного списка операциях вроде вставки/удаления вперёд/назад или по итератору.
Если речь заходит о чуть более специфических операциях, то всё становится куда интереснее, так как константный
size()позволяет реализовать ряд других методов (которые, ИМХО, используются как минимум не реже) более эффективно. Howard Hinnant об этом хорошо писал в своё время.vamireh
14.11.2019 18:12Если речь заходит о чуть более специфических операциях, то всё становится куда интереснее, так как константный size() позволяет реализовать ряд других методов (которые, ИМХО, используются как минимум не реже) более эффективно. Howard Hinnant об этом хорошо писал в своё время.
Если есть подобная необходимость, то можно подсчитывать размер внешними средствами. Т.е. из двусвязного списка сделать особую химеру имени std довольно легко, а вот наоборот — нет.
GCU
14.11.2019 19:00Похоже Ваше мнение о сложности std::list не популярно, как и моё :).
По сути «химера» это лишь дополнительное поле размера, которое создаёт линейную сложность лишь при вставке части от другого списка.
Однако при вставке другого списка целиком — сложность константна (т.к. размер вставляемого списка известен).
Исходя из структуры данных «двусвязный список», линейная сложность вставки куска из другого списка действительно «сюрприз». Но для универсальной библиотеки контейнеров это лучше, так как многие другие операции будут эффективнее. Это можно понять и простить :).vamireh
14.11.2019 19:08-1По сути «химера» это лишь дополнительное поле размера, которое создаёт линейную сложность лишь при вставке части от другого списка
Реализация понятна. Речь о внешнем поведении.Однако при вставке другого списка целиком — сложность константна (т.к. размер вставляемого списка известен)
Какая половая разница известен нам размер или нет? У двусвязного списка вставка куска другого списка всегда константна, вне зависимости от того, представляет ли этот кусок весь список или его часть. Так что здесь никакой «прибавки» нет.Но для универсальной библиотеки контейнеров это лучше
Для универсальной библиотеки контейнеров лучше, что в ней нет реализации двусвязного списка? Оригинальный подход — с таким надо идти в комитет по стандартизации :)так как многие другие операции будут эффективнее
Во-первых, как я и говорил, сделать химеру легко и поверх. Во-вторых, вполне возможно, что при таких требованиях нужна другая структура данных.
mobi
15.11.2019 14:19Наверное, никто не мешает сделать реализацию, в которой при выполнении splice внутреннее поле размера устанавливается в -1 и будет пересчитано автоматически при выполнении последующих операций, требующих знания размера.
vamireh
15.11.2019 15:36Совершенно точно этому мешает всё. И не только весьма странная попытка в беззнаковый тип данных впихнуть -1, но ещё и нарушение требований асимптотики «последующих операций». Так что не говорите, пожалуйста, ерунды.
vamireh
14.11.2019 13:38+1Во-во-во, советы двадцатилетней давности как догмат современной разработки. Я об этом и говорю.
Tsvetik
13.11.2019 12:36-3Мда, все больше разочаровываюсь в C++. Почему же, чтобы написать простой цикл надо так извращаться?
Enjection
13.11.2019 12:53+13А если бы вы читали статью внимательнее, то заметили бы:
А как же for-цикл с обходом диапазона, появившийся в C++11?
Спешу вас обрадовать: он работает! Это, по сути, синтаксический сахар, за которым скрывается почти в том же виде наша версия с итератором, где мы фиксировали указатель end в локальной переменной до начала цикла. Так что быстродействие у него то же.
PsyHaSTe
18.11.2019 03:04+1Но если прочитать еще дальше, то там предупреждение, что все может случайно сломаться если компилятору покажется что какие-то другие данные могут алиаситься.
bfDeveloper
13.11.2019 12:58+4При чём тут C++? Заметьте, код корректно работает во всех версиях, дело только в производительности. Ну а то, что для написания производительного кода приходится закапываться в асм и архитектуру процессора, никогда никого не удивляло.
ss-nopol
13.11.2019 15:43+6Возможно потому что здесь (на первый взгляд) нарушается основополагающий принцип C++ Don’t pay for what you don’t use
Мы теряем производительность из-за возможности изменять размер вектора, которая не используется. То есть платим за то, что не используем.
При этом вектор в С++ позиционируется как безопасная замена массива из С, работающая без потери производительности.bfDeveloper
13.11.2019 16:02+5Так вектор и не теряет. Немного маскирует. На чистом uint8_t* вы получите ту же самую беду с алиасингом, если не как автор в примере с указателем передадите по значению, а создадите свой struct с указателем и длинной и передадите указтель на этот самый struct. Это очень часто используется в C для всевозможных массивов и буферов и точно так же стреляет.
GCU
13.11.2019 14:39В коде написаны явные вызовы size() и оператора индексирования [] для каждого элемента массива. Для такой простой операции как увеличить на 1 — это может быть довольно накладно.
Код работает даже лучше, чем написан. В чём извращение? :)Tsvetik
13.11.2019 15:03Перечитал статью еще раз и разобрался в испытываемых чувствах. Как человек из мира С, не обратил внимание, что [] — это все-таки оператор, перегруженный в std::vector, а v.size() его метод, который не обязан быть константным.
0xd34df00d
13.11.2019 21:01+1Вообще-то
size()обязан быть константным.0xd34df00d
14.11.2019 00:49+4Ух ты, люди несогласны со стандартом (26.3.11.1/2). Ну, тем хуже для стандарта.
GCU
14.11.2019 11:09-1А почему люди должны быть с ним согласны?
Я, например, не согласен с тем что они «улучшили» сложность size() в std:list до константы за счёт других операций.
Стандарт можно только понять и простить :)
fougasse
14.11.2019 10:00- Каким образом?
- Вектора растут не монотонно.
Aldrog
14.11.2019 11:54- При итерации по индексу, как в статье, действительно поможет. Для итераторов — нет.
- Рост — это монотонное изменение размера по определению.
fougasse
14.11.2019 12:40в многопоточной среде?
Aldrog
14.11.2019 12:58Конкретно в примере из статьи да, добавление элементов в конец вектора из другого потока ничего не сломает. В чуть более сложном случае может и сломать, так что в целом предложение PeterK я тоже не совсем понимаю.
Videoman
14.11.2019 13:30Смелое утверждение. Там же сплошные гонки. Как только вектор превысит capacity, будет полная переаллокация с перемещением элементов. В какой-то момент инкремент будет по удаленному куску памяти — 100%.
Aldrog
14.11.2019 13:38Да, согласен, ошибся. Даже в этом примере инкремент не атомарный, так что проблемы будут.
Videoman
13.11.2019 18:11Не надо. Это как-раз хорошая иллюстрация на тему преждевременной оптимизации. Не нужно всегда и везде добиваться предельно возможной скорости. Только если профайлер показал в таком цикле hot spot, только в этом случае нужно «извращаться», как вы выразились. Но тогда это уже придется делать на любом языке, иной раз с гораздо большими затратами по сложности и времени.
bfDeveloper
13.11.2019 12:54+3Спасибо за перевод. У меня появился ещё один аргумент в войне за возвращение strict aliasing в проект. К сожалению сейчас по причинам зависимостей и глубокой истории включен -fno-strict-aliasing. Он вообще абсурдно популярен. С одной стороны люди не хотят разбираться с правилами и багами оптимизированного билда, но с другой иногда существенно теряют в производительности, что и показано в статье.
danfe
14.11.2019 05:08Он вообще абсурдно популярен.
Реальность, к сожалению, такова, что очень много кода ломается при строгом алиасинге разными неочевидными способами (когда-то обсуждали в этом топике).
Aldrog
13.11.2019 13:48+3Интересно. Проверил исходную версию кода на gcc 9.2 и i7-8700, результаты совсем другие:
- O1
8-bit test: 0.051112 ms
32-bit test: 0.059481 ms - O2
8-bit test: 0.008815 ms
32-bit test: 0.006372 ms - O3
8-bit test: 0.000545 ms
32-bit test: 0.00189 ms - O3 + march=native
8-bit test: 0.000387 ms
32-bit test: 0.001062 ms
bfDeveloper
13.11.2019 16:09Нет возможности запустить бенчмарк, но дизасм на gcc 9.2, да и на любом другом, такой же, как у автора статьи: godbolt.org/z/VtCGU4
- O1
KindDragon
13.11.2019 15:56Хочу заметить что с range-based for компилятор генерирует код такой же как ваш лучший вариант https://gcc.godbolt.org/z/f84s8e .
anonymous
00.00.0000 00:00
DistortNeo
13.11.2019 20:17+1Не поможет даже теоретически. Наличие const-квалификаторов не влияет на оптимизацию кода, насколько я знаю.
0xd34df00d
13.11.2019 21:03+1Смотря где. При объявлении переменной вполне может влиять, при объявлении параметра — мне трудно придумать пример, когда помогло бы. В данном случае точно не поможет, да.
fougasse
13.11.2019 23:11В С++ приняты два понятия неизменяемости — "логическая" и "физическая".
Даже ключевое слово сделали для таких фокусов.
Не очень понятно, что даст возможность вектора только расти в плане безопасности, ведь наступит реаллокация и всё.
RSATom
14.11.2019 10:12А почему в вынесении v.size() за пределы цикла мы на компилятор не полагаемся, но при этом верим что i++ это правильно?
bfDeveloper
14.11.2019 12:53Потому что про i++ компилятор имеет и прав, и возможность убрать лишние операции, превратив в ++i, а v.size() выносить за пределы цикла нет. Если я, конечно, правильно понял вашу претензию к i++
PyerK
14.11.2019 13:06+2Конкретно для POD типов компилятор так умеет. На остальных классах это не всегда возможно из-за природы постинкремента.
Некоторые программисты считают что лучше выработать у себя дефолтный стиль кода, который правильный в большем числе случаев (например по умолчанию всё конст, по умолчанию прединкремент, по умолчанию всегда RAII etc). И пост инкремент использовать только в том контексте, где он имеет смысл.
perfect_genius
21.11.2019 13:07Надо бы ещё в хабы «Ассемблер» и «Высокая производительность» — чуть не пропустил статью из-за этого.
EviLOne
21.11.2019 23:59давно для себя усвоил, если память позволяет, то нужно работать в родной размерности вычислительной системы, уменьшать смысла нет. Это я про МК
staticmain
Из древних пещерных времен к нам пришел переводчик. Потому что в оригинале автор говорит , где он не оскорбляет пользователей С, а говорит о том, что с точки зрения С++ С-подобной функции в С++ коде делать нечего.