Является ли безопасным отнять от указателя 1 и итерироваться по массиву [1,N], а не [0, N-1]?

Question

[floppa322]

Вопрос на первый вгляд выглядит тривиальным, но почему-то есть некоторые опасения, например GPT сказал, что могут быть проблемы с алиасингом.

Решил написать cache oblivious d-кучу. Если индексировать элементы кучи с 0, а не с 1, то формула для обращения к child'ам/parent'ам становится некрасивая, поэтому решил сделать индексацию [1, N]. При этом куча такая, что все дети одного родителя находятся на одной кеш линиии.
Примерный код:

Entry * arr = allocator.allocate(N,  std::max(alignof(Entry), CACHE_LINE_SIZE));
--arr;
for(size_t i = 1; i <= N; ++i) arr[i]; // do something

При этом, например, выделить на 1 элемент больше и сделать то же самое, но без --arr; не получается, потому что тогда arr[1]...arr[d] (и вообще инвариант с выравниванием детей отвалится) не будут выровнены по кеш линии

В общем gpt слегка напугал с алиасингом, хотя так и не объяснил почему именно он нарушается при таком подходе

Ну и вариант с расширением апи аллокатора, где он будет возвращать такой адрес, что: (addr + sizeof(Entry)) % CACHE_LINE_SIZE == 0 тоже не подходит :)

Comments

[mayton2019]

Если индексировать элементы кучи с 0, а не с 1, то формула для обращения к child'ам/parent'ам становится некрасивая

Выглядит как будто ты одну проблему променял на другую. Можешь показать 2 формулы. "До" и "после"?

[floppa322]

mayton2019,

Индексация с 1:
j-й child j[1; d] : i*d+j
parent: (i-1)/d

Индексация с 0:
j-й child j[0; d-1] : (i+1)*d+j
parent: (i-d)/d

Всё-таки для индексации с 1 формулы получше + даже быстрее немного доступ к ребенку

[mayton2019]

floppa322, ты-же последовательно обходить будешь? Во втором случае можно
объявить итератор. Сдвинуть его на шаг вперед. И далее - та-же формула без изменений.
Ну тоесть я считаю что итерировать с 0 до N-1 или с 1 до N - это одна и та-же фигня.
Как бутерброд на язык класть колбасой или хлебом.

[floppa322]

mayton2019,

а, точно, можно же скобки раскрыть:
j-й child j[d; 2d-1] : i*d + j

[floppa322]

mayton2019, короч действительно, получилась проблема XY

[mayton2019]

floppa322, ахах

Answer 1

[Wataru]

Это не безопасно. Это не UB, но оно не определено стандартом. А значит, компилятор может что-то там соптимизитровать и поломать код.
В документации написано:

Every value of pointer type is one of the following:
* a pointer to an object or function (in which case the pointer is said to point to the object or function), or
* a pointer past the end of an object, or
* the null pointer value for that type, or
* an invalid pointer value.

Т.е. arr у вас, вообще-то, invalid pointer value перед циклом.

Плюс там же написано:

Any other use of an invalid pointer value has implementation-defined behavior.

А GPT, как это почти всегда и происходит - нагаллюционировал вам бред. Это не база знаний, не поисковик по информации, а лишь модель, которая пытается создать текст, похожий на текст из обучающей выборки. Если что-то часто встречается там слово-в-слово, то вам может и повести. Если ваш вопрос хоть чуть-чуть не отвечается первой страницей гугловой выдачи - вам почти гарантированно не повезет.

Edit: немного не то написал. Так делать "не рекомендуется", а не "небезопасно". Оно генерирует непереносимый код. Если у вас на конкретном компиляторе с конкретными ключами работает, то, в общем-то, можно использовать. Но лучше не надо.

Comments

[floppa322]

Any other use of an invalid pointer value has implementation-defined behavior.

Хм, по этим правилам выведения является ли указатель невалидным непонятно, как тогда оно будет работать в коде аллокатора

[Wataru]

floppa322, new работает на другом уровне и как-то выделяет объект и возвращает валидный указатель на него.

[floppa322]

Wataru, ну, например если пишешь свой кастомный аллокатор типа jemalloc или tcmalloc, то какими правилами руководствоваться, хотя по идее там просто работа с void*, мб оно спасает

[Wataru]

