none
C# Замена ступенчатого массива многопоточной коллекцией RRS feed

  • Вопрос

  • Добрый день!

    Требуется ваше экспертное мнение. Есть массив int a[][], к которому понадобилось предоставить многопоточный доступ на чтение, изменение, добавление, удаление элементов. Чтобы находить каждый элемент массива по ключу-индексу, воспользуемся ConcurrentDictionary. Какая из реализаций будет правильной в этом случае для исключения коллизий: так new ConcurrentDictionary<int,int[]> или так new ConcurrentDictionary<int, ConcurrentDictionary<int,int>>? Имеет ли вообще смысл создавать многопоточную коллекцию внутри многовоточной коллекции? Если я правильно понял, то никто не сможет получить доступ к данным внутри ConcurrentDictionary, пока с ними не завершит работу один из потоков.

    Заранее благодарен.



    12 июля 2016 г. 4:40

Ответы

  • Это в общем случае не работает. Например подумайте что будет если вставить строку/столбец с индексом 0...  А доступ к int и так атомный, мы ведь на 32/64 битных процессорах...

    Таким образом никаких ConcurrentDictionary не надо, просто берете lock на весь массив.

    Если преобладают операции чтения то скорее всего следует использовать ReaderWriterLock, это уменьшит простои. 

    Если случай не общий, а имеет какие то ограничения то можно думать об оптимизации (если она требуется). Скажем, если размеры массива не меняются то возможно обойтись без синхронизации.


    This posting is provided "AS IS" with no warranties, and confers no rights.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    12 июля 2016 г. 16:40
    Модератор
  • Можете подробнее и проще написать про то, почему ConcurrentDictionary не подойдет? Я до этого использовал lock на весь массив, но хочу отказаться от этого подхода из-за низкой производительности.

    Подойдет или не подойдет - зависит о конкретного случая.

    Обычно работа с массивами сопряжена с наличием цикла по элементам. Если другой поток меняет размеры массива, то цикл может выйти за пределы массива или пропустить часть данных. Добавление ConcurrentDictionary совершенно ничего в этом плане не меняет. 


    This posting is provided "AS IS" with no warranties, and confers no rights.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 16:19
    Модератор
  • Все операции одновременно выполняются тысячами потоков.

    И для чего столько? Обычно количество потоков не должно превышать количество ядер.

    Тысячи потоков всё равно большую часть времени простаивают, ожидая, когда планировщик ОС выделит им квант времени.

    Начинать нужно с изменения алгоритма.

    string[][] a;

    a[o][p] += value;

    Ну ё-моё... При конкатенации строк порождается огромное количество мусора. Начинать нужно с азов, с чтения (повторения) учебника по C#, глава про строки.

    Возможно, чуточку поможет StringBuilder.

    И вообще, что говорит профайлер? В Visual Studio 2015 Community есть встроенный. Нужно погонять приложение под ним, он покажет, где именно наибольшая нагрузка: на память, на процессор и т. п.

    Короче, рано ещё про кэш думать.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 17:10
  • материалы про кэш процессора

    Мои любимые ссылки (уже несколько раз приводил на разных форумах).

    RAM - не RAM, или Cache-Conscious Data Structures. Азы. Обратите внимание, как много значит порядок обхода массивов!

    Оптимизация циклов: нужны блоки. Рекомендую перевести код на C# и самостоятельно убедиться в ускорении в несколько раз.

    False sharing. Тоже азы. Одна из самых частых проблем.

    Locality of reference. Для дополнительного чтения. Там много ссылок.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 17:30
  • Это небольшие массивы.
    Я каждый день получаю массивы по 10 млн записей.
    Чтобы просмотреть такой массив нужно совсем немного времени.
    Загрузка одного такого массива, 400 Мб, в Notepad++
    занимает ~10 секунд.
    Ну а после его загрузки просмотр в памяти - это вообще копейки...

    • Изменено QazRdx 12 июля 2016 г. 9:58
    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    12 июля 2016 г. 9:54
  • Лучше бы посмотреть как именно вы с массивами работаете, но внутренний голос подсказывает, что ваш выбор: List<ConcurrentDictionary<int,int>>
    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 6:46
    Отвечающий

