Ручное внедрение высокопроизводительных алгоритмов в .NET

Question

Как опыт обучения, я недавно попробовал реализовать Quicksort with 3 way partitioning в C#.

Помимо необходимости добавить дополнительную проверку диапазона влево/вправо перед рекурсивным вызовом, он работает очень хорошо.

Я знал заранее, что каркас обеспечивает built-in Quicksort implementation в списке <> .Sort (через Array.Sort). Поэтому я попробовал некоторое базовое профилирование для сравнения производительности. Результаты: встроенный метод List List <> .Sort, работающий в тех же списках, выполняет примерно в 10 раз быстрее, чем моя собственная ручная реализация.

Используя отражатель, я обнаружил, что фактическая сортировка в списке <> .Sort реализована во внешнем коде, а не в IL (в функции с именем tryszsort()).

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

Итак, мой вопрос: реалистично ли ожидать, что производительность в оптимизированном алгоритме (написанная в .NET IL, связанная с собственным кодом) может конкурировать с производительностью алгоритма, реализованного извне?

Еще раз, я понимаю, что Quicksort предоставляется как часть фреймворка, для меня это было всего лишь опытом обучения. Однако есть также много алгоритмов (CRC32 приходит на ум), которые не предоставляются, но все же могут иметь большое значение для многих приложений. Вот связанный с этим вопрос относительно implementing CRC32 in .NET и проблем с производительностью.

Итак, если вам нужно реализовать такой алгоритм в .NET, каковы основные соображения производительности для понимания, чтобы ваш алгоритм мог по крайней мере приблизиться к производительности внешнего кода?

[Update]

Я улучшил скорость выполнения в пределах примерно 10% от встроенного Array.sort путем изменения алгоритма для работы на простом массиве Int вместо List. В Reflector я вижу, что это позволяет избежать операции Callvirt() для каждого get или set в списке. Я думал, что это может улучшить ситуацию, но я удивлен, насколько.

Answer 1

Используя нерекурсивный код и, в частности, с помощью «небезопасных» блоки и арифметика указателей (если это применимо), вы могли реально увидеть прирост производительности x5 или x10 с алгоритмом, написанным в C#. Как и всегда с производительностью (и даже больше при работе с управляемой средой), вы никогда не знаете, пока не попробуете ее и не сравните ее.

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

Answer 2

Просто из любопытства, так как, несмотря на мой 9-летний опыт работы с .NET, я все еще постоянно делаю эту ошибку: вы скомпилировали свой код в режиме Release с оптимизацией? Код отладки значительно хуже, чем оптимизированный код выпуска.

Предполагая, что вы скомпилируете в режиме деблокирования, не должно быть огромной разницы в производительности, если вы аналогично реализуете алгоритм (например, итеративный или итеративный или рекурсивный или рекурсивный).Если вы хотите увидеть реализацию .NET и выяснить, вы можете загрузить SSCLI, Share-Source Common Language Infrastructure. Это общедоступная версия CLI, совместимая с ECMA-стандартом. Это не 100% платформы .NET, все мы знаем и любим, но это значительная ее часть. Он может предоставить много информации, которую Reflector не может, включая внутренние реализации. Доступны все типы кода, включая C#, C++ и даже некоторые ассемблеры в нескольких случаях.

Answer 3

Убедитесь, что вы сравниваете яблоки и яблоки.

При сортировке функция сравнения может быть доминирующей, и это может различаться между реализациями.

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