Скоростной бинарный поиск

[POP]

Кто как ищет бинарные данные в памяти?

Допустим есть условие: в 300mb памяти найти с десяток разных значений.

Я делаю так: тупо для каждого значения, которое нужно найти, цикл побайтный с нуля и до конца блока памяти, и с каждого адреса делаю сверку функцией CompareMem. То есть для десяти значений нужно 10 раз эти 300mb побайтно пробежать, что влечет за собой добротный такой зависончик секунд на 20 на мощном компе. Страшно представить, что будет на обычных офиcных PC.

[--Ins--]

Смотря что и где искать. В общем случае рецепта нет. Но в частных возможно составления по данным некоторого кеша и поиска уже в нем

[Pavia]

POP
Бинарный поиск это поиск дехотомией. Пару микросекунд.

Цитата POP @ 11.06.12, 10:33

То есть для десяти значений нужно 10 раз эти 300mb побайтно пробежать

Пробегайте один раз.

Цитата POP @ 11.06.12, 10:33

что влечет за собой добротный такой зависончик секунд на 20 на

А это у вас ошибка в коде.

[POP]

Pavia

Цитата Pavia @ 11.06.12, 11:43

Пробегайте один раз.

Дык, от перемены мест умножаемых результат не меняется. Какая разница, 10 раз пробежать сверяя каждый байт с одним значением или пробежать один раз, но каждый байт сверять 10 раз? Разницы никакой.

Цитата Pavia @ 11.06.12, 11:43

А это у вас ошибка в коде.

Дело не в Application.ProcessMessages, а в затрачиваемом времени. Все равно долго ждать.

Цитата Pavia @ 11.06.12, 11:43

Бинарный поиск это поиск дехотомией. Пару микросекунд.

Это вы о чем?

[MBo]

>Это вы о чем?
О том, что название темы вводит в заблуждение. Бинарный (двоичный) поиск - известный алгоритм поиска на сортированных данных, к данной задаче отношения не имеет.

Добавлено 11.06.12, 12:40
А по теме - какого типа данные нужно искать?

[POP]

MBo

А я имею ввиду от слова "бинари", то есть обычный блок памяти, байты, в котором нужно искать любую последовательность байт.

[MBo]

Если нужно искать последовательности байт, то нужно обратить внимание на алгоритмы поиска в строках - подыскать такой, который позволяет искать сразу много образцов в тексте - например, Ахо-Корасик или Рабин-Карп это умеют.

Сообщение отредактировано: MBo - 11.06.12, 13:35

[Pavia]

POP

Цитата POP @ 11.06.12, 12:34

Дык, от перемены мест умножаемых результат не меняется.

Это ты зря сказал. Это в математике не меняется. А в программирование ещё как. Но сейчас не об этом.

Цитата POP @ 11.06.12, 12:34

Какая разница, 10 раз пробежать сверяя каждый байт с одним значением или пробежать один раз, но каждый байт сверять 10 раз?

В первом случае кэш не оптимально используется.

Цитата POP @ 11.06.12, 12:34

А это у вас ошибка в коде.
Дело не в Application.ProcessMessages, а в затрачиваемом времени. Все равно долго ждать.

У меня поиск подстроки в строке выдает на одной машине 250Мбайт/с на другой 500МБайт/с
Т.е 300 мб за 10 проходов должен отрабатывать 6-12, а у вас в 2 раза больше.

Цитата POP @ 11.06.12, 13:10

А я имею ввиду от слова "бинари", то есть обычный блок памяти, байты, в котором нужно искать любую последовательность байт.

Наконец то задачу услышали. Это называется поиск подстрок в строке.

[--Ins--]

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

Сообщение отредактировано: --Ins-- - 11.06.12, 13:51

[leo]

Цитата Pavia @ 11.06.12, 13:36

В первом случае кэш не оптимально используется

В общем случае это, конечно, так, но при тупом побайтовом сравнении разницы практически может и не быть, т.к. скорость чтения современной памяти в пересчете к частоте процессора составляет не менее 1 байта за такт, а для тупой побайтовой проверки без разворота цикла и прочих ухищрений требуется не менее 2-3 тактов на 1 байт, а с учетом условных переходов при "ложном обнаружении" и того больше. Поэтому чтобы проявился эффект от кэширования, нужно еще и саму скорость сравнений повысить, например, использовать известную фишку с поиском нуля в 4-байтных словах (используемую при поиске длины строки в strlen)
Ну или если речь идет о поиске не слишком коротких строк, то можно использовать алгоритмы быстрого поиска а ля Бойер-Мур, но только не по всему файлу за раз, а блоками размером с кэш первого уровня

