Russian Qt Forum

Здравствуйте. Никогда толком не имел дел с многопоточностью / параллельностью, а хотелось бы научиться.

Есть папка с n файлами. Требуется загрузить данные из каждого файла (файлы маленькие, не более 10 кб, нужных данных и того меньше), а потом провести перекрестное сравнение файлов (т.е. сравнить данные 1-го файла с 2,3,...,n и т.д.).

Сейчас у меня сделано очень банально: слот загрузки/обработки запускается через QtConcurrent::run(), а интерфейс обновляется через QMetaObject::invokeMethod(). Процессор при этом загружается на 30% (по ядрам не смотрел), а сам процесс отрабатывает крайне долго для 10к файлов. (даже для 500 файлов приходится ждать секунд 30)

Это можно как-то распараллелить и ускорить?

10 000 файлов * 10К = 100Мб, даже если таких файлов будет 100 000, то они все займут чуть больше 1Гб. Расходы на память приемлемые, поэтому не вижу причин отказываться от их загрузки в память и дальнейшем разборе уже без чтения с диска.
Поэтому, я бы разделил этот вопрос на два:
* параллельная загрузка всех файлов в память
* параллельная их обработка.
С какой начнем?

сейчас я так и делаю, только память на этих 10к вырастает до 400 МБ (это с учетом создания необходимых структур данных), но это нестрашно.
логично начать с первого пункта :)

Самый простой в реализации вариант с использованием  QtConcurrent.
Посмотрите пример Image Scaling Example, только вместо скалинга картинок загружайти файлы в QByteArray. Из коробки будет прогресс, сигнал окончания и коллекция результирующих буферов.
Тоже можно сделать руками, с организацией пула рабочих потоков, очередями заданий и средствами синхронизации или использовать openmp. :)

А в чем заключается сравнение? По размеру файла, по содержимому, или как-то хитро? Не верится в полчаса, пусть и на одной нитке

спасибо, попробую
хитро по содержимому :) файлы — это сохранения диабло 2, задача — поиск клонированных предметов.

пример посмотрел, оказывается все достаточно просто :)

обнаружилась одна проблема (код не трогал около года, забыл): первый шаг не распараллелить, потому что там используется синглтон для хранения данных о текущем загруженном файле. Этот функционал со сравнением файлов не является основным (им пользуется всего лишь один человек), поэтому переделывать синглтон не буду — слишком уж много возни получится.

теперь в шаге 2 имеется QHash<QString, QList> и нужно провести сравнение каждого с каждым (списки, естественно, сравниваются поэлементно). Можно ли разрезать хэш пополам и раздать сравнение 3-м потокам, которые будут сравнивать 1 с 1, 2 с 2 и 1 с 2? Или лучше как-то по-другому?

Multi-threading - отличное лекарство от синглтон и глобальных переменных вообще  :)

Надо стремиться к равномерной загрузке ниток, поэтому напрашивается аналогия с суммой арифметической прогрессии,
1 + 100
2 + 99
3 + 98
...
Так сразу известно число задач и они примерно равны. Рез-ты сравнения лучше писать в саму задачу, обходясь без всяких блокировок

то есть хэш разрезать на n/2 частей и на каждую выделить нить, которая будет проводить 3 сравнения?

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

Первая задача будет сравнивать первый файл со всеми остальными
Вторая задача будет сравнивать второй файл со всеми последующими + предпоследний с последним
Третья - третий файл со всеми последующими + 3 последних
и.т.д

Задаче надо знать только контейнер и 2 индекса с которых начинать

Вспомнилась мне точно такая же история. Нужно было в строго определенное время анализировать ~40000 техпроцессов (1 тп - 1 файл). Программа была написана задолго до меня в Delphi и отрабатывала за 2,5 часа. Руководству для принятия каких-то там решений оставалось 30 минут и попросили ускорить. Переписал все в Builder 2006 и результат получал через 40 минут. Все в восторге! Но какой то гвоздь в заднице не давал покоя и в одну  из новогодних ночей переписал все на чистом "С" без шаблонов, классов, с загрузкой файлов в память и расчета смещения указателей и все на 2-х потоках. Программа обсчитала все эти файлы за полторы минуты. Я в шоке! Руководство в испуге! Попросили больше таких программ не писать) Использование привычных классов будет вас тормозить.

