всем привет!
надо согласно исходный сетей раскидать пакеты по vlan 
список сетей приводим к uint32_t и загоняем в массив по принцыпу lower[] upper[] что соответсвует нижней и верхней границы сети потом в цыкле определяем принадлежность ип к сети :

проблема в следуещем , когда загружаеш в массив сетей ну хотя бы ua-ix (19000 сетей) получается что каждый пакет надо прогнать по 19000 элементам массива что очень тормозит работу програмы на практике выяснил что такой алгоритм поиска не выдерживает более 42000 - 43000 входящий пакетов в секунду даже при работе в 8 треадов 
подскажите более быстрый алгоритм 

Это сообщение отредактировал(а) box - 12.5.2014, 00:44

Самое, пожалуй, быстрое -- построить perfect hash function. 
Впрочем, возможно, что ты в этой математике закопаешься -- тогда можно просто hash, дажэ очень тупой (типа два средних байта номера сети), примерно в два размера таблички. 

Или взять btree или какой-нибудь вариант trie (их сейчас можно найти сделанными на макросах, вполне эффективные) -- реализацыя будет во-первых довольно эффективной на любых размерах массива (в варианте с hash -- только примерно соответствующем первоначальному предположэнию), кроме того, trie обычно компактнее, что, например, позволит влезть всей структуре в L2 cache.

PS А, да, про cache: ещё, размеется, батчинг: постарайся проводить этот поиск для множэства пакетов подряд. Чтобы твои данные про сети висели таки в кэшах во время работы алгоритма. Т.е. накапливаешь тысячу или десяток тысяч пакетов -- и потОм распределяешь.

Аналог mod_geoip? Конечно, дерево, последовательный перебор слишком затратный. Насколько я помню, в mod_geoip используется специфическое дерево интервалов.

Но если у Вас все подсети имеют "правильный" вид (то есть с масками вида /20, /24 ...), то можно обойтись простым бинарным деревом, максимальное количество сравнений тогда будет не более 30. Правда, нужно будет учесть, что для конкретного IP нужно будет выбирать как можно узкую подсеть (с максимальной маской).

речь идет о 10g ethernet а именно о 14млн пакетов в сек так что тут ни дерево ни какие хаши боюсь не справятся , надо будет попробовать перенести поиск по сетям на cuda

Думаю, Вы не до конца понимаете, что дают Вам деревья. Feodorv, в таком случае даже преувеличил число сравнений для поиска: на 14млн пакетов будет порядка 7 сравнений на поиск. Конечно, я имею ввиду сбалансированные деревья и бинарный поиск. Посмотрите вот для примера: http://ru.wikipedia.org/wiki/Красно-чёрное_дерево .

А если Вы сами всё так хорошо знаете -- то зачем здесь что-то спрашываете?