A lot of this went over my head, but all of it was fun to read. I wish I had some time, or a work reason, to justify digging into some of these references, but bookmarked for later, in case the day comes. Thanks!
My approach to this is to just look at the worst case time (all constants included). Keeping a low worst case time also “composes” into low (but perhaps more importantly, predictable) worst case times for larger functions. If something looks like it runs slow then you can also check if any part breaks your assumptions about the maximum amount of time it should take.
In that case, you don’t have to try to second guess how your program (or C compiler) will be used (i.e., on what input distribution).
By accepting to “lose” this time difference between average and worst case, you can also get clear cut winners. For n cases in a switch statement,
linear search takes 2n
jump tables takes log(n) + 4
binary search takes log(n)
instructions in the worst case. This tells us what to do for large n. For small n, we can still look at the details of how many instructions the worst execution path will take for each approach (or even the best imaginable approach for worst case time).
Huffman search doesn’t apply since we don’t assume to know frequencies in advance.
This is more of a complimentary point to this post both because we still have to figure out the best thing to do for small n (and hard code it into the compiler) and the point that the compiler will optimize the switch statement on its own (so the programmer doesn’t have to) still hold. Although I do find it adds an extra level of indirection for reasoning about the code’s running time.
A lot of this went over my head, but all of it was fun to read. I wish I had some time, or a work reason, to justify digging into some of these references, but bookmarked for later, in case the day comes. Thanks!
Another paper on this topic, shared on Lobsters two years ago: “Branch Prediction and the Performance of Interpreters - Don’t Trust Folklore”: https://lobste.rs/s/dek4o5/branch_prediction_performance
My approach to this is to just look at the worst case time (all constants included). Keeping a low worst case time also “composes” into low (but perhaps more importantly, predictable) worst case times for larger functions. If something looks like it runs slow then you can also check if any part breaks your assumptions about the maximum amount of time it should take.
In that case, you don’t have to try to second guess how your program (or C compiler) will be used (i.e., on what input distribution).
By accepting to “lose” this time difference between average and worst case, you can also get clear cut winners. For n cases in a switch statement,
instructions in the worst case. This tells us what to do for large n. For small n, we can still look at the details of how many instructions the worst execution path will take for each approach (or even the best imaginable approach for worst case time).
Huffman search doesn’t apply since we don’t assume to know frequencies in advance.
This is more of a complimentary point to this post both because we still have to figure out the best thing to do for small n (and hard code it into the compiler) and the point that the compiler will optimize the switch statement on its own (so the programmer doesn’t have to) still hold. Although I do find it adds an extra level of indirection for reasoning about the code’s running time.
How is a jump table log(n)? Wouldn’t it be O(1)?
Yes, thank you! Its just a table lookup. And I think binary search might be 2 log(n) in general to compare and then jump.
Looks like its too late for me to edit though.