[Mono-dev] Dictionary implementation + concurrency

[Greg Young]

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.