Возможности оптимизации в языках C и C++

Интересен вариант с генерацией test_predicate с помощью LLVM в рантайме — может быть быстрее и гибче.

Как насчёт такой оптимизации?

static inline unsigned char test_predicate_12(struct T_cash_account_row const*const __restrict row, struct T_range_filters const*const __restrict range_filters)
{
    const char p0 = (row->age - range_filters->begin.age) <=  (range_filters->end.age - range_filters->begin.age);
    const char p1 = (row->code - range_filters->begin.code) <= (range_filters->end.code - row->begin.code);
    return p0 & p1;
}

static inline size_t search_12(struct T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size, struct T_cash_account_row *const __restrict result_ptr, struct T_range_filters const*const __restrict range_filters) 
{
    size_t result_size = 0;
    size_t i; /* loop index */
    for(i = 0; i < c_array_size; ++i) {
        result_ptr[result_size] = array_ptr[i];
        result_size += test_predicate_12(array_ptr + i, range_filters);
    }
    return result_size; 
}

Вы хоть попробуйте прежде, чем писать :)
Во-первых, у типичных запросов достаточно маленькая селективность, поэтому выгодней делать && с условным переходом, чем &. Аналогично и с записью в массив — быстрее с условным переходом. Этот теоретический шаблонный совет о бездумном избегании условных переходов тянется ещё со времен длиннющих конвейеров.
Во-вторых, ваш вариант возвращает неверное число строк :)
Это помимо множества синтаксических ошибок.
В свое время был написан bench с несколькими десятками вариантов. Так что, чтобы вы ни написали — скорее всего уже проверялось. Но вы ещё попробуйте.

>Казалось бы, что здесь можно ещё ускорить и оптимизировать при полном проходе без индексов?
Сменить AoS на SoA.

Знатный наброс :)

Неплохо, но есть небольшая проблемка – C-разработчикам придется вручную создать эти 32 функции, нигде в них не ошибиться перебирая все варианты и при любом изменении числа и имен полей менять нужные функции.

В С есть макросы и инлайновые функции, так что не все так плохо, как вы пытаетесь показать.

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

Также, интересны какой эффект будет при отказе от битфилдов.

К слову, эта оптимизация не применима в Java и C#, т.к. в generics невозможно использовать параметром значение, а не тип.

Ради справедливости стоит отметить, что в том же C# можно довольно легко средствами фреймфорка сгенерировать код фильтра во время исполнения и запускать вариант с нужным набором проверок.

Тот момент, когда код на асме понятнее, чем шаманства с шаблонами...)

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

Но Google C++ Style Guide рекомендует передавать неизменяемые параметры по константной ссылке const&, а изменяемые по константному указателю *const

Я, наверное, что-то путаю, но в Google C++ Style Guide говорится о const T*, а не о T* const ??

Неоднократно замечал, что при проэктировинии баз данных поле «пол» делают булевым. При чем «true» означает мужской пол, а «false» — женский.
bash.im/quote/396500

unsigned gender:1;

В данном случае, видимо, 1 означает мужской пол, а 0 — женский, т. к. цифры 0 и 1 похожи на… Ладно, не буду продолжать.

Помимо этого, даже, существуют статьи показывающие преимущества в скорости языков с компиляцией налету (JIT — Just-in-time compilation), таких как Java и C#. Сравнить последние мы оставим тем, кто считает их быстрыми, но мы объясним почему это не так

Небольшой пример, использующий динамическую генерацию кода и JIT: Ищем на java, оптимизация во время исполнения. За счет генераци «плана исполнения запроса» на лету и JIT, скорость получилась сравнимая со статической оптимизацией.

По поводу LLVM.
Я хотел реализовать этот пример на LLVM, но не стал, так как там надо писать кучу кода. Вот, например, чтобы скомпилировать return x + 1;, нужно написать:

  // Get pointers to the constant `1'.
  Value *One = ConstantInt::get(Type::getInt32Ty(Context), 1);

  // Get pointers to the integer argument of the add1 function...
  assert(Add1F->arg_begin() != Add1F->arg_end()); // Make sure there's an arg
  Argument *ArgX = Add1F->arg_begin();  // Get the arg
  ArgX->setName("AnArg");            // Give it a nice symbolic name for fun.

  // Create the add instruction, inserting it into the end of BB.
  Instruction *Add = BinaryOperator::CreateAdd(One, ArgX, "addresult", BB);

  // Create the return instruction and add it to the basic block
  ReturnInst::Create(Context, Add, BB);

