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

Существует мнение, что C++ имеет заметные накладные расходы по сравнению с C и поэтому он медленнее. Помимо этого, даже, существуют статьи показывающие преимущества в скорости языков с компиляцией налету (JIT — Just-in-time compilation), таких как Java и C#. Сравнить последние мы оставим тем, кто считает их быстрыми, но мы объясним почему это не так. А C и C++ мы сравним на примере задачи поиска данных.
Задача поиска данных часто встречается в: веб-сервисах, системах управления баз данных (СУБД), гео-поиске и аналитике.
Сначала для простоты объяснения поставим задачу поиска элементов полным проходом по массиву из 10 000 000 элементов (структур), содержащих 5 полей с диапазонами значений: amount_of_money(0-1000000), gender(0-1), age(0-100), code(0-1000000), height(0-300). А в следующих статьях добавим в решение индексный поиск.
Мы будем писать кроссплатформенно под MSVC11(MSVS2012) и GCC 4.7.2, и использовать в них частично реализованный стандарт C++11.

1. Решение на C


Простейшим решением этой задачи на C будет создать структуру битовых полей занимаемую 8 байт (общее правило, в отсутствии директивы #pragma pack(push,1), поля не могут пересекать границы размера их базовых типов, в нашем случае unsigned – 32 бита):
/* Fields */
enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e, last_e };

struct T_cash_account_row {
	// 1 – double word (32 bits)
	unsigned code:20;			// 0 - 1000000
	unsigned gender:1;			// 0 - 1
	unsigned age:7;			// 0 - 100	
	// 2 – double word (32 bits)
	unsigned amount_of_money:20;	// 0 - 1000000
	unsigned height:9;			// 0 – 300
};

Выделить память под 10 000 000 таких элементов:
const size_t c_array_size = 10000000;
struct T_cash_account_row *const array_ptr = ( struct T_cash_account_row *)calloc(c_array_size, sizeof(struct T_cash_account_row));
    if (array_ptr == NULL) {
		printf ("calloc error\n");
		exit(1);
	}

В цикле заполнить случайными значениями в пределах диапазонов заданных по условию:
/* Generate random data for the one row */
static inline struct T_cash_account_row generate_row() {
	struct T_cash_account_row cash_account_row;
	cash_account_row.age = rand() % 100;
	cash_account_row.amount_of_money = (rand() % 1000)*(rand() % 1000);
	cash_account_row.code = (rand() % 1000)*(rand() % 1000);
	cash_account_row.gender = rand() % 2;
	cash_account_row.height = rand() % 300;
	return cash_account_row;
}
/* ----------------------------------------------------------------------- */
/* in int main() { … } */

	/* Fill table random data */
	for(i = 0; i < c_array_size; ++i) 
		array_ptr[i] = generate_row();

Создать структуру поискового запроса-фильтра, где last_e – перечисление со значением числа полей в строке (C++03 7.2 Enumeration declarations):
/* Filters */
struct T_range_filters {
    struct T_cash_account_row begin, end;
    /* bytes array or bitset from https://gist.github.com/jmbr/667605 */
    unsigned char use_filter[last_e]; 
};
/* ----------------------------------------------------------------------- */

Здесь use_filter[] используется для указания – фильтровать ли по данному условию-полю или нет.
И производить поиск проверкой по заданным полям проходя по всем элементам массива в цикле:
/* Compare row with filters */
static inline unsigned char test_predicate(struct T_cash_account_row const*const row, 
    struct T_range_filters const*const range_filters) 
{    
    return 
        (!range_filters->use_filter[amount_of_money_e] || 
            (row->amount_of_money >= range_filters->begin.amount_of_money &&
            row->amount_of_money <= range_filters->end.amount_of_money)) &&
        (!range_filters->use_filter[gender_e] || 
            (row->gender >= range_filters->begin.gender && 
            row->gender <= range_filters->end.gender)) &&
        (!range_filters->use_filter[age_e] || 
            (row->age >= range_filters->begin.age && 
            row->age <= range_filters->end.age)) &&
        (!range_filters->use_filter[code_e] || 
            (row->code >= range_filters->begin.code && 
            row->code <= range_filters->end.code)) &&
        (!range_filters->use_filter[height_e] || 
            (row->height >= range_filters->begin.height && 
            row->height <= range_filters->end.height));
}
/* ----------------------------------------------------------------------- */

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

Ссылка на рабочий код целиком на GitHub.com
Казалось бы, что здесь можно ещё ускорить и оптимизировать при полном проходе без индексов?
  • Развернуть цикл, для уменьшения числа сравнений с условием цикла и делать за одну итерацию несколько фильтраций test_predicate? – Это слишком мало по сравнению с от 5 до 15 сравнений нашей строки во встраиваемой функции test_predicate и по сравнению с обращением к RAM.
  • Делать prefetching-cache? – Можно и на C, и на C++, но в рамках нашей задачи это мало что даст, т.к. многократный поиск и так закэширует в LLC(L3) сколько сможет, а весь массив в 80 МБ в любом случае не сможет.
  • Использовать векторные команды сравнения из SSE: CMPSS, COMISS, UCOMISS? – Можно и в C, и в C++. Но эта оптимизация не переносима на отличные от x86/x64 процессоры такие, как ARM или Power[PC].
  • Можно использовать ключи оптимизации компилятора и PGO, на C и C++. PGO – это в любом случае компромисс, т.к. создается оптимизированный код для одного пути исполнения программы в ущерб остальным путям, т.е. при каких-то входных данных будет быстрее, а при каких-то медленнее. Я же покажу как создать оптимизированный код под каждый из возможных путей исполнения, и только в наиболее критичной к скорости части программы.

На этом низкоуровневая (не архитектурная) оптимизация на C заканчивается, и любые из этих оптимизаций применимы на C++.

2. Как выглядит ещё одна оптимизация на C и C++


  1. Во-первых, приведенное выше на C решение легко компилируется на компиляторе C++ без каких-либо изменений, т.к. в большинстве случаев имеет место обратная совместимость.
    Результат в онлайн компиляторе на C: ideone.com
    Результат в онлайн компиляторе на C++11: ideone.com
    Я закомментировал подсчет random seed
     /* srand (time(NULL)); */
    , чтобы сравнивать результаты разных запусков программы. Но вы можете раскомментировать его и убедиться, что абсолютное время выполнения меняется, но относительное ускорение от моих оптимизаций остается примерно одинаковым.
  2. Во-вторых, особо ушлые C-разработчики могли предложить ещё одну оптимизацию – создать 2^5 = 32 варианта функций test_predicate/search на каждый вариант числа условий поиска, сохранить указатели на них в массив и выбирать нужный вариант во время исполнения в зависимости от условий поиска. Это заметно сократит число сравнений.

