Многопоточный поиск подстроки

[Anarchist]

Имеются текстовые файлы очень больших объёмов (гигабайты). Пишу программу поиска в этих файлах строк из другого файла. Так как файлы очень большого объема то выполняется очень долго и соответственно появилось желание сделать многопоточный поиск.  Алгоритм следующий:
1) Создаётся "главный" поток (что бы GUI не зависало), который открывает очень большой файл и читает по одной строке из него.
2) Создаются ещё дочерние потоки и потокам раздаются строки из этого большого файла.
3) Каждый дочерний поток должен искать в переданной ему строке подстроку считываемую из файла с подстроками (он не сильно большой по размеру) и в случае нахождения высылать сигнал "главному" потому на запись в выходной файл переданной ему строки.
4) В "главном" потоке при получении сигнала на запись строки складываются в список и на выходе этот список записывается в выходной файл.

Пробовал реализовать создавая в "главном" потоке список размером idealThreadCount() пар потоков и открытых экземпляров файлов с подстроками (подумал что открытие каждый раз файла в потоке при получении очередной строки может замедлить работу). Потом раздавать в цикле строки потокам из списка. Но когда все потоки заняты делом нужно дождаться пока какой нибудь из них освободится, вот как это узнать не могу придумать.

Был вариант использования QThreadPool, но при этом варианте основной проблемой становится реализация отмены. И было замечено что даже если отключить autoRemove всё равно со временем начинают появляться новые экземпляры потоков. Сейчас не могу привести код, так как всё на работе. В общем основные вопросы это: плохо ли часто открывать и закрывать файл или лучше всё же создавать для каждого потока свой экземпляр файла открывать его, а потом передавать его адрес; как реализовать ожидание завершения любого потока из списка потоков (в QThreadPool можно только дождаться завершения всех потоков); можно ли как то остановить QThreadPool после такого цикла:

QTextStream fileStream(&file)
QString string;

while (fileStream.atEnd()) {
  string = fileStream.readLine();
  SaerchThread *thread = new SaerchThread(string);
   QThreadPool::globalInstance()->start(thread);
}

[Igors]

Я бы крутил примерно так

Код

C++ (Qt)
struct TSearchJob {
  QString mFileName,                   // имя файла где искать
  qint64 mPos[2],                      // с какой позиции и до какой
  const QStringList * mMatch,    //  что искать 
  bool mIgnoreCase,                   // и как 
  QList <TSearchResult> mResult;  // результат 
};
 

TSearchResult может быть напр таким

Код

C++ (Qt)
struct TSearchResult {
 qint64 mPos;   // позиция найденной строки в файле
 int mIndex;     // индекс строки в match
};
 

Посчитал число кусков в файле (размер / число ниток) и дал каждой нитке по куску

Код

C++ (Qt)
int ScanFile( TSearchJob & job );
 

Придется правда проверить участки "между кусками", но это можно сделать той же ф-цией ScanFile. В конце слил бы result из всех job

[Anarchist]

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

[Anarchist]

При варианте с кусками отмена произойдёт ещё быстрее конечно, тут я что то не подумал , но вариант с раздаванием каждому своей строки мне кажется более привлекательным.

[Igors]

При варианте с кусками отмена произойдёт ещё быстрее конечно, тут я что то не подумал , но вариант с раздаванием каждому своей строки мне кажется более привлекательным.

Совсем нет - ведь расходы на чтение файла (как минимум) не меньше расходов на поиск (особенно учитывая что файл будет читаться неск. нитками). Проще говоря I/O всегда медленнее процессора. Поэтому если уж загрузили кусок - нужно выжать из него все.  Да и с общностью получше - а если надо искать аж одну строку - так что, работает 1 нитка?

Примечание: не надо понимать буквально "каждая нитка грузит весь свой кусок (часть файла) в память". Нет, каждая нитка тоже загружает порциями, напр 1 Mb

[Anarchist]

Имеется очень большой файл (из него берём по одной строке) и значительно меньше (в нём ищем строку). Можно наоборот, но тогда мы несколько раз бегаем по большому файлу. Я подумал что строки из небольшого файла (можно не все сразу, а частями в цикле допустим тоже, что бы не переполнять список) затолкать вообще в QStringList и раздать каждой нитке по экземпляру (закэшировать что ли), тогда мы один раз проходимся по большому файлу, а все поиски происходят в оперативке. Итого 1 раз читаем большой файл и 1 раз маленький. При этом каждый поток работает со своим экземпляром маленького файла только уже в виде списка строк.

[Igors]

Имеется очень большой файл (из него берём по одной строке) и значительно меньше (в нём ищем строку). Можно наоборот, но тогда мы несколько раз бегаем по большому файлу. Я подумал что строки из небольшого файла (можно не все сразу, а частями в цикле допустим тоже, что бы не переполнять список) затолкать вообще в QStringList и раздать каждой нитке по экземпляру (закэшировать что ли), тогда мы один раз проходимся по большому файлу, а все поиски происходят в оперативке. Итого 1 раз читаем большой файл и 1 раз маленький. При этом каждый поток работает со своим экземпляром маленького файла только уже в виде списка строк.

В этом смысла нет - все уйдет на чтение большого файла и расфасовывание его в QStringList, нитки будут так, "для интерьера" 

