Здравствуйте, igor-booch, Вы писали:


IB>Если ключ был к примеру int, так можно было бы сделать.
IB>К сожалению этот вариант для меня не подходит так тип ключа мне неизвестен, для меня он object.
Можно применить object.GetHashCode

Здравствуйте, igor-booch, Вы писали:

S>>Вообще для улучшения производительности, можно Хэш таблицу Разделить например на 1) хэш таблиц. Учитывая что данных будет много.
S>>Тогда Доступ к каждой можно сделать как поз=Хэш % 10. Если хэши хорошо перемешаны вероятность доступа из двух потоков к одной хэш таблицы будет как 1/10, и соответсвенно уменьшится время ожидания на вставку изменения.

IB>Если ключ был к примеру int, так можно было бы сделать.
IB>К сожалению этот вариант для меня не подходит так тип ключа мне неизвестен, для меня он object.
У любого object есть метод GetHashCode любая Хэш таблица использует этот метод для получения Хэш Кода.
Либо всегда можно применить свою функцию Хэширования к ключу.

0>Можно применить object.GetHashCode
А по каким критериям определить оптимальное количество словарей в этом случае?

Здравствуйте, 0x7be, Вы писали:

0>Здравствуйте, igor-booch, Вы писали:


IB>>Если ключ был к примеру int, так можно было бы сделать.
IB>>К сожалению этот вариант для меня не подходит так тип ключа мне неизвестен, для меня он object.
0>Можно применить object.GetHashCode
Вообще-то на вход словарю подается IEqualityComparer, его-то и следует использовать.

S>Вообще-то на вход словарю подается IEqualityComparer, его-то и следует использовать.

Не понимаю как в этом случае реализовать преложенное Serginio1

IB>А по каким критериям определить оптимальное количество словарей в этом случае?
Количество словарей наверное = количеству потоков = количеству ядер CPU

Здравствуйте, igor-booch, Вы писали:

0>>Можно применить object.GetHashCode
IB>А по каким критериям определить оптимальное количество словарей в этом случае?
по критериям, построенным по результатам анализа полученных на практике данных.

Здравствуйте, igor-booch, Вы писали:

S>>Вообще-то на вход словарю подается IEqualityComparer, его-то и следует использовать.

IB>Не понимаю как в этом случае реализовать преложенное Serginio1
А в чем конкретно заключается непонимание?

Здравствуйте, igor-booch, Вы писали:

IB>>А по каким критериям определить оптимальное количество словарей в этом случае?
IB>Количество словарей наверное = количеству потоков = количеству ядер CPU
Здесь играет роль вероятности. Чем больше массив тем меньше вероятность доступа к одному словарю. Тут много факторов влияет, в том числе и распределение хэш функции. Но лучше всего экспериментальным путем.
Например б+ дерево по сути и является массивом массивов. Там оптимальность длины зависит от вставки и перестроения дерева. Сделай 100 словарей, если к нему будет постоянный доступ. Не ошибешься.
Вернее приведи этот размер к простому числу

IB>>Если ключ был к примеру int, так можно было бы сделать.
IB>>К сожалению этот вариант для меня не подходит так тип ключа мне неизвестен, для меня он object.
0>Можно применить object.GetHashCode

К сожалению данный вариант тоже не подходит. Но за идею спасибо.
У меня добавление происходит подряд в несколько словарей.
И для каждого разные ключи.
Если применить этот подход,
и каждый словарь разделить на несколько, и в каждый из этих нескольких добавлять в отдельных потоках,
то последовательность может быть нарушена.
Конечно теоретически можно абстрагировать мою логику от последовательности добавления (чтобы добавлять можно было в любом порядке), то тогда логика получится слишком сложной.

Здравствуйте, igor-booch, Вы писали:

I>>А сценарии у тебя какие ? Итерации не нужны, удаление не нужно ?

IB>Сценарий у меня добавить элементы в словарь за максимально короткое время

Cкажи пожалуйста, почему тебе пришла в голову идея что ConcurrentDictionary решает именно эту проблему или хотя бы может помочь с этой проблемой ? Вроде как слово Concurent говорит совсем о другом.

IB>>Не понимаю как в этом случае реализовать преложенное Serginio1
S>А в чем конкретно заключается непонимание?

Предположим я решил по совету Serginio1 я решил разделить свой словарь на 10 словарей
Каждый словарь отвечает за определенный диапозон ключей.
Как эти диапазоны определить имея только IEqualityComparer и не зная какого типа будет ключ.
От какого объекта до какого каждый диапозон?
Ситуация усложнится если допустить что ключи могут быть разных типов.
Варианту с GetHashCode в этом случае пофиг.

Здравствуйте, igor-booch, Вы писали:

IB>>>Не понимаю как в этом случае реализовать преложенное Serginio1
S>>А в чем конкретно заключается непонимание?

IB>Предположим я решил по совету Serginio1 я решил разделить свой словарь на 10 словарей
IB>Каждый словарь отвечает за определенный диапозон ключей.
Serginio1 писал не о диапазоне, а об операции нахождения остатка от деления на число словарей хэшкода ключа.

