Компактная упаковка списка IPv4 адресов

1-5 тысяч — ни о чём же, скорее всего, даже btree будет достаточно.

хотя да, 5 тыс упаковать в 4 байта — это жалкие 20 килобайт.

А в памяти уже обычная хеш-таблица.

Да, не надо перемудривать.

Ну или trie, будет быстрее и не сильно оверхэд по памяти.

Плюсую trie.

Скорее всего, эта задача эффективна решена в ipset

чё мудрить-то - массив unsigned long + сортировка пузырьком + поиск делением пополам

Через boolean**** можно (mask[i1][i2][i3][i4]). Если адреса более-менее локализованы, бОльшая часть будут NULL-ы и заметного перерасхода памяти не будет.

radix tree ?

std::unordered_set<uint32_t>

Каков характер адресов? Случайные, со всей планеты, или с какой-то закономерностью, типа мультикастных фидов на бирже?

Через boolean**** можно (mask[i1][i2][i3][i4]). Если адреса более-менее локализованы, бОльшая часть будут NULL-ы и заметного перерасхода памяти не будет.

man TLB

https://en.wikipedia.org/wiki/Translation_lookaside_buffer

А почему именно man TLB, можно поинтересоваться? То есть, понятно что будет проседание по производительности из-за pointer chasing'а, но в чем специфика TLB, а не кеш-миссов в целом?

А почему именно man TLB, можно поинтересоваться? То есть, понятно что будет проседание по производительности из-за pointer chasing'а, но в чем специфика TLB, а не кеш-миссов в целом?

1. Размер TLB существенно меньше, чем строк в кэше. Случайный доступ в массив размером 64мб вытирал TLB у Nehalem полностью

2. Для восполнения промаха в кэше нужен один доступ в память (плюс вытеснение одной строки из кэша), для TLB - 3 или 4 для обхода таблицы страниц, в зависимости от процессора и режима его работы, с вытеснением такого же количества строк из кэша

3. У кэша есть префетчер и спекулятивный доступ, обычно успешно подтягивающий данные до того, как они будут нужны, у TLB этого нет

4. Транслятор адресов может параллельно делать всего две трансляции для чтения и одну для записи. И это нужно делать для каждой кэш-строчки.

5. Большие страницы для sparse-массива - это огромный перерасход памяти, а на микроархитектурах до Haswell ещё и тормоза из-за отдельного и крохотного TLB для больших страниц (на SnB было 32).

Спасибо за развернутый ответ!

битмаска в 4 гигабайта

Гигабита! Каких-то 256 мегабайт. Не так уж и плохо. А вообще см(если не страшно - авторы не советуют) judy array.

Чем тебе std::set<uint32_t> не подходит?

А что кроется за словом «Проверка»?

radix tree ?

Плюсую. Реализация есть в py-radix.

Подскажите пожалуйста, какой есть хороший способ упаковать список IP адресов (без зон и масок, скорее всего только адреса) в какую-то структуру, что бы проверка по ней была очень быстрой.

Если обновление не критично, то это задача для perfect hashing с доступом за O(1). В теории, получается сжатие, близкое к теоретическим пределам. Если стукнешь в почту, могу подкинуть статей по этой теме. Если тебе не шашечки, а ехать, то есть куча вариантов хэширования, например, Cuckoo Hashing.

Зачем radix tree, когда размер маски фиксированный?

У radix tree тоже доступ O(1) и отличное сжатие, но плюс к этому возможность быстрого поиска:
- нескольких масок по более широкой маске
- масок, включающих более узкую маску

Видимо, мы по-разному понимаем задачу. Я вижу ее так, что маски не нужны (я не знаю почему, постановка задачи на совести ТС):

список IP адресов (без зон и масок, скорее всего только адреса)

В этом случае достаточно хэш-таблицы. В теории, два доступа к памяти будут достаточны; на практике, достигается использованием Cuckoo Hashing.

У radix tree тоже доступ O(1) и отличное сжатие

В худшем случае понадобится 32 обращения для IPv4, тоже O(1), но какая разница по сравнению с двумя! Если интересует сжатие, то есть perfect hashing, как я отмечал (проблемы, правда, с обновлением — придется создавать структуру заново), это ни разу не хуже radix tree. А если не оптимизировать указатели в radix tree, то с учетом них, perfect hashing может быть лучше. ЕМНИП, в perfect hashing поиск требует 5 доступов.

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

случайные, со всей планеты.

Я в итоге их просто передам по сети списком 32-битных чисел, а в памяти загоню в обычный хеш.

Тогда выбирай самую компактную структуру. Процессору проще посчитать побольше на локальных данных, чем память шерстить.

radix tree

локальные — это какой размер?

Вся иерархия кэшей.

Но структура там резидентной должна быть. Если её раздуть на весь L3, то она полностью там никогда не будет, естественно.

я боюсь, что учитывая что наш код на эрланге, особо про L2/L3 говорить не приходится =(

Правило остаётся: чем меньше память дёргаешь, тем лучше.

А эрланговская VM умеет huge pages использовать?

вроде как можно упросить.

А для этого надо настраивать ядро и ребутать сервер?

Ребутить не надо, только если под большестраницы не хочется почти всю память отдать.

так если никаких большестраниц ещё не настроено, чего делать?

sysctl -w vm.nr_hugepages=NNN