fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <chrono>
  4.  
  5. const std::size_t SIZE = 30000;
  6.  
  7. // =====================================================================
  8. // 1. C++14 Fix: Custom Constexpr Array
  9. // Bypasses the C++14 std::array limitation where operator[] isn't constexpr
  10. // =====================================================================
  11. template <typename T, std::size_t N>
  12. struct CXArray {
  13.     T data[N];
  14.  
  15.     // Explicitly marking both const and non-const operator[] as constexpr
  16.     constexpr T& operator[](std::size_t i) { return data[i]; }
  17.     constexpr const T& operator[](std::size_t i) const { return data[i]; }
  18.  
  19.     // Iterators so std::sort still works in our benchmark
  20.     constexpr T* begin() { return data; }
  21.     constexpr T* end() { return data + N; }
  22.     constexpr const T* begin() const { return data; }
  23.     constexpr const T* end() const { return data + N; }
  24. };
  25.  
  26. // =====================================================================
  27. // 2. C++14 Compile-Time Helpers
  28. // =====================================================================
  29. template <typename T>
  30. constexpr void cx_swap(T& a, T& b) {
  31.     T tmp = a;
  32.     a = b;
  33.     b = tmp;
  34. }
  35.  
  36. // =====================================================================
  37. // 3. C++14 Template Metaprogramming Quicksort (Compile-Time)
  38. // =====================================================================
  39. template <typename T, std::size_t N>
  40. constexpr void compile_time_sort(CXArray<T, N>& arr, int left, int right) {
  41.     if (left >= right) return;
  42.  
  43.     T pivot = arr[left + (right - left) / 2];
  44.     int i = left;
  45.     int j = right;
  46.  
  47.     while (i <= j) {
  48.         while (arr[i] < pivot) i++;
  49.         while (arr[j] > pivot) j--;
  50.  
  51.         if (i <= j) {
  52.             cx_swap(arr[i], arr[j]);
  53.             i++;
  54.             j--;
  55.         }
  56.     }
  57.  
  58.     if (left < j) compile_time_sort(arr, left, j);
  59.     if (i < right) compile_time_sort(arr, i, right);
  60. }
  61.  
  62. // Wrapper to return the sorted array
  63. template <typename T, std::size_t N>
  64. constexpr CXArray<T, N> generate_sorted(CXArray<T, N> arr) {
  65.     compile_time_sort(arr, 0, N - 1);
  66.     return arr;
  67. }
  68.  
  69. // =====================================================================
  70. // 4. Constexpr Random Number Generator (LCG)
  71. // =====================================================================
  72. constexpr CXArray<int, SIZE> generate_random_data() {
  73.     CXArray<int, SIZE> arr{};
  74.     unsigned int seed = 12345;
  75.     for (std::size_t i = 0; i < SIZE; ++i) {
  76.         seed = (1103515245 * seed + 12345) % 2147483648; 
  77.         arr[i] = seed % 100000;
  78.     }
  79.     return arr;
  80. }
  81.  
  82. // The compiler generates, sorts, and embeds this in the binary
  83. constexpr auto unsorted_data = generate_random_data();
  84. constexpr auto sorted_data = generate_sorted(unsorted_data);
  85.  
  86. // =====================================================================
  87. // Benchmark Engine
  88. // =====================================================================
  89. int main() {
  90.     std::cout << "Data Size: " << SIZE << " elements\n";
  91.  
  92.     // Benchmark 1: std::sort (Runtime)
  93.     CXArray<int, SIZE> runtime_data = unsorted_data; 
  94.  
  95.     auto start1 = std::chrono::high_resolution_clock::now();
  96.     std::sort(runtime_data.begin(), runtime_data.end());
  97.     auto end1 = std::chrono::high_resolution_clock::now();
  98.     std::chrono::duration<double, std::milli> time_std = end1 - start1;
  99.  
  100.     // Benchmark 2: Compile-Time Metaprogramming Sort
  101.     auto start2 = std::chrono::high_resolution_clock::now();
  102.  
  103.     // Prevent compiler from optimizing the clock check away
  104.     volatile int dummy = sorted_data[0]; 
  105.  
  106.     auto end2 = std::chrono::high_resolution_clock::now();
  107.     std::chrono::duration<double, std::milli> time_cx = end2 - start2;
  108.  
  109.     // Results
  110.     std::cout << "\n--- Benchmark Results ---\n";
  111.     std::cout << "Runtime std::sort:   " << time_std.count() << " ms\n";
  112.     std::cout << "Compile-Time sort:   " << time_cx.count() << " ms\n";
  113.  
  114.     bool correct = std::is_sorted(sorted_data.begin(), sorted_data.end());
  115.     std::cout << "\nCompile-Time array is sorted correctly: " << (correct ? "True" : "False") << "\n";
  116.  
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Data Size: 30000 elements

--- Benchmark Results ---
Runtime std::sort:   1.64357 ms
Compile-Time sort:   4.1e-05 ms

Compile-Time array is sorted correctly: True
https://ideone.com/aPfbYX
language:
C++14 (gcc 8.3)
created:
8 hours 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!