arkworks-rs · jon-chuang · Feb 11, 2021 · Feb 8, 2021 · Feb 8, 2021 · Feb 8, 2021
@@ -188,6 +188,19 @@ pub trait Field:
         }
         res
     }
+
+    /// Exponentiates this element by a number represented with `u64` limbs,
+    /// least significant limb first.
+    #[inline]
+    fn pow_with_table<S: AsRef<[u64]>>(pows_2: &[Self], exp: S) -> Self {
+        let mut res = Self::one();
+        for (pow, bit) in BitIteratorLE::without_trailing_zeros(exp).enumerate() {
+            if bit {
+                res *= &pows_2[pow];
+            }
+        }
+        res
+    }
 }
 
 /// A trait that defines parameters for a field that can be used for FFTs.

@@ -1,8 +1,12 @@
 extern crate criterion;
 
 use ark_ff::Field;
-use ark_poly::{polynomial::univariate::DensePolynomial, Polynomial, UVPolynomial};
+use ark_poly::{
+    polynomial::univariate::DensePolynomial, polynomial::univariate::SparsePolynomial, Polynomial,
+    UVPolynomial,
+};
 use ark_poly_benches::size_range;
+use ark_std::rand::Rng;
 use ark_test_curves::bls12_381::Fr as bls12_381_fr;
 use criterion::BenchmarkId;
 use criterion::{criterion_group, criterion_main, Bencher, Criterion};
@@ -14,6 +18,7 @@ const BENCHMARK_LOG_INTERVAL_DEGREE: usize = 1;
 const ENABLE_ADD_BENCH: bool = true;
 const ENABLE_ADD_ASSIGN_BENCH: bool = true;
 const ENABLE_EVALUATE_BENCH: bool = true;
+const ENABLE_SPARSE_EVALUATE_BENCH: bool = true;
 
 // returns vec![2^{min}, 2^{min + interval}, ..., 2^{max}], where:
 // interval = BENCHMARK_LOG_INTERVAL_DEGREE
@@ -35,6 +40,21 @@ fn setup_bench<F: Field>(c: &mut Criterion, name: &str, bench_fn: fn(&mut Benche
     group.finish();
 }
 
+fn bench_sparse_poly_evaluate<F: Field>(b: &mut Bencher, non_zero_entries: &usize) {
+    const MAX_DEGREE: usize = 1 << 15;
+    // Per benchmark setup
+    let mut rng = &mut ark_std::test_rng();
+    let mut inner: Vec<(usize, F)> = Vec::with_capacity(*non_zero_entries);
+    (0..*non_zero_entries)
+        .for_each(|_| inner.push((rng.gen_range(0, MAX_DEGREE), F::rand(&mut rng))));
+    let poly = SparsePolynomial::<F>::from_coefficients_vec(inner);
+    b.iter(|| {
+        // Per benchmark iteration
+        let pt = F::rand(&mut rng);
+        poly.evaluate(&pt);
+    });
+}
+
 fn bench_poly_evaluate<F: Field>(b: &mut Bencher, degree: &usize) {
     // Per benchmark setup
     let mut rng = &mut ark_std::test_rng();
@@ -81,6 +101,10 @@ fn poly_benches<F: Field>(c: &mut Criterion, name: &'static str) {
         let cur_name = format!("{:?} - evaluate_polynomial", name.clone());
         setup_bench::<F>(c, &cur_name, bench_poly_evaluate::<F>);
     }
+    if ENABLE_SPARSE_EVALUATE_BENCH {
+        let cur_name = format!("{:?} - evaluate_sparse_polynomial", name.clone());
+        setup_bench::<F>(c, &cur_name, bench_sparse_poly_evaluate::<F>);
+    }
 }
 
 fn bench_bls12_381(c: &mut Criterion) {

@@ -62,11 +62,30 @@ impl<F: Field> Polynomial<F> for SparsePolynomial<F> {
         if self.is_zero() {
             return F::zero();
         }
+
+        let total_bits = core::mem::size_of::<usize>() * 8;
+        let max_pow_2 = total_bits - self.degree().leading_zeros() as usize;
+
+        let mut pows_2 = Vec::<F>::with_capacity(max_pow_2);
+
+        let mut p = *point;
+        pows_2.push(p);
+        for _ in 1..max_pow_2 {
+            p.square_in_place();
+            pows_2.push(p);
+        }
         // compute all coeff * point^{i} and then sum the results
         let total = self
             .coeffs
             .iter()
-            .map(|(i, c)| (*c * point.pow(&[*i as u64])))
+            .map(|(i, c)| {
+                debug_assert_eq!(
+                    F::pow_with_table(&pows_2[..], &[*i as u64]),
+                    point.pow(&[*i as u64]),
+                    "pows not equal"
+                );
+                *c * F::pow_with_table(&pows_2[..], &[*i as u64])
+            })
             .sum();
         total
     }