fork(1) download 
  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.  
  8. const size_t c_array_size = 10000000;
  9.  
  10. /* Fields */
  11. enum T_field_enum { amount_of_money_e, gender_e, age_e, code_e, height_e,   /*<<<<<- add fields here */	last_e };
  12.  
  13. /* Row */
  14. struct T_cash_account_row {
  15.     unsigned code:20;			// 0 - 1000000
  16. 	unsigned gender:1;			// 0 - 1
  17. 	unsigned age:7;			    // 0 - 100	
  18. 	unsigned amount_of_money:20;// 0 - 1000000
  19. 	unsigned height:9;			// 0 – 300
  20. };
  21. /* ----------------------------------------------------------------------- */
  22.  
  23. /* Generate random data for the one row */
  24. static inline struct T_cash_account_row generate_row() {
  25. 	struct T_cash_account_row cash_account_row;
  26. 	cash_account_row.age = rand() % 100;
  27. 	cash_account_row.amount_of_money = (rand() % 1000)*(rand() % 1000);
  28. 	cash_account_row.code = (rand() % 1000)*(rand() % 1000);
  29. 	cash_account_row.gender = rand() % 2;
  30. 	cash_account_row.height = rand() % 300;
  31. 	return cash_account_row;
  32. }
  33. /* ----------------------------------------------------------------------- */
  34.  
  35. /* Filters */
  36. struct T_range_filters {
  37.     struct T_cash_account_row begin, end;
  38.     /* bytes array or bitset from https://g...content-available-to-author-only...b.com/jmbr/667605 */
  39. 	unsigned char use_filter[last_e]; 
  40. };
  41. // -------------------------------------------------------------------------
  42.  
  43. // The templated constructor of unrolling of the class (no return, mandatory call to the constructor, called once)
  44. template<unsigned unroll_count, template<unsigned> class T>
  45. struct T_unroll_constructor {
  46. 	T_unroll_constructor<unroll_count-1, T> next_unroll;
  47. 	T<unroll_count-1> functor;
  48. 	template<typename T1> inline T_unroll_constructor(T1 & val1) : next_unroll(val1), functor(val1) {}
  49. };
  50. // End of unroll
  51. template<template<unsigned> class T>
  52. struct T_unroll_constructor<0, T> { 
  53. 	template<typename T1> inline T_unroll_constructor(T1 &) {} 
  54. };
  55. // -------------------------------------------------------------------------
  56.  
  57. // Abstract base class of filters for each search variant (range_filters)
  58. struct T_filter {
  59. 	// search
  60. 	virtual size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,
  61. 		T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) = 0;
  62. };
  63. // -------------------------------------------------------------------------
  64.  
  65. // The filters for each search variant (range_filters)
  66. template<unsigned index_pred>
  67. struct T_custom_filter : T_filter {
  68.  
  69. 	inline unsigned char test_predicate(T_cash_account_row const*const __restrict row, 
  70. 		T_range_filters const*const __restrict range_filters) 
  71. 	{    
  72. 		return 
  73. 			(!(index_pred & 1<<amount_of_money_e) || 
  74. 				(row->amount_of_money >= range_filters->begin.amount_of_money &&
  75. 				row->amount_of_money <= range_filters->end.amount_of_money)) &&
  76. 			(!(index_pred & 1<<gender_e) || 
  77. 				(row->gender >= range_filters->begin.gender && row->gender <= range_filters->end.gender)) &&
  78. 			(!(index_pred & 1<<age_e) || 
  79. 				(row->age >= range_filters->begin.age && row->age <= range_filters->end.age)) &&
  80. 			(!(index_pred & 1<<code_e) || 
  81. 				(row->code >= range_filters->begin.code && row->code <= range_filters->end.code)) &&
  82. 			(!(index_pred & 1<<height_e) || 
  83. 				(row->height >= range_filters->begin.height && row->height <= range_filters->end.height));
  84. 	}
  85. 	// -------------------------------------------------------------------------
  86.  
  87. 	// search
  88. 	virtual size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,
  89. 		T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) final
  90. 	{
  91. 		size_t result_size = 0;
  92. 		size_t i; // loop index
  93. 		for(i = 0; i < c_array_size; ++i) {
  94. 			if(test_predicate(array_ptr + i, range_filters)) 
  95. 				result_ptr[result_size] = array_ptr[i], ++result_size;
  96. 		}
  97. 		return result_size;
  98. 	}
  99. };
  100. // -------------------------------------------------------------------------
  101.  
  102. class T_optimized_search {
  103. 	// unroll tamplates
  104. 	template<unsigned index_pred>
  105. 	struct T_unroll_find {
  106. 		template<typename T> T_unroll_find(T &filters) { 
  107. 			filters[index_pred].reset( new T_custom_filter<index_pred>() ); 
  108. 		}
  109. 	};
  110. 	// -------------------------------------------------------------------------
  111.  
  112. 	// Get index of T_test_pred version for current search range
  113. 	inline unsigned get_index_pred(T_range_filters const*const __restrict range_filters) {
  114. 		unsigned result = 0;
  115. 		for(size_t i = 0; i < last_e; ++i) 
  116. 			result |= range_filters->use_filter[i]?(1<<i):0;
  117. 		return result;
  118. 	}
  119.  
  120. 	std::array<std::unique_ptr<T_filter>, 1<<last_e> filters;
  121. 	T_unroll_constructor<1<<last_e, T_unroll_find> fill_filter;
  122. public:
  123. 	T_optimized_search() : fill_filter(filters) {}
  124.  
  125. 	// C++ optimized search
  126. 	inline size_t search(T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,
  127. 			T_cash_account_row *const __restrict result_ptr, T_range_filters const*const __restrict range_filters) 
  128. 	{
  129. 		auto const& filter = filters[get_index_pred(range_filters)];
  130. 		return filter->search(array_ptr, c_array_size, result_ptr, range_filters);
  131. 	}
  132. };
  133. // -------------------------------------------------------------------------
  134.  
  135. /* Compare row with filters */
  136. static inline unsigned char test_predicate(struct T_cash_account_row const*const __restrict row, 
  137.     struct T_range_filters const*const __restrict range_filters) 
  138. {    
  139.     return 
  140.         (!range_filters->use_filter[amount_of_money_e] || 
  141.             (row->amount_of_money >= range_filters->begin.amount_of_money &&
  142.             row->amount_of_money <= range_filters->end.amount_of_money)) &&
  143.         (!range_filters->use_filter[gender_e] || 
  144.             (row->gender >= range_filters->begin.gender && row->gender <= range_filters->end.gender)) &&
  145.         (!range_filters->use_filter[age_e] || 
  146.             (row->age >= range_filters->begin.age && row->age <= range_filters->end.age)) &&
  147.         (!range_filters->use_filter[code_e] || 
  148.             (row->code >= range_filters->begin.code && row->code <= range_filters->end.code)) &&
  149.         (!range_filters->use_filter[height_e] || 
  150.             (row->height >= range_filters->begin.height && row->height <= range_filters->end.height));
  151. }
  152. /* ----------------------------------------------------------------------- */
  153.  
  154. /* search */
  155. static inline size_t search(struct T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size,
  156. 	struct T_cash_account_row *const __restrict result_ptr, struct T_range_filters const*const __restrict range_filters) 
  157. {
  158. 	size_t result_size = 0;
  159. 	size_t i; /* loop index */
  160. 	for(i = 0; i < c_array_size; ++i) {
  161. 		if(test_predicate(array_ptr + i, range_filters)) 
  162. 			result_ptr[result_size] = array_ptr[i], ++result_size;
  163. 	}
  164. 	return result_size;
  165. }
  166. /* ----------------------------------------------------------------------- */
  167.  
  168. int main() {
  169.  
  170. 	size_t i; /* loop index */
  171.     struct T_cash_account_row *const array_ptr = ( struct T_cash_account_row *)calloc(c_array_size, sizeof(struct T_cash_account_row));
  172.     if (array_ptr == NULL) {
  173. 		printf ("calloc error\n");
  174. 		exit(1);
  175. 	}
  176.  
  177. 	/* initialize random seed: */
  178. 	/* srand (time(NULL)); */
  179.  
  180. 	/* Fill table random data */
  181. 	for(i = 0; i < c_array_size; ++i) 
  182. 		array_ptr[i] = generate_row();
  183. 	printf ("Generated rows: %d \n", c_array_size);
  184.  
  185.     struct T_range_filters range_filters = {0};  
  186.  
  187. 	range_filters.use_filter[amount_of_money_e] = rand()%1 + 0;
  188. 	range_filters.use_filter[gender_e] = rand()%1 + 0;
  189. 	range_filters.use_filter[height_e] = rand()%1 + 0;
  190.  
  191.     range_filters.begin.age = rand() % 100;
  192.     range_filters.end.age = range_filters.begin.age + 5;
  193.     range_filters.use_filter[age_e] = rand()%1 + 1;
  194.  
  195.     range_filters.begin.code = rand() % 30000;
  196.     range_filters.end.code = range_filters.begin.code + 5;
  197.     range_filters.use_filter[code_e] = rand()%1 + 1;
  198.  
  199.     struct T_cash_account_row *const result_ptr = ( struct T_cash_account_row *)calloc(c_array_size, sizeof(struct T_cash_account_row));
  200.  
  201. 	size_t result_size;
  202. 	clock_t end, start;
  203. 	T_optimized_search optimized_search;	// C++ optimized search
  204.  
  205. 	printf ("C++-Searching...\n");
  206.  
  207. 	start = clock();
  208. 	result_size = optimized_search.search(array_ptr, c_array_size, result_ptr, &range_filters);
  209. 	end = clock();
  210. 	float cpp_took_time = static_cast<float>(end - start);
  211. 	printf ("C++-optimized search took %f seconds.\n", cpp_took_time/CLOCKS_PER_SEC);
  212.  
  213. 	printf ("Found rows: %d \n", result_size);
  214.  
  215. 	printf ("C-Searching...\n");
  216.  
  217. 	start = clock();
  218. 	result_size = search(array_ptr, c_array_size, result_ptr, &range_filters);
  219. 	end = clock();
  220. 	float c_took_time = static_cast<float>(end - start);
  221. 	printf ("C-search took %f seconds.\n", c_took_time/CLOCKS_PER_SEC);
  222.  
  223. 	printf ("The C++ faster than C: %f times \n", c_took_time/cpp_took_time);
  224.  
  225. 	printf ("Found rows: %d \n", result_size);
  226.  
  227. 	//for(i = 0; i < result_size; ++i) {
  228. 	//	printf ("%d, %d, %d, %d, %d \n", 
  229. 	//		result_ptr[i].age, result_ptr[i].amount_of_money, result_ptr[i].code, result_ptr[i].gender, result_ptr[i].height);
  230. 	//}
  231.  
  232.     int qwerty;
  233.     scanf ("%d",&qwerty);
  234.     return 0;
  235. }
Success #stdin #stdout 2.05s 159296KB
comments (?)
stdin 
Standard input is empty
stdout 
Generated rows: 10000000 
C++-Searching...
C++-optimized search took 0.040000 seconds.
Found rows: 38 
C-Searching...
C-search took 0.070000 seconds.
The C++ faster than C: 1.750000 times 
Found rows: 38
https://ideone.com/o9mE2m
language:
C++14 (gcc 8.3)
created:
11 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!