IRC channel logs


back to list of logs

<damo22>youpi: welcome back
<damo22> imagine an array bent into a circle, and each element is the head of a linked list. Each offset into the circle represents the time to an elapsing timer % circle size. So you can use this callwheel structure to insert elapsing timers into the future, and at each clock interrupt, you increment a counter and in constant time you can look up all the timers expiring at this tick. At worst, you have to traverse a small list to find the right
<damo22> timeout
<damo22>i tried implementing this algorithm for hurd mach_clock timers but its not working yet
<gnucode>damo22: that's an interesting data structure. Looks cool in my head.
<damo22>i did not invent this, its from a paper from 1995 by Costello and Varghese
<gnucode>damo22: It's still cool. :)