floppa322, Не вижу тут никакой проблемы. Эти аллокаторы обычно выделяют большой кусок памяти каким-нибудь другим аллокатором (например, обычным new), а потом по запросу режут его на кусочки. Там нигде в процессе не возникает указатель на -1-ый элемент массива. Или в середину объекта, потому что объекты там - байты.

[floppa322]

Wataru, они, как правило внутри даже malloc не используют, а прямо системные вызовы типа mmap

Answer 2

[Adamos]

Такие мелкие фокусы, ломающие читающему голову, небезопасны, если сопровождающий ваш код знает, где вы живете.

Comments

[floppa322]

Весь низкоуровневый код один большой фокус )

[Adamos]

floppa322, отнюдь.
Низкоуровневый код может быть банальной рутиной, читаемой с листа без малейших затруднений.
Зато взаимоотношения классов могут оказаться безумной борьбой между антипаттернами.

Answer 3

[maaGames]

Работай с массивом не напрямую, а через функцию. Ещё лучше, убери массив в класс.

double Get(double * arr, int index)
{
      assert( index > 0 );
      return arr[index - 1];
}

Или, ещё проще. Создавай массив на 1 элемент больше и игнорируй наличие нулевого элемента.

Comments

[floppa322]

Для 1го случая тогда уж взять "некрасивую" формулу (хотя , как выяснилось, если скобки в ней раскрыть, то норм) и с 0го по N-1 работать
А во втором случае дети ребёнка не лягут в одну кеш линию

[maaGames]

floppa322,
Где в вопросе упоминание хотя бы архитектуры процессора, на котором будет работать? А какие данные в массиве? Entry размером намного меньше cache_line_size, что у тебя куча детей в неё умещается?

[floppa322]

Где в вопросе упоминание хотя бы архитектуры процессора, на котором будет работать? А какие данные в массиве?

не понимаю, что это даст в данном контексте, на мой взгляд, в вопросе достаточно инфы

Entry это K, V или K, Void
d выбирается таким образом чтобы d = cache_line_size / k.size + v.size, если нацело не делится, то в Entry padding добавляется, то есть по умолчанию он 0

вроде бы стандартная реализация d кучи )

[maaGames]

floppa322, cache line разного размера всё же бывает. Если Entry больше размера cache line, то можно особо и не париться. Например, если это 64 байта, то из чего вообще Entry состоит, чтобы не только указатель на дочерний(дочерние) элементы хранить, но ещё и полезные даные были?

Возможно, я думаю не про то, но под выравниванием данных часто подразумевают выравнивание на 16 байт, чтобы всякие sse/avx инструкции смогли работать. Ну или на 4 байта для int, например.

[floppa322]

maaGames,

cache line разного размера всё же бывает. Если Entry больше размера cache line, то можно особо и не париться. Например, если это 64 байта, то из чего вообще Entry состоит, чтобы не только указатель на дочерний(дочерние) элементы хранить, но ещё и полезные даные были?

Ну просто сделать отдельную сборку для чипов с 64 и 128 байтами длинной кеш линии, чтобы в compile-time d вычислять. Ну либо в рантайме вычислять, но всё же в compile-time безопаснее намного

Ключ K это число (теоретически может быть последовательность байт, но такого для куч не встречал никогда, если всё-таки это она, то d heap ничего не даст по сравнению с бинарной), т.е. размер не превосходит 8 байт. А V, если размер V, больше 8 байт делают указателем, итого K+V не больше 16 байт и уже можно сделать d = 4. При увеличении d падает количество рандомных скачков по памяти, например при увеличении d с 2 до 4 - в 2 раза, но при этом растёт количество сравнений, поэтому d обычно берут от 4 до 16
Ну и да, все дети одного родителя должны лежать в одной кеш линии, тогда по ним по всем пробежаться можно будет за 1 промах по кешу

[floppa322]

maaGames, график

Тут на графике зеленым цветом обозначены количества сравнений в зависимости от d, а фиолетовым - глубина дерева, то есть максимальное количество скачков по рандомным областям памяти
Ну а там, где прямые линии это графики для d=2, то есть классической кучи
Параметр 1'000'000 - количество элементов
Это для sift down/up

Answer 4

[floppa322]

В общем, выяснилось, что это проблема XY
Но тем не менее, в академических целях, хотелось бы знать, является ли это strict aliasing violation или ещё чем-то