1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  extern crate criterion;
 20  
 21  use alphavm_algorithms::fft::{DensePolynomial, EvaluationDomain};
 22  use alphavm_curves::bls12_377::Fr as Bls12_377_Fr;
 23  use alphavm_fields::PrimeField;
 24  use alphavm_utilities::TestRng;
 25  
 26  use criterion::{criterion_group, criterion_main, Bencher, BenchmarkId, Criterion};
 27  use std::cmp::min;
 28  
 29  /// Degree bounds to benchmark on
 30  /// e.g. degree bound of 2^{15}, means we do an FFT for a degree (2^{15} - 1)
 31  /// polynomial
 32  const BENCHMARK_MIN_DEGREE: usize = 1 << 15;
 33  const BENCHMARK_MAX_DEGREE: usize = 1 << 22;
 34  const BENCHMARK_LOG_INTERVAL_DEGREE: usize = 1;
 35  
 36  /// Utility function for getting a vector of degrees to benchmark on.
 37  /// Returns vec![2^{min}, 2^{min + interval}, ..., 2^{max}], where:
 38  /// interval = log_interval
 39  /// min      = ceil(log_2(min_degree))
 40  /// max      = ceil(log_2(max_degree))
 41  pub fn size_range(log_interval: usize, min_degree: usize, max_degree: usize) -> Vec<usize> {
 42      let mut to_ret = vec![min_degree.next_power_of_two()];
 43      let interval = 1 << log_interval;
 44  
 45      while *to_ret.last().unwrap() < max_degree {
 46          let next_elem = min(max_degree, interval * to_ret.last().unwrap());
 47          to_ret.push(next_elem);
 48      }
 49  
 50      to_ret
 51  }
 52  
 53  /// Returns vec![2^{min}, 2^{min + interval}, ..., 2^{max}], where:
 54  /// interval = BENCHMARK_LOG_INTERVAL_DEGREE
 55  /// min      = ceil(log_2(BENCHMARK_MIN_DEGREE))
 56  /// max      = ceil(log_2(BENCHMARK_MAX_DEGREE))
 57  fn default_size_range() -> Vec<usize> {
 58      size_range(BENCHMARK_LOG_INTERVAL_DEGREE, BENCHMARK_MIN_DEGREE, BENCHMARK_MAX_DEGREE)
 59  }
 60  
 61  fn setup_bench(c: &mut Criterion, name: &str, bench_fn: fn(&mut Bencher, &usize)) {
 62      let mut group = c.benchmark_group(name);
 63      for degree in default_size_range().iter() {
 64          group.bench_with_input(BenchmarkId::from_parameter(degree), degree, bench_fn);
 65      }
 66      group.finish();
 67  }
 68  
 69  fn create_evaluation_domain<F: PrimeField>(degree: usize) -> (EvaluationDomain<F>, Vec<F>) {
 70      let domain = EvaluationDomain::new(degree).unwrap();
 71      let a = DensePolynomial::<F>::rand(degree - 1, &mut TestRng::default()).coeffs().to_vec();
 72      (domain, a)
 73  }
 74  
 75  fn bench_fft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 76      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 77  
 78      b.iter(|| {
 79          domain.fft_in_place(&mut a);
 80      });
 81  }
 82  
 83  fn bench_ifft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 84      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 85  
 86      b.iter(|| {
 87          domain.ifft_in_place(&mut a);
 88      });
 89  }
 90  
 91  fn bench_coset_fft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 92      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 93  
 94      b.iter(|| {
 95          domain.coset_fft_in_place(&mut a);
 96      });
 97  }
 98  
 99  fn bench_coset_ifft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
100      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
101  
102      b.iter(|| {
103          domain.coset_ifft_in_place(&mut a);
104      });
105  }
106  
107  fn fft_benches<F: PrimeField>(c: &mut Criterion, name: &str) {
108      let description = format!("{name:?} - subgroup_fft_in_place");
109      setup_bench(c, &description, bench_fft_in_place::<F>);
110      let description = format!("{name:?} - subgroup_ifft_in_place");
111      setup_bench(c, &description, bench_ifft_in_place::<F>);
112      let description = format!("{name:?} - coset_fft_in_place");
113      setup_bench(c, &description, bench_coset_fft_in_place::<F>);
114      let description = format!("{name:?} - coset_ifft_in_place");
115      setup_bench(c, &description, bench_coset_ifft_in_place::<F>);
116  }
117  
118  fn bench_bls12_377(c: &mut Criterion) {
119      fft_benches::<Bls12_377_Fr>(c, "BLS12-377 - radix-2");
120  }
121  
122  criterion_group!(benches, bench_bls12_377);
123  criterion_main!(benches);