IB>Ситуация усложнится если допустить что ключи могут быть разных типов.
IB>Варианту с GetHashCode в этом случае пофиг.
EqualityComparer<Object>.Default будет делегировать именно object.GetHashCode()-у если ссылка не нулевая.

I>Cкажи пожалуйста, почему тебе пришла в голову идея что ConcurrentDictionary решает именно эту проблему или хотя бы может помочь с этой проблемой ? Вроде как слово Concurent говорит совсем о другом.

Concurent — способный работать в условиях многопоточности, потокобезопасный. Одно из предназначений многопоточности это для того чтобы множество операций можно было разделить на несколько подмножеств и выполнять операции из этих подмножеств параллельно, то есть в условиях многопоточности.
Понятно что потокобезопасность не означает что код будет работать быстрее на нескольких потоках.
Это скорее значит что код не отвалится на нескольких потоках.
Так как можно на все операции повесить эксклюзивную блокировку на весь объект (или вообще на тип объекта) и код станет потокобезовасным,
но при обращении к коду из нескольких потоков все опрациии будут работать последовательно, как будто отращаются из одного потока.
Чтобы сделать код быстрее на нескольких потоках необходимо использовать более гранулярные блокировки, чем эксклюзивную блокировку на объект.
Если посмотреть сорцы ConcurrentDictionary такая попытка делается (см. обсуждения выше: http://rsdn.ru/forum/dotnet/5176846.1

Автор: samius
Дата: 22.05.13

).
Но судя по результатам теста не совсем удачная попытка, ну или удачная но хотелось бы чтобы она была поудачнее.
Если они хотели добиться только потокобезопасности, без увеличения производительности на нескольких потоках, то назвали бы тогда честно
ThreadSafeDictionary.

S>EqualityComparer<Object>.Default будет делегировать именно object.GetHashCode()-у если ссылка не нулевая.
Я наверное Вас не понимаю, но этим постом
http://rsdn.ru/forum/dotnet/5178359.1

Автор: samius
Дата: 23.05.13

Вы предложили альтернативу GetHashCode.

S>Serginio1 писал не о диапазоне, а об операции нахождения остатка от деления на число словарей хэшкода ключа.
По моему мнению алгоритм может быть в 2-х вариантах:

Создаем 10 словарей
Каждый словарь отвечает за определенный диапазон целочиленных значений ключей (или хэш кодов ключей, если мы не знаем тип ключей)
Предположим нужно добавить элемент по ключу K
Тогда
1) мы ищем в какой диапазон попадает K, если К целочисленное
или в какой диапозон попадает K.GetHashCode(), если мы не знаем тип K
2) И делаем вставку в соответсвующей словарь с блокировкой на него

Но этого варианта есть недостаток: нет разброса ключей (хэш кодов ключей) по словарям.

Serginio1 изначально предложил более эффективный вариант (я это сразу не заметил)
Создаем изначально просто 10 словарей без всяких диапозонов
Предположим нужно добавить элемент по ключу K
1) делаем K % 10 и получаем номер словаря, если К целочисленное
или K.GetHashCode() % 10, если тип K неизвестен
2) И делаем вставку в этот словарь с блокировкой на него

Этот вариант избавляет от необходимости определения диапозонов и одновременно обеспечивает разброс ключей (хэш кодов ключей) по словарям.

Вы писали следующее:
0>>Можно применить object.GetHashCode
S>Вообще-то на вход словарю подается IEqualityComparer, его-то и следует использовать.
Как использовать в этих алгоритмах IEqualityComparer переданный на вход словарю непонятно.

Здравствуйте, igor-booch, Вы писали:


IB>Если они хотели добиться только потокобезопасности, без увеличения производительности на нескольких потоках, то назвали бы тогда честно
IB>ThreadSafeDictionary.

ConcurrentDictionary<TKey, TValue> — класс




Кстати внутри Это Хэш таблица использующая GetHashCode. Внутри при добавлении используется Monitor.Enter но на конкретную запись, используется Volaitile.Read, TryUdate
Идет сравнение на текущую таблицу. То есть скрость записи изменения из разных потоков должна увеличиться по сравнению с потокобезопасной/
Применение массива ConcurrentDictionary может дать пользу при реструктуризации.

Здравствуйте, igor-booch, Вы писали:

IB>http://rsdn.ru/forum/dotnet/5178359.1

Автор: samius
Дата: 23.05.13

IB>Вы предложили альтернативу GetHashCode.
Нет, предложили его разработчики фреймворка, а я лишь предложил использовать именно его, как и задумано разработчиками.

S>>Serginio1 писал не о диапазоне, а об операции нахождения остатка от деления на число словарей хэшкода ключа.
IB>По моему мнению алгоритм может быть в 2-х вариантах:

IB>Создаем 10 словарей
IB>Каждый словарь отвечает за определенный диапазон целочиленных значений ключей (или хэш кодов ключей, если мы не знаем тип ключей)
Можно, но надо еще эффективно решать задачу поиска диапазона.
IB>Но этого варианта есть недостаток: нет разброса ключей (хэш кодов ключей) по словарям.
Да, и этот

