Арифметика большого массива в C#

Question

Каков наилучший способ хранения 2D-массива в C# для оптимизации производительности при выполнении множества арифметических элементов в массиве?

У нас есть большие (около 1,5 Г) массивы, которые, например, мы хотим умножить друг на друга по элементам. Производительность имеет решающее значение. Контекст, в котором это делается, находится в C#. Есть ли какой-либо умный способ хранения массивов и итерации по ним? Можем ли мы написать эти части в неуправляемом C++, и это действительно увеличит производительность? Массивы должны быть доступны для остальной части программы C#.

В настоящее время (в) массив хранится как один длинный вектор. Мы выполняем вычисления для каждого элемента массива и перезаписываем старое значение. Вычисления обычно уникальны для каждого элемента вектора.

Временные эксперименты показывают, что сохранение и итерация по данным в виде массива в C# происходит медленнее, чем сохранение его в виде 2D-массива. Я хотел бы знать, есть ли еще лучший способ обработки данных. Конкретная выполняемая арифметика не имеет отношения к вопросу.

Answer 1

Для лучшей производительности массива, убедитесь, что вы используете один массив размера с более низким индексом 0.

Чтобы получить доступ к элементам массива как можно быстрее, вы можете использовать небезопасные указатели как так:

int[] array = Enumerable.Range(0, 1000).ToArray(); 

int count = 0; 
unsafe { 
    fixed (int* pArray = array) { 
     for (int i = 0; i < array.Length; i++) { 
      count += *(pArray + i); 
     } 
    } 
} 

EDIT Drat! Не заметил, что вы сказали 2D-массив. Этот трюк не будет работать с многомерным массивом, поэтому я не уверен, насколько он поможет. Хотя вы можете превратить любой массив в одномерный массив, выполнив некоторую арифметику в индексе массива. Просто зависит от того, интересует ли вас производительность при индексировании массива или итерации по массиву.

Answer 2

Анна,

Вот большая страница, которая обсуждает разницу в производительности между традицией научных языков программирования (Fortran, C++) и C#.

http://msdn.microsoft.com/en-us/magazine/cc163995.aspx

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

alt text http://i.msdn.microsoft.com/cc163995.fig08.gif

Я хотел бы предложить экспериментировать самостоятельно, и использовать анализ производительности в VS 2008 для сравнения.

Если использование C# «достаточно быстро», ваше приложение будет намного проще в обслуживании.

Удачи!

Answer 3

Если вы загружаете F # и ссылаетесь на одну из библиотек времени исполнения (я думаю, это FSharp.PowerPack) и используйте Microsoft.FSharp.Maths.Matrix. Он оптимизирует себя на основе того, используете ли вы плотную или разреженную матрицу.

Answer 4

Проводите ли вы повторение матрицы за строкой или по столбцу или по обоим? Вы всегда получаете доступ к близлежащим элементам или выполняете произвольный доступ к матрице.

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

Довольно простой способ сделать это - написать небольшую функцию доступа, чтобы превратить индексы строки/colum в индекс и работать с одномерной матрицей, способом кэширования.

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

http://en.wikipedia.org/wiki/Z-order_(curve) < - извините, не могу связать, что SO не любит URL-адреса с тире в нем. Вы должны отказаться от пасты.

Ускорение фактора 10 и более реалистично кстати. Однако это зависит от алгоритма, который вы используете над вашими матрицами.