Inline функции
Самый оптимальный с точки зрения производительности код - это сплошной набор вычислительных инструкций от начала и до конца. Это может быть и быстро, но никто так не пишет код. Любую целостную функциональность пришлось бы заново писать самостоятельно или копировать. Это все увеличивает время разработки(которое иногда важнее времени выполнения кода) и количество ошибок на единицу объема кода. Это естественно всех не устраивало.
Но в любой программе отчетливо просматривается группировка команд по смыслу. То есть определенная группа команд отвечает за выполнение какого-то комплексного действия. Это можно представить в виде графа, где вершины - эти группы, а ребра - переходы между ними. И оказалось очень удобным ввести сущность, отражающую во эту общность набора строк. Такая сущность называется функцией. И чтобы организовывать код с учетом наличия функций, нужны правила, согласно которым их будут вызывать. Так появился стек вызовов, calling conventions и так далее.
Что здесь важно знать. Чтобы выполнить функцию нужно сделать довольно много дополнительных действий. Положить значение base pointer'а на стек, через него же или через регистры передать аргументы, прыгнуть по адресу функции, сохранить возвращаемое значение функции, восстановить base pointer и прыгнуть обратно в вызывающий код. Может что-то забыл, но не суть. Суть в том, что дополнительные действия - дополнительные временные затраты на выполнение. Опять такой trade-off между перфомансом и удобством.
Для человека может быть очень удобно определить функцию сложения двух чисел. Семантически это действительно отдельная операция, которую удобно вынести в отдельную функцию и всегда ей пользоваться. Но с точки зрения машинного кода, затраты на вызов функции вносят значительный вклад в вычисление нужного значения. А вообще-то нам бы хотелось и рыбку съесть и на..., то есть перфоманс не потерять. И такой способ существует!
Называется инлайнинг. Для не очень сложных функций компилятор может просто взять и вставить код из функции в вызывающий код. Таким образом мы получаем преимущества организации кода по функциям и не просаживаем производительность. И еще дополнительно компилятор может сделать и другие оптимизации, которые невозможны были бы при вызове функции.
Для этих целей когда-то давно было придумано ключевое слово inline. Оно служило индикатором оптимизатору, что функцию, помеченную этим словом, нужно встроить. Эх, были времена, когда слово программиста имело вес...
Сейчас компилятор настолько преисполнился в своем познании, что может любую функцию сам встроить по своему хотению. А еще может просто проигнорировать вашу пометку inline и не встраивать функцию. Да и вообще, сейчас все методы, которые определены в объявлении класса неявно помечены как inline. С учетом наплевательского отношения компилятора к нашим пожеланиям, кажется, что вообще бессмысленно использовать ключевое слово inline для оптимизации кода. Хотя у inline есть и другое полезное свойство, но об этом в другой раз.
Но помимо бенефитов встраивания кода, у него есть и недостатки.
Из очевидного - увеличение размера бинаря. Код функции можно переиспользовать, а код заинлайненной функции будет располагаться в каждом ее вызове. Больше инструкций - больший размер бинаря.
Из неочевидного - встраивание функций может оказывать повышенное давление на кэш процессора. Например, если функция слишком большая, чтобы поместиться в L1, она может выполниться медленнее, чем при обычном выполнении function call. Для вызова функции CPU может заранее подгрузить ее инструкции и адрес возврата и выполнить ее быстрее. Или например, большое количество одного и того же встроенного кода может увеличить вероятность кэш-промаха и замедлить пайплайн процессора.
Опций, контролирующих встраивание, в компиляторе довольно много. Если будет желание, накидайте лайков и расскажу о них подробнее. Но самый простой способ разрешить инлайнинг - включить оптимизации O1 или даже О2.
Stay optimized. Stay cool.
#compiler #optimization #cppcore #performance #hardcore #memory
Самый оптимальный с точки зрения производительности код - это сплошной набор вычислительных инструкций от начала и до конца. Это может быть и быстро, но никто так не пишет код. Любую целостную функциональность пришлось бы заново писать самостоятельно или копировать. Это все увеличивает время разработки(которое иногда важнее времени выполнения кода) и количество ошибок на единицу объема кода. Это естественно всех не устраивало.
Но в любой программе отчетливо просматривается группировка команд по смыслу. То есть определенная группа команд отвечает за выполнение какого-то комплексного действия. Это можно представить в виде графа, где вершины - эти группы, а ребра - переходы между ними. И оказалось очень удобным ввести сущность, отражающую во эту общность набора строк. Такая сущность называется функцией. И чтобы организовывать код с учетом наличия функций, нужны правила, согласно которым их будут вызывать. Так появился стек вызовов, calling conventions и так далее.
Что здесь важно знать. Чтобы выполнить функцию нужно сделать довольно много дополнительных действий. Положить значение base pointer'а на стек, через него же или через регистры передать аргументы, прыгнуть по адресу функции, сохранить возвращаемое значение функции, восстановить base pointer и прыгнуть обратно в вызывающий код. Может что-то забыл, но не суть. Суть в том, что дополнительные действия - дополнительные временные затраты на выполнение. Опять такой trade-off между перфомансом и удобством.
Для человека может быть очень удобно определить функцию сложения двух чисел. Семантически это действительно отдельная операция, которую удобно вынести в отдельную функцию и всегда ей пользоваться. Но с точки зрения машинного кода, затраты на вызов функции вносят значительный вклад в вычисление нужного значения. А вообще-то нам бы хотелось и рыбку съесть и на..., то есть перфоманс не потерять. И такой способ существует!
Называется инлайнинг. Для не очень сложных функций компилятор может просто взять и вставить код из функции в вызывающий код. Таким образом мы получаем преимущества организации кода по функциям и не просаживаем производительность. И еще дополнительно компилятор может сделать и другие оптимизации, которые невозможны были бы при вызове функции.
Для этих целей когда-то давно было придумано ключевое слово inline. Оно служило индикатором оптимизатору, что функцию, помеченную этим словом, нужно встроить. Эх, были времена, когда слово программиста имело вес...
Сейчас компилятор настолько преисполнился в своем познании, что может любую функцию сам встроить по своему хотению. А еще может просто проигнорировать вашу пометку inline и не встраивать функцию. Да и вообще, сейчас все методы, которые определены в объявлении класса неявно помечены как inline. С учетом наплевательского отношения компилятора к нашим пожеланиям, кажется, что вообще бессмысленно использовать ключевое слово inline для оптимизации кода. Хотя у inline есть и другое полезное свойство, но об этом в другой раз.
Но помимо бенефитов встраивания кода, у него есть и недостатки.
Из очевидного - увеличение размера бинаря. Код функции можно переиспользовать, а код заинлайненной функции будет располагаться в каждом ее вызове. Больше инструкций - больший размер бинаря.
Из неочевидного - встраивание функций может оказывать повышенное давление на кэш процессора. Например, если функция слишком большая, чтобы поместиться в L1, она может выполниться медленнее, чем при обычном выполнении function call. Для вызова функции CPU может заранее подгрузить ее инструкции и адрес возврата и выполнить ее быстрее. Или например, большое количество одного и того же встроенного кода может увеличить вероятность кэш-промаха и замедлить пайплайн процессора.
Опций, контролирующих встраивание, в компиляторе довольно много. Если будет желание, накидайте лайков и расскажу о них подробнее. Но самый простой способ разрешить инлайнинг - включить оптимизации O1 или даже О2.
Stay optimized. Stay cool.
#compiler #optimization #cppcore #performance #hardcore #memory
Флаги контроля за встраиванием
Под этим постом было предложение выпустить пост с флагами компилятора, которые контролируют инлайнинг, если вы поактивничаете лайками. Вы хорошо постарались, поэтому мой черёд.
Оговорюсь, что буду вещать про флаги gcc, так как это самый популярный инструмент. Да и в шланге, думаю, будут те же самые флаги, чисто для совместмости и привычного использования. Погнали:
-fno-inline - запрещает какие-либо функции, за исключением тех, которые маркированы атрибутом alwaysinline. Этот режим стоит по дефолту, когда не подрублены оптимизации. И кстати, есть такой атрибут noinline, которым можно пометить отдельную функцию, и это запретит ее встраивать.
-finline-small-functions - разрешает встраивать функции в код их коллера, когда их тело меньше, чем тот код, который генерируется для вызова этих функций. Тогда размер всей программы будет меньше. У компилятора там есть свои эвристики, по которым он принимает решение, достаточно ли маленькая определенная функция. В этом случае компилятор может применить инлайнинг ко всем функциям, даже к тем, которые не помечены ключевым словом inline. Применяется на уровнях оптимизации -O2, -O3, -Os.
-finline-functions - разрешает рассматривать вообще все функции, как кандидатов на встраивание, даже если они не помечены как inline. Опять же компилятор у нас самостоятельный дядя и сам решает, когда и что встроить. Применяется на уровнях оптимизации -O2, -O3, -Os.
Если все вызовы определенной функции встроены и она помечена static, то для нее вообще не генерируется ассемблер.
-findirect-inlining - разрешает встаивать также непрямые вызовы функции, например через указатель на функцию. Опция имеет смысл только, когда подключена хотя бы одна из двух предыдущих опций. Применяется на уровнях оптимизации -O2, -O3, -Os.
-finline-functions-called-once - разрешает рассматривать для встраивания все статические функции, которые лишь однажды вызываются, даже если они не помечены как inline. Если инлайнинг удался, то для функции не генерируется ассемблер. Применяется почти на уровнях оптимизации -O1, -O2, -O3, -Os, но не для -Og.
-finline-limit=n - по дефолту gcc ограничивает размер функций, которые могут быть встроены. Этот флаг позволяет грубо контролировать этот предел. n тут - это размер функции, измеряемый в псевдоинструкциях(знать бы еще что это такое).
-fkeep-inline-functions - оставляет ассемблер для всех встроенных функций. Даже для статических и встроенных во все свои вызовы.
-fpartial-inlining - разрешает встраивание частей функции. Это довольно агрессивная и опасная оптимизация, потому что не совсем понятно, как именно компилятор разбивает функцию на части и решает, какие из них встаивать. Опция имеет смысл только при включенных -finline-functions или -finline-small-functions. Применяется на уровнях оптимизации -O2, -O3, -Os.
Это все основные флаги. Есть еще несколько, но они сложны в описании и понимании, поэтому не буду их упоминать. А в этом списке вроде все логично, понятно и практически применимо.
Optimize your life. Stay cool.
#compiler #optimization #performance
Под этим постом было предложение выпустить пост с флагами компилятора, которые контролируют инлайнинг, если вы поактивничаете лайками. Вы хорошо постарались, поэтому мой черёд.
Оговорюсь, что буду вещать про флаги gcc, так как это самый популярный инструмент. Да и в шланге, думаю, будут те же самые флаги, чисто для совместмости и привычного использования. Погнали:
-fno-inline - запрещает какие-либо функции, за исключением тех, которые маркированы атрибутом alwaysinline. Этот режим стоит по дефолту, когда не подрублены оптимизации. И кстати, есть такой атрибут noinline, которым можно пометить отдельную функцию, и это запретит ее встраивать.
-finline-small-functions - разрешает встраивать функции в код их коллера, когда их тело меньше, чем тот код, который генерируется для вызова этих функций. Тогда размер всей программы будет меньше. У компилятора там есть свои эвристики, по которым он принимает решение, достаточно ли маленькая определенная функция. В этом случае компилятор может применить инлайнинг ко всем функциям, даже к тем, которые не помечены ключевым словом inline. Применяется на уровнях оптимизации -O2, -O3, -Os.
-finline-functions - разрешает рассматривать вообще все функции, как кандидатов на встраивание, даже если они не помечены как inline. Опять же компилятор у нас самостоятельный дядя и сам решает, когда и что встроить. Применяется на уровнях оптимизации -O2, -O3, -Os.
Если все вызовы определенной функции встроены и она помечена static, то для нее вообще не генерируется ассемблер.
-findirect-inlining - разрешает встаивать также непрямые вызовы функции, например через указатель на функцию. Опция имеет смысл только, когда подключена хотя бы одна из двух предыдущих опций. Применяется на уровнях оптимизации -O2, -O3, -Os.
-finline-functions-called-once - разрешает рассматривать для встраивания все статические функции, которые лишь однажды вызываются, даже если они не помечены как inline. Если инлайнинг удался, то для функции не генерируется ассемблер. Применяется почти на уровнях оптимизации -O1, -O2, -O3, -Os, но не для -Og.
-finline-limit=n - по дефолту gcc ограничивает размер функций, которые могут быть встроены. Этот флаг позволяет грубо контролировать этот предел. n тут - это размер функции, измеряемый в псевдоинструкциях(знать бы еще что это такое).
-fkeep-inline-functions - оставляет ассемблер для всех встроенных функций. Даже для статических и встроенных во все свои вызовы.
-fpartial-inlining - разрешает встраивание частей функции. Это довольно агрессивная и опасная оптимизация, потому что не совсем понятно, как именно компилятор разбивает функцию на части и решает, какие из них встаивать. Опция имеет смысл только при включенных -finline-functions или -finline-small-functions. Применяется на уровнях оптимизации -O2, -O3, -Os.
Это все основные флаги. Есть еще несколько, но они сложны в описании и понимании, поэтому не буду их упоминать. А в этом списке вроде все логично, понятно и практически применимо.
Optimize your life. Stay cool.
#compiler #optimization #performance
Инициализация вектора
Под вот этим постом в комментах завелась небольшая дискуссия по поводу целесообразности использования круглых скобок для инициализации объектов. Мол универсальная инициализация предпочтительнее и от круглых скобок можно вообще отказаться. На канале уже есть пост про то, что с вектором универсальную инициализацию использовать не получится из-за того, что у вектора есть конструктор от initializer_list и из-за этого вместо того, чтобы передавать объекты из {} в конструктор, компилятор рассматривает {} и все внутри них как один аргумент - initializer_list. И появляются приколы, что хочешь создать массив на 100 элементов, заполненных нулями, а получаешь массив на 2 элемента: 100 и 0.
Однако был выдвинут интересный вопрос. Что эффективнее: создавать массив и инициализировать его в конструкторе через круглые скобки или дефолтно создать массив, а потом использовать resize и std::fill. Сегодня мы это и проверим.
Мое изначальное предположение было в том, что 3 вызова хуже одного в плане перфоманса. Прост исходя из логики, что отдельно взятый метод стандартной библиотеки очень оптимизирован. И если делать ту же самую работу, только руками, даже через другие вызовы из std, то мы как бы лишаем компилятор некоторых оптимизаций, которые могли бы быть сделаны внутри одного вызова.
Снова наклепал простенький бенчмарк. Скомпилировал это дело 11-м гцц с 20-ми плюсами и O2 оптимизациями. Результаты можно увидеть на картинке к посту.
Специально проверял несколько случаев: создание массива чисел с заданным размером и с дефолтным значением элементов, далее с кастомным значением чисел и для интереса со строками.
В целом, моя гипотеза подтвердилась. Создание массива чисел через круглые скобки быстрее на 20-30%, чем через последовательность конструктор-ресайз-филл. Но это с чиселками. Со строками последовательный вариант проигрывает уже почти в 2 раза. Хз, с чем это связано. Видимо как раз в этих самых межвызовных оптимизациях. Кто очень хорошо за асемблер шарит, наверное может подсказать причину.
Можете сами поиграться с примером в голдболде. Правда там иногда странные результаты, так что придется потыкаться в версии и опции.
Поэтому, думаю, что инициализации с круглыми скобками быть! Не надо отказываться от инструментов только из-за того, что мода на них прошла. Нужно понимать, что и где выгоднее использовать, и проверять свои предположения.
Measure your performance. Stay cool.
#compiler #optimization #cpp11
Под вот этим постом в комментах завелась небольшая дискуссия по поводу целесообразности использования круглых скобок для инициализации объектов. Мол универсальная инициализация предпочтительнее и от круглых скобок можно вообще отказаться. На канале уже есть пост про то, что с вектором универсальную инициализацию использовать не получится из-за того, что у вектора есть конструктор от initializer_list и из-за этого вместо того, чтобы передавать объекты из {} в конструктор, компилятор рассматривает {} и все внутри них как один аргумент - initializer_list. И появляются приколы, что хочешь создать массив на 100 элементов, заполненных нулями, а получаешь массив на 2 элемента: 100 и 0.
Однако был выдвинут интересный вопрос. Что эффективнее: создавать массив и инициализировать его в конструкторе через круглые скобки или дефолтно создать массив, а потом использовать resize и std::fill. Сегодня мы это и проверим.
Мое изначальное предположение было в том, что 3 вызова хуже одного в плане перфоманса. Прост исходя из логики, что отдельно взятый метод стандартной библиотеки очень оптимизирован. И если делать ту же самую работу, только руками, даже через другие вызовы из std, то мы как бы лишаем компилятор некоторых оптимизаций, которые могли бы быть сделаны внутри одного вызова.
Снова наклепал простенький бенчмарк. Скомпилировал это дело 11-м гцц с 20-ми плюсами и O2 оптимизациями. Результаты можно увидеть на картинке к посту.
Специально проверял несколько случаев: создание массива чисел с заданным размером и с дефолтным значением элементов, далее с кастомным значением чисел и для интереса со строками.
В целом, моя гипотеза подтвердилась. Создание массива чисел через круглые скобки быстрее на 20-30%, чем через последовательность конструктор-ресайз-филл. Но это с чиселками. Со строками последовательный вариант проигрывает уже почти в 2 раза. Хз, с чем это связано. Видимо как раз в этих самых межвызовных оптимизациях. Кто очень хорошо за асемблер шарит, наверное может подсказать причину.
Можете сами поиграться с примером в голдболде. Правда там иногда странные результаты, так что придется потыкаться в версии и опции.
Поэтому, думаю, что инициализации с круглыми скобками быть! Не надо отказываться от инструментов только из-за того, что мода на них прошла. Нужно понимать, что и где выгоднее использовать, и проверять свои предположения.
Measure your performance. Stay cool.
#compiler #optimization #cpp11
static inline
Мы с вами уже немного знаем про эти две вещи в отдельности. А сегодня мы разберем одну интересную вещь: что будет, если соединить эти два ключевых слова? Как изменится поведение сущностей в таком случае?
И как это обычно бывает, все разделяется на кучу вариантов использования: в хэдере или в цппшнике, для переменной или функции, для поля класса или метода. Не знаю, хватит ли тут места для них всех и нужно ли это. Но погнали.
Рассмотрим static inline свободные функции. inline говорит компилятору, что эту функцию неплохо бы встроить, и это дает ей внешнее связывание. Теперь функцию можно определять во всех единицах трансляции единожды. И итоге код для всех этих определений объединится и будет один экземпляр функции в бинарнике. А вот static говорит, что у функции теперь внутреннее связывание и в каждой единице трансляции будет своя копия функции.
Нихера не клеится. Эти ключевые слова задают практически противоположное поведение. Как же они будут сочетаться?
static победит. И в каждой единице трансляции будет своя копия функции. inline здесь будет всего лишь подсказкой к встраиванию функции.
Однако здесь есть один интересный момент. Лишь для статической функции компилятор может попробовать встроить все ее вызовы и вообще не генерировать код для нее. Потому что static - гарантия того, что за пределами юнита трансляции никто не будет пробовать вызвать эту функцию. А значит, если получится в текущем юните встроить все вызовы, то и код функции вообще генерировать не нужно. Он просто никому не понадобиться. Для функций с внешней линковкой такой трюк не провернуть. Компилятор обязан для них генерировать код, потому что линкер потом может сослаться на вызов этой функции. И придется делать call, который должен перепрыгивать в тело функции.
Для глобальных переменных применимо все то же самое, что и в предыдущем случае, за исключением возможности встраивания. inline переменные, введенные вместе с 17-м стандартом, повторяют только линковочную семантику inline функций, поэтому static inline переменная также будет иметь копии в каждой единице трансляции, куда она попала.
К тому же это все справедливо и для хэдеров, и для цппшников.
Теперь про методы класса. Для них static не имеет того же значения, что и для предыдущих случаев. Статические методы - это по факту обычные свободные функции с внешним связыванием, которые имеют доступ ко всем полям класса. Поэтому в этом случае добавление inline просто будет явным намеком компилятору, что метод можно встроить. Хотя смысла от этого намека немного, ибо при этом всем, все статические методы, определенные внутри описания класса, неявно помечены inline, чтобы иметь возможность определять такие методы сразу в хэдерах и обходить odr.
И для полей класса. Мы кстати разбирали уже этот случай в этом посте. Пометив статическое поле inline, мы получаем возможность определять это поле внутри описания класса и не беспокоиться по поводу линкера и odr. Собственно, как и в случае с методами.
Даже компактно справился. Надо конечно запоминать все эти тонкости линковки, чтобы связывать такие довольно сложные конструкции вместе. Надеюсь, что эти посты помогают что-то структурировать в голове.
Combine things together. Stay cool.
#cpp17 #compiler #optimization
Мы с вами уже немного знаем про эти две вещи в отдельности. А сегодня мы разберем одну интересную вещь: что будет, если соединить эти два ключевых слова? Как изменится поведение сущностей в таком случае?
И как это обычно бывает, все разделяется на кучу вариантов использования: в хэдере или в цппшнике, для переменной или функции, для поля класса или метода. Не знаю, хватит ли тут места для них всех и нужно ли это. Но погнали.
Рассмотрим static inline свободные функции. inline говорит компилятору, что эту функцию неплохо бы встроить, и это дает ей внешнее связывание. Теперь функцию можно определять во всех единицах трансляции единожды. И итоге код для всех этих определений объединится и будет один экземпляр функции в бинарнике. А вот static говорит, что у функции теперь внутреннее связывание и в каждой единице трансляции будет своя копия функции.
Нихера не клеится. Эти ключевые слова задают практически противоположное поведение. Как же они будут сочетаться?
static победит. И в каждой единице трансляции будет своя копия функции. inline здесь будет всего лишь подсказкой к встраиванию функции.
Однако здесь есть один интересный момент. Лишь для статической функции компилятор может попробовать встроить все ее вызовы и вообще не генерировать код для нее. Потому что static - гарантия того, что за пределами юнита трансляции никто не будет пробовать вызвать эту функцию. А значит, если получится в текущем юните встроить все вызовы, то и код функции вообще генерировать не нужно. Он просто никому не понадобиться. Для функций с внешней линковкой такой трюк не провернуть. Компилятор обязан для них генерировать код, потому что линкер потом может сослаться на вызов этой функции. И придется делать call, который должен перепрыгивать в тело функции.
Для глобальных переменных применимо все то же самое, что и в предыдущем случае, за исключением возможности встраивания. inline переменные, введенные вместе с 17-м стандартом, повторяют только линковочную семантику inline функций, поэтому static inline переменная также будет иметь копии в каждой единице трансляции, куда она попала.
К тому же это все справедливо и для хэдеров, и для цппшников.
Теперь про методы класса. Для них static не имеет того же значения, что и для предыдущих случаев. Статические методы - это по факту обычные свободные функции с внешним связыванием, которые имеют доступ ко всем полям класса. Поэтому в этом случае добавление inline просто будет явным намеком компилятору, что метод можно встроить. Хотя смысла от этого намека немного, ибо при этом всем, все статические методы, определенные внутри описания класса, неявно помечены inline, чтобы иметь возможность определять такие методы сразу в хэдерах и обходить odr.
И для полей класса. Мы кстати разбирали уже этот случай в этом посте. Пометив статическое поле inline, мы получаем возможность определять это поле внутри описания класса и не беспокоиться по поводу линкера и odr. Собственно, как и в случае с методами.
Даже компактно справился. Надо конечно запоминать все эти тонкости линковки, чтобы связывать такие довольно сложные конструкции вместе. Надеюсь, что эти посты помогают что-то структурировать в голове.
Combine things together. Stay cool.
#cpp17 #compiler #optimization
Снова сравниваем решения задачи с поездами
Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @tigrisVD сделала несколько улучшений алгоритма спидометра. Вот ее сообщение с пояснениями и кодом.
Первое - базовое улучшение. Вместо того, чтобы возвращаться назад на каждом шаге(что очень расточительно), мы возвращаемся назад, только, если встретили единичку и поменяли ее на ноль. Только в этом случае мы могли поменять самую первую лампочку.
Это уже улучшение уполовинило количество шагов. И сравняло его с маятником.
Но она пошла дальше и придумала следующую оптимизацию: пусть мы встретили единичку, когда шли вправо. Тогда разрешим себе поменять ее на нолик и идти дальше на еще столько же шагов, сколько мы сделали до этой единички. Но если мы встретим еще одну единичку, то возвращаемся обратно и чекаем нулевую ячейку. Таким образом мы сэкономим себе проход до первой ячейки и обратно. А если мы за этот удвоенный период не нашли ее одну единичку, то мы просто обязаны обратно вернуться, чтобы проверить была ли первая новая единичка на нашем пути - тем самым началом.
Там есть некоторые проблемы с тем, что оптимизированные алгоритмы спидометра зависят от входных данных. И в худшем случае, когда в поезде включены все лампочки, последний оптимизированный алгоритм работает лишь в 2 раза лучше базового спидометра. В лучшем случае, когда все лампочки выключены - сложность алгоритмов линейно зависит от количества вагонов, а не квадратично, как у базового спидометра. Базовое улучшение - нужно пройти всего х2 от количества вагонов. А оптимизированный вариант- х4(я там одну ошибочку нашел в коде при подсчете пройденных вагонов, поэтому не в 3, а в 4). Но в рандомных случаях оптимизированный вариант примерно в 2 раза быстрее базового улучшенного и в 4 раза быстрее оригинального спидометра.
Позапускать ее код и посмотреть на цифры можно тут
Спасибо вам, @tigrisVD, за такие интересные решения!
Но ваши улучшения натолкнули и меня на размышления и улучшения, о которых я расскажу завтра.
Impove yourself. Stay cool.
#fun #optimization
Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @tigrisVD сделала несколько улучшений алгоритма спидометра. Вот ее сообщение с пояснениями и кодом.
Первое - базовое улучшение. Вместо того, чтобы возвращаться назад на каждом шаге(что очень расточительно), мы возвращаемся назад, только, если встретили единичку и поменяли ее на ноль. Только в этом случае мы могли поменять самую первую лампочку.
Это уже улучшение уполовинило количество шагов. И сравняло его с маятником.
Но она пошла дальше и придумала следующую оптимизацию: пусть мы встретили единичку, когда шли вправо. Тогда разрешим себе поменять ее на нолик и идти дальше на еще столько же шагов, сколько мы сделали до этой единички. Но если мы встретим еще одну единичку, то возвращаемся обратно и чекаем нулевую ячейку. Таким образом мы сэкономим себе проход до первой ячейки и обратно. А если мы за этот удвоенный период не нашли ее одну единичку, то мы просто обязаны обратно вернуться, чтобы проверить была ли первая новая единичка на нашем пути - тем самым началом.
Там есть некоторые проблемы с тем, что оптимизированные алгоритмы спидометра зависят от входных данных. И в худшем случае, когда в поезде включены все лампочки, последний оптимизированный алгоритм работает лишь в 2 раза лучше базового спидометра. В лучшем случае, когда все лампочки выключены - сложность алгоритмов линейно зависит от количества вагонов, а не квадратично, как у базового спидометра. Базовое улучшение - нужно пройти всего х2 от количества вагонов. А оптимизированный вариант- х4(я там одну ошибочку нашел в коде при подсчете пройденных вагонов, поэтому не в 3, а в 4). Но в рандомных случаях оптимизированный вариант примерно в 2 раза быстрее базового улучшенного и в 4 раза быстрее оригинального спидометра.
Позапускать ее код и посмотреть на цифры можно тут
Спасибо вам, @tigrisVD, за такие интересные решения!
Но ваши улучшения натолкнули и меня на размышления и улучшения, о которых я расскажу завтра.
Impove yourself. Stay cool.
#fun #optimization
Telegram
Грокаем C++
Cамая популярная задачка с собеседований
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно…
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно…
Линейное решение задачи с поездами
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).
Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.
В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.
В первом случае мы просто пройдем лишний круг и вернемся обратно. Таким образом пройдя 2 лишних круга.
Во втором случае мы идем обратно и проверяем, была ли последняя выключенная нами лампочка той самой начальной. Если не была, то снова начинаем идти вправо, пока не наткнемся на зажженную лампочку.
Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.
Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.
Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)
Вроде бы звучит разумно и тесты все проходятся прекрасно. И сложность на первый взгляд линейная во всех случаях, что не может не радовать.
Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.
Критика и замечания приветствуются.
Improve yourself. Stay cool.
#fun #optimization
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).
Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.
В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.
В первом случае мы просто пройдем лишний круг и вернемся обратно. Таким образом пройдя 2 лишних круга.
Во втором случае мы идем обратно и проверяем, была ли последняя выключенная нами лампочка той самой начальной. Если не была, то снова начинаем идти вправо, пока не наткнемся на зажженную лампочку.
Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.
Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.
Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)
Вроде бы звучит разумно и тесты все проходятся прекрасно. И сложность на первый взгляд линейная во всех случаях, что не может не радовать.
Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.
Критика и замечания приветствуются.
Improve yourself. Stay cool.
#fun #optimization
static функции
В этом посте были краткие выжимки из того, как ключевое слово static влияет на сущности. Сегодня будем разбирать функции.
Для начала надо понимать базовые настройки функции, чтобы отталкиваться от этого в контексте static.
Функция - блок кода в .text section, то есть просто в области, где находится код. Этому куску кода соответствует определенная метка - замангленное имя функции(видимо уже пора делать пост про манглинг, а то много упоминаний без объяснений). Когда функцию хотят вызвать, то это делается через инструкцию call, которая принимает метку функции. Этой метке после линковки будет соответствовать конкретный адрес, которому и будет передано исполнение кода во время выполнения программы.
Mangled name функции формируется только на основе ее сигнатуры. Поэтому любой код, который знает только лишь(!) сигнатуру функции, то есть ее объявление, знает трушное название функции(ту самую метку). Вот теперь интересности.
По дефолту функции имеют внешнее связывание.
Для текущей единицы трансляции все тривиально. Есть метка, мы можем просто перейти на нее.
Но внешнее связывание значит, что и другие единицы трансляции могут видеть эту функцию, не зная ее определение! Не только видеть, но и вызвать! Как? Имея правильное объявление функции, текущая единица трансляции получает доступ к замангленному имени функции. А в коде появится такая строчка: call label. Прикол в том, что до этапа линковки мы можем пытаться в коде вызывать вообще любые функции и нам это будет сходить с рук. А вот уже работа линкера заключается в том, чтобы сопоставить метку из вызова с адресом реальной функции. И если линкер найдет код для этой метки в другой единице трансляции, то он просто подставит адрес, соответствующий метке, в call и все будет чики-пуки.
Ну и для того, чтобы линкер в принципе смог определить, что текущую метку могут видеть все остальные единицы трансляции, ее надо пометить как .globl label. Логично предположить, что так обозначаются глобальные для всей программы сущности, коей и является базовая функция.
Я описываю все сильно верхнеуровнево(насколько это возможно, обсуждая ассемблер ахха). Но вроде должно быть понятно.
Теперь вернемся к нашим static баранам. Что тут на самом деле меняется. Сильно верхнеуровнего - меняется тип связывания с внешнего на внутреннее. Это значит, что другие единицы трансляции просто перестают видеть эту функцию. Звучит прикольно, но как конкретно это изменение достигается?
На самом деле всего двумя деталями.
1) Пометка .globl label больше не генерируется.
2) Появляется заглавная L перед именем функции(которое в с++ коде было) в ее замангленном варианте.
Что это дает. Даже если мы знаем сигнатуру функции и объявили ее в другой единице трансляции, то на этапе линковки компоновщик посмотрит на реальное определение функции, не увидит пометку о глобальности символа, распарсит замангленное имя и увидит эту букву L и поймет, что это локальная функция для этой единицы трансляции. И не будет резолвить этот символ. Если линкер не найдет подходящего глобального определения в остальных юнитах трансляции, то произойдет ошибка линковки - undefined reference.
И на самом деле, локальная видимость функции открывает дорогу к некоторым оптимизациям. Например, компилятор может решить, что функция подходит для inline expantion и встроить все ее вызовы. Но раз в текущем юните код функции не нужен(его полностью встроили везде, где требуется), а в других его никто не должен видеть, то компилятор просто удалит метку этой функции и ее сгенерированный код. Это позволяет уменьшить размер бинаря. Мы конечно его увеличиваем за счет встраивания кода функции. Но лучше так, чем оставлять бесполезный код в бинарнике.
Hide your secrets. Stay cool.
#compiler #cppcore #optimization
В этом посте были краткие выжимки из того, как ключевое слово static влияет на сущности. Сегодня будем разбирать функции.
Для начала надо понимать базовые настройки функции, чтобы отталкиваться от этого в контексте static.
Функция - блок кода в .text section, то есть просто в области, где находится код. Этому куску кода соответствует определенная метка - замангленное имя функции(видимо уже пора делать пост про манглинг, а то много упоминаний без объяснений). Когда функцию хотят вызвать, то это делается через инструкцию call, которая принимает метку функции. Этой метке после линковки будет соответствовать конкретный адрес, которому и будет передано исполнение кода во время выполнения программы.
Mangled name функции формируется только на основе ее сигнатуры. Поэтому любой код, который знает только лишь(!) сигнатуру функции, то есть ее объявление, знает трушное название функции(ту самую метку). Вот теперь интересности.
По дефолту функции имеют внешнее связывание.
Для текущей единицы трансляции все тривиально. Есть метка, мы можем просто перейти на нее.
Но внешнее связывание значит, что и другие единицы трансляции могут видеть эту функцию, не зная ее определение! Не только видеть, но и вызвать! Как? Имея правильное объявление функции, текущая единица трансляции получает доступ к замангленному имени функции. А в коде появится такая строчка: call label. Прикол в том, что до этапа линковки мы можем пытаться в коде вызывать вообще любые функции и нам это будет сходить с рук. А вот уже работа линкера заключается в том, чтобы сопоставить метку из вызова с адресом реальной функции. И если линкер найдет код для этой метки в другой единице трансляции, то он просто подставит адрес, соответствующий метке, в call и все будет чики-пуки.
Ну и для того, чтобы линкер в принципе смог определить, что текущую метку могут видеть все остальные единицы трансляции, ее надо пометить как .globl label. Логично предположить, что так обозначаются глобальные для всей программы сущности, коей и является базовая функция.
Я описываю все сильно верхнеуровнево(насколько это возможно, обсуждая ассемблер ахха). Но вроде должно быть понятно.
Теперь вернемся к нашим static баранам. Что тут на самом деле меняется. Сильно верхнеуровнего - меняется тип связывания с внешнего на внутреннее. Это значит, что другие единицы трансляции просто перестают видеть эту функцию. Звучит прикольно, но как конкретно это изменение достигается?
На самом деле всего двумя деталями.
1) Пометка .globl label больше не генерируется.
2) Появляется заглавная L перед именем функции(которое в с++ коде было) в ее замангленном варианте.
Что это дает. Даже если мы знаем сигнатуру функции и объявили ее в другой единице трансляции, то на этапе линковки компоновщик посмотрит на реальное определение функции, не увидит пометку о глобальности символа, распарсит замангленное имя и увидит эту букву L и поймет, что это локальная функция для этой единицы трансляции. И не будет резолвить этот символ. Если линкер не найдет подходящего глобального определения в остальных юнитах трансляции, то произойдет ошибка линковки - undefined reference.
И на самом деле, локальная видимость функции открывает дорогу к некоторым оптимизациям. Например, компилятор может решить, что функция подходит для inline expantion и встроить все ее вызовы. Но раз в текущем юните код функции не нужен(его полностью встроили везде, где требуется), а в других его никто не должен видеть, то компилятор просто удалит метку этой функции и ее сгенерированный код. Это позволяет уменьшить размер бинаря. Мы конечно его увеличиваем за счет встраивания кода функции. Но лучше так, чем оставлять бесполезный код в бинарнике.
Hide your secrets. Stay cool.
#compiler #cppcore #optimization
Empty base optimization
В этом посте мы рассказали, о том, сколько весит объект пустого класса. Настоятельно рекомендую вернуться к этому посту, чтобы быть в контексте.
Теперь возникает вопрос: что будет, если мы отнаследуемся от пустого класса? Каким образом будет учитываться этот один байт в наследнике и где он будет расположен?
Вообще говоря, ненулевой размер объекта пустого класса нужен просто для нормальной его адресации. Никакой полезной нагрузки он не несет и нужен, чтобы "просто работало". Однако, когда мы наследуется от такого класса, и, например, размещаем в наследнике какие-то поля, то наследник уже не нуждается в фейковом байте, чтобы нормально работать. У него это и так получится прекрасно. Получается, что этот 1 байт будет, как жабры на теле млекопитающего: предкам были нужны, а сейчас вообще ни к селу, ни к пгт.
Поэтому есть такое понятие, как empty base class optimization. Если мы наследуемся от пустого класса, то размер класса наследника будет ровно таким же, как как будто бы он ни от чего не наследовался.
Пример:
Вывод консоли:
Вроде бы очень логичная штука и даже почти интуитивная штука, но немногие знают в ее в профиль и анфас, поэтому сегодня исправили этот момент)
Optimize your life. Stay cool.
#cppcore #optimization
В этом посте мы рассказали, о том, сколько весит объект пустого класса. Настоятельно рекомендую вернуться к этому посту, чтобы быть в контексте.
Теперь возникает вопрос: что будет, если мы отнаследуемся от пустого класса? Каким образом будет учитываться этот один байт в наследнике и где он будет расположен?
Вообще говоря, ненулевой размер объекта пустого класса нужен просто для нормальной его адресации. Никакой полезной нагрузки он не несет и нужен, чтобы "просто работало". Однако, когда мы наследуется от такого класса, и, например, размещаем в наследнике какие-то поля, то наследник уже не нуждается в фейковом байте, чтобы нормально работать. У него это и так получится прекрасно. Получается, что этот 1 байт будет, как жабры на теле млекопитающего: предкам были нужны, а сейчас вообще ни к селу, ни к пгт.
Поэтому есть такое понятие, как empty base class optimization. Если мы наследуемся от пустого класса, то размер класса наследника будет ровно таким же, как как будто бы он ни от чего не наследовался.
Пример:
struct EmptyClass {
void MethodMeantJustNotToLeaveClassDeadInside() {}
};
struct Derived : public EmptyClass {
int a;
char b;
double c;
};
struct SizeReference {
int a;
char b;
double c;
};
int main() {
EmptyClass a;
Derived b;
SizeReference c;
std::cout << "EmptyClass object size: " << sizeof(a) << std::endl;
std::cout << "Derived object size: " << sizeof(b) << std::endl;
std::cout << "SizeReference object size: " << sizeof(c) << std::endl;
}
Вывод консоли:
EmptyClass object size: 1
Derived object size: 16
SizeReference object size: 16
Вроде бы очень логичная штука и даже почти интуитивная штука, но немногие знают в ее в профиль и анфас, поэтому сегодня исправили этот момент)
Optimize your life. Stay cool.
#cppcore #optimization
Странный размер std::unordered_map
#опытным
Стандартная ситуация. Создаем контейнер, резервируем подходящий размер для ожидаемого количества элементов в коллекции и запихиваем элементы. Все просто. Но это с каким-нибудь вектором все просто. А хэш-мапа - дело нетривиальное. Смотрим на код:
Все, как обычно. А теперь вывод:
WTF? Я же сказал выделить в мапе 6 бакетов, а не 7. Какой непослушный компилятор!
Вообще, поведение странное, но может там просто всегда +1 по какой-то причине?
Поменяем map_size на 9 и посмотрим вывод:
Again. WTF? Уже на 2 разница. Нужна новая гипотеза... Попробуем третье число. Возьмем 13.
А тут работает! Но это не прибавляет понимания проблемы... В чем же дело?
Из цппреференса про метод reserve:
То есть стандарт разрешает реализациям выделять больше элементов для мапы, чем мы запросили.
Легитимацию безобразия мы получили, но хотелось бы внятное объяснение причины предоставления такой возможности.
Реализации обычно выбирают bucket_count исходя из соображений быстродействия(как обычно). Тут они выбирают из двух опций:
1️⃣ Выбирают в качестве bucket_count степень двойки, то есть округляют до степени двойки в большую сторону. Это помогает эффективно маппить результат хэш функции на размер самой хэш-таблицы. Можно просто сделать битовое И и отбросить все биты, старше нашей степени. Что делается на один цикл цпу.
Но этот способ имеет негативный эффект в виде того же отбрасывания битов. То есть эти страшие биты никак не влияют на маппинг хэша на бакеты, то уменьшает равномерность распределения.
Таким способом пользуется Visual C++.
2️⃣ Поддерживают bucket_count простым числом.
Это дает крутой эффект того, что старшие биты также влияют на распределение объектов по бакетам. В этом случае даже плохие хэш-функции имеют более равномерное размещение бакетов.
Однако наивная реализация такого подхода заставляет каждый раз делить на рантаймовое значение bucket_count, что может занимать до 100 раз больше циклов.
Более быстрой альтернативой может быть использование захардкоженой таблицы простых чисел. Индекс в ней выбирается на основе запрашиваемого значения bucket_count. Таким образом компилятор может заоптимизировать деление по модулю через битовые операции, сложения, вычитания и умножения. Можете посмотреть на эти оптимизации более подробно на этом примере в годболт.
Этой реализацией пользуется GCC и Clang.
Вот такие страсти происходят у нас под носом под капотом неупорядоченной мапы.
Optimize everything. Stay cool.
#STL #optimization #compiler
#опытным
Стандартная ситуация. Создаем контейнер, резервируем подходящий размер для ожидаемого количества элементов в коллекции и запихиваем элементы. Все просто. Но это с каким-нибудь вектором все просто. А хэш-мапа - дело нетривиальное. Смотрим на код:
constexpr size_t map_size = 6;
std::unordered_map<int, int> mymap;
mymap.reserve(map_size);
for (int i = 0; i < map_size; i++) {
mymap[i] = i;
}
std::cout << "mymap has " << mymap.bucket_count() << " buckets\n";
Все, как обычно. А теперь вывод:
mymap has 7 buckets
WTF? Я же сказал выделить в мапе 6 бакетов, а не 7. Какой непослушный компилятор!
Вообще, поведение странное, но может там просто всегда +1 по какой-то причине?
Поменяем map_size на 9 и посмотрим вывод:
mymap has 11 buckets
Again. WTF? Уже на 2 разница. Нужна новая гипотеза... Попробуем третье число. Возьмем 13.
mymap has 13 buckets
А тут работает! Но это не прибавляет понимания проблемы... В чем же дело?
Из цппреференса про метод reserve:
Request a capacity change
Sets the number of buckets in the container (bucket_count) to the most appropriate to contain at least n elements.
То есть стандарт разрешает реализациям выделять больше элементов для мапы, чем мы запросили.
Легитимацию безобразия мы получили, но хотелось бы внятное объяснение причины предоставления такой возможности.
Реализации обычно выбирают bucket_count исходя из соображений быстродействия(как обычно). Тут они выбирают из двух опций:
1️⃣ Выбирают в качестве bucket_count степень двойки, то есть округляют до степени двойки в большую сторону. Это помогает эффективно маппить результат хэш функции на размер самой хэш-таблицы. Можно просто сделать битовое И и отбросить все биты, старше нашей степени. Что делается на один цикл цпу.
Но этот способ имеет негативный эффект в виде того же отбрасывания битов. То есть эти страшие биты никак не влияют на маппинг хэша на бакеты, то уменьшает равномерность распределения.
Таким способом пользуется Visual C++.
2️⃣ Поддерживают bucket_count простым числом.
Это дает крутой эффект того, что старшие биты также влияют на распределение объектов по бакетам. В этом случае даже плохие хэш-функции имеют более равномерное размещение бакетов.
Однако наивная реализация такого подхода заставляет каждый раз делить на рантаймовое значение bucket_count, что может занимать до 100 раз больше циклов.
Более быстрой альтернативой может быть использование захардкоженой таблицы простых чисел. Индекс в ней выбирается на основе запрашиваемого значения bucket_count. Таким образом компилятор может заоптимизировать деление по модулю через битовые операции, сложения, вычитания и умножения. Можете посмотреть на эти оптимизации более подробно на этом примере в годболт.
Этой реализацией пользуется GCC и Clang.
Вот такие страсти происходят у нас под носом под капотом неупорядоченной мапы.
Optimize everything. Stay cool.
#STL #optimization #compiler
