Название: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 15, 2010, 17:03 Имеются текстовые файлы очень больших объёмов (гигабайты). Пишу программу поиска в этих файлах строк из другого файла. Так как файлы очень большого объема то выполняется очень долго и соответственно появилось желание сделать многопоточный поиск. Алгоритм следующий:
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); } Название: Re: Многопоточный поиск подстроки Отправлено: Igors от Декабрь 15, 2010, 18:10 Я бы крутил примерно так
Код TSearchResult может быть напр таким Код Посчитал число кусков в файле (размер / число ниток) и дал каждой нитке по куску Код Придется правда проверить участки "между кусками", но это можно сделать той же ф-цией ScanFile. В конце слил бы result из всех job Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 15, 2010, 21:27 Я уже думал над тем что бы разбить и дать каждому потоку по куску, но если один поток будет медленнее свой кусок обрабатывать, то остальные будут простаивать. Конечно потеря совсем не значительная, но таких поисков будет очень много. Я хотел просто давать не кусок, а сразу весь список (в конструкторе) и строку которую искать (уже потом) потоку, соответственно следующему потоку так же весь список, но уже следующую строку которую искать и т.д. Потом дожидаться когда какой либо из потоков завершит выполнение и снова загружать его работой. При таком подходе потоки будут постоянно загружены и легко реализовать остановку процесса так как потокам не нужно сообщать об остановке, а достаточно остановить цикл и дождаться пока все всё доделают. Но вот как раз не могу понять как реализовать ожидание пока какой либо поток будет свободен и не понятно что будет если я передам в конструкторе потока список строк, у каждого потока будет свой экземпляр или надо кэшировать. Если не разберусь, то похоже придётся реализовывать вариант с разбиением на куски.
Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 15, 2010, 21:36 При варианте с кусками отмена произойдёт ещё быстрее конечно, тут я что то не подумал :), но вариант с раздаванием каждому своей строки мне кажется более привлекательным.
Название: Re: Многопоточный поиск подстроки Отправлено: Igors от Декабрь 15, 2010, 21:49 При варианте с кусками отмена произойдёт ещё быстрее конечно, тут я что то не подумал :), но вариант с раздаванием каждому своей строки мне кажется более привлекательным. Совсем нет - ведь расходы на чтение файла (как минимум) не меньше расходов на поиск (особенно учитывая что файл будет читаться неск. нитками). Проще говоря I/O всегда медленнее процессора. Поэтому если уж загрузили кусок - нужно выжать из него все. Да и с общностью получше - а если надо искать аж одну строку - так что, работает 1 нитка?Примечание: не надо понимать буквально "каждая нитка грузит весь свой кусок (часть файла) в память". Нет, каждая нитка тоже загружает порциями, напр 1 Mb Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 15, 2010, 22:25 Имеется очень большой файл (из него берём по одной строке) и значительно меньше (в нём ищем строку). Можно наоборот, но тогда мы несколько раз бегаем по большому файлу. Я подумал что строки из небольшого файла (можно не все сразу, а частями в цикле допустим тоже, что бы не переполнять список) затолкать вообще в QStringList и раздать каждой нитке по экземпляру (закэшировать что ли), тогда мы один раз проходимся по большому файлу, а все поиски происходят в оперативке. Итого 1 раз читаем большой файл и 1 раз маленький. При этом каждый поток работает со своим экземпляром маленького файла только уже в виде списка строк.
Название: Re: Многопоточный поиск подстроки Отправлено: Igors от Декабрь 15, 2010, 22:33 Имеется очень большой файл (из него берём по одной строке) и значительно меньше (в нём ищем строку). Можно наоборот, но тогда мы несколько раз бегаем по большому файлу. Я подумал что строки из небольшого файла (можно не все сразу, а частями в цикле допустим тоже, что бы не переполнять список) затолкать вообще в QStringList и раздать каждой нитке по экземпляру (закэшировать что ли), тогда мы один раз проходимся по большому файлу, а все поиски происходят в оперативке. Итого 1 раз читаем большой файл и 1 раз маленький. При этом каждый поток работает со своим экземпляром маленького файла только уже в виде списка строк. В этом смысла нет - все уйдет на чтение большого файла и расфасовывание его в QStringList, нитки будут так, "для интерьера" :)Название: Re: Многопоточный поиск подстроки Отправлено: Пантер от Декабрь 15, 2010, 22:41 Полностью согласен с Igors. Можно еще отмапить файл в память и разделить его чтение между потоками.
Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 15, 2010, 23:03 Итого 1 раз читаем большой файл и 1 раз маленький. При этом каждый поток работает со своим экземпляром маленького файла только уже в виде списка строк. Конечно, маленький файл должен быть загружен и распарсен один раз.Вопросы возникают как лучше разделить большой файл на порции. Первый вопрос это как разделить большой файл на куски, которые однозначно начинались с начала строки и заканчивались в конце, т.е. что бы граница блока никогда не могла попасть на середину предложения и тем более слова. Здесь можно поступить так: принять константу blockSize равную, для примера, длине файла деленного на количество рабочих потоков. blockSize = fileSize / threadNum; Далее считать что первый блок начинается с начала файла (beginBlock = 0), а его конец будет по смещению blockSize (endBlock = blockSize). Далее двигаемся по файлу от позиции endBlock и ищем конец строки, как только нашли корректируем endBlock. Это же смещение становиться началом следующего блока, к которому прибавляется blockSize и ищется конец второго блока и т.д. Второй вопрос в размере этих блоков. Как я написал выше, размер блока можно принять в зависимости от количества рабочих потоков, но может случиться так, что один поток уже закончить работу, а другой будет еще долго работать (в этом куске текста были постоянные совподения). Соответственно простаивающий поток никак не сможет помочь работающему. Наверное здесь лучше принудительно уменьшать размер блоков с постановкой их в очередь, из которой освободившиеся потоки смогут выбирать новые задания. Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 16, 2010, 06:42 В этом смысла нет - все уйдет на чтение большого файла и расфасовывание его в QStringList, нитки будут так, "для интерьера" :) Да не большой файл в QStringList, а маленький и каждому потоку по экземпляру. Файлы кстати эти маленькие содержат по паре тысяч строк, 32 тысячи очень мало вероятно что превзойдёт (можно проверку поставить и в случае превышения попросить пользователя разбить файл). А читать кусками большой файл не понимаю всё же зачем. Можно же считать 1 строку и ждать пока освободится любой процесс. Эксперименты показали, что если дать задание одному потоку, а потом считать следующую строку из большого файла, то ещё и ожидать приходится пока поток завершится. Мне кажется недопонимание происходит. Обычно берут строку из маленького файла и шуруют искать в большом (в кусках), а я хотел перевернуть этот весь процесс. Конечно, маленький файл должен быть загружен и распарсен один раз. Вот и вопрос как? QThreadStorage? Вопросы возникают как лучше разделить большой файл на порции. Никак не пойму для чего же. Если можно подгружать по строке пока потоки работают, а работают они не так уж шустро как показала практика, вполне можно успеть считать ещё одну строку из большого файла. Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 16, 2010, 07:30 Вот и вопрос как? QThreadStorage? Да можно просто загрузить их в QStringList и в каждый поток передавать ссылку на него.Это константные данные, потоки этот список все равно не изменяют. Никак не пойму для чего же. Если можно подгружать по строке пока потоки работают, а работают они не так уж шустро как показала практика, вполне можно успеть считать ещё одну строку из большого файла. Если поиск получается заведомо медленней загрузки, то алгоритм можно изменить.Один поток читает большой файл построчно, формирует задания из нескольких строк и кладет их в очередь. Рабочие потоки, по мере освобождения, выбирают из очереди новые задания. Тут возможно, что читающий поток будет забивать очередь заданий очень быстро, а рабочие потоки не будут успевать их выбирать из очереди. Тогда придется ограничивать читающую очередь и принудительно ее усыплять, если в очереди накопится большое количество данных. Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 16, 2010, 07:38 Да можно просто загрузить их в QStringList и в каждый поток передавать ссылку на него. Это константные данные, потоки этот список все равно не изменяют. Просто получается чтение будет с одного объекта двумя потоками причём из разных мест, не пострадает ли скорость? Стоит ли использовать локеры или можно не заморачиваться ведь потоки будут только читать? Если поиск получается заведомо медленней загрузки, то алгоритм можно изменить. Один поток читает большой файл построчно, формирует задания из нескольких строк и кладет их в очередь. Рабочие потоки, по мере освобождения, выбирают из очереди новые задания. Да так и есть один поток раздаёт строки другим. Может сумбурно в самом верхнем топике написал, но оно так и было задумано. А вот насчёт очереди это очень интересный совет. Использовать семафоры? Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 16, 2010, 08:02 Просто получается чтение будет с одного объекта двумя потоками причём из разных мест, не пострадает ли скорость? Стоит ли использовать локеры или можно не заморачиваться ведь потоки будут только читать? Локеры не нужны и скорость не пострадает.IMHO, маленький файл лучше прочитать и слова положить в QSet, а в рабочем потоке доставать из строки очередное слово и проверять содержится ли оно в сете. Так будет быстрее. Использовать семафоры? Я бы использовал условные переменные (condition variable) - QWaitCondition.Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 16, 2010, 09:15 IMHO, маленький файл лучше прочитать и слова положить в QSet, а в рабочем потоке доставать из строки очередное слово и проверять содержится ли оно в сете. Так будет быстрее. Не получится так ибо маленький файл содержит подстроки которые могут (очень даже часто) быть частью слова из строки большого файла. Так бы конечно можно было применить потом contains и радоваться. Думаю был бы конечно очень большой прирост :). Я бы использовал условные переменные (condition variable) - QWaitCondition. Можно пожалуйста поподробнее, а то я этот механизм не могу понять из того что прочитал. Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 16, 2010, 09:29 Можно пожалуйста поподробнее, а то я этот механизм не могу понять из того что прочитал. http://www.prog.org.ru/index.php?topic=14426.msg95463#msg95463Название: Re: Многопоточный поиск подстроки Отправлено: Igors от Декабрь 16, 2010, 11:57 Да не большой файл в QStringList, а маленький и каждому потоку по экземпляру. Не мудрите. Здесь лучше действовать по принципу "безобразно зато однообразно". Если файл мал - просто обрабатываем его меньшим числом ниток, совсем маленький - всего 1 ниткой. Это нормально, не все "масштабируется". Связываясь с QStringList Вы получаете массу ненужных проблем на свою голову. А если строки малы? (как в обычном текстовике). Тогда использование 2 и более ниток просто в минус. Значит надо как-то делить QStringList на пачки. и.т.д. и.т.п.Вообще время обсуждения уже давно превысило время реализации :) Напишите рабочую ф-цию для поиска в куске - она нужна по-любому. Затем попробуйте запустить N ниток с этой ф-цией. А дальше видно будет - может все уже хорошо. А может будут др. проблемы которые сейчас не видны. К слову сказать, поиск без использования QString даст прирост более чем вдвое Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 16, 2010, 13:03 Тут возможно, что читающий поток будет забивать очередь заданий очень быстро, а рабочие потоки не будут успевать их выбирать из очереди. Тогда придется ограничивать читающую очередь и принудительно ее усыплять, если в очереди накопится большое количество данных. Может ссылка есть или так опишите? Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 16, 2010, 13:36 Может ссылка есть или так опишите? Семафор инициализируется значением максимальной длины очереди, например это может быть число рабочих поток умноженное на 2.При помещении задания в очередь этот семафор захватывает ресурс, при извлечении задания из очереди - освобождает. Читающий поток заполнит очередь (исчерпает количество ресурсов в семафоре) и заблокируется, до тех пор, пока очередной освободившийся поток не выдернет из очереди задание. Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 16, 2010, 15:04 Вообще время обсуждения уже давно превысило время реализации :) Реализация давно ведётся. Пока не реализован и не продуман даже механизм определения что поиск окончен и пора завершаться потокам и не реализован как раз метод заполнения очереди заданий порциями. Завтра потестирую время выполнения. Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 17, 2010, 22:38 В главном потоке пишу:
Код: semaphore.acquire(); В поисковых потоках: Код: do { Встаёт колом: ... zabral SearchThread(0x9a4f858) tasklist size from thread: 1 zabral SearchThread(0x9a4f858) tasklist size from thread: 0 nakidal 1 MainSearchThread(0x9a55b40) tasklist size from main: 1 MainSearchThread(0x9a55b40) nakidal 0 MainSearchThread(0x9a55b40) tasklist size from main: 2 MainSearchThread(0x9a55b40) И встаёт, потоки не забирают больше. Не подскажете в чём может быть дело? Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 17, 2010, 22:47 Побольше бы кода.
Это что за цикл такой? Код
Под инициализацией семафора, я имел ввиду то число, которое передается в конструкторе QSemaphore. Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 18, 2010, 07:12 Код: #ifndef TASKING_H Код: #include "tasking.h" Код: #ifndef SEARCHTHREAD_H Код: #include "searchthread.h" Код: #ifndef MAINSEARCHTHREAD_H Код: #include "mainsearchthread.h" Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 18, 2010, 10:46 Перенеси семафор в класс Tasking, соответственно захват/освобождение этого семафора лучше выполнять в addTask/getTask.
В конструкторе Tasking, при создании семафора, указывай ему в качестве параметра необходимую максимальную длину очереди. Ну и в цикле SearchThread::run убери эту проверку с количеством доступных ресурсов в семафоре. Разберись как работают семафоры. Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 18, 2010, 10:54 То что перенести надо это понял, сделаю.
Код: QSemaphore semaphore(2 * QThread::idealThreadCount()); //симофор для контроля раздачи заданий Цитировать Ну и в цикле SearchThread::run убери эту проверку с количеством доступных ресурсов в семафоре. Я посылаю сигнал остановки, но мне нужно что бы потоки доделали всё что в очереди лежит, вот и проверяю.Название: Re: Многопоточный поиск подстроки Отправлено: BRE от Декабрь 18, 2010, 11:10 Сейчас посмотрю твой код повнимательней, лучше будет, если выложишь компилябельный код.
Я набросал небольшой пример, посмотри. (Для сборки используется cmake, если его нет, то нужно будет сделать pro-файл) Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 18, 2010, 19:47 Спасибо огромное Вам. Посмотрел Ваш код и доработал свой, почерпнул много интересных мыслей. Немного отличается реализация, но основные идеи одинаковые. Мой код конечно побольше, просто содержит кучу проверок разных и взаимодействие с интерфейсом. Я его повылизываю хорошенько и выложу потом здесь. Сейчас он уже рабочий. Всё работает очень замечательно. Думаю "заказчик" будет очень доволен производительностью :).
Название: Re: Многопоточный поиск подстроки Отправлено: Waryable от Декабрь 20, 2010, 11:16 Если еще предложения принимаются, то есть такое:
1. список файлов для поиска в QStringList. 2. Каждый поток извлекает(и удаляет) из QStringList имя файла, и обрабатывает весь файл. 3. Алгоритм поиска строки довольно прост: для начала читай файл в QByteArray целиком, потом сравнивай побайтно строку поиска с байтами файла QByteArray. Не понимаю зачем делить содержимое файла на строки. Этож жеж сколько лишних трудов... Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Декабрь 20, 2010, 22:27 1. список файлов для поиска в QStringList. Файлов всего 2, в одном строки которые искать в другом где искать.Не понимаю зачем делить содержимое файла на строки. Этож жеж сколько лишних трудов... Файлы и так содержат строки. И каких же это трудов, когда есть QTextStream?Всё уже готово и проходит обкатку. Просто на работе всё, как-нибудь обязательно выложу. Название: Re: Многопоточный поиск подстроки Отправлено: Waryable от Декабрь 21, 2010, 06:03 Цитировать Файлы и так содержат строки. И каких же это трудов, когда есть QTextStream? Файлы содержат только байты. Строки между собой разделяются служебными байтами(или их комбинациями). Поэтому явно или неявно при чтении файла в текстовом режиме приходится искать конец каждой строки. Исходя из этих(и не только из этих) соображений, при загрузке файла в текстовом режиме класс QTextStream осуществляет различные "служебные" действия на все случаи жизни. Но, если эффективность приложения устраивает, то конечно удобней пользоваться готовыми решениями. Ну а если всетаки встанет вопрос о повышении эффективности возвращайся в тему! ;)Название: Re: Многопоточный поиск подстроки Отправлено: Anarchist от Январь 25, 2011, 09:41 Всё некогда было, вот выкладываю исходники. Может кто посмотрит и что умное подскажет. Приму все замечания и предложения к рассмотрению.
|