Классы, которые люди самостоятельно пишут, а потом копируют из одного проекта в другой, хотя они уже есть в стандартных библиотеках, в простонародье называются велосипедами. Первый вопрос, который возникает при встрече с таким «велосипедом» — зачем люди переписывают что-то заново? Вариантов может быть несколько.
Сегодня мы не будем говорить о том, что велосипеды — это плохо, это не обязательно так. Мы поговорим о том, что действительно плохо:
А также затронем «вредные» советы, обсудим новейшие практики программирования (C++ 11 и позднее), подумаем, что делать с «идеальным» велосипедом.
О спикере: Антон Полухин (@antoshkka) сотрудник компании Яндекс, активный разработчик библиотек Boost, автор TypeIndex, DLL, Stacktrace, Maintainer Boost Any, Conversion, LexicalСast, Variant, сопредседатель Национальной рабочей группы по стандартизации С++. Всё это вместе значит, что Антон ежедневно видит очень много кода, как опенсорсного, так и коммерческого, и очень хорошо знает, как часто разработчики изобретают велосипеды.
Итак, тема — велосипеды. С какого класса начнем? Правильно — со строки.
Представьте себе, что на дворе глубокое средневековье, люди в латах скачут на лошадях. Вы — разработчик стандартной библиотеки, и единственный стандарт, который есть, это С++ 98. Вам надо написать свою строчку.
Вы начнете писать что-то очень простое без всяких шаблонов. У вас будет указатель на динамический проаллоцированный кусок памяти (data), переменная size, которая хранит количество символов в проаллоцированном куске памяти, и переменная capacity, которая задает размер этого динамического куска памяти.
Для вашего класса строки вы напишите конструктор копирования и конструктор от массива символов. Оба они будут динамически аллоцировать кусок памяти, перемещать туда символы. Здесь написано new + memmove, но на самом деле там могут быть быть небольшие вариации типа malloc, memcpy, смысл остается тем же.
Так как вы — хороший разработчик стандартной библиотеки, вас интересует, насколько хорошо такой класс строки будет работать. Вы открываете пользовательский код, смотрите популярные рецепты и находите что-то наподобие примера ниже, где создается map от строки и int, и туда вставляется пара.
И тут вы понимаете, что дела плохи — медленно, очень медленно.
У вас есть знакомый Вася, который тоже разрабатывает стандартную библиотеку и у него класс строки работает быстрее. Где именно теряется производительность:
Получается весьма печальная картина — 3 вызова new, 3 вызова memmove, пара вызовов delete, и все это жутко медленно. Вас раздражает, что у Васи быстрее, и вы начинаете думать, как сделать лучше.
Тут вы либо сами придумываете, либо где-то читаете о технологии Copy-On-Write (COW). Она позволяет эффективнее работать с временными объектами. Большая часть потерь была за счет того, что создаются временные объекты, которые никак не модифицируются: их просто создали, что-то из них скопировали и тут же уничтожили.
По технологии Copy-On-Write вместо того, чтобы строка уникально владела динамическим объектом, который создан в куче, можно сделать так, чтобы несколько строк одновременно ссылались на динамический объект. Тогда в этом динамическом объекте будет счетчик ссылок — сколько одновременно строчек работает с ним. Код будет выглядеть так:
Вы напишете class string_impl (можно написать его получше) и добавите use_count, т. е. счетчик ссылок — сколько строчек ссылается одновременно на динамический объект. Еще вы поменяете конструктор копирования, теперь он будет брать указатель на динамический объект от входной строки и увеличивать счетчик ссылок.
Немного придется повозиться с неконстантными функциями, которые потенциально меняют строчку. Если две строки владеют динамическим объектом, и одна из них начнет менять его, то другая увидит изменения. Это побочный эффект, которым пользователи будут недовольны, ведь они сначала работали с одной строчкой, а потом она внезапно поменялась.
Нужно добавить проверку: если мы уникально владеем динамическим объектом, то есть счетчик ссылок равен 1, то мы можем делать с ним все, что угодно. Если счетчик ссылок не равен 1, мы должны вызвать new и memmove, создать еще один динамический объект и скопировать туда данные из старого объекта.
Деструктор тоже изменится. Он будет уменьшать счетчик ссылок и смотреть: если мы — последний владелец динамического объекта, тогда его нужно удалить.
В конструкторе от массива символов ничего лучше не стало, по-прежнему new и memmove. Зато дальше вызовется конструктор копирования строки при создании пары, который теперь не вызывает ни new, ни memmove. Когда пара будет вставляться в map, опять будет вызван конструктор копирования строки, который опять-таки не вызывает new и memmove.
Все деструкторы временных объектов тоже не вызовут delete — красота!
Итого, COW более чем в 2 раза ускоряет код в C++98.
Если сейчас мне кто-то скажет, что знает технологию, которая увеличивает производительность моего кода в 2-3 раза, я буду использовать ее везде.
В 90-е года многие библиотеки так делали. Например, есть библиотека QT, где COW присутствует практически во всех базовых классах.
Но технологии не стоят на месте. Наступают 2000-е года, появляются процессоры с Hyper-threading и многоядерные процессоры, причем не только серверные, но и пользовательские:
Теперь у каждого пользователя может быть более, чем 1 ядро. И наша строка уже плохо работает, потому что у нас общий счетчик ссылок.
Например, есть два потока, в них по строке, которые ссылаются на общий динамический объект. Если потоки работают со строками и одновременно решают их удалить, получается, что мы из двух потоков будем пытаться одновременно менять динамический счетчик ссылок use_count. Это приведет к тому, что либо возникнет утечка памяти, либо приложение аварийно завершится.
Чтобы это исправить, вводим атомарную переменную — сделаем вид, что в C++ 98 есть std::atomic. Теперь наш класс выглядит так:
Все работает — замечательно! Почти…
Теперь у нас и конструктор копирования, и деструктор имеет в себе атомарную инструкцию , что не очень хорошо. Неконстантные методы превращаются в жуткое безобразие, потому что появляются граничные условия, которые редко возникают, но которые мы обязаны обрабатывать.
Например, два потока владеют строчками. Эти строчки ссылаются на один и тот же динамический объект. Один поток решает поменять строку. Строка смотрит, что она неуникально владеет динамическим объектом и начинает объект клонировать. В этот момент второй поток говорит, что строчка ему больше не нужна и вызывает ее деструктор.
А первый поток все еще клонирует, вызывает new, memmove. Он закончил свои дела и вдруг понимает, что у него две строки, а нужна ему одна.
Придется еще предусмотреть логику и на такое, а это дополнительные проверки, возможно, дополнительный лишний вызов new и memmove, и опять много атомарных операций, что плохо.
На X86 не атомарный инкремент — простое увеличение integer на единицу занимает один такт процессора [1]. Если сделать эту операцию атомарной, то она будет занимать от 5 до 20 тактов, если только одно ядро делает атомарную инструкцию и если это ядро последнее меняло атомарную переменную [2]. Если ядро не последним меняло атомарную переменную, то в районе 40 тактов.
Итого, такое решение в 5-40 раз медленнее только за счет того, что использована атомарная переменная. Дальше хуже.
Если несколько ядер одновременно работают с атомарной переменной, например, три ядра одновременно хотят сделать инкремент атомарной переменной, у нас будет ядро-счастливчик, которое начнет делать атомарный инкремент, остальные два ядра будут ждать от 5 до 40 тактов, пока ядро не закончит все свои действия.
Тут появляется второе ядро-счастливчик, которое начинает делать атомарную операцию, т. к. не оно последнее меняло атомарную переменную, это займет 40 тактов. Третье ядро все еще ждет. Чем больше ядер одновременно пытаются сделать атомарную операцию над одной и той же переменной, тем дольше последнее ядро будет ждать.
Так выглядит график ожидания последнего ядра:
В этом примере 16 ядер и последнее ядро ждет в районе 600 тактов. Это простой самого несчастливого ядра. Если просуммировать простои, то получится картина простоя получится квадратичная.
На 16 ядрах примерно 6000 тактов ушло в никуда.
Существуют системы, содержащие более 90 ядер, и если все они 90 ядер решат одновременно работать с одной и той же атомарной переменной, все будет очень печально.
COWболее чем в 2 раза ускоряет код в C++98. Все равно Copy-On-Write быстрее и все тут.
В C++11 появляются rvalue reference, что позволяет писать специальные классы и специальные методы, которые работают с временными объектами.
Например, move-конструктор для строки одинаково хорошо работает, если строка COW и если строка самая обычная базовая из средневековья, где динамически аллоцируется объект, и только одна строка им владеет.
Что здесь происходит? На вход приходит объект s. Он временный, мы знаем, что компиллятор его скоро удалит, что больше им никто пользоваться не будет, и мы можем забрать у него ресурсы. С ним можно делать вообще все, что угодно, — главное, чтобы для него потом можно было вызвать деструктор.
Забрали ресурсы. Мы — пустая строка, нам пришла строка с результатом, делаем swap. Теперь мы строка с результатом, а временная строка без всяких ресурсов — пустая.
Посмотрим, как это работает на нашем примере, если у нас строка без COW.
Создается строка от массива символов «Hello». Тут new и memmove — так же, как с COW.
Дальше — лучше. При копировании строки в пару у нас вызовется move-конструктор строки (
При вставке пары в map, map видит, что пара у нас тоже временный объект (
Без new и memmove строка перекочует внутрь map: 1 вызов new и 1 вызов memmove — так же, как с COW, но без атомарных операций.
Хорошо, а если мы хотим копировать строчку? Мы все разумные люди, и хотим копировать строчку, как правило, если мы хотим ее менять.
Без COW мы скопировали строчку, сразу вызывался new и memmove. Мы можем менять строчку и делать все, что угодно.
Если у нас COW строка:
Результат тот же, что и без COW, но, как минимум, пара лишних атомарных операций появляется.
Неконстантные методы по-прежнему ужасны. Если мы хотим пройтись по нашей строке (первым десяти символам в строке), используя индексы, с COW строкой — это 10 атомарных операций над одной и той же атомарной переменной. Если два потока одновременно проходятся по одной и той же строке — большая беда.
В итоге COW-конструктор имеет атомарные операторы, деструктор, скорее всего, будет вызывать атомарные инструкции — везде много атомарных инструкций, которые нам не нужны. Мы их не просили, и это против правил C++. Мы платим за то, чем не пользуемся.
Начиная с C++11 COW строчки запрещены в стандарте. Там наложены специальные условия на строчку, что COW реализовать невозможно. Все современные имплементации стандартных библиотек не имеют COW строк.
COW устарел, осторожнее с его использованием.
Аккуратнее используйте COW в новых проектах. Не доверяйте статьям, которым больше 10 лет, перепроверяйте их. COW не показывает таких хороших результатов, как 20 лет назад.
Если вы имели COW строчку и всем своим пользователям говорили: «У нас COW строка — она идеально все копирует, у нас все замечательно, у нас везде COW», пользователи могли заточиться под это, и писать код с учетом того, что ваши классы используют COW.
Например, пользователь мог написать класс bimap — это класс, который умеет искать как по ключу, так и по значению.
Он мог написать его через два std::map, каждая из которых имеет строчку. Здесь строчка COW, пользователь об этом знает, как и то, что в map две копии строки. Пользователь знает, что они динамически будут ссылаться на один и тот же объект памяти, и что это эффективно по памяти. Если здесь COW строчку поменять на обычную, затраты по памяти увеличатся вдвое.
В C++17 это можно поправить, например, как в примере выше, заменив одну из строчек на string_view. По памяти получится точно также, но уберутся атомарные операции и код станет немного быстрее.
Получается, что к той древней строчке 98 года, которая уникально владела динамическим объектом, мы добавили move-конструктор, и все — это идеальная строка? Ничего лучше сделать нельзя?
Вот что придумали люди. Они посмотрели на один из первых наших примеров, где создается map от строки и int, и туда вставляется пара, долго качали головой и говорили, как все плохо:
Люди придумали, как можно, не меняя размер строки — переменной std::string — хранить в ней символы, не аллоцируя динамически память. Они посмотрели на самый первый класс строки:
Теперь внутри строки в примере выше находится union. Первая часть — это указатель на data и переменная size_t. Вторая часть union — структура — содержит data (маленький буфер размером с char* и size_t). В него влезает примерно 16 байт.
Если сapacity = 0 — это значит, что мы память динамически не аллоцировали и нам надо идти в impl small_buffer_t, и в data будет лежать наша строчка без динамической аллокации.
Если сapacity ? 0, значит, мы динамически где-то проаллоцировали память, и нужно идти в impl no_small_buffer_t. Там есть указатель на динамически проаллоцированный кусок памяти и переменная size.
Конечно, в примере немного упрощенный вариант. Некоторые стандартные библиотеки, например Boost, умеют хранить 22 символа и вдобавок терминирующий 0 без динамических аллокаций, не увеличивая размер строки. Все современные стандартные библиотеки используют этот трюк. Это называется Small String Optimization.
Эта штука хороша, во-первых, на пустых строчках. Они теперь гарантированно не аллоцируют память, и гарантированно вызов метода c_str() теперь не будет аллоцировать память.
Я знаю компании, которые переписывали std::string, потому что у них пустая строка динамически аллоцировала память. Не надо этого больше делать.
Во-вторых, например, наш «Hello!» влезет без динамической аллокации. Если в строчках хранятся логины пользователей, их имена и фамилии отдельно от имен, какие-то идентификаторы, города, страны, названия валют — как правило, все влезет в строчку без динамических аллокаций.
Но люди посмотрели и опять подумали, что медленно. Начиная с C++17, компилятор умеет оптимизировать memmove, его альтернативу — ту, которая находится в строке, на этапе компиляции. Но и этого показалось мало. В C++17 есть Guaranteed copy elision, который гарантирует, что в ряде случаев вообще никаких копирований и memmove не будет. Просто в map каким-то чудом образуется эта строчка без промежуточных переменных.
На примере std::variant рассмотрим, что бывает, если люди пытаются велосипедостроительствовать, не заглядывая в чужие решения.
В C++17 принят класс std::variant — это умный union, который помнит, что он хранит. Мы можем написать std::variant<std::string, std::vector<int>>. Это значит, что вариант может хранить в себе либо строку, либо вектор. Если мы запишем в такой вариант слово «Hello», variant запомнит индекс шаблонного параметра в переменной t_index (что он содержит в себе строчку), по месту проаллоцирует строчку и будет ее хранить.
Если теперь попытаться записать туда вектор, std::variant посмотрит, что он хранит в себе строчку в данный момент, а не вектор, вызовет delete для строки, на месте строки сконструирует вектор и в какой-то момент обновит t_index.
Класс приняли в C++17, и люди по всему миру сразу кинулись его писать заново, переписывать, велосипедостроительствовать.
Выше — реальный код из опенсорсного проекта, видите в нем ошибку? Здесь вместо union получился struct.
Ниже — код из коммерческого проекта:
Здесь ошибка гораздо хуже и во многих имплементациях variant она присутствует. Здесь будут большие проблемы с исключениями.
Например, у нас variant, который хранит в себе std::string и мы пытаемся записать в него вектор. В строчке destroy вызовется delete для строки. С этого момента variant пустой, он ничего не хранит.
Потом на месте строки мы пытаемся создать вектор. Вектор передался по константной ссылке и мы вынуждены его копировать. Вызываем placement new и пытаемся скопировать вектор. Вектор — класс большой, в нем могут храниться пользовательские данные, которые при копировании могут кидать исключения. Допустим, мы кинули исключение. Оно выйдет из текущего блока, вызывая деструкторы всех локальных переменных, и выйдет в блок выше. Там исключение тоже вызовет деструкторы всех локальных переменных. Дойдет до того блока, где был объявлен сам variant и вызовет деструктор варианта.
Деструктор варианта смотрит, что у него записано в переменной index, которая еще не обновлена. В ней записано std::string, т. е. variant думает, что у него есть строка, которую надо удалить. А на самом деле на этом месте уже ничего нет, строка уже удалена. В этот момент вся ваша программа аварийно завершится.
Чтобы этого избежать, достаточно открыть интерфейс стандартной библиотеки и посмотреть, что std::variant имеет функцию valueless_by_exception, удивиться, что это такое, и посмотреть, зачем оно нужно. Можно открыть исходники Boost — там 2/3 кода посвящено этой проблеме.
Я говорю это все к тому, чтобы вы и все ваши подчиненные смотрели, как написаны велосипеды у других людей, во избежание таких печальных последствий. Это очень популярная ошибка. Она везде проскакивает.
Я привожу пример только variant, но в многих других классах есть подобное. Люди переписывают, думают, что что-то лишнее, не заглядывают в чужой код, и это приводит к катастрофическим последствиям.
Самое время попрыгать по больным мозолям.
Можно найти проекты, где все методы помечены как FORCE_INLINE — буквально весь проект вдоль и поперек на гигабайты кода. У людей спрашиваешь:
И с этого момента с людьми очень сложно спорить, потому что у них есть бенчмарк, а ты написать такой бенчмарк не можешь.
Современные процессоры — очень сложные устройства. Никто не знает до конца, как они устроены, даже разработчики процессоров.
Современный процессор не может выполнять вашу программу прямо с диска или прямо с оперативной памяти. Прежде, чем он начнет выполнять программу, он должен подтянуть ее в кеш инструкции. Только оттуда процессор может выполнять инструкции.
Некоторые процессоры имеют хитрый кеш инструкций, который делает дополнительную обработку команд, которые в него попадают. Но кеш инструкций — маленький, в него помещается мало кода. Если вы используете компилятор, который действительно делает FORCE_INLINE, когда вы его просите сделать FORCE_INLINE, у вас увеличивается объем вашего бинарного кода.
Представьте, что на рисунке выше ваша программа. Зеленым отмечено то, что поместилось в кеш. Это еще дополнительно ваш hot path — то место, где ваша программа тратит основное количество времени. Сейчас оно все поместилось в кеш процессора, в кеше инструкций простоя не будет.
Если вы добавите FORCE_INLINE, по бенчмаркам все будет замечательно, но код перестанет помещаться в кеш инструкций.
Когда вы дойдете до красной строчки, процессор скажет: «У меня нет инструкций новых, я должен подождать, пока они подтянутся из памяти». Если это где-то в цикле, он будет постоянно перещелкивать какие-то инструкции, подтягивать их себе из памяти в кеш. Это медленно.
Чтобы ваш бенчмарк правильно отражал реальное положение дел, он должен учитывать все 3 кеша — данных, инструкций и адресов. Для этого бенчмарк должен:
Другими словами, написать такой бенчмарк невозможно. Можно протестировать только ваш production код.
Если вы добавили FORCE_INLINE и ваш production код не стал лучше — лучше убрать FORCE_INLINE. Современные компиляторы умеют инлайнить. 10 лет назад они не умели этого делать хорошо, и FORCE_INLINE действительно в некоторых случаях помогал, например, на GCC. Сейчас нет.
Я говорю, что FORCE_INLINE — плохо, стоит отказаться от него в большинстве случаев, хотя иногда он может быть полезен.
Однако, разработчики компиляторов умные люди. Они видят, что пользователи пишут везде FORCE_INLINE и программы становится медленнее. Поэтому современные компиляторы имеют разные эвристики на игнорирование FORCE_INLINE. Некоторые компиляторы просто считают строчки внутри функции — если ваша функция длиннее трех строчек кода, FORCE_INLINE будет проигнорирован.
Ходит легенда, что есть компилятор, где люди очень сильно озаботились FORCE_INLINE, он их так достал, что они придумали следующую эвристику:
Если вы вдруг написали программу, добавили туда десяток FORCE_INLINE и все стало замечательно быстрее, возможно, что вы пользуетесь этим компилятором. Смотрите ассемблерный код, если вам действительно нужно, чтобы что-то встраивалось, чтобы FORCE_INLINE в этом месте действительно был. Я сам удивлялся тому, что в ряде случаев компиляторы тихо игнорируют FORCE_INLINE.
И наоборот, компилятор может тихо игнорировать ваше «не инлайнить». Он подумает: «Ты не знаешь, что делаешь, написал не инлайнить, но я лучше знаю — я заинлайню».
Я знаю очень умного программиста, который писал имплементацию B-Tree. Все было сделано на С++, на шаблонах, везде perfect forwarding, без всяких динамический аллокаций — просто идеально. Когда этот код стали проверять на одном из Performance Analyze, выяснилось, что исполнение не достаточно быстрое из-за того, что большую часть времени занимает ожидание инструкций в кеше инструкций.
Программист подумал, чуть упростил B-tree, убрал perfect forwarding, заменил его везде на константные ссылки, потому что B-tree никак не менял данные, которые ему приходили, убрал пару шаблонов, сделал код чуть компактнее, добавил noexcept, что тоже уменьшает объем бинарного кода.
В итоге код стал работать в 2 раза быстрее. Алгоритм не меняли — все то же самое, но код стал работать быстрее.
Если не верите мне, что FORCE_INLINE плохо, то рекомендую посмотреть лекции (1, 2) разработчика Clang Чендлера Каррута. Он говорит о том же, что и я, но короче, быстрее и на английском.
От «вредных» бенчмарков переходим к «вредным» советам.
Редко, когда разработка идет под одну платформу. Чаще бывает, что когда-то давным-давно разрабатывали под одну платформу, а теперь — под несколько.
Обычно, если компания начинается, как маленький стартап, она может выбрать себе одну платформу, под которую у нее уже есть заказчики. Постепенно компания растет, код становится популярнее, и приходит мысль портировать его на другие платформы.
Но в момент, когда люди начинают портировать на GCC, программа перестает работать: все компилируется, но тесты не проходят, программа выдает какой-то неадекватный вывод. Люди лезут на Stack Overflow или на другие ресурсы, посвященные программированию, задают этот вопрос и получают ответ:
И действительно — все начинает работать.
Объясню на примере, что делает эта опция (с именем функции я здесь не заморачивался).
Функция qwe принимает в себя две переменные: foo по ссылке, bar по константной ссылке. Это два разных типа данных. Внутри тела функции к f прибавляется значение b и выводится квадрат от b.
Ниже немного ассемблерного псевдокода, который скомпилирует компилятор, если подсунуть опцию -fno-strict-aliasing.
Компилятор:
Тут большинство людей задаются вопросом, зачем мы второй раз подгружали b в регистр, она же уже в регистре.
А потому, что добавили опцию -fno-strict-aliasing. Она говорит компилятору о том, что два типа данных, абсолютно разных, никак друг с другом не пересекающихся, все равно могут находиться в одной и той же ячейке памяти. Исходя из этого компилятор начинает генерировать код.
Когда вы делаете f += b, компилятор думает, что возможно f и b находятся в одной и той же ячейке памяти, и запись в f меняет значение b. И это во всем вашем проекте — добавили опцию, во всем проекте код стал генерироваться хуже.
По разным замерам (например, этому и этому), в зависимости от кода и оптимизации, это дает от 5% до 30% просадки производительности. Все очень зависит от вашего кода. Если у вас просто системные вызовы и работа с сетью, возможно, ничего не изменится для вас с -fno-strict-aliasing. Но просто ее писать при сборке вашего проекта не совсем правильно.
Правильнее включить предупреждение компилятора (GCC умеет предупреждать, когда нарушается strict-aliasing) и исправить в этом месте нарушение strict-aliasing. Как правило, это нарушение происходит, когда вы используете reinterpret_cast для двух несвязанных друг с другом типов.
Вместо reinterpret_cast лучше использовать memcopy или memmove. Компиляторы GCC умеют их оптимизировать. Просадки производительности в том месте, где вы делаете memcpy вместо reinterpret_cast, быть не должно.
От лютой теории переходим к советам, которыми можно пользоваться в повседневной практике.
Скорее всего, вы все это знаете, и, скорее всего, не используете.
Ниже пример функции foo, в которой создается вектор от shared_ptr. Мы знаем, shared_ptr — ровно тысяча. Они вставляются в вектор, и он возвращается.
Первый недочет: если мы знаем, сколько элементов будет хранить наш вектор, стоит вызвать res. reserve(1000). Это заранее проаллоцирует нужное количество памяти, и вектор при вставке в него не будет пытаться угадать, сколько памяти нужно. Без reserve в C++11 и раньше вектор сначала примет значение под 2 элемента, потом под 4 элемента, 8, 16 и т. д. Все это время при изменении размера он будет вызывать new, delete, копирование либо move вашего типа данных, что медленно.
Если же вызвать res. reserve(1000), то вектор точно знает, что это 1000 элементов, никаких дополнительных move, new, delete не будет.
Начиная с C++14 компиляторам разрешено оптимизировать вызовы new. Некоторые компиляторы умеют это делать, но им должно повезти — не во всех случаях это получается. Если вы хотите быть уверены, что компилятор сгенерирует оптимальный код, лучше вставить reserve — хуже не будет.
Другое проблемное место в этом примере компилятор соптимизировать не сможет. Это вызов std::shared_ptr<int>. В этой строчке происходит две динамические аллокации:
Причем в памяти они находятся в разных местах. Если ваше приложение не использует weak pointers, или использует их не сильно, вместо строчки std::shared_ptr<int>(new int) имеет смысл написатьstd::make_shared<int>().
Make_shared сразу проаллоцирует кусок памяти, где может хранить и int, и счетчик ссылок. За счет того, что эти две переменные будут находиться рядом, это более кеш-дружелюбно. Работа с shared_ptr станет чуть быстрее, динамических аллокаций будет не две, а одна.
Итого, код в первом примере мы ускорили чуть более, чем в два раза,просто добавив reserve и заменив конструктор shared_ptr на make_shared.
Код в примере, представленном выше, ужасен. Давайте его улучшать постепенно, причем, скорее всего, не с того места, которое вы заметили.
V здесь копия элемента из вектора. За пределами цикла, и после итераций цикла она нам особо не нужна. Мы можем сказать компилятору, что переменная v больше не используется, заменив v на std::move(v), превратить ее в rvalue, и тогда вставка в результирующий контейнер res произойдет по rvalue ссылке. Ресурсы из v будут просто перекинуты внутрь контейнера, что быстрее.
Массив vector data больше никак не используется, все, что в нем содержится, будет уничтожено при выходе из функции. Вместо того, чтобы копировать v, мы можем написать for (auto&& v: data), т. е. сделать ссылку на v (&& — здесь это тоже ссылка).
В итоге получится следующее: v — ссылка на элемент внутри data. Когда мы к этой ссылке применим std::move, ресурс заберется уже из вектора data — прямо из вектора строка перетянется внутрь контейнера res. Никаких динамических аллокаций в итоге не будет. По сравнению с изначальным кодом стало в 100500 раз быстрее.
Ситуация, как в примере выше, возникает чаще — то же самое, но из вектора мы запоминаем последний элемент, а потом этот последний элемент извлекаем.
Также можно соптимизировать: мы говорим std::string res = std::move(data. back()). После этого в res — значение последнего элемента (мы перетащили ресурсы из вектора в переменную res). Теперь back внутри вектора — это пустая строка, data.pop_back() просто изменит одну из внутренних переменных вектора. Никаких динамических аллокаций, никаких вызовов delete — все быстрее.
В парсерах и протоколах зачастую есть массивы заранее известных строк. Люди часто пишут их так:
Кажется, что это лишь немного не оптимально, но, в принципе, не так страшно. Это произойдет один раз при запуске вашей программы либо при подгрузке DLL.
Но когда проект очень большой, то в разных его частях может накопиться большое количество таких кусков кода — 10, 100, 1000. Инициализация переменной CONSTANTS происходит при запуске программы либо при подгрузке динамической библиотеки. В этот момент этот однопоточный код будет вызывать new, аллокации, инициализировать вектор строк и это может замедлить старт вашей программы либо подгрузку динамической библиотеки.
Для тех, кто пишет realtime приложения и приложения, которые должны быстро рестартовать, если они упали, это может быть критично. Если у вас тысячи и миллионы таких объектов, это замедлит старт программы.
Если вам массив констант нужен, и вы обращаетесь к нему только по индексу или используете его только в range-based for, вы можете заменить вектор на обычный массив. То есть вместо std::vector<std::string> CONSTANTS можно написать std::string_viewCONSTANTS[].
В итоге старт вашего приложения не будет делать дополнительных операций, вызывать new, дополнительно фрагментировать память.
Если вам нужна строгая гарантия, что это выполнится еще до того, как ваша программа запустится, вы можете
Выше базовый класс base, в нем метод act —ничего интересного. Интересно, когда мы от этого base наследуемся. Представьте себе, что вы разработчик в компании и вам сказали разобраться в чужом коде, причем вы видите только то, что идет ниже.
Вы видите только это, вы еще не заглядывали в описание base и вас интересует, что это за метод act, объявлен ли он в базовом классе, перегружаем ли мы его, и вообще, что здесь происходит.
Вы можете сделать код более читабельным, просто добавив слово override:
Он будет не только более читабельный, но и более безопасный. Новый человек, когда будет читать ваш код, увидит override и подумает: «Ага, значит, этот метод объявлен в базовом классе, мы его перегружаем, все в порядке».
Придет новый человек и будет рефакторить базовый класс, поменяет там сигнатуру метода act, добавит туда integer и на этапе компиляции словит ошибку, что в классе-наследнике мы пытаемся заоверрайдить класс, который уже не объявлен в базовом, которого нет.
В итоге он не поломает ваш код. Без override все скомпилируется, как-то будет работать, но будет ошибка на рантайме. На ее отлавливание может уйти много времени. С override сломается на компайлтайме. Человек, который будет делать рефакторинг, это заметит и поправит и здесь метод act.
Еще можно добавить final в первую строку:
Компилятор видит, что класс final. Когда он видит some_implementation и переменную этого класса, и у этой переменной вызывается act, компилятор понимает, что от этого класса больше никто не наследуется, и в нем есть act. Он будет вызывать act без прохода по виртуальным таблицам, не будет различных динамических вещей — будет вызов act, как будто он не виртуальный.
Можно еще чуть-чуть улучшить, запихнув все в анонимный namespace:
Анонимный namespace — это как бы static на стероидах. Можно объявить переменную или функцию статиком, тогда она не будет видна наружу. Все, что вы объявите внутри анонимного пространства имен, будет видно только в этой единице трансляции.
Это хорошо тем, что развязывает руки оптимизатору. Он может делать больше оптимизаций, основываясь на том, что этот класс больше снаружи никто не использует. Оптимизатор также может подумать, что раз этот класс снаружи никто не использует, то его не надо экспортировать, что увеличит скорость загрузки и линковки приложения на рантайме.
Например, в OpenOffice была проблема, что этап динамической загрузки библиотек и линкер, который соединял все зависимости друг с другом, занимали 10 секунд, потому что много символов торчало наружу. Если использовать анонимный namespace, эта проблема станет меньше.
Ниже move constructors для класса my_data_struct. В нем только вектор data.
Только move забыли. И еще noexcept. Давайте перепишем:
Ряд стандартных контейнеров, например, vector, делают сложные подсчеты на этапе компиляции на основе того, помечены ли move-конструкторы как noexcept или нет. Если ваши move-конструкторы не помечены как noexcept, вектор может дополнительно аллоцировать память, когда он будет расширяться, и копировать элементы, вместо того, чтобы их перемещать. Это безобразие, потому что очень медленно.
Чтобы было быстрее, добавляем noexcept.
Эта запись не нравится большинству людей. Здесь непонятно, что написано, и нужно знать:
Куча каких-то деталей, которые нам не нужны.
Надо все лишь написать вот так и все это станет заботой компилятора:
Теперь компилятор сам расставит noexcept, constexpr, если сможет. Код из стандартной библиотеки будет работать быстрее — вам легче.
Хочу рассказать об одной штуке, на которую я недавно натолкнулся, и которая меня удивила.
Люди закешировали деление единицы на число. Они создали extern массив на 256 элементов, в котором запомнили:
Далее работают с этим массивом везде, где нужна часть от 1.
Как вы думаете, так будет быстрее или медленнее? Давайте выясним.
Залезаем в талмуды, где описано, сколько тактов занимают инструкции, и обнаруживаем, что доступ к элементу массива, который находится в L1 кеше, занимает 5 тактов, а деление — 22-29 тактов. Итого такое кеширование может быть в 2-4 раза быстрее, но…
1. Оптимизатор не видит значения
Это серьезное негативное влияние на производительность.
При этом компилятор даже не поверит вам, если вы везде напишите const, потому что он не оптимизирует, основываясь на const. Если вы где-то написали const, компилятор проигнорирует это, потому что где-то в другом месте вы могли написать const_cast.
2. Мы потратили кучу времени на обсуждение этого...
То, что мы потратили кучу времени на его обсуждение, тоже плохо в этом примере. Когда вы увидите его в чужом коде, вы тоже потратите кучу времени, чтобы разобраться, что это за безобразие.
3. Мы потратили 1Kb L1 кеша из 16/32Kb
Люди, которые разрабатывают компиляторы, пишут книги на эту тему и защищают сложные теории, говорят, что в современном мире производительность системы ограничена не скоростью процессора, а зачастую работой с памятью:
Мы потратили 1Kb кеша 1-го уровня на то, чтобы сохранить массив, и другие полезные данные теперь туда не поместятся.
Разработчик стандартной библиотеки C под Linux Ульрих Дреппер написал труд «What Every Programmer Should Know About Memory», то есть о том, что каждый программист должен знать о памяти. В нем намешана серьезная теория и физика, но есть замечательный простой пример важности кеша. На куске кода с переумножением матриц, не меняя практически алгоритм и ассемблерные инструкции, Ульрих Дреппер ускорил производительность в 10 раз просто за счет более эффективной работы с кешом данных.
Станет ли быстрее с таким кешированием единиц или нет — непонятно:
Но люди написали кучу кода, а мы потратили кучу времени на его разбор. Когда вы его встретите в чужом продакшн-коде, вы тоже потратите кучу времени на разбор, ваша производительность упадет. Работодатель будет недоволен.
Мы уже поговорили о «вредном», перейдем к хорошему.
Как написать свой идеальный велосипед, свою идеальную программу, я вам не скажу. На это есть куча книг, часть из них правильная, часть — не очень. Но, если вы написали программу, библиотеку, которая:
добро пожаловать в рабочую группу РГ21, мы:
С первого раза сделать proposal не просто, потому что есть специальные термины, которых надо остерегаться, и определенные формальности, которые надо соблюдать. Если вы просто напишете proposal и отправите его в Комитет, скорее всего, дальше ничего не произойдет, если вы (или доверенный человек) не прибудете в Комитет и не защитите вашу идею перед международным собранием. Приходит много предложений, и в первую очередь приоритет отдается тем, которые лично представляют и защищают.
Заходите на сайт рабочей группы https://stdcpp.ru/, там можно предложить свою идею, посмотреть, что предлагают другие, а самые интересные предложения мы обсудим вместе.
Узнать о других докладах Антона, посмотреть его презентации, публикации и множество другой полезной информации можно здесь — http://apolukhin.github.io/
- Некоторые делают это для самообучения: берут класс стандартной библиотеки, пишут его сами с нуля, сравнивают то, что получилось, с тем, что есть в стандартной библиотеке — в процессе узнают для себя что-то новое.
- Некоторые проекты имеют особое требования к коду. В embedded-разработке принято работать без RTTI и без exception, поэтому части стандартной библиотеки, которые используют RTTI и exception, необходимо переписать без них.
- Редко, но бывает, когда велосипед пишут, потому что могут написать лучше, чем в стандартной библиотеке. Как правило, такие нововведения рано или поздно попадают в стандартную библиотеку.
- Другим только кажется, что они могут написать лучше, и таких людей больше. Но в процессе они обучаются, выясняют для себя что-то новое и что-то интересное открывают.
- Могут быть другие причины.
Сегодня мы не будем говорить о том, что велосипеды — это плохо, это не обязательно так. Мы поговорим о том, что действительно плохо:
- бездумно переносить устаревшие технологии 20-30-летней давности в современные проекты;
- пользоваться «вредными» бенчмарками и оптимизациями.
А также затронем «вредные» советы, обсудим новейшие практики программирования (C++ 11 и позднее), подумаем, что делать с «идеальным» велосипедом.
О спикере: Антон Полухин (@antoshkka) сотрудник компании Яндекс, активный разработчик библиотек Boost, автор TypeIndex, DLL, Stacktrace, Maintainer Boost Any, Conversion, LexicalСast, Variant, сопредседатель Национальной рабочей группы по стандартизации С++. Всё это вместе значит, что Антон ежедневно видит очень много кода, как опенсорсного, так и коммерческого, и очень хорошо знает, как часто разработчики изобретают велосипеды.
Итак, тема — велосипеды. С какого класса начнем? Правильно — со строки.
std::string
string: C++98
Представьте себе, что на дворе глубокое средневековье, люди в латах скачут на лошадях. Вы — разработчик стандартной библиотеки, и единственный стандарт, который есть, это С++ 98. Вам надо написать свою строчку.
class string {
char* data;
size_t size;
size_t capacity;
// ...
};
Вы начнете писать что-то очень простое без всяких шаблонов. У вас будет указатель на динамический проаллоцированный кусок памяти (data), переменная size, которая хранит количество символов в проаллоцированном куске памяти, и переменная capacity, которая задает размер этого динамического куска памяти.
class string {
char* data;
// ...
public:
string(const string& s)
:data(s. clone()) // new + memmove
{}
// ...
string(const char* s); // new + memmove
};
Для вашего класса строки вы напишите конструктор копирования и конструктор от массива символов. Оба они будут динамически аллоцировать кусок памяти, перемещать туда символы. Здесь написано new + memmove, но на самом деле там могут быть быть небольшие вариации типа malloc, memcpy, смысл остается тем же.
Так как вы — хороший разработчик стандартной библиотеки, вас интересует, насколько хорошо такой класс строки будет работать. Вы открываете пользовательский код, смотрите популярные рецепты и находите что-то наподобие примера ниже, где создается map от строки и int, и туда вставляется пара.
std::map<string, int> m;
m.insert(
std::pair<string, int>("Hello!", 1)
);
И тут вы понимаете, что дела плохи — медленно, очень медленно.
У вас есть знакомый Вася, который тоже разрабатывает стандартную библиотеку и у него класс строки работает быстрее. Где именно теряется производительность:
- Cначала вызывается конструктор строки от массива символов — это вызов new и memmove (
string("Hello!")). - Потом вызывается конструктор пары, т. е. будет вызван copy-конструктор строки. Это еще один вызов new и еще один вызов memmove (
make_pair(string("Hello!"), 1)). - Потом эта пара вставляется в map. Копируется пара и ее содержимое — еще один вызов new и memmove (
m.insert(make_pair(string("Hello!"), 1))). - После этого временный объект пары и временный объект строки будут удалены.
Получается весьма печальная картина — 3 вызова new, 3 вызова memmove, пара вызовов delete, и все это жутко медленно. Вас раздражает, что у Васи быстрее, и вы начинаете думать, как сделать лучше.
string: COW
Тут вы либо сами придумываете, либо где-то читаете о технологии Copy-On-Write (COW). Она позволяет эффективнее работать с временными объектами. Большая часть потерь была за счет того, что создаются временные объекты, которые никак не модифицируются: их просто создали, что-то из них скопировали и тут же уничтожили.
std::map<string, int> m;
m.insert(
std::pair<string, int>("Hello!", 1) // копии которые не надо копировать
); // копии которые не надо копировать
По технологии Copy-On-Write вместо того, чтобы строка уникально владела динамическим объектом, который создан в куче, можно сделать так, чтобы несколько строк одновременно ссылались на динамический объект. Тогда в этом динамическом объекте будет счетчик ссылок — сколько одновременно строчек работает с ним. Код будет выглядеть так:
class string_impl {
char* data;
size_t size;
size_t capacity;
size_t use_count; // <===
// ...
};
Вы напишете class string_impl (можно написать его получше) и добавите use_count, т. е. счетчик ссылок — сколько строчек ссылается одновременно на динамический объект. Еще вы поменяете конструктор копирования, теперь он будет брать указатель на динамический объект от входной строки и увеличивать счетчик ссылок.
class string {
string_impl*impl;
public:
string(const string& s)
:impl(s.impl)
{
++impl->use_count;
}
};
Немного придется повозиться с неконстантными функциями, которые потенциально меняют строчку. Если две строки владеют динамическим объектом, и одна из них начнет менять его, то другая увидит изменения. Это побочный эффект, которым пользователи будут недовольны, ведь они сначала работали с одной строчкой, а потом она внезапно поменялась.
Нужно добавить проверку: если мы уникально владеем динамическим объектом, то есть счетчик ссылок равен 1, то мы можем делать с ним все, что угодно. Если счетчик ссылок не равен 1, мы должны вызвать new и memmove, создать еще один динамический объект и скопировать туда данные из старого объекта.
class string {
string_impl*impl;
public:
char& operator[](size_t i) {
if (impl->use_count > 1)
*this = clone();
}
return impl->data[i];
}
};
Деструктор тоже изменится. Он будет уменьшать счетчик ссылок и смотреть: если мы — последний владелец динамического объекта, тогда его нужно удалить.
class string {
string_impl*impl;
public:
~string() {
--impl->use_count;
if (!impl->use_count) {
delete impl;
}
}
};
Производительность вставки в std::map
В конструкторе от массива символов ничего лучше не стало, по-прежнему new и memmove. Зато дальше вызовется конструктор копирования строки при создании пары, который теперь не вызывает ни new, ни memmove. Когда пара будет вставляться в map, опять будет вызван конструктор копирования строки, который опять-таки не вызывает new и memmove.
Все деструкторы временных объектов тоже не вызовут delete — красота!
Итого, COW более чем в 2 раза ускоряет код в C++98.
Если сейчас мне кто-то скажет, что знает технологию, которая увеличивает производительность моего кода в 2-3 раза, я буду использовать ее везде.
В 90-е года многие библиотеки так делали. Например, есть библиотека QT, где COW присутствует практически во всех базовых классах.
Но технологии не стоят на месте. Наступают 2000-е года, появляются процессоры с Hyper-threading и многоядерные процессоры, причем не только серверные, но и пользовательские:
- Hyper-threading в процессорах Pentium 4.
- 2-ядерный процессор Opteron архитектуры AMD64, предназначенный для серверов.
- Pentium D x86-64 — первый 2-ядерный процессором для персональных компьютеров.
Теперь у каждого пользователя может быть более, чем 1 ядро. И наша строка уже плохо работает, потому что у нас общий счетчик ссылок.
Например, есть два потока, в них по строке, которые ссылаются на общий динамический объект. Если потоки работают со строками и одновременно решают их удалить, получается, что мы из двух потоков будем пытаться одновременно менять динамический счетчик ссылок use_count. Это приведет к тому, что либо возникнет утечка памяти, либо приложение аварийно завершится.
string: COW MT fixes
Чтобы это исправить, вводим атомарную переменную — сделаем вид, что в C++ 98 есть std::atomic. Теперь наш класс выглядит так:
class string_impl {
char* data;
size_t size;
size_t capacity;
atomic<size_t> use_count; //<=== Fixed
// ...
};
Все работает — замечательно! Почти…
Теперь у нас и конструктор копирования, и деструктор имеет в себе атомарную инструкцию , что не очень хорошо. Неконстантные методы превращаются в жуткое безобразие, потому что появляются граничные условия, которые редко возникают, но которые мы обязаны обрабатывать.
class string {
string_impl*impl;
public:
char& operator[](size_t i) {
if (impl->use_count > 1) { // atomic
string cloned = clone(); // new + memmove + atomic —
swap(*this, cloned);
// atomic in ~string for cloned; delete in ~string if other thread released the string
} // ...
}
};
Например, два потока владеют строчками. Эти строчки ссылаются на один и тот же динамический объект. Один поток решает поменять строку. Строка смотрит, что она неуникально владеет динамическим объектом и начинает объект клонировать. В этот момент второй поток говорит, что строчка ему больше не нужна и вызывает ее деструктор.
А первый поток все еще клонирует, вызывает new, memmove. Он закончил свои дела и вдруг понимает, что у него две строки, а нужна ему одна.
Придется еще предусмотреть логику и на такое, а это дополнительные проверки, возможно, дополнительный лишний вызов new и memmove, и опять много атомарных операций, что плохо.
Atomic
На X86 не атомарный инкремент — простое увеличение integer на единицу занимает один такт процессора [1]. Если сделать эту операцию атомарной, то она будет занимать от 5 до 20 тактов, если только одно ядро делает атомарную инструкцию и если это ядро последнее меняло атомарную переменную [2]. Если ядро не последним меняло атомарную переменную, то в районе 40 тактов.
Итого, такое решение в 5-40 раз медленнее только за счет того, что использована атомарная переменная. Дальше хуже.
Если несколько ядер одновременно работают с атомарной переменной, например, три ядра одновременно хотят сделать инкремент атомарной переменной, у нас будет ядро-счастливчик, которое начнет делать атомарный инкремент, остальные два ядра будут ждать от 5 до 40 тактов, пока ядро не закончит все свои действия.
Тут появляется второе ядро-счастливчик, которое начинает делать атомарную операцию, т. к. не оно последнее меняло атомарную переменную, это займет 40 тактов. Третье ядро все еще ждет. Чем больше ядер одновременно пытаются сделать атомарную операцию над одной и той же переменной, тем дольше последнее ядро будет ждать.
Так выглядит график ожидания последнего ядра:
В этом примере 16 ядер и последнее ядро ждет в районе 600 тактов. Это простой самого несчастливого ядра. Если просуммировать простои, то получится картина простоя получится квадратичная.
На 16 ядрах примерно 6000 тактов ушло в никуда.
Существуют системы, содержащие более 90 ядер, и если все они 90 ядер решат одновременно работать с одной и той же атомарной переменной, все будет очень печально.
COW
С++11
В C++11 появляются rvalue reference, что позволяет писать специальные классы и специальные методы, которые работают с временными объектами.
Например, move-конструктор для строки одинаково хорошо работает, если строка COW и если строка самая обычная базовая из средневековья, где динамически аллоцируется объект, и только одна строка им владеет.
string::string(string&& s) {
swap(*this, s);
}
Что здесь происходит? На вход приходит объект s. Он временный, мы знаем, что компиллятор его скоро удалит, что больше им никто пользоваться не будет, и мы можем забрать у него ресурсы. С ним можно делать вообще все, что угодно, — главное, чтобы для него потом можно было вызвать деструктор.
Забрали ресурсы. Мы — пустая строка, нам пришла строка с результатом, делаем swap. Теперь мы строка с результатом, а временная строка без всяких ресурсов — пустая.
Посмотрим, как это работает на нашем примере, если у нас строка без COW.
std::map<string, int> m;
m.insert(
std::pair<string, int>("Hello!", 1) // string("Hello!")
);
Создается строка от массива символов «Hello». Тут new и memmove — так же, как с COW.
Дальше — лучше. При копировании строки в пару у нас вызовется move-конструктор строки (
pair(string&&, int)). Пара видит, что строка временная, и забирает ресурсы из временного объекта. New и memmove не будет.При вставке пары в map, map видит, что пара у нас тоже временный объект (
m.insert(pair&&)). Map вызовет move-конструктор для пары, пара вызовет move-конструктор для своего содержимого, move-конструктор для строки.Без new и memmove строка перекочует внутрь map: 1 вызов new и 1 вызов memmove — так же, как с COW, но без атомарных операций.
Хорошо, а если мы хотим копировать строчку? Мы все разумные люди, и хотим копировать строчку, как правило, если мы хотим ее менять.
Без COW мы скопировали строчку, сразу вызывался new и memmove. Мы можем менять строчку и делать все, что угодно.
Если у нас COW строка:
- создаем новый объект строки с атомарным инкрементом общего счетчика ссылок;
- одну из этих строчек начинаем менять;
- строчка атомарно посмотрит, что мы не уникально владеем строкой, вызовет new, memmove, проведет дополнительные проверки, чтобы внезапно второй поток не уничтожил эту строчку, что у нас нужное количество строчек и т. д.
Результат тот же, что и без COW, но, как минимум, пара лишних атомарных операций появляется.
char& operator[](size_t i) {
if (impl->use_count > 1) { // atomic
string cloned = clone(); // atomic—
swap(*this, cloned); // atomic in ~string for cloned
}
return impl->data[i];
}
Неконстантные методы по-прежнему ужасны. Если мы хотим пройтись по нашей строке (первым десяти символам в строке), используя индексы, с COW строкой — это 10 атомарных операций над одной и той же атомарной переменной. Если два потока одновременно проходятся по одной и той же строке — большая беда.
В итоге COW-конструктор имеет атомарные операторы, деструктор, скорее всего, будет вызывать атомарные инструкции — везде много атомарных инструкций, которые нам не нужны. Мы их не просили, и это против правил C++. Мы платим за то, чем не пользуемся.
Начиная с C++11 COW строчки запрещены в стандарте. Там наложены специальные условия на строчку, что COW реализовать невозможно. Все современные имплементации стандартных библиотек не имеют COW строк.
COW устарел, осторожнее с его использованием.
Аккуратнее используйте COW в новых проектах. Не доверяйте статьям, которым больше 10 лет, перепроверяйте их. COW не показывает таких хороших результатов, как 20 лет назад.
Случаи, где COW все еще жжет
Если вы имели COW строчку и всем своим пользователям говорили: «У нас COW строка — она идеально все копирует, у нас все замечательно, у нас везде COW», пользователи могли заточиться под это, и писать код с учетом того, что ваши классы используют COW.
Например, пользователь мог написать класс bimap — это класс, который умеет искать как по ключу, так и по значению.
// COW legacy
class bimap {
std::map<string, int> str_to_int;
std::map<int, string> int_to_str;
public:
void insert(string s, int i) {
str_to_int.insert(make_pair(s, i));
int_to_str.insert(make_pair(i, std::move(s)));
}
Он мог написать его через два std::map, каждая из которых имеет строчку. Здесь строчка COW, пользователь об этом знает, как и то, что в map две копии строки. Пользователь знает, что они динамически будут ссылаться на один и тот же объект памяти, и что это эффективно по памяти. Если здесь COW строчку поменять на обычную, затраты по памяти увеличатся вдвое.
// COW legacy fix
class bimap {
std::map<string, int> str_to_int;
std::map<int, string_view> int_to_str;
public:
void insert(string s, int i) {
auto it = str_to_int.insert(make_pair(std::move(s), i));
int_to_str.insert(make_pair(i, *it.first)));
}
В C++17 это можно поправить, например, как в примере выше, заменив одну из строчек на string_view. По памяти получится точно также, но уберутся атомарные операции и код станет немного быстрее.
Одна оптимизация для string
Получается, что к той древней строчке 98 года, которая уникально владела динамическим объектом, мы добавили move-конструктор, и все — это идеальная строка? Ничего лучше сделать нельзя?
Вот что придумали люди. Они посмотрели на один из первых наших примеров, где создается map от строки и int, и туда вставляется пара, долго качали головой и говорили, как все плохо:
— Тут вызывается new и memmove. За new может стоять системный вызов и атомарные операции, а у нас еще нет C++14, где компилятор умеет оптимизировать new. Все очень плохо — давайте сделаем что-нибудь получше!
Люди придумали, как можно, не меняя размер строки — переменной std::string — хранить в ней символы, не аллоцируя динамически память. Они посмотрели на самый первый класс строки:
—У нас здесь указатель на 64-битной платформе — это 8 байт, у нас size тоже на 64-битной платформе — это опять 8 байт. Это 16 байт — в них можно сохранить 15 символов! Что, если пользоваться этими двумя переменными не как переменной-указателем и переменной size, а прямо поверх них располагать данные.
class string {
size_t capacity;
union {
struct no_small_buffer_t {
char* data;
size_t size;
} no_small_buffer;
struct small_buffer_t {
char data[sizeof(no_small_buffer_t)];
}small_buffer;
}impl;
}
Теперь внутри строки в примере выше находится union. Первая часть — это указатель на data и переменная size_t. Вторая часть union — структура — содержит data (маленький буфер размером с char* и size_t). В него влезает примерно 16 байт.
Если сapacity = 0 — это значит, что мы память динамически не аллоцировали и нам надо идти в impl small_buffer_t, и в data будет лежать наша строчка без динамической аллокации.
Если сapacity ? 0, значит, мы динамически где-то проаллоцировали память, и нужно идти в impl no_small_buffer_t. Там есть указатель на динамически проаллоцированный кусок памяти и переменная size.
Конечно, в примере немного упрощенный вариант. Некоторые стандартные библиотеки, например Boost, умеют хранить 22 символа и вдобавок терминирующий 0 без динамических аллокаций, не увеличивая размер строки. Все современные стандартные библиотеки используют этот трюк. Это называется Small String Optimization.
Эта штука хороша, во-первых, на пустых строчках. Они теперь гарантированно не аллоцируют память, и гарантированно вызов метода c_str() теперь не будет аллоцировать память.
Я знаю компании, которые переписывали std::string, потому что у них пустая строка динамически аллоцировала память. Не надо этого больше делать.
Во-вторых, например, наш «Hello!» влезет без динамической аллокации. Если в строчках хранятся логины пользователей, их имена и фамилии отдельно от имен, какие-то идентификаторы, города, страны, названия валют — как правило, все влезет в строчку без динамических аллокаций.
Но люди посмотрели и опять подумали, что медленно. Начиная с C++17, компилятор умеет оптимизировать memmove, его альтернативу — ту, которая находится в строке, на этапе компиляции. Но и этого показалось мало. В C++17 есть Guaranteed copy elision, который гарантирует, что в ряде случаев вообще никаких копирований и memmove не будет. Просто в map каким-то чудом образуется эта строчка без промежуточных переменных.
Со строкой разобрались, но ответы на некоторые уточняющие вопросы из зала здесь
— Больше-то не нужно!
— У меня реальный случай из практики. Замена COW-строки на строку со Small String Optimization ускорила проект на 7-15%, потому что большую часть времени мы работаем почему-то с маленькими строчками, которые в std::string влезают. Поэтому становится быстрее.
Можно ли использовать строчку, которая будет динамически в памяти хранить size и capacity? Можно. Тут подключатся проблемы с оптимизатором. Видя, что у нас указатель на какой-то участок памяти, он не сможет лучше оптимизировать эти переменные. Оптимизатор не сможет делать эвристики, основанные на size и capacity. Если же size и capacity расположены на стеке и оптимизатор видит это, он сможет делать на этом эвристики и лучше оптимизировать код.
— Да, хуже. Но количество байтов, которое есть в small_buffer, все то же.
— Пока все выглядит как реклама велосипедов на самом деле. Например, COW в GCC был до 2015 года, до выхода 5.1. Значит, нужно было писать велосипеды?
— Больше-то не нужно!
— Как? Например, все говорят, что классная штука Small String Optimization. Но, допустим, когда строка выделяется динамически, size и capacity можно засунуть в тот же самый буфер, в котором лежит строка. Тогда строка будет всего 8 байт. И если у меня в объекте много строк, это будет выгоднее?
— У меня реальный случай из практики. Замена COW-строки на строку со Small String Optimization ускорила проект на 7-15%, потому что большую часть времени мы работаем почему-то с маленькими строчками, которые в std::string влезают. Поэтому становится быстрее.
Можно ли использовать строчку, которая будет динамически в памяти хранить size и capacity? Можно. Тут подключатся проблемы с оптимизатором. Видя, что у нас указатель на какой-то участок памяти, он не сможет лучше оптимизировать эти переменные. Оптимизатор не сможет делать эвристики, основанные на size и capacity. Если же size и capacity расположены на стеке и оптимизатор видит это, он сможет делать на этом эвристики и лучше оптимизировать код.
— С широкими юникодными строками эта оптимизация хуже работает?
— Да, хуже. Но количество байтов, которое есть в small_buffer, все то же.
Разработка без оглядки на готовые решения. std::variant
На примере std::variant рассмотрим, что бывает, если люди пытаются велосипедостроительствовать, не заглядывая в чужие решения.
В C++17 принят класс std::variant — это умный union, который помнит, что он хранит. Мы можем написать std::variant<std::string, std::vector<int>>. Это значит, что вариант может хранить в себе либо строку, либо вектор. Если мы запишем в такой вариант слово «Hello», variant запомнит индекс шаблонного параметра в переменной t_index (что он содержит в себе строчку), по месту проаллоцирует строчку и будет ее хранить.
union {
T0 v0;
T1 v1;
T2 v2;
// ...
};
int t_index;
Если теперь попытаться записать туда вектор, std::variant посмотрит, что он хранит в себе строчку в данный момент, а не вектор, вызовет delete для строки, на месте строки сконструирует вектор и в какой-то момент обновит t_index.
Класс приняли в C++17, и люди по всему миру сразу кинулись его писать заново, переписывать, велосипедостроительствовать.
template <class... T>
class variant {
// ...
std::tuple<T...> data;
};
Выше — реальный код из опенсорсного проекта, видите в нем ошибку? Здесь вместо union получился struct.
Ниже — код из коммерческого проекта:
variant<T...>& operator=(const U& value) {
if (&value == this) {
return *this;
}
destroy(); // data->~Ti()
construct_value(value); // new (data) Tj(value);
t_index = get_index_from_type<U>(); // t_index = j;
return *this;
}
Здесь ошибка гораздо хуже и во многих имплементациях variant она присутствует. Здесь будут большие проблемы с исключениями.
Например, у нас variant, который хранит в себе std::string и мы пытаемся записать в него вектор. В строчке destroy вызовется delete для строки. С этого момента variant пустой, он ничего не хранит.
Потом на месте строки мы пытаемся создать вектор. Вектор передался по константной ссылке и мы вынуждены его копировать. Вызываем placement new и пытаемся скопировать вектор. Вектор — класс большой, в нем могут храниться пользовательские данные, которые при копировании могут кидать исключения. Допустим, мы кинули исключение. Оно выйдет из текущего блока, вызывая деструкторы всех локальных переменных, и выйдет в блок выше. Там исключение тоже вызовет деструкторы всех локальных переменных. Дойдет до того блока, где был объявлен сам variant и вызовет деструктор варианта.
variant<T...>& operator=(const U& value) {
if (&value == this) {
return *this;
}
destroy(); // data->~Ti()
construct_value(value); // throw; ...
// ...
// ~variant() {
// data->~Ti() // Oops!!!
Деструктор варианта смотрит, что у него записано в переменной index, которая еще не обновлена. В ней записано std::string, т. е. variant думает, что у него есть строка, которую надо удалить. А на самом деле на этом месте уже ничего нет, строка уже удалена. В этот момент вся ваша программа аварийно завершится.
Чтобы этого избежать, достаточно открыть интерфейс стандартной библиотеки и посмотреть, что std::variant имеет функцию valueless_by_exception, удивиться, что это такое, и посмотреть, зачем оно нужно. Можно открыть исходники Boost — там 2/3 кода посвящено этой проблеме.
Я говорю это все к тому, чтобы вы и все ваши подчиненные смотрели, как написаны велосипеды у других людей, во избежание таких печальных последствий. Это очень популярная ошибка. Она везде проскакивает.
Я привожу пример только variant, но в многих других классах есть подобное. Люди переписывают, думают, что что-то лишнее, не заглядывают в чужой код, и это приводит к катастрофическим последствиям.
Пожалуйста, смотрите в код, который вы переписываете или придумываете
заново. Такой подход значительно упростит вашу жизнь.
FORCE_INLINE
Самое время попрыгать по больным мозолям.
Можно найти проекты, где все методы помечены как FORCE_INLINE — буквально весь проект вдоль и поперек на гигабайты кода. У людей спрашиваешь:
— Зачем вы все пометили FORCE_INLINE?
— Мы написали маленький бенчмарк, проверили — с FORCE_INLINE быстрее. Мы написали и здесь маленький бенчмарк — проверили, с FORCE_INLINE быстрее. Мы протестировали все маленькими бенчмарками и везде с FORCE_INLINE быстрее — мы FORCE_INLINE запихнули во весь проект.
— Вы неправильно делали бенчмарк.
И с этого момента с людьми очень сложно спорить, потому что у них есть бенчмарк, а ты написать такой бенчмарк не можешь.
У процессора есть не только кеш данных
Современные процессоры — очень сложные устройства. Никто не знает до конца, как они устроены, даже разработчики процессоров.
"Большинство современных микропроцессоров для компьютеров и серверов имеют как минимум три независимых кеша: кеш инструкций для ускорения загрузки машинного кода, кеш данных для ускорения чтения и записи данных и буфер ассоциативной трансляции (TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных" [1].
Современный процессор не может выполнять вашу программу прямо с диска или прямо с оперативной памяти. Прежде, чем он начнет выполнять программу, он должен подтянуть ее в кеш инструкции. Только оттуда процессор может выполнять инструкции.
Некоторые процессоры имеют хитрый кеш инструкций, который делает дополнительную обработку команд, которые в него попадают. Но кеш инструкций — маленький, в него помещается мало кода. Если вы используете компилятор, который действительно делает FORCE_INLINE, когда вы его просите сделать FORCE_INLINE, у вас увеличивается объем вашего бинарного кода.
Представьте, что на рисунке выше ваша программа. Зеленым отмечено то, что поместилось в кеш. Это еще дополнительно ваш hot path — то место, где ваша программа тратит основное количество времени. Сейчас оно все поместилось в кеш процессора, в кеше инструкций простоя не будет.
Если вы добавите FORCE_INLINE, по бенчмаркам все будет замечательно, но код перестанет помещаться в кеш инструкций.
Когда вы дойдете до красной строчки, процессор скажет: «У меня нет инструкций новых, я должен подождать, пока они подтянутся из памяти». Если это где-то в цикле, он будет постоянно перещелкивать какие-то инструкции, подтягивать их себе из памяти в кеш. Это медленно.
Чтобы ваш бенчмарк правильно отражал реальное положение дел, он должен учитывать все 3 кеша — данных, инструкций и адресов. Для этого бенчмарк должен:
- в бинарном виде занимать столько же, сколько ваш production код;
- иметь приблизительно такое же количество функций и переходов, как ваш production код;
- вызывать методы так же, как ваш production код.
Другими словами, написать такой бенчмарк невозможно. Можно протестировать только ваш production код.
Если вы добавили FORCE_INLINE и ваш production код не стал лучше — лучше убрать FORCE_INLINE. Современные компиляторы умеют инлайнить. 10 лет назад они не умели этого делать хорошо, и FORCE_INLINE действительно в некоторых случаях помогал, например, на GCC. Сейчас нет.
Я говорю, что FORCE_INLINE — плохо, стоит отказаться от него в большинстве случаев, хотя иногда он может быть полезен.
Однако, разработчики компиляторов умные люди. Они видят, что пользователи пишут везде FORCE_INLINE и программы становится медленнее. Поэтому современные компиляторы имеют разные эвристики на игнорирование FORCE_INLINE. Некоторые компиляторы просто считают строчки внутри функции — если ваша функция длиннее трех строчек кода, FORCE_INLINE будет проигнорирован.
Ходит легенда, что есть компилятор, где люди очень сильно озаботились FORCE_INLINE, он их так достал, что они придумали следующую эвристику:
Если пользователь помечает FORCE_INLINE функцию, которую гарантированно не надо делать FORCE_INLINE, компилятор это запоминает и считает, сколько раз такое произошло. Если превышено некое пороговое значение, компилятор у себя выставляет галочку: «Пользователь не знает, что такое FORCE_INLINE и использует его не там, где нужно — игнорировать все FORCE_INLINE от пользователя».
Если вы вдруг написали программу, добавили туда десяток FORCE_INLINE и все стало замечательно быстрее, возможно, что вы пользуетесь этим компилятором. Смотрите ассемблерный код, если вам действительно нужно, чтобы что-то встраивалось, чтобы FORCE_INLINE в этом месте действительно был. Я сам удивлялся тому, что в ряде случаев компиляторы тихо игнорируют FORCE_INLINE.
И наоборот, компилятор может тихо игнорировать ваше «не инлайнить». Он подумает: «Ты не знаешь, что делаешь, написал не инлайнить, но я лучше знаю — я заинлайню».
Cлучай из практики
Я знаю очень умного программиста, который писал имплементацию B-Tree. Все было сделано на С++, на шаблонах, везде perfect forwarding, без всяких динамический аллокаций — просто идеально. Когда этот код стали проверять на одном из Performance Analyze, выяснилось, что исполнение не достаточно быстрое из-за того, что большую часть времени занимает ожидание инструкций в кеше инструкций.
Программист подумал, чуть упростил B-tree, убрал perfect forwarding, заменил его везде на константные ссылки, потому что B-tree никак не менял данные, которые ему приходили, убрал пару шаблонов, сделал код чуть компактнее, добавил noexcept, что тоже уменьшает объем бинарного кода.
В итоге код стал работать в 2 раза быстрее. Алгоритм не меняли — все то же самое, но код стал работать быстрее.
Если не верите мне, что FORCE_INLINE плохо, то рекомендую посмотреть лекции (1, 2) разработчика Clang Чендлера Каррута. Он говорит о том же, что и я, но короче, быстрее и на английском.
От «вредных» бенчмарков переходим к «вредным» советам.
Aliasing
Редко, когда разработка идет под одну платформу. Чаще бывает, что когда-то давным-давно разрабатывали под одну платформу, а теперь — под несколько.
Обычно, если компания начинается, как маленький стартап, она может выбрать себе одну платформу, под которую у нее уже есть заказчики. Постепенно компания растет, код становится популярнее, и приходит мысль портировать его на другие платформы.
Но в момент, когда люди начинают портировать на GCC, программа перестает работать: все компилируется, но тесты не проходят, программа выдает какой-то неадекватный вывод. Люди лезут на Stack Overflow или на другие ресурсы, посвященные программированию, задают этот вопрос и получают ответ:
— Добавьте волшебную опцию компилятора -fno-strict-aliasing и у вас все заработает.
И действительно — все начинает работать.
Объясню на примере, что делает эта опция (с именем функции я здесь не заморачивался).
bar qwe(foo& f, const bar& b) {
f += b;
return b * b;
}
Функция qwe принимает в себя две переменные: foo по ссылке, bar по константной ссылке. Это два разных типа данных. Внутри тела функции к f прибавляется значение b и выводится квадрат от b.
Ниже немного ассемблерного псевдокода, который скомпилирует компилятор, если подсунуть опцию -fno-strict-aliasing.
bar qwe(foo& f, const bar& b) {
// load b
// load f
f += b;
// load b
return b * b;
}
Компилятор:
- подгрузит в регистр значение переменной b,
- подгрузит в регистр значение переменной f,
- произведет операцию f += b,
- запишет значение f в память,
- подгрузит значение b опять в память,
- выполнит b2.
Тут большинство людей задаются вопросом, зачем мы второй раз подгружали b в регистр, она же уже в регистре.
А потому, что добавили опцию -fno-strict-aliasing. Она говорит компилятору о том, что два типа данных, абсолютно разных, никак друг с другом не пересекающихся, все равно могут находиться в одной и той же ячейке памяти. Исходя из этого компилятор начинает генерировать код.
Когда вы делаете f += b, компилятор думает, что возможно f и b находятся в одной и той же ячейке памяти, и запись в f меняет значение b. И это во всем вашем проекте — добавили опцию, во всем проекте код стал генерироваться хуже.
По разным замерам (например, этому и этому), в зависимости от кода и оптимизации, это дает от 5% до 30% просадки производительности. Все очень зависит от вашего кода. Если у вас просто системные вызовы и работа с сетью, возможно, ничего не изменится для вас с -fno-strict-aliasing. Но просто ее писать при сборке вашего проекта не совсем правильно.
Правильнее включить предупреждение компилятора (GCC умеет предупреждать, когда нарушается strict-aliasing) и исправить в этом месте нарушение strict-aliasing. Как правило, это нарушение происходит, когда вы используете reinterpret_cast для двух несвязанных друг с другом типов.
Вместо reinterpret_cast лучше использовать memcopy или memmove. Компиляторы GCC умеют их оптимизировать. Просадки производительности в том месте, где вы делаете memcpy вместо reinterpret_cast, быть не должно.
От лютой теории переходим к советам, которыми можно пользоваться в повседневной практике.
Советы на каждый день
Скорее всего, вы все это знаете, и, скорее всего, не используете.
Пример #1, vector
Ниже пример функции foo, в которой создается вектор от shared_ptr. Мы знаем, shared_ptr — ровно тысяча. Они вставляются в вектор, и он возвращается.
auto foo() {
std::vector< std::shared_ptr<int> > res;
for (unsigned i = 0; i < 1000; ++i)
res.push_back(
std::shared_ptr<int>(new int)
);
return res;
}
Первый недочет: если мы знаем, сколько элементов будет хранить наш вектор, стоит вызвать res. reserve(1000). Это заранее проаллоцирует нужное количество памяти, и вектор при вставке в него не будет пытаться угадать, сколько памяти нужно. Без reserve в C++11 и раньше вектор сначала примет значение под 2 элемента, потом под 4 элемента, 8, 16 и т. д. Все это время при изменении размера он будет вызывать new, delete, копирование либо move вашего типа данных, что медленно.
Если же вызвать res. reserve(1000), то вектор точно знает, что это 1000 элементов, никаких дополнительных move, new, delete не будет.
Начиная с C++14 компиляторам разрешено оптимизировать вызовы new. Некоторые компиляторы умеют это делать, но им должно повезти — не во всех случаях это получается. Если вы хотите быть уверены, что компилятор сгенерирует оптимальный код, лучше вставить reserve — хуже не будет.
Другое проблемное место в этом примере компилятор соптимизировать не сможет. Это вызов std::shared_ptr<int>. В этой строчке происходит две динамические аллокации:
- Первая — new int.
- Вторая скрыта внутри конструктора shared_ptr. Ему нужен счетчик ссылок, который он динамически аллоцирует где-то в куче.
Причем в памяти они находятся в разных местах. Если ваше приложение не использует weak pointers, или использует их не сильно, вместо строчки std::shared_ptr<int>(new int) имеет смысл написатьstd::make_shared<int>().
Make_shared сразу проаллоцирует кусок памяти, где может хранить и int, и счетчик ссылок. За счет того, что эти две переменные будут находиться рядом, это более кеш-дружелюбно. Работа с shared_ptr станет чуть быстрее, динамических аллокаций будет не две, а одна.
Итого, код в первом примере мы ускорили чуть более, чем в два раза,просто добавив reserve и заменив конструктор shared_ptr на make_shared.
Пример #2, for (auto v: data)
auto foo() {
std::vector<std::string> data = get_data();
// ...
for (auto v: data)
res. insert(
v
);
return res;
}
Код в примере, представленном выше, ужасен. Давайте его улучшать постепенно, причем, скорее всего, не с того места, которое вы заметили.
V здесь копия элемента из вектора. За пределами цикла, и после итераций цикла она нам особо не нужна. Мы можем сказать компилятору, что переменная v больше не используется, заменив v на std::move(v), превратить ее в rvalue, и тогда вставка в результирующий контейнер res произойдет по rvalue ссылке. Ресурсы из v будут просто перекинуты внутрь контейнера, что быстрее.
Массив vector data больше никак не используется, все, что в нем содержится, будет уничтожено при выходе из функции. Вместо того, чтобы копировать v, мы можем написать for (auto&& v: data), т. е. сделать ссылку на v (&& — здесь это тоже ссылка).
В итоге получится следующее: v — ссылка на элемент внутри data. Когда мы к этой ссылке применим std::move, ресурс заберется уже из вектора data — прямо из вектора строка перетянется внутрь контейнера res. Никаких динамических аллокаций в итоге не будет. По сравнению с изначальным кодом стало в 100500 раз быстрее.
Пример #3, vector
auto foo() {
std::vector<std::string> data = get_data();
// ...
std::string res = data.back();
data.pop_back();
// ...
return res;
}
Ситуация, как в примере выше, возникает чаще — то же самое, но из вектора мы запоминаем последний элемент, а потом этот последний элемент извлекаем.
Также можно соптимизировать: мы говорим std::string res = std::move(data. back()). После этого в res — значение последнего элемента (мы перетащили ресурсы из вектора в переменную res). Теперь back внутри вектора — это пустая строка, data.pop_back() просто изменит одну из внутренних переменных вектора. Никаких динамических аллокаций, никаких вызовов delete — все быстрее.
Пример #4, глобальные константы
В парсерах и протоколах зачастую есть массивы заранее известных строк. Люди часто пишут их так:
#include <vector>
#include <string>
static const std::vector<std::string> CONSTANTS = {
"Hello",
"Word",
"!"
};
Кажется, что это лишь немного не оптимально, но, в принципе, не так страшно. Это произойдет один раз при запуске вашей программы либо при подгрузке DLL.
Но когда проект очень большой, то в разных его частях может накопиться большое количество таких кусков кода — 10, 100, 1000. Инициализация переменной CONSTANTS происходит при запуске программы либо при подгрузке динамической библиотеки. В этот момент этот однопоточный код будет вызывать new, аллокации, инициализировать вектор строк и это может замедлить старт вашей программы либо подгрузку динамической библиотеки.
Для тех, кто пишет realtime приложения и приложения, которые должны быстро рестартовать, если они упали, это может быть критично. Если у вас тысячи и миллионы таких объектов, это замедлит старт программы.
Если вам массив констант нужен, и вы обращаетесь к нему только по индексу или используете его только в range-based for, вы можете заменить вектор на обычный массив. То есть вместо std::vector<std::string> CONSTANTS можно написать std::string_viewCONSTANTS[].
В итоге старт вашего приложения не будет делать дополнительных операций, вызывать new, дополнительно фрагментировать память.
Если вам нужна строгая гарантия, что это выполнится еще до того, как ваша программа запустится, вы можете
static const заменить на constexpr. Это будет обязывать ваш компилятор выполнить этот кусок кода до рантайма.Пример #5, наследование
// base. hpp
struct base {
// ...
virtual void act() = 0;
virtual ~base(){}
};
Выше базовый класс base, в нем метод act —ничего интересного. Интересно, когда мы от этого base наследуемся. Представьте себе, что вы разработчик в компании и вам сказали разобраться в чужом коде, причем вы видите только то, что идет ниже.
// something. cpp
struct some_implementation: base {
// ...
void act() { /* ... */ }
};
Вы видите только это, вы еще не заглядывали в описание base и вас интересует, что это за метод act, объявлен ли он в базовом классе, перегружаем ли мы его, и вообще, что здесь происходит.
Вы можете сделать код более читабельным, просто добавив слово override:
// something. cpp
struct some_implementation: base {
// ...
void act() override { /* ... */ } // <======
};
Он будет не только более читабельный, но и более безопасный. Новый человек, когда будет читать ваш код, увидит override и подумает: «Ага, значит, этот метод объявлен в базовом классе, мы его перегружаем, все в порядке».
Придет новый человек и будет рефакторить базовый класс, поменяет там сигнатуру метода act, добавит туда integer и на этапе компиляции словит ошибку, что в классе-наследнике мы пытаемся заоверрайдить класс, который уже не объявлен в базовом, которого нет.
В итоге он не поломает ваш код. Без override все скомпилируется, как-то будет работать, но будет ошибка на рантайме. На ее отлавливание может уйти много времени. С override сломается на компайлтайме. Человек, который будет делать рефакторинг, это заметит и поправит и здесь метод act.
Еще можно добавить final в первую строку:
struct some_implementation final: base. Это значит, что этот класс финальный, больше от него никто не наследуется. Нам от этого не очень жарко и не очень холодно, но от этого веселее компилятору.Компилятор видит, что класс final. Когда он видит some_implementation и переменную этого класса, и у этой переменной вызывается act, компилятор понимает, что от этого класса больше никто не наследуется, и в нем есть act. Он будет вызывать act без прохода по виртуальным таблицам, не будет различных динамических вещей — будет вызов act, как будто он не виртуальный.
Можно еще чуть-чуть улучшить, запихнув все в анонимный namespace:
// something. cpp
namespace { // <======
struct some_implementation final: base {
// ...
void act() override { /* ... */ }
};
} // anonymous namespace</strong>
Анонимный namespace — это как бы static на стероидах. Можно объявить переменную или функцию статиком, тогда она не будет видна наружу. Все, что вы объявите внутри анонимного пространства имен, будет видно только в этой единице трансляции.
Это хорошо тем, что развязывает руки оптимизатору. Он может делать больше оптимизаций, основываясь на том, что этот класс больше снаружи никто не использует. Оптимизатор также может подумать, что раз этот класс снаружи никто не использует, то его не надо экспортировать, что увеличит скорость загрузки и линковки приложения на рантайме.
Например, в OpenOffice была проблема, что этап динамической загрузки библиотек и линкер, который соединял все зависимости друг с другом, занимали 10 секунд, потому что много символов торчало наружу. Если использовать анонимный namespace, эта проблема станет меньше.
Пример #5, move constructors
Ниже move constructors для класса my_data_struct. В нем только вектор data.
class my_data_struct {
std::vector<int> data_;
public:
// ...
my_data_struct(my_data_struct&& other)
:data_(other.data_)
{}
};
Только move забыли. И еще noexcept. Давайте перепишем:
class my_data_struct {
std::vector<int> data_;
public:
// ...
my_data_struct(my_data_struct&& other) noexcept // <======
:data_(std::move(other.data_))
{}
};
Ряд стандартных контейнеров, например, vector, делают сложные подсчеты на этапе компиляции на основе того, помечены ли move-конструкторы как noexcept или нет. Если ваши move-конструкторы не помечены как noexcept, вектор может дополнительно аллоцировать память, когда он будет расширяться, и копировать элементы, вместо того, чтобы их перемещать. Это безобразие, потому что очень медленно.
Чтобы было быстрее, добавляем noexcept.
Эта запись не нравится большинству людей. Здесь непонятно, что написано, и нужно знать:
- как устроен std::vector;
- кидает ли он exception при move-конструировании;
- будет ли он кидать exception, если туда подставить необычный аллокатор;
- можно ли этот move-конструктор пометить noexcept;
- обзательно ли его нужно помечать noexcept.
Куча каких-то деталей, которые нам не нужны.
Надо все лишь написать вот так и все это станет заботой компилятора:
class my_data_struct {
std::vector<int> data_;
public:
// ...
my_data_struct(my_data_struct&& ) = default; // <======
};
Теперь компилятор сам расставит noexcept, constexpr, если сможет. Код из стандартной библиотеки будет работать быстрее — вам легче.
Caching divs
Хочу рассказать об одной штуке, на которую я недавно натолкнулся, и которая меня удивила.
// .h
extern const double fractions[256];
// .cpp
const double fractions[256] = { 1.0 / i, ... };
Люди закешировали деление единицы на число. Они создали extern массив на 256 элементов, в котором запомнили:
- первое число — это 1/0 (сделали 0).
- второе число по индексу 1 — это 1/1.
- число по индексу 100 — это 1/100 и т. д.
Далее работают с этим массивом везде, где нужна часть от 1.
Как вы думаете, так будет быстрее или медленнее? Давайте выясним.
Залезаем в талмуды, где описано, сколько тактов занимают инструкции, и обнаруживаем, что доступ к элементу массива, который находится в L1 кеше, занимает 5 тактов, а деление — 22-29 тактов. Итого такое кеширование может быть в 2-4 раза быстрее, но…
Недостатки cashing divs:
1. Оптимизатор не видит значения
- Нет возможности оптимизировать ближайшие инструкции. Массив объявлен в другой единице трансляции. Если у вас нет Link-time -оптимизации, или link-time-optimizer недостаточно продвинутый, он не будет видеть значения и не сможет оптимизировать, основываясь на значениях. Если у вас будет обращение к 1/100, а потом умножение на 100, то, если бы оптимизатор видел значение, сразу получилось бы 1 (плюс-минус). Но если оптимизатор не видит значение, он не сможет это соптимизировать и умножение на 100 останется.
- Нет возможности использовать этот массив в constexpr выражениях, шаблонах.
- Другая проблема — aliasing. Ссылка на double может указывать на ту же ячейку памяти, как в примере с -fno-strict-aliasing при изменении этого double компилятор будет перечитывать значение из памяти для этой переменной.
Это серьезное негативное влияние на производительность.
При этом компилятор даже не поверит вам, если вы везде напишите const, потому что он не оптимизирует, основываясь на const. Если вы где-то написали const, компилятор проигнорирует это, потому что где-то в другом месте вы могли написать const_cast.
2. Мы потратили кучу времени на обсуждение этого...
То, что мы потратили кучу времени на его обсуждение, тоже плохо в этом примере. Когда вы увидите его в чужом коде, вы тоже потратите кучу времени, чтобы разобраться, что это за безобразие.
3. Мы потратили 1Kb L1 кеша из 16/32Kb
Люди, которые разрабатывают компиляторы, пишут книги на эту тему и защищают сложные теории, говорят, что в современном мире производительность системы ограничена не скоростью процессора, а зачастую работой с памятью:
«В то время, как традиционно компиляторы уделяли большее внимание оптимизации работы процессора, сегодня больший упор следует делать на более эффективное использование иерархии памяти».
Ахо, Сети, Ульман. Компиляторы. Принципы, технологии, инструменты. 2ed.2008
Мы потратили 1Kb кеша 1-го уровня на то, чтобы сохранить массив, и другие полезные данные теперь туда не поместятся.
Разработчик стандартной библиотеки C под Linux Ульрих Дреппер написал труд «What Every Programmer Should Know About Memory», то есть о том, что каждый программист должен знать о памяти. В нем намешана серьезная теория и физика, но есть замечательный простой пример важности кеша. На куске кода с переумножением матриц, не меняя практически алгоритм и ассемблерные инструкции, Ульрих Дреппер ускорил производительность в 10 раз просто за счет более эффективной работы с кешом данных.
Кеш данных очень важен. Не надо туда писать то, чем вы редко
пользуетесь.
Станет ли быстрее с таким кешированием единиц или нет — непонятно:
- Если у вас критически важный кусок памяти, где вы часто делаете эти операции, где их особо нельзя соптимизировать — да, может стать лучше.
- Если у вас обобщенный код, где вы много работаете с другими данными, и это одно-единственное вычисление — вы тратите лишний кеш. Скорее всего, станет хуже.
Но люди написали кучу кода, а мы потратили кучу времени на его разбор. Когда вы его встретите в чужом продакшн-коде, вы тоже потратите кучу времени на разбор, ваша производительность упадет. Работодатель будет недоволен.
Мы уже поговорили о «вредном», перейдем к хорошему.
Идеальный велосипед
Как написать свой идеальный велосипед, свою идеальную программу, я вам не скажу. На это есть куча книг, часть из них правильная, часть — не очень. Но, если вы написали программу, библиотеку, которая:
- кроссплатформенная;
- быстрая;
- полезная;
- функциональная
- пригодится большому количеству людей,
добро пожаловать в рабочую группу РГ21, мы:
- Поможем с формальностями.
- Поможем с принятием в Boost.
- Поможем с написанием proposal.
- Защитим ваши интересы на международном заседнии при ISO, передадим отзывы на ваше предложение.
С первого раза сделать proposal не просто, потому что есть специальные термины, которых надо остерегаться, и определенные формальности, которые надо соблюдать. Если вы просто напишете proposal и отправите его в Комитет, скорее всего, дальше ничего не произойдет, если вы (или доверенный человек) не прибудете в Комитет и не защитите вашу идею перед международным собранием. Приходит много предложений, и в первую очередь приоритет отдается тем, которые лично представляют и защищают.
Идеи в разработке РГ21:
- P0539R0: wide_int by Игорь Клеванец, чтобы можно было писать int256, int512, int4000000;
- P0275R1: Dynamic library load;
- ConcurrentHashMap by Сергей Мурылев, Антон Малахов — пока очень ранний этап;
- Constexpr: «D0202R2: Constexpr algorithm», std::array — добавление везде, где только можно;
- Улучшение поддержки динамических библиотек в стандартной библиотеке (?dlsym?);
- Stacktrace в стандартной библиотеке, чтобы можно было иметь класс Stacktrace, который в поток можно вывести и посмотреть Stacktrace, например, что происходило до этого, почему мы здесь упали.
- Множество мелочей, которые делают все в ISO WG21 — это исправление мелких недочетов стандарта, стенографирование заседаний и куча других дел.
Заходите на сайт рабочей группы https://stdcpp.ru/, там можно предложить свою идею, посмотреть, что предлагают другие, а самые интересные предложения мы обсудим вместе.
Узнать о других докладах Антона, посмотреть его презентации, публикации и множество другой полезной информации можно здесь — http://apolukhin.github.io/
Эта статья — расшифровка одного из лучших докладов наших друзей C++ Russia 2017, ближайшая их конференция в этом году пройдет уже в апреле с 19 по 21 число.
Открывать конференцию в этом году будет Jon Kalb, разработчик с 25-летним стажем
В течении этого времени успел поработать в Amazon, Microsoft, Netscape,
Yahoo и других компаниях. Jon — организатор конференции CppCon. Автор книги
C++ Today: The Beast is Back.
А мы пока активно работаем над программой фестиваля конференций Российские интернет-технологии (РИТ++), до 9 апреля еще можно успеть подать заявку на доклад, и выходим на финишную прямую. Обещаем, что серверный блок будет представлен очень хорошо, хотя и про другие можно сказать то же самое.
Antervis
хм. А рассматривались ли варианты сделать layout строки с битовым флагом?
antoshkka
Да, в Boost как раз так и сделано
Antervis
а в реализациях STL? И, если нет, почему?
antoshkka
В реализации стандартной библиотеки может быть любая имплементация. Например GCC предпочитает жертвовать несколькими символами, но держать валидный указатель — эту убирет if на каждую операцию.
encyclopedist
В этом ответе на SO есть обзор реализаций в стандартных библиотеках https://stackoverflow.com/a/28003328/4451432
darkAlert
Спасибо за статью, обожаю плюсы.
st0ke
А не может ли кто-нибудь проявить на это свет? Я конечно, рад что можно сказать = default мув конструктору, но не всегда же они дефолтные.
У нас в проекте не принято расставлять noexcept, только если для самих-себя, т.е. в теле метода точно есть catch всего или ему вылетать неоткуда и использующему надо точно это знать. Но ситуация с вектором всегда напрягала.
Действительно ли noexcept делает что-то полезное? А если исключение все таки вылетит от туда?
Antervis
std::vector и прочие контейнеры на этапе компиляции проверяют, является ли класс is_noexcept_(movable/copyable/constructible/...) и в ряде случаев используют разный код для noexcept и не-noexcept случаев, чтобы гарантировать корректность состояния контейнера при возможном исключении, но использовать более быстрый вариант если исключение невозможно. Самый простой пример — std::vector::push_back() для пустого вектора.
если внутри noexcept функции возникает необработанное исключение, вызывается std::terminate. Т.е. не вылетит
st0ke
Скорректирую вопрос. Если явно не поменить, что noexcept, и не использовать мув-конструктор по умолчанию, то всегда будет выбираться noexcept вариант (т.е. в случае вектора — медленное копирование)? Правило жесткое на уровне языка или есть маневр для компилятора, что он сам вычислит, что исключений не будет?
Antervis
Результат noexcept(...) опирается на гарантии языка. Нет гарантий — будет подставлена ветка с исключениями, которую дальше компилятор может оптимизировать в силу собственного разумения. Но даже если компилятор и умеет сложные оптимизации (например, выкинуть new+copy+delete) ему может банально не хватить контекстуальной информации.
Arech
Ой какие знакомые грабельки)
Остаётся только со всем согласиться. И ещё предложить добавить трик, учитывающий проблему ссылок и strict-aliasing: если так сложилось, что в performance critical код приходит переменная (особенно POD) по ссылке, то имеет смысл сделать временную служебную переменную по значению, в которую сразу загрузить то, что было по ссылке, и использовать её. Тогда мы обезопасим себя от бесконечных загрузок значения из памяти через ссылку. Наблюдал в таких условиях десятикратные приросты скорости.
Не спроста стараются передавать POD переменные по значению, но во первых, бывает legacy, а во вторых, — тип может быть под шаблоном, который не всегда развернётся в POD.
tretyakovmax
Еще одна причина — чтобы точно понимать как это работает. Особенно если функционал касается денег.
antoshkka
Это работает с точностью до наоборот: количество ошибок в ПО, работающем с деньгами, на несколько порядков больше чем в любом другом проекте.
Если не верите — сделайте не долларовый перевод из небольшого европейского банка в небольшой российский. У вас будут неплохие шансы натолкнуться на «неподдерживаемая кодировка», «получены не все поля, необходимые дле перевода» и т.п.
QtRoS
Кодировка в C++ это отдельная беда. Очень приятно, что в современных (без обид, господа ярые сторонники C++) языках эту проблему решают в начале дизайна языка.
deviant_9
Кодировка (точнее, проблема зоопарка кодировок) беда прежде всего винды. В цивилизованном мире просто используется UTF-8.
khim
Современные — это какие? Пока что худшее, что я видел — это Python3. C++ отдыхает.
firk
Многоядерные процы и hyperthreading, которые упоминались в связи с этим, на самом деле тут не особо при чём. Хотя они и увеличивают шансы напороться на race condition по сравнению с одноядерными, но не создают их там, где их не было — многозадачные ОС вполне прозрачно организуют многопоточность (и все её проблемы — тоже) вне зависимости от количества ядер.
antoshkka
Атомарная инструкция выполняется на процессоре, ОС о ней ничего не знает.
Одновременно может сработать только одна rmw атомарная инструкция, остальные должны будут «попытаться еще раз, позднее».
Viacheslav01
Видел я адскую реализацию атомика от микрософта, замкнутую на системный мьютекс. По разному бывает.
Antervis
это fallback implementation для типов, размер которых превышает поддерживаемый атомарными операциями.
firk
Где вы там атомарную инструкцию увидели? Или вы обсуждаете какой-то другой код, не тот что в статье?
antoshkka
ReeseE
А вот вы мне объясните такую вещь. Когда это у нас std::string стал mt-safe? И если он не mt-safe, то каким образом он у вас окажется в многопоточном контексте сам по себе? На каком основании вы требуете mt-safe от COW-строки?
khim
На основании того, что иначе многопоточные программы на C++ писать невозможно. GCC 4.x так делает, например.
ReeseE
Точно так же, как и с дефолтным std::string. Тут можно пытаться ехать в сторону «а как нам пошарить две одинаковые строки между тредами», но это так же не является проблемой. Решается одним методом, который делает реальную копию.
khim
Если на большинстве компиляторов (где нет COW) это работает без дополнительных методов, то ваш COW нужно закрутить так, чтобы он тоже работал, извините.
antoshkka
Есть отличный коментарий с ютуба от Konstantin Akimov:
ReeseE
Я уже ответил на это выше. Ничего не мешает сделать сделать метод copy для строки.
Тут и не нужны никакие кишки. Вызов clone/copy не является кишками. Шарить «cow-копии» строки между тредами нельзя, так же как и ссылки, так же как и мувить из другого треда и прочее.
olegator99
А как реализовать деструктор для COW строк без atomic ref counter?
(при условии, что наша реализации должна соответствовать стандарту C++, которая не запрещает передавать копии строки в другие потоки)
ReeseE
А зачем вы пытаетесь придумывать какие-то новый условия? Никто не сравнивал реализацию std::string с COW и без COW. Сравнивали COW-велосипед, а теперь вы пытаетесь превратить COW-велосипед в «std::string с COW». Как так получилось?
COW-велосипед не должно интересовать то, какая там реализация должна быть в стандарте. Особенно в контексте того, что у COW совершенно другая терминология и семантика.
olegator99
На мой вкус, если называешь свой велосипед именем стандартного контейнера, то он должен вести себя точно так же, как стандартный контейнер. Иначе, это будет мина замедленного действия, на которую с большой вероятностью, кто ни-буть наступит.
Например, если последовать вашему совету — убрать atomic rc из string, который рассматривается в статье, то код:
Будет гарантированно рейсить в момент освобождения памяти, в которой лежит массив байтов "abc".
Что бы этого избежать, прийдется постоянно держать в голове, что в проекте своя реализация string, копии которого нельзя передавать в потоки.
Согласитесь, не плохая подстава для новых людей на проекте.
ReeseE
С каких пор какой-то стандарт приватизировал имя string? Оно было ещё тогда, когда этого стандарта в проекте не было, как и С++.
Это иначе и нужно писать в причинах, а не всё остальное. Вот и напишите его, а всё остальное удалите. Раз вы не можете вести дискуссию в рамках прежних тезисов и постоянно пытаетесь их поменять.
Чтобы этого избежать — постоянно надо держать в голове, что просто замувить что-то нельзя. Дальше что? Я что-то не вижу от вас тех же рассуждений в адрес move?
Я обсуждаю тему в рамках тезисов определённых в статье. Хотите использовать другие тезисы — поменяйте их в статье.
olegator99
Попробую еще раз, с комментариями
И при чем тут move?
Естественно, move имеет право модифицировать исходный объект.
deviant_9
С тех самых пор, как появились потоки и само понятие потокобезопасности, как следствие — то есть с C++11. Все классы потокобезопасны (на базовом уровне), если не оговорено обратное; в частности, здесь применимо следующее правило:
(С++11/14, 17.6.5.9 Data race avoidance, абзац 7
C++17, 20.5.5.9 Data race avoidance, абзац 7)
В C++ нет понятия «COW-строка», есть просто «строка». COW — это один из возможных видов реализации, про которые пользователь ничего знать не обязан, ибо инкапсуляцию никто не отменял. Связанные с COW проблемы потокобезопасности лежат исключительно на разработчиках стандартной библиотеки.
ReeseE
К чему это написано и спащена цитата ниже? Спащенная цитат имеет отношение к нюансам реализации. «Если вы используете потоки в реализации — вы должны сами обеспечивать их безопасность», но из этого никак не следует то, что строка mt-safe.
Меня мало интересуют тезисы, которые рождаются постфактум. В рамках статьи говорилось о велосипедах, вот и говорите о них. Зачем вы постоянно придумываете новые истории?
Неверно. Вы можете мне попытаться показать, где в статье говорилось об cow-реализациях std::string. Да, там приводились в примеры cow-реализации std::string(старого), но ими дело не ограничивалось. std::string там приведён на правах истории, как объяснение того — почему раньше так было в std::string.
Да что говорить — там даже эта строка есть:
Т.е. автор явно не сравнивает std::string и std::string. Это следует и из множество других мест.
Осталось только понять — откуда вы взяли всю эти историю со стандартной библиотекой? Сами придумали? А какое отношение ваши придумки имеют к теме?
Автор дал определение «cow-велосипед», который никаким образом не является стандартной библиотекой и не является имплементацией std::string.
deviant_9
К вашему вопросу «Когда это у нас std::string стал mt-safe?».
Цитата из стандарта C++.
Неверно. Перевожу на русский, раз такие трудности:
«Реализации могут расшаривать их собственные внутренние объекты между потоками, если эти объекты невидимы для пользователей и защищены от гонок.»
«Реализация» — это компилятор+стандартная библиотека, если что. В частности, реализация std::string.
Потокобезопасность std::string (в том смысле, что два потока могут параллельно работать с двумя разными объектами std::string, пусть даже полученными из одного объекта std::string присваиванием или конструктором копии) следует из всей совокупности требований раздела «Data race avoidance», в частности:
Я отвечаю на ваш комментарий про якобы потоконебезопасный std::string, а не на статью.
Вы написали два вопроса про std::string и один — про COW-строки, таким образом, словно это три вопроса на одну и ту же тему.
firk
Ваш процитированный код расположен в статье после заявления о том, что виноваты multi-core процессоры, в качестве исправления той проблемы. Так что на момент описания проблемы этот код ещё не используется. Я в своём первом комментарии как раз писал о том, что этот код нужен вне зависимости от того, сколько ядер в проце, потому как без него может случиться (хоть и с меньшей вероятностью) race и на одном ядре с разделением времени между потоками.
Впрочем, сейчас посмотрел внимательнее — появилась ещё одна претензия к статье — ибо даже этот код от race может не спасти. Посмотрите на деструктор ~string ещё раз. Там сначала делается декремент, а потом переменная сравнивается с нулём (и atomic тут не защищает). Между этим декрементом и сравнением теоретически может произойти переключение на другой поток, который сделает ещё один декремент. После чего либо оба потока увидеть use_count==0 с сделают double-delete, либо второй из этих потоков сделает UB обращением к impl->use_count уже освобождённого соседним потоком impl. Возможно, компилятор оптимизирует декремент + сравнение в одну операцию (и тогда скомпилированный код станет хорошим даже без atomic<>), но в любом случае делать он этого не обязан, а в зависимости от деталей реализации класса atomic<> может оказаться что и вообще не имеет права.
Хотя наверно эта проблема обходится через if(!--impl->use_count) — тут явно указано что надо брать именно результат декремента, а не содержимое переменной после него.
antoshkka
Извиняюсь, код должен выглядеть как
firk
В C для указателей для этого есть restrict — что бы явно указать, что не надо подозревать два указателя пересекающимися (причём это работает и если они одинакового типа). На локальные переменные эти подозрения и так и так не распространяются (если только вы где-то не применили к ним оператор &) а ссылок там нет. Не в курсе касательно C++ но возможно там есть какой-нить restrict для ссылок — было бы очень хорошо, потому как strict-aliasing реально можно много чего испортить.
deviant_9
Стандартного restrict-а нет, но есть как расширение, например, в gcc (__restrict__/__restrict).
Если -fstrict-aliasing что-то «испортил», код в любом случае надо переписывать. К тому же, он включается по умолчанию уже на -O2.
DaylightIsBurning
Viacheslav01
Как это реализуется технически? Не могу себе представить другой реализации кроме как обмен ссылок, но тогда контейнеры должны хранить указатели, а не сами объекты, что приводит к замедлению чтения данных из контейнера.
firk
Поля объекта string побайтно (примерно так) копируются, выделенная в куче память для данных — остаётся на месте (сама строка в общем случае хранится не в объекте string а по указателю из него). Если компилятор умный то он может и копирование полей объекта местами соптимизировать.
deviant_9
Оптимизирует. Пример (присваивание *ptr = 9; может изменить x2, но не x1): godbolt.org/g/QPvwup С массивами получается аналогично.
Модификация константного объекта (посредством const_cast или другими путями) — неопределённое поведение, компилятор всегда имеет право полагать, что такого не происходит.
Другое дело, если нам передали параметр типа const T& или const T* и он ссылается на на самом деле неконстантный объект.
humbug
Либо всё будет хорошо. Либо прилетят назальные демоны.
Ну серьезно, сколько можно с серьезным лицом описывать последствия UB, если они непредсказуемы?
Overlordff
Тем не менее, вероятность конкретных последствий на распространенных платформах с распространенными компиляторами выше остальных. О вероятности уже рассуждать можно.
dev96
Неплохо было бы написать вам книгу по типу «Эффективный современный С++», где были бы наиболее актуальные советы, включая C++17 :)
jackfrostfromcuba
Закапывайте уже это разложившийся труп ЦЭПЛУСПЛУС, хватит его насиловать
ReeseE
Нельзя просто так взять и заменить std::string на std::string_view, ведь в очень многих кейсах нужна c_str(). Да, по факту там будет си-строка, но завязываться на это мы не можем.
Это касается и первого случая.
olegator99
Жаль, что string_view ничего не знает про время жизни объекта, на который ссылается. С одной стороны, это мощный и удобный инструмент, для тех кто понимает, что делает.
А с другой стороны string_view приносит еще сто-пятьсот способов выстрелить себе в ногу, особенно для новичков.
ReeseE
Не хочу показаться грубым, но
Вы не понимаете талмуд и вообще всю эту тему с тактами:
Во-первых, 2раза ещё можно как-то объяснил отсылкой к l2, но 22-29 — это более пяти раз.
Во-вторых. Вы показываете не фпешный див для 32битных чисел в контексте даблов.
Третье — вы совсем не понимаете этих цифр. На самом деле там не 5тактов, чтение пайплайновое, дак и к тому же параллельное. Там от 0.5тактов, что уже в 50раз. На самом деле там разница до 100раз, ведь деление не обладает этими свойствами. Именно поэтому и оптимизируют деление.
Четвёртое. Это скорее всего не «Caching divs» — это n / m (~)== n * (1 / m) — поэтому аргумент уровня:
Это не проблема кода. Вы не понимаете контекста, и естественно, что вы не поймёте ни код, ни причин его написания. И это исключительно ваша проблема, ведь аналогичное будет с любым другим кодом. С любой другой оптимизацией.
Это оптимизация деления, которая не имеет смысла, если мы итак будет использовать деление. Поэтому, это:
Так же не работает, ведь эта оптимизация стоит куда дороже чем всё остальное. К тому же, подобные примеры не имеют смысла и притянуты за уши.
К тому же, плавучка неассоциативна, а значит просто так компилятор там ничего менять не может, кроме базовых случаев. Только fm, но результаты могут быть непредсказуемыми.
Оба тезиса не имеют никакого отношения к Caching divs, а имеют отношение к конкретной реализации. Ничего не мешает таблицу вынести в хедер со статик, либо сделать её constexpr.
Если оно будет алиасится, то в 95% случаев — с другими даблами, и уже только потом с чем-то другим. Никакой strict-aliasing этому не поможет. К тому же. В случае со static, либо constexpr — никакой из этих проблем не будет.
Зачастую эти люди имеют мало отношения к практики, но дело даже не в этом. Ссылка на это ничего не даёт, ведь эти тезисы бессмысленны. Это некие общие рассуждения, которые к данному контексту отношения не имеют.
Естественно, что в тех кейсах, которые завязаны на летенси памяти — всё будет упираться в кэш. Это уровень КО. И что самое главное — подобные рассуждения существуют только потому, что интел сделал alu с летенси 1 такт. Как только дело касается плавучки, где такой халявы нет — все эти истории работают слабо.
И что самое важное. l1d — это уровень именно «скорости процессора», как и все операция связанные с ним — завязаны на процессоре, на инструкциях и работе с ними.
Причины просты — если этот код не является горячим, то его в кэше ИТАК НЕ БУДЕТ, а если он является горячим, то он ГОРЯЧИЙ, а значит от времени ЕГО исполнения ЗНАЧИТЕЛЬНО зависит время работы ПРОГРАММЫ в целом.
Полная глупость.
Абсолютно притянутый за уши пример. И это даже неважно, ведь этот пример ничего не показывает. Ведь точно так же это умножение можно переписать и получить ещё х10. К тому же — это именно уровень процессора, а не памяти. Просто некоторый обобщённый до уровня памяти пример.
Естественно, что важны любые ресурсы и оптимальное их использование даёт профит. Но из этого не следует «вычислительное время неважно». Она так же важно. И самое важное — тот-то в glibc весь код на асме. Не нужно ведь — там всякие строки и прочая работа с памятью. Ан нет.
Даже не знаю, что на это ответить. Это ведь базовые знания. Кэш это не просто тупой буфер — он обладает свойством вытеснять наименее используемые данные. Именно поэтому, если эта таблица используется мало — она будет читаться в кэш и тут же из него вытеснятся. Как и любая другая память. Она не читается вся сразу в память — читается лишь несколько соседних элементов.
Правильно, и вывод тут можно сделать один и единственный — не стоит смотреть и оценивать какой-то код не имея необходимого бекграунда. Можно всё перепутать и ничего не понять. Это свойство любого кода, а не только этого.
DaylightIsBurning
On x86 cache lines are usually 64 bytes. Если кешировать флоаты, к примеру, но выходит 16 элементов, что не так уж и мало.
ReeseE
Абсолютно неважно сколько их там выходит — из этого ровным счётом ничего не следует.
DaylightIsBurning
а если выходит 100?
ReeseE
Да хоть мильён — какая разница? Это свойство памяти — она не читается по 1/2/4/8 байт — она читается кешлайнами и любая память читается только через кэш(за исключением nt). Это не свойство это таблицы — это глобальное свойство, которое распространяется на все чтения в программе.
На любое чтение — процессор прочитает кешлайн. Если этот кешлайн далее не нужен — он вытеснится чтением другого кешлайна. И это, ровным счётом, ни на что не повлияет.
DaylightIsBurning
Вы написали:
Я написал, что поскольку кеш-линия — большая, то вытеснение, о котором Вы говорите не будет так уж хорошо работать.ReeseE
Это ни из чего не следует. По крайней мере я не вижу связи, но вы можете мне её показать. Внимательно слушаю.
DaylightIsBurning
Что бы работало вытеснение, нужно что бы те объекты, к которым нет обращения могли быть вымыты из кеша. Поскольку в реальности вытеснение идет на уровне линий, то достаточно что бы хоть один элемент из линии использовался, что бы заблокировать вытеснение всей линии. В результате эффективность вытеснения тем ниже, чем больше размер кеш линии по отношению к размеру элемента. Если размер кеш линии уже порядка размера всего кешируемого массива — вытеснение почти не работает. В результате может получится, что «несколько соседних элементов» — это практически весь кешируемый массив и есть. В случае с массивом на 100 флоатов (400 байт) и линией на 64 байта, при случайном доступе достаточно задействовать примерно 8-10 флоатов из 100 что бы исключить вытеснение и забить кеш.
ReeseE
Это не имеет смысла. Зачем вы пытаетесь общие вещи натянуть на конкретный случай? Общие вещи не относятся к данному случаю — ведь они на то и общие.
Неверно. Абсолютно неважен размер элемента — память считается не в элементах.
Работает.
Может, но из этого ничего не следует. Это явно не этот массив, да и даже если бы был этот — это ничего не меняет.
Неверно. Во-первых, как я уже говорил — это попытка натянут сову на глобус.
Во-вторых, это ничего не меняет, ведь будет вытеснятся тот кешлайн, в который было прочитано предыдущие значение. Описанное вами может случится только в том случае, если эти 8-10 элементов ГОРЯЧЕЕ ДРУГИХ данных, а значит — другие данные объективно менее важные. А то, что ненужно — то неважно. И есть ли ненужны данные в кэше, либо их нет — абсолютно неважно.
Повторю ещё раз. Тут есть два основных тезиса Первый общий и предпосылки к нему формулируются так «чтение какого угодно куска памяти — триггерит чтение куска данных шириной в кешлайн»", а далее — все вытекающие. Но а) этих вытекающих почти нет, б) они итак есть везде и эта «таблица» — не исключение.
Второй тезис «ненужные данные в кэше» — в кэше не может быть «Ненужных данных», даже если попутно с нужными кэш забьётся ненужными, то в любом случае — это данные нужнее всех остальных, ведь они читаются чаще.
Подобное может проявиться только в очень-очень редких случаях, когда у нас есть некий датасет, который тютелька в тютельку упирается в ширину кэша, при этом он настолько же горяч, как и данная таблица. Но даже тут есть проблемы, ведь у нас есть l2, который всё равно дешевле показанных 20+тактов.
Слишком притянуто за уши.
DaylightIsBurning
не будет. на след такте он снова понадобится.
Не исключение. Просто при расчёте того, на сколько кеширующая таблица зафлудит кеш нужно считать не среднее число используемых элементов в некий короткий промежуток времени (скажем ~100-1000 тактов), а среднее число используемых кеш линий. Вытеснение определяется не размером элемента (в байтах) и таблицы, а размером кеш-линии и распределением обращений по таблице. При таблице в 400 байт (100 флоатов) и 10 случайно распределенных релевантных (на промежутке в 100 тактов) элементов, на эти 100 тактов, будет забито 384 байта кеша, а не 40 байт. Выходит, что при 10% использовании таблицы кеш будет зафлужен на ~100% размера таблицы. И это вполне обычный сценарий использования таких таблиц. Я не беру самый неблагоприятный случай, когда достаточно что бы каждый 16й элемент был задействован. Я беру именно 10% случайно распределенных элементов. Конечно, могут быть и более благоприятные, но проблема именно в том, что столкнуться с неблагоприятным очень легко.
ReeseE
Вы писали про какую-то «эффективность вытеснения», которая очень слабо связана и с первым и со вторым и с третьим. И абсолютно неважно что там, элементы, размеры в байтах, отношения — это одно и то же, а точнее то, что не имеет никакого отношения к делу. Вернее имеет, но крайне опосредованное.
Во-первых, зачем вы мне об этом рассказываете, когда я сделал до вас? Я ведь не зря там сделал уточнение.
Второе — промежуток времени никого не интересует и ничего не значит. И вам уже объяснили почему.
Не будет.
Не будет.
Вы продолжаете повторять одно и то же, игнорирую то, о чём вам говорят. Но я повторю в сотый раз.
Абсолютно неважно то, сколько и чего вы там насчитали — это не имеет отношения к реальности. Для того, чтобы вытеснились не данные из таблицы, а левые данные — надо обеспечить то, чтобы эти данные были холоднее. А раз они холоднее — они не нужны, а значит все эти рассуждения не имеют смысла.
Если у нас есть горячие данные в кэше, то абсолютно неважно сколько вы там будите читать, хоть каждый 16элемент — занимать это будет ровно ОДИН кешлайн. Хоть там будь терабайт табилцы — это ничего не изменит.
И только тогда, когда ваши данные из таблице станут горячее других данных — в кеше будут оставаться данные из таблице, но в этом случае таблица станет узким местом, а раз таблица быстрее вычислений — таблица себя оправдает.
ErmIg
Хотелось бы сделать небольшое замечание, касательно быстрого деления на число. На самом деле кеширование результата операции целесообразно только для деление на небольшое число. Кроме того доступ к закешированным данным плохо векторизуется. Если деление настолько массовая операция, то наиболее оптимально будет ее выполнять на лету при помощи векторных инструкций. Нашел пример с умножением по модулю:
stackoverflow.com/questions/46790237/vectorization-of-modulo-multiplication/46790553#46790553
ReeseE
Это абсолютно неважно. Число может быть каким угодно — определяющим является их кол-во, а не то «большое» оно, либо нет.
Неверно. Можно хранить целые вектора, либо есть броадкаст. Да что там далеко ходить — по вашей ссылки есть пример:
__m128 _k = _mm_set1_ps(1.0f / p);
Это именно одно число с «броадкастом», ничего не мешает подставить сюда число из таблицы.
Никаких проблем нет, если нам нужно и умножать на последовательность чисел — она спокойно читается.
Таблица таблице рознь, но до — таблица не векторизуется и они почти полностью бесполезны при векторизации.
Этот пример никакого отношения к тому, о чём вы говорите — не имеет. Это оптимизация деления на констанату, которая вычисляется не «при помощи векторных инструкций», а банальным делением, а потом используется как константа при вычислениях.
Если у вас константа одна и её можно предрассчитать, то проще предрассчитать, но не всегда и не везде. К тому же — есть множество кейсов, где длинна предвычисление будет стоит дорого, неоправданно дорого.
В данном примере просто векторизуется операция int(float(d)/float(p))*p. Причём очень колхозно. И самое интересное — этот же пример вас опровергает. Это деление будет исполнятся значительную часть от самого цикла. 10-20+% и это лишь потому, что флоат-деление достаточно халявное. К тому же флоаты тут явно не подходят, ведь их точности на инт не хватит — нужны даблы. Там уже ситуация будет куда хуже.
К тому же, не стоит забывать, что данная реализация слишком кастыльная — там почти всё время тратится на касты. Будь это изначально флоаты/даблы — мы бы потеряли не 10-20%+, а все 100%+.
И нам бы пришлось выносить это из цикла, т.е. кэшировать вычисление.
ErmIg
Да пример не самый удачный. Тем не менее даже с учетом конвертации туда и обратно, fp деление будет быстрее, потому как векторизуемо.
ReeseE
Быстрее чего? Какое деление? Откуда оно взялось? О чём вы вообще говорите?
В вашем примере нет никакого деления, нет никакой векторизации. Вам об этом сообщили — вы всё перепутали. Вам нужно это осознать и сделать соответствующие выводы.
Ваш пример — это 1в1 то, что критиковал автор, а именно — кэширование 1/n, а после использование этого коэффициента для замены деления на умножения. При его вычисление НЕ ИСПОЛЬЗУЕТ НИКАКИХ " выполнять на лету при помощи векторных инструкций. ", вообще никаких векторных инструкций.
Никакого отношения ваш пример к векторизации деления не имеет. Повторюсь уже в 3-4раз.
ErmIg
Я не поленился и проверил скорость деления с применением закешированного значение и напрямую с использованием SSE:
У меня получилось, что второй вариант более чем вдвое быстрее (35 ms и 15 ms).
antoshkka
Так в этом и посыл: «Не делайте преждевременных оптимизаций».
Вы говорите, что бездумное выключение оптимизацией компилятора, вместо исправления ошибок, это ОК? Или вы спорите ради спора?
Разработчики оптимизаторов имеют мало отношения к оптимизациям? Я вам не верю.
######
Надо отметить, что вещи вы порой говорите правильные. НО их практически не видно из-за вашей агрессии и желания поспорить ради спора. Жаль, ведь можно было бы более продуктивно обсудить этот пример. Смотрите:
Вы: Out Of Order Execution увидит что доступ к памяти и заранее постарается подтянуть данные в кеш, зачастую сводя на нет простои
Я: Это не гарантия. Если этот код будет стоять в начале одной из веток, branch predictor мог бы сплоховать и мы получили бы простой в полной мере.
Вы: Вы взяли количество тактов для целочисленного деления, вместо деления double
Я: Это просто неудачное название для деления на слайде. Да и современные процессоры, деление делают достаточно быстро. Так FDIV на Ivy Bridge занимает 10-24 тактов
…
ReeseE
Зачем вы пытаетесь врать и дёргать фразы из контекста? Там написано то, что если убрать таблицу и заменить её на деление — это не будет иметь смысла и вам объяснили почему. У вас получится x * (1 / m), что попросту не имеет смысла.
В этом ваша проблемы — вы не понимает того, о чём пишите. Это касается всего, и бездумное пасты «тактов» и из таблицы, и обвинение кода в непонятности, который понятен всем, кто имел отношение к оптимизации вычислений.
Опять какое-то враньё. Где я говорил подобное? Покажите мне.
Мне не нужно верить. Есть факты, которые мною доказаны: а) вы не понимаете тему, б) вы не понимаете матчасть. Поэтому извините, но ваши рассуждения об оптимизациях, тактах, понятности кода — стоят ноль.
И самое важное — мы опять видим враньё. Вы выдернули какую-то фразу из контекста, в которой вообще не говорится об «Разработчики оптимизаторов».
Давайте я перечислю вам всё ваше враньё.
Первое — оптимизации оптимизациям рознь. Один вид оптимизаций требует совершенного другого понимания, нежели другой. Как бы вам попроще объяснить. Берём llvm, в котором( на уровне ир, т.е. почти все) почти все оптимизации являются обобщёнными, т.е. они никак не учитывают таргет. Да, частично и в каком-то виде они могут это делать, но это крохи. В этом их смысл, ведь таргетов много.
И все людям, которые разрабатывают эти обобщённые оптимизации нет смысла, и попросту невозможно понимать и знать какой-то таргет. Таргет — это уровень кодогена, а там какими-то оптимизациями еле пахнет.
Так же, есть просто примитивные оптимизации и таких 90%. Всякие реплейсы по паттерну — замена циклов копирования на мемсет, замена циклов подсчёта бит на popcount и прочее и прочее. Это всё так же не имеет никакого отношения к тому, о чём говорил я.
Враньё второе. Вы написали это, а после «Разработчики оптимизаторов». Зачем? Разработчик компилятора — это далеко не только разработчик оптимизатора, вернее в подавляющем большинстве случаев это не так.
В том то и дело, что пишут книги, защищают теории. Но совершенно на другие темы, и опять же — они не занимаются разработкой оптимизаций.
Это очередной пример того, как человек где-то услышал какую-то фразу и повторяет её везде. Зачем? Это ничего не стоит и ничего не значит. Это общие фразы, которые никакого отношения к конкретному случаю не имеют.
В конкретном случае мы можем почитать — во что и как у нас упирается производительность и для этого нам не нужны общие фразы. Вы не можете, вы не знаете, вы не понимаете — именно поэтому вы и кидаетесь общими фразами.
Вы мне не покажите «неправильно», в этом и проблема. Это не спор ради спора, не агрессия — это лишь ваши попытки свести дискуссию куда-то не туда.
Вы не можете обсуждать этот пример — вы некомпетентны. И вам это не нравиться. Вы хотите, чтобы я принял ваши попытки ехать в сторону общих враз и поверий — нет, этого не будет.
Вы не понимаете того, о чём говорите. Зачем вы мои слова выдаёте какой-то малограмотный бред?
Опять — вы не понимаете того, о чём говорите. Ну и тут прослеживается явная попытка съехать с темы. В рамках конкретного примера можно почитать — будет там гарантия, либо нет. И ваши общие фразы — ничего не стоят.
Нет, опять враньё. Вы не просто взяли не то, вы неправильно даже разделили 25+ на 5, не говоря уже о том, что там будет 4-5раз( в рамках вашей логики), но никак не 2-4. Т.е. тут проблема даже с банальной арифметикой.
Тут вы опять пытаетесь врать. Это не ваша основная проблема — ваша проблема( основная) в том, что вы пытаетесь кидаться какими-то цифрами, значения которых вы не понимаете. Зачем?
Вот опять мы видим очередную глупость. Никакие процессоры не делают никакое деление быстро — это невозможно. Второе, вы опять пытаетесь кидаться непонятными вам цифрами, хотя об этом я уже говорил выше.
И ладно, я даже не требую с вас понимания, но. Даже не понимания проблемы, любой, что хоть раз видел живот код — никогда не сошлётся на fdiv. Вывод? Вы даже кода не видели, но зачем вы куда-то лезете?
Но я вам сообщаю — fpu сдохло во времена core2, а значит все fdiv«ы тоже. Такие дела.
Хотя о чём это я, 10-24такта — это в 20-48раз медленнее чтения из l1d.
Разберитесь в теме перед тем, как о чём-то рассуждать. Да, никто тут вас не поймает и можно с умным видом нести откровенный бред. И меня всегда можно заминусовать, но. Это ничего не изменит. Если вы хотите действительно говорить полезные вещи — изучите тему, а если нет — продолжайте в том же духе. Шансы на изобличение крайне малы.
Я хотел разобрать и то, что вы там наговорили на тему форсинлайна, но мне стало лень. И до сих пор лень. На самом деле везде, где вы пытаетесь говорить о матчасти — выходит полный бред.
antoshkka
Прочитайте публикацию ещё раз, но внимательно. Вы додумываете факты которых в примере не было, приписываете мне отсебятину и оскорбляетесь на неё.
ReeseE
Опять враньё, опять ноль аргументации. Опять попытка врать в надежде, что публике будет лень читать мой подробный разбор. Мне достаточно спросить:
Где, покажите. Почему вы не показали ни одного примера?
И далее ответа не будет, как его не было и сейчас. Ведь никаких додумываний фактов там нет — это враньё. А вот я уже много раз вас поймал на этом самом додумывании, подмене тезисов, откровенном вранье, игнорировании и прочем. И я могу это показать, в отличии от вас.
Хорошо, возьмём пример, который будет понятен всем.
Это ответ на моё ответ на:
И вы тут можете заметить то, о чём говорил я. Человек пытается врать, т.е. вначале он говорил об одном, а потом «разрабатывают компиляторы» пропали и появились «Разработчики оптимизаторов».
И мало того, я даже на эти «Разработчики оптимизаторов» ответил, но что мы видим? Видим игнор и очередное враньё.
antoshkka
Ваш подробный разбор не стоит и выеденного яйца, потому что вы разбираете не пример из статьи, а что-то из своей головы. Откуда вы взяли «x * (1 / m)» мне не ведомо, почему вы вдруг считаете что мы на горячем пути — не понятно, из-за чего мы вдруг оказались в CPU bound примере — ????, почему на основе этих выдуманных фактов вы делаете какие-то выводы о компетентности — совсем не очевидно.
Давайте я разберу пример подробнее. Берём godbolt. Видим что код с делением превращается в
test2(unsigned int):mov edi, edi
vcvtsi2sd xmm0, xmm0, rdi
vmovsd xmm1, QWORD PTR .LC0[rip]
vdivsd xmm0, xmm1, xmm0
ret
Код с доступом к памяти превращается в
test1(unsigned int):mov edi, edi
vmovsd xmm0, QWORD PTR divs[0+rdi*8]
ret
Прогоняем через Intel Architecture Code Analyzer, видим что код с делением занимает 14 тактов, код с досупом к памяти — 0.5 тактов
Внезапно вспоминаем, что этот инструмент не принимает во внимание летенси кешей, смотрим на летенси.
Видим что в случае L2 доступа перимущество практически сходит на нет, в случае L3 или доступа к памяти — кеширование серьёзно проигрывает.
Данный вывод сходится с выводом из статьи «Станет ли быстрее с таким кешированием единиц или нет — непонятно:<и далее по тексту> может стать лучше<...>может ухудшиться». (Я вообще удивлён, что вы пытаетесь спорить с таким выводом!).
Возможно специалист вы и компетентный, но из разговора следует обратное.
olegator99
Спасибо, отличная статья.
В свое время искал реализацию std::vector, с SSO оптимизацией (по аналогии с std::string, хранящий N элементов внутри себя, без дополнительных аллоков на куче)
Не нашел, в итоге написали свой.
DaylightIsBurning
boost small_vector, llvm small_vector
olegator99
О, спасибо!
Про llvm small_vector не знал — посмотрю.
А boost ИМХО, все же жирноват, что бы из за нескольких полезных контейнеров тащить в зависимости десятки мегабайт либ, и усложнять процесс сборки...
DaylightIsBurning
можно не тащить весь буст, а скопировать только сам вектор.
olegator99
Согласен, мы именно так и поступили с intrusive_ptr
olegator99
UPD:
Посмотрел на boost small_vector — увы, тащит за собой много #include из буста.
И по использованию памяти не очень оптимальный:
sizeof (small_vector<int,4>) = 40 байт, а наша реализация обходится 20-тью, для аналогичного случая
DaylightIsBurning
_
dipsy
olegator99
Одно другому не мешает, а дополняет.
А так согласен, хороший процент покрытия тестами + регулярный прогон их в CI с ASAN и TSAN дает уверенность, что код внезапно не выстрелит себе в ногу на по проде...
Konstontin
Класс! Прочитал на одном дыхании.
perfhunter
Насчет FORCE_INLINE имеется некоторое лукавство.
1. Проблема с кэшом инструкций может возникнуть не от самого по себе инлайна, а когда один и тот же код инлайнится многократно. Ибо если функция не инлайнится, то ее код все равно попадает в кэш инструкций :)
2. Обычно FORCE_INLINE применяют в тех случаях, когда это буквально пара строчек, которые определять #define'ом вроде как уже некошерно, а возможности сделать intrinsic для компилятора нет. И в этих случаях FORCE_INLINE вполне оправдан. А если кто-то принудительно инлайнит функции на несколько десятков строчек кода, то он сам себе злобный Буратино.
Если уж тема инлайна и кэша инструкций была затронута, то можно было бы обратить внимание и на смежную проблему — когда кэш заполняется за счет кусков кода, которые потенциально не исполняются вообще или исполняются на slow path. В некоторых случаях компилятор может сам оптимизировать такие случаи, хороший пример — инициализация статических переменных, которую компилятор выносит за пределы тела функции. В общем же случае компилятор ничего не знает, насколько вероятно выполнение/невыполнение некоторого условия. С точки зрения процессора, пока код еще не выполнялся, действует static branch prediction, у которого, например, на Intel'е крайне простые правила — условный переход назад считается вероятным событием, условный переход вперед — маловероятным. В соответствии с этим префетчер будет подтягивать инсрукции в кэш. Поэтому во многих случаях является оправданным использование интринсиков типа GCC'шного __builtin_expect — те самые макросы likely и unlikely, которые многие так не любят. Эти макросы позволяют компилятору наиболее оптимально организовать код с точки зрения кэша инструкций и работы механизма предсказания переходов.
antoshkka
+1
В случае c 2) я говорил именно о неразумных применениях («весь проект вдоль и поперек»).
К несчастью, о всех интересных темах сразу рассказать не возможно из-за ограничений по времени. В дополнение к тому что вы сказали — некоторые компиляторы вытаскивают вероятность исполнения условия из наличия в одной из веток [[noreturn]] или throw. Ещё одна из забавных и неплохо работающих эвристик — «если if без else — то условие редко выполняется; если if с else — условие выполняется часто».