Микроконтроллеры

"Simple Timing Wheels" -- это какой-то испорченный пересказ на тему bucket queue. Для которых известно, что они хорошо работают когда там распределение равномерное и/или число приоритетов -- небольшое. В нашем случае числа большие (32-битное время, например) и распределение явно не равномерное, все таймеры могут свалиться в один bucket. "Since there may be many timers in any given slot, we maintain an ordered list of timers for each slot..." -- и здесь мы возвращаемся к 

исходной проблеме, как поддержать упорядоченный список. "Hierarchical Timing Wheels " -- это попытка изобрести то же дерево или кучу. Круг замкнулся.

В википедии даётся наводка (https://en.wikipedia.org/wiki/Bucket_queue) ускоряющая поиск нужного bucket'а, но внутри списка всё печально, о чём в твоей статье и говориться (O(n) на вставке или O(n) на планировании). А на прикладном уровне, допустим, возникло какое-то событие и оно запускает 1000 таймеров с одинаковым интервалом. И приплыли.

Приходит в голову мысль, в момент вставки к таймеру прибавлять небольшую рандомную величину (мы же гарантируем срабатывание не "вовремя", а "не раньше"). Тогда таймеры более-менее равномерно распределятся по bucket'ам. Или просто записывать в один из соседних более свободный bucket... (см. ниже)

Единственное что, вставка тут может быть -- lockless (для неупорядоченных списков). Что-то в этом есть! Только для популярных ARM-контроллеров Cortex-M0 оно не доступно (у них из атомиков только флаги, инструкция swap).

Интересно, кстати, вообще какие осмысленные алгориты можно делать на Cortex-M0. Только битовые, верней "байтовые" поля. И мьютекс можно сделать. Печально. У пиков и AVR тоже только swap. С другой стороны там можно быстренько запретить прерывания...

Развивая мысль дальше, почему бы тогда не сделать что-то вроде хеш-таблицы с открытой адресацией: массив на N элементов, где индекс таймера -- T % N, где T -- абсолютное время. И если ячейка занята -- класть в соседнюю... Понятно, что число таймеров в любой момент << N, иначе всё разваливается. Зато просто. При этом есть индекс таймера с минимальным временем, обновляется при каждой вставке. При удалении -- просматриваются следующие ячейки. В худшем случае все N-1... В среднем -- встретив ячейку которая отстоит по времени менее чем на N тиков можно понять, что можно останавливаться. Для маленьких N (максимум десятки) по-моему вполне вариант. Но не для больших...