Почему умножение матриц в .NET так медленно?

Я не совсем понимаю, что делает умножение матриц в C#/.NET (и даже в Java) таким медленным.

Посмотрите на этот тест (источник): Попытка найти обновленный тест.

Разборка Java, C# и C++

Целочисленная и двойная производительность C# чертовски близка к C++, скомпилированному с помощью MSVC++. На 87 % быстрее для двойного числа и на 99 % быстрее для 32-битного целого числа. Чертовски хорошо, я бы сказал. Но тогда посмотрите на умножение матриц. Разрыв увеличивается до C# примерно на 19% быстрее. Это довольно большое несоответствие, которое я не понимаю. Умножение матриц — это просто набор простых математических операций. Как это становится так медленно? Разве это не должно быть примерно так же быстро, как эквивалентное количество простых операций с плавающей запятой или целочисленных операций?

Это особенно касается игр и XNA, где производительность матриц и векторов имеет решающее значение для таких вещей, как физические движки. Некоторое время назад в Mono была добавлена ​​поддержка SIMD-инструкций с помощью изящных векторных и матричных классов. Он сокращает разрыв и делает Mono быстрее, чем написанный от руки C++, хотя и не так быстро, как C++ с SIMD. (источник)

Сравнение умножения матриц

Что тут происходит?

Редактировать: присмотревшись, я неправильно понял второй график. С# кажется довольно близким. Может, первый тест делает что-то ужасно неправильное? Извините, я пропустил номер версии в первом тесте. Я взял его как удобную ссылку на «линейную алгебру C# медленную», которую я всегда слышал. попробую найти другую.


.net c# performance matrix-multiplication xna
person Matthew Olenik    schedule 12.07.2010    source источник
comment
Версия C# + параметры: .Net Framework 1.1.4322 Эээ... нет ли более новой версии?   -  person GalacticJello    schedule 12.07.2010
comment
сидит и ждет, что JonSkeet скажет по этому поводу :-)   -  person WestDiscGolf    schedule 12.07.2010
comment
Тест был проведен с VS 2003. (Обратите внимание также на версию C++.) Следовательно, древняя версия .net.   -  person cHao    schedule 12.07.2010
comment
@GalacticJello да, но все же, почему это намного медленнее, чем операции с целыми числами / с плавающей запятой? Я посмотрю, смогу ли я найти еще несколько тестов.   -  person Matthew Olenik    schedule 12.07.2010
comment
@Matt Olenick: Это была первая (ну... вторая) версия .NET. Более того, XNA даже не будет работать на .NET 1.1, это реализация .NET 2.0 Compact Edition. Хотите верьте, хотите нет, но в языки вносятся улучшения после более ранних выпусков.   -  person Powerlord    schedule 12.07.2010
comment
@Matt: Хороший звонок. Тесты 6-летней давности — и для версий каменного века задействованных фреймворков/языков — в значительной степени бесполезны.   -  person cHao    schedule 12.07.2010
comment
Вздох. Да, я пропустил номер версии, я это вижу. Я знаю, что они делают улучшения, не нужно умничать. Постараюсь найти что-нибудь поновее.   -  person Matthew Olenik    schedule 12.07.2010
comment
@cHao: Часто базовая реализация не сильно меняется со временем. Чем ниже вы спускаетесь, тем реже происходят изменения. IL/ByteCode довольно низкого уровня. Вопрос также не бесполезен, если вы все еще используете эти фреймворки. (В конце концов, программисты на COBOL все еще востребованы)   -  person Armstrongest    schedule 12.07.2010
comment
@ Гэри '-': Ну, в данном случае так и есть. .net 2.0 был в значительной степени капитальным ремонтом. Они добавили кучу всего, включая дженерики (читай: лучший способ создавать классы коллекций...). 4.0 также обновил CLR, но я забыл, что они добавили.   -  person cHao    schedule 12.07.2010
comment
@cHao: Возможно, вы правы cHao... Я согласен с тем, что это была капитальная переработка .Net, но я думаю, что производительность чего-то относительно простого, подобного этому, будет находиться на уровне IL, над которым, я сомневаюсь, было проделано много работы (хотя я мог быть неправым).   -  person Armstrongest    schedule 13.07.2010
comment
@Gary '-': Generics требовали поддержки с нуля, поэтому я почти уверен, что транслятор IL / JIT был по крайней мере затронут. Даже если бы это было не так, IL — это просто полупереваренный код. Сама CLR (которая претерпела довольно большие изменения) — это то, что на самом деле запускает ее.   -  person cHao    schedule 13.07.2010

