[Mono-dev] Dictionary implementation + concurrency

[Alan]

It's not documented so you're relying on a quirk which may or may not
actually work on multi-core systems under heavy load. I'm just saying
that it's not worth relying on this as a guarantee as you will break
when run on different implementations of the BCL because you're
relying on something which is not a guarantee.

Alan

On 4 February 2013 10:46, 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.