[Mono-list] SortedList<> inconsistencies and deficiencies

[Nicholas Frechette]

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 <zeno490 at gmail.com> 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