18 октября 2012 в 17:29

Ленивый map на Qt

Qt*
В Qt есть возможность параллельного выполнения вашей функции для каждого члена последовательности — QtConcurrent::mapped() и его друзья.

Проблема только в одном — результаты сохраняются в QVector. Поэтому, когда мне понадобилось выполнить свою функцию для 65 миллионов кусочков данных, я не стал мучать оперативку, а написал примерно то же самое, только более ленивое, то есть новые значения будут вычисляться, только если старые уже использовались.

Код: bitbucket.org/cblp/threadpool

Под капотом

ThreadPool наследует QThreadPool. Функция ThreadPool::map() принимает итератор в стиле Java на входе и функцию преобразования, возвращает итератор в стиле Java с результатами.

Ваша функция оборачивается в QRunnable и в количестве M=maxThreadCount штук (как правило, это количество процессоров) закидывается в QThreadPool.

FutureIterator предоставляет методы hasNext() и next(), которые возвращают следующий результат, если он есть, или блокируются, пока следующий результат не будет готов. Если M текущих задач выполнены, а за результатами никто не пришёл, вычислители блокируются.

Пример

Прочитать из стандартного ввода строки, от каждой посчитать N-кратный MD5 с солью, результат записать в стандартный вывод. (Это сильно изменённый пример из реальной жизни.)

const uint N = 10000;
const QString Salt = "5417";

QByteArray md5_N_times(QString line)
{
    QByteArray data = line.toUtf8();
    for ( uint i = 0; i < N; ++i )
        data = QCryptographicHash::hash(Salt.toUtf8() + data, QCryptographicHash::Md5);
    return data;
}

int main()
{
    QTextStream input(stdin);
    QTextStream output(stdout);

    ThreadPool pool;

    FutureIterator<QByteArray> results = pool.map(
        QTextStreamIterator(input),
        md5_N_times
    );

    while ( results.hasNext() )
        output << results.next().toHex() << endl;

    return 0;
}


Всё это пока довольно сыро, например, нельзя запустить в одном бассейне несколько задач так, чтобы они друг другу не мешали. Можете предлагать свои улучшения.
Юрий Сыровецкий @cblp
карма
10,5
рейтинг 0,0
говорящий с машинами
Самое читаемое Разработка

Комментарии (5)

  • +1
    Мне кажется, краткое описание что и как у Вас работает, не помешало бы =).
    • 0
      Последовательный вызов моей функции (что именно — коммерческая тайна) на моих данных (65 млн кортежей) выполняется за полтора часа, а в 16 потоков — за полчаса. Думаю, узкое место — чтение и запись на диск. Что-то ещё описать?
      • +2
        Это, безусловно, прогресс, троекратное ускорение и прочее. Но.

        Статья вышла слишком сухой. «Я написал код. Вот ссылка. Вот пример.»

        Нет нормального описания самого алгоритма — вот в чём дело. Да, можно залезть в код и долго его вычитывать, но было бы приятнее и удобнее прочесть абзац-другой текста с его разъяснением.

        «Ленивый map» — очень расплывчатое понятие.
        • +1
          Описал принцип работы.

          А пример не сух, он даёт понятие об интерфейсе.
          • +1
            Интерфейс — это хорошо, но «под капотом» — интереснее )
            Спасибо!

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.