Используйте память после конца std::vector, используя настраиваемый распределитель с превышением доступности

Допустим, у меня есть распределитель my_allocator, который всегда будет выделять память для n+x (вместо n) элементов при вызове allocate(n).

Могу ли я с уверенностью предположить, что память в диапазоне [data()+n, data()+n+x) (для std::vector<T, my_allocator<T>>) доступна/действительна для дальнейшего использования (т. е. для размещения новых или загрузки/сохранения simd в случае основ (пока нет перераспределения)?

Примечание. Я знаю, что все, что находится после data()+n-1, является неинициализированным хранилищем. Вариант использования будет вектором фундаментальных типов (у которых в любом случае нет конструктора) с использованием пользовательского распределителя, чтобы избежать особых угловых случаев при добавлении встроенных свойств simd в вектор. my_allocator должна выделять хранилище, которое 1.) правильно выровнено и имеет 2.) размер, кратный размеру используемого регистра.

Чтобы немного прояснить ситуацию:

Допустим, у меня есть два вектора, и я хочу их добавить:

std::vector<double, my_allocator<double>> a(n), b(n);
// fill them ...
auto c = a + b;
assert(c.size() == n);

Если хранилище, полученное из my_allocator, теперь выделяет выровненное хранилище и если sizeof(double)*(n+x) всегда кратно используемому размеру регистра simd (и, следовательно, кратно количеству значений в регистре), я предполагаю, что могу сделать что-то вроде

for(size_t i=0u; i<(n+x); i+=y) 
{ // where y is the number of doubles per register and and divisor of (n+x)
    auto ma = _aligned_load(a.data() + i);
    auto mb = _aligned_load(b.data() + i);
    _aligned_store(c.data() + i,  _simd_add(ma, mb)); 
}

где мне не нужно заботиться о каком-либо особом случае, таком как невыровненная загрузка или отставание от некоторого n, которое не делится на y.

Но все же векторы содержат только n значений и могут обрабатываться как векторы размера n.


c++ language-lawyer stdvector allocator
person Pixelchemist    schedule 15.10.2016    source источник
comment
Зачем тебе это? Если вам нужно пространство n+x, установите размер n+x.   -  person Chris Dodd    schedule 15.10.2016
comment
@ChrisDodd: мне нужны векторы размером n. Я просто хочу развернуть какой-то цикл, не следя за тем, чтобы не промахнуться (или проверить, есть ли что-то, что нужно обработать неразвернутым способом).   -  person Pixelchemist    schedule 15.10.2016
comment
Как насчет того, чтобы просто использовать reserve (до развертывания операции, например, reserve(n+x)) вместо того, чтобы возиться с распределителем? И если вы не сохраняете ничего полезного после size, почему i<(n+x) вместо простого i<n?   -  person FranMowinckel    schedule 15.10.2016
comment
@FranMowinckel: Потому что мне не нужны возможные накладные расходы на перераспределение, и я хотел бы скрыть это как деталь реализации. Да, i<n в этом случае точно эквивалентен. Этот код не настоящий код, а просто иллюстрация.   -  person Pixelchemist    schedule 15.10.2016
comment
@Pixelchemist - если вам не нужна специальная обработка хвоста цикла, сегодня большинство высокопроизводительных реализаций справляются с этим следующим образом: (а) обеспечить разумное выравнивание начала области (например, до 16- граница байта для SSE или 32 байта для AVX), а затем (b) для чтения выделенной области в последней итерации, игнорируя любые данные за пределами выделенной области. Это безопасно на практике, на определенных платформах/компиляторах и широко используется. Я добавил больше деталей в свой ответ ниже.   -  person BeeOnRope    schedule 30.10.2016

Ответы (2)


arrow_upward
1
arrow_downward

Для вашего варианта использования у вас не должно быть никаких сомнений. Однако, если вы решите хранить что-то полезное в дополнительном пространстве и позволите размеру вашего вектора изменяться в течение его жизни, вы, вероятно, столкнетесь с проблемами, связанными с возможностью перераспределения — как вы собираетесь передавать лишние данные из старое распределение в новое распределение, учитывая, что перераспределение происходит в результате отдельных вызовов allocate() и deallocate() без прямой связи между ними?

ИЗМЕНИТЬ (обращение к коду, добавленному к вопросу)

В своем первоначальном ответе я имел в виду, что у вас не должно возникнуть проблем с доступом к дополнительным байтам, выделенным вашим распределителем сверх того, что было запрошено. Однако запись данных в диапазон памяти, который находится за пределами диапазона, используемого в настоящее время векторным объектом, но принадлежит диапазону, который будет охватывать немодифицированное выделение, вызывает проблемы. Реализация std::vector может запросить у распределителя больше памяти, чем было бы доступно через его функции size()/capacity(), и хранить вспомогательные данные в неиспользуемой области. Хотя это очень теоретически, игнорирование такой возможности означает открытие двери в неопределенное поведение.

Рассмотрим следующую возможную схему размещения вектора:

---====================++++++++++------.........
  1. === - используемая мощность вектора
  2. +++ - неиспользованная емкость вектора
  3. --- - превышено вектором (но не показано как часть его емкости)
  4. ... — превышено вашим распределителем

