Re:There are no good constant-time data structures
by eps on Wednesday December 03, 2014 @05:22AM
(#8692881)
It is actually quite trivial.
You simply align function running time to the worst case _so far_. Start with 0, put it through a warm-up cycle and use it to set a reasonable default. Cache the value between app's sessions, re-initialize when changing the setup.
Determining the the worst case amount of time is far from trivial. What's the slowest amount of time it takes lookup table based AES to decrypt a block?
The only answer to that question is to measure it a bunch, then pick some percentile and hope your margin of safety is sufficient. Or you could use a constant time algorithm to start and rely less on hope.