fork download
copy 
  1. #include <stdio.h>      /* printf, scanf, NULL */
  2. #include <stdlib.h>     /* calloc, exit, free */
  3. #include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */
  4.  
  5. #include <memory>    	// std::unique_ptr<>
  6. #include <array>		// std::array<>
  7. #include <vector>
  8. #include <type_traits>	// std::enable_if<>
  9. #include <algorithm>
  10.  
  11. #include <iostream>		// std::cout
  12. #include <map>			// std::map<>
  13.  
  14. const size_t c_array_size = 10000000;
  15.  
  16. /* Row */
  17. struct T_cash_account_row {
  18.  
  19. 	// Fields:
  20. 	enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e,   /*<<<<<- add fields here (with index) */
  21. 		last_e
  22.         /*<<<<<- add included fields here (without index) */
  23. 	};
  24. 	static_assert(last_e > 0, "Number of indexed fields in enum of T_user_row must be greater than 0!");
  25.  
  26. //    int32_t code;			// 0 - 1000000
  27. //    int32_t amount_of_money;// 0 - 1000000
  28. //    int16_t height;       // 0 - 300
  29. //    int16_t age:7;		// 0 - 100
  30. //    int16_t gender:1;		// 0 - 1
  31.  
  32.     unsigned code:20;			// 0 - 1000000
  33. 	unsigned gender:1;			// 0 - 1
  34. 	unsigned age:7;			    // 0 - 100
  35. 	unsigned amount_of_money:20;// 0 - 1000000
  36. 	unsigned height:9;			// 0 – 300
  37.  
  38. 	// Get field value
  39. 	template<int field_enum> inline typename std::enable_if<field_enum == code_e, decltype(code)>::type		get_field_value() const { return code; }
  40. 	template<int field_enum> inline typename std::enable_if<field_enum == gender_e, decltype(gender)>::type get_field_value() const { return gender; }
  41. 	template<int field_enum> inline typename std::enable_if<field_enum == age_e, decltype(age)>::type		get_field_value() const { return age; }
  42. 	template<int field_enum> inline typename std::enable_if<field_enum == amount_of_money_e, decltype(amount_of_money)>::type get_field_value() const { return amount_of_money; }
  43. 	template<int field_enum> inline typename std::enable_if<field_enum == height_e, decltype(height)>::type get_field_value() const { return height; }
  44.  
  45. 	template<int field_enum> inline typename std::enable_if<field_enum == last_e, bool>::type get_field_value() const { return true; }
  46. 	static_assert(5 == last_e, "Add/delete new field-case and correct this assert!");
  47.  
  48. 	// Get cardinality
  49. 	template<int field_enum>
  50. 	// constexpr // not supported in the MSVS2012(MVCC11)
  51. 	static inline const unsigned int get_bitf_size() {
  52. 		return (field_enum == gender_e)?1:
  53.         (field_enum == age_e)?		100:
  54.         (field_enum == height_e)?	300:
  55.         (field_enum == code_e)?		1000000:
  56.         (field_enum == amount_of_money_e)?1000000:
  57.         0;
  58. 		static_assert(5 == last_e, "Add/delete new field-case and correct this assert!");
  59. 	}
  60.  
  61. };
  62. /* ----------------------------------------------------------------------- */
  63.  
  64. /* Generate random data for the one row */
  65. static inline struct T_cash_account_row generate_row() {
  66. 	struct T_cash_account_row cash_account_row;
  67. 	cash_account_row.age = rand() % 100;
  68. 	cash_account_row.amount_of_money = (rand() % 1000)*(rand() % 1000);
  69. 	cash_account_row.code = (rand() % 1000)*(rand() % 1000);
  70. 	cash_account_row.gender = rand() % 2;
  71. 	cash_account_row.height = rand() % 300;
  72. 	return cash_account_row;
  73. }
  74. /* ----------------------------------------------------------------------- */
  75.  
  76. /* C-style filters */
  77. struct T_range_filters {
  78.     struct T_cash_account_row begin, end;
  79.     /* bytes array or bitset from https://g...content-available-to-author-only...b.com/jmbr/667605 */
  80. 	unsigned char use_filter[T_cash_account_row::last_e];
  81. };
  82. /* ----------------------------------------------------------------------- */
  83.  
  84. // Templated constructor of class unrolling (no return, mandatory call to the constructor, called once)
  85. template<unsigned unroll_count, template<unsigned> class T>
  86. struct T_unroll_constructor {
  87. 	T_unroll_constructor<unroll_count-1, T> next_unroll;
  88. 	T<unroll_count-1> functor;
  89. 	template<typename T1> inline T_unroll_constructor(T1 &val1) : next_unroll(val1), functor(val1) {}
  90. 	template<typename T1, typename T2> inline T_unroll_constructor(T1 *const __restrict val1, T2 *const __restrict val2) : next_unroll(val1, val2), functor(val1, val2) {}
  91. };
  92. // End of unroll
  93. template<template<unsigned> class T>
  94. struct T_unroll_constructor<0, T> {
  95. 	template<typename T1> inline T_unroll_constructor(T1 &) {}
  96. 	template<typename T1, typename T2> inline T_unroll_constructor(T1 *const __restrict, T2 *const __restrict) {}
  97. };
  98. // -------------------------------------------------------------------------
  99.  
  100. // Templated functor unrolling (reusable)
  101. template<unsigned unroll_count, template<unsigned> class T>
  102. struct T_unroll_functor {
  103. 	T_unroll_functor<unroll_count-1, T> next_unroll;
  104. 	T<unroll_count-1> functor;
  105. 	template<typename T1, typename T2> inline bool operator()(T1 const& val1, T2 const& val2) {
  106. 		return next_unroll(val1, val2) && functor(val1, val2);
  107. 	}
  108. };
  109. // End of unroll
  110. template<template<unsigned> class T>
  111. struct T_unroll_functor<0, T> {
  112. 	template<typename T1, typename T2> inline bool operator()(T1 const&, T2 const&) { return true; }
  113. };
  114. // -------------------------------------------------------------------------
  115.  
  116. // Abstract base class of filters for each search variant (range_filters)
  117. template<typename T_row>
  118. struct T_filter {
  119. 	// whether to use the filter for a given predicate? (strictly at compile time)
  120. 	template <unsigned index_pred, unsigned number_filter>
  121. 	struct T_get_use_filter : std::integral_constant<bool, !(index_pred & 1<<number_filter)> {};
  122.  
  123. 	// Get index of T_test_pred version for current search range
  124. 	static inline const unsigned get_index_pred(T_range_filters const*const __restrict range_filters) {
  125. 		unsigned result = 0;
  126. 		for(size_t i = 0; i < T_row::last_e; ++i) result |= range_filters->use_filter[i]?(1<<i):0;
  127. 		return result;
  128. 	}
  129. 	// -------------------------------------------------------------------------
  130.  
  131. 	// The unrolling filling of selectivity in a compile-time
  132. 	template<unsigned field_num>
  133. 	struct T_selectivity_fill {
  134. 		T_selectivity_fill(std::map<unsigned, unsigned> *const __restrict ordered_filters, T_range_filters const*const __restrict range_filters) {
  135. 			const auto begin = range_filters->begin.template get_field_value<field_num>(), end = range_filters->end.template get_field_value<field_num>();
  136. 			const auto delta = (begin > end)?0:(1 + end - begin);
  137. 			const unsigned selectivity = range_filters->use_filter[field_num]?
  138.             (delta*c_array_size /
  139.              T_row::template get_bitf_size<field_num>() // cardinality
  140.              )
  141.             :c_array_size;
  142. 			ordered_filters->insert(std::make_pair(field_num, selectivity));		// selectivity for each field-filter
  143. 		}
  144. 	};
  145.  
  146. 	// Get index of T_test_pred version for current search range
  147. 	static inline const unsigned get_index_order(T_range_filters const*const __restrict range_filters) {
  148. 		unsigned result = 0;
  149.  
  150. 		std::map<unsigned, unsigned> ordered_filters;
  151. 		T_unroll_constructor<T_row::last_e, T_selectivity_fill> selectivity_fill(&ordered_filters, range_filters);
  152.  
  153. 		unsigned multiplexor = 1;
  154. 		for(size_t i = 0; i < T_row::last_e; ++i) {
  155. 			unsigned cur_index = 0, min_index = 0;
  156. 			unsigned field_num = ordered_filters.cbegin()->first, min = c_array_size;
  157. 			for(auto const& it : ordered_filters) {
  158. 				if (it.second < min) min = it.second, field_num = it.first, min_index = cur_index;
  159. 				++cur_index;
  160. 			}
  161. 			ordered_filters.erase(field_num);
  162. 			result += min_index*multiplexor;
  163. 			multiplexor *= (T_row::last_e - i);
  164. 		}
  165. 		return result;
  166. 	}
  167. 	// -------------------------------------------------------------------------
  168. 	// Brute force permutations fields at compile-time
  169.  
  170. 	// Get the sequence number the remaining field for the number_filter, after removal of all previous
  171. 	template <unsigned index_order, unsigned number_filter, unsigned index = T_row::last_e>
  172. 	struct T_number_remaining_field : std::integral_constant<unsigned, T_number_remaining_field<index_order / index, number_filter - 1, index - 1>::value> {};
  173.  
  174. 	// End of unroll
  175. 	template <unsigned index_order, unsigned index>
  176. 	struct T_number_remaining_field<index_order, 0, index> : std::integral_constant<unsigned, index_order % index> {};
  177. 	// -------------------------------------------------------------------------
  178.  
  179. 	// Get 1 or 0 offset if current_field (for number_filter) affect to number_field
  180. 	template <unsigned index_order, unsigned number_filter, unsigned number_field>
  181. 	struct T_offset {
  182. 		enum { current_field = T_number_remaining_field<index_order, number_filter>::value,
  183. 			value = (current_field <= number_field)?1:0 };
  184. 	};
  185.  
  186. 	// Get offset of number_field (enum in row-type) for number_filter
  187. 	template <unsigned index_order, unsigned number_filter, unsigned number_field>
  188. 	struct T_offset_number_field {
  189. 		enum { offset = T_offset<index_order, number_filter-1, number_field>::value,
  190. 			value = T_offset_number_field<index_order, number_filter-1, number_field + offset>::value + offset };
  191. 	};
  192.  
  193. 	// End of unroll
  194. 	template <unsigned index_order, unsigned number_field>
  195. 	struct T_offset_number_field<index_order, 0, number_field> : std::integral_constant<unsigned, 0> {};
  196.  
  197. 	// (Main) Get number of field (enum in row-type) for number_filter
  198. 	template <unsigned index_order, unsigned number_filter>
  199. 	struct T_number_field {
  200. 		enum { remaining_field = T_number_remaining_field<index_order, number_filter>::value,
  201. 			value = remaining_field + T_offset_number_field<index_order, number_filter, remaining_field>::value };
  202. 	};
  203. 	// -------------------------------------------------------------------------
  204.  
  205. 	// search
  206. 	virtual size_t search(T_row const*const __restrict array_ptr, const size_t c_array_size,
  207.                           T_row *const __restrict result_ptr, T_range_filters const*const __restrict filters) = 0;
  208. };
  209. // -------------------------------------------------------------------------
  210.  
  211. // The filters for each search variant (range_filters)
  212. template<typename T_row, unsigned index_pred, unsigned index_order = 0>
  213. struct T_custom_filter : T_filter<T_row> {
  214.  
  215. 	// Test predicates functor for unrolling
  216. 	template<unsigned field_num>
  217. 	struct T_test_pred {
  218. 		bool inline operator()(T_row const*const __restrict row, T_range_filters const*const __restrict range_filters) const
  219. 		{
  220. 			typedef typename T_row::T_field_enum T_field_enum;
  221. 			// Without fields where use_filter==0
  222. 			enum { ordered_field_number = T_filter<T_row>::template T_number_field<index_order, field_num>::value };
  223. 			return ( T_filter<T_row>::template T_get_use_filter<index_pred, ordered_field_number>::value ||
  224.                     (row->template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() >=
  225.                      range_filters->begin.template get_field_value<static_cast<T_field_enum>(ordered_field_number)>()	&&
  226.                      row->template get_field_value<static_cast<T_field_enum>(ordered_field_number)>() <=
  227.                      range_filters->end.template get_field_value<static_cast<T_field_enum>(ordered_field_number)>()) );
  228. 		}
  229. 	};
  230. 	// -----------------------------------------------------------------------
  231.  
  232. 	// search
  233. 	virtual size_t search(T_row const*const __restrict array_ptr, const size_t c_array_size,
  234.                           T_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) final
  235. 	{
  236. 		size_t result_size = 0;
  237. 		size_t i; // loop index
  238. 		T_unroll_functor<T_row::last_e, T_test_pred> test_predicate;
  239. 		for(i = 0; i < c_array_size; ++i) {
  240. 			if(test_predicate(array_ptr + i, range_filters))
  241. 				result_ptr[result_size] = array_ptr[i], ++result_size;
  242. 		}
  243. 		return result_size;
  244. 	}
  245. };
  246. // -------------------------------------------------------------------------
  247.  
  248. template <unsigned N> struct factorial : std::integral_constant<unsigned, N * factorial<N-1>::value> {};
  249. template <> struct factorial<0> : std::integral_constant<unsigned, 1> {};
  250.  
  251. template<typename T_row>
  252. class T_optimized_search {
  253. 	// unroll tamplates
  254. 	template<unsigned index_pred>
  255. 	struct T_unroll_find {
  256. 		template<unsigned index_order>
  257. 		struct T_unroll_order {
  258. 			template<typename T> T_unroll_order(T &filters) {
  259. 				filters[index_pred + index_order*(1<<T_row::last_e)].reset( new T_custom_filter<T_row, index_pred, index_order>() );
  260. 			}
  261. 		};
  262. 		T_unroll_constructor<factorial<T_row::last_e>::value, T_unroll_order> fill_ordered_filter;
  263.  
  264. 		template<typename T> T_unroll_find(T &filters) : fill_ordered_filter(filters)
  265. 		{
  266. 		}
  267. 	};
  268. 	// -------------------------------------------------------------------------
  269.  
  270. 	std::array<std::unique_ptr<T_filter<T_row>>, (1<<T_row::last_e)*factorial<T_row::last_e>::value> filters;
  271. 	T_unroll_constructor< 1<<T_row::last_e, T_unroll_find> fill_filter;
  272. public:
  273. 	T_optimized_search() : fill_filter(filters) {}
  274.  
  275. 	// C++ optimized search
  276. 	inline size_t search(T_row const*const __restrict array_ptr, const size_t c_array_size,
  277.                          T_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters)
  278. 	{
  279. 		auto const& filter = filters[T_filter<T_row>::get_index_pred(range_filters) + T_filter<T_row>::get_index_order(range_filters)*(1<<T_row::last_e)];
  280. 		return filter->search(array_ptr, c_array_size, result_ptr, range_filters);
  281. 	}
  282.     };
  283.     // -------------------------------------------------------------------------
  284.  
  285.     /* Compare row with filters */
  286.     static inline unsigned char test_predicate(struct T_cash_account_row const*const __restrict row,
  287.                                                struct T_range_filters const*const __restrict range_filters)
  288.     {
  289.         return
  290.         (!range_filters->use_filter[T_cash_account_row::amount_of_money_e] ||
  291.          (row->amount_of_money >= range_filters->begin.amount_of_money &&
  292.           row->amount_of_money <= range_filters->end.amount_of_money)) &&
  293.         (!range_filters->use_filter[T_cash_account_row::gender_e] ||
  294.          (row->gender >= range_filters->begin.gender && row->gender <= range_filters->end.gender)) &&
  295.         (!range_filters->use_filter[T_cash_account_row::age_e] ||
  296.          (row->age >= range_filters->begin.age && row->age <= range_filters->end.age)) &&
  297.         (!range_filters->use_filter[T_cash_account_row::code_e] ||
  298.          (row->code >= range_filters->begin.code && row->code <= range_filters->end.code)) &&
  299.         (!range_filters->use_filter[T_cash_account_row::height_e] ||
  300.          (row->height >= range_filters->begin.height && row->height <= range_filters->end.height));
  301.     }
  302.     /* ----------------------------------------------------------------------- */
  303.  
  304.     /* search */
  305.     static inline size_t search(struct T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,
  306.                                 struct T_cash_account_row *const __restrict result_ptr, struct T_range_filters const*const __restrict range_filters)
  307.     {
  308.         size_t result_size = 0;
  309.         size_t i; /* loop index */
  310.         for(i = 0; i < c_array_size; ++i) {
  311.             if(test_predicate(array_ptr + i, range_filters))
  312.                 result_ptr[result_size] = array_ptr[i], ++result_size;
  313.         }
  314.         return result_size;
  315.     }
  316.     /* ----------------------------------------------------------------------- */
  317.  
  318. struct Row {
  319.     int32_t code;			// 0 - 1000000
  320.     int32_t amountOfMoney;// 0 - 1000000
  321.     int16_t height;       // 0 - 300
  322.     int16_t age:7;		// 0 - 100
  323.     int16_t gender:1;		// 0 - 1
  324.  
  325.     Row() : code(0), amountOfMoney(0), height(0), age(0), gender(0) {};
  326.  
  327.     Row(int32_t code_, int32_t money, int16_t height_, int16_t age_, int16_t gender_)
  328.     : code(code_), amountOfMoney(money), height(height_), age(age_), gender(gender_){}
  329. };
  330.  
  331. int main() {
  332.  
  333.     std::cout << "C++: " << sizeof(Row) << " | C: " << sizeof(T_cash_account_row) << std::endl;
  334.  
  335.     size_t i; /* loop index */
  336.     struct T_cash_account_row *const array_ptr = ( struct T_cash_account_row *)calloc(c_array_size, sizeof(struct T_cash_account_row));
  337.     if (array_ptr == NULL) {
  338.         printf ("calloc error\n");
  339.         exit(1);
  340.     }
  341.  
  342.     /* initialize random seed: */
  343.     /* srand (time(NULL)); */
  344.  
  345.     /* Fill table random data */
  346.     for(i = 0; i < c_array_size; ++i)
  347.         array_ptr[i] = generate_row();
  348.     printf ("Generated rows: %zd \n", c_array_size);
  349.  
  350.     /* C-style range filters */
  351.     struct T_range_filters range_filters = {};
  352.  
  353.     range_filters.use_filter[T_cash_account_row::amount_of_money_e] = rand()%1 + 0;
  354.     range_filters.use_filter[T_cash_account_row::gender_e] = rand()%1 + 0;
  355.     range_filters.use_filter[T_cash_account_row::height_e] = rand()%1 + 0;
  356.  
  357.     range_filters.begin.age = rand() % 100;
  358.     range_filters.end.age = range_filters.begin.age + 5;
  359.     range_filters.use_filter[T_cash_account_row::age_e] = rand()%1 + 1;
  360.  
  361.     range_filters.begin.code = rand() % 30000;
  362.     range_filters.end.code = range_filters.begin.code + 5;
  363.     range_filters.use_filter[T_cash_account_row::code_e] = rand()%1 + 1;
  364.  
  365.     size_t result_size;
  366.     clock_t end, start;
  367.  
  368.     double cpp_took_time;
  369.     double c_took_time;
  370.  
  371.     {
  372.         struct T_cash_account_row *const result_ptr = ( struct T_cash_account_row *)calloc(c_array_size, sizeof(struct T_cash_account_row));
  373.         start = clock();
  374.         result_size = search(array_ptr, c_array_size, result_ptr, &range_filters);
  375.         end = clock();
  376.         c_took_time = static_cast<double>(end - start);
  377.         printf ("C search took %f seconds.\n", c_took_time/CLOCKS_PER_SEC);
  378.         printf ("Found rows: %zd \n", result_size);
  379.  
  380.         free(result_ptr);
  381.     }
  382.  
  383.     {
  384.         std::vector<Row> rows(c_array_size);
  385.         for(size_t i = 0; i < c_array_size; ++i)
  386.         {
  387.             T_cash_account_row r = array_ptr[i];
  388.             rows[i] = Row(r.code, r.amount_of_money, r.height, r.age, r.gender);
  389.         }
  390.         free(array_ptr);
  391.  
  392.         std::vector<Row> output;
  393.         output.reserve(32);
  394.  
  395.         auto filter = [&](const Row& row)
  396.         {
  397.             return
  398.             (!range_filters.use_filter[T_cash_account_row::amount_of_money_e] ||
  399.              (row.amountOfMoney >= range_filters.begin.amount_of_money &&
  400.               row.amountOfMoney <= range_filters.end.amount_of_money)) &&
  401.             (!range_filters.use_filter[T_cash_account_row::gender_e] ||
  402.              (row.gender >= range_filters.begin.gender && row.gender <= range_filters.end.gender)) &&
  403.             (!range_filters.use_filter[T_cash_account_row::age_e] ||
  404.              (row.age >= range_filters.begin.age && row.age <= range_filters.end.age)) &&
  405.             (!range_filters.use_filter[T_cash_account_row::code_e] ||
  406.              (row.code >= range_filters.begin.code && row.code <= range_filters.end.code)) &&
  407.             (!range_filters.use_filter[T_cash_account_row::height_e] ||
  408.              (row.height >= range_filters.begin.height && row.height <= range_filters.end.height));
  409.         };
  410.  
  411.         start = clock();
  412.         std::copy_if(rows.begin(), rows.end(), std::back_inserter(output), filter);
  413.         end = clock();
  414.         cpp_took_time = static_cast<double>(end - start);
  415.         printf ("C++ search took %f seconds.\n", cpp_took_time/CLOCKS_PER_SEC);
  416.         printf ("Found rows: %ld \n", output.size());
  417.     }
  418.  
  419.     printf ("The C++ faster than C: %f times \n", c_took_time/cpp_took_time);
  420.  
  421.     return 0;
  422. }
Success #stdin #stdout 2.28s 3032KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
C++: 12 | C: 8
Generated rows: 10000000 
C search took 0.050000 seconds.
Found rows: 38 
C++ search took 0.080000 seconds.
Found rows: 38 
The C++ faster than C: 0.625000 times
https://ideone.com/dSsmya
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!