Ayende @ Rahien

My name is Oren Eini
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:


+972 52-548-6969

, @ Q c

Posts: 6,026 | Comments: 44,842

filter by tags archive

Optimized, but way out of line

time to read 2 min | 263 words

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.


Frank Quednau

Nice! btw, It's 73 nanoseconds.


I find the bottom-up view to be mostly useless. Top-down would have broken down the costs more clearly. Bottom-up tends to spread costs that logically belong together over many leaf methods.


dotTrace's display hierarchy looks confusing. Why is Next, FindGreaterOrEqual and Compare showing at the same level if one is calling the other? What's the order of execution.


Just wondering, what kind of "pointer magic" did you do to fix the CaseInsensitiveCompare?

Rob Lyndon

So would it be feasible to create a profiler with an inbuilt Schlemiel detector, rather like the Entity Framework Profiler's SELECT n + 1 detector?

Ayende Rahien

Rob, Sure, technically speaking, that is pretty easy to do.

Comment preview

Comments have been closed on this topic.


No future posts left, oh my!


  1. Technical observations from my wife (3):
    13 Nov 2015 - Production issues
  2. Production postmortem (13):
    13 Nov 2015 - The case of the “it is slow on that machine (only)”
  3. Speaking (5):
    09 Nov 2015 - Community talk in Kiev, Ukraine–What does it take to be a good developer
  4. Find the bug (5):
    11 Sep 2015 - The concurrent memory buster
  5. Buffer allocation strategies (3):
    09 Sep 2015 - Bad usage patterns
View all series


Main feed Feed Stats
Comments feed   Comments Feed Stats