Описание алгоритма

Нам дан ориентированный ациклический граф (DAG). Для каждой вершины нужно посчитать значение как некоторую функцию от значений вершин, в которые из данной направлены рёбра. Из одной вершины может исходить несколько рёбер, в одну вершину может входить несколько рёбер.

Идея алгоритма проста -- обойти граф в порядке топологической сортировки и посчитать значение для каждой вершины. Такой порядок обхода гарантирует, что когда мы собираемся вычислить значение очередной вершины, значения вершин, от которых она зависит, уже вычислены.

Шаги алгоритма:

Снабдим каждую вершину счётчиком wait_for_dependecies_count - это количество вершин, в которые исходят рёбра и для которых нужно посчитать значение перед тем, как начать считать значение для данной вершины.
Будем складывать в очередь wait_for_process вершины, для которых уже можно вычислить значение.
Так как граф ациклический, то гарантированно есть вершины, у которых уже задано значение. Переберём все такие вершины. Для очередной вершины V пройдём по всем входящим в неё рёбрам и уменьшим wait_for_dependecies_count на 1 для достигнутых вершин (другими словами, для каждого ребра U -> V мы делаем U.wait_for_dependecies_count -= 1). Если для какой-то вершины wait_for_dependecies_count стало равно нулю, значит, для этой вершины можно вычислить значение, и мы помещаем её в очередь wait_for_process.
Теперь запускаем цикл: пока в очереди wait_for_process есть элементы:
1. Достаём из неё очередную вершину
2. Считаем её значение, суммируя значения по всем исходящим рёбрам
3. Проходим по всем входящим рёбрам и делаем то же самое, что и на шаге 3.
Если очередь опустела, значит, значения для всех вершин посчитаны

Итоги работы

Самый быстрый вариант, который мне удалось создать - это multi_thread_four_lf.cpp. Однако он отклоняется от требований задания, так как использует lock-free очередь MoodyCamel.
Самая быстрая реализация, в которой не используется сторонний код, - multi_thread_two_batches.cpp. Она использует мьютексы и подробно описана ниже в шаге 5.

Прирост от использования lock-free по сравнению с multi_thread_two_batches.cpp составил 19%. Это существенный результат, но не кратный. Поэтому я отказался от реализации собственной lock-free очереди, потому что моя очередь, написанная с нуля вряд ли сможет догнать готовую, в которую вложено немало человеко-часов. Так что в итоге я здесь осознанно отклонился от постановки задачи (не использовать сторонние библиотеки). Ниже, в шаге 9, я описываю, почему принял такое решение.

Далее по шагам идёт описание моего пути выполнения задания.

Ход работы

Описание общих деталей реализации

Вершина графа представлена классом Node, который лежит в файле graph.h. Она хранит два списка указателей на вершины:

dependencies_ -- это список вершин, в которые из данной исходят рёбра
dependent_ -- это список вершин, из которых рёбра входят в данную вершину

Сам граф мы представляем как std::deque<Node>. Выбор std::deque тут важен, потому что push_back в него не инвалидирует указатели на его элементы (а нам важна валидность указателей, так как в Node мы храним указатели на другие вершины).

Шаг 1 - однопоточное решение

Я начал с создания однопоточного решения, чтобы у меня был baseline, относительно которого я буду искать более быстрое решение.

Детали реализации:

Однопоточное решение использует в качестве очереди обычную std::queue.
Счётчик wait_for_dependecies_count был простым int'ом, но потом был заменён на std::atomic<int>, чтобы использовать один и тот же код класса Node и в многопоточной реализации, и в однопоточной.
Для подсчёта значения вершины используется функция int64_t CalculateNodeValue(const Node& cur) в файле graph.cpp.

Работа велась на ноутбуке с такими характеристиками:

CPU Intel(R) Core(TM) i7-9850H CPU @ 2.60GHz, 12 cores
32 GB RAM
CPU Caches:
- L1 Data 32 KiB (x6)
- L1 Instruction 32 KiB (x6)
- L2 Unified 256 KiB (x6)
- L3 Unified 12288 KiB (x1)

