Является ли безопасным отнять от указателя 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-х рандомных меств памяти не читала, либо читала но редко

Seed для CRC32?

mayton2019, не понимаю, как оно за разумное время могло сработать при 5'000'000 в 5'008'333 слотов. Вот, например, рассмотрим момент, когда вставилось 2'500'000 ключей (т.е. load factor ~ 0.5) теперь осталось вставить ещё столько же ключей и для каждого вероятность, что он вызовет коллизию не меньше 0.5 (и она будет расти по мере продвижения), то есть после момента, как вставилось без коллизий 2.5кк ключей вероятность, что остальные вставятся без коллизий не меньше 0.5^2'500'000

Seed для CRC32?

mayton2019, а какие ключи (равномерное распределение, нормальное распределение, инкрементальные значения и т.д.) ? какая хеш функция ? с какой попытки сошлось ?

Seed для CRC32?

Алгоритм примерно такой:
1) Берем размер хеш-таблицы в n = size(K). Метод открытой адресации.
2) Берем любую хеш-функцию (по области определения больше чем n
SHA1, MD5, xxhash, mur-mur-hash)
3) Начинаем наполнять таблицу.
4) Как только детектирована коллизия - удаляем старую таблицу и создаем новую
с размером например 120% от исходного n.
5) Повторяем алгортм до тех пор пока не будут расставлены все ключи.

Такой подход, к сожалению, сходится к ~n^2 памяти

Изучать хеширование на базе целых чисел - вобщем-то не интересно. Более общий случай - это
строки (String) и я-бы делал эксперименты со строками и с реальными данными (мобильные
телефоны емейлы налоговые номера и прочее). Целые числа - это .... слишком синтетические
тесты и их результаты потом никуда натянуть нельзя.

А как же какой-нибудь Map(id, User) ))

Seed для CRC32?

mayton2019, внешняя и все внутренние таблицы могут быть выделены в непрерывном куске памяти, только вот из-за того, что размер внутренней константный, перерасход памяти получается порядка 10-16n