Или почему не нужно бояться того, что удобно работает.
Стойте! Уберите руки от клавиатуры, дайте человеку сказать! У этой статьи есть обоснованные причины и благая цель! В прошлой моей статье о массивах (которую необязательно читать для понимания статьи этой) некоторые читатели выражали озабоченность тем, что std::array может быть медленнее встроенного С-массива.
Есть несколько источников правды в этом вопросе, и сегодня мы пройдёмся по каждому из них. Сначала узнаем, что по этому поводу пишет стандарт, потом заглянем в реализации std::array в libc++ и libstdc++, а затем посмотрим на ассемблер некоторых операций с этими объектами. Ну и завершим всё это дело, как и полагается, бенчмаркингом.
Стандарт
Строго говоря, стандарт не содержит в себе какой-либо информации, которая помогла бы нам разобраться в нашей дилемме. Мы опираемся на текст наиболее свежей версии, имеющейся в свободном доступе. Параграф 24.3.7 [array] описывает общие требования к std::array и его интерфейсу, но на этом описание, фактически, заканчивается. Что ж, галочку поставили, быстрее переходим к коду!
Библиотеки
Тем не менее, что бы там ни было написано в стандарте, нам — программистам — приходится иметь дело с конкретными реализациями. Посмотрим на две из них: одну — проекта LLVM (libc++), вторую – GNU (libstdc++). И там интересного для наших целей можно найти много-много больше!
LLVM
Начнём с простого. Как хранятся элементы коллекции?
template <class _Tp, size_t _Size>
struct _LIBCPP_TEMPLATE_VIS array {
//...
_Tp __elems_[_Size];
//...
};
Элементы типа _Tp хранятся как, ну... встроенный С-массив. Одного представления нам недостаточно, конечно, мы будем копать дальше.
Как производится доступ к элементам?
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX17 reference
operator[](size_type __n) _NOEXCEPT {
_LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
__n < _Size, "out-of-bounds access in std::array<T, N>");
return __elems_[__n];
}
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 const_reference
operator[](size_type __n) const _NOEXCEPT {
_LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
__n < _Size, "out-of-bounds access in std::array<T, N>");
return __elems_[__n];
}
Ага! Тут есть какая-то проверка _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS! Значит, индексация проходит медленнее!
Стоит разобраться. В LLVM есть так называемый hardening-механизм — _LIBCPP_HARDENING_MODE. Он позволяет устанавливать дополнительные проверки в зависимости от уровня данного механизма, которых всего предусмотрено 4. При включении самого слабого из них (либо, лучше сказать, что выключении механизма вовсе) проверки удаляются из кода. В остальных случаях проверка может быть, а может и не быть, в зависимости от самой проверки и уровня режима. Докажем это.
Для того, чтобы понять, что во что раскрывается, нужно обратиться к исходникам. В них мы увидим, что в зависимости от заданного значения _LIBCPP_HARDENING_MODE, сам _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS может раскрываться в _LIBCPP_ASSERT.
#define _LIBCPP_ASSERT(expression, message) \
(__builtin_expect(static_cast<bool>(expression), 1) \
? (void)0 \
: _LIBCPP_ASSERTION_HANDLER(__FILE__ ":" \
_LIBCPP_TOSTRING(__LINE__) ": assertion " \
_LIBCPP_TOSTRING(expression) " failed: " \
message "\n"))
Интринсик компилятора (встроенная функция, реализация которой есть в самом компиляторе) __builtin_expect задаёт наиболее вероятное значение целочисленного выражения expression, что может помочь процессору путём подсказок во время предсказания ветвлений (branch prediction). Это само по себе наводит на мысль о том, что такие проверки в продакшн коде не будут иметь большого влияния на производительность. Но давайте смотреть дальше. Во что раскрывается _LIBCPP_ASSERTION_HANDLER? Если верить этому и этому исходникам, то раскрываются они либо в __builtin_abort, либо в __builtin_verbose_trap, либо в __libcpp_verbose_abort. Иными словами — в интринсик компилятора, заставляющий программу нештатно завершиться. Сродни библиотечной функции std::abort.
Хорошо. При включённом hardening-механизме происходит валидация того, что индекс находится в рамках массива, что теоретически может замедлить исполнение программы.
В случае, если механизм выключен, то макрос _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS разворачивается в макрос _LIBCPP_ASSUME, который, в свою очередь, определён следующим образом:
# define _LIBCPP_ASSUME(expression) ((void)0)
Никаких проверок, только мусорная безобидная операция. Замедления в данном случае не предвидится вовсе.
Обратите внимание, что включение и выключение дополнительных проверок никак не связано с типом сборки — они могут быть (равно, как и не быть) как в релизной, так и в отладочной версиях. Контроль за ними отдан исключительно hardening-механизму, в чём мы могли убедиться, исследуя код выше, и -DNDEBUG к этому отношения не имеет.
Hardening-механизм появился в LLVM 18 и заменил механизм _LIBCPP_ENABLE_ASSERTIONS. Если верить исходникам, то эта настройка соответствует строгому режиму в новом механизме.
Больше про hardening-механизм можно почитать в исходниках или посте разработчиков.
Упустили ли мы что-либо?
Теоретически, от замены встроенного массива на std::array может пострадать итерация через range-based цикл. Как можно прочитать в стандарте ([stmt.ranged]), при такой итерации по встроенному массиву используются нативные указатели, а в остальных случаях — итераторы, получаемые через begin и end соответственно (методы или свободные функции). В случае std::array будут использоваться итераторы. Как они определены?
using value_type = _Tp;
using pointer = value_type*;
using const_pointer = const value_type*;
#if defined(_LIBCPP_ABI_USE_WRAP_ITER_IN_STD_ARRAY)
using iterator = __wrap_iter<pointer>;
using const_iterator = __wrap_iter<const_pointer>;
#else
using iterator = pointer;
using const_iterator = const_pointer;
Как мы видим, в части случаев используется обычный указатель, как и в итерации по встроенным массивам. Но макрос _LIBCPP_ABI_USE_WRAP_ITER_IN_STD_ARRAY всегда определён, как видно из файла, его содержащего. То есть, итерация будет вестись с помощью некой обёртки над указателем __wrap_iter. Как можно понять из её кода, итератор этот используется в контейнерах, гарантирующих последовательное расположение элементов в памяти, таких как std::basic_string, std::basic_string_view, std::vector, std::span и в нашем дружище std::array.
Зачем нужная такая обёртка? Из текста исходников и, например, этого обсуждения, становится понятно: __wrap_iter нужен в первую очередь для того, чтобы клиентский обобщённый код понимал, что прилетевший ему итератор указывает на элемент, расположенный в последовательной памяти. Что после этого элемента есть ещё элементы. Обратите внимание, такая обёртка используется только в контейнерах, гарантирующих последовательное расположение элементов в памяти. Значит, шаблон функции, принимающий std::array<T,S>::iterator, будет знать точно, что этот итератор указывает на последовательную область памяти. Что, вообще-то, случайный итератор делать не обязан, равно как и обычный указатель. Кстати, вот тут описаны ещё несколько причин, почему имплементации стандартных библиотек часто не используют обычный указатель в качестве итераторов по контейнерам.
Но вернёмся к вопросу о том, насколько такие обёртки влияют на производительность. Строго говоря, я не нашёл в приведённой выше имплементации ничего такого, что замедлило бы выполнение программы. Например, то же обращение по этому итератору не содержит никаких проверок, даже при включённом hardening-механизме. Обёртка эта, в конце концов, очень тонкая. Конечно, из-за того, что мы вводим в программу новые шаблоны, время компиляции и размер объектных файлов увеличатся. Но мы тут говорим о производительности, не так ли?
На этом, пожалуй, закончим с имплементацией LLVM.
GNU
Перейдём к реализации std::array в проекте GNU. Как хранятся элементы?
template<typename _Tp, std::size_t _Nm>
struct array {
//...
typename __array_traits<_Tp, _Nm>::_Type _M_elems;
//...
__array_traits<_Tp, _Nm>::_Type представляет из себя псевдоним для типа хранящегося массива. С помощью этого служебного класса разработчики добиваются отличия в поведении std::array нулевой длины от всех остальных std::array. Обычно _Type является типом массива, который несёт в себе объект std::array, но __array_traits<_Tp, 0>::_Type переопределяет _Type и предоставляет свои реализации некоторых операторов. Например, оператор индексации вызывает __builtin_trap. Кстати, реализация std::array в LLVM решает эту же проблему с помощью отдельной частичной специализации std:: array<_Tp, 0>.
Ну ладно, массив хранится так же просто, как массив в большинстве случаев. Как происходит индексация?
[[__nodiscard__]]
_GLIBCXX17_CONSTEXPR reference
operator[](size_type __n) noexcept
{
__glibcxx_requires_subscript(__n);
return _M_elems[__n];
}
[[__nodiscard__]]
constexpr const_reference
operator[](size_type __n) const noexcept
{
#if __cplusplus >= 201402L
__glibcxx_requires_subscript(__n);
#endif
return _M_elems[__n];
}
Опять же, ситуация схожа с той, что мы видели в реализации от LLVM: есть проверка, и только после неё идёт индексация. __glibcxx_requires_subscript представляет из себя макрос, который определён вот так:
#ifndef _GLIBCXX_DEBUG
// ....
# define __glibcxx_requires_subscript(_N) \
__glibcxx_assert(_N < this->size())
// ....
#else // Use the more verbose Debug Mode checks.
// ....
# define __glibcxx_requires_subscript(_N) \
__glibcxx_check_subscript(_N)
// ....
Интересно. То есть, проверка в коде будет в любом случае, так что ли? Давайте сначала разберёмся с ситуацией, когда макрос _GLIBCXX_DEBUG всё-таки не определён. При таком раскладе наша проверка будет проводиться с помощью __glibcxx_assert. Вот как он определён:
#if defined(_GLIBCXX_ASSERTIONS)
// Enable runtime assertion checks, and also check in constant expressions.
# define __glibcxx_assert(cond) \
do {\
if (__builtin_expect(!bool(cond), false)) \
_GLIBCXX_ASSERT_FAIL(cond); \
} while (false)
#elif _GLIBCXX_HAVE_IS_CONSTANT_EVALUATED
// Only check assertions during constant evaluation.
namespace std
{
__attribute__((__always_inline__,__visibility__("default")))
inline void
__glibcxx_assert_fail()
{ }
}
# define __glibcxx_assert(cond) \
do {\
if (std::__is_constant_evaluated())\
if (__builtin_expect(!bool(cond), false)) \
std::__glibcxx_assert_fail(); \
} while (false)
#else
// Don't check any assertions.
# define __glibcxx_assert(cond)
#endif
Как видно из else-ветки, есть случаи, когда макрос разворачивается в ничто, сиречь в коде окажется пустое выражение ";".
Случай с _GLIBCXX_ASSERTIONS называется "debug mode lite" и призван включать некоторые ассерты без определения макроса _GLIBCXX_DEBUG. Макрос этот включается в том числе через флажок hardened — своего рода аналог режима от LLVM. Одним словом, его можно отключить.
Случай с _GLIBCXX_HAVE_IS_CONSTANT_EVALUATED чуть более интересный. Определяется он тут (в двух местах) внутри тела функции std::__is_constant_evaluated, которая как раз и вызывается в проверке. Данная функция позволяет выполнить участок кода только в случае, если он выполняется в constant-evaluated контексте. Иными словами, на этапе компиляции. Иными словами, не в рантайме. Иными словами, без ущерба для производительности, так как на этапе выполнения этого кода не будет вовсе.
В случае, если же определён макрос _GLIBCXX_DEBUG, __glibcxx_requires_subscript раскрывается в __glibcxx_check_subscript, который раскрывается в _GLIBCXX_DEBUG_VERIFY, а что там происходит дальше нас волновать не должно, так как интересна нам, в конце концов, производительность в релизных, а не отладочных сборках.
Что происходит при итерации по range-based циклу? Посмотрим, как определены итераторы по std::array (опустим в этот раз константные итераторы и попросим читателя поверить или проверить, что они реализованы схожим образом).
typedef _Tp value_type;
typedef value_type* pointer;
typedef value_type* iterator;
Как видно из кода, обычные итераторы определены как нативные указатели. А что возвращают begin и end?
// Iterators.
[[__gnu__::__const__, __nodiscard__]]
_GLIBCXX17_CONSTEXPR iterator
begin() noexcept
{ return iterator(data()); }
[[__gnu__::__const__, __nodiscard__]]
_GLIBCXX17_CONSTEXPR iterator
end() noexcept
{ return iterator(data() + _Nm); }
}
[[__nodiscard__, __gnu__::__const__, __gnu__::__always_inline__]]
_GLIBCXX17_CONSTEXPR pointer
data() noexcept
{ return static_cast<pointer>(_M_elems); }
Строго говоря, разбираться особенно не в чем. Функции возвращают указатели на первый элемент и на элемент, следующий за последним.
Промежуточный вывод
Мы рассмотрели реализации std::array от двух крупнейших компиляторостроителей. Ни в одной из них мы, автор, не нашли ни одного места, в котором на продакшене могло бы произойти существенное замедление. Естественно, мы, автор, готовы подискутировать об этом в комментариях.
Но не будем останавливаться на исходниках. Возможно, std::array компилируется во что-то принципиально непроизводительное?
Ассемблер
Попробуем посмотреть на примере нескольких операций, какой ассемблер получается у компилятора. Использовать будем последний доступный на Compiler Explorer Clang для платформы x86-64.
Для начала возьмём простую итерацию по массиву и по std::array с последовательным их заполнением случайными числами.
Пролог обеих функций идентичен — происходит выделение памяти с её последующим обнулением:
push rbp
mov rbp, rsp
sub rsp, 4032 ;выделили память
lea rdi, [rbp - 4000]
xor esi, esi ;решили, чем будем занулять
mov edx, 4000
call memset@PLT ;занулили
Код с получением итераторов закономерно отличается. В случае с массивами происходит загрузка указателей, обрамляющих массив:
lea rax, [rbp - 4000] ; получили значение начала
mov qword ptr [rbp - 4008], rax ;сохранили значение начала
mov rax, qword ptr [rbp - 4008]
mov qword ptr [rbp - 4016], rax ;сохранили значение итератора
mov rax, qword ptr [rbp - 4008]
add rax, 4000 ; получили значение конца
mov qword ptr [rbp - 4024], rax ;сохранили значение конца
Ассемблер варианта с std::array отличается только тем, что для получения итераторов вызываются соответствующие методы. Происходит, фактически, то же самое.
lea rax, [rbp - 4000]
mov qword ptr [rbp - 4008], rax
mov rdi, qword ptr [rbp - 4008]
call std::array<int, 1000ul>::begin()
mov qword ptr [rbp - 4016], rax
mov rdi, qword ptr [rbp - 4008]
call std::array<int, 1000ul>::end()
mov qword ptr [rbp - 4024], rax
Код самой итерации абсолютно идентичен (за исключением меток, на которые происходит прыжок).
.LBB8_1: ;сравнили итераторы
mov rax, qword ptr [rbp - 4016]
cmp rax, qword ptr [rbp - 4024]
je .LBB8_4 ;вышли из цикла, если надо
mov rax, qword ptr [rbp - 4016]
mov qword ptr [rbp - 4032], rax ;получили адрес элемента
lea rdi, [rip + dis]
lea rsi, [rip + gen]
call int std::uniform_int_distribution ;много текста
mov ecx, eax
mov rax, qword ptr [rbp - 4032]
mov dword ptr [rax], ecx ;сохранили новое значение
mov rax, qword ptr [rbp - 4016]
add rax, 4
mov qword ptr [rbp - 4016], rax
jmp .LBB8_1
.LBB8_4: ;вышли из функции
add rsp, 4032
pop rbp
ret
Как видно из примера, функции практически идентичны. Если же немного поиграть с кодом и включить оптимизации уровня O3, то идентичными они станут не почти, а полностью (за исключением меток). Никаких вызовов к методам begin и end в случае std::array не появится.
Одним из аргументов против использования std::array может служить довод о том, что когда он передаётся в функции по ссылке, то при обращении к его элементам происходит дополнительная косвенность. Давайте проверим этот аргумент. В этот раз будем передавать массив и объект std::array в функции. Для чистоты картины будем делать обращения к случайному элементу.
Как видно из сгенерированного ассемблерного кода, инструкции практически идентичны. Приведём только различающиеся части, начиная с записи в элементы обычного массива.
mov edx, dword ptr [rbp - 28] ;читаем новое значение
mov ecx, eax ;читаем индекс
mov rax, qword ptr [rbp - 24] ;читаем значение указателя
movsxd rcx, ecx ;конвертируем
mov dword ptr [rax + 4*rcx], edx ;записываем новое значение
Сама запись занимает пять инструкций, одно сложение и одно умножение. В случае std::array всё выглядит несколько иначе.
mov rdi, qword ptr [rbp - 32] ;указатель на первый элемент
movsxd rsi, eax ;индекс
call std::array< >::operator[] ;получаем указатель на элемент
mov ecx, dword ptr [rbp - 20] ;читаем новое значение
mov dword ptr [rax], ecx ;записываем новое значение
В этом случае появляется дополнительный вызов метода operator[], возвращающий lvalue-ссылку на элемент std::array. Внутри этой функции, скорее всего, произойдёт такая же адресная арифметика, как и в предыдущем случае —* [rax + 4*rcx]*. Наверное, это действительно несколько медленнее (на один вызов функции).
Но что будет, если мы включим все оптимизации? Ассемблер станет абсолютно одинаковым (за исключением, естественно, меток). Никакого вызова operator[] нет и в помине.
К слову, мы немного упустили рассмотрение двойной косвенной адресации. Особенно вдумчивые читатели могли бы сказать, что в случае передачи std::array по ссылке в функцию мы встречаем двойную косвенность. Дескать, при обращении к элементу нужно будет сначала получить сам объект, после чего уже обратиться к хранящемуся в нём массиву. Как мы сами увидели, этого не происходит, во всяком случае в коде со включённой оптимизацией.
Промежуточный вывод
Хорошо, без включённых оптимизаций компилятор генерирует различный код для операций над массивами и std::array. Он отличается незначительно, но всё же отличается. Возможно, в некоторых ситуациях, на определённых операциях и определённых масштабах, это может сыграть не в лучшую для std::array сторону. Со включёнными оптимизациями говорить о замедлениях не приходится — код получается в прямом смысле одинаковый.
Раз уж мы начали говорить о скорости, то почему бы нам не сравнить эти две сущности в лоб и немного их не поэчпочмакать?
Эчпочмакинг
Бенчмаркинг — дело неблагодарное, и, более того, не всегда точное. Результаты тестов могут меняться от машины к машине, от компилятора к компилятору и даже от запуска к запуску. Поэтому мы используем его в качестве дополнительного источника истины в нашем бравом приключении в поисках скорости, но не как основное мерило правды.
Как и в случае с исследованием ассемблерного кода, будем смотреть на два типа операций — последовательное заполнение массива случайными числами, а также на случайное обращение к произвольным элементам массива при одновременной передаче массива в функцию. Для компиляции используем GCC и Clang. Проверять будем на дебажной (с флагом -DDEBUG) и релизной (с оптимизациями уровня -O3 и флагом -DNDEBUG) сборках. И, конечно, для самих тестов используем Google Benchmark.
Рабочая машина автора:
Процессор Intel® Core™ i7-9700K, 3.60GHz, L1 Data 32 KiB (x8), L1 Instruction 32 KiB (x8), L2 Unified 256 KiB (x8), L3 Unified 12288 KiB (x1).
Объём оперативной памяти — 32 гигабайта.
Каждый тест мы будем гонять на массивах и std::array разных размеров, полностью занимающих первый, второй и третий кэши соответственно. Каждый тест будет проходить 10000 итераций, чтобы примерно выровнять результаты.
Результаты
Строго говоря, мы могли бы обойтись одним графиком вместо шести у нас имеющихся, так как отношение между различными сборками одинаковое для всех линий кэша, меняются только абсолютные числа. Тем не менее, приводим все результаты для большей наглядности.
На оси ординат указано время прохождения 10000 итераций каждого теста в наносекундах.
Для начала приведём результаты прогона тестов с последовательным заполнением памяти.
Рисунок 1 — L1, sequential indexing
Рисунок 2 — L2, sequential indexing
Рисунок 3 — L3, sequential indexing
Как видно из графиков, в отладочных версиях std::array показывает меньшую производительность, чем встроенный массив. Оно и понятно, выше в ассемблере мы видели вызовы функции operator[], а они работают медленнее, чем простая адресация массива. Кроме того, исследуя реализации библиотек, мы показали, как при использовании std::array в некоторых случаях происходят дополнительные проверки на выход за границу массива.
Однако стоит только включить оптимизации, как картина меняется. Не знаю как вы, но автор реальной разницы в скорости не видит. В std::array каких-либо замедлений в сравнении со встроенным массивом нет.
Отличаются ли как-то принципиально тесты случайного доступа к памяти? Давайте посмотрим.
Рисунок 4 — L1, random indexing
Рисунок 5 — L2, random indexing
Рисунок 6 — L3, random indexing
Помимо возросшего времени прохождения, графики отличаются только одним — ничем.
Соображения
Допустим, мы вас убедили в том, что перейти на std::array — не страшно. Какие соображения вас могут от этого отвадить (представим, что это новый проект, и переписывать старый код не придётся)?
Например, разрастание размера объектных файлов (в худшем случае). Посудите сами, была у вас раньше функция, которая принимала указатель и длину, и прекрасно себе при этом поживала:
void foo(int *arr, size_t len)
{
/* ... */
}
Теперь мы хотим переделать её на использование std::array:
template<std::size_t N>
void bar(std::array<int, N> arr)
{
/* ... */
}
После такого перехода хочешь-не хочешь, но придётся использовать шаблоны! Даже если до этого наша гипотетическая функция foo использовала бы шаблоны для вывода типа элемента массива, то в новой реализации bar будут выводиться, помимо этого, и размеры передаваемых массивов. Это приведёт к пропорциональному росту размера объектных файлов, ведь разных функций будет инстанцировано в количестве type*size, а не просто type, как в случае с передачей в функцию встроенного массива.
Если в вашем проекте используется C++20, то удобной заменой для этих целей может служить std::span:
void bar(std::span<int> s)
{
/* ... */
}
std::span — это лёгкая обёртка вокруг указателя на последовательную память, несущая в себе информацию и о размере этой памяти. По нему можно итерировать, его можно индексировать, его можно сделать из std::array. Можно сказать, что это своего рода клёвый указатель на массив целиком. Размер массива может храниться как внутри объекта, так и быть переданным в качестве шаблонного аргумента (для этого есть второй параметр, по умолчанию принимающий константное значение std::dynamic_extent).
Вообще, есть в этом классе некоторая философская элегантность. Со времён чистого С массивы были чем-то невразумительно промежуточным между полноценным объектом и указателем на первый элемент. С введением std::span, фактически, эта дихотомия развалилась на два отдельных класса: std::array ведёт себя только как полноценный массив, а std::span — только как указатель (абстрагирующий от программиста конкретный контейнер). Здорово! И никаких самописных обёрток.
В итоге там, где массив должен храниться, он хранится как std::array. Его объекты могут быть переданы дальше в использующие его функции как объекты класса std::span.
Помимо этого, с переходом на std::array мы получаем встроенные проверки выхода за массив на дебаге (как мы видели в части про бенчмаркинг), удобство поддержания и расширения кода, а также возможность отказа от самописных утилит для работы со встроенными массивами. И, что самое главное, мы получаем единообразное поведение объектов std::array. Приятно, когда они ведут себя именно как полноценные объекты, а не норовят при любом удобном случае обратиться в указатель.
Выводы
Такие вот дела. std::array — это хорошая альтернатива встроенным С-массивам, которая лишена многих его недостатков. Если наличие стандартной библиотеки в проекте не запрещено, то почему бы не попробовать использовать удобную абстракцию вместо встроенной функциональности? В конце концов, платим мы за обе вещи одинаковую цену.
А если у вас есть, что нам сказать по этому поводу, с удовольствием ждём вас в комментариях!
Благодарим, что дошли до конца! El Psy Kongroo.
Комментарии (27)
Paulus
27.09.2024 18:09+3На самом деле std::array -- это просто С массив с фиксированными во время компиляции типом и размером , к которому однако применимы с++ итераторы и который соответственно может быть использован в stdc++ functions вроде сортировки или поиска, boost и дальше до куда фантазии хватит.
Spym
27.09.2024 18:09+3задаёт наиболее вероятное значение целочисленного выражения expression, что может помочь процессору путём подсказок во время предсказания ветвлений (branch prediction)
Интринсики для указания вероятности ветвления к аппаратному предсказателю ветвлений никакого отношения не имеют. Как и написано в документации, на которую вы ссылаетесь, это влияет лишь на генерацию кода. В общем случае, компилятор ничего не знает об аппаратном предсказателе ветвлений, и манипулировать его состояниями не может (оставим в стороне вещи вроде сброса конвейера, это про другое).
Одним из аргументов против использования std::array может служить довод о том, что-де когда он передаётся в функции по ссылке, то при обращении к его элементам происходит дополнительная косвенность.
Косвенность у вас в бенчмарке исчезла из-за того, что вызываемая функция была встроена в место вызова (inlined). Думаю, будет легко показать, что при отсутствии встраивания косвенность не исчезает, значит примеры не эквивалентны.
dkosolobov
27.09.2024 18:09+2Можно косвенно влиять на предсказатель. Это не точная наука, но кое на что можно полагаться. Например, что предсказатель считает дальние условные переходы менее вероятными (именно такой скорее всего будет переход на abort) и что условные ближние переходы назад более вероятны. Понятно, что предсказатель это непростая штука и есть много условий, в том числе история выполнения кода. Но можно немного на него влиять. Думаю, что автор это и имел ввиду под подсказками предсказателю.
tntnkn Автор
27.09.2024 18:09Отпишу сначала про предсказатель, потом про косвенность в следующем комментарии.
Касательно подобных железных вещей практической экспертизой я похвастать не могу, конечно. Но. Если правильно понимаю, современные архитектуры не поддерживают инструкции, напрямую влияющие на предсказатель, в этом вы безоговорочно правы. Так же вы безоговорочно правы и касательно генерации кода - использование указанной интриники может привести к реорганизации кода. При этой реорганизации, например, инструкции двух ветвей условного оператора могут быть поменяны местами. Эта перестановка, в свою очередь, может повлиять на то, какую ветвь исполнения предсказатель выберет за наиболее вероятную.
Вы согласитесь с подобным описанием?
Spym
27.09.2024 18:09+1С описанием согласен, но акцент на предсказателе ветвлений тут лишний. Реорганизация ветвей может иметь большое влияние на производительность и в архитектурах вообще без предсказателя (например, в микроконтроллерах), где инструкции перехода сбрасывают конвейер и приостанавливают исполнение. Вашим интринсиком вы можете сказать компилятору, какая ветвь наименее вероятна, и она будет исполнятся после исполнения инструкции перехода (с возможным сбросом конвейера), в то время как более вероятная ветвь перехода вообще не потребует.
tntnkn Автор
27.09.2024 18:09Из ассемблерного кода видно, что, действительно, в оптимизированной сборке на месте вызова operator[] стоит расчёт индекса и доступ к элементу, то есть код идентичнен коду для С масисва. Мне кажется, вам придётся показать, что в релизных сборках такого встраивания может не быть для того, чтобы показать не эквивалентность примеров.
Spym
27.09.2024 18:09+1Оптимизации, очевидно, не могут гарантировать встраивания всех функций. Ваш пример сломается если функция, например, слишком велика для встраивания (или по каким-то иным эвристикам компилятор решит, что делать этого не следует), или если она находится в иной единице трансляции при отключенном LTO.
tntnkn Автор
27.09.2024 18:09Согласен, полагаться на оптимизации компиляторора в общем случае нужно осторожно. Но в статье описан очень конкретный случай.
OlegZH
27.09.2024 18:09Простите! А можно задать вопрос человеку, который сильно отстал от жизни? Вы не подскажите, std::array — это STL? А где можно ознакомиться с современным состоянием вопроса? И в каких компиляторах это реализовано?
haqreu
27.09.2024 18:09+4Когда вы видите
std::
, это в целом говорит про то, что это часть стандартной библиотеки. С чем именно вы хотите ознакомиться? Вот, например, документация на std::array. Реализация есть во всех основных компиляторах, и в интеле, и в микрософтном, и в кланге, и в гцц.
tntnkn Автор
27.09.2024 18:09std::array является частью стандартной библиотеки начиная со стандарта С++11. Любой компилятор, следующий стандарту, должен его содержать.
ice872
27.09.2024 18:09+1спасибо за приведение замечательного сравнения статистики тестов... ( я ранее был не уверен, а теперь точно знаю, что он всеже "как ни странно" оказывается быстрее в некоторых ситуациях нежели СИщный массив )
у меня все еще остались флешбеки, когда обсужадли с командой/начальством использования эррея и других фич от новых стандартов ( много-много лет назад ), и конкретно тогда как запомнилось - больше всего вопросов было к эррею и умным указателям
tntnkn Автор
27.09.2024 18:09Спасибо и вам, рад, что понравилось!
Касательно того, почему он в некоторых тестах оказался быстрее, чем С массив, хотя реализован через С массив - это, вообще, интересно.
haqreu
27.09.2024 18:09+3На самом деле, результат не является удивительным, поскольку современный C++ это zero-cost abstraction (но лишний раз убедиться на практике - это всегда хорошо).
Например, я здесь же на хабре предлагал использовать в качестве циклов конструкции не вида
for (int i=0; i<n; i++)
, а питонообразные вещи типаfor (int a: range(n))
илиfor (auto [u, v]: zip(arra, arrb))
.И да, они ни разу не медленнее стандартного цикла, поскольку оптимизирующий компилятор радостно выбрасывает всё лишнее. Что здорово, поскольку можно писать всё более и более человекочитаемый код, не жертвуя производительностью!
tntnkn Автор
27.09.2024 18:09Вы только что написали заклинание вызова холивара в комментариях))
Не ради холивара, но ради интересной беседы:
1) Стоит разделять оверхед в рантайме и компайлтайме. Многие абстракции никак не zero-cost когда речь доходит до размера объектников и времени компиляции.
2) Даже говоря о рантайме, не всё в плюсах бесплатно. Понимание цены абстракции и её отношение к бенефитам, которые эта абстракция несёт, важно. Наши примеры (std::array и ranged-for), наверное, можно назвать примерами zero-cost, во всяком случае в релизном рантайме. Поэтому они так показательны. Но, например, тут можно послушать про очень интересный пример о std::unique_ptr и о том, как он не бесплатен по отнешению к сырым указателям.
haqreu
27.09.2024 18:09+1Ну именно поэтому я и говорю, что полезно иногда проверять :)
Zero cost возможен благодаря оптимизирующему компилятору, который очень сильный, но очень близорукий. Его нужно направлять.
Современное программирование - это (экспериментальная) ч0рная магия. Чисто умозрительно можно мало что утверждать с полной уверенностью, теперь нужно экспериментировать и замерять.
tntnkn Автор
27.09.2024 18:09Да! Плюсы круты в том числе тем имхо, что всегда можно посмотреть на то, что конкретно будет исполнятся.
ЗЫ: знаю одного толкового джуна, который попал в одну плюсерскую команду написав потрясающее сопроводительное письмо о том, как он хочет научится владеть ч0рной магией и быть колдуном)
haqreu
27.09.2024 18:09+1ха, слушаю этого дядю, и прямо выясняется, что мы с ним говорим просто одними словами:
and last, but not least: please, please, please, please, measure that cost
Спасибо за ссылку :)
tntnkn Автор
27.09.2024 18:09+1Кстати, к питону отсылки отличные. Те же итертулз в нём - отпадная вещь, пользоваться которой крайне приятно!
mastan
27.09.2024 18:09Например, разрастание размера объектных файлов (в худшем случае). Посудите сами, была у вас раньше функция, которая принимала указатель и длину, и прекрасно себе при этом поживала:
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, который предпочтительнее.
SIWRX
Спасибо!
Сейчас как раз в качестве обучения C++ переписываю рабочий Embedded проект для микроконтроллера с C на современный C++. Интересно почитать о сравнении массивов и о скорости работы.
tntnkn Автор
Если перейдёте на std::array, будет интересно потом почитать о том, что получилось. Случились ли замедления и на сколько стало/не стало удобнее.