[Mono-dev] Dictionary implementation + concurrency

Greg Young gregoryyoung1 at gmail.com
Mon Feb 4 11:09:12 UTC 2013


tess covers race condition here
http://blogs.msdn.com/b/tess/archive/2009/12/21/high-cpu-in-net-app-using-a-static-generic-dictionary.aspx
i figured it was only for items > ref size.

On Mon, Feb 4, 2013 at 1:07 PM, Greg Young <gregoryyoung1 at gmail.com> wrote:
> from reading it appears there is actually a possible race condition
> with 1/n in the .net impl as well so nm
>
> On Mon, Feb 4, 2013 at 12:56 PM, Daniel Lo Nigro <lists at dan.cx> wrote:
>>> My guess the reason its not explicitly documented is that its only for
>>> types reference or smaller.
>>
>> In this case it sounds like an unintentional implementation detail that
>> shouldn't be relied on?
>>
>> You could probably look at the SSCLI and see if there's any comments around
>> it (but I think that if you look at that code, you will be unable to
>> contribute to Mono).
>>
>>
>> On Mon, Feb 4, 2013 at 9:46 PM, Greg Young <gregoryyoung1 at gmail.com> wrote:
>>>
>>> The .NET version does support it for types or reference size or smaller.
>>>
>>> My guess the reason its not explicitly documented is that its only for
>>> types reference or smaller.
>>>
>>> On Mon, Feb 4, 2013 at 12:40 PM, Alan <alan.mcgovern at gmail.com> wrote:
>>> > Hey,
>>> >
>>> > As per the 'thread safety' section of the documentation, your code is
>>> > invalid: http://msdn.microsoft.com/en-us/library/xfhwa508.aspx. This
>>> > kind of change will not make it safe to use the dictionary in a
>>> > read/write way from multiple threads, especially not when you have
>>> > multiple cores and multiple unshared caches for those CPU cores.
>>> >
>>> > Hashtable is documented to support multiple readers with at most 1
>>> > writer. If you require those semantics, you should use a hashtable not
>>> > a Dictionary. If you require a threadsafe dictionary class, you either
>>> > need to roll your own or use ConcurrentDictionary. This is the only
>>> > realistic way of having thread safe code.
>>> >
>>> > Alan
>>> >
>>> >
>>> > On 4 February 2013 10:18, Rafael Teixeira <monoman at gmail.com> wrote:
>>> >> 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
>>> >>
>>> >>
>>> >>
>>> >> _______________________________________________
>>> >> Mono-devel-list mailing list
>>> >> Mono-devel-list at lists.ximian.com
>>> >> http://lists.ximian.com/mailman/listinfo/mono-devel-list
>>> >>
>>>
>>>
>>>
>>> --
>>> 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
>>
>>
>
>
>
> --
> Le doute n'est pas une condition agréable, mais la certitude est absurde.



-- 
Le doute n'est pas une condition agréable, mais la certitude est absurde.


More information about the Mono-devel-list mailing list