fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <chrono>
  4.  
  5. // We are now sorting 100,000 elements at compile time!
  6. const std::size_t SIZE = 150000;
  7.  
  8. // =====================================================================
  9. // 1. C++14 Constexpr Array 
  10. // =====================================================================
  11. template <typename T, std::size_t N>
  12. struct CXArray {
  13.     T data[N];
  14.     constexpr T& operator[](std::size_t i) { return data[i]; }
  15.     constexpr const T& operator[](std::size_t i) const { return data[i]; }
  16.     constexpr T* begin() { return data; }
  17.     constexpr T* end() { return data + N; }
  18.     constexpr const T* begin() const { return data; }
  19.     constexpr const T* end() const { return data + N; }
  20. };
  21.  
  22. // =====================================================================
  23. // 2. The 100k Strategy: Constexpr Radix Sort O(N)
  24. // Reduces 20,000,000 compiler steps to just 1,600,000 steps
  25. // =====================================================================
  26. template <typename T, std::size_t N>
  27. constexpr CXArray<T, N> generate_radix_sort(CXArray<T, N> arr) {
  28.     // We allocate a buffer entirely inside compiler memory
  29.     CXArray<T, N> buffer{}; 
  30.  
  31.     // 4 passes for 32-bit integers (8 bits / base-256 per pass)
  32.     for (int byte = 0; byte < 4; ++byte) {
  33.         int counts[256] = {0};
  34.         int shift = byte * 8;
  35.  
  36.         // Step A: Count frequencies (O(N))
  37.         for (std::size_t i = 0; i < N; ++i) {
  38.             unsigned int val = static_cast<unsigned int>(arr[i]);
  39.             counts[(val >> shift) & 0xFF]++;
  40.         }
  41.  
  42.         // Step B: Prefix sums (O(256))
  43.         int pos[256] = {0};
  44.         for (int i = 1; i < 256; ++i) {
  45.             pos[i] = pos[i - 1] + counts[i - 1];
  46.         }
  47.  
  48.         // Step C: Scatter to buffer (O(N))
  49.         for (std::size_t i = 0; i < N; ++i) {
  50.             unsigned int val = static_cast<unsigned int>(arr[i]);
  51.             int bucket = (val >> shift) & 0xFF;
  52.             buffer[pos[bucket]++] = arr[i];
  53.         }
  54.  
  55.         // Step D: Copy back to array (O(N))
  56.         for (std::size_t i = 0; i < N; ++i) {
  57.             arr[i] = buffer[i];
  58.         }
  59.     }
  60.  
  61.     return arr;
  62. }
  63.  
  64. // =====================================================================
  65. // 3. Constexpr Data Generation
  66. // =====================================================================
  67. constexpr CXArray<int, SIZE> generate_random_data() {
  68.     CXArray<int, SIZE> arr{};
  69.     unsigned int seed = 987654321;
  70.     for (std::size_t i = 0; i < SIZE; ++i) {
  71.         seed = (1103515245 * seed + 12345) % 2147483648; 
  72.         arr[i] = seed % 10000000; // Generate numbers up to 10 million
  73.     }
  74.     return arr;
  75. }
  76.  
  77. // 💥 COMPILER EXECUTES 100,000 ELEMENT RADIX SORT HERE 💥
  78. constexpr auto unsorted_data = generate_random_data();
  79. auto start2 = std::chrono::high_resolution_clock::now();
  80. constexpr auto sorted_data = generate_radix_sort(unsorted_data);
  81. auto end2 = std::chrono::high_resolution_clock::now();
  82.  
  83. // =====================================================================
  84. // Benchmark Engine
  85. // =====================================================================
  86. int main() {
  87.     std::cout << "Data Size: " << SIZE << " elements\n";
  88.  
  89.     // 1. Runtime Standard Sort Benchmark
  90.     CXArray<int, SIZE> runtime_data = unsorted_data; 
  91.  
  92.     auto start1 = std::chrono::high_resolution_clock::now();
  93.     std::sort(runtime_data.begin(), runtime_data.end());
  94.     auto end1 = std::chrono::high_resolution_clock::now();
  95.     std::chrono::duration<double, std::milli> time_std = end1 - start1;
  96.  
  97.     // 2. Compile-Time Sort Benchmark (0ms)
  98.  
  99.     volatile int dummy = sorted_data[0]; 
  100.  
  101.     std::chrono::duration<double, std::milli> time_cx = end2 - start2;
  102.  
  103.     std::cout << "\n--- Benchmark Results ---\n";
  104.     std::cout << "Runtime std::sort:          " << time_std.count() << " ms\n";
  105.     std::cout << "Compile-Time Radix Sort:    " << time_cx.count() << " ms\n";
  106.  
  107.     bool correct = std::is_sorted(sorted_data.begin(), sorted_data.end());
  108.     std::cout << "\nCompile-Time array is sorted correctly: " << (correct ? "True" : "False") << "\n";
  109.  
  110.     return 0;
  111. }
Success #stdin #stdout 0.02s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Data Size: 150000 elements

--- Benchmark Results ---
Runtime std::sort:          9.21226 ms
Compile-Time Radix Sort:    0.000212 ms

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