В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

graalvm_ru

247 membersпожаловаться на группу
2018 June 20

OC

Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀 in graalvm_ru
pragus
и? вот есть такая старая задачка про роутинг ipv4 пакетов, которую решает каждый разработчик ос. потому что нужна структура данных с быстрым лукапом и при этом компактная, а записей в ней может быть относительно много(например, 500к).
нахер мне нужно решать какую-то проблему роутинка ipv4 пакетов, если я пишу банковский софт? Почему этот ворклоад меня должен хоть как-то беспокоить?
источник
01:41пожаловаться#1

p

pragus in graalvm_ru
так вот, про роутинг. сначала делали тупо хеш-таблицу, но оно сильно жрет память и хоть декларируется O(1), но по факту все сильно хуже )
источник
01:41пожаловаться#2

NK

ID:414983998 in graalvm_ru
pragus
так вот, про роутинг. сначала делали тупо хеш-таблицу, но оно сильно жрет память и хоть декларируется O(1), но по факту все сильно хуже )
Конечно хуже, чем больше таблица, тем выше вероятность коллизий и соответственно дальше или поключаем список или пересчитываем хэш фкнкцию с другим seed number. Но хэш-таблицы бывают разные есть например DHT которая менее подвержена этому, есть trie-структуры типа Judy-array
источник
01:45пожаловаться#3

p

pragus in graalvm_ru
Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀
нахер мне нужно решать какую-то проблему роутинка ipv4 пакетов, если я пишу банковский софт? Почему этот ворклоад меня должен хоть как-то беспокоить?
я тебе историю хочу рассказать. в итоге, в ход пошли всякие префиксные деревья. но чтобы не бегать по пустым узлам туда втащили path compression.

в итоге. получилось lpc-trie(в linux) и какая-то модификация patricia у freebsd. на относительно современном железе это все дает ~ 8 млн. лукапов в секунду на 1 ядро. вроде збс, да?
источник
01:47пожаловаться#4

OC

Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀 in graalvm_ru
такс, продолжайте. Вроде заебись!
источник
01:48пожаловаться#5

p

pragus in graalvm_ru
а потом появился DIR-24-8 в пейпере "Routing Lookups in Hardware at Memory Access Speeds".
источник
01:49пожаловаться#6

p

pragus in graalvm_ru
потом появился DXR, различные вариации которого дают больше сотни млн лукапов
источник
01:50пожаловаться#7

p

pragus in graalvm_ru
а теперь вот выкатили popcount trie, который быстрее dxr в 1.6 раза.
источник
01:50пожаловаться#8

p

pragus in graalvm_ru
короче, поинт в том, что зная своё железо можно обнаружить что у тебя совсем не хайлоад и надо просто взять профайлер.
источник
01:51пожаловаться#9

OC

Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀 in graalvm_ru
На всякий случай участникам чатика, @shelajevoleg - один из разрабов Грааля. Так что можно вносить сюда и более сложные вопросы)
источник
01:52пожаловаться#10

NK

ID:414983998 in graalvm_ru
popcount trie это тоже самое что QP-tries?
источник
01:53пожаловаться#11

p

pragus in graalvm_ru
ID:414983998
popcount trie это тоже самое что QP-tries?
угу.
источник
01:56пожаловаться#12

p

pragus in graalvm_ru
ID:414983998
popcount trie это тоже самое что QP-tries?
https://www.slideshare.net/hirochikasai/poptrie-a-compressed-trie-with-population-count-for-fast-and-scalable-software-ip-routing-table-lookup
www.slideshare.net
Poptrie: A Compressed Trie with Population Count for Fast and Scalabl…
Presented in SIGCOMM 2015.
источник
01:57пожаловаться#13

NK

ID:414983998 in graalvm_ru
Ясно. Judy-array пробовали? У него самое лучшее cache coherence среди всех структур что я встречал, но я не уверен, что поиск столь же быстрый как у popcount trie
источник
01:59пожаловаться#14

NK

ID:414983998 in graalvm_ru
Ну и компрессии нету
источник
02:00пожаловаться#15

OC

Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀 in graalvm_ru
Хей ребята, а вы чем по жизни занимаетесь?
источник
02:05пожаловаться#16

OC

Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀 in graalvm_ru
Ну, не каждый интересуется пейперами по Trie
источник
02:05пожаловаться#17

p

pragus in graalvm_ru
Oleg Chirukhin ☄️ 🧙🏻‍♂️🚀
Хей ребята, а вы чем по жизни занимаетесь?
всякое сетевое говно пишу на разных языках.
источник
02:11пожаловаться#18

p

pragus in graalvm_ru
а, у меня лапки.
источник
02:11пожаловаться#19

NK

ID:414983998 in graalvm_ru
Ну trie структура о которой должен знать каждый девелопер так или иначе. Это веб-разработчики могут обходиться массивами да хештаблицами, им даже Map/Set очень редко когда нужен, а для всех остальных это нормальное владение computer science
источник
02:11пожаловаться#20