(пример взят из ссылки, которую я уже кидал выше)

Но всё-таки посмотреть, как будет работать генерация кода на лету, хотелось. Поэтому я сделал некий псевдо-JIT. JIT без JIT'а. А именно: в рантайме генерирую код на си, потом компилирую его вызывая обычный компилятор, создаю таким образом разделяемую библиотеку (.so в GNU/Linux, .dll в Windows), подгружаю её в свой процесс и вызываю только что скомпилированную функцию. Да, это немного через пятую точку. И в реальных приложениях, наверное, нужно использовать настоящий JIT (например, на основе LLVM), потому что в настоящем JIT'е не тратится время на парсинг кода. Зато в моём способе не нужно писать кучу громоздкого кода для конструирования return x + 1;: просто пишем fprintf(fout, "return x + 1;");. Вдобавок такой способ портируем на любую ОС, в которой есть компилятор си, который может создавать разделяемые библиотеки.

Для начала Hello world, который демонстрирует этот трюк: paste.org.ru/?ga0au3 (для Windows и UNIX-подобных ОС). За одно этот трюк показывает, что в си можно реализовать eval (а вы думали, что eval есть только в интерпретируемых языках?).

int main(void){
	eval("printf(\"Hello, world!\\n\")");
	return 0;
}

А теперь применим всё это дело к нашей задаче: paste.org.ru/?09yt9c. Код получился быстрее, чем ваш код на шаблонах: 0.54 секунды против 0.88 «шаблонного» решения на моём компьютере. При сравнении времени я во всех алгоритмах использовал c_array_size, равный 200 000 000, а не 10 000 000, а то на моём компьютере выполнялось слишком быстро.

Причина такого ускорения в том, что в моём способе в момент псевдо-JIT'а известен не только шаблон поиска (т. е. массив use_filter), но и сами граничные значения (begin и end). В вашем же решении на шаблонах генерируются шаблоны для каждого варианта use_filter, но begin и end по-прежнему остаются runtime-переменными. Естественно, то же самое получилось бы и при использовании LLVM (в смысле LLVM имел бы такую же скорость, как и мой псевдо-JIT).

Чтобы убедиться в том, что причина такого ускорения именно в константности begin и end, я написал специальный вариант моего кода, в котором begin и end являются переменными времени исполнения. Вот он: paste.org.ru/?q7gu4p. Как и следовало ожидать, время выполнения получилось такое же, как и у решения на шаблонах: 0.88 секунд.

Я проверил, что весь код компилируется в следующих двух окружениях:

• Debian GNU/Linux Wheezy amd64, gcc 4.7.2, физическая машина, Intel Core i7, 2 ГГц
• Windows 8 Release Preview x86_64, MVC++ 2010 Express, виртуальная машина

Тестирование времени проводил в первой из них. Ещё раз табличка с результатами:

Неоптимизированный поиск на C        | 1.41, 1.34, 1.47 (было 3 теста)
Шаблоны C++                          | 0.88
Псевдо-JIT                           | 0.54 (+0.02 на саму "компиляцию на лету")
Псевдо-JIT с переменными begin и end | 0.88 (+0.02 на "компиляцию")

Функция clock, которую вы используете, совсем неточная, выдаёт время лишь с точностью до 0.01 на GNU/Linux. Надо было какую-нибудь другую. Но мне не хотелось разбираться, так что я использовал её. Вдобавок я не учитывал советы, данные тут: habrahabr.ru/post/180161. И вообще, все тесты я проводил по одному разу. Так что можете всё перетестить и получить более точные результаты.

И хватит всем говорить «Приведите пример и результаты тестов». У человека может быть время написать коммент, но не быть времени для написания примера.