For the 3rd point, see this blog post about an identical problem in the java implementation of a similar method: http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html
On Sun, Apr 1, 2012 at 3:42 PM, Nicholas Frechette <[email protected]> wrote: > In looking at the code in SortedList<>, I noticed the following things: > > - Clear() causes a new allocation, this is inconsistent with other > generic containers such as List<> and Stack<> that simply perform an > Array.Clear() on their internal array. > > - PutImpl(), if Find(key) throws an exception, it is swallowed and an > InvalidOperationException is thrown, this is something that happened > to me when my key was a System.Type and I have no way of figuring out > what happened (forcing me to use a Dictionary<> instead). > > - Find(key), if I am not mistaken, when the list gets very large, the > line calculating the guess can overflow: int guess = (left + right) >> > 1; > For example, if the size is 2^31 - 1, and we provide a key that is in > the top half, the loop will go as follow: left = 0, right = 2^31 - 2, > guess = ~2^30. if cmp < 0, left becomes ~2^30 and on the next > iteration, left + right will be (2^31 - 2 + ~2^30) which is larger > than int.MaxValue (2^31-1) thus causing overflow before the right > shift to divide by 2. > > Cheers, > Nicholas _______________________________________________ Mono-list maillist - [email protected] http://lists.ximian.com/mailman/listinfo/mono-list
