Инициализация вектора
Под вот этим постом в комментах завелась небольшая дискуссия по поводу целесообразности использования круглых скобок для инициализации объектов. Мол универсальная инициализация предпочтительнее и от круглых скобок можно вообще отказаться. На канале уже есть пост про то, что с вектором универсальную инициализацию использовать не получится из-за того, что у вектора есть конструктор от 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
🔥15👍7❤4
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
🔥15👍8❤5
Снова сравниваем решения задачи с поездами
Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @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амая популярная задачка с собеседований
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно…
Это вообще отдельный жанр в собеседованиях - логические задачки. Есть те, кто любит задавать их каждому кандидату. Но большинство обходит не используют их при найме людей. Оно и понятно, на собесах люди в довольно…
🔥10👍5❤3
Линейное решение задачи с поездами
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х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
🔥15👍4❤2
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
👍17🔥8❤4
strict aliasing
В посте о
Наложение, пересечение областей памяти с разными типами — это достаточно старое и известное явление, именуемое aliasing. С нашей точки зрения указатели
Давайте посмотрим на этот живой пример. Результат отличается, в зависимости от примененных оптимизаций
Познакомимся с правилом strict aliasing. Стандарт С++ определяет понятие динамического типа в §3.9:
В соответствии со стандартом C++ §8.2.1, обращаться к памяти объекта через другой тип легально, если:
1. Если мы меняем динамический тип объекта
2. Если другой тип совпадает с исходным типом
3. Если другой тип — это cv-специфицированный тип динамического типа
4. Если другой тип — это знаковый или беззнаковый тип динамического типа
5. Если другой тип — это знаковый или беззнаковый cv-специфицированный тип динамического типа
6. Если другой тип совпадает с динамическим типом члена, который включает в себя агрегатный тип (структура, класс, массив, или union), в том числе вложенные
Объединение
7. Если другой тип - это родительский тип динамического типа
8. Если другой тип - это cv-специфицированный тип базового класса динамического типа
9. Если другой тип - это char, unsigned char, std::byte, int8_t, uint8_t
Это является исключением, т.к. требуется в разнородных функциях типа memcpy, memset и т.д.
Во всех остальных случаях, обращение к памяти другого объекта является UB!
Пост получился большой, но сказать на эту тему хотелось бы еще больше: о мотивации, o ключевом слове restrict, опциях сборки. Завтра более подробно расскажу, почему в стандарте появилось это правило strict aliasing и что оптимизирует компилятор.
#cppcore #compiler #optimization
В посте о
reinterpret_cast я имел неаккуратность показать не самый легальный пример, т.к. он приводит к UB. Напомню пример:double *pointer_f64 = new double(42);
int64_t *pointer_i64 = reinterpret_cast<int64_t *>(pointer_f64);
Наложение, пересечение областей памяти с разными типами — это достаточно старое и известное явление, именуемое aliasing. С нашей точки зрения указатели
pointer_f64 и pointer_i64 ссылаются на одну и ту же область памяти, но работают с ней, как с разными типами. И это в моем примере работало, где же тут UB?Давайте посмотрим на этот живой пример. Результат отличается, в зависимости от примененных оптимизаций
-O0 vs -O2. Это и есть то самое неопределенное поведение, но полученное в других условиях. Тут является важным именно то, через какой тип программа получает доступ к пересекающейся области памяти. От этого зависит будет ли компилятор подставлять значения констант или нет.Познакомимся с правилом strict aliasing. Стандарт С++ определяет понятие динамического типа в §3.9:
Динамический тип — это тип наиболее наследованного объекта, который инициализирован в памяти.
В соответствии со стандартом C++ §8.2.1, обращаться к памяти объекта через другой тип легально, если:
1. Если мы меняем динамический тип объекта
void *origin = malloc(sizeof(int));
// placement new инициализирует int
int *other = new (origin) int(0);
2. Если другой тип совпадает с исходным типом
int variable = 123;
int *alias = &variable; // OK
3. Если другой тип — это cv-специфицированный тип динамического типа
int variable = 123;
int const *alias = &variable; // OK
4. Если другой тип — это знаковый или беззнаковый тип динамического типа
unsigned int variable = 123;
signed int *alias = reinterpret_cast<signed int*>(&variable); // OK
5. Если другой тип — это знаковый или беззнаковый cv-специфицированный тип динамического типа
unsigned int variable = 123;
signed int const *alias = reinterpret_cast<signed int*>(&variable); // OK
6. Если другой тип совпадает с динамическим типом члена, который включает в себя агрегатный тип (структура, класс, массив, или union), в том числе вложенные
union U
{
int ivalue;
float dvalue;
};
// OK
auto set_default(U &u, int &ivalue)
{
ivalue = 0;
u.dvalue = 2.0;
return std::pair(ivalue, u.dvalue);
}
Объединение
U содержит тип int. Следовательно, int &ivalue потенциально может перезаписывать пересекающуюся память. Компилятор учтет это и не применит оптимизацию.7. Если другой тип - это родительский тип динамического типа
struct Derived : Base {};
// OK
Derived *derived = new Derived;
Base *base = derived;
8. Если другой тип - это cv-специфицированный тип базового класса динамического типа
Derived *derived = new Derived;
const Base *base = derived;
9. Если другой тип - это char, unsigned char, std::byte, int8_t, uint8_t
int *data = new int();
uint8_t *byte = reinterpret_cast<uint8_t*>(data);
Это является исключением, т.к. требуется в разнородных функциях типа memcpy, memset и т.д.
Во всех остальных случаях, обращение к памяти другого объекта является UB!
Пост получился большой, но сказать на эту тему хотелось бы еще больше: о мотивации, o ключевом слове restrict, опциях сборки. Завтра более подробно расскажу, почему в стандарте появилось это правило strict aliasing и что оптимизирует компилятор.
#cppcore #compiler #optimization
❤16👍10🔥5
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
👍23🔥10🤯4😁3❤1
Девиртуализация вызовов. Ч1
#опытным
Продолжаем тему динамического полиморфизма. Практически во всех статьях на эту тему говорят о том, что вызов виртуальных методов сопряжен с накладными расходами. Это действительно так, достаточно посмотреть на результаты бенчмарка.
Вызов виртуальных методов требует дополнительного разыменования указателя для вызова нужной реализации метода. Эта дополнительная операция как раз и тратит ценные такты процессора. А что нам мешает от неё избавиться? По большому счёту, если мы уверены, что работаем с объектом конкретного типа, то мы могли бы сделать что-то такое:
Однако, такой код выглядит вычурно и получается совсем не гибким в перспективе дальнейшей разработки. Ну вдруг кто-то ещё наследуется от
Будем рассуждать логически, что необходимо гарантировать компилятору, чтобы применить такую оптимизацию?
П.1: Неизменность виртуальной таблицы методов
П.2: Однозначность типа полиморфного объекта
П.3: Неизменность виртуального указателя в полиморфном объекте
П.4: Однозначность кандидата при вызове виртуального метода
Компилятор генерирует виртуальные таблицы и не рассчитывает, что вы будете их подменять. Следовательно, П.1 будет выполняться автоматически. В П.2 компилятору необходимо иметь возможность отследить динамический тип полиморфного объекта: чем глубже это получится сделать, тем лучше можно оптимизировать код. Появление П.3 обусловлено тем, что указатель на виртуальную таблицу можно перезаписать, а это уже должно приводить к вызову других методов. Необходимость П.4 обусловлена тем, что в других единицах компиляции могут появиться другие наследники полиморфного класса, о которых мы ничего не знаем в рамках текущей единицы компиляции.
Тут следует сделать оговорку, что стандарт C++ никак не регламентирует реализацию оптимизаций. Следовательно, они могут не выполняться. Данный материал актуален для компиляторов gcc, llvm clang, icc/icx под x86-64:
- GCC (6.1 и выше, см. подробнее)
- LLVM, Clang (8.0.0 и выше, см. подробнее)
- Intel Compiler (icx 2021.1.2 и выше, icc 19.0.0 и выше)
На мой взгляд, достаточно знакомства с этой оптимизацией, чтобы знать свои возможности для потенциального манёвра.
Классика
Начнём с того, что компилятор сам пытается выполнять прямую подстановку вызова метода. Из живого примера:
В данном случае, у компилятора получается проследить все операции над указателем
Запрет на переопределение
Идентификатор
Если явно используется указатель/ссылка на объект класса с запретом на наследование или класса, который содержит неперегружаемые методы, то компилятор заменит косвенный вызов на прямой.
Продолжение в комментариях 👇
#optimization #hardcore #howitworks
#опытным
Продолжаем тему динамического полиморфизма. Практически во всех статьях на эту тему говорят о том, что вызов виртуальных методов сопряжен с накладными расходами. Это действительно так, достаточно посмотреть на результаты бенчмарка.
Вызов виртуальных методов требует дополнительного разыменования указателя для вызова нужной реализации метода. Эта дополнительная операция как раз и тратит ценные такты процессора. А что нам мешает от неё избавиться? По большому счёту, если мы уверены, что работаем с объектом конкретного типа, то мы могли бы сделать что-то такое:
// object is always `Derived`
void baz(Base &object)
{
// explicit cast to Derived
static_cast<Derived&>(object).Derived::vmethod();
}
Однако, такой код выглядит вычурно и получается совсем не гибким в перспективе дальнейшей разработки. Ну вдруг кто-то ещё наследуется от
Derived да перегрузит метод? Значит надо вызывать другой - идём переписывать код. К счастью, в современных компиляторах есть возможность выполнить такой трюк более безопасным и элегантным способом. Девиртуализация — это оптимизация, которая позволяет выполнить прямой вызова виртуального метода, без обращения к таблице виртуальных методов. Необходимым условием применения является наличие гарантий, что вызываемый виртуальный метод будет единственным возможным вариантом для вызова.
Будем рассуждать логически, что необходимо гарантировать компилятору, чтобы применить такую оптимизацию?
П.1: Неизменность виртуальной таблицы методов
П.2: Однозначность типа полиморфного объекта
П.3: Неизменность виртуального указателя в полиморфном объекте
П.4: Однозначность кандидата при вызове виртуального метода
Компилятор генерирует виртуальные таблицы и не рассчитывает, что вы будете их подменять. Следовательно, П.1 будет выполняться автоматически. В П.2 компилятору необходимо иметь возможность отследить динамический тип полиморфного объекта: чем глубже это получится сделать, тем лучше можно оптимизировать код. Появление П.3 обусловлено тем, что указатель на виртуальную таблицу можно перезаписать, а это уже должно приводить к вызову других методов. Необходимость П.4 обусловлена тем, что в других единицах компиляции могут появиться другие наследники полиморфного класса, о которых мы ничего не знаем в рамках текущей единицы компиляции.
Тут следует сделать оговорку, что стандарт C++ никак не регламентирует реализацию оптимизаций. Следовательно, они могут не выполняться. Данный материал актуален для компиляторов gcc, llvm clang, icc/icx под x86-64:
- GCC (6.1 и выше, см. подробнее)
- LLVM, Clang (8.0.0 и выше, см. подробнее)
- Intel Compiler (icx 2021.1.2 и выше, icc 19.0.0 и выше)
На мой взгляд, достаточно знакомства с этой оптимизацией, чтобы знать свои возможности для потенциального манёвра.
Классика
Начнём с того, что компилятор сам пытается выполнять прямую подстановку вызова метода. Из живого примера:
struct Base
{
virtual void vmethod();
};
struct Derived : public Base
{
void vmethod() override;
};
int main()
{
Base *object = new Derived();
// call direct Derived::vmethod()
object->vmethod();
}
В данном случае, у компилятора получается проследить все операции над указателем
object до вызова vmethod, чтобы доказать П.2 и П.3. Условия П.4 выполняется, т.к. main - это единственная точка входа в программу.Запрет на переопределение
Идентификатор
final, используемый как при объявлении классов, так и при объявлении методов, позволяет гарантировать, что других перегрузок методов не может быть в принципе:struct Base
{
virtual void vmethod();
};
struct DerivedA : public Base
{
// Can't override `DerivedA::vmethod`
// in child classes
void vmethod() override final;
};
// Can't inherit from `DerivedB`
struct DerivedB final : public Base
{
void vmethod() override;
};
Если явно используется указатель/ссылка на объект класса с запретом на наследование или класса, который содержит неперегружаемые методы, то компилятор заменит косвенный вызов на прямой.
Продолжение в комментариях 👇
#optimization #hardcore #howitworks
🔥9👍7❤🔥2⚡2❤1🤯1
Странный размер 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
🔥33👍11❤2🤔2
Кейсы применения ref-qualified методов
#опытным
В нескольких предыдущих постах мы говорили про ref-qualified методы и как компилятор выбирает правильную перегрузку. Эта фича многим незнакома и сходу не очень понятно, где ее можно использовать. Давайте сегодня чуть подробнее поговорим о том, где они могут быть реально полезны, чтобы вы вдохновились и использовали такую перегрузку методов чаще.
✅ Разработка библиотек. Довольно очевидно, что разработчикам всяких библиотек нужно учитывать примерно все сценарии использования их классов. Пользователи(безумные) могут скастить объект к константной правой ссылке и методы класса должны работать корректно. Тут очень важно, чтобы тип возвращаемого значения методов соответствовал типу объекта. Пример:
Если объект временный, то возвращаем правую ссылку на мувнутый ресурс. Если объект lvalue, то возвращаем обычную ссылку.
✅ Форсить ограничения на методы. Если у вас методы возвращают левые ссылки(константные и неконстантные), то неплохо бы их пометитьразбитым корытом висячей ссылкой. Спасибо @d7d1cd за кейс)
Также прикрепляю ссылочку на быстрый ответ из блога стандарта С++ посвященный этому кейсу.
✅ Оптимизации. Иногда для определенных ссылочных типов мы можем оптимизировать какой-то метод. Например, в С++23 ввели rvalue reference перегрузку для метода substr класса std::basic_string. Мы знаем, что метод substr формирует новую строку, копируя туда рэндж из оригинальной строки. С++23 теперь сделал так, чтобы при вызове метода substr у правых ссылок объект подстроки тырил данные у оригинальной строки и фактически формировался из ее внутреннего буфера. Более подробно можно почитать в пропоузале.
Также, если вы возвращаете из метода легковесный объект, то в перегрузке для rvalue ссылок вы можете возвращать объект по значению. Так вы избавляетесь от избыточной ссылочной семантики и индирекции и , возможно, улучшаете перформанс. Ведь маленькие типы быстрее передавать и возвращать именно по значению:
В общем, в каждом конкретном случае оптимизировать можно по-разному.
Так что ref-qualified методы - это прекрасный инструмент тонкой настройки в руках профессионалов.
Be useful. Stay cool.
#cppcore #optimization #cpp23
#опытным
В нескольких предыдущих постах мы говорили про ref-qualified методы и как компилятор выбирает правильную перегрузку. Эта фича многим незнакома и сходу не очень понятно, где ее можно использовать. Давайте сегодня чуть подробнее поговорим о том, где они могут быть реально полезны, чтобы вы вдохновились и использовали такую перегрузку методов чаще.
✅ Разработка библиотек. Довольно очевидно, что разработчикам всяких библиотек нужно учитывать примерно все сценарии использования их классов. Пользователи(безумные) могут скастить объект к константной правой ссылке и методы класса должны работать корректно. Тут очень важно, чтобы тип возвращаемого значения методов соответствовал типу объекта. Пример:
template <typename T>
class optional {
constexpr T& value() & {
if (has_value()) {
return this->m_value;
}
throw bad_optional_access();
}
constexpr T const& value() const& {
if (has_value()) {
return this->m_value;
}
throw bad_optional_access();
}
constexpr T&& value() && {
if (has_value()) {
return std::move(this->m_value);
}
throw bad_optional_access();
}
constexpr T const&& value() const&& {
if (has_value()) {
return std::move(this->m_value);
}
throw bad_optional_access();
}
// ...
};
Если объект временный, то возвращаем правую ссылку на мувнутый ресурс. Если объект lvalue, то возвращаем обычную ссылку.
✅ Форсить ограничения на методы. Если у вас методы возвращают левые ссылки(константные и неконстантные), то неплохо бы их пометить
&, чтобы эти методы могли вызываться только у именованных объектов. Ведь если получить ссылку на внутренний ресурс временного объекта, то временный объект уничтожится, а вы останетесь с struct Vector {
int & operator[](size_t index) & { // notice & after arguments
return vec[index];
}
std::vector<int> vec;
};
Vector v;
v.vec = {1, 2, 3, 4};
v[1]; // ok
Vector{{1, 2, 3, 4}}[1]; // compile errorТакже прикрепляю ссылочку на быстрый ответ из блога стандарта С++ посвященный этому кейсу.
✅ Оптимизации. Иногда для определенных ссылочных типов мы можем оптимизировать какой-то метод. Например, в С++23 ввели rvalue reference перегрузку для метода substr класса std::basic_string. Мы знаем, что метод substr формирует новую строку, копируя туда рэндж из оригинальной строки. С++23 теперь сделал так, чтобы при вызове метода substr у правых ссылок объект подстроки тырил данные у оригинальной строки и фактически формировался из ее внутреннего буфера. Более подробно можно почитать в пропоузале.
Также, если вы возвращаете из метода легковесный объект, то в перегрузке для rvalue ссылок вы можете возвращать объект по значению. Так вы избавляетесь от избыточной ссылочной семантики и индирекции и , возможно, улучшаете перформанс. Ведь маленькие типы быстрее передавать и возвращать именно по значению:
struct Vector {
int operator[](size_t index) && { // notice & after arguments
return vec[index];
}
std::vector<int> vec;
};В общем, в каждом конкретном случае оптимизировать можно по-разному.
Так что ref-qualified методы - это прекрасный инструмент тонкой настройки в руках профессионалов.
Be useful. Stay cool.
#cppcore #optimization #cpp23
❤20👍9🔥8⚡2❤🔥2
Передача объекта в методы по значению
#опытным
Небольшие типы данных, особенно до 8 байт длиной, быстрее передавать в методы или возвращать из методов по значению.
С помощью deducing this мы можем вызывать методы не для ссылки(под капотом которой указатель), а для значения объекта.
Семантика будет ровно такая, как вы ожидаете. Объект скопируется внутрь метода и все операции будут происходить над копией.
Давайте посмотрим на пример:
Здесь используется старая нотация с неявным this.
Посмотрим, какой код может нам выдать компилятор:
Пройдемся по строчкам и посмотрим, что тут происходит:
- первая строчка аллоцирует 40 байт на стеке. 4 байта для объекта tiny_tim, 32 байта теневого пространства для метода uwu и 4 байта паддинга.
- инструкция lea загружает адрес tiny_tim в регистр rcx, в котором метод uwu ожидает свой неявный параметр.
- mov помещает число 42 в поле объекта tiny_tim.
- вызываем функцию-метод uwu
- наконец деаллоцируем памяти и выходим из main
А теперь применим deducing this с параметром по значению и посмотрим на ассемблер:
Ассемблер:
Мы переместили 42 в нужный регистр и сразу же прыгнули в функцию uwu, а не вызвали ее. Поскольку мы не передаем объект в метод по ссылке, нам ничего не нужно аллоцировать на стеке. А значит и деаллоцировать ничего не нужно. Раз нам не нужно за собой подчищать, то можно просто прыгнуть в функцию и не возвращаться оттуда.
Конечно, это искусственный пример, оптимизация есть и мы можем в целом ожидать, то объекты маленьких типов можно быстрее обрабатывать с помощью deducing this.
Optimize yourself. Stay cool.
#cpp23 #optimization #compiler
#опытным
Небольшие типы данных, особенно до 8 байт длиной, быстрее передавать в методы или возвращать из методов по значению.
С помощью deducing this мы можем вызывать методы не для ссылки(под капотом которой указатель), а для значения объекта.
Семантика будет ровно такая, как вы ожидаете. Объект скопируется внутрь метода и все операции будут происходить над копией.
Давайте посмотрим на пример:
struct just_a_little_guy {
int how_small;
int uwu();
};
int main() {
just_a_little_guy tiny_tim{42};
return tiny_tim.uwu();
}Здесь используется старая нотация с неявным this.
Посмотрим, какой код может нам выдать компилятор:
sub rsp, 40
lea rcx, QWORD PTR tiny_tim$[rsp]
mov DWORD PTR tiny_tim$[rsp], 42
call int just_a_little_guy::uwu(void)
add rsp, 40
ret 0
Пройдемся по строчкам и посмотрим, что тут происходит:
- первая строчка аллоцирует 40 байт на стеке. 4 байта для объекта tiny_tim, 32 байта теневого пространства для метода uwu и 4 байта паддинга.
- инструкция lea загружает адрес tiny_tim в регистр rcx, в котором метод uwu ожидает свой неявный параметр.
- mov помещает число 42 в поле объекта tiny_tim.
- вызываем функцию-метод uwu
- наконец деаллоцируем памяти и выходим из main
А теперь применим deducing this с параметром по значению и посмотрим на ассемблер:
struct just_a_little_guy {
int how_small;
int uwu(this just_a_little_guy);
};Ассемблер:
mov ecx, 42
jmp static int just_a_little_guy::uwu(this just_a_little_guy)
Мы переместили 42 в нужный регистр и сразу же прыгнули в функцию uwu, а не вызвали ее. Поскольку мы не передаем объект в метод по ссылке, нам ничего не нужно аллоцировать на стеке. А значит и деаллоцировать ничего не нужно. Раз нам не нужно за собой подчищать, то можно просто прыгнуть в функцию и не возвращаться оттуда.
Конечно, это искусственный пример, оптимизация есть и мы можем в целом ожидать, то объекты маленьких типов можно быстрее обрабатывать с помощью deducing this.
Optimize yourself. Stay cool.
#cpp23 #optimization #compiler
Stack Overflow
What is the 'shadow space' in x64 assembly?
I found plenty of topics about this shadow space, but I couldn't find the answer in none of them, so my question is:
How much exactly bytes I need to subtract from the stack pointer, before enteri...
How much exactly bytes I need to subtract from the stack pointer, before enteri...
❤18🔥14👍7❤🔥3
Выравнивание. А зачем?
#новичкам
Представим, что мы пишем что-то связанное с графикой. У нас есть плоскость черно-белых пикселей. Каждый пиксель определяется через цвет черно-белого тона и координаты на плоскости:
Мы хотим сделать супер-мега-блезингово-быстрое приложение, которое при работе будет тратить всего 1 бит памяти. Ну или сколько получится, но как можно меньше. Поэтому мы паримся, как о перфомансе, так и о эффективности по памяти.
Если паримся, значит надо считать.
Посчитаем, сколько байт занимает структура Pixel. Это по сути
Теория - это прекрасно, но надо все проверять:
И получаем..... 12 байт.
/+ 33% от расчетов. Вообще неоптимально получается. Но почему расчеты не сходятся с реальностью?
Дело вот в чём. Процессор читает данные из памяти не хаотично, а определёнными порциями, например, по 4, 8 байта за раз. Причём эти порции он читает только с определённых адресов. Например, 4-байтовое число int обычно нужно читать с адреса, который делится на 4. Чтобы понять, почему так, нужно лезть в устройство процессора и организации работы с памятью. Не будем так глубоко погружаться.
Просто представим аналогию, что процессор, как автобус, может забирать данные определенного размера только с определенных адресов, как людей с остановок.
Иногда на между остановок вообще нельзя останавливаться. Некоторые процессоры этого не позволяют. Иногда можно. Например, можно прочитать int с адреса, который на 3 делится. Но тогда нужно читать 2 соседние порции и из их кусочков составлять нужное число. А это лишние операции и накладные расходы.
То есть высокая скорость обработки данных достигается в случае, когда адреса выровнены по нужной границе.
Теперь вернемся к Pixel. Представим, что мы создаем объект структуры:
Исходя из рассуждений выше, логично предположить, что начало
Но компилятор у нас - не тупая машина, питающаяся текстом программы. Он умный и умеет оптимизировать. Если для скорости работы программы нужно, что адреса
Ну ладно, мы еще повоюем за память. Попробуем перетасовать поля:
Теперь-то будет 9 байт размер?!
Да нет. Все те же 12 байт.
Представьте, что вы сделали массив пикселей. Да, у первого элемента
Кстати, эти дополнительные куски памяти, которые компилятор добавляет для обеспечения выравнивания, называются паддингами(padding). В них не хранятся данные, они нужны чисто для выравнивания.
Сегодня мы рассмотрели, фактически, только предназначение выравнивания. В следующих постах будем раскрывать подробности.
Align yourself. Stay cool.
#cppcore #optimization #compiler
#новичкам
Представим, что мы пишем что-то связанное с графикой. У нас есть плоскость черно-белых пикселей. Каждый пиксель определяется через цвет черно-белого тона и координаты на плоскости:
struct Pixel {
unsigned char grayscale;
int x, y;
};Мы хотим сделать супер-мега-блезингово-быстрое приложение, которое при работе будет тратить всего 1 бит памяти. Ну или сколько получится, но как можно меньше. Поэтому мы паримся, как о перфомансе, так и о эффективности по памяти.
Если паримся, значит надо считать.
Посчитаем, сколько байт занимает структура Pixel. Это по сути
sizeof(unsigned char) + 2 * sizeof(int). размер char'a 1 байт, размер int на современных десктопах 4 байта. С помощью применения дифференциального исчисления в пространстве Минковского получаем 9 байт.Теория - это прекрасно, но надо все проверять:
std::cout << sizeof(Pixel) << std::endl;
И получаем..... 12 байт.
/+ 33% от расчетов. Вообще неоптимально получается. Но почему расчеты не сходятся с реальностью?
Дело вот в чём. Процессор читает данные из памяти не хаотично, а определёнными порциями, например, по 4, 8 байта за раз. Причём эти порции он читает только с определённых адресов. Например, 4-байтовое число int обычно нужно читать с адреса, который делится на 4. Чтобы понять, почему так, нужно лезть в устройство процессора и организации работы с памятью. Не будем так глубоко погружаться.
Просто представим аналогию, что процессор, как автобус, может забирать данные определенного размера только с определенных адресов, как людей с остановок.
Иногда на между остановок вообще нельзя останавливаться. Некоторые процессоры этого не позволяют. Иногда можно. Например, можно прочитать int с адреса, который на 3 делится. Но тогда нужно читать 2 соседние порции и из их кусочков составлять нужное число. А это лишние операции и накладные расходы.
То есть высокая скорость обработки данных достигается в случае, когда адреса выровнены по нужной границе.
Теперь вернемся к Pixel. Представим, что мы создаем объект структуры:
Pixel p{255, 1, 1};Исходя из рассуждений выше, логично предположить, что начало
p будет лежать по уже выравненному адресу для более быстрого чтения. Допустим, он делится на 4. В начале структуры лежит 1 байт цвета. А после лежат 2 int'а по 4 байта, доступ к которым должен быть выровнен. Но если к числу, кратному 4-м, прибавить 1, то оно перестанет делиться на 4. То есть, если данные лежат прям последовательно, то доступ будет невыровненный, а значит медленный.Но компилятор у нас - не тупая машина, питающаяся текстом программы. Он умный и умеет оптимизировать. Если для скорости работы программы нужно, что адреса
x и y должны быть выровнены по четверке, то он сделает магию и выровняет их. Заклинание простое - добавляем 3 байта после поля grayscale и дело в шляпе! Вот поэтому на практике размер Pixel равен 12 байтам.Ну ладно, мы еще повоюем за память. Попробуем перетасовать поля:
struct Pixel {
int x, y;
unsigned char grayscale;
};Теперь-то будет 9 байт размер?!
Да нет. Все те же 12 байт.
Представьте, что вы сделали массив пикселей. Да, у первого элемента
x и y выровнены по 4-ке. Но начиная со второго элемента выравнивание поедет к черту. Так не годится и приходят на помощь все те же 3 байта, только уже в конце структуры.Кстати, эти дополнительные куски памяти, которые компилятор добавляет для обеспечения выравнивания, называются паддингами(padding). В них не хранятся данные, они нужны чисто для выравнивания.
Сегодня мы рассмотрели, фактически, только предназначение выравнивания. В следующих постах будем раскрывать подробности.
Align yourself. Stay cool.
#cppcore #optimization #compiler
❤32👍17🔥7❤🔥3😁3
Выравнивание. Принципы
#новичкам
Сегодня поговорим о выравнивании чуть поближе, чтобы вы в первом приближении могли разобраться, как лежат данные в структурах.
🔍 Однобайтовые данные не нужно выравнивать. Да, процессор читает данные определенными порциями, которые больше 1 байта. Но для любой взятой char переменной, при попытке ее прочитать ее значение будет лежат в самом начале порции. Минимальная адресуемая единица - это 1 байт, поэтому однобайтовые данные неделимы. Не нужно никаких дополнительных плясок.
Для наглядности можно представить себе массив чаров:
Это просто 10 подряд идущих символов. И адреса каждого символа не нужно выравнивать. Поэтому и количество байт, которое занимает этот массив, равно просто количеству его элементов. Без всяких дополнений.
🔍 Адрес поля тривиального типа должен быть выровнен по размеру этого типа
- для short адреса должны быть кратными 2
- для int адреса должны быть кратными 4
- для size_t адреса должны быть кратными 8
- для float адреса должны быть кратными 4
- для double адреса должны быть кратными 8
- для указателей адреса должны быть кратными 8
Если сделать меньше, то придется читать несколькими порциями и вычислять из них нужное значение, что долго.
Если сделать больше, то будет понапрасну тратится память.
Все это актуально для современных 64-битных десктопов.
🔍 Адреса полей кастомных классов должны быть выровнены по длине самого жирного тривиального типа, входящего в состав класса. Не по размеру самого объекта, а по самому жирному его полю.
Например:
У нас есть составная структура А, размер которой равен 2 байтам. Структура B содержит А в качестве поля. Так как в А только char поля, для доступа к ним не нужны паддинги. Поэтому размер В равен 3-м.
Но если будет вот так:
Мало того, что паддинг размером 7 добавися перед полем
🔍 Паддинг добавляется в основном перед тем полем, адрес которого должен быть выровнен. Мы это уже увидели на практике.
В реальности это также значит, что паддинг может добавляться в конце, чтобы обеспечить корректное выравнивание следующих данных.
Допустим, у нас есть структура и мы хотим из нее сделать массив:
Паддинг в 7 байт нужно добавить для того, чтобы адреса поля
Не нужно добавлять паддинги после каждого поля, чтобы для всех них было одинаковое выравнивание. Выровненным по определенной границе должен быть лишь адрес данного конкретного поля. Паддинги добавляются независимо.
🔍 Чтобы оптимально использовать память, лучше располагать поля в порядке убывания их требований к выравниванию. Так вы предыдущим полем гарантируете нужное выравнивание следующему. Сравните:
Реальный размер данных - 15 байт. Для double поля в любом случае нужно выравнивание по 8-ке. Но правильно расположив данные, мы экономим 8 байт.
Тема выравнивания довольно большая и мы прошлись только по верхам. Но даже эти простые принципы помогут вам правильно оценивать размер структур и организовывать их поля оптимальным образом.
Align yourself. Stay cool.
#cppcore #optimization #compiler
#новичкам
Сегодня поговорим о выравнивании чуть поближе, чтобы вы в первом приближении могли разобраться, как лежат данные в структурах.
🔍 Однобайтовые данные не нужно выравнивать. Да, процессор читает данные определенными порциями, которые больше 1 байта. Но для любой взятой char переменной, при попытке ее прочитать ее значение будет лежат в самом начале порции. Минимальная адресуемая единица - это 1 байт, поэтому однобайтовые данные неделимы. Не нужно никаких дополнительных плясок.
Для наглядности можно представить себе массив чаров:
char array[10];
std::cout << sizeof(array) << std::endl;
// OUTPUT: 10
Это просто 10 подряд идущих символов. И адреса каждого символа не нужно выравнивать. Поэтому и количество байт, которое занимает этот массив, равно просто количеству его элементов. Без всяких дополнений.
🔍 Адрес поля тривиального типа должен быть выровнен по размеру этого типа
- для short адреса должны быть кратными 2
- для int адреса должны быть кратными 4
- для size_t адреса должны быть кратными 8
- для float адреса должны быть кратными 4
- для double адреса должны быть кратными 8
- для указателей адреса должны быть кратными 8
Если сделать меньше, то придется читать несколькими порциями и вычислять из них нужное значение, что долго.
Если сделать больше, то будет понапрасну тратится память.
Все это актуально для современных 64-битных десктопов.
🔍 Адреса полей кастомных классов должны быть выровнены по длине самого жирного тривиального типа, входящего в состав класса. Не по размеру самого объекта, а по самому жирному его полю.
Например:
struct A {
char a;
char b;
};
struct B {
char first;
A second;
};
std::cout << sizeof(A) << std::endl;
std::cout << sizeof(B) << std::endl;
// OUTPUT:
// 2
// 3У нас есть составная структура А, размер которой равен 2 байтам. Структура B содержит А в качестве поля. Так как в А только char поля, для доступа к ним не нужны паддинги. Поэтому размер В равен 3-м.
Но если будет вот так:
struct A {
char a;
double b;
};
struct B {
char first;
A second;
};
std::cout << sizeof(A) << std::endl;
std::cout << sizeof(B) << std::endl;
// OUTPUT:
// 16
// 24Мало того, что паддинг размером 7 добавися перед полем
b структуры А, так он же еще добавится перед `second` в В. И в B он такого размера именно потому, чтобы доступ до b в итоге всех размещений был выровнен.🔍 Паддинг добавляется в основном перед тем полем, адрес которого должен быть выровнен. Мы это уже увидели на практике.
В реальности это также значит, что паддинг может добавляться в конце, чтобы обеспечить корректное выравнивание следующих данных.
Допустим, у нас есть структура и мы хотим из нее сделать массив:
struct A {
double a;
char b;
};
A array[10];Паддинг в 7 байт нужно добавить для того, чтобы адреса поля
a из всех элементов, начиная со второго, тоже были выровнены по границе 8.Не нужно добавлять паддинги после каждого поля, чтобы для всех них было одинаковое выравнивание. Выровненным по определенной границе должен быть лишь адрес данного конкретного поля. Паддинги добавляются независимо.
🔍 Чтобы оптимально использовать память, лучше располагать поля в порядке убывания их требований к выравниванию. Так вы предыдущим полем гарантируете нужное выравнивание следующему. Сравните:
struct A {
char a;
// 7 byte padding
double d;
short b;
// 2 byte padding
int c;
};
struct B {
double d;
int c;
short b;
char a;
// 1 byte padding
};
std::cout << sizeof(A) << std::endl;
std::cout << sizeof(B) << std::endl;
// OUTPUT:
// 24
// 16Реальный размер данных - 15 байт. Для double поля в любом случае нужно выравнивание по 8-ке. Но правильно расположив данные, мы экономим 8 байт.
Тема выравнивания довольно большая и мы прошлись только по верхам. Но даже эти простые принципы помогут вам правильно оценивать размер структур и организовывать их поля оптимальным образом.
Align yourself. Stay cool.
#cppcore #optimization #compiler
🔥23❤12👍10