1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the deltavm library.
  3  
  4  // Licensed under the Apache License, Version 2.0 (the "License");
  5  // you may not use this file except in compliance with the License.
  6  // You may obtain a copy of the License at:
  7  
  8  // http://www.apache.org/licenses/LICENSE-2.0
  9  
 10  // Unless required by applicable law or agreed to in writing, software
 11  // distributed under the License is distributed on an "AS IS" BASIS,
 12  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 13  // See the License for the specific language governing permissions and
 14  // limitations under the License.
 15  
 16  extern crate criterion;
 17  
 18  use deltavm_algorithms::fft::{DensePolynomial, EvaluationDomain};
 19  use deltavm_curves::bls12_377::Fr as Bls12_377_Fr;
 20  use deltavm_fields::PrimeField;
 21  use deltavm_utilities::TestRng;
 22  
 23  use criterion::{Bencher, BenchmarkId, Criterion, criterion_group, criterion_main};
 24  use std::cmp::min;
 25  
 26  /// Degree bounds to benchmark on
 27  /// e.g. degree bound of 2^{15}, means we do an FFT for a degree (2^{15} - 1)
 28  /// polynomial
 29  const BENCHMARK_MIN_DEGREE: usize = 1 << 15;
 30  const BENCHMARK_MAX_DEGREE: usize = 1 << 22;
 31  const BENCHMARK_LOG_INTERVAL_DEGREE: usize = 1;
 32  
 33  /// Utility function for getting a vector of degrees to benchmark on.
 34  /// Returns vec![2^{min}, 2^{min + interval}, ..., 2^{max}], where:
 35  /// interval = log_interval
 36  /// min      = ceil(log_2(min_degree))
 37  /// max      = ceil(log_2(max_degree))
 38  pub fn size_range(log_interval: usize, min_degree: usize, max_degree: usize) -> Vec<usize> {
 39      let mut to_ret = vec![min_degree.next_power_of_two()];
 40      let interval = 1 << log_interval;
 41  
 42      while *to_ret.last().unwrap() < max_degree {
 43          let next_elem = min(max_degree, interval * to_ret.last().unwrap());
 44          to_ret.push(next_elem);
 45      }
 46  
 47      to_ret
 48  }
 49  
 50  /// Returns vec![2^{min}, 2^{min + interval}, ..., 2^{max}], where:
 51  /// interval = BENCHMARK_LOG_INTERVAL_DEGREE
 52  /// min      = ceil(log_2(BENCHMARK_MIN_DEGREE))
 53  /// max      = ceil(log_2(BENCHMARK_MAX_DEGREE))
 54  fn default_size_range() -> Vec<usize> {
 55      size_range(BENCHMARK_LOG_INTERVAL_DEGREE, BENCHMARK_MIN_DEGREE, BENCHMARK_MAX_DEGREE)
 56  }
 57  
 58  fn setup_bench(c: &mut Criterion, name: &str, bench_fn: fn(&mut Bencher, &usize)) {
 59      let mut group = c.benchmark_group(name);
 60      for degree in default_size_range().iter() {
 61          group.bench_with_input(BenchmarkId::from_parameter(degree), degree, bench_fn);
 62      }
 63      group.finish();
 64  }
 65  
 66  fn create_evaluation_domain<F: PrimeField>(degree: usize) -> (EvaluationDomain<F>, Vec<F>) {
 67      let domain = EvaluationDomain::new(degree).unwrap();
 68      let a = DensePolynomial::<F>::rand(degree - 1, &mut TestRng::default()).coeffs().to_vec();
 69      (domain, a)
 70  }
 71  
 72  fn bench_fft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 73      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 74  
 75      b.iter(|| {
 76          domain.fft_in_place(&mut a);
 77      });
 78  }
 79  
 80  fn bench_ifft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 81      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 82  
 83      b.iter(|| {
 84          domain.ifft_in_place(&mut a);
 85      });
 86  }
 87  
 88  fn bench_coset_fft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 89      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 90  
 91      b.iter(|| {
 92          domain.coset_fft_in_place(&mut a);
 93      });
 94  }
 95  
 96  fn bench_coset_ifft_in_place<F: PrimeField>(b: &mut Bencher, degree: &usize) {
 97      let (domain, mut a) = create_evaluation_domain::<F>(*degree);
 98  
 99      b.iter(|| {
100          domain.coset_ifft_in_place(&mut a);
101      });
102  }
103  
104  fn fft_benches<F: PrimeField>(c: &mut Criterion, name: &str) {
105      let description = format!("{name:?} - subgroup_fft_in_place");
106      setup_bench(c, &description, bench_fft_in_place::<F>);
107      let description = format!("{name:?} - subgroup_ifft_in_place");
108      setup_bench(c, &description, bench_ifft_in_place::<F>);
109      let description = format!("{name:?} - coset_fft_in_place");
110      setup_bench(c, &description, bench_coset_fft_in_place::<F>);
111      let description = format!("{name:?} - coset_ifft_in_place");
112      setup_bench(c, &description, bench_coset_ifft_in_place::<F>);
113  }
114  
115  fn bench_bls12_377(c: &mut Criterion) {
116      fft_benches::<Bls12_377_Fr>(c, "BLS12-377 - radix-2");
117  }
118  
119  criterion_group!(benches, bench_bls12_377);
120  criterion_main!(benches);