10

So I was looking through the implementation of SortedList<TKey, TValue> and the implementation of Add (which calls Insert shown below) really surprised me.

The Add method does the obvious binary search to determine the index in which the KVP should go, but the Insert seems as if it could be improved significantly (albeit on larger scales of course):

private void Insert(int index, TKey key, TValue value)
{
  if (this._size == this.keys.Length)
    this.EnsureCapacity(this._size + 1);
  if (index < this._size)
  {
    Array.Copy((Array) this.keys, index, (Array) this.keys, index + 1, this._size - index);
    Array.Copy((Array) this.values, index, (Array) this.values, index + 1, this._size - index);
  }
  this.keys[index] = key;
  this.values[index] = value;
  ++this._size;
  ++this.version;
}

If I'm reading this correctly, and I reserve the right to be wrong at all times, this is an O(2n) operation.

It seems to me that the values should be implemented with pointers. Kind of like a LinkedList in relation to the value from the key, but not linked in that it doesn't support random access. More so the key is simply linked to its value. The get operation wouldn't be any slower, and neither would the remove because we have the pointer, but the add operation would be O(n) now instead.

Can somebody shed some light on why the decision may have gone this direction?

Mike Perrenoud
  • 66,820
  • 29
  • 157
  • 232
  • 2
    Why don't you test both approach by writing your own custom `SortedList`. Your question would be only meaningful if your version were faster. – L.B Feb 12 '14 at 14:43
  • 1
    @L.B: are you suggesting that my big O might be wrong? In that I need to actually verify the scalability literally rather than theoretically? And I'm not being sarcastic, just asking. – Mike Perrenoud Feb 12 '14 at 14:45
  • 2
    @MichaelPerrenoud O(2n) is the same as O(n). They both exhibit linear growth and will scale equally. It's the shape of the curve that matters, not the slope. – dcastro Feb 12 '14 at 14:48
  • 1
    Check out http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist to get a Big O comparison between the two (`ArrayList` uses the same dynamic size array as this implementation). – Justin Niessner Feb 12 '14 at 14:49
  • @dcastro: but `O(2n)` would exhibit growth at a higher rate right? – Mike Perrenoud Feb 12 '14 at 14:50
  • You could consider the `2` irrelevant. If an algorithm with `2n` steps is the bottleneck of your application, changing it to take `n` steps isn't gonna solve your problem. – dcastro Feb 12 '14 at 14:51
  • 1
    @MichaelPerrenoud The 2 is one of the constant factors that complexity analysis ignores. Constant factors can matter (though big Oh is the completely wrong tool to express that). However, all sorts of other things influence constant factors, including whether you use a linked list for the values and how you lay out data. You can't ignore most constant factors and claim an improvement then you only knocked down one of them without investigating how the others changed and whether this may eat up the performance improvements. –  Feb 12 '14 at 14:55
  • @JustinNiessner: awesome information, and so what I'm questioning is the fact that adding an item to anywhere but the end requires both arrays to be copied. The auto-sizing is sensible to me as it ensures there is enough capacity and requires resizing much less frequently (clearly even the `List` implements it this way). – Mike Perrenoud Feb 12 '14 at 14:55
  • @delnan: so collateral damage is understandable, but I was only using the `LinkedList` as an example. I'm specifically saying that the key could use a pointer to the value and thus the lookup of the value is not affected, the removal isn't either because we have the pointer, but the add then (as you stated) knocks off a constant factor. – Mike Perrenoud Feb 12 '14 at 15:00
  • @MichaelPerrenoud I know that was an analogy, but *any* change to how data is organized in memory affects all sorts of constant factors in often counter intuitive ways (likewise for seemingly harmless changes to code, the compiler you use, the hardware, etc.). For example, the indirection and lack of order in the values array might cause more cache misses during iteration. I'm not saying this is not necessarily an improvement, but that it'd be the sort of improvement that needs **much** more careful and low-level reasoning, or better yet, empirical evidence. –  Feb 12 '14 at 15:05
  • 1
    @MichaelPerrenoud: An obvious drawback of mapping keys to values in an arbitrary manner is that you need extra storage for the map. So in effect the question can be reduced to "why did they optimize for size instead of speed?", which clearly does not have such a straightforward answer as you look to be after. – Jon Feb 12 '14 at 15:19
  • 1
    I'm not clear on how you efficiently implement the [`Values`](http://msdn.microsoft.com/en-us/library/ms132380(v=vs.110).aspx) property under your proposal. Remember, collections don't get optimized for just *one* scenario. – Damien_The_Unbeliever Feb 12 '14 at 15:20
  • @Jon: okay so every item in the list would now conceivably have an additional 32 bits of overhead - gotcha. – Mike Perrenoud Feb 12 '14 at 15:20
  • @Damien_The_Unbeliever: I apologize if it seems ignorant, but can you expand on what you're saying a bit? – Mike Perrenoud Feb 12 '14 at 15:23
  • http://stackoverflow.com/questions/1376965/when-to-use-a-sortedlisttkey-tvalue-over-a-sorteddictionarytkey-tvalue – zs2020 Feb 12 '14 at 15:28
  • `Values` returns the values in the same order as they're contained in the sorted list. It can just operate over the `this.Values` `Array` in order. Wouldn't your proposal require it to iterate over the keys and then dereference each pointer, to achieve the same result? – Damien_The_Unbeliever Feb 12 '14 at 15:31
  • @Damien_The_Unbeliever I believe one could define a (private to `SortedList`) implementation of `IList` that does this with a compatible interface. Still, quite some work for a micro optimization, and another dent in the claim of superiority. –  Feb 12 '14 at 16:06

