timeout
timeout copied to clipboard
Optimization: Use LIST_ instead of TAILQ_.
According to the queue(3) manpage, TAILQ "operations run about 20% slower than lists". So using LIST_ instead ought to make our code much faster.
But this optimization comes at a nonzero cost to other aspects of the code. Notably:
-
When multiple items are added expiring all at the same time, they will no longer be triggered in exactly the same order in which they were added. (Since we have to add to lists at the head, whereas we could add to tailqs at the tail.)
-
We need to use more stack space in timeouts_update, since we can no longer concatenate many tailqs into one.
(Make sure to benchmark this before merging; it may not actually be worthwhile. I have looked at the generated code, but not benchmarked it. Also, I am not sure whether the issues I mention above make this patch a bad idea or not.)
This will conflict with #14; I'm happy to help with the merge if you want to take both.
Hm, we'd better be careful here. I just ran the benchmarks over master and all 3 of these branches, and to my surprise they don't show a very large improvement. (I wasn't very careful in my setup, though, so maybe better benchmark run would show results better.)
At least the stack requirement is fixed at compile time, but it gives me pause because
-
The space used here is easily in the 1-2KB range, or more.
-
Some people are using this in embedded projects, and this could be a surprising change. I myself will likely be using this library in an embedded project where KB of stack will actually matter for once.
-
I'm becoming more aware of special scenarios where even small amounts of stack space matters. For example, Go makes a costly switch to a special stack when invoking C routine via FFI, but perhaps some day this can be avoided for well-behaved C libraries with minimal stack requirements. (At least in this case we can still easily provide a maximum upper bound, but from the perspective of a dynamically loaded library it's not invariant like it is now.)
-
Some coroutine libraries for C can (or ideally should, at least) have small stacks on the order of just a couple KB. timeout.c squarely targets such scenarios.