Optimized but Way Out of Line

yesterday i showed the following profiler results.

the first place someone would look at optimizing is the caseinsensitivecomparator.compare call, right? that is clearly taking a really long time.

in fact, we re-wrote that method to use pointer magic in order to get it to work faster. but that isn’t the issue. look at the numbers . compare is called 68 million times. that means that under the profiler, it is still completing an operation in 0.000073 ms. i am not even sure what time unit that is .

however, we can see that the major caller for compare was findgreaterorequal, right? and that is called only 11 thousand times. what does this tells you?

that tells me we have a schlemiel the painter's algorithm . so i double checked, and skiplist insert perf should be o(logn) on average. but what we were seeing is o(n) costs .indeed, it appeared that we had a bug in which our skip list implementation would never do skips, essentially turning it into a sorted linked list, with insert perf of o(n). once we fixed that bug… well, things got better, a lot better.

as you can see, the cost of this went down really hard. and now we can focus on other stuff.