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

Question

Как опыт обучения, я недавно пытался реализовать Quicksort с 3-х сторонним разделением в C #.

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

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

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

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

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

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

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

[Update]

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

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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