[Пантер]

Полностью согласен с Igors. Можно еще отмапить файл в память и разделить его чтение между потоками.

[BRE]

Итого 1 раз читаем большой файл и 1 раз маленький. При этом каждый поток работает со своим экземпляром маленького файла только уже в виде списка строк.

Конечно, маленький файл должен быть загружен и распарсен один раз.
Вопросы возникают как лучше разделить большой файл на порции.
Первый вопрос это как разделить большой файл на куски, которые однозначно начинались с начала строки и заканчивались в конце, т.е. что бы граница блока никогда не могла попасть на середину предложения и тем более слова.
Здесь можно поступить так: принять константу blockSize равную, для примера, длине файла деленного на количество рабочих потоков.
blockSize = fileSize / threadNum;
Далее считать что первый блок начинается с начала файла (beginBlock = 0), а его конец будет по смещению blockSize (endBlock = blockSize). Далее двигаемся по файлу от позиции endBlock и ищем конец строки, как только нашли корректируем endBlock. Это же смещение становиться началом следующего блока, к которому прибавляется blockSize и ищется конец второго блока и т.д.
Второй вопрос в размере этих блоков. Как я написал выше, размер блока можно принять в зависимости от количества рабочих потоков, но может случиться так, что один поток уже закончить работу, а другой будет еще долго работать (в этом куске текста были постоянные совподения). Соответственно простаивающий поток никак не сможет помочь работающему. Наверное здесь лучше принудительно уменьшать размер блоков с постановкой их в очередь, из которой освободившиеся потоки смогут выбирать новые задания.

[Anarchist]

В этом смысла нет - все уйдет на чтение большого файла и расфасовывание его в QStringList, нитки будут так, "для интерьера" 

Да не большой файл в QStringList, а маленький и каждому потоку по экземпляру. Файлы кстати эти маленькие содержат по паре тысяч строк, 32 тысячи очень мало вероятно что превзойдёт (можно проверку поставить и в случае превышения попросить пользователя разбить файл). А читать кусками большой файл не понимаю всё же зачем. Можно же считать 1 строку и ждать пока освободится любой процесс. Эксперименты показали, что если дать задание одному потоку, а потом считать следующую строку из большого файла, то ещё и ожидать приходится пока поток завершится. Мне кажется недопонимание происходит. Обычно берут строку из маленького файла и шуруют искать в большом (в кусках), а я хотел перевернуть этот весь процесс.

Конечно, маленький файл должен быть загружен и распарсен один раз.

Вот и вопрос как? QThreadStorage?

Вопросы возникают как лучше разделить большой файл на порции.

Никак не пойму для чего же. Если можно подгружать по строке пока потоки работают, а работают они не так уж шустро как показала практика, вполне можно успеть считать ещё одну строку из большого файла.

[BRE]

Вот и вопрос как? QThreadStorage?

Да можно просто загрузить их в QStringList и в каждый поток передавать ссылку на него.
Это константные данные, потоки этот список все равно не изменяют.

Никак не пойму для чего же. Если можно подгружать по строке пока потоки работают, а работают они не так уж шустро как показала практика, вполне можно успеть считать ещё одну строку из большого файла.

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

[Anarchist]

Да можно просто загрузить их в QStringList и в каждый поток передавать ссылку на него.
Это константные данные, потоки этот список все равно не изменяют.

Просто получается чтение будет с одного объекта двумя потоками причём из разных мест, не пострадает ли скорость? Стоит ли использовать локеры или можно не заморачиваться ведь потоки будут только читать?

Если поиск получается заведомо медленней загрузки, то алгоритм можно изменить.
Один поток читает большой файл построчно, формирует задания из нескольких строк и кладет их в очередь. Рабочие потоки, по мере освобождения, выбирают из очереди новые задания.

Да так и есть один поток раздаёт строки другим. Может сумбурно в самом верхнем топике написал, но оно так и было задумано. А вот насчёт очереди это очень интересный совет. Использовать семафоры?

[BRE]

Просто получается чтение будет с одного объекта двумя потоками причём из разных мест, не пострадает ли скорость? Стоит ли использовать локеры или можно не заморачиваться ведь потоки будут только читать?

Локеры не нужны и скорость не пострадает.
IMHO, маленький файл лучше прочитать и слова положить в QSet, а в рабочем потоке доставать из строки очередное слово и проверять содержится ли оно в сете. Так будет быстрее.

Использовать семафоры?

Я бы использовал условные переменные (condition variable) - QWaitCondition.

[Anarchist]

IMHO, маленький файл лучше прочитать и слова положить в QSet, а в рабочем потоке доставать из строки очередное слово и проверять содержится ли оно в сете. Так будет быстрее.

Не получится так ибо маленький файл содержит подстроки которые могут (очень даже часто) быть частью слова из строки большого файла. Так бы конечно можно было применить потом contains и радоваться. Думаю был бы конечно очень большой прирост .

Я бы использовал условные переменные (condition variable) - QWaitCondition.

Можно пожалуйста поподробнее, а то я этот механизм не могу понять из того что прочитал.

[BRE]

Можно пожалуйста поподробнее, а то я этот механизм не могу понять из того что прочитал.

http://www.prog.org.ru/index.php?topic=14426.msg95463#msg95463