Вчера взялся за оптимизацию своей реализации архиватора Хаффмана. Долго думал – заменяя поиск перебором на бинарный, выносить ли его отдельной функцией? Не найдя ответа, провёл небольшой эксперимент.
Написал коротенькую программу на Turbo Pascal, которая выполняла сортировку "пузырьком" одномерного массива три раза.
В первом тесте оба цикла, проверка и обмен располагались в одной процедуре.
Во втором обмен вынесен отдельной процедурой.
В третьем проверка вместе с обменом были вынесены отдельной процедурой.

Надо сказать, результаты меня поразили. Конечно, когда-то я, впервые узнав о структурном программировании, думал о том – не снижает ли разбиение на подпрограммы общей производительности? – но надеялся, что не снижают.
Итак, взглянем ещё раз: проверка выполняется, как известно, n*n/2 раз, где n – длина массива; обмен – несколько реже, в зависимости от степени начальной упорядоченности.
Результаты на моём компьютере для n=1000: соответственно 0.110, 0.165 и 0.220 секунд;
n= 2000: 0.440, 0.605, 0.770;
n= 5000: 2.750, 3.795, 4.730;
n=10000: 11.165, 15.290, 18.810.
То есть, при вынесении обмена отдельной процедурой производительность снижалась в 1,37 раз, а при вынесении вместе с проверкой – в 1,685 раз! Меня это, разумеется, достаточно сильно удивило, и, заподозрив нечто, я перенёс эту программу на Virtual Pascal. Вот на нём, как раз, все три реализации работают точно одинаковое время! Очевидно, он встраивает функцию (типа как по указанию inline в C).
То есть, если компилятор встраивает функцию, то всё равно, куда писать алгоритм – отдельной функцией или дописывать в вызывающую!
Дальше. Устанавливал я для себя разницу в эффективности разных методов сортировки. В Turbo Pascal сортировка массива с 10000 элементов выбором давала незначительный прирост производительности (по отношению к сортировке прямым обменом "пузырьком"), а включением – более чем двукратный прирост (короче, приблизительно 11 с, 10 с и 5 с). Быстрая сортировка массива из 10000 элементов происходила мгновенно, поэтому я перенёс всю программу на Virtual Pascal, где над массивом из 1000000 элементов быстрая сортировка работала всего 16 с.
Что касается "пузырька", что здесь вышла некоторая неувязочка: массив из 1000000 элементов сортировался за 46 с, а из 10000 – за 16 с, то есть, дольше, чем в Turbo Pascal. Сортировки включением и выбором я не дождался даже на длине в 100000 элементов. Такие сильные расхождения не могу объяснить ничем, кроме как возможностью/невозможностью компилятора выполнить низкоуровневую оптимизацию алгоритма. Ведь, чем проще алгоритм, и, чем меньше в нём переходов, тем более эффективный код генерирует компилятор.
Как бы там ни было, ясно, что быстрая сортировка работает на несколько порядков быстрее прямых методов. Ну, а уже среди прямых наиболее эффективный – метод прямого включения, затем – метод прямого выбора, и, наконец, метод прямого обмена "пузырьком".