Ответы (4)


arrow_upward
13
arrow_downward

С такими большими матрицами ограничивающим фактором становится кэш процессора. Что очень важно, так это то, как хранится матрица. А код бенчмарка сравнивает яблоки и апельсины. В коде C++ использовались зубчатые массивы, в коде C# — двумерные массивы.

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

person Hans Passant    schedule 12.07.2010
comment
Спасибо, это проясняет ситуацию. Так почему же я всегда слышу (помимо других причин), что XNA работает медленно, потому что умножение матриц в C# выполняется медленно? Это просто неправда? - person Matthew Olenik; 12.07.2010
comment
Я не знаю, это не поддающееся проверке утверждение с того места, где я сижу. Часто ли программисты XNA пишут собственный код умножения матриц? Код C/C++ бескомпромиссен, когда дело доходит до скорости, и вам остается выковыривать шрапнель из ушей, когда она взрывается. Если есть проблема со скоростью с определенным алгоритмом в C#, у вас всегда есть возможность вернуться к C/C++. - person Hans Passant; 12.07.2010
comment
Нет, они используют библиотеку, предоставленную XNA. - person Matthew Olenik; 12.07.2010

arrow_upward
10
arrow_downward

Чтобы объяснить происхождение идеи о медленных матричных операциях XNA:

Прежде всего, есть небольшая хитрость для начинающих: класс XNA Matrix operator* сделает несколько копий. Это медленнее, чем можно было бы ожидать от эквивалентного кода C++.

(Конечно, если вы используете Matrix.Multiply(), то можете передать по ссылке.)

Вторая причина заключается в том, что .NET Compact Framework, используемый XNA на Xbox 360, не имеет доступа к оборудованию VMX (SIMD), доступному для собственных игр C++.

Вот почему вы продолжаете слышать, что это, по крайней мере, медленно. Как вы можете видеть из опубликованных вами тестов - это не так уж и «медленно», если сравнивать яблоки с яблоками.

person Andrew Russell    schedule 12.07.2010
comment
В этом есть смысл. Возможно, некоторые заблуждения возникают из-за использования оператора. - person Matthew Olenik; 12.07.2010

arrow_upward
7
arrow_downward

Очевидно, что автор теста не понял разницы между зубчатыми и многомерными массивами в C#. Это действительно не было сравнение яблок с яблоками. Когда я изменил код, чтобы использовать зубчатые массивы вместо многомерных массивов, чтобы он работал в манере, более похожей на Java, тогда код C# работал в два раза быстрее... делая его быстрее, чем Java (хотя едва ли, и это, вероятно, статистически незначимы). В C# многомерные массивы работают медленнее, потому что требуется дополнительная работа по поиску слота массива и потому что проверка границ массива не может быть устранена для них... пока.

См. этот вопрос для более глубокий анализ того, почему многомерные массивы медленнее, чем зубчатые массивы.

См. этот blog для получения дополнительной информации о проверке границ массива. Статья специально предостерегает от использования многомерных массивов для умножения матриц.

person Brian Gideon    schedule 12.07.2010

arrow_upward
3
arrow_downward

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

Параллельное умножение матриц с параллельной задачей Библиотека (TPL)

В статье рассматриваются различные методы и объясняется, почему многомерные массивы — плохой выбор:

Самый простой способ выполнить умножение матриц — использовать многомерный массив .NET с порядком i, j, k в циклах. Проблемы двоякие. Во-первых, порядок i,j.k обращается к памяти лихорадочно, заставляя данные извлекаться из разных мест. Во-вторых, он использует многомерный массив. Да, многомерный массив .NET удобен, но очень медленный.

person GalacticJello    schedule 12.07.2010