ЗАПРЕЩАЕТСЯ писать что-либо в регионах 2 (---) и 3 (+++). Все ваши записи должны быть ограничены областью 4 (...), иначе вы можете повредить важные биты.

person Leon    schedule 15.10.2016
comment
Я не хочу на самом деле хранить что-то там. Если то, что я предполагаю, верно, я бы (и, надеюсь, смог бы) убедиться, что я могу справиться или предотвратить случай перераспределения, но на данный момент это не намерение. В настоящее время я хочу выполнить развертывание цикла. - person Pixelchemist; 15.10.2016
comment
@Pixelchemist Смотрите обновленный ответ - на самом деле способ, которым вы собираетесь развернуть цикл, содержит угрозы UB. - person Leon; 15.10.2016

arrow_upward
2
arrow_downward

Вернемся на мгновение назад. Если проблема, которую вы пытаетесь решить, состоит в том, чтобы позволить базовой памяти эффективно обрабатываться встроенными функциями SIMD или развернутыми циклами, или и тем, и другим, вам не обязательно выделять память сверх используемого объема только для «округления». off" размер выделения кратен ширине вектора.

Существуют различные подходы, используемые для обработки этой ситуации, и вы упомянули пару, например, специальный код ввода и вывода для обработки начальной и конечной частей. На самом деле здесь есть две разные проблемы: обработка того факта, что данные не кратны ширине вектора, и обработка (возможно) невыровненных начальных адресов. Ваш метод перераспределения решает первую проблему, но, вероятно, есть лучший способ...

На практике большая часть SIMD-кода может просто считывать конец обрабатываемой области. Кто-то может возразить, что технически это UB, но при использовании встроенных функций SIMD вы уже выходите за рамки стандартного C++. На самом деле этот метод уже широко используется в стандартной библиотеке, поэтому он неявно поддерживается компилятором и сопровождающими библиотеки. Это также стандартный метод обработки SIMD-кодов в целом, так что вы можете быть уверены, что он не сломается внезапно.

Ключом к тому, чтобы заставить его работать, является наблюдение, что если вы можете правильно прочитать хотя бы один байт в каком-то месте N, то любое естественно выровненное чтение любого размера1 победит. t вызвать ошибку. Конечно, вам все еще нужно игнорировать или иным образом обрабатывать данные, которые вы читаете за пределами официально выделенной области, но вам все равно придется делать это с вашим подходом «выделить больше», верно? В зависимости от алгоритма вы можете замаскировать недопустимые данные или исключить недопустимые данные после выполнения части SIMD (т. е. если вы ищете байт, если вы найдете байт после выделенной области, это то же самое, что «не найденный").

Чтобы это сработало, вам нужно читать выровненным образом, но, я думаю, это то, что вы, вероятно, уже хотите сделать. Вы можете либо договориться о том, чтобы ваша выделенная память была выровнена в первую очередь, либо выполнить чтение с перекрытием в начале (т. Е. Сначала одно невыровненное чтение, затем все выровнено с первым выровненным чтением, перекрывающим невыровненную часть), или использовать тот же трюк в качестве хвоста для чтения перед массивом (с теми же рассуждениями, почему это безопасно). Кроме того, существуют различные приемы для запроса выровненной памяти без необходимости написания собственного распределителя.

В целом, я рекомендую стараться избегать написания собственного распределителя. Если код не достаточно жестко ограничен, вы можете столкнуться с различными ловушками, включая другой код, делающий неверные предположения о том, как была выделена ваша память, и различные другие ловушки, которые Леон упоминает в своем ответе. Кроме того, использование пользовательского распределителя отключает множество оптимизаций, используемых стандартными алгоритмами контейнера, если только вы не используете его повсеместно, поскольку многие из них применимы только к контейнерам, использующим один и тот же распределитель.

Кроме того, когда я фактически реализовывал пользовательские распределители2 , я обнаружил, что это хорошая идея в теории, но слишком неясная, чтобы поддерживать ее одинаковым образом во всех компиляторах. Теперь компиляторы со временем стали намного более совместимыми (в основном я смотрю на вас, Visual Studio), а поддержка шаблонов также улучшилась, так что, возможно, это не проблема, но я чувствую, что она все еще попадает в категорию «сделать». это только в том случае, если вы должны».

Имейте в виду также, что пользовательские распределители не очень хорошо компонуются - вы получаете только один! Если кто-то еще в вашем проекте захочет использовать настраиваемый распределитель для вашего контейнера по какой-либо другой причине, он не сможет этого сделать (хотя вы можете согласовать и создать комбинированный распределитель).

Этот вопрос, который я задал ранее, также мотивированный SIMD, охватывает много вопросов о безопасности чтения после конца ( и, неявно, перед началом), и, вероятно, это хорошее место для начала, если вы рассматриваете это.

1 Технически, ограничением является любое выровненное чтение до размера страницы, которого при размере 4 КБ или больше достаточно для любой из текущих векторно-ориентированных ISA общего назначения.

2 В данном случае я делал это не для SIMD, а в основном для того, чтобы избежать malloc() и разрешить частичное и непрерывное быстрое выделение в стеке для контейнеров с множеством мелких узлов.

person BeeOnRope    schedule 30.10.2016