Russian Qt Forum

Qt => Многопоточное программирование, процессы => Тема начата: Anarchist от Декабрь 15, 2010, 17:03



Название: Многопоточный поиск подстроки
Отправлено: 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
Я бы крутил примерно так

Код
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


Название: 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();
allTasks.addTask(string);
qDebug() << "nakidal" << semaphore.available() << QThread::currentThread();
qDebug() << "tasklist size from main:" << allTasks.getSize() << QThread::currentThread();

В поисковых потоках:
Код:
do {
    string = Tasks->getTask();
    sem->release();
    qDebug() << "zabral" << QThread::currentThread();
    qDebug() << "tasklist size from thread:" << Tasks->getSize();
    ....
while (!stoped && (2 * QThread::idealThreadCount() != sem->available()));

Встаёт колом:

...
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
Побольше бы кода.

Это что за цикл такой?
Код
C++ (Qt)
do {
   ....
while (!stoped && (2 * QThread::idealThreadCount() != sem->available()));

Под инициализацией семафора, я имел ввиду то число, которое передается в конструкторе QSemaphore.


Название: Re: Многопоточный поиск подстроки
Отправлено: Anarchist от Декабрь 18, 2010, 07:12
Код:
#ifndef TASKING_H
#define TASKING_H

#include <QStringList>
#include <QWaitCondition>
#include <QMutex>
#include <QString>

class Tasking
{
public:
    Tasking();
    QString getTask();
    void addTask(QString string);
    void clear();
    int getSize();

private:
    QStringList stringList;
    QWaitCondition cond;
    QMutex mutex;
};

#endif // TASKING_H

Код:
#include "tasking.h"

Tasking::Tasking()
{
}

QString Tasking::getTask()
{
    QMutexLocker locker(&mutex);
    while(stringList.empty())
        //cond.wait(&mutex, ULONG_MAX);
        cond.wait(&mutex);

    return stringList.takeFirst();
}

void Tasking::addTask(QString newString)
{
    QMutexLocker locker(&mutex);
    stringList.append(newString);
    cond.wakeOne();
}

int Tasking::getSize()
{
    return stringList.size();
}

void Tasking::clear()
{
    QMutexLocker locker(&mutex);
    stringList.clear();
}

Код:
#ifndef SEARCHTHREAD_H
#define SEARCHTHREAD_H

#include <QThread>
#include <QStringList>
#include <QSemaphore>

class Tasking;

class SearchThread : public QThread
{
    Q_OBJECT
public:
    SearchThread(Tasking *allTasks, QStringList numberList, int direction, QSemaphore *semaphore, QThread *parent = 0);

signals:
    void write(QString);
    void ended();

public slots:
    void run();
    void stop();

private:
    volatile bool stoped;
    int direct;
    QString string;
    QStringList list;
    Tasking *Tasks;
    QSemaphore *sem;
};

#endif // SEARCHTHREAD_H

Код:
#include "searchthread.h"
#include "tasking.h"
#include <QDebug>
#include <QTextCodec>

SearchThread::SearchThread(Tasking *allTasks, QStringList smallList, int direction, QSemaphore *semaphore, QThread *parent) :
    QThread(parent)
{
    Tasks = allTasks;
    list = smallList;
    direct = direction;
    sem = semaphore;
    stoped = false;
}

void SearchThread::stop()
{
    stoped = true;
}

void SearchThread::run()
{
    do {
        string = Tasks->getTask();
        sem->release();
        qDebug() << "zabral" << QThread::currentThread();
        qDebug() << "tasklist size from thread:" << Tasks->getSize();

        //qDebug() << string << QThread::currentThread() << stoped;
        QTextCodec::setCodecForCStrings(QTextCodec::codecForName("Windows-1251"));

        for (int i = 0; i < list.size(); ++i) {
            if (-1 != string.indexOf(list[i]))
                emit write(string);
                break;
            }
        }
        emit ended();
    }
    while (!stoped && (2 * QThread::idealThreadCount() != sem->available()));
}

Код:
#ifndef MAINSEARCHTHREAD_H
#define MAINSEARCHTHREAD_H

#include <QThread>
#include <QStringList>
#include <QMutex>
#include <QWaitCondition>

class SearchThread;

class MainSearchThread : public QThread
{
    Q_OBJECT
public:
    MainSearchThread(QString bigFile,
                     QString smallFile,
                     QString outFile,
                     int direction,
                     QObject *parent = 0);

signals:
    void warning(const QString);
    void progress(int);
    void ended(bool);
    void ended(QString);
    void stop();

public slots:
    void write(QString);
    void counter();
    void cancel();

protected:
    void run();

private:
    QList<SearchThread*> threadList;

    volatile bool canceled;
    QString bigFileName;
    QString smallFileName;
    QString outFileName;
    int direct;
    volatile qint64 count;
    volatile qint64 bigSize;
    QStringList list;
    qint64 lineCount(const QString FileName);
};

#endif // MAINSEARCHTHREAD_H

Код:
#include "mainsearchthread.h"
#include "searchthread.h"
#include "tasking.h"
#include <QFile>
#include <QTextStream>
#include <QThread>
#include <QSemaphore>
#include <QDebug>

MainSearchThread::MainSearchThread(QString bigFile,
                                   QString smallFile,
                                   QString outFile,
                                   int direction,
                                   QObject *parent) :
    QThread(parent),
    canceled(false),
    count(0),
    bigSize(0)
{
    bigFileName = bigFile;
    smallFileName = smallFile;
    outFileName = outFile;
    direct = direction;
}

void MainSearchThread::cancel()
{
    canceled = true;
}

qint64 MainSearchThread::lineCount(const QString FileName)
{
  QFile File(FileName);
  if (!File.open(QIODevice::ReadOnly)) {
      emit warning(tr("Cannot read file %1:\n%2.").arg(File.fileName()).arg(File.errorString()));
      emit ended(tr("Error."));
      return -1;
  }

  char   buff[1024*128];
  qint64 lcount = 0;
  int    len;

  char prev = 0;
  char cur  = 0;
  for(;;) {
      if (canceled)
      {
          emit ended(tr("Canceled."));
          return -1;
      }

      len = File.read(buff, sizeof(buff));
      if (File.error()) return -1;
      if(!len) {break;}

      for (int i=0; i<len; ++i) {
          cur = buff[i];
          if      (cur  == 10) {++lcount;}
          else if (prev == 13) {++lcount;}
          prev = cur;
      }
  }
  if (cur == 13) {++lcount;}
  File.close();
  return lcount + 1;
}

void MainSearchThread::counter()
{
    count++;
    emit progress(count*100/bigSize);
}

void MainSearchThread::write(QString string)
{
    qDebug() << string;
    list.append(string);
}

void MainSearchThread::run()
{
    //определяем размер файла
    billingSize = lineCount(bigFileName);
    if ( -1 == bigSize)
        return;
    //проверка на открытие файла
    QFile bigFile(bigFileName);
    if (!bigFile.open(QIODevice::ReadOnly)) {
        emit warning(tr("Cannot read file %1:\n%2.").arg(bigFile.fileName()).arg(bigFile.errorString()));
        emit ended(tr("Error."));
        return;
    }
    //проверка открытия файла
    QFile smallFile(smallFileName);
    if (!smallFile.open(QIODevice::ReadOnly)) {
        emit warning(tr("Cannot read file %1:\n%2.").arg(smallFile.fileName()).arg(smallFile.errorString()));
        emit ended(tr("Error."));
        bigFile.close();
        return;
    }
    //берём строки из файла и кладём в список строк
    QTextStream numberStream(&smallFile);
    QStringList smallList;
    QString smallString;
    while (!smallStream.atEnd()) {
        //проверка на отмену
        if (canceled) {
            bigFile.close();
            smallFile.close();
            emit ended(true);
            emit ended(tr("Canceled."));
        }
        smallString = smallStream.readLine();
        //если строка пустая, то пропускаем её
        if ("" == smallString)
            continue;
        smallList.append(smallString);
    }

    Tasking allTasks; //создаём список заданий
    QSemaphore semaphore(2 * QThread::idealThreadCount()); //семафор для контроля раздачи заданий
    //QSemaphore semaphore(2); //семафор для контроля раздачи заданий
    //подготавливаем список потоков, раздаем списки и указатель на список заданий
    for (int i = 1; i <= QThread::idealThreadCount(); i++) {
        SearchThread *thread = new SearchThread(&allTasks, smallList, direct, &semaphore);
        connect(thread, SIGNAL(write(QString)), this, SLOT(write(QString)));
        connect(thread, SIGNAL(ended()), this, SLOT(counter()));
        connect(this, SIGNAL(stop()), thread, SLOT(stop()));
        threadList.append(thread);
        thread->start();
    }
    //устанавливаем счётчик строк в 0
    count = 0;
    //читаем построчно файл и раздаем строки списку потоков
    QTextStream bigStream(&bigFile);
    QString bigString;
    while (!bigStream.atEnd()) {
        //проверка на отмену
        if (canceled) {
            //очищаем список заданий
            allTasks.clear();
            //сообщаем об остановке
            emit stop();
            //ждем пока все потоки завершат выполнение
            for (int i = 1; i <= QThread::idealThreadCount(); i++) {
                threadList[i - 1]->wait();
            }
            bigFile.close();
            emit ended(true);
            emit ended(tr("Canceled."));
            return;
        }
        //читаем строку из файла
        bigString = bigStream.readLine();
        //если строка пустая, то пропускаем её
        if ("" == bigString)
            continue;

        semaphore.acquire();
        allTasks.addTask(bigString);
        qDebug() << "nakidal" << semaphore.available() << QThread::currentThread();
        qDebug() << "tasklist size from main:" << allTasks.getSize() << QThread::currentThread();
    }
    //необходимо сообщить потокам что всё
    emit stop();
    //ожидаем завершения всех потоков
    for (int i = 1; i <= QThread::idealThreadCount(); i++) {
        threadList[i - 1]->wait();
    }
    qDebug() << list;
    //закрываем файл
    bigFile.close();
    //открываем файл для записи найденых строк
    QFile outFile(outFileName);
    if (!outFile.open(QIODevice::WriteOnly)) {
        emit warning(tr("Cannot write file %1:\n%2.").arg(outFile.fileName()).arg(outFile.errorString()));
        return;
    }
    //записываем найденые строки
    QTextStream outStream(&outFile);
    for (int i = 0; i < list.size(); ++i)
        outStream << list[i] << "\r\n";

    outFile.close(); //закрываем файл с найдеными строками
    emit ended(true);
    emit progress(100);
    emit ended(tr("Sucsessfuly complited."));
}


Название: Re: Многопоточный поиск подстроки
Отправлено: BRE от Декабрь 18, 2010, 10:46
Перенеси семафор в класс Tasking, соответственно захват/освобождение этого семафора лучше выполнять в addTask/getTask.
В конструкторе Tasking, при создании семафора, указывай ему в качестве параметра необходимую максимальную длину очереди.
Ну и в цикле SearchThread::run убери эту проверку с количеством доступных ресурсов в семафоре.
Разберись как работают семафоры.



Название: Re: Многопоточный поиск подстроки
Отправлено: Anarchist от Декабрь 18, 2010, 10:54
То что перенести надо это понял, сделаю.

Код:
QSemaphore semaphore(2 * QThread::idealThreadCount()); //симофор для контроля раздачи заданий
Инициализирую как количество потоков умноженное на 2, что тут не так?

Цитировать
Ну и в цикле 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
Всё некогда было, вот выкладываю исходники. Может кто посмотрит и что умное подскажет. Приму все замечания и предложения к рассмотрению.