Confirmed users
753
edits
User:Bjacob/ArithmeticTimingDifferences: Difference between revisions
User:Bjacob/ArithmeticTimingDifferences (view source)
Revision as of 15:48, 4 November 2013
, 4 November 2013→Running the code
| (2 intermediate revisions by the same user not shown) | |||
| Line 52: | Line 52: | ||
The reason to compare these normal laws to the overall ''median'', not the overall ''mean'', is that the overall mean may fall in between the actual "normal" time range and some abnormal, much higher values obtained for certain operands. In that case, ''all'' actual timings would fall far away from the mean, which would cause all timings to be reported as abnormal! This problem is averted by using the median instead, which is by definition an actual timing, and is most stable in the face of outliers. | The reason to compare these normal laws to the overall ''median'', not the overall ''mean'', is that the overall mean may fall in between the actual "normal" time range and some abnormal, much higher values obtained for certain operands. In that case, ''all'' actual timings would fall far away from the mean, which would cause all timings to be reported as abnormal! This problem is averted by using the median instead, which is by definition an actual timing, and is most stable in the face of outliers. | ||
Times are measured by clock_gettime using CLOCK_THREAD_CPUTIME_ID. In other words, this is per-thread CPU time. This should be as resilient to perturbations as it gets, especially as the core benchmarking loop is free of I/O or syscalls (no malloc) and relies on only at most two cache lines (it only accesses a few bytes on the stack, and in the worst case they would extend | Times are measured by clock_gettime using CLOCK_THREAD_CPUTIME_ID. In other words, this is per-thread CPU time. This should be as resilient to perturbations as it gets, especially as the core benchmarking loop is free of I/O or syscalls (no malloc) and relies on only at most two cache lines (it only accesses a few bytes on the stack, and in the worst case they would extend across one cache line boundary). | ||
== Caveats == | == Caveats == | ||
| Line 71: | Line 71: | ||
== Running the code == | == Running the code == | ||
You can either build [https://github.com/bjacob/time-math | You can either build [https://github.com/bjacob/time-math the source code] or use [http://people.mozilla.org/~bjacob/ta/bin/ prebuilt binaries]. Note that only Linux is supported at the moment. | ||
The binaries should run on any Linux-based system: GNU/Linux, Android, Firefox OS. They are statically linked, so they don't have any dependency, not even on the standard library. | The binaries should run on any Linux-based system: GNU/Linux, Android, Firefox OS. They are statically linked, so they don't have any dependency, not even on the standard library. | ||
| Line 115: | Line 115: | ||
As expected, divisions are not constant-time whatsoever, not even on finite values, and not even on integer types. | As expected, divisions are not constant-time whatsoever, not even on finite values, and not even on integer types. | ||
=== Integer addition, subtraction and multiplication are universally constant-time === | === Integer addition, subtraction and multiplication are almost universally constant-time === | ||
But again, note that integer ''division'' isn't, and nor are any ''floating-point'' operations. | But again, note that integer ''division'' isn't, and nor are any ''floating-point'' operations. | ||
See below for a strange exception, where int64 subtraction is not constant time on some 32bit CPUs. | |||
== The hopefully interesting parts == | == The hopefully interesting parts == | ||