Need Something Sorted? Sleep on It

Re:Need Something Sorted? Sleep on It by EquallyJust on Monday May 24, 2021 @08:55PM (#27271519)

Hashed hierarchical timing wheels is a cool very specialized data structure to make this efficient. The paper claims it's O(1) to start, stop and maintain timers which is much more efficient than O(log n).

Given there's n timers and O(1) operations I'm not sure where the O(n log n) fits in here. Possible in the minimum number of ticks?

http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing...

Production implementation: https://github.com/facebook/folly/blob/master/folly/io/async...

[ Parent | on HN ]

Re:Need Something Sorted? Sleep on It by klyrs on Monday May 24, 2021 @09:51PM (#27271838)

Probably this bit from section 5

> If we can guarantee that all timers are set for periods less than MaxInterval, this modified algorithm takes O(1) latency for START_TIMER, STOP_TIMER, and PER_TICK_BOOKKEEPING.

I think that puts this in the same class as counting sort.

[ Parent | on HN ]

Re:Need Something Sorted? Sleep on It by sly010 on Monday May 24, 2021 @10:48PM (#27272120)

The paper says it's essentially bucket sort. Which was also my thirst thought when I heard about sleep sort.

[ Parent | on HN ]