Обработка тестового примера однопоточным решением заняло 2,3 сек:

$ time cmake-build-release/spreadsheet st ~/Downloads/input.txt /dev/null

real	0m2,268s
user	0m2,224s
sys	0m0,044s

При этом профилирование показало, что бОльшую часть времени программа тратит на чтение графа. Значит, нужно создавать отдельные бенчмарки, чтобы замерять, сколько времени работает именно обработка графа.

   - 95,10% main
      + 78,35% ReadGraph
      + 9,03% CalculateValuesST
      + 6,73% std::deque<Node, std::allocator<Node> >::~deque
        0,54% std::__ostream_insert<char, std::char_traits<char> >

Шаг 2 -- лобовое многопоточное решение

Первый шаг к параллелизации решения - разбирать очередь wait_for_process не одним, а в несколько потоков. Я написал самую лобовую реализацию многопоточной очереди, чтобы не делать преждевременной оптимизации -- лучше пусть потом профилировщик покажет, где на самом деле узкое место.

Детали первой версии многопоточной реализации:

заводим атомарный счётчик nodes_left -- это количество вершин, для которых ещё нужно посчитать значение
очередь - это просто std::queue под мьютексом
создаём столько тредов, сколько возвращает std::thread::hardware_concurrency()
каждый поток выполняет активное ожидание:
- пока nodes_left > 0, он пытается достать что-то из очереди wait_for_process
- если не смог, пробует снова
- если смог, он вычисляет значение в этой вершине, уменьшает nodes_left на один и добавляет в очередь те вершины, для которых теперь нужно посчитать значение.

Обработка графа из примера таким многопоточным алгоритмом не дала видимого ускорения -- те же 2,3 секунды.

$ time cmake-build-release/spreadsheet mt ~/Downloads/input.txt /dev/null

real	0m2,317s
user	0m2,748s
sys	0m1,459s

Значит, пора делать бенчмарки

Шаг 3 -- бенчмарки

Я решил использовать библиотеку Google Benchmark. Созданные бенчмарки лежат в файле benchmark.cpp. Я решил сравнивать скорость работы однопоточной и многопоточной реализации на графах разных размеров. Для этого мне нужно было научиться генерировать графы. Я сделал это по следующему алгоритму:

Задаём число рёбер как число вершин, умноженное на случайное целое число от 2 до 10 - таким образом, значения большинства вершин надо будет вычислять и лишь для малой доли вершин оно будет задано заранее
Для каждого ребра выбираем два случайных индекса и проводим ребро из вершины с меньшим индексом в вершину с большим - так мы гарантируем, что у нас не будет циклов.

Для бенчмарков строим графы размером 100, 10 000 и 1 000 000 вершин. Последний используем, потому что во входном примере ~400 000 вершин, а в условии сказано, что тестировать решение будут на гораздо большем числе вершин.

Результаты первых бенчмарков:

--------------------------------------------------------------------
Benchmark                          Time             CPU   Iterations
--------------------------------------------------------------------
BM_SingleThread/100             1878 ns         1878 ns       365166
BM_SingleThread/10000         462438 ns       462412 ns         1592
BM_SingleThread/1000000    467379671 ns    467335524 ns            2
BM_MultiThreadOne/100         134245 ns       126392 ns         4782
BM_MultiThreadOne/10000      3172903 ns       454085 ns         1000
BM_MultiThreadOne/1000000  477720254 ns     65989520 ns           10

Как и предсказывалось в условии, если просто суммировать значения, многопоточное решение не даёт никакого выигрыша по времени, а на маленьких размерах графов ещё и работает медленнее, чем однопоточное. Поэтому добавляем в функцию суммирования задержку <= 4 мкс:

int64_t CalculateNodeValue(const Node& cur) {
  std::chrono::microseconds delay{std::hash<std::string>()(cur.Name()) % 5};
  std::this_thread::sleep_for(delay);
  ...
}

Тут важно, что в качестве значения задержки используется хеш от имени вершины - это сделано, чтобы для одной и той же вершины значение задержки было фиксировано. Так правильнее сравнивать между собой время работы разных реализаций.

Запускаем бенчмарки:

--------------------------------------------------------------------
Benchmark                          Time             CPU   Iterations
--------------------------------------------------------------------
BM_SingleThread/100           3075643 ns        61667 ns         1000
BM_SingleThread/10000       326684177 ns      6823492 ns           10
BM_SingleThread/1000000   39256600473 ns   1249976104 ns            1
BM_MultiThreadOne/100         1225298 ns       268965 ns         2606
BM_MultiThreadOne/10000      27541057 ns       472398 ns          100
BM_MultiThreadOne/1000000  3332736255 ns     57170263 ns            1

Отлично! Многопоточная реализация обогнала однопоточную. Теперь будем искать в ней узкие места и оптимизировать.

Шаг 4 -- поиск узкого места в многопоточной реализации

Для поиска узкого места я взял профайлер и прогнал под ним бенчмарк для графа на миллион вершин. Из-за того, что у меня совершенно тупая многопоточная реализация, можно ожидать, что потоки будут тонуть в contention'е за мьютекс - проверим.

Результат профилирования потока, в котором запущен бенчмарк

   - 100% CalculateValuesMT
      - 86,1% Node::SignalReady
        + <1% pthread_mutex_unlock
        + <1% pthread_mutex_lock

Результат профилирования потока в thread-pool'е:

   - 100% std::thread::_State_impl::_M_run
      + 74,6% CalculateNodeValue
      - 18,6% Node::SignalReady
        + 1,8% pthread_mutex_unlock
        + 1,8% pthread_mutex_lock
      + 1,7% pthread_mutex_unlock
      + 1,7% pthread_mutex_lock

Contention на мьютексе составляет менее 2% для потока бенчмарка и 6,8% для потока в thread-pool'е. С одной стороны, для нашей задачи и 6,8% времени имеют значение, но с другой стороны, для игрушечной задачи я бы здесь остановился.

Самое главное -- 3/4 времени наши потоки заняты полезной работой.

В таком виде мне стало неудобно профилировать свой код, потому что contention происходит в нескольких местах, поэтому я решил его чуть переделать.

Шаг 5 - локализую contention

Внесённые изменения можно посмотреть в файле multi_thread_two_batches.cpp:

ThreadSafeQueue получила метод PushMany, который позволяет положить в очередь несколько вершин, один раз захватив мьютекс - в этом есть смысл, так как в нашем алгоритме одна вершина может "активировать" сразу несколько
Потоки thread pool'а теперь собирают вектор вершин, которые надо добавить в очередь. Если в нём есть хотя бы одна вершина, то вместо того, чтобы брать очередную из очереди (и дёргать мьютекс), поток считает значение для неё (этакий work stealing). Если в векторе больше одного элемента, то все кроме первого разом добавляются в очередь.

Сравним производительность двух реализаций:

BM_SingleThread/100              3071125 ns        60102 ns         1000
BM_SingleThread/10000          326528424 ns      6682932 ns           10
BM_SingleThread/1000000      39216153675 ns   1214467602 ns            1
BM_MultiThreadOne/100            1202706 ns       257753 ns         2701
BM_MultiThreadOne/10000         27548549 ns       449086 ns          100
BM_MultiThreadOne/1000000     3342977526 ns     57070090 ns            1
BM_MultiThreadTwo/100            1250919 ns       268887 ns         2562
BM_MultiThreadTwo/10000         27485928 ns       476922 ns          100
BM_MultiThreadTwo/1000000     3306004430 ns     65153943 ns            1

Вообще никаких отличий! Хотя вроде бы contention стал ниже. Но с такой реализацией стало проще изучать долю contention'а в общем времени работы.

Шаг 6 - изучене влияния числа потоков на время работы

До этого я всё время использовал столько потоков, сколько возвращала функция std::thread::hardware_concurrency(). Я решил поисследовать, ускоряется ли мой алгоритм с ростом числа потоков и при каком числе потоков скорость работы будет максимальна. Для этого я стал передавать число потоков в функцию CalculateValuesMtBatches. Результаты бенчмарков на графе из миллиона вершин:

Benchmark                             Time             CPU    Speedup
---------------------------------------------------------------------
BM_MultiThreadTwo/4/1000000   9913444557 ns     59458579 ns      1,00
BM_MultiThreadTwo/8/1000000   4998137057 ns     58802435 ns      1,98
BM_MultiThreadTwo/12/1000000  3346757563 ns     59905520 ns      2,96
BM_MultiThreadTwo/16/1000000  2171970451 ns     60086186 ns      4,56
BM_MultiThreadTwo/24/1000000  1379291958 ns     60952688 ns      7,19
BM_MultiThreadTwo/32/1000000  1030740740 ns     60964580 ns      9,62
BM_MultiThreadTwo/64/1000000   580532986 ns     61450913 ns     17,08
BM_MultiThreadTwo/96/1000000   463265034 ns     61542860 ns     21,40
BM_MultiThreadTwo/128/1000000  422032613 ns     62180239 ns     23,49
BM_MultiThreadTwo/192/1000000  407823751 ns     63376141 ns     24,31
BM_MultiThreadTwo/256/1000000  375420144 ns     63811802 ns     26,41
BM_MultiThreadTwo/320/1000000  374205102 ns     65911192 ns     26,49
BM_MultiThreadTwo/384/1000000  416985510 ns     66702139 ns     23,77
BM_MultiThreadTwo/448/1000000  425703722 ns     66744354 ns     23,29
BM_MultiThreadTwo/512/1000000  451327446 ns     68729726 ns     21,97

Видно, что до 64 потоков скорость растёт пропорционально росту числа потоков. Затем рост замедляется и максимальная скорость достигается на 256 потоков.

Шаг 7 - профилируем реализацию, которая использует 256 потоков

Запускаем профилирование бенчмарка BM_MultiThreadTwo/256/1000000, так как на предыдущем шаге он работал быстрее всех.

Результат профилирования потока, в котором запущен бенчмарк

   - 100% CalculateValuesMT
      +  3,3% libstdc++.so.6.0.25`std::thread::_M_start_thread
      +  1,2% libstdc++.so.6.0.25`std::thread::join

Не видно узких мест, которые стоило бы оптимизировать. Результат профилирования потока в thread-pool'е:

   - 100% std::thread::_State_impl::_M_run
      + 58,3% libpthread-2.27.so`__pthread_mutex_lock
      + 33,3% benchmark`CalculateNodeValue
      +  8,3% libpthread-2.27.so`__pthread_mutex_unlock

Вот здесь явно виден contention. В некоторых тредах картина немного отличается, но в среднем треды проводят 40% времени, ожидая мьютекс. Этот contention стоит попробовать снизить.

Шаг 8 - пробую снизить contention, добавив в очередь work-stealing.

Переделываю очередь следующим образом (см. multi_thread_three_work_stealing_queue.cpp):

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

Идея в том, что до этого все треды ломились в один и тот же мьютекс, теперь они обращаются каждый к своему и иногда к другим. Должны получиться более гранулярные блокировки, и это должно снизить contention.

Запускаем benchmark, сравнивая получившуюся реализацию (BM_MultiThreadThree) с предыдущей - BM_MultiThreadTwo:

Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_MultiThreadTwo/4/10000         90070249 ns       933818 ns          100
BM_MultiThreadTwo/8/10000         46100368 ns      1240137 ns          100
BM_MultiThreadTwo/16/10000        18799224 ns       723138 ns          934
BM_MultiThreadTwo/24/10000        12292196 ns       838651 ns         1108
BM_MultiThreadTwo/32/10000         9695942 ns       860625 ns          768
BM_MultiThreadTwo/64/10000        43440558 ns      1290578 ns          100
BM_MultiThreadTwo/96/10000        83301210 ns      1862511 ns          100
BM_MultiThreadTwo/128/10000      112976239 ns      2460450 ns          100
BM_MultiThreadTwo/256/10000      183359273 ns      4832319 ns          100
BM_MultiThreadTwo/320/10000      187017435 ns      5944167 ns          117

BM_MultiThreadThree/4/10000       91200565 ns      1012644 ns          100
BM_MultiThreadThree/8/10000       46689517 ns       991916 ns          100
BM_MultiThreadThree/16/10000      19436456 ns       799340 ns          854
BM_MultiThreadThree/24/10000      14029025 ns      1142376 ns          990
BM_MultiThreadThree/32/10000       9842682 ns       931137 ns          833
BM_MultiThreadThree/64/10000      12030165 ns      1308299 ns          537
BM_MultiThreadThree/96/10000      47024828 ns      1875291 ns          100
BM_MultiThreadThree/128/10000     78205789 ns      2475460 ns          100
BM_MultiThreadThree/256/10000     59002981 ns      4819786 ns          100
BM_MultiThreadThree/320/10000     40525460 ns      5889576 ns          117

BM_MultiThreadTwo/4/1000000    10984791439 ns     59339145 ns            1
BM_MultiThreadTwo/8/1000000     5439683904 ns     58683609 ns            1
BM_MultiThreadTwo/16/1000000    2247885529 ns     74152963 ns           11
BM_MultiThreadTwo/24/1000000    1427016225 ns     80602437 ns           12
BM_MultiThreadTwo/32/1000000    1074384116 ns     71447333 ns            9
BM_MultiThreadTwo/64/1000000     616181140 ns     62649993 ns           11
BM_MultiThreadTwo/96/1000000     493116493 ns     63177699 ns           11
BM_MultiThreadTwo/128/1000000    440103043 ns     63735249 ns           11
BM_MultiThreadTwo/256/1000000    402344611 ns     65972157 ns           11
BM_MultiThreadTwo/320/1000000    401730530 ns     67988334 ns           10

BM_MultiThreadThree/4/1000000  22951292970 ns     58274262 ns            1
BM_MultiThreadThree/8/1000000   5864964838 ns     64410561 ns            1
BM_MultiThreadThree/16/1000000  2273127116 ns     73009905 ns           10
BM_MultiThreadThree/24/1000000  1472573452 ns     78480590 ns           12
BM_MultiThreadThree/32/1000000  1085506992 ns     74733781 ns           11
BM_MultiThreadThree/64/1000000   613088504 ns     62917152 ns           11
BM_MultiThreadThree/96/1000000   493710274 ns     62985075 ns           11
BM_MultiThreadThree/128/1000000  449409039 ns     63647684 ns           11
BM_MultiThreadThree/256/1000000  416271716 ns     67062698 ns           11
BM_MultiThreadThree/320/1000000  412646388 ns     68171604 ns           10

Для графа из 10000 вершин самое быстрое время работы происходит на 32 потоках. Для графа из 1 000 000 вершин минимум времени достигается на 256 потоках. Видим, что новый подход не дал никакого заметного ускорения.

Шаг 9 - пробую снизить contention за счёт отказа от мьютексов

Гранулярные блокировки не помогли снизить время доступа к очереди, поэтому пробую использовать lock-free очередь. В задании сказано, что нельзя использовать сторонние библиотеки, но я для начала хочу взять готовую lock-free очередь, чтобы просто понять, насколько существенный выигрыш она может дать. Поискал в Интернете и нашёл MoodyCamel. Автор пишет, что это "An industrial-strength lock-free queue for C++". Пробуем - multi_thread_four_lf.cpp.

Запустил benchmark'и и сравнил производительность с наилучшей на данный момент реализацией - MultiThreadTwo:

Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_MultiThreadTwo/4/10000         90070249 ns       933818 ns          100
BM_MultiThreadTwo/8/10000         46100368 ns      1240137 ns          100
BM_MultiThreadTwo/16/10000        18799224 ns       723138 ns          934
BM_MultiThreadTwo/24/10000        12292196 ns       838651 ns         1108
BM_MultiThreadTwo/32/10000         9695942 ns       860625 ns          768
BM_MultiThreadTwo/64/10000        44076507 ns      1254516 ns          100
BM_MultiThreadTwo/96/10000        80962154 ns      1757622 ns          100
BM_MultiThreadTwo/128/10000      112227618 ns      2349964 ns          100
BM_MultiThreadTwo/256/10000      180947092 ns      4603333 ns          100
BM_MultiThreadTwo/320/10000      189560039 ns      5676955 ns          123

BM_MultiThreadFour/4/10000        93331815 ns      1075886 ns          100
BM_MultiThreadFour/8/10000        47777764 ns      1167666 ns          100
BM_MultiThreadFour/16/10000       23190697 ns      1312026 ns          989
BM_MultiThreadFour/24/10000       16024090 ns      1443542 ns          806
BM_MultiThreadFour/32/10000       10717162 ns       832750 ns          696
BM_MultiThreadFour/64/10000        6579564 ns      1031378 ns          685
BM_MultiThreadFour/96/10000        5548252 ns      1431726 ns          491
BM_MultiThreadFour/128/10000       5488744 ns      1897883 ns          370
BM_MultiThreadFour/256/10000       7587288 ns      3937570 ns          177
BM_MultiThreadFour/320/10000       9021093 ns      5257087 ns          135

BM_MultiThreadTwo/4/1000000    10984791439 ns     59339145 ns            1
BM_MultiThreadTwo/8/1000000     5439683904 ns     58683609 ns            1
BM_MultiThreadTwo/16/1000000    2247885529 ns     74152963 ns           11
BM_MultiThreadTwo/24/1000000    1427016225 ns     80602437 ns           12
BM_MultiThreadTwo/32/1000000    1074384116 ns     71447333 ns            9
BM_MultiThreadTwo/64/1000000     605014737 ns     62570456 ns           11
BM_MultiThreadTwo/96/1000000     480468077 ns     63009257 ns           11
BM_MultiThreadTwo/128/1000000    427856664 ns     63553556 ns           11
BM_MultiThreadTwo/256/1000000    385885706 ns     65443285 ns           11
BM_MultiThreadTwo/320/1000000    380470911 ns     67240556 ns           11

BM_MultiThreadFour/4/1000000   11033062765 ns     61306083 ns            1
BM_MultiThreadFour/8/1000000    5481073865 ns     83530244 ns            1
BM_MultiThreadFour/16/1000000   2288351761 ns     77042461 ns           12
BM_MultiThreadFour/24/1000000   1482883760 ns     86840403 ns           11
BM_MultiThreadFour/32/1000000   1075002681 ns     73552448 ns           11
BM_MultiThreadFour/64/1000000    597630071 ns     76212218 ns           11
BM_MultiThreadFour/96/1000000    458763186 ns     65961483 ns           11
BM_MultiThreadFour/128/1000000   390270721 ns     64871787 ns            9
BM_MultiThreadFour/256/1000000   311426226 ns     68358147 ns           11
BM_MultiThreadFour/320/1000000   326435317 ns     68407463 ns           10

Для графа из 10000 вершин реализация с мьютексом быстрее всего работает на 32 потоках, реализация с lock-free очередью - на 128. При этом ускорение за счёт использования lock-free очереди составляет (9695942-5488744)/9695942=43% - очень внушительно.

Но наш целевой кейс - это граф из 1 000 000 вершин. На нём обе реализации достигают минимума времени на 256 потоках, при этом прирост от использования lock-free составляет (385885706-311426226)/385885706=19% - очень хороший результат.

И вот здесь я решил остановиться. Если готовая lock-free очередь, в которую вложили немало человеко-часов работы, даёт выигрыш в 19%, то написанная мною с нуля (чтобы соответствовать заданию и не использовать сторонние библиотеки), вряд ли её догонит. К тому же lock-free всегда связано с большим количеством нетривиальных ошибок, поэтому создание своей очереди займёт у меня весьма приличное время.

Направления для дальнейшего улучшения

Используемая в финальной версии MoodyCamel - это general-purpose очередь. Стоит изучить её исходный код и поискать способы оптимизировать её под нашу конкретную задачу.
Во всех сравниваемых реализациях используется фиксированное число потоков. Можно поработать над реализацией, которая будет прикидывать требуемое количество потоков по размеру графа или динамически добавлять новые потоки, если существующих не хватает.
Сейчас функция суммирования использует sleep, чтобы однопоточная версия была медленнее. Отдельно стоит поисследовать, как будет вести себя время работы, если этот sleep убрать.
Сейчас при работе с атомиками используется std::memory_order_seq_cst. Можно ослабить требования к барьерам памяти и поисследовать, как это скажется на времени работы. Я до сих пор не делал этого, так как не видел в профайлере, чтобы код упирался в операции с атомиками.

Как проводить измерения

$ for i in st mt mtb mt_lf; do echo $i; time cmake-build-release/spreadsheet $i ~/Downloads/input.txt /dev/null; done
st

real	0m27,982s
user	0m2,852s
sys	0m0,210s
mt
Thread count is 12

real	0m4,290s
user	0m3,084s
sys	0m0,208s

Результаты финальных измерений

/home/ishfb/code/spreadsheet/cmake-build-release/benchmark
2021-08-09T12:41:37+03:00
Running /home/ishfb/code/spreadsheet/cmake-build-release/benchmark
Run on (12 X 3927.72 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x6)
  L1 Instruction 32 KiB (x6)
  L2 Unified 256 KiB (x6)
  L3 Unified 12288 KiB (x1)
Load Average: 2.18, 7.74, 4.86
--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_SingleThread/100                3070499 ns        59731 ns         1000
BM_SingleThread/10000            325972557 ns      6582379 ns           10
BM_SingleThread/1000000         39175909453 ns   1199626704 ns            1
BM_MultiThreadOne/100               626509 ns       180603 ns         3849
BM_MultiThreadOne/1000             2740442 ns       186977 ns         1000
BM_MultiThreadOne/10000           27821107 ns       443176 ns          100
BM_MultiThreadOne/1000000       3377339382 ns     56792805 ns            1
BM_MultiThreadTwo/64/10000        44076507 ns      1254516 ns          100
BM_MultiThreadTwo/96/10000        80962154 ns      1757622 ns          100
BM_MultiThreadTwo/128/10000      112227618 ns      2349964 ns          100
BM_MultiThreadTwo/256/10000      180947092 ns      4603333 ns          100
BM_MultiThreadTwo/320/10000      189560039 ns      5676955 ns          123
BM_MultiThreadTwo/64/1000000     605014737 ns     62570456 ns           11
BM_MultiThreadTwo/96/1000000     480468077 ns     63009257 ns           11
BM_MultiThreadTwo/128/1000000    427856664 ns     63553556 ns           11
BM_MultiThreadTwo/256/1000000    385885706 ns     65443285 ns           11
BM_MultiThreadTwo/320/1000000    380470911 ns     67240556 ns           11
BM_MultiThreadThree/64/10000      10361712 ns      1204652 ns          572
BM_MultiThreadThree/96/10000      42768310 ns      1717043 ns          100
BM_MultiThreadThree/128/10000     89142739 ns      2286593 ns          100
BM_MultiThreadThree/256/10000     68365592 ns      4450471 ns          100
BM_MultiThreadThree/320/10000     42265697 ns      5436026 ns          128
BM_MultiThreadThree/64/1000000   597903506 ns     63236668 ns           11
BM_MultiThreadThree/96/1000000   474134817 ns     63598775 ns           11
BM_MultiThreadThree/128/1000000  436311345 ns     63944414 ns           11
BM_MultiThreadThree/256/1000000  364880213 ns     67724616 ns           11
BM_MultiThreadThree/320/1000000  387112069 ns     69700351 ns           10
BM_MultiThreadFour/64/10000        6579564 ns      1031378 ns          685
BM_MultiThreadFour/96/10000        5548252 ns      1431726 ns          491
BM_MultiThreadFour/128/10000       5488744 ns      1897883 ns          370
BM_MultiThreadFour/256/10000       7587288 ns      3937570 ns          177
BM_MultiThreadFour/320/10000       9021093 ns      5257087 ns          135
BM_MultiThreadFour/64/1000000    597630071 ns     76212218 ns           11
BM_MultiThreadFour/96/1000000    458763186 ns     65961483 ns           11
BM_MultiThreadFour/128/1000000   390270721 ns     64871787 ns            9
BM_MultiThreadFour/256/1000000   311426226 ns     68358147 ns           11
BM_MultiThreadFour/320/1000000   326435317 ns     68407463 ns           10
BM_MultiThreadTwo/4/10000        90070249 ns       933818 ns          100
BM_MultiThreadTwo/8/10000        46100368 ns      1240137 ns          100
BM_MultiThreadTwo/16/10000       18799224 ns       723138 ns          934
BM_MultiThreadTwo/24/10000       12292196 ns       838651 ns         1108
BM_MultiThreadTwo/32/10000        9695942 ns       860625 ns          768
BM_MultiThreadTwo/4/1000000    10984791439 ns     59339145 ns            1
BM_MultiThreadTwo/8/1000000    5439683904 ns     58683609 ns            1
BM_MultiThreadTwo/16/1000000   2247885529 ns     74152963 ns           11
BM_MultiThreadTwo/24/1000000   1427016225 ns     80602437 ns           12
BM_MultiThreadTwo/32/1000000   1074384116 ns     71447333 ns            9
BM_MultiThreadThree/4/10000      91200565 ns      1012644 ns          100
BM_MultiThreadThree/8/10000      46689517 ns       991916 ns          100
BM_MultiThreadThree/16/10000     19436456 ns       799340 ns          854
BM_MultiThreadThree/24/10000     14029025 ns      1142376 ns          990
BM_MultiThreadThree/32/10000      9842682 ns       931137 ns          833
BM_MultiThreadThree/4/1000000  22951292970 ns     58274262 ns            1
BM_MultiThreadThree/8/1000000  5864964838 ns     64410561 ns            1
BM_MultiThreadThree/16/1000000 2273127116 ns     73009905 ns           10
BM_MultiThreadThree/24/1000000 1472573452 ns     78480590 ns           12
BM_MultiThreadThree/32/1000000 1085506992 ns     74733781 ns           11
BM_MultiThreadFour/4/10000       93331815 ns      1075886 ns          100
BM_MultiThreadFour/8/10000       47777764 ns      1167666 ns          100
BM_MultiThreadFour/16/10000      23190697 ns      1312026 ns          989
BM_MultiThreadFour/24/10000      16024090 ns      1443542 ns          806
BM_MultiThreadFour/32/10000      10717162 ns       832750 ns          696
BM_MultiThreadFour/4/1000000   11033062765 ns     61306083 ns            1
BM_MultiThreadFour/8/1000000   5481073865 ns     83530244 ns            1
BM_MultiThreadFour/16/1000000  2288351761 ns     77042461 ns           12
BM_MultiThreadFour/24/1000000  1482883760 ns     86840403 ns           11
BM_MultiThreadFour/32/1000000  1075002681 ns     73552448 ns           11

Process finished with exit code 0

ishfb / spreadsheet Goto Github PK

spreadsheet's Introduction

Описание алгоритма

Итоги работы

Ход работы

Описание общих деталей реализации

Шаг 1 - однопоточное решение

Шаг 2 -- лобовое многопоточное решение

Шаг 3 -- бенчмарки

Шаг 4 -- поиск узкого места в многопоточной реализации

Шаг 5 - локализую contention

Шаг 6 - изучене влияния числа потоков на время работы

Шаг 7 - профилируем реализацию, которая использует 256 потоков

Шаг 8 - пробую снизить contention, добавив в очередь work-stealing.

Шаг 9 - пробую снизить contention за счёт отказа от мьютексов

Направления для дальнейшего улучшения

Как проводить измерения

Результаты финальных измерений

spreadsheet's People

Contributors

Stargazers

Watchers

Recommend Projects

Recommend Topics

Recommend Org