Или почему не нужно бояться того, что удобно работает.
Стойте! Уберите руки от клавиатуры, дайте человеку сказать! У этой статьи есть обоснованные причины и благая цель! В прошлой моей статье о массивах (которую необязательно читать для понимания статьи этой) некоторые читатели выражали озабоченность тем, что 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.
Автор: tntnkn