2 Answers2

10

This should not surprise you, it is well documented in the MSDN article for SortedList:

SortedDictionary has faster insertion and removal operations for unsorted data, O(logn) as opposed to O(n) for SortedList.

SortedDictionary uses a red-black tree (i.e. "pointers"), SortedList is an array. You choose between the two based on what you do with the collection. Both are O(logn) for lookup, but if you iterate the collection frequently then you can be ahead with SortedList a great deal. It uses the cpu caches much more effectively. Makes a huge difference on modern machines.

Also do note that the efficiency of adding items to the collections is heavily dependent on how sorted the items are. A SortedDictionary really likes random data, gives it much better odds of not having to re-balance the trees. Having it sorted gives it worst-case O(n) behavior. SortedList really likes sorted items, makes adding O(1).

Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
  • SortedList of course hates data with a reversed sorted input, giving it the worst case behavior. – Servy Feb 12 '14 at 16:50
  • Okay, so they did this because there is a need for a **different** *type* of data structure. This really opens my mind when it comes to these types of things. It has to do with providing **solutions** that account for different data, its current form, **and** its usage (regular vs. rare) to choose the right data structure. It was implemented that way because the `SortedDictionary` does exactly what I'm talking about, whereas there is (clearly now) a total different usage for the `SortedList`. Hans, thanks and I hope I haven't wasted your time with what may be an elementary question now. – Mike Perrenoud Feb 12 '14 at 16:51
1

Another very important difference other than speed/big O complexity is memory overhead. With a tree (SortedDictionary) the overhead is of magnitude 50-70 bytes per key/value pair (measured approximately on F#'s AVL tree with 1M <int64,int64> items on x64, but with red/black should be around that range), while SortedList takes only 2 bytes per pair.

The point is, with value types, e.g. <int,int>, SortedDictionary could "waste" several time more memory than useful payload with the single isolated advantage of faster random insert. In practice, the advantage of CPU cache in SortedList is so noticeable (the constant in O(lon n) lookups) that one should measure the difference for each particular use case (ratio of lookups/inserts, inserts patterns, memory/speed requirements).

V.B.
  • 6,236
  • 1
  • 33
  • 56