Энтони Уильямс - Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

Листинг 8.10.Параллельная реализация алгоритма find()с применением std::async

template ← (1)

Iterator parallel_find_impl(Iterator first, Iterator last,

MatchType match,

std::atomic& done) {

try {

unsigned long const length = std::distance(first, last);

unsigned long const min_per_thread = 25; ← (2)

if (length < (2 * min_per_thread)) { ← (3)

for(; (first != last) && !done.load(); ++first) {← (4)

if (*first == match) {

done = true; ← (5)

return first;

}

}

return last; ← (6)

} else {

Iterator const mid_point = first + (length / 2); ← (7)

std::future async_result =

std::async(&parallel_find_impl,← (8)

mid_point, last, match, std::ref(done));

Iterator const direct_result =

parallel_find_impl(first, mid_point, match, done); ← (9)

return (direct_result == mid_point) ?

async_result.get() : direct_result; ← (10)

}

} catch (...) {

done = true; ← (11)

throw;

}

}

template

Iterator parallel_find(

Iterator first, Iterator last, MatchType match) {

std::atomic done(false);

return parallel_find_impl(first, last, match, done); ← (12)

}

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

Основная же ветвь кода не таит никаких неожиданностей. Как и во многих предыдущих реализациях, мы задаем минимальное количество элементов, обрабатываемых в одном потоке (2); если размер обеих половин диапазона меньше этой величины, то весь диапазон обрабатывается в текущем потоке (3). Собственно алгоритм сводится к простому циклу — он продолжается, пока не будет достигнут конец заданного диапазона или не установлен флаг done (4). При обнаружении совпадения мы устанавливаем флаг doneи выходим из функции (5). Если мы дошли до конца списка или вышли из цикла, потому что другой поток установил флаг done, то возвращаем значение last, означающее, что совпадение не найдено (6).

Если диапазон можно разбивать, то мы сначала находим среднюю точку (7), а потом через std::asyncзапускаем поиск во второй половине диапазона (8), не забыв передать ссылку на флаг doneс помощью std::ref. Одновременно мы просматриваем первую половину диапазона, рекурсивно вызывая себя же (9). И асинхронный, и рекурсивный вызов могут разбивать диапазон и дальше, если он достаточно велик.

Если прямой рекурсивный вызов вернул mid_point, значит, он не нашел совпадения, поэтому нужно получить результат асинхронного поиска. Если и в той половине ничего не было найдено, то мы получим last (10). Если «асинхронный» вызов на самом деле был не асинхронным, а отложенным, то выполняться он начнет именно при обращении к get(); в таком случае поиск во второй половине списке вообще не будет производиться, если поиск в первой оказался успешным. Если же асинхронный поиск действительно выполнялся в другом потоке, то деструктор переменной async_resultбудет ждать завершения этого потока, поэтому утечки потоков не произойдет.

Как и раньше, применение std::asyncгарантирует безопасность относительно исключений и распространения исключений вверх по стеку вызовов. Если прямой рекурсивный вызов возбудит исключение, то деструктор будущего результата позаботится о том, чтобы поток, в котором работал асинхронный поиск, завершился до возврата из функции. Если исключение возбудит асинхронный вызов, то оно распространится вверх при вызове get() (10). Внешний блок try/catchнужен только для того, чтобы установить флаг doneи обеспечить тем самым быстрое завершение всех потоков в случае исключения (11). Программа правильно работала бы и без этого, по продолжала бы сравнивать элементы до естественного завершения всех потоков.

Существенной особенностью обеих реализаций этого алгоритма (характерной и для других рассмотренных выше параллельных алгоритмов) является тот факт, что элементы могут обрабатываться не в том же порядке, что в стандартном алгоритме std::find. Это важный момент при распараллеливании любого алгоритма. Если порядок имеет значение, то обрабатывать элементы параллельно нельзя. В таких алгоритмах, как parallel_for_each, порядок обработки независимых элементов не важен, однако parallel_findможет вернуть элемент, найденный где-то в конце диапазона, хотя имеется другой такой же элемент в начале. Это может оказаться неприятной неожиданностью.