IB>Serginio1 изначально предложил более эффективный вариант (я это сразу не заметил)
IB>1) делаем K % 10 и получаем номер словаря, если К целочисленное
IB>или K.GetHashCode() % 10, если тип K неизвестен
Мне кажется что именно это предложил Serginio1.

IB>Этот вариант избавляет от необходимости определения диапозонов и одновременно обеспечивает разброс ключей (хэш кодов ключей) по словарям.
Разброс обеспечивает функция GetHashCode и только она.

IB>Вы писали следующее:
0>>>Можно применить object.GetHashCode
S>>Вообще-то на вход словарю подается IEqualityComparer, его-то и следует использовать.
IB>Как использовать в этих алгоритмах IEqualityComparer переданный на вход словарю непонятно.
Вызывать IEqualityComparer.GetHashCode, а как еще?

Уточню. Object.GetHashCode() — глупая функция, прикрученная к объекту. Предполагается что именно объект должен указывать функцию получения своего хэшкода на все случаи жизни. Глупость такого подхода заключается в том, что в общем случае такой одной эффективной функции на все случаи жизни может не существовать. В различных условиях нам следует указывать рализчные функции для вычисления кэшкода. Словари в конструкторе принимают IEqualityComparer, который как раз достаточно гибок что бы для разных ситуаций использовать разные реализации. И частный случай IEqualityComparer- ObjectEqualityComparer — это такой IEqualityComparer, который делегирует вызов на Object.GetHashCode.
Реализуя собственный словарь вы не должны избегать принятых соглашений. Можете, конечно, но если вдруг вы будете хэшкод вычислять одним способом, а словари другим — возможно получите не самую эффективную реализацию в лучшем случае и самую неэфективную в худшем, когда Object.GetHashCode возвращает константу. Случаи когда GetHashCode реализован неверно я не рассматриваю.

S> Кстати внутри Это Хэш таблица использующая GetHashCode. Внутри при добавлении используется Monitor.Enter но на конкретную запись, используется Volaitile.Read, TryUdate
S>Идет сравнение на текущую таблицу. То есть скрость записи изменения из разных потоков должна увеличиться по сравнению с потокобезопасной/
Она увеличивается но к сожалению не настолько чтобы обогнать даже на 8 потоках на 8-ми ядерном проце
обычный Dictionary на одном потоке. Я ожидал большего от ConcurrentDictonary. Об этом пост.
Чтобы ConcurentDictonary обгонял на множестве потоков нужно в нем увеличивать гранулярность блокировок (умельчать блокировки). Интересно это хотя бы теоретически возможно? Или MS достигла предел гранулярности блокировок в ConcurrentDictonary?

S>Применение массива ConcurrentDictionary может дать пользу при реструктуризации.
Под реструктуризацией Вы понимаете что сначала если код вызывающий ConcurrentDictionary был однопоточным, а потом стал многопоточным? Типа ConcurrentDictionary абстрагирован от поточности?

IB>>Если они хотели добиться только потокобезопасности, без увеличения производительности на нескольких потоках, то назвали бы тогда честно
IB>>ThreadSafeDictionary.
S> ConcurrentDictionary<TKey, TValue> — класс
Не понял, Вы хотите сказать что класс не моет быть ThreadSafe?

Здравствуйте, igor-booch, Вы писали:


S>>Применение массива ConcurrentDictionary может дать пользу при реструктуризации.
IB>Под реструктуризацией Вы понимаете что сначала если код вызывающий ConcurrentDictionary был однопоточным, а потом стал многопоточным? Типа ConcurrentDictionary абстрагирован от поточности?
Внутри ConcurrentDictionary массив структур Кей Валуе который при заполнение создается новый массив в 2 раза бошльше и в него копируются текущие значения
IB>>>Если они хотели добиться только потокобезопасности, без увеличения производительности на нескольких потоках, то назвали бы тогда честно
IB>>>ThreadSafeDictionary.
S>> ConcurrentDictionary<TKey, TValue> — класс
IB>Не понял, Вы хотите сказать что класс не моет быть ThreadSafe?
Я хочу сказать, что он ThreadSafe и с конкуренцией на конкретную запись. Но вот тут есть может быть проблема в том, что дополнительный обслуживающий код сам может тормозить.
Можно выяснить это так создать массив с размером простым числом например 101 для того что бы не было затрат на GetHashCode сделать код интовым и посмотреть на скорость выполнения для обыкновенных Хэш Таблиц с блокровками на запись, можно использовать SpinLock. И предусмотреть TryUpdate

I>Cкажи пожалуйста, почему тебе пришла в голову идея что ConcurrentDictionary решает именно эту проблему или хотя бы может помочь с этой проблемой ? Вроде как слово Concurent говорит совсем о другом.

Дополнение к
http://rsdn.ru/forum/dotnet/5178474.1

Автор: igor-booch
Дата: 23.05.13

О чем по Вашему говорит Concurent?
Интересна также причина Вашей оценки к посту. По-моему остроумие не основная его часть.