[Mono-dev] Dictionary implementation + concurrency

Daniel Lo Nigro lists at dan.cx
Mon Feb 4 10:56:30 UTC 2013


>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ximian.com/pipermail/mono-devel-list/attachments/20130204/8163e79b/attachment-0001.html>


More information about the Mono-devel-list mailing list