[Mono-dev] Dictionary implementation + concurrency

[Rafael Teixeira]

Yes, please.

Rafael "Monoman" Teixeira
---------------------------------------
"The most exciting phrase to hear in science, the one that heralds new
discoveries, is not 'Eureka!' (I found it!) but 'That's funny ...'"
Isaac Asimov
US science fiction novelist & scholar (1920 - 1992)


On Sun, Feb 3, 2013 at 5:15 PM, Greg Young <gregoryyoung1 at gmail.com> wrote:

> The .NET dictionary implementation is thread safe on reads/updates so
> long as the internal collection does not grow and size is of reference
> type or smaller. eg: if you set size to 1m items and had 100k with a
> fill factor that did not cause an internal growth it would be
> threadsafe. This assurance has been brought over from Hashtable (well
> documented) and is relatively not well documented but many take a
> dependency on it. The current mono implementation does not meet this
> assurance.
>
>                         int cur = table [(hashCode & int.MaxValue) %
> table.Length] - 1;
>
>                         // walk linked list until right slot is found or
> end is reached
>                         while (cur != NO_SLOT) {
>                                 // The ordering is important for
> compatibility with MS and strange
>                                 // Object.Equals () implementations
>                                 if (linkSlots [cur].HashCode == hashCode
> && hcp.Equals (keySlots
> [cur], key)) {
>                                         value = valueSlots [cur];
>                                         return true;
>                                 }
>                                 cur = linkSlots [cur].Next;
>                         }
>
> seems fine when accessing. However when adding...
>
>                         // find an empty slot
>                         cur = emptySlot;
>                         if (cur == NO_SLOT)
>                                 cur = touchedSlots++;
>                         else
>                                 emptySlot = linkSlots [cur].Next;
>
>                         // store the hash code of the added item,
>                         // prepend the added item to its linked list,
>                         // update the hash table
>                         linkSlots [cur].HashCode = hashCode;
>                         linkSlots [cur].Next = table [index] - 1;
>                         table [index] = cur + 1;
>
>                         // store item's data
>                         keySlots [cur] = key;
>                         valueSlots [cur] = value;
>
> Can cause null reads of a key as its in linkSlots but the value slot
> has not yet been updated. Setting keySlots after valueSlots would seem
> to solve this. Pull request wanted?
>
> Cheers,
>
> Greg
>
> --
> Le doute n'est pas une condition agréable, mais la certitude est absurde.
> _______________________________________________
> Mono-devel-list mailing list
> Mono-devel-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ximian.com/pipermail/mono-devel-list/attachments/20130204/65e7a4ff/attachment.html>