Приветственный пост
Рады приветствовать всех на нашем канале!
Вы устали от скучного, монотонного, обезличенного контента по плюсам?
Тогда мы идем к вам!
Здесь не будет бесполезных 30 IQ постов, сгенеренных ChatGPT, накрученных подписчиков и активности.
Канал ведут два сеньора, Денис и Владимир, которые искренне хотят делится своими знаниями по С++ и создать самое уютное коммьюнити позитивных прогеров в телеге!
(ну вы поняли, да? с++, плюс плюс, плюс типа
позитивный?.. ай ладно)
Жмакай и попадешь в наш чат. Там обсуждения не привязаны к постам, можете общаться на любые темы.
ГАЙДЫ:
Мини-гайд по собеседования
Гайд по категория выражения и мув-семантике
Гайд по inline
Дальше пойдет список хэштегов, которыми вы можете пользоваться для более удобной навигации по каналу и для быстрого поиска группы постов по интересующей теме:
#algorithms
#datastructures
#cppcore
#stl
#goodoldc
#cpp11
#cpp14
#cpp17
#cpp20
#commercial
#net
#database
#hardcore
#memory
#goodpractice
#howitworks
#NONSTANDARD
#interview
#digest
#OS
#tools
#optimization
#performance
#fun
#compiler
#multitasking
#design
#exception
#guide
#задачки
#base
#quiz
#concurrency
Рады приветствовать всех на нашем канале!
Вы устали от скучного, монотонного, обезличенного контента по плюсам?
Тогда мы идем к вам!
Здесь не будет бесполезных 30 IQ постов, сгенеренных ChatGPT, накрученных подписчиков и активности.
Канал ведут два сеньора, Денис и Владимир, которые искренне хотят делится своими знаниями по С++ и создать самое уютное коммьюнити позитивных прогеров в телеге!
(ну вы поняли, да? с++, плюс плюс, плюс типа
позитивный?.. ай ладно)
Жмакай и попадешь в наш чат. Там обсуждения не привязаны к постам, можете общаться на любые темы.
ГАЙДЫ:
Мини-гайд по собеседования
Гайд по категория выражения и мув-семантике
Гайд по inline
Дальше пойдет список хэштегов, которыми вы можете пользоваться для более удобной навигации по каналу и для быстрого поиска группы постов по интересующей теме:
#algorithms
#datastructures
#cppcore
#stl
#goodoldc
#cpp11
#cpp14
#cpp17
#cpp20
#commercial
#net
#database
#hardcore
#memory
#goodpractice
#howitworks
#NONSTANDARD
#interview
#digest
#OS
#tools
#optimization
#performance
#fun
#compiler
#multitasking
#design
#exception
#guide
#задачки
#base
#quiz
#concurrency
Telegram
Грокаем C++
Мини-гайд по собеседованиям
Доброго дня, дорогие подписчики. Сегодня у нас радостный день - на канале выходит первый гайд. Не так давно мы в комментах с ребятами осуждали этот вопрос, что нужно сделать чеклист по вопросам с собесов. Собственно, сделал. Скачивайте…
Доброго дня, дорогие подписчики. Сегодня у нас радостный день - на канале выходит первый гайд. Не так давно мы в комментах с ребятами осуждали этот вопрос, что нужно сделать чеклист по вопросам с собесов. Собственно, сделал. Скачивайте…
Small string optimization
Люди, которые разрабатывают компилляторы - гении. Никто не знает тех маленьких индусов, которые рвут свои маленькие попки, чтобы из твоего зачастую дурнопахнущего кода на С++ сделать конфетку. Эта фича не является геймченджером или сильным бустром перфоманса. Это просто крутая оптимизация, которая исходит из понимания работы с памятью на низком уровне и юз-кейсов класса строки.
Дело в том, что в основе плюсовой строки лежит обычный сишный массив. Точнее не обычный, а выделенный в куче. Так вот, когда вы пишите std::string var = "Like this post", по идее на куче должен выделяться блок памяти, равный размеру этой строки. Но. Зачастую пользователь класса std::string хочет присвоить переменной какую-нибудь короткую строку, которую он менять не собирается. Зачем тогда тратить драгоценные клоки проца и делать дорогостоящий вызов, когда можно поместить эту короткую строку в маленький внутренний буффер самого объекта строки и жить счастливо? Не дергать аллокатор, не фрагментировать память. Хорошо звучит? Вот и индусы так же подумали и запилили small string optimization.
Замечу, что этой фичи нет в стандарте. Это просто хорошая практика реализации стандартной библиотеки. Длина буферизируемой строки может отличатся от одной реализации к другой, а также может варьирываться с помощью опций компиллятора. Для гцц по дефолту она равна 15 байт.
Давайте все быть такими же умными, как индусы.
Stay cool.
#optimization #datastructures
Люди, которые разрабатывают компилляторы - гении. Никто не знает тех маленьких индусов, которые рвут свои маленькие попки, чтобы из твоего зачастую дурнопахнущего кода на С++ сделать конфетку. Эта фича не является геймченджером или сильным бустром перфоманса. Это просто крутая оптимизация, которая исходит из понимания работы с памятью на низком уровне и юз-кейсов класса строки.
Дело в том, что в основе плюсовой строки лежит обычный сишный массив. Точнее не обычный, а выделенный в куче. Так вот, когда вы пишите std::string var = "Like this post", по идее на куче должен выделяться блок памяти, равный размеру этой строки. Но. Зачастую пользователь класса std::string хочет присвоить переменной какую-нибудь короткую строку, которую он менять не собирается. Зачем тогда тратить драгоценные клоки проца и делать дорогостоящий вызов, когда можно поместить эту короткую строку в маленький внутренний буффер самого объекта строки и жить счастливо? Не дергать аллокатор, не фрагментировать память. Хорошо звучит? Вот и индусы так же подумали и запилили small string optimization.
Замечу, что этой фичи нет в стандарте. Это просто хорошая практика реализации стандартной библиотеки. Длина буферизируемой строки может отличатся от одной реализации к другой, а также может варьирываться с помощью опций компиллятора. Для гцц по дефолту она равна 15 байт.
Давайте все быть такими же умными, как индусы.
Stay cool.
#optimization #datastructures
std::make_shared
Недавно тут и тут мы поговорили про плюсы и минусы использования std::make_unique. Настала очередь его братишки std::make_shared.
Базового все pros and cons с предыдущих постов справедливы и для сегодняшнего разбора. Поэтому не будем на этом долго останавливаться.
Но шаренный указатель немного сложнее внутри устроен, чем уникальный. От этого идут и уникальные преимущества и недостатки. А связаны они вот с чем. Посмотрите на эту строчку:
std::shared_ptr<T>(new T(...));
Сколько раз память аллоцируется в результате выполнения этой строчки?
Многие скажут 1. А люди, знающие внутреннее устройство шареного уккзателя, скажут 2. И будут правы.
Первая аллокация, очевидно, происходит в new. А вот где вторая?
На выделении памяти для, так называемого, control block'а. Это внутренняя структура, которая хранит счетчики ссылок и еще пару приколюх. Она нужна для того, чтобы вести учет существующих объектов указателя, указывающих на данный объект. Естественно, эта структура должна быть общей для всех таких объектов. Поэтому в каждом объекте указателя хранится сырой указатель на этот самый контрол блок. То есть базово в классе std::shared_ptr 2 поля: указатель на объект и указатель на контрол блок. Ну и приняв указатель на объект, конструктор указателя дополнитель выделяет память для этого блока.
Чем в этом контексте отличается поведение std::make_shared?
Она вызывает всего одну аллокацию. Как? выделяет просто один блок памяти, который может содержать сразу и создаваемый объект, и control block, и кладет эти данные вместе. Это уменьшает статический размер программы, потому что код содержит всего 1 вызов аллокатора. И увеличивает скорость выполнения кода, потому что аллокация - довольно дорогостоящий вызов.
Перформанс - это уже серьезный аргумент отдать свое предпочтение в пользу make функции.
Однако эта фича ведет к одной проблеме. Для кого-то она совсем не проблемная, но об этом надо знать.
Дело в том, что может создаться такая ситуация, когда ни одного shared_pointer уже не существует, а память, выделенная для объекта и блока, все еще не отдана системе. Как такое может быть? Слабые ссылки.
Контрол блок помимо счетчика сильных ссылок(собственно сами shared_ptr'ы) хранит еще и счетчик слабых ссылок - для weak_ptr'ов. А деструктор control block'а и деаллокация памяти происходят только после того, как оба счетчика зануляться. Поэтому, если у вас есть хоть один висящий std::weak_ptr, то у вашего объекта хоть и будет вызван деструктор, но память так и не будет возвращена системе.
При создании больших объектов и при обильном использовании слабых ссылок это действительно может создавать проблему.
А если у вас не этот случай - смело используйте std::make_shared()
Stay efficient. Stay cool.
#cpp17 #cpp17 #STL #optimization #memory
Недавно тут и тут мы поговорили про плюсы и минусы использования std::make_unique. Настала очередь его братишки std::make_shared.
Базового все pros and cons с предыдущих постов справедливы и для сегодняшнего разбора. Поэтому не будем на этом долго останавливаться.
Но шаренный указатель немного сложнее внутри устроен, чем уникальный. От этого идут и уникальные преимущества и недостатки. А связаны они вот с чем. Посмотрите на эту строчку:
std::shared_ptr<T>(new T(...));
Сколько раз память аллоцируется в результате выполнения этой строчки?
Многие скажут 1. А люди, знающие внутреннее устройство шареного уккзателя, скажут 2. И будут правы.
Первая аллокация, очевидно, происходит в new. А вот где вторая?
На выделении памяти для, так называемого, control block'а. Это внутренняя структура, которая хранит счетчики ссылок и еще пару приколюх. Она нужна для того, чтобы вести учет существующих объектов указателя, указывающих на данный объект. Естественно, эта структура должна быть общей для всех таких объектов. Поэтому в каждом объекте указателя хранится сырой указатель на этот самый контрол блок. То есть базово в классе std::shared_ptr 2 поля: указатель на объект и указатель на контрол блок. Ну и приняв указатель на объект, конструктор указателя дополнитель выделяет память для этого блока.
Чем в этом контексте отличается поведение std::make_shared?
Она вызывает всего одну аллокацию. Как? выделяет просто один блок памяти, который может содержать сразу и создаваемый объект, и control block, и кладет эти данные вместе. Это уменьшает статический размер программы, потому что код содержит всего 1 вызов аллокатора. И увеличивает скорость выполнения кода, потому что аллокация - довольно дорогостоящий вызов.
Перформанс - это уже серьезный аргумент отдать свое предпочтение в пользу make функции.
Однако эта фича ведет к одной проблеме. Для кого-то она совсем не проблемная, но об этом надо знать.
Дело в том, что может создаться такая ситуация, когда ни одного shared_pointer уже не существует, а память, выделенная для объекта и блока, все еще не отдана системе. Как такое может быть? Слабые ссылки.
Контрол блок помимо счетчика сильных ссылок(собственно сами shared_ptr'ы) хранит еще и счетчик слабых ссылок - для weak_ptr'ов. А деструктор control block'а и деаллокация памяти происходят только после того, как оба счетчика зануляться. Поэтому, если у вас есть хоть один висящий std::weak_ptr, то у вашего объекта хоть и будет вызван деструктор, но память так и не будет возвращена системе.
При создании больших объектов и при обильном использовании слабых ссылок это действительно может создавать проблему.
А если у вас не этот случай - смело используйте std::make_shared()
Stay efficient. Stay cool.
#cpp17 #cpp17 #STL #optimization #memory
Когда нужно явно вызывать деструктор?
В прошлом мы поговорили о том, можно ли явно вызывать деструкторы у объектов и какие последствия это за собой несет. Обещал рассказать, когда это делать разумно, собственно выполняю обещание.
Проблема в том, что при выходе из скоупа автоматически вызывается деструктор для локальных объектов, а при выделении объектов на куче мы обязаны вручную это делать через delete, в том числе и чтобы освободить память. Прежде чем говорить о каких-то реальных приложениях, нам нужно найти способ, при котором аллокация памяти и создание/удаление объекта полностью и раздельно управляется программистом. И такой способ есть.
Мы знает, как выделить и удалить просто сырой кусок памяти. Статический массив чаров, комбинация malloc+free, и комбинация operator new + operator delete помогут это сделать. Последние операторы имеют ту же семантику, что и malloc+free.
Теперь нужен механизм, позволяющий конструировать объект на уже заранее известной области памяти. Этот механизм называется placement new. Тут п****ц какой-то с названиями на русском языке, на английском new expression - это то, что наиболее часто используют для аллокации+конструирования, operator new - функция, которая выполняет только аллокацию памяти, а placement new - конструирует объект на заданной памяти. И, наконец, явный вызов деструктора позволяет освободить ресурсы из объекта.
Применяя эти связки, мы добиваемся полного контроля над всеми этапами создания и удаления объекта. И в этом случае, проблем с double free или повторном освобождении ресурса происходить не будет. Но это все равно на какое-то время порождает зомби-объекты, для которых есть имя и мы знаем как к ним обратиться, но по факту они уже удалены.
Для чего нужно идти на риск неправильно использовать объекты ради возможности самостоятельно вызывать декструкторы? High risk - high reward. Смысл в оптимизации работы с памятью. Выделение объектов в куче - дело дорогостоящее в плане производительности и использования дополнительных ячеек памяти. Если мы очень сильно ограничены в ресурсах железки, то приходится идти на риск, чтобы добиться желаемого. Обычно выделяется какой-то чанк памяти и на этом чанке создаются и, что самое главное, пересоздаются объекты, потенциально разных типов. Это сильно сокращает используемое пространство памяти, уменьшает ее фрагментацию и снижает издержки на выделение новых ячеек. Сейчас сложно представить себе, что есть такие жесткие рамки, при которых нужно максимумально ужиматься в использовании ресурсов. Однако в прошлом, когда у компьютеров было несколько сот килобайт оперативы, ужимались все и во всем. Даже при работе со стеком нужно было использовать такие ухищрения.
Еще один пример использования явного деструктора - стандартный класс std::vector. Тут на самом деле ситуация очень похожая. У вектора есть некий внутренний буфер, который всегда выделяется с некоторым запасом, чтобы не аллоцировать память на каждое добавление элемента. Поэтому при этом самом добавлении элемента происходит конструирование объекта на нужном блоке памяти. И у вектора есть метод erase, который удаляет элемент из контейнера. Хотя удаляет - слишком общий термин. Он его уничтожает. При этом память, занимаемая этим объектом не освобождается. Поэтому в этом случае просто необходимо использовать явный вызов деструктора.
В принципе, в любом случае, когда необходимо раздельно аллоцировать память и конструировать объекты, будет использоваться явный вызов деструктора. Вряд ли обычные бэкэнд девелоперы когда-нибудь с этим столкнуться. Но знать, что такое есть, надо.
Расскажите о своих кейсах, когда вы знаете, что нужно использовать явный вызов деструктора. Будет интересно почитать другие варианты)
Stay optimized. Stay cool.
#cppcore #optimization #memory
В прошлом мы поговорили о том, можно ли явно вызывать деструкторы у объектов и какие последствия это за собой несет. Обещал рассказать, когда это делать разумно, собственно выполняю обещание.
Проблема в том, что при выходе из скоупа автоматически вызывается деструктор для локальных объектов, а при выделении объектов на куче мы обязаны вручную это делать через delete, в том числе и чтобы освободить память. Прежде чем говорить о каких-то реальных приложениях, нам нужно найти способ, при котором аллокация памяти и создание/удаление объекта полностью и раздельно управляется программистом. И такой способ есть.
Мы знает, как выделить и удалить просто сырой кусок памяти. Статический массив чаров, комбинация malloc+free, и комбинация operator new + operator delete помогут это сделать. Последние операторы имеют ту же семантику, что и malloc+free.
Теперь нужен механизм, позволяющий конструировать объект на уже заранее известной области памяти. Этот механизм называется placement new. Тут п****ц какой-то с названиями на русском языке, на английском new expression - это то, что наиболее часто используют для аллокации+конструирования, operator new - функция, которая выполняет только аллокацию памяти, а placement new - конструирует объект на заданной памяти. И, наконец, явный вызов деструктора позволяет освободить ресурсы из объекта.
Применяя эти связки, мы добиваемся полного контроля над всеми этапами создания и удаления объекта. И в этом случае, проблем с double free или повторном освобождении ресурса происходить не будет. Но это все равно на какое-то время порождает зомби-объекты, для которых есть имя и мы знаем как к ним обратиться, но по факту они уже удалены.
Для чего нужно идти на риск неправильно использовать объекты ради возможности самостоятельно вызывать декструкторы? High risk - high reward. Смысл в оптимизации работы с памятью. Выделение объектов в куче - дело дорогостоящее в плане производительности и использования дополнительных ячеек памяти. Если мы очень сильно ограничены в ресурсах железки, то приходится идти на риск, чтобы добиться желаемого. Обычно выделяется какой-то чанк памяти и на этом чанке создаются и, что самое главное, пересоздаются объекты, потенциально разных типов. Это сильно сокращает используемое пространство памяти, уменьшает ее фрагментацию и снижает издержки на выделение новых ячеек. Сейчас сложно представить себе, что есть такие жесткие рамки, при которых нужно максимумально ужиматься в использовании ресурсов. Однако в прошлом, когда у компьютеров было несколько сот килобайт оперативы, ужимались все и во всем. Даже при работе со стеком нужно было использовать такие ухищрения.
Еще один пример использования явного деструктора - стандартный класс std::vector. Тут на самом деле ситуация очень похожая. У вектора есть некий внутренний буфер, который всегда выделяется с некоторым запасом, чтобы не аллоцировать память на каждое добавление элемента. Поэтому при этом самом добавлении элемента происходит конструирование объекта на нужном блоке памяти. И у вектора есть метод erase, который удаляет элемент из контейнера. Хотя удаляет - слишком общий термин. Он его уничтожает. При этом память, занимаемая этим объектом не освобождается. Поэтому в этом случае просто необходимо использовать явный вызов деструктора.
В принципе, в любом случае, когда необходимо раздельно аллоцировать память и конструировать объекты, будет использоваться явный вызов деструктора. Вряд ли обычные бэкэнд девелоперы когда-нибудь с этим столкнуться. Но знать, что такое есть, надо.
Расскажите о своих кейсах, когда вы знаете, что нужно использовать явный вызов деструктора. Будет интересно почитать другие варианты)
Stay optimized. Stay cool.
#cppcore #optimization #memory
Оптимизации компилятора
Задача компилятора - перевести код на понятном человеку языке программирования в непонятный человеку машинный код. Соответственно, чем больше мы делаем наш язык и программу проще для понимания: вводим удобные языковые конструкции, строим сложные архитектурные абстракции - тем больше работы нужно сделать компилятору, чтобы преобразовать наш код в машинный. Когда-нибудь это дойдет до такого, что мы пишем тех задания на русском языке и на его основе код будет писаться за нас. Но это уже лирика. То, как удобно человеку - не обязательно самый эффективный вариант. С очень большой вероятностью это будет самый медленный вариант.
Компьютер - очень сложная штука. Людей, которые реально понимают, что происходит внутри него, и, исходя из этого, знают, как писать эффективные программы - ну если не по пальцам пересчитать, то их числа явно недостаточно, чтобы закрыть мировой спрос на программистов. Умные дяди думали-думали над этой проблемой и придумали одно решение. "А напишем-ка мы программу, которая будет знать, что происходит внутри машины, позволит людям писать удобный код и, на основе своих знаний, поможет им этот код ускорить!" Это и есть компилятор. Отсюда еще одной задачей компилятора является изменение наивного пользовательского кода так, чтобы его функционал не изменился, а время работы скоратилось. Причем делать такие изменения только по запросу программиста. Так появились оптимизации компилятора и соотвествующие опции, включающие их.
Вчерашний пост очень хорошо демонстрирует описанные выше концепции. Было 4 вида циклов и сравнивались затраты на их итерирование. Те результаты, которые получились там, отражают именно что различия в том, как эти циклы реализованы. То есть компилятор тупо брал и переводил их машинные инструкции без каких либо дополнительных манипуляций со своей стороны. И результаты получились соответствующими: чем проще и понятнее было писать цикл, тем больше времени требовалось на его отработку. Это напрямую подтверждает мысль о том, что за все удобные плюсовые примочки мы платим цену временем работы этих примочек.
Но я не дал компилятору проявить себя во всей красе. Умные люди в комментариях сразу указали на эту проблему. Код компилировался без оптимизаций. И тот пост был подводкой к теме оптимизаций компилятора и как они могут аффектить наш код. Просто так рассказать про это было бы не очень интересно. А так чуть ли не скандал разразился и вы сильнее вовлеклись в тему😆. А я не устаю убеждаться, что в нашем коммьюнити много крутых и внимательных специалистов с критическим мышлением)
И хоть многое уже было проспойлерено, но не все, поэтому начнем раскрывать эту тему с наглядной демонстрации возможностей gcc по изменению выхлопа от вчерашнего кода.
Существует дохренальен флагов оптимизации, но сегодня мы обратим внимание на группу флагов с префиксом -О. -О0, -О1, -О2, -О3. Это такие удобные верхнеуровневые рычажки, дергая которые вы включаете целый набор оптимизаций. Пока не будем углубляться из чего он состоит. Важно знать, что -О0 - дефолтный флаг(нет оптимизаций), и что чем больше чиселка при букве О, тем больше компилятор изменяет ваш код, чтобы он работал быстрее. Не факт, что у него получится что-то ускорить, но в среднем выигрыш будет. Какого характера может быть выигрыш?
Продолжение в комментах
#optimization #compiler #goodoldc #performance
Задача компилятора - перевести код на понятном человеку языке программирования в непонятный человеку машинный код. Соответственно, чем больше мы делаем наш язык и программу проще для понимания: вводим удобные языковые конструкции, строим сложные архитектурные абстракции - тем больше работы нужно сделать компилятору, чтобы преобразовать наш код в машинный. Когда-нибудь это дойдет до такого, что мы пишем тех задания на русском языке и на его основе код будет писаться за нас. Но это уже лирика. То, как удобно человеку - не обязательно самый эффективный вариант. С очень большой вероятностью это будет самый медленный вариант.
Компьютер - очень сложная штука. Людей, которые реально понимают, что происходит внутри него, и, исходя из этого, знают, как писать эффективные программы - ну если не по пальцам пересчитать, то их числа явно недостаточно, чтобы закрыть мировой спрос на программистов. Умные дяди думали-думали над этой проблемой и придумали одно решение. "А напишем-ка мы программу, которая будет знать, что происходит внутри машины, позволит людям писать удобный код и, на основе своих знаний, поможет им этот код ускорить!" Это и есть компилятор. Отсюда еще одной задачей компилятора является изменение наивного пользовательского кода так, чтобы его функционал не изменился, а время работы скоратилось. Причем делать такие изменения только по запросу программиста. Так появились оптимизации компилятора и соотвествующие опции, включающие их.
Вчерашний пост очень хорошо демонстрирует описанные выше концепции. Было 4 вида циклов и сравнивались затраты на их итерирование. Те результаты, которые получились там, отражают именно что различия в том, как эти циклы реализованы. То есть компилятор тупо брал и переводил их машинные инструкции без каких либо дополнительных манипуляций со своей стороны. И результаты получились соответствующими: чем проще и понятнее было писать цикл, тем больше времени требовалось на его отработку. Это напрямую подтверждает мысль о том, что за все удобные плюсовые примочки мы платим цену временем работы этих примочек.
Но я не дал компилятору проявить себя во всей красе. Умные люди в комментариях сразу указали на эту проблему. Код компилировался без оптимизаций. И тот пост был подводкой к теме оптимизаций компилятора и как они могут аффектить наш код. Просто так рассказать про это было бы не очень интересно. А так чуть ли не скандал разразился и вы сильнее вовлеклись в тему😆. А я не устаю убеждаться, что в нашем коммьюнити много крутых и внимательных специалистов с критическим мышлением)
И хоть многое уже было проспойлерено, но не все, поэтому начнем раскрывать эту тему с наглядной демонстрации возможностей gcc по изменению выхлопа от вчерашнего кода.
Существует дохренальен флагов оптимизации, но сегодня мы обратим внимание на группу флагов с префиксом -О. -О0, -О1, -О2, -О3. Это такие удобные верхнеуровневые рычажки, дергая которые вы включаете целый набор оптимизаций. Пока не будем углубляться из чего он состоит. Важно знать, что -О0 - дефолтный флаг(нет оптимизаций), и что чем больше чиселка при букве О, тем больше компилятор изменяет ваш код, чтобы он работал быстрее. Не факт, что у него получится что-то ускорить, но в среднем выигрыш будет. Какого характера может быть выигрыш?
Продолжение в комментах
#optimization #compiler #goodoldc #performance
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