Ну тут уже вопрос, стоит ли овчинка выделки?
Ну и да, вопрос сколько обрабатывать будет простой цикл?

это мне вопрос? ну время указано в первом посте

А есть возможность скинуть минимальный проект и файлы для обработки?
Я б тогда поковырялся.

трудно будет вычленить минимальный

тема создана не для «напишите мне», а «расскажите как правильно сделать и что почитать».вот это буду пробовать

Уж вас ли не знать, что наличие в руках непонятной фигни, увеличиваем шансы на разбор и правильный сбор этой фигни :D

по-моему всю необходимую информацию я предоставил: имеется хэш «строка-массив» (ну или просто массив массивов, непринципиально), необходимо поэлементно сравнить каждый массив с каждым, это сравнение я хочу распараллелить.

Ну я вообще то брал в расчёт все расходы - на чтение, на вычисление хеша и на сравнение.

PS я имел в виду дать данные для работы, эти 10к файлов или что там :D

так толку с файлов, если ты не знаешь как их читать (алгоритм там нетривиальный). а вычленить минимальный проект непросто, как я уже сказал.

главный затык в перекрестном сравнении (потому что много сравнивать), а что там внутри — неважно.

В случае когда 1-я задача в первом потоке будет сравнивать 1-й и 2-й файлы, а 2-я задача во втором потоке будет сравнивать 2-й и 3-й файлы, то два потока будут обращаться к одному и тому же 2-му массиву данных. Это приведет к снижению производительности.

Читать одно и то же могут хоть все нитки сразу. Это будет даже чуть шустрее за счет кеша процессора

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

При использовании QString и (я так подозреваю) "регулярки" о таких вещах говорить просто неприлично  :)

главный вопрос темы: как ускорить обработку, отсюда Q'стринги просто не применимы  :)

Давайте спокойнее относиться к моде/увлечениям молодежи  :)

мимо

http://bash.im/quote/438082

 :)

всем спасибо, все получилось. результаты (дебаг сборка без подключенного дебаггера):

• загрузка файлов и обработка по отдельности (эту часть я не менял):
  
  • 1000 файлов: 17 секунд
  • 10000 файлов: 220 секунд
• перекрестное сравнение:
  
  • 1000 файлов: 30 секунд => 13 секунд
  • 10000 файлов: 2850 секунд => 1420 секунд

в релиз сборке студией 2015 10к файлов обрабатывается чуть менее 3-х минут :) правда, тут машина чуть помощнее.

Наверное 4 ядра? Маловато КПД. Если интересно сравните с OMP, там главная забота - подключить либу, (в MSVC она есть), дальше так

C++ (Qt)
#pragma omp parallel for
for (int i = 0; i < task.size(); ++i)
 DoTask(task[i]);
 

Ну и воткнуть omp_set_num_threads на старте приложения

процессор 2.4GHz Intel Core i5, реальных 2 ядра, виртуальных — 4. но это дебаг сборка была (и под мак ос).
тут частота 2.8, ядер столько же.

омп может попробую, но позже. спасибо.

попробовал с омп с 4-мя потоками — по времени вышло столько же :)

а с 8-ю потоками вышло аж на 4 секунды быстрее.

Что-то не так. Частенько бывает что время съедается на индикаторе прогресса

я его отключил (выставил в неопределенное состояние) т.к. непонятно как там прогресс обновлять

результат каждого таска пишется в QTextBrowser, но у него я отключаю обновления до завершения обработки

Ну профайлить надо. По поводу прогресса: omp задействует и ту нитку из которой был parallel. Можно создать еще нитку и в ней уже parallel (чтобы оставить главную свободной). Но я всегда использую второй способ

C++ (Qt)
int prev = 0;
QAtomicInt numDone = 0;
#pragma omp parallel for
for (int i = 0; i < task.size(); ++i) {
 DoTask(task[i]);
 ++numDone;
 #pragma omp master
 {
   if (numDone > prev + 100) {
    UpdateUI(numDone);
    prev = numDone;
   }
  }
}
 

Обычно главной нитке и делать-то нечего кроме обновления прогресса, ну и пусть тоже считает, по ходу дела обновляя