В одном из соседних топиков дали ссылку на хабровскую статью http://habrahabr.ru/post/182428/ c таким вот незатейливым названием.
Статья развесистая, заумная, там и дизассемблированный код, и какие-то адовые формулы, видно что автор подошел к делу основательно, язык С окончательно разгромлен, вот цитата из заключения:
Я показал, как с помощью C++–шаблонов реализовать вычисления и кросс-аппаратную оптимизацию во время компиляции для получения ускорения в 3.5-5.3 раза для реальной задачи.
Нет таких оптимизаций в C, которые бы нельзя было применить в C++, т.к. имеется почти полная обратная совместимость. А вот в C – единственная альтернатива C++–шаблонам для подобных оптимизаций – это писать десятки, сотни и тысячи функций – вот уж где действительно copy-paste.
По большому счету, можно было бы пожать плечами и пройти дальше, я помню статьи приблизительно такого же накала вроде «как я вызываю виртуальные функции в 5 раз быстрее чем обычные», «наследование, инкапсуляция, полиморфизм - нереально быстрая разработка и последние гвозди в крышку гроба С» и т.п.
Но автор пишет «Вычисление факториала нам понадобит_ь_ся», с мягким знаком, я сам не заметил как глаза налились кровью, как скачал его код и стал разбираться.
Для тех кому лень читать статью суть такова:
Есть массив структур, автор хочет без индексов, последовательным перебором, быстро выбирать из него записи по каким-то критериям (фильтрам). Организация данных немного странная, ему в каментах сказали что можно бы «Сменить AoS на SoA» (Array of Structures на Structure of Arrays), но это осталось без ответа. Ну, хорошо, допустим что данные есть только в таком виде.
Да, все считается в один поток, на CPU.
Фильтры задаются в виде каких-то границ, в которых должно быть значение, и флага, нужно ли применять фильтр к этому полю.
Неоптимизированный вариант выглядит так: for по всем элементам, внутри цикла смотрим для каждой записи, нужно ли фильтровать по этому полю, и если да, то уже дальше проверяем попадает ли значение в диапазон.
Оптимизированный вариант: берем фильтр, анализируем его, и на основании анализа флагов запускаем циклы по всем записям. Для каждого набора флагов цикл свой. Внутри цикла уже не пересматриваем каждый раз флаги фильтра а просто смотрим, попадает ли нужное значение в диапазон.
Дальше автор приступает к селективности. В этом месте начинается магия с факториалами, формулами, в такие моменты хочется пропустить этот кусок текста и написать «В кои-то веки толковая статья про C++ в которой на живом примере показан нетривиальный способ использования шаблонов. Автор молодец.»
Насколько я понял (поправьте, если неправильно) посыл такой: если считать что данные распределены равномерно, проверку надо начинать с полей, у которых больше бит, так будет быстрее.
Ну и приводит решение с оптимизацией шаблонами. Там не очень большой файл, но когда я попробовал собрать (gcc 4.7.2) - изумился. Он собирается _несколько минут_ (да!). Интересно, как народ с этим работает? Используют pch? В общем, пришлось вынести код search в отдельную единицу трансляции.
Еще странный момент - он измеряет время вызовов функций clock()-ом. У меня он давал какие-то совсем дискретные значения, заменил на gettimeofday().
Мое решение - генератор кода на С (автор в каментах напирает на то что у него решение исключительно на С++, хорошо, пусть будет только С) здесь
Генератор очень простой - он проходит все возможные комбинации флагов фильтров (2**5) и для каждой комбинации делает свой for. То есть фактически то же самое что и в статье, но прямо в лоб
Итог, повторюсь, такой: решение «на С» почти такое же по скорости как и «на С++» (на единицы процентов быстрее). Скорость разработки - ну-у, даже у меня, не очень быстрого разумом, на это ушло всего часа 4
P.S. procoder99, можешь не возбуждаться, это на самом деле тонкий троллинг сишников (единицы процентов за 4 часа, ха-ха), я знаю как на С++ сделать быстрее