Сообщение отредактировано: leo - 11.06.12, 14:39

[Pavia]

leo
И вообще я тему поиска подстроки очень хорошо проработал.

Частота памяти RAM около 100Мгц с этой частотой к неё идут запросы. Уже очень давно и практически не растёт. Растёт частота отдачи данных. Но она практически неважна. Так как в первом случае у тебя будет 10*N запросов. А во втором N запросов.

Эффект кэша будет заметен при любом раскладе. Что-бы его не заметить надо очень сильно постараться.

Цитата

т.к. скорость чтения современной памяти в пересчете к частоте процессора составляет не менее 1 байта за такт

Чтение из кэша первого уровня составляет 3 такта. Читать мы можем по 1,2,4,8 байт. Заставить компилятор использовать оптимальную конструкцию чтения не просто. Тут только ассемблер поможет, но на переходах 2 такта потратите. За такт 0.5 байта не больше. Так что больше 1000-1500 МБайт/с не получить.

Цитата

например, использовать известную фишку с поиском нуля

Эта фишка не работает если несколько разных байт. Да и другие тоже плохо работают. Я нашел только две фишки которые работают.
Первая, вылизанная программа. Когда мы читаем из кэша 4 байта в регистр и далее из регистра выбираем по байту и использовать этот байт для поиска в таблице. Таблица это реализация автомата. Но проблема построения таблицы чтобы она хорошо помещалась в кэш вопрос открытый.


Вторая фишка сравнивать не байт, а два байта за раз. В среднем хорошо работает. Правда если надо найти несколько подстрок, то быстрее будет автомат.

[POP]

Pavia

Цитата Pavia @ 11.06.12, 13:36

У меня поиск подстроки в строке выдает на одной машине 250Мбайт/с на другой 500МБайт/с
Т.е 300 мб за 10 проходов должен отрабатывать 6-12, а у вас в 2 раза больше.

Вообщем сделал замеры:

Файл 277mb, загружен весь в память, замеры производил на третью попытку (чтобы в кеше все было), 22 параметра искал (в среднем длина каждого 5 байт), проц AMD 4x 955 3,2 ГГц. = 49 секунд.

Причем в каждом из 22-x циклов, каждую 1024 итерацию я делаю ProcessMessages, дабы форма не зависала. Никаких ASM вставок или подобных оптимизаций нет конечно.

Сделайте у себя замеры тоже, если материал под рукой.

[Pavia]

Цитата POP @ 11.06.12, 15:44

каждую 1024 итерацию я делаю ProcessMessages

Надо через 1 миллионов, а лучше через 10 миллионов.

t=15,21 с; speed=455,00 МБайт/с C2D 2.2ГГц И дело тут не в процессоре, а в частоте памяти.

procedure TForm1.Button1Click(Sender: TObject);
Var
 s:String;
 t1,t2:Integer;
 sub:array [0..21] of String;
 I,J:Integer;
begin
SetLength(s,300*1024*1024);
for i:=1 to 300*1024*1024 do
 s[i]:=Char(Random(255));
 
for i:=0 to Length(sub)-1 do
 begin
 SetLength(Sub[i],5);
 for j:=1 to 5 do
  begin
  sub[i][j]:=Char(Random(255));
  end;
 end;
t1:=GetTickCount;
for i:=0 to Length(sub)-1 do
 Memo1.Lines.Add(IntToStr(Pos(sub[i],s)));
t2:=GetTickCount;
Memo1.Lines.Add('******');
Memo1.Lines.Add(Format('t=%f с; speed=%f МБайт/с',[(t2-t1)/1000,Length(sub)*(Length(s)/1000)/(t2-t1)]));
end;

[POP]

Pavia

У меня в таком варианте выдает: t=4,27 с; speed=1622,27 МБайт/с

а вот если переделать цикл под CompareMem вот так:

t1:=GetTickCount;
for i:=0 to Length(sub)-1 do
begin
 for j:= 1 to Length(s)-5 do
 begin
  if CompareMem(@s[j], @sub[i], 5) then
   Beep();
 end;
end;
t2:=GetTickCount;

То выдает близкий к моему результат:

t=55,16 с; speed=125,47 МБайт/с


Может функцию Pos можно как-то под бинарный (binary) поиск приспособить, почему она такая быстрая?

[Pavia]

POP
Вам лучше сделать алгоритм Ахо-Корасик.