Допустим пришло условие поиска по 2-ум полям из 5-ти: age и code. Тогда вызываем функцию search_12():
/* Compare row with filters */
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) 
{    
    return 
     (row->age >= range_filters->begin.age && row->age <= range_filters->end.age) &&
     (row->code >= range_filters->begin.code && row->code <= range_filters->end.code);
}
/* ----------------------------------------------------------------------- */

/* search */
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) {
		if(test_predicate_12(array_ptr + i, range_filters)) 
			result_ptr[result_size] = array_ptr[i], ++result_size;
	}
	return result_size; 
}


Хотя число условий в этой функции и уменьшилось до 4-ех с 15-ти первоначальных. Реально же в варианте решения на C сравнений исполнялось из 15 только 9, для условия поиска по 2-ум полям – это видно в дизассемблере функции test_predicate: github.com. Это происходило потому, что после каждого сравнения use_filter[] == false шел условный переход на сравнения по следующему полю. Т.е. помимо этих 4-ех сравнений там исполнялись ещё только 5 сравнений с use_filter[].
Описываемое здесь решение, например, для поиска по 2-ум полям из 5-ти, даст ускорение в 1.3 раза. Неплохо, но есть небольшая проблемка – C-разработчикам придется вручную создать эти 32 функции, нигде в них не ошибиться перебирая все варианты и при любом изменении числа и имен полей менять нужные функции. Ну и если вам понадобиться подобное решение для таблицы с 10 полями, то вам придется создать 1024 функций. В общем просто сказка при доработке кода!
Дополнительно путаница создается при добавлении полей типов с нетривиальным сравнением, как например строка char[] сравниваемая через strcmp(). В C++ это решается созданием пользовательского типа с перегруженным оператором сравнения. (Операторы для фундаментальных типов в C++ перегружать нельзя – одним из параметров оператора обязательно должен быть пользовательский класс.)
А задача автоматического создания нужного числа оптимизированных функций на C++ легко решается раскруткой шаблонов (unrolling of template).
Кому-то может показаться, что это вполне можно решить на C и в run-time, и незачем городить 32 – 1024 функций оптимизированных в compile-time. Допустим создать массив указателей на функции числом равным числу условий, в нашем случае 5, и при каждом поиске заполнять этот массив только теми функциями с условиями, которые используются для данного поискового запроса. А в конце добавлять указатель на функцию возвращающую 1 (true). И каждая из таких функций получает указатель на массив функций, такого же типа, как и сама, и индекс следующей вызываемой функции. Разочарую, но в таком случае функции не встроятся (inline), а их вызов ничуть не быстрее сравнений с условными переходами.
Вот рабочий вариант этого run-time решения на C: GitHub.com
Как видим в MSVC скорость упала с 74 мс, до 84мс. А в GCC ещё больше – до 117мс. На C такая оптимизация не возможна, а возможна лишь оптимизация через создание большого числа функций.

3. Решение на C++


Раскрутка шаблонов осуществляется созданием экземпляра (инстанцированием) одного шаблона другим шаблоном, со значением параметра шаблона на единицу меньше, чем у создающего. А для шаблона со значением параметра 0 мы создаем пустую, ничего не делающую специализацию. В результате инстанцируя раскрутку шаблона с параметром N, мы получаем N – экземпляров раскручиваемого шаблона, в каждом из которых вызывается конструктор или inline оператор вызова следующего экземпляра шаблона. В такой раскрутке могут участвовать, как шаблонные функции, так и шаблонные классы.
Чтобы вынести раскрутку из логики самих шаблонов, мы создадим шаблонный класс раскрутки. Одним параметром он будет принимать число, на которое необходимо раскрутить, а вторым параметром будет принимать шаблон, который нужно раскрутить:
// The templated constructor of unrolling of the class (no return, mandatory call to the constructor, called once)
template<unsigned unroll_count, template<unsigned> class T>
struct T_unroll_constructor {
	T_unroll_constructor<unroll_count-1, T> next_unroll;
	T<unroll_count-1> functor;
	template<typename T1> inline T_unroll_constructor(T1 & val1) : next_unroll(val1), functor(val1) {}
};
// End of unroll
template<template<unsigned> class T>
struct T_unroll_constructor<0, T> { 
	template<typename T1> inline T_unroll_constructor(T1 &) {} 
};
// -------------------------------------------------------------------------


Теперь создадим базовый абстрактный класс поиска. Унаследуем от него шаблонный дочерний класс, принимающий параметром шаблона 32-битное значение unsigned int, каждый бит которого будет означать использовать ли соответствующий фильтр или нет:
// Abstract base class of filters for each search variant (range_filters)
struct T_filter {
	// search
	virtual size_t search(T_cash_account_row const*const __restrict array_ptr, 
const size_t c_array_size,	T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) = 0;
};
// -------------------------------------------------------------------------

// The filters for each search variant (range_filters)
template<unsigned index_pred>
struct T_custom_filter : T_filter {

	inline unsigned char test_predicate(T_cash_account_row const*const __restrict row, 
		T_range_filters const*const __restrict range_filters) 
	{    
		return 
			(!(index_pred & 1<<amount_of_money_e) || 
 				(row->amount_of_money >= range_filters->begin.amount_of_money &&
 				row->amount_of_money <= range_filters->end.amount_of_money)) &&
			(!(index_pred & 1<<gender_e) || 
 				(row->gender >= range_filters->begin.gender && 
 				row->gender <= range_filters->end.gender)) &&
			(!(index_pred & 1<<age_e) || 
 				(row->age >= range_filters->begin.age && 
 				row->age <= range_filters->end.age)) &&
			(!(index_pred & 1<<code_e) || 
 				(row->code >= range_filters->begin.code && 
 				row->code <= range_filters->end.code)) &&
			(!(index_pred & 1<<height_e) || 
 				(row->height >= range_filters->begin.height && 
 				row->height <= range_filters->end.height));
	}
	// -------------------------------------------------------------------------

	// search
	virtual size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,	T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) final
	{
		size_t result_size = 0;
		size_t i; // loop index
		for(i = 0; i < c_array_size; ++i) {
			if(test_predicate(array_ptr + i, range_filters)) 
				result_ptr[result_size] = array_ptr[i], ++result_size;
		}
		return result_size;
	}
};
// -------------------------------------------------------------------------

