Ratas – A hierarchical timer wheel | Hacker News Reader

Ratas – A hierarchical timer wheel

snellman.net

79 pointspanic12 comments

rathas/ratha Actually means a chariot (horse powered, two wheeled, for warfare) in Sanskrit

rat ("t" pronounced as dental) means wheel

I was intrigued by the name—"ratas" means "wheel" in Lithuanian, but the author appeears to be from Switzerland and neither first nor last names are even remotely Lithuanian. Even more intriguing then…

Not so intriguing i think, ratas also means Wheel in Finnish which matches at least the authors first name. For reference: https://en.wiktionary.org/wiki/ratas

Indeed. Interesting it's from PIE via Lithuanian - I hadn't thought about it before but it is cognate with English rota, rotate via Latin.

And Estonian..

Ratt is steering wheel in Swedish. Bet its PIE.

TIL. I had no idea, Lithuanina and Finnish being in different language groups that we can have same words :)

I was also intrigued... it means "rats" in Spanish. I had no idea it meant anything in Lithuanian.

This version still has to tick, yes? The whole point of optimizing ticks-until-next-event is to support nohz tickless modes. "Optimizing for high occupancy" also means low granularity - since the more granular timeouts you need, the more likely buckets are to be empty.

It doesn't need to tick in the sense of being driven by a predictable timer interrupt, since it's totally agnostic to the actual time source. The primitive for finding out when the next event expires is there for anyone wanting to operate it in a nohz-like manner. It's just a different tradeoff: make insert/delete a little faster at the expense of making ticks-until-next-event a little slower.

This is perhaps coming from a very different direction than the kernel use case. There it's totally plausible to have no events expiring for a long time (like the next second), and there is real value in going completely idle for a long period (lower power use).

But there are application areas where this just isn't the case. For example applications doing poll mode network IO can't possibly afford to go idle for a second. Even a millisecond would be stretching it. There's just no value in being slightly faster at knowing whether the next expiring timer is in 100ms or 110ms. The application will be waking up far earlier than that no matter what.

To put numbers on it: my thinking is that if a timer tick is e.g. 20us (so 50 ticks per ms) and there are no events expiring in the next 10 ticks, the system load must be so low that it might as well be completely idle.

wow, the idea reminds me of epicycles (the Ptolemaean model of the solar system where he planets did loops within loops).

Now i wonder if you save a lot with having to promote all these entries from the outer wheel(s) to inner wheel, one option is to pick a large enough wheel size (so that the wheel would cover most typical timeouts) and just allow collisions in the timer buckets if a timeout requires more slots than the maximum size of the wheel (just would require you to do more checks when there are collisions).

Another problem is that one has to do a lot more work when you do a full revolution of the inner wheel (due to promotions within between the outer wheels); so that each tick does take a uniform amount of time.

Another point is that these linked lists + indirections are not very cache friendly; one could try to use some sort of unrolled list (however this will eat up more memory).

Reply on news.ycombinator.com