Все ответы

  • 1. Насколько велики Ваши массивы?
    2. ConcurrentDictionary


    12 июля 2016 г. 6:10
  • Массивы порядка 500000 записей. Я знаю, что такое ConcurrentDictionary, но в документации ответа на вопрос не нашел.
    12 июля 2016 г. 9:11
  • Это небольшие массивы.
    Я каждый день получаю массивы по 10 млн записей.
    Чтобы просмотреть такой массив нужно совсем немного времени.
    Загрузка одного такого массива, 400 Мб, в Notepad++
    занимает ~10 секунд.
    Ну а после его загрузки просмотр в памяти - это вообще копейки...

    • Изменено QazRdx 12 июля 2016 г. 9:58
    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    12 июля 2016 г. 9:54
  • Я не совсем понимаю, какое отношение имеет время просмотра к моему вопросу. У меня массив int[][] a, и требуется сделать многопоточный доступ к каждому элементу допустимым с помощью ConcurrentDictionary. Вопрос в том, чем будет отличаться с точки зрения многопоточности реализация ConcurrentDictionary<int,int[]> от ConcurrentDictionary<int,ConcurrentDictionary<int,int>>, и какая реализация правильная и почему? Здесь совершенно нет разницы в том, сколько элементов в массивах. Заранее благодарен за обстоятельный ответ.
    12 июля 2016 г. 13:42
  • При доступе к какому-либо элементу коллекции из одного из потоков
    этот элемент блокируется от доступа из всех остальных потоков
    до завершения операции.
    В Вашем первом случае элементом коллекции является int[] - массив,
    а во втором случае - int - элемент в "двух-уровневом" словаре.
    Выбирать нужно в зависимости от того, что Вы корректируете при однократном доступе,
    массив или одно единственное число.
    12 июля 2016 г. 15:45
  • Это в общем случае не работает. Например подумайте что будет если вставить строку/столбец с индексом 0...  А доступ к int и так атомный, мы ведь на 32/64 битных процессорах...

    Таким образом никаких ConcurrentDictionary не надо, просто берете lock на весь массив.

    Если преобладают операции чтения то скорее всего следует использовать ReaderWriterLock, это уменьшит простои. 

    Если случай не общий, а имеет какие то ограничения то можно думать об оптимизации (если она требуется). Скажем, если размеры массива не меняются то возможно обойтись без синхронизации.


    This posting is provided "AS IS" with no warranties, and confers no rights.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    12 июля 2016 г. 16:40
    Модератор
  • У меня есть рабоат и с массивом и с одним элементом одного из вложенных массивов.
    13 июля 2016 г. 6:29
  • Можете подробнее и проще написать про то, почему ConcurrentDictionary не подойдет? Я до этого использовал lock на весь массив, но хочу отказаться от этого подхода из-за низкой производительности.
    13 июля 2016 г. 6:30
  • Лучше бы посмотреть как именно вы с массивами работаете, но внутренний голос подсказывает, что ваш выбор: List<ConcurrentDictionary<int,int>>
    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 6:46
    Отвечающий
  • Покажите код, как именно вы работаете с массивом из разных потоков. Потому что подход очень сильно может различаться в зависимости от того, какие операции производятся.

    -----

    При виде сочетания слов: "массив" и "производительность" у меня срабатывает условный рефлекс и я сразу думаю о кэше процессора. Можно в несколько раз ускорить код при грамотном использовании кэша без всякой многопоточности. В-общем, показывайте код и рассказывайте техническое задание.

    13 июля 2016 г. 13:35
  • Тип нужен string. Lock я не привожу, т.к. везде он ставится на весь массив. Все операции одновременно выполняются тысячами потоков.

    string[][] a;

    ...

    a[i][j]=value;

    ...

    return a[k][l];

    ...

    return a[m];

    ...

    a[n] = value;

    ...

    a[o][p] += value;

    ...

    a = value;

    ...

    return a;

    ...

    В каждый конкретный момент времени частота выполнения каждой из приведённых операций может меняться.


    13 июля 2016 г. 16:16
  • Операции - выше. ТЗ у меня нет. Многопоточность - ограничение системы, не могу без неё.
    13 июля 2016 г. 16:18
  • Можете подробнее и проще написать про то, почему ConcurrentDictionary не подойдет? Я до этого использовал lock на весь массив, но хочу отказаться от этого подхода из-за низкой производительности.

    Подойдет или не подойдет - зависит о конкретного случая.

    Обычно работа с массивами сопряжена с наличием цикла по элементам. Если другой поток меняет размеры массива, то цикл может выйти за пределы массива или пропустить часть данных. Добавление ConcurrentDictionary совершенно ничего в этом плане не меняет. 


    This posting is provided "AS IS" with no warranties, and confers no rights.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 16:19
    Модератор
  • Не могли бы Вы привести материалы про кэш процессора, чтобы я тоже ознакомился?
    13 июля 2016 г. 16:20
  • Все операции одновременно выполняются тысячами потоков.

    И для чего столько? Обычно количество потоков не должно превышать количество ядер.

    Тысячи потоков всё равно большую часть времени простаивают, ожидая, когда планировщик ОС выделит им квант времени.

    Начинать нужно с изменения алгоритма.

    string[][] a;

    a[o][p] += value;

    Ну ё-моё... При конкатенации строк порождается огромное количество мусора. Начинать нужно с азов, с чтения (повторения) учебника по C#, глава про строки.

    Возможно, чуточку поможет StringBuilder.

    И вообще, что говорит профайлер? В Visual Studio 2015 Community есть встроенный. Нужно погонять приложение под ним, он покажет, где именно наибольшая нагрузка: на память, на процессор и т. п.

    Короче, рано ещё про кэш думать.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 17:10
  • ТЗ у меня нет.
    Ещё как есть. Опиши своими словами, откуда берутся данные (из БД, из файла, из сетевого потока), куда они потом записываются. И что делается с этими данными? Вряд ли всё сводится только к сложению строк.
    Многопоточность - ограничение системы, не могу без неё.
    Можно без неё. Node.js работает в одном потоке и может обрабатывать тысячи запросов в секунду. Асинхронность рулит. При работе с потоками ввода-вывода (англ. stream) потоки вычисления (англ. thread) будут в-основном простаивать, ожидая, пока данные грузятся.
    13 июля 2016 г. 17:16
  • материалы про кэш процессора

    Мои любимые ссылки (уже несколько раз приводил на разных форумах).

    RAM - не RAM, или Cache-Conscious Data Structures. Азы. Обратите внимание, как много значит порядок обхода массивов!

    Оптимизация циклов: нужны блоки. Рекомендую перевести код на C# и самостоятельно убедиться в ускорении в несколько раз.

    False sharing. Тоже азы. Одна из самых частых проблем.

    Locality of reference. Для дополнительного чтения. Там много ссылок.

    • Помечено в качестве ответа Энтомолог 15 июля 2016 г. 4:34
    13 июля 2016 г. 17:30
  • Речь идет про ASP.NET MVC, где один поток - одна сессия. Все сессии могут пользоваться общими статическими переменными. Соответственно, у меня все пользователи пользуются этим массивом. На данный момент сначала он инициализируется из БД (при каждом старте приложения). Затем каждому пользователю выводится часть данных на страницу. Пользователь щелкает по кнопкам и вводит данные в поля. Данные из полей записываются в этот массив в соответствии с индексами, соответствующими номерам полей и номерам страниц.
    13 июля 2016 г. 17:46