Т.к. параметр шаблона index_pred и перечисления amount_of_money_e, gender_e … известны на этапе компиляции, то часть условий компилятор выкинет, как всегда верные. Фактически мы помогает компилятору оптимизировать нашу программу. Это самое важное в данном решение!
А теперь покажем, как развернется этот шаблонный дочерний класс template<unsigned index_pred> struct T_custom_filter в 32 класса. Создадим 32 объекта каждого из них и сохраним на них указатели базового типа в статичный массив std::array<>. А во время выполнения будем полиморфно обращаться к нужному объекту, в зависимости от условий поиска:
class T_optimized_search {
	// unroll tamplates
	template<unsigned index_pred>
	struct T_unroll_find {
		template<typename T> T_unroll_find(T &filters) { 
			filters[index_pred].reset( new T_custom_filter<index_pred>() ); 
		}
	};
	// -------------------------------------------------------------------------

	// Get index of T_test_pred version for current search range
	inline unsigned get_index_pred(T_range_filters const*const __restrict range_filters) {
		unsigned result = 0;
		for(size_t i = 0; i < last_e; ++i) 
			result |= range_filters->use_filter[i]?(1<<i):0;
		return result;
	}

	std::array<std::unique_ptr<T_filter>, 1<<last_e> filters;
	T_unroll_constructor< 1<<last_e, T_unroll_find> fill_filter;
public:
	T_optimized_search() : fill_filter(filters) {}

	// C++ optimized search
	inline size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,	T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) 
	{
		auto const& filter = filters[get_index_pred(range_filters)];
		return filter->search(array_ptr, c_array_size, result_ptr, range_filters);
	}
};
// -------------------------------------------------------------------------

