Где могла закрасться ошибка?

Несовсем понял, почему тег сменили с математики на алгоритмы, когда в вопросе представлена задача по теории вероятности, неужели потому что в тексте есть ссылка на код

Нужно ли здесь выравнивание на стеке?

А, ещё вопрос:
если есть момент, когда ROOT_POS = insertPosition, но именно в этот момент в buffer будет находиться мусор, может ли привести такой memcpy к UB с логической точки зрения ? Ну то есть поскольку области будут перекрываться, то это UB формально, но так как там уже лежит мусор, то, если мусорные объекты станут в невалидном состоянии, то это не UB. Или может что-то ещё произойти ?

memcpy(&buffer[ROOT_POS], &buffer[insertPosition], sizeof(Entry<K, V>));

Нужно ли здесь выравнивание на стеке?

Не уверен, поэтому и делаю )

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

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

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

maaGames, график

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

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

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 промах по кешу

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

mayton2019,

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

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

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 формулы получше + даже быстрее немного доступ к ребенку

Seed для CRC32?

mayton2019, я не знал, что там речь шла именно о популярных/непопулярных ключах
Почему O(1) нельзя в данном случае ? Всегда можно сделать размер таблицы n^2 и захешировать, в среднем за 2 раза без коллизий сойдётся. Но с одной стороны так много памяти жалко, с другой, даже, если там будет всего лишь 10к интов, то оно даже в L3 не уложится (нужно 400 мб для этого, а стандавртный серверный L3 обычно 128/256 мб)

Seed для CRC32?

floppa322, я вот решил следующее посчитать. Допустим я не буду вставлять конфликтующие ключи. А просто буду вести их список. Долг типа. Вот получилось так на 5 млн.

2023-07-28 20:06:28,511 : [INFO] - Start demo
2023-07-28 20:06:29,417 : [INFO] - Populated successfully!
2023-07-28 20:06:29,417 : [INFO] - Inserted : 3160854
2023-07-28 20:06:29,419 : [INFO] - Collision list size : 1839146
2023-07-28 20:06:29,419 : [INFO] - Hash set physical size is 5000000 slots (20000000 bytes)
2023-07-28 20:06:29,419 : [INFO] - Inserted/slots ratio : 63%
2023-07-28 20:06:29,419 : [INFO] - Finish

Из 5 лямов успешно вставились порядка 3.1 млн. Долговых ключей на 1.8. Хорошая новость
их хотя-бы не так много. Далее я могу рекурсивно применить алгоритм построения этой-же
таблицы к списку долговых ключей. Но теперь мне уже не нужно 5 млн слотов. Я сразу создаю
1.8. И если эта геометрическая прогрессия работает (100% - 63% = 37%) то каждый раз
я буду получать треть от оригнального размера. Хеш функцию в данном случае можно
даже не менять. Просто меняется у нас остаток от деления. Будет пирамида таблиц.

Если честно, у меня пока нет никаких мыслей, как это можно развить, чтобы было O(1) без жирных констант на contains

Seed для CRC32?

mayton2019, и да, нужно, чтобы запросов, где на contains/get было false/null, было мало, иначе в этом подходе не будет смысла особого

Seed для CRC32?

mayton2019, кстати, насчёт "skewed histograms" на самом деле, хорошую идею подкинул, если такой шаблон встретился где-то.
Действительно, можно отсортировать данные по частоте заросов на них, скажем на 10% объектов приходится 90% запросов contains/get, тогда можно с обычным линейным пробированием эти 10% запихать первыми (так, чтобы distance от места вставки до реального места был не больше 1.05 скажем), а остальные 90% запихать потом. Тогда мат. ожидание кеш мисса будет близко к 1.

Единственный минус это большие таблицы. То есть, например, может так получиться, чтобы сохранить инвариант distance <= 1.05 для 10% объектов может потребоваться массив размером, например, 60n, если данных очень много. Из-за того что вероятность коллизии как квадрат растёт от n, к сожалению

Seed для CRC32?

mayton2019, ну если речь идёт о статичной таблице (однажды построилась и далее с неё только читают, не модифицируют), то кукушка будет пробовать строиться, пока не построится так, чтобы каждому элементу было отведено место (не было циклов), ну а дальше просто запросы get/contains в зависимости от того мапа это или сет, ничего никуда больше перемещаться не будет))

Seed для CRC32?

mayton2019, ну я хотел либо попробовать похешировать столько раз, чтобы distance от места вставки до реального расположения был небольше какой-то константы (как в робин гуде) ну и дальше что-то поулучшать там. Либо придумать так, чтобы кукушка из 2-х рандомных меств памяти не читала, либо читала но редко