Comments 49
Спасибо!
Сейчас как раз в качестве обучения C++ переписываю рабочий Embedded проект для микроконтроллера с C на современный C++. Интересно почитать о сравнении массивов и о скорости работы.
На самом деле std::array -- это просто С массив с фиксированными во время компиляции типом и размером , к которому однако применимы с++ итераторы и который соответственно может быть использован в stdc++ functions вроде сортировки или поиска, boost и дальше до куда фантазии хватит.
задаёт наиболее вероятное значение целочисленного выражения expression, что может помочь процессору путём подсказок во время предсказания ветвлений (branch prediction)
Интринсики для указания вероятности ветвления к аппаратному предсказателю ветвлений никакого отношения не имеют. Как и написано в документации, на которую вы ссылаетесь, это влияет лишь на генерацию кода. В общем случае, компилятор ничего не знает об аппаратном предсказателе ветвлений, и манипулировать его состояниями не может (оставим в стороне вещи вроде сброса конвейера, это про другое).
Одним из аргументов против использования std::array может служить довод о том, что-де когда он передаётся в функции по ссылке, то при обращении к его элементам происходит дополнительная косвенность.
Косвенность у вас в бенчмарке исчезла из-за того, что вызываемая функция была встроена в место вызова (inlined). Думаю, будет легко показать, что при отсутствии встраивания косвенность не исчезает, значит примеры не эквивалентны.
Можно косвенно влиять на предсказатель. Это не точная наука, но кое на что можно полагаться. Например, что предсказатель считает дальние условные переходы менее вероятными (именно такой скорее всего будет переход на abort) и что условные ближние переходы назад более вероятны. Понятно, что предсказатель это непростая штука и есть много условий, в том числе история выполнения кода. Но можно немного на него влиять. Думаю, что автор это и имел ввиду под подсказками предсказателю.
Отпишу сначала про предсказатель, потом про косвенность в следующем комментарии.
Касательно подобных железных вещей практической экспертизой я похвастать не могу, конечно. Но. Если правильно понимаю, современные архитектуры не поддерживают инструкции, напрямую влияющие на предсказатель, в этом вы безоговорочно правы. Так же вы безоговорочно правы и касательно генерации кода - использование указанной интриники может привести к реорганизации кода. При этой реорганизации, например, инструкции двух ветвей условного оператора могут быть поменяны местами. Эта перестановка, в свою очередь, может повлиять на то, какую ветвь исполнения предсказатель выберет за наиболее вероятную.
Вы согласитесь с подобным описанием?
С описанием согласен, но акцент на предсказателе ветвлений тут лишний. Реорганизация ветвей может иметь большое влияние на производительность и в архитектурах вообще без предсказателя (например, в микроконтроллерах), где инструкции перехода сбрасывают конвейер и приостанавливают исполнение. Вашим интринсиком вы можете сказать компилятору, какая ветвь наименее вероятна, и она будет исполнятся после исполнения инструкции перехода (с возможным сбросом конвейера), в то время как более вероятная ветвь перехода вообще не потребует.
Из ассемблерного кода видно, что, действительно, в оптимизированной сборке на месте вызова operator[] стоит расчёт индекса и доступ к элементу, то есть код идентичнен коду для С масисва. Мне кажется, вам придётся показать, что в релизных сборках такого встраивания может не быть для того, чтобы показать не эквивалентность примеров.
Оптимизации, очевидно, не могут гарантировать встраивания всех функций. Ваш пример сломается если функция, например, слишком велика для встраивания (или по каким-то иным эвристикам компилятор решит, что делать этого не следует), или если она находится в иной единице трансляции при отключенном LTO.
Согласен, полагаться на оптимизации компиляторора в общем случае нужно осторожно. Но в статье описан очень конкретный случай.
А в каком месте вы ожидаете появление косвенной адресации? В примере из статьи видно, что результат компиляции foo_impl и bar_impl идентичен. Если поиграться с кодом, видно, что их вызовы в foo и bar при невозможности инлайнинга тоже иденичны.
Простите! А можно задать вопрос человеку, который сильно отстал от жизни? Вы не подскажите, std::array — это STL? А где можно ознакомиться с современным состоянием вопроса? И в каких компиляторах это реализовано?
Когда вы видите std::, это в целом говорит про то, что это часть стандартной библиотеки. С чем именно вы хотите ознакомиться? Вот, например, документация на std::array. Реализация есть во всех основных компиляторах, и в интеле, и в микрософтном, и в кланге, и в гцц.
std::array является частью стандартной библиотеки начиная со стандарта С++11. Любой компилятор, следующий стандарту, должен его содержать.
спасибо за приведение замечательного сравнения статистики тестов... ( я ранее был не уверен, а теперь точно знаю, что он всеже "как ни странно" оказывается быстрее в некоторых ситуациях нежели СИщный массив )
у меня все еще остались флешбеки, когда обсужадли с командой/начальством использования эррея и других фич от новых стандартов ( много-много лет назад ), и конкретно тогда как запомнилось - больше всего вопросов было к эррею и умным указателям
Из статьи узнал о различиях std::array и std::span, благодарю.
Знаю, что хабр полон едких комментаторов, можете ставить минусы, мне всë равно.
На самом деле, результат не является удивительным, поскольку современный C++ это zero-cost abstraction (но лишний раз убедиться на практике - это всегда хорошо).
Например, я здесь же на хабре предлагал использовать в качестве циклов конструкции не вида for (int i=0; i<n; i++), а питонообразные вещи типа for (int a: range(n)) или for (auto [u, v]: zip(arra, arrb)).
И да, они ни разу не медленнее стандартного цикла, поскольку оптимизирующий компилятор радостно выбрасывает всё лишнее. Что здорово, поскольку можно писать всё более и более человекочитаемый код, не жертвуя производительностью!
конкретный пример на всякий случай: https://godbolt.org/z/s6vh1K
Вы только что написали заклинание вызова холивара в комментариях))
Не ради холивара, но ради интересной беседы:
1) Стоит разделять оверхед в рантайме и компайлтайме. Многие абстракции никак не zero-cost когда речь доходит до размера объектников и времени компиляции.
2) Даже говоря о рантайме, не всё в плюсах бесплатно. Понимание цены абстракции и её отношение к бенефитам, которые эта абстракция несёт, важно. Наши примеры (std::array и ranged-for), наверное, можно назвать примерами zero-cost, во всяком случае в релизном рантайме. Поэтому они так показательны. Но, например, тут можно послушать про очень интересный пример о std::unique_ptr и о том, как он не бесплатен по отнешению к сырым указателям.
Ну именно поэтому я и говорю, что полезно иногда проверять :)
Zero cost возможен благодаря оптимизирующему компилятору, который очень сильный, но очень близорукий. Его нужно направлять.
Современное программирование - это (экспериментальная) ч0рная магия. Чисто умозрительно можно мало что утверждать с полной уверенностью, теперь нужно экспериментировать и замерять.
ха, слушаю этого дядю, и прямо выясняется, что мы с ним говорим просто одними словами:
and last, but not least: please, please, please, please, measure that cost
Спасибо за ссылку :)
Но, например, тут можно послушать про очень интересный пример о std::unique_ptr и о том, как он не бесплатен по отнешению к сырым указателям.
Вы не могли бы указать временну́ю метку, ну или кратко пересказать, о чём там говорится?
Спасибо!
Кстати, к питону отсылки отличные. Те же итертулз в нём - отпадная вещь, пользоваться которой крайне приятно!
Например, разрастание размера объектных файлов (в худшем случае). Посудите сами, была у вас раньше функция, которая принимала указатель и длину, и прекрасно себе при этом поживала:
void foo(int *arr, size_t len){ /* ... */}Теперь мы хотим переделать её на использование std::array:
template<std::size_t N>
void bar(std::array<int, N> arr){ /* ... */}Вот тут в статье неравнозначная замена. Вариант с std::array создаёт копию при каждом вызове. См. вызов memcpy: https://godbolt.org/z/8vozsEzra. Вероятно это и есть тот самый случай, когда использование std::array замедляет программу при невнимательном рефакторинге.
Равнозначная замена будет при использовании ссылки:
template<std::size_t N>
void bar(std::array<int, N>& arr){ /* ... */}Это конечно на случай, если нет c++20 с std::span, который предпочтительнее.
Я конечно дилетант в C++, надеюсь меня поправят, если я не прав. На ум приходит ситуация, когда std::array эффективнее С-style массивов. Из-за pointer aliasing компилятор не может в некоторых ситуациях хорошо векторизовать С-style массивы из-за того, что они по сути сырые указатели и потенциально могут указывать на перекрывающиеся участки памяти. А ключевого слова restrict в С++ нет.
Например: https://godbolt.org/z/h5xnWWT3f
Интересный пример. Из-за того, что сырые массивы могут частично налагаться друг на друга, векторизация может не сработать. std::array, в свою очередь, гарантирует, что объекты не перекрываются (так как его нельзя сделать из сырого указателя).
Было бы интересно найти пример, в котором веткоризирующих инструкций нет вовсе в случае с указателями, но есть в случае с std::array. Попробую таким заняться.
Как уже говорили выше, передавать std::array в функции по значению - очевидный оверхед на memcpy. Следовательно, передавать нужно по ссылке. Но посудите сами — при передаче двух std::array по ссылке занимаемые ими области памяти могут быть идентичны. Если есть аналог memcpy с такой сигнатурой
void f(std::array<int, 10> &a, std::array<int, 10> &b)То вызов
std::array<int, 10> arr;
f(arr, arr);Оптимизировать нельзя, потому что области памяти перекрываются, они буквально идентичны.
Поправьте, если неправ
`template<std::size_t N> void bar(std::array<int, N>& arr)`
Зачем, если если есть std::vector, который тоже очень неплохо оптимизируется?
У std::array размер известен во время компиляции (что помогает в оптимизации) и он не аллоцирует динамически память, в отличии от std::vector.
Это всё кончено замечательно, но я это и так знао. Вопрос бы в том, что если у тебя куча массивов разной длинны, то не лучше ли не клепать шаблонную функцию, а сделать одну нормальную функцию для вектора или итератора. Я даже больше за итератор голосую, не смотря даже что сделаны они в плюсах через дупу.
в общем случае интерфейс сstd::vector, конечно, малость оверхед(будет хорошо работать только при условии, что временные объекты не создаются), правильная альтернатива - std::span (если нам позарез нужен указатель на массив в памяти, например, для передачи в C API), ну и пара итераторов/диапазон для работы с "конвенционными" контейнерами C++
справедливости ради, в вашем же блоге была статья, в которой std::array не только не ловит выход за массив, а генерит код с безусловно бесконечным циклом, который вываливает все содержимое стека (подозреваю что из-за constexpr const_reference operator[], что дает компилятору повод пооптимизировать обращения к несуществующим элементам). В комментах победило мнение что это не баг а фича, пути UB непостижимы. Но как-то таких фич не хочется.
Чтобы std::array ловил выход за пределы, надо пользоваться методом at(). operator[] не делает никаких проверок.
Сам для себя я понял, что UB компиляторами понимается как то, что никогда не происходит. А значит компилятор может вырезать любой код, который вызывает UB или зависит от вызова UB. Т.е. это именно фича для оптимизации. Раз выход за пределы массива это UB, то этот выход никогда не происходит, а значит никаких проверок добавлять не надо и программа не будет терять на них время.
Хорошее описание UB! Есть отличное видео как раз об этом.
Давеча закончил отличную игрульку Plague's Tale: Requiem, там в конце была фраза "All natural laws end here". Мне кажется, к UB она подходит замечательно)
Строго говоря, начать печатать стек можно и с обычным массивом. В моей прошлой статье был вот такой пример подобного.
В моей прошлой статье был вот такой пример подобного
кстати да, тоже было такое, хотя и не так проявлялось (в плане что встроенный массив не панацея). Но здесь Вы работаете с абстракцией как с другой абстракцией (чуть ниже как с памятью и это уже прокатывает, хотя тоже смешивание) - дело сознательное. В начальном примере и этого нет, а константы размера/цикла могут быть обфусцированы, преднамеренно или нет.
"All natural laws end here". Мне кажется, к UB она подходит замечательно)
Если в плане что здесь природные законы заканчиваются и начинаются человеческие со всеми их особенностями - то полностью согласен.
Список UB это что-то вроде перечня триггеров, включающих фантазии компилятора на тему оптимизации, которые правильно работают только на определенном подмножестве случаев, причем точно его границы компилятор сам определить не может. Если романтичное undefined behaviour заменить на прозаичное known issues - мысленный путь до workaround становится значительно короче.
std::array в С++ не медленнее массива в С