Здесь функция unsigned get_index_pred((T_range_filters const*const __restrict range_filters) возвращает индексный номер необходимого поискового объекта для данных условия поиска range_filters.
Используется аналогичным образом, как и решение на C:
T_optimized_search optimized_search;	// C++ optimized search
result_size = optimized_search.search(array_ptr, c_array_size, result_ptr, &range_filters);


Вот сравнение дизассемблерного кода двух функций test_predicate на C и оптимизированной на C++, скомпилированных на MSVC11(MSVS 2012), с моими комментариями – наглядно видна разница если смотреть через TortoiseDiff: ссылка diff на GitHub.com
Мы видим, что от 15 сравнений, 9 из которых при наших поисковых условиях исполняются, остались только 4 сравнения – ассемблерные команды cmp.
«Картинка disasm из TortoiseDiff c моими комментариями»
image

Фактически, с помощью шаблонов мы вынесли из цикла во вне проверку на использование каждого из фильтров. А внутри цикла получили значения использования фильтров use_filter[] известные в compile-time, что позволило компилятору исключить их во время оптимизации. Т.е. данная оптимизация применима ко всем подобным случаям выноса вычислений или проверок из цикла во вне.

В примере на C++ я использовал C-style способ передачи параметров в функцию по константному указателю *const, чтобы в diff между C и C++ видеть изменения касающиеся только обсуждаемой оптимизации. Однако, используя интерфейсы в C++-style, функция может принимать параметры и по ссылке &, что исключит возможность забыть const после * и это несколько короче. Но Google C++ Style Guide рекомендует передавать неизменяемые параметры по константной ссылке const&, а изменяемые по константному указателю *const. Если код написан в таком стиле, то вы полностью контролируете изменение (или не изменение) ваших переменных передаваемых в чужую функцию – т.е. если передаете по значению
void func(int const& a, int *b) {} // function of other developer in Google C++ Style

int* a = new int(1); 
int b = 2; 
func(*a, b);

то компилятор выдаст ошибку о том, что функция хочет изменить ваш параметр b. Это особенно важно при разработке через тестирование TDD, когда внешние вызовы тестов жестко задают формат интерфейсов, и в данном случае такой вызов во внешних тестах сказал бы разработчику функции о том, что b – изменять нельзя.
А если передаем по указателю (или со взятием адреса):
void func(int const& a, int *b) {}	// function of other developer in Google C++ Style

int* a = new int(1); 
int b = 2; 
func(*a, &b);

то скомпилируется без ошибок. И нам даже из вызова функции очевидно, что функцией переменная a не изменяется, а переменная b изменяется. А в случае применения TDD мы говорим о том, что разработчик должен принимать b по указателю, а значит и должен изменять её. И a он должен будет принять по константной ссылке или значению, и не сможет менять её внешнее значение.
Но в C, где нет ссылок, такой подход не возможен, т.к. если функция всегда принимает только по указателю, то на стороне вызывающего нельзя гарантировать невозможность их модификации, а передача по значению переменных пользовательского типа может иметь значительные накладные расходы.


4. Заключение


Вот полностью рабочий вариант этого решения на C++: GitHub.com
У меня на GCC4.7.2 с ключами –O3 –march=native, CPUCore i5 K750 и размером exe-файла в 74КБ результат такой:
Generated rows: 10000000
C++-Searching…
C++-optimized search took 0.061000 seconds.
Found rows: 38
C-Searching…
C-search took 0.089000 seconds.
The C++ faster than C: 1.459016 times
Found rows: 38

А на MSVC11(MSVS2012) с ключами /O2 /Ob2 /Oi, CPU Core i5 K750 и размером exe-файла в 138КБ получился результат:
Generated rows: 10000000
C++-Searching…
C++-optimized search took 0.056000 seconds.
Found rows: 38
C-Searching…
C-search took 0.074000 seconds.
The C++ faster than C: 1.321429 times
Found rows: 38

Как мы видим время исполнения упало с 74мс, до 56мс, т.е. скорость выросла в 1.3 раза. В принципе не плохо.
Всего в 1.3 раза? А как насчет ускорения в 3.5 – 5.3 раза для поиска полным проходом, есть идеи?
Вывод – чем больше компилятору известно во время компиляции, тем лучше он сможет оптимизировать программу. А в этом ему как ничто другое помогают шаблоны (templates).
К слову, эта оптимизация не применима в Java и C#, т.к. в generics невозможно использовать параметром значение, а не тип.
В следующей статье хардкорное решение с ускорением в 3.5 – 5.3 и все ещё без индексов. Но использоваться решение будет далее и при индексном поиске.

Средняя зарплата в IT

111 111 ₽/мес.
Средняя зарплата по всем IT-специализациям на основании 6 844 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 93

    +2
    Интересен вариант с генерацией test_predicate с помощью LLVM в рантайме — может быть быстрее и гибче.
      +3
      Приведите пример и результаты тестов.
        0
        Таки да, это решение выглядит рациональнее, чем идея сгенерировать заранее код для всех возможных вариантов предиката/порядка сравнений.
          +1
          В теории выглядит-то много что рациональнее, но на тестах многое сливалось, а значит теории были не верны.
          Ну так приведите своё решение с генерацией test_predicate с помощью LLVM в рантайме и результаты тестов, сравним, пример-то простой :)
        0
        Как насчёт такой оптимизации?

        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; 
        }
          +8
          Вы хоть попробуйте прежде, чем писать :)
          Во-первых, у типичных запросов достаточно маленькая селективность, поэтому выгодней делать && с условным переходом, чем &. Аналогично и с записью в массив — быстрее с условным переходом. Этот теоретический шаблонный совет о бездумном избегании условных переходов тянется ещё со времен длиннющих конвейеров.
          Во-вторых, ваш вариант возвращает неверное число строк :)
          Это помимо множества синтаксических ошибок.
          В свое время был написан bench с несколькими десятками вариантов. Так что, чтобы вы ни написали — скорее всего уже проверялось. Но вы ещё попробуйте.
            +2
            >Казалось бы, что здесь можно ещё ускорить и оптимизировать при полном проходе без индексов?
            Сменить AoS на SoA.
              +8
              Знатный наброс :)
              Неплохо, но есть небольшая проблемка – C-разработчикам придется вручную создать эти 32 функции, нигде в них не ошибиться перебирая все варианты и при любом изменении числа и имен полей менять нужные функции.
              В С есть макросы и инлайновые функции, так что не все так плохо, как вы пытаетесь показать.

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

              Также, интересны какой эффект будет при отказе от битфилдов.
                –1
                для поиска, я бы использовал hash_table. Есть много разных реализаций.
                  0
                  Вопрос был не про то, смотрите — автор создает кучу специализированных функций, из них надо в рантайме выбрать наиболее подходящую для входных данных. Решение влоб — инициализировать таблицу указателей на специализированные функции вручную, но это не красиво.

                  В своей другой статье автор предлагает решение основанное на инициализации таблицы в рантайме при помощи рекурсивной шаблонной функции, в принципе годный вариант.
                    0
                    Годный run-time вариант на C во второй главе ускоряет только в 1.6-1.8 раза, против в 3.5-5.3 раза на C++. Если готовы купить в 2-3 раза больше/дороже серверов и заплатить за оборудование вместо 2 млн, 6 млн, то C годный вариант :)
                    Кстати, если читали внимательно, то и в этой статье сравнивается run-time вариант на C в конце второй главы, который только замедляет выполнение.
                      –5
                      Просто вы не умеете его готовить (с)
                        +3
                        Пустословие. Выкладывайте своё решение, сравним :)
                          –5
                          Сначала сделайте так, чтобы ваш тест нормально собирался, и вобще соответствовал принципам правильного бенчмарка. Тогда может быть кто-то и захочет с вами померяться.
                            +1
                            Научитесь пользоваться компилятором GCC 4.7.2 на ideone.com, тогда может кто-то захочет с вами дискутировать.
                            Справедливости ради замечу, что действительно в моем примере нет полноценного бенчмарка. Он будет в третье статье, в более реальном примере с Ordered Hash/IOT/IOS.
                    +1
                    Использовать hash_table для поиска по диапазонам нескольких полей — круто!

                    Прочитайте последнюю главу второй статьи, там упоминается кое-что об упорядоченным хэш-индексе.
                    +3
                    В С есть макросы и инлайновые функции, так что не все так плохо, как вы пытаетесь показать.

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

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

                    Если вам не лень писать 32 специализированных функций на C, выкладывайте пример. А потом вам вдруг приходит задача добавить 2 поля, и вы пишите уже 128 функций :)
                    На C++ шаблоны пишутся быстрее и гораздо гибче при изменении числа полей и их названий.

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

                    Это оффтопик. Но что вам мешает попробовать?
                      –2
                      Что значит есть инлайновые функции, как будто я их здесь не использовал при сравнении?
                      Подумайте, как инлайновые функции можно использовать в задаче кодогенерации (подсказка: устранение константных выражений при оптимизации).

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

                      Если вам не лень писать 32 специализированных функций на C, выкладывайте пример. А потом вам вдруг приходит задача добавить 2 поля, и вы пишите уже 128 функций :)
                      Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++, а мне такая постановка вопроса кажется скучной — для разных задач я использую и Си и C++ и еще штук пять других языков. На случай, если вы считаете всех собеседников по умолчанию идиотами, прошу ознакомиться.

                      Также, интересны какой эффект будет при отказе от битфилдов.
                      Это оффтопик. Но что вам мешает попробовать?

                      У меня ваш пример не собирается — clang 4.2 просто падает.

                      На счет оффтопика категорически не согласен. Во-первых, обращение к битфилдам не бесплатное (нужно применять маски и делать сдвиги), и на таком микробенчмарке это может быть заметно. Во-вторых, это нас вплотную подводит к мысли — какое влияние на производительность окажет увеличение размера элемента? А что если элемент «размазан» по памяти (например имеет два строковых поля, строки аллоцируются отдельно от самого элемента)? Стоимость кеш-промаха сотни тактов. Вам в самом деле надо искать по неупорядоченному списку элементов с целочисленными полями, все поля сумарно влезают в 64 бита? В противном случае, ваши оптимизации станут неэффективны.

                      Вот, интересная статистика.
                        +3
                        Подумайте, как инлайновые функции можно использовать в задаче кодогенерации (подсказка: устранение константных выражений при оптимизации).

                        Вы у меня видели не inline функции, кроме main() и тех, что должны быть виртуальными?

                        я использую и Си и C++ и еще штук пять других языков

                        Использовать языки и знать их — это разные вещи.

                        «Сами придумали — сами обиделись». Только вы могли придумать использовать для скоростного поиска строки аллоцируемые отдельно от элемента.
                        Я не считаю никого идиотом. Мне все равно. Меня интересуют только решение и результат.

                        Разница в том, что мой аргумент рабочий пример и результат тестов, а ваш аргумент, что вам скучно. И от скуки пишите что попало.

                        Т.е. вы обсуждаете то, что даже не смогли скомпилировать? Попросите кого-нибудь скомпилировать за вас. Могу только доказать, что это возможно: GCC 4.7.2 на ideone.com
                        Когда осилите скомпилировать и предложите свой вариант — продолжим.
                          –3
                          Подумайте, как инлайновые функции можно использовать в задаче кодогенерации (подсказка: устранение константных выражений при оптимизации).
                          Вы у меня видели не inline функции, кроме main() и тех, что должны быть виртуальными?
                          Ответ не в тему. Подумайте-подумайте, гуру шаблонов вы наш.

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

                          Разница в том, что мой аргумент рабочий пример и результат тестов, а ваш аргумент, что вам скучно. И от скуки пишите что попало.

                          Ваш аргумент — синтетический тест. Мой аргумент — я знаю об этой теме не меньше вашего.

                          Впрочем, если вы не способны к нормальному общению, и стремитесь любую беседу превратить в бокс по переписке, то я пожалуй от дальнейшего участия воздержусь.
                            +2
                            Куда уж мне до вас знающего C, C++ и ещё 5 языков программирования.
                            Вы действительно думаете, что я сейчас буду гадать, что за фантазии пришли в вашу голову, которые вы стесняетесь прямо сказать в виде кода?

                            Только вы могли придумать использовать для скоростного поиска строки аллоцируемые отдельно от элемента.

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

                            Спасибо Кэп.
                              +2
                              Куда уж мне до вас знающего C, C++ и ещё 5 языков программирования.
                              У меня еще и ВО есть)

                              Давайте подведем итоги?
                              • В статье представлена техника для генерации специализированных вариантов функций, с целью сократить число условных переходов, методами шаблонного метапрограммирования на C++.

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

                                Если рассматривать статью исключительно в контексте сравнения возможностей языков Си и C++, то все более менее ок. Задача специально подобрана так, чтобы лучше показать превосходство C++. Решение на Си или потребует кодогенерации или будет сложнее (LLVM) или будет хуже поддерживаемым чем на C++ (макросы), я с вами согласен.
                                0
                                Скажу больше. Эта статья написана только для того, чтобы проще было понять вторую статью.
                                Вторая статья о кросс-аппаратной оптимизации через шаблоны, и очень странно ждать рассказы об аппаратно-зависимых кэшах.
                                К тому же строка занимает 8 байт и выровнена по границам кэшей.

                                Исходя из выше сказанного, все ваши голословные придирки не подтвержденные кодом, и воспринимаются как не уместные.

                                Конкретно в данной постановке задачи поиска полным проходом, с данным числом и типами полей, prefetching-cache ничего не даст, о чем написано в первой главе.
                                  –1
                                  При чем тут префетч? Нужно понимать, что с чуть менее cache-friendly структурой данных, чем что-то с целочисленными полями, умещаюшимися в 8 байта, значимость вычислительных оптимизаций упадет из-за cash miss. Подавляющее число реальных данных — именно такие.

                                  Поэтому я и говорю — пример игрушечный. Код есть ниже.
                                    +1
                                    Послушайте, есть реальные проекты с реальными данными, на которых это реально дает существенный профит.
                                    Не упадет, вы не знаете что такое IOT и стратегия IOS, вы плохо в этом разбираетесь потому, что подобные оптимизации применяются для последовательного доступа после сужения поиска при Index Range Scan используя IOT/IOS. Мы уже убедились, у вас может упасть что угодно, хоть компилятор, хоть доступ к строкам, которые вы додумались аллоцировать отдельно. Надеюсь больше не надо объяснять, что аппаратно зависимые вещи не предмет статей о кросс-аппаратной оптимизации через шаблоны?
                                      –2
                                      Послушайте, я вас целый день пытаю на предмет практической применимости а вы все упражняетесь в остроумии. Так держать!
                                        +1
                                        Вы действительно думаете, что я сейчас вам вышлю ТЗ реальной задачи, где все это решено и дам VPN в банки, где это практически применено, что у вас в голове вообще происходит?
                                          0
                                          А просто сказать СУБД/банковская аналитика и не вставать в позу нельзя было?
                            +7
                            На правах взгляда со стороны:

                            >Ваш аргумент — синтетический тест. Мой аргумент — я знаю об этой теме не меньше вашего.

                            Если честно, то даже самый синтетический тест — куда более весомый аргумент, чем «я автор статей, текстов и постов знаю пять языков, и ваще очень умный».

                            Вы бы куда меньше времени потратили на написание своего правильного теста, чем на голые комментарии с пустой критикой.

                            Кстати, то, что компилятор «просто падает» на каком-либо коде — это камень в первую очередь в огород компилятора. И не просто камень, а здоровенный булыжник. Даже если код написан с нарушением всех мыслимых и немыслимых стандартов, компилятор падать не должен.
                              –3
                              стати, то, что компилятор «просто падает» на каком-либо коде — это камень в первую очередь в огород компилятора. И не просто камень, а здоровенный булыжник. Даже если код написан с нарушением всех мыслимых и немыслимых стандартов, компилятор падать не должен.

                              Рекурсивное инстанцирование шаблонов глубиной в 5000 это весьма серьезный стресс для компилятора. Стандарт языка C++ рекомендует поддерживать глубину не менее 17.

                              Вы бы куда меньше времени потратили на написание своего правильного теста, чем на голые комментарии с пустой критикой.

                              Тут мы с вами расходимся во мнениях. Критика была аргументированная.
                                0
                                >Рекурсивное инстанцирование шаблонов глубиной в 5000 это весьма серьезный стресс для компилятора. Стандарт языка C++ рекомендует поддерживать глубину не менее 17.

                                Клики мышкой с частотой 10 раз в секунду — это весьма серьёзный стресс для любого приложения.
                                Текстовый файл размером 2 гигабайта… ну вы поняли, да?

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

                                >Критика была аргументированная.

                                Но по-прежнему ничем не подтверждённая.

                                «Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++» — да, он доказывает превосходство С++ на данной конкретной задаче, и у него есть на это основания — конкретный тест. Если вы хотите опровергать — опровергайте предметно, а не «я знаю лучше, вот тут будет так-то и так-то, но доказывать ничего не собираюсь». Это на опровержение ну никак не тянет.
                                  +3
                                  «Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++» — да, он доказывает превосходство С++ на данной конкретной задаче, и у него есть на это основания — конкретный тест. Если вы хотите опровергать — опровергайте предметно, а не «я знаю лучше, вот тут будет так-то и так-то, но доказывать ничего не собираюсь». Это на опровержение ну никак не тянет.

                                  Вот скрипт на python который генерирует все возможные специализированные варианты функции—компаратора на Си. Это канает?

                                  from itertools import permutations as p
                                  from math import pow
                                  fields = ['','code','gender','age','amount_of_money','height']
                                  def field_list_to_index(fl):
                                      return sum(fields.index(i)*int(pow(len(fields),n)) for n,i in enumerate(fl))
                                  for params in set(fl[:fl.index('')] for fl in p(fields) if fl[0]):
                                      index = field_list_to_index(params)
                                      print 'BEGINF(%s)'%index
                                      print '\n'.join('  COMPAR(%s)'%p for p in params)
                                      print 'ENDF(%s)'%index
                                  

                                  Генерируется такая портянка кода:

                                  BEGINF(377)
                                    COMPAR(height)
                                    COMPAR(gender)
                                    COMPAR(amount_of_money)
                                    COMPAR(code)
                                  ENDF(377)
                                  BEGINF(31)
                                    COMPAR(code)
                                    COMPAR(height)
                                  ENDF(31)
                                  

                                  Исходный код таблицы функций. Время компиляции полученного Си кода — 2 мс.
                                    +1
                                    >Вот скрипт на python который генерирует все возможные специализированные варианты функции—компаратора на Си. Это канает?

                                    Разумеется! Сразу же становится видно, что Си рвёт плюсы как тузик грелку.
                                  +4
                                  Кстати, это хороший повод запостить багрепорт.
                                  0
                                  Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
                                  Прекрасно всё собрал.
                                    0
                                    У меня 425.0.28, падает не clang а линкер c SIGBUS.
                        0
                        К слову, эта оптимизация не применима в Java и C#, т.к. в generics невозможно использовать параметром значение, а не тип.


                        Ради справедливости стоит отметить, что в том же C# можно довольно легко средствами фреймфорка сгенерировать код фильтра во время исполнения и запускать вариант с нужным набором проверок.
                          0
                          Приведите пример и результаты тестов.
                            +5
                            Ну сольются на этом синтетическом тесте и джава, и шарп. Скажем, будут в два раза медленнее.

                            Но ваш код — будет в пять раз дольше писаться, в десять раз дороже поддерживаться. Подходит не каждый компилятор — это минус, как и любая дополнительная зависимость, особенно не идущая из коробки. Разобраться в вашем коде могут немногие — это минус: сложно найти реально сильного программиста, и стОят такие дофига. Кто может разобраться, тот будет разбираться долго — это минус: нужно добавлять новые фичи, а он будет разбираться в том, как добавить поле в этого монстра.

                            Я не спорю, код крутой, быстрый. И в отличие от многих статей с финтами ушами, как вы заметили, может быть успешно применён. Но он в индустрии мало кому нужен. Железо в долгосрочной перспективе — почти всегда дешевле.

                            Скажите, этот код у вас из реального проекта, или это зарядка для мозгов?
                              0
                              Кстати, даже у Java не так все плохо. На Q8200 (который слабее i750) решение в лоб для 10 000 000 работает около 110ms. Правда выжирает больше гигабайта.
                              Решение для миллиона: ideone.com/LFe228 (иначе падает). Нолик добавлять в первой строке метода main
                              Второй тест — без функции сравнение, она руками инлайнена в цикл, проверял собственно работу в JVM инлайна.
                              Что выжирает так память я не понял.
                                +2
                                На домашней машине (Core i3 380M):
                                Неоптимизированный алгорит C с максимальными настройками компилятора -march=native -O3 —
                                82мс
                                Java сверху по ссылке java -Xms3g -Xmx3g -server -verbose:gc Test
                                от 51мс до 150мс, потребление память — чуть меньше 300Миб
                                Результаты Java сильно разняться по-видимому из-за рантайм оптимизаций, лучший результат был, когда выбрались все строки, то есть JVM пыталась сделать в рантайме оптимизации по типу тех, что автор статьи делает во время компиляции.

                                От себя добавлю, что если вы не готовы к оптимизациям, описанным в статье, лучше брать Яву.

                                P.S.Насчет выжирания гигабайта, я ошибся, просто с менее чем гигабайтом выделенной памяти включался GC.
                                  0
                                  Пересчитал для 100 итераций. Если вручную встроить провеку в цикл — то 117мс, если не встраивать, то 147мс.

                                  Интересно ведет себя garbage collector. Если его вызов не форсировать, то удаляет обекты он в средним по 270 мс, очищая память примерно на половину, после примерно каждой второй итерации.
                                  Если же перед каждой новой итерацией, перед генерацие нового массива данных делать Runtime.getRuntime().gc(), то делается 2 вызова (GC и Full GC), общее время которых не привышает 8мс, что уже намного лучше.

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

                            Во-первых, компиляция на ходу приводит к ощутимым задержкам, поэтому не во всех случаях удобна.

                            Во-вторых, построение кода на Expression'ах — это тоже нехилые простыни, которые в подходе write-only составят достойную конкуренцию коду на шаблонах из соседнего топика.

                            Я бы трижды подумал, прежде чем внедрять в реальный проект такое шаманство.
                              0
                              А почему сразу на Expression'ах? Я обычно Reflection.Emit использую...

                              По поводу задержек — они все равно окупаются дальнейшим ускорением, особенно на больших наборах данных.
                                0
                                Код с Emit ещё более нечитаемый…
                                  0
                                  Спасибо, я и сам заметил
                                0
                                Во-первых, компиляция на ходу приводит к ощутимым задержкам, поэтому не во всех случаях удобна.


                                В случае автора все фильтры генерируются заранее. Здесь тоже можно сделать во время инициализации программы или ленивым образом, так что это операция которая выполняется один раз.

                                Во-вторых, построение кода на Expression'ах — это тоже нехилые простыни, которые в подходе write-only составят достойную конкуренцию коду на шаблонах из соседнего топика.


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

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


                                Это вещь которая применяется в разовых случаях, это понятно. Равно как и подобные извращения с шаблонами.
                                +2
                                Ради справедливости стоит также отметить, что преимущества в производительности C# могут достигаться за счет менеджера памяти. C# может легко перемещать блоки памяти, снижая фрагментацию. С++ после активной работы с памятью будет сидеть с фрагментированной кучей…
                                  +2
                                  Если быть совсем уж справедливыми, то стоит отметить, что из-за оверхеда связанного с о сборщиком мусора и другими особенностями виртуальной машины лично у меня никогда не получалось достичь лучших относительно нативного кода производительности.
                                    +2
                                    Шарп даёт преимущества в производительности кода, который написан относительно быстро. Если писать долго, с использованием ручных менеджеров памяти, с углублением в ассемблер, со всеми мыслимыми и немыслимыми оптимизациями — шарп конкурировать с плюсами не может.
                                    0
                                    Виртуальная память жеж давно.
                                      +2
                                      А что, если виртуальная, то фрагментация ей не страшна, что ли?
                                        0
                                        C# может легко перемещать блоки памяти, снижая фрагментацию. С++ после активной работы с памятью будет сидеть с фрагментированной кучей…


                                        Это же умеет делать ОС на уровне виртуальной памяти. В крайнем случае можно использовать какой-нибудь nedmalloc c пулингом.
                                          +3
                                          Не умеет. Если память выделена, то ее перемещать нельзя, т.к. приложение ее использует и перемещение привдет к ошибке. Менеджер памяти .NET может свободно перемещать любые куски памяти, т.к. с указателями код напрямую не работает.
                                            +1
                                            Выделять память из кучи и потом ее возвращать, вообще-то не очень хорошее решение. Если что-то подобное требуется, то используются пулы или циклический буфер.
                                  +16
                                  Тот момент, когда код на асме понятнее, чем шаманства с шаблонами...)
                                    0
                                    извините, что не совсем по теме статьи, но мне стало любопытно, а есть ли практический смысл в конструкциях const*const? я знаю, что оно обозначает, но на практике больше одного const-модификатора в типе не видел.
                                      +3
                                      IMHO, смысл есть — более сильная константность (транзитивная в случае const *const — измениться не может ни значение (в случае отсутствие последующей индирекции), ни указатель на него) дает компилятору больше потенциальных возможностей оптимизировать этот код.

                                      И я, например, всегда стараюсь использовать модификатор const, и не использую его лишь в редких случаях.
                                        0
                                        Полностью согласен. Хочу добавить, что const*const можно полностью выносить в заголовочные файлы, в отличие от const*. Это удобно, так как все константы, включая строковые, могут быть объявлены и определены в одном месте.
                                      0
                                      Но Google C++ Style Guide рекомендует передавать неизменяемые параметры по константной ссылке const&, а изменяемые по константному указателю *const

                                      Я, наверное, что-то путаю, но в Google C++ Style Guide говорится о const T*, а не о T* const ??
                                        0
                                        Скорее всего да, ибо const T * — указатель на константный объект типа Т, а T * const — константный указатель на изменяемый объект.

                                        пруф линк для сомневающихся
                                          0
                                          об этом я и говорю — автор что-то напутал немножко.
                                            +1
                                            Нет, напутали вы.
                                              0
                                              В Google C++ Style Guide идёт речь об const T*, тогда как в статье говорится о том, что Google C++ Style Guide рекомендует «константный указатель *const», т.е. T* const, что не одно и тоже. Смысл говорить об одном и давать ссылку на немножко другое? Ладно, не столь важно, статья не об этом.
                                                0
                                                Ну как вы передадите изменяемый параметр по const T*? Другое дело, что в Google C++ Style Guide я вообще не нашел раздела про указатели.

                                                Так что можно сказать, что автор немного ошибся — Google C++ Style Guide не отдает предпочтения ни одному варианту из T* или T* const
                                                  0
                                                  имеенно об этом я и говорю — ничего о T* const Google C++ Style Guide не говорит.

                                                  И я ничего не говорил о передаче изменяемого параметра как const T* — имелось в виду, что Google C++ Style Guide если уж и что-то говорит о передаче параметров — то только о const T*, а не о T* const (или const T* const).
                                                  Меня просто не поняли, глупо получилось.
                                                    0
                                                    Google рекомендует при любой возможности использовать const, если нет необходимости в обратном. Если нет необходимости в адресной арифметике, то для изменяемых параметров он отдает предпочтение: T *const.
                                                      0
                                                      А почему нельзя передать по ссылке?
                                                        0
                                                        All parameters passed by reference must be labeled const.
                                                        Через T const& нельзя менять значение.
                                                          0
                                                          Потому что при использовании ссылок неочевидно, может функция менять аргумент или нет.
                                                            0
                                                            Если ссылка константная, то не может, и наоборот, очевидно же.
                                                              0
                                                              Вот вам кусок кода:
                                                              int x = 5;
                                                              foo(x);
                                                              cout << x;
                                                              
                                                              Назовите-ка, что он выведет, не глядя на объявление foo, скрытое черт знает в каком заголовочном файле?

                                                              Если следовать рекомендациям Google, то программа может вывести только 5 и ничего другого.
                                                                0
                                                                Заменю на const int x = 5;, а вообще пример из пальца высосан. Я также могу сказать вам, что передача указателя на int вызовет у меня больше сомнений, ибо чё там дальше с указателем делается, я тоже не знаю.
                                                                  0
                                                                  В виде бонуса ссылка позволяет отловить ошибки, гарантируя передачу рельного объекта. Если вы, конечно, не сделаете foo(*ptr), такой код заслуживет отдельных лучей поноса.
                                                                    0
                                                                    Зато если кто-то сделает foo(*ptr), то поставить проверку на нулевой указатель уже не получится.
                                              +6
                                              Неоднократно замечал, что при проэктировинии баз данных поле «пол» делают булевым. При чем «true» означает мужской пол, а «false» — женский.
                                              bash.im/quote/396500

                                              unsigned gender:1;

                                              В данном случае, видимо, 1 означает мужской пол, а 0 — женский, т. к. цифры 0 и 1 похожи на… Ладно, не буду продолжать.
                                                +1
                                                Помимо этого, даже, существуют статьи показывающие преимущества в скорости языков с компиляцией налету (JIT — Just-in-time compilation), таких как Java и C#. Сравнить последние мы оставим тем, кто считает их быстрыми, но мы объясним почему это не так
                                                Небольшой пример, использующий динамическую генерацию кода и JIT: Ищем на java, оптимизация во время исполнения. За счет генераци «плана исполнения запроса» на лету и JIT, скорость получилась сравнимая со статической оптимизацией.
                                                –1
                                                Но в C, где нет ссылок, такой подход не возможен, т.к. если функция всегда принимает только по указателю, то на стороне вызывающего нельзя гарантировать невозможность их модификации

                                                Почему это? Можно написать так:
                                                void func(int const *a, int *b) {}

                                                Вы, конечно, можете возразить, что a здесь можно поменять при помощи
                                                *(int *)a = 0

                                                Но тогда и в вашем решении с int const& a переменную a тоже можно поменять с помощью
                                                (int&)a = 0

                                                Естественно, я не хочу сказать, что int const *a лучше
                                                  +1
                                                  Выше уже 100 раз обсудили.
                                                  на стороне вызывающего нельзя гарантировать невозможность их модификации

                                                  Приведите мне код вызывающий функцию в Google C++ Style, и я вам только по этому вызову на 100% скажу, какие переменные могут быть изменены, а какие нет.
                                                  Если бы вы писали код в Google C++ Style, то функция выглядела бы так:
                                                  void func(int const& a, int *b) {}
                                                  

                                                  А код вызова так:
                                                  int a, b; func(a, &b);
                                                  

                                                  Откуда очевидно, что a — не меняется, b — меняется.

                                                  В C такое не получиться.
                                                  Код вызова вашей функции:
                                                  int a, b; func(&a, &b);
                                                  

                                                  Это крайне важно, когда вы не хотите, чтобы ваша переменная менялась при использовании чужой функции, которую её автор может поменять, а падать будет у вас.
                                                –2
                                                C++ не быстрее C. Всё, что можно сделать в C++, можно и в C. Возможно, не так красиво, но можно. В данном случае, решение на C, возможно, было бы красивее, чем эти выкрутасы с шаблонами. И никаких «C-разработчикам придется вручную создать эти 32 функции». Можно просто сделать как-то на макросах C. Например (для примера рассмотрены только три поля):

                                                /* Compare row with filters */
                                                #define DECLARE(use_amount_of_money, use_gender, use_age) \
                                                static inline unsigned char test_predicate_ ## use_amount_of_money ## _ ## use_gender ## _ ## use_age(struct T_cash_account_row const*const row, \
                                                    struct T_range_filters const*const range_filters) \
                                                {    \
                                                    return \
                                                        (!use_amount_of_money || \
                                                            (row->amount_of_money >= range_filters->begin.amount_of_money && \
                                                            row->amount_of_money <= range_filters->end.amount_of_money)) && \
                                                        (!use_gender || \
                                                            (row->gender >= range_filters->begin.gender && \
                                                            row->gender <= range_filters->end.gender)) && \
                                                        (!use_age || \
                                                            (row->age >= range_filters->begin.age && \
                                                            row->age <= range_filters->end.age)); \
                                                }
                                                
                                                #define DECL2(m, g) DECLARE(m, g, 0) DECLARE(m, g, 1)
                                                #define DECL1(m) DECL2(m, 0) DECL2(m, 1)
                                                
                                                DECL1(0)
                                                DECL1(1)
                                                


                                                Обратите внимание, что здесь use_amount_of_money — это выражение времени компиляции, и на этапе препроцессинга оно превратится в 0 или 1. Поэтому в (!use_amount_of_money || ...) компилятор выкинет этот use_amount_of_money. Поэтому скорость будет такая же, как и в вашем решении на шаблонах C++. Тестировать не буду — не хочу. Сами тестируйте, если хотите. Скорость будет такая же, так как суть одна. Просто то, что можно было сделать на шаблонах, сделано на макросах. Можно ещё попробовать просто сгенерировать C-код скриптом.
                                                  +2
                                                  Можно сделать, но на макросах никогда не было красивее. И на макросах всегда в разы хуже с поддержкой кода. Почти никто не захочет тестировать ваш код на макросах и использовать в production. В макросах почти ничего не контролируется, ни тело, ни входные параметры. Словив ошибку при разработке или при слияниях веток в Git/Mercurial, вам придется часами гадать на хрустальном шаре. Содержательность сообщений компилятора при ошибках в макросах на порядок ниже, чем при ошибках в шаблонах. На ошибку в любой строке тела макросах компилятор всегда выдаст ошибку в одной и той же строке — в месте использования макроса. По этому и придумали шаблоны, со строгим синтаксисом и содержательными сообщениями компилятора.
                                                  Тот же Google C++ Style, предпочитает макросам даже Prefer inline functions, enums, and const variables to macros. А использовать их вместо шаблонов — это вообще за гранью адекватности.
                                                    –1
                                                    Содержательность сообщений компилятора при ошибках в макросах на порядок ниже, чем при ошибках в шаблонах

                                                    pascalg.wordpress.com/2008/02/24/stl-error-messages-are-so-great :)
                                                      0
                                                      Всё там понятно.
                                                      note: candidates are: typename std::vector<_Tp, _Alloc>::iterator
                                                      Прямо написано, что передавать надо итератор, а не значение.
                                                      А затем приведены две сигнатуры функции insert().
                                                        0
                                                        Да, эти сообщения слишком подробные. Но слишком подробное сообщение все равно лучше, чем ничего не содержащее.
                                                    +4
                                                    По поводу 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. И вообще, все тесты я проводил по одному разу. Так что можете всё перетестить и получить более точные результаты.

                                                    И хватит всем говорить «Приведите пример и результаты тестов». У человека может быть время написать коммент, но не быть времени для написания примера.
                                                      +1
                                                      Молодец, что нашли время не только писать комментарии, но и сделать что-то работающее :)
                                                      Но надеюсь вы понимаете, что:
                                                      1. Поддерживать такой код тоже очень «удобно», не знаю даже лучше или хуже, чем с макросами. Для ошибок кода из строковых переменных вы получаете в пост-процессинговом исходнике при второй компиляции, а править их надо в первоначальном исходнике.
                                                      2. И первая, и вторая статьи — это лишь одна из оптимизаций, которая применяется после сужения индексного поиска за счет IOT/IOS до 50 — 1000 элементов, и выполняется этот алгоритм за 1мкс — 20мкс, примерно до 10^6 запросов в секунду на одно ядро. Тут уж не по компилируешь каждый раз.
                                                      Будет свободное время — напишу третью статью, где это покажу.
                                                        +2
                                                        А знаете что? Ваш пример показывает, что, оказывается, всё-таки имеет смысл делать self-modifying machine code. Вот смотрите:

                                                        Решение на шаблонах
                                                        • Плюс: не надо компилировать в рантайме
                                                        • Минус: медленнее, чем JIT


                                                        Решение на JIT (ну или псевдо-JIT, сейчас это не важно)
                                                        • Плюс: быстрее, чем на шаблонах
                                                        • Минус: надо делать JIT в рантайме


                                                        А теперь посмотрим на self-modifying code: просто нужно на этапе компиляции скомпилировать, скажем, 32 варианта функции test_predicate, потом в рантайме выбрать нужный из этих вариантов, а потом записать прямо в (уже скомпилированный) машинный код значения begin и end и передать управление этому модифицированному коду. (Если непонятно, могу подробнее объяснить.)

                                                        В результате получаем такую же скорость, как и в решении с JIT'ом, т. к. переменные begin и end будут с точки зрения самой функции test_predicate константами. Но при этом не надо делать JIT. Достаточно лишь поменять машинный код во время исполнения, а это занимает лишь единицы тактов процессора, в отличие от JIT.

                                                        Непонятно только, как это реализовать на практике. Ведь, как я понимаю, во всех нормальных ОС текущий выполняемый код защищён от записи. Собственно, этот пример показывает, что такую защиту иногда бывает нужно снимать.

                                                        Да, теперь я понимаю, что self-modifying code — это не пережиток времён DOS. Он реально бывает нужен.
                                                          0
                                                          Как мне кажется, в случае константных begin и end компилятор оптимизирует код под эти константы, и просто так заменить их в получившемся машинном коде не получится.

                                                          А по поводу защиты от записи — тут все просто. Например, в Windows достаточно вызвать функцию VirtualProtect.
                                                            0
                                                            Как мне кажется, в случае константных begin и end компилятор оптимизирует код под эти константы, и просто так заменить их в получившемся машинном коде не получится.


                                                            Всё равно можно что-то придумать. Можно подобную оптимизацию в рантайме замутить. Но, опять-таки, не полноценный JIT, а именно немножко манипуляций байтами, чтоб укладывалось в маленькое число тактов.

                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                    Самое читаемое