IRC channel logs
2023-08-03.log
back to list of logs
<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>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