У меня есть критический код производительности, который включает в себя сортировку очень короткого массива с фиксированной длиной между примерно 3 и 10 элементами в С++ (параметр изменяется во время компиляции).
Мне пришло в голову, что статическая сеть сортировки, специализирующаяся на каждом возможном размере ввода, возможно, была бы очень эффективным способом сделать это: мы делаем все сравнения, необходимые для определения того, в каком случае мы находимся, а затем делаем оптимальное количество свопы сортировать массив.
Чтобы применить это, мы используем немного магии шаблонов, чтобы вывести длину массива и применить правильную сеть:
#include <iostream>
using namespace std;
template< int K >
void static_sort(const double(&array)[K])
{
cout << "General static sort\n" << endl;
}
template<>
void static_sort<3>(const double(&array)[3])
{
cout << "Static sort for K=3" << endl;
}
int main()
{
double array[3];
// performance critical code.
// ...
static_sort(array);
// ...
}
Очевидно, что это довольно сложно, чтобы закодировать все это, поэтому:
- Есть ли у кого-нибудь мнения о том, стоит ли это делать?
- Кто-нибудь знает, существует ли такая оптимизация в любых стандартных реализациях, например, std:: sort?
- Есть ли свободное место для реализации кода, реализующего такую сортировочную сеть?
- Возможно, можно было бы создать такую сортирующую сеть, как это статически, используя магию шаблонов.
Теперь я просто использую сортировку вставки с параметром статического шаблона (как указано выше), в надежде, что он будет поощрять разворачивание и другие оптимизации времени компиляции.
Ваши мысли приветствуются.
Update: Я написал некоторый тестовый код для сравнения "статической" вставки short и std:: sort. (Когда я говорю "статический", я имею в виду, что размер массива фиксирован и выведен во время компиляции (предположительно, позволяет разворачивать цикл и т.д.). Я получаю хотя бы 20% улучшение NET (обратите внимание, что генерация включена в выборку). Платформа: clang, OS X 10.9.
Код здесь https://github.com/rosshemsley/static_sorting, если вы хотите сравнить его с вашими реализациями stdlib.
Мне еще предстоит найти хороший набор реализаций для сортировщиков сетевых компараторов.
