Оптимизация очереди тасков

 Пришло время оптимизировать очередь тасков для job/task system.

В идеале алгоритм выглядит так:

• Одна очередь на все потоки, чтобы таски, которые долго находятся в очереди смещались в ее начало и чаще проверялись на готовность к выполнению.
•  Потоки захватывают небольшие диапазоны в очереди и проверяют таски в нем, потом блокируют следующий свободный участок.
• Таски с зависимостями добавляются в конец очереди, таски без зависимостей добавляются ближе к началу, так как могут быть вополнены сразу же.

В итоге я перепробовал несколько алгоритмов:

1. Первоначальный вариант - std::vector защищенный мютексом и 0.5 - 1 очередь на поток. Мютекс используется только через try_lock, что предотвращает простаивание потока. Основная потеря производительности была на erase() при удалении таска из вектора. После замены вектора на самописную очередь все стало упираться в мютекс. Удвоение количества очередей и замена мютекса на атомик никак не повлияли и до 90% времени при поиске таска уходило на try_lock(). Здесь же был реализован work stealing - если в одной очереди не нашлось готового к выполнению таска, то идет поиск по другим очередям. 

2. Lock-free list оказался мало пригодным, так как один и тот же таск может проверяться из разных потоков, а compare_and_swap (CAS) для атомиков достаточно медленные, когда сразу несколько потоков пытаются поменять значение.

3. Тот же lock-free list, но для статичных массиов на 126 тасков, вместе с дополнительными данными получалось 1 Кб на блок. Отдельный блок можно было заблокировать через спинлок, причем сначала использовалось только чтение вместо CAS, что значительно увеличило производительность. Если блок заблокирован, то идет чтение атомика с указателем на следующий блок. Производительность увеличилась в 1.5 раза, так же обнаружилось, что алгоритм отлично самомасштабируется под любое количество потоков, в отличие от первого варианта. Профалер показал равномерную производительность всего алгоритма, в нем больше нечего оптимизировать.

Дальнейшие попытки оптимизации привели только к замедлению, поэтому пока остановился на этом простом варианте. Некоторые идеи, которые еще не пробовал:

• Каждый таск содержит список зависящих от него тасков. После завершения текущего таска идет проход по зависимым таскам и убирается один бит, как только битовое поле становится нулевым - таск готов к выполнению. Таким образом я могу получить список новых тасков без поиска по очереди.
• Использовать свой Lock-free аллокатор для блоков, что увеличит производительность при резком увеличении количества тасков.

Некоторые особенности оптимизации многопоточных алгоритмов:

• CAS для атомиков это все операции за исключением load/store.
• Несколько атомиков внутри блока на 64 байта по производительности не отличаются от одного атомика, это называется false sharing, поэтому все атомики надо выравнивать по 64 байта (std::hardware_destructive_interference_size)  для x86/x64 архитектур, на Apple M1 кэшлиния уже 128 байт.
• load() неизмененного атомика работает максимально быстро.
• Самый плохой случай когда все потоки делают CAS на одном атомике, по этой причине алгоритмы с битовым деревом оказываются намного медленее тупого перебора. Добавление и удаление элементов из связаного списка также медленное. Правильнее сделать статичный массив и раскидывать потоки по thread_id, внутри массива уже будет динамический список.
• Самый простой код чаще оказывается самым быстрым при многопоточном использовании и отлаживать его намного проще.