5 ms·

Ratas – A hierarchical timer wheel

79 points by panic 10y ago

rimantas 10y ago
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…
- sharken 10y ago
  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 https://en.wiktionary.org/wiki/ratas
  - Sharlin 10y ago
    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.
  - pisipisipisi 10y ago
    And Estonian..
  - jacobush 10y ago
    Ratt is steering wheel in Swedish. Bet its PIE.
  - rimantas 10y ago
    TIL. I had no idea, Lithuanina and Finnish being in different language groups that we can have same words :)
- ggambetta 10y ago
  I was also intrigued... it means "rats" in Spanish. I had no idea it meant anything in Lithuanian.
djwatson24 10y ago
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.
- jsnell 10y ago
  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.
daurnimator 10y ago
See also: http://25thandclement.com/~william/projects/timeout.c.html http://25thandclement.com/~william/projects/timeout.c.html
MichaelMoser123 10y ago
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).
morekozhambu 10y ago
rathas/ratha Actually means a chariot (horse powered, two wheeled, for warfare) in Sanskrit rat ("t" pronounced as dental) means wheel

79 points by panic 10y ago

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…

sharken 10y ago
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 https://en.wiktionary.org/wiki/ratas
- Sharlin 10y ago
  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.
- pisipisipisi 10y ago
  And Estonian..
- jacobush 10y ago
  Ratt is steering wheel in Swedish. Bet its PIE.
- rimantas 10y ago
  TIL. I had no idea, Lithuanina and Finnish being in different language groups that we can have same words :)
ggambetta 10y ago
I was also intrigued... it means "rats" in Spanish. I had no idea it meant anything in Lithuanian.

djwatson24 10y ago

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.

jsnell 10y ago
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.

daurnimator 10y ago

See also: http://25thandclement.com/~william/projects/timeout.c.html http://25thandclement.com/~william/projects/timeout.c.html

MichaelMoser123 10y ago

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).

morekozhambu 10y ago

rathas/ratha Actually means a chariot (horse powered, two wheeled, for warfare) in Sanskrit rat ("t" pronounced as dental) means wheel