summaryrefslogtreecommitdiffstats
path: root/third_party/rust/itertools-0.8.0/benches
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/rust/itertools-0.8.0/benches')
-rw-r--r--third_party/rust/itertools-0.8.0/benches/bench1.rs733
-rw-r--r--third_party/rust/itertools-0.8.0/benches/extra/mod.rs4
-rw-r--r--third_party/rust/itertools-0.8.0/benches/extra/zipslices.rs189
-rw-r--r--third_party/rust/itertools-0.8.0/benches/tree_fold1.rs126
-rw-r--r--third_party/rust/itertools-0.8.0/benches/tuple_combinations.rs97
-rw-r--r--third_party/rust/itertools-0.8.0/benches/tuples.rs190
6 files changed, 1339 insertions, 0 deletions
diff --git a/third_party/rust/itertools-0.8.0/benches/bench1.rs b/third_party/rust/itertools-0.8.0/benches/bench1.rs
new file mode 100644
index 0000000000..b9d3b4ff4b
--- /dev/null
+++ b/third_party/rust/itertools-0.8.0/benches/bench1.rs
@@ -0,0 +1,733 @@
+#![feature(test)]
+
+extern crate test;
+#[macro_use] extern crate itertools;
+
+use test::{black_box};
+use itertools::Itertools;
+
+use itertools::free::cloned;
+
+use std::iter::repeat;
+use std::cmp;
+use std::ops::Add;
+
+mod extra;
+
+use extra::ZipSlices;
+
+#[bench]
+fn slice_iter(b: &mut test::Bencher)
+{
+ let xs: Vec<_> = repeat(1i32).take(20).collect();
+ b.iter(|| for elt in xs.iter() {
+ test::black_box(elt);
+ })
+}
+
+#[bench]
+fn slice_iter_rev(b: &mut test::Bencher)
+{
+ let xs: Vec<_> = repeat(1i32).take(20).collect();
+ b.iter(|| for elt in xs.iter().rev() {
+ test::black_box(elt);
+ })
+}
+
+#[bench]
+fn zip_default_zip(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ for (&x, &y) in xs.iter().zip(&ys) {
+ test::black_box(x);
+ test::black_box(y);
+ }
+ })
+}
+
+#[bench]
+fn zipdot_i32_default_zip(b: &mut test::Bencher)
+{
+ let xs = vec![2; 1024];
+ let ys = vec![2; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let mut s = 0;
+ for (&x, &y) in xs.iter().zip(&ys) {
+ s += x * y;
+ }
+ s
+ })
+}
+
+#[bench]
+fn zipdot_f32_default_zip(b: &mut test::Bencher)
+{
+ let xs = vec![2f32; 1024];
+ let ys = vec![2f32; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let mut s = 0.;
+ for (&x, &y) in xs.iter().zip(&ys) {
+ s += x * y;
+ }
+ s
+ })
+}
+
+#[bench]
+fn zip_default_zip3(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let zs = vec![0; 766];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+ let zs = black_box(zs);
+
+ b.iter(|| {
+ for ((&x, &y), &z) in xs.iter().zip(&ys).zip(&zs) {
+ test::black_box(x);
+ test::black_box(y);
+ test::black_box(z);
+ }
+ })
+}
+
+#[bench]
+fn zip_slices_ziptuple(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+
+ b.iter(|| {
+ let xs = black_box(&xs);
+ let ys = black_box(&ys);
+ for (&x, &y) in itertools::multizip((xs, ys)) {
+ test::black_box(x);
+ test::black_box(y);
+ }
+ })
+}
+
+#[bench]
+fn zipslices(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ for (&x, &y) in ZipSlices::new(&xs, &ys) {
+ test::black_box(x);
+ test::black_box(y);
+ }
+ })
+}
+
+#[bench]
+fn zipslices_mut(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let xs = black_box(xs);
+ let mut ys = black_box(ys);
+
+ b.iter(|| {
+ for (&x, &mut y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) {
+ test::black_box(x);
+ test::black_box(y);
+ }
+ })
+}
+
+#[bench]
+fn zipdot_i32_zipslices(b: &mut test::Bencher)
+{
+ let xs = vec![2; 1024];
+ let ys = vec![2; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let mut s = 0i32;
+ for (&x, &y) in ZipSlices::new(&xs, &ys) {
+ s += x * y;
+ }
+ s
+ })
+}
+
+#[bench]
+fn zipdot_f32_zipslices(b: &mut test::Bencher)
+{
+ let xs = vec![2f32; 1024];
+ let ys = vec![2f32; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let mut s = 0.;
+ for (&x, &y) in ZipSlices::new(&xs, &ys) {
+ s += x * y;
+ }
+ s
+ })
+}
+
+
+#[bench]
+fn zip_checked_counted_loop(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ // Must slice to equal lengths, and then bounds checks are eliminated!
+ let len = cmp::min(xs.len(), ys.len());
+ let xs = &xs[..len];
+ let ys = &ys[..len];
+
+ for i in 0..len {
+ let x = xs[i];
+ let y = ys[i];
+ test::black_box(x);
+ test::black_box(y);
+ }
+ })
+}
+
+#[bench]
+fn zipdot_i32_checked_counted_loop(b: &mut test::Bencher)
+{
+ let xs = vec![2; 1024];
+ let ys = vec![2; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ // Must slice to equal lengths, and then bounds checks are eliminated!
+ let len = cmp::min(xs.len(), ys.len());
+ let xs = &xs[..len];
+ let ys = &ys[..len];
+
+ let mut s = 0i32;
+
+ for i in 0..len {
+ s += xs[i] * ys[i];
+ }
+ s
+ })
+}
+
+#[bench]
+fn zipdot_f32_checked_counted_loop(b: &mut test::Bencher)
+{
+ let xs = vec![2f32; 1024];
+ let ys = vec![2f32; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ // Must slice to equal lengths, and then bounds checks are eliminated!
+ let len = cmp::min(xs.len(), ys.len());
+ let xs = &xs[..len];
+ let ys = &ys[..len];
+
+ let mut s = 0.;
+
+ for i in 0..len {
+ s += xs[i] * ys[i];
+ }
+ s
+ })
+}
+
+#[bench]
+fn zipdot_f32_checked_counted_unrolled_loop(b: &mut test::Bencher)
+{
+ let xs = vec![2f32; 1024];
+ let ys = vec![2f32; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ // Must slice to equal lengths, and then bounds checks are eliminated!
+ let len = cmp::min(xs.len(), ys.len());
+ let mut xs = &xs[..len];
+ let mut ys = &ys[..len];
+
+ let mut s = 0.;
+ let (mut p0, mut p1, mut p2, mut p3, mut p4, mut p5, mut p6, mut p7) =
+ (0., 0., 0., 0., 0., 0., 0., 0.);
+
+ // how to unroll and have bounds checks eliminated (by cristicbz)
+ // split sum into eight parts to enable vectorization (by bluss)
+ while xs.len() >= 8 {
+ p0 += xs[0] * ys[0];
+ p1 += xs[1] * ys[1];
+ p2 += xs[2] * ys[2];
+ p3 += xs[3] * ys[3];
+ p4 += xs[4] * ys[4];
+ p5 += xs[5] * ys[5];
+ p6 += xs[6] * ys[6];
+ p7 += xs[7] * ys[7];
+
+ xs = &xs[8..];
+ ys = &ys[8..];
+ }
+ s += p0 + p4;
+ s += p1 + p5;
+ s += p2 + p6;
+ s += p3 + p7;
+
+ for i in 0..xs.len() {
+ s += xs[i] * ys[i];
+ }
+ s
+ })
+}
+
+#[bench]
+fn zip_unchecked_counted_loop(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let len = cmp::min(xs.len(), ys.len());
+ for i in 0..len {
+ unsafe {
+ let x = *xs.get_unchecked(i);
+ let y = *ys.get_unchecked(i);
+ test::black_box(x);
+ test::black_box(y);
+ }
+ }
+ })
+}
+
+#[bench]
+fn zipdot_i32_unchecked_counted_loop(b: &mut test::Bencher)
+{
+ let xs = vec![2; 1024];
+ let ys = vec![2; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let len = cmp::min(xs.len(), ys.len());
+ let mut s = 0i32;
+ for i in 0..len {
+ unsafe {
+ let x = *xs.get_unchecked(i);
+ let y = *ys.get_unchecked(i);
+ s += x * y;
+ }
+ }
+ s
+ })
+}
+
+#[bench]
+fn zipdot_f32_unchecked_counted_loop(b: &mut test::Bencher)
+{
+ let xs = vec![2.; 1024];
+ let ys = vec![2.; 768];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+
+ b.iter(|| {
+ let len = cmp::min(xs.len(), ys.len());
+ let mut s = 0f32;
+ for i in 0..len {
+ unsafe {
+ let x = *xs.get_unchecked(i);
+ let y = *ys.get_unchecked(i);
+ s += x * y;
+ }
+ }
+ s
+ })
+}
+
+#[bench]
+fn zip_unchecked_counted_loop3(b: &mut test::Bencher)
+{
+ let xs = vec![0; 1024];
+ let ys = vec![0; 768];
+ let zs = vec![0; 766];
+ let xs = black_box(xs);
+ let ys = black_box(ys);
+ let zs = black_box(zs);
+
+ b.iter(|| {
+ let len = cmp::min(xs.len(), cmp::min(ys.len(), zs.len()));
+ for i in 0..len {
+ unsafe {
+ let x = *xs.get_unchecked(i);
+ let y = *ys.get_unchecked(i);
+ let z = *zs.get_unchecked(i);
+ test::black_box(x);
+ test::black_box(y);
+ test::black_box(z);
+ }
+ }
+ })
+}
+
+#[bench]
+fn group_by_lazy_1(b: &mut test::Bencher) {
+ let mut data = vec![0; 1024];
+ for (index, elt) in data.iter_mut().enumerate() {
+ *elt = index / 10;
+ }
+
+ let data = test::black_box(data);
+
+ b.iter(|| {
+ for (_key, group) in &data.iter().group_by(|elt| **elt) {
+ for elt in group {
+ test::black_box(elt);
+ }
+ }
+ })
+}
+
+#[bench]
+fn group_by_lazy_2(b: &mut test::Bencher) {
+ let mut data = vec![0; 1024];
+ for (index, elt) in data.iter_mut().enumerate() {
+ *elt = index / 2;
+ }
+
+ let data = test::black_box(data);
+
+ b.iter(|| {
+ for (_key, group) in &data.iter().group_by(|elt| **elt) {
+ for elt in group {
+ test::black_box(elt);
+ }
+ }
+ })
+}
+
+#[bench]
+fn slice_chunks(b: &mut test::Bencher) {
+ let data = vec![0; 1024];
+
+ let data = test::black_box(data);
+ let sz = test::black_box(10);
+
+ b.iter(|| {
+ for group in data.chunks(sz) {
+ for elt in group {
+ test::black_box(elt);
+ }
+ }
+ })
+}
+
+#[bench]
+fn chunks_lazy_1(b: &mut test::Bencher) {
+ let data = vec![0; 1024];
+
+ let data = test::black_box(data);
+ let sz = test::black_box(10);
+
+ b.iter(|| {
+ for group in &data.iter().chunks(sz) {
+ for elt in group {
+ test::black_box(elt);
+ }
+ }
+ })
+}
+
+#[bench]
+fn equal(b: &mut test::Bencher) {
+ let data = vec![7; 1024];
+ let l = data.len();
+ let alpha = test::black_box(&data[1..]);
+ let beta = test::black_box(&data[..l - 1]);
+ b.iter(|| {
+ itertools::equal(alpha, beta)
+ })
+}
+
+#[bench]
+fn merge_default(b: &mut test::Bencher) {
+ let mut data1 = vec![0; 1024];
+ let mut data2 = vec![0; 800];
+ let mut x = 0;
+ for (_, elt) in data1.iter_mut().enumerate() {
+ *elt = x;
+ x += 1;
+ }
+
+ let mut y = 0;
+ for (i, elt) in data2.iter_mut().enumerate() {
+ *elt += y;
+ if i % 3 == 0 {
+ y += 3;
+ } else {
+ y += 0;
+ }
+ }
+ let data1 = test::black_box(data1);
+ let data2 = test::black_box(data2);
+ b.iter(|| {
+ data1.iter().merge(&data2).count()
+ })
+}
+
+#[bench]
+fn merge_by_cmp(b: &mut test::Bencher) {
+ let mut data1 = vec![0; 1024];
+ let mut data2 = vec![0; 800];
+ let mut x = 0;
+ for (_, elt) in data1.iter_mut().enumerate() {
+ *elt = x;
+ x += 1;
+ }
+
+ let mut y = 0;
+ for (i, elt) in data2.iter_mut().enumerate() {
+ *elt += y;
+ if i % 3 == 0 {
+ y += 3;
+ } else {
+ y += 0;
+ }
+ }
+ let data1 = test::black_box(data1);
+ let data2 = test::black_box(data2);
+ b.iter(|| {
+ data1.iter().merge_by(&data2, PartialOrd::le).count()
+ })
+}
+
+#[bench]
+fn merge_by_lt(b: &mut test::Bencher) {
+ let mut data1 = vec![0; 1024];
+ let mut data2 = vec![0; 800];
+ let mut x = 0;
+ for (_, elt) in data1.iter_mut().enumerate() {
+ *elt = x;
+ x += 1;
+ }
+
+ let mut y = 0;
+ for (i, elt) in data2.iter_mut().enumerate() {
+ *elt += y;
+ if i % 3 == 0 {
+ y += 3;
+ } else {
+ y += 0;
+ }
+ }
+ let data1 = test::black_box(data1);
+ let data2 = test::black_box(data2);
+ b.iter(|| {
+ data1.iter().merge_by(&data2, |a, b| a <= b).count()
+ })
+}
+
+#[bench]
+fn kmerge_default(b: &mut test::Bencher) {
+ let mut data1 = vec![0; 1024];
+ let mut data2 = vec![0; 800];
+ let mut x = 0;
+ for (_, elt) in data1.iter_mut().enumerate() {
+ *elt = x;
+ x += 1;
+ }
+
+ let mut y = 0;
+ for (i, elt) in data2.iter_mut().enumerate() {
+ *elt += y;
+ if i % 3 == 0 {
+ y += 3;
+ } else {
+ y += 0;
+ }
+ }
+ let data1 = test::black_box(data1);
+ let data2 = test::black_box(data2);
+ let its = &[data1.iter(), data2.iter()];
+ b.iter(|| {
+ its.iter().cloned().kmerge().count()
+ })
+}
+
+#[bench]
+fn kmerge_tenway(b: &mut test::Bencher) {
+ let mut data = vec![0; 10240];
+
+ let mut state = 1729u16;
+ fn rng(state: &mut u16) -> u16 {
+ let new = state.wrapping_mul(31421) + 6927;
+ *state = new;
+ new
+ }
+
+ for elt in &mut data {
+ *elt = rng(&mut state);
+ }
+
+ let mut chunks = Vec::new();
+ let mut rest = &mut data[..];
+ while rest.len() > 0 {
+ let chunk_len = 1 + rng(&mut state) % 512;
+ let chunk_len = cmp::min(rest.len(), chunk_len as usize);
+ let (fst, tail) = {rest}.split_at_mut(chunk_len);
+ fst.sort();
+ chunks.push(fst.iter().cloned());
+ rest = tail;
+ }
+
+ // println!("Chunk lengths: {}", chunks.iter().format_with(", ", |elt, f| f(&elt.len())));
+
+ b.iter(|| {
+ chunks.iter().cloned().kmerge().count()
+ })
+}
+
+
+fn fast_integer_sum<I>(iter: I) -> I::Item
+ where I: IntoIterator,
+ I::Item: Default + Add<Output=I::Item>
+{
+ iter.into_iter().fold(<_>::default(), |x, y| x + y)
+}
+
+
+#[bench]
+fn step_vec_2(b: &mut test::Bencher) {
+ let v = vec![0; 1024];
+ b.iter(|| {
+ fast_integer_sum(cloned(v.iter().step(2)))
+ });
+}
+
+#[bench]
+fn step_vec_10(b: &mut test::Bencher) {
+ let v = vec![0; 1024];
+ b.iter(|| {
+ fast_integer_sum(cloned(v.iter().step(10)))
+ });
+}
+
+#[bench]
+fn step_range_2(b: &mut test::Bencher) {
+ let v = black_box(0..1024);
+ b.iter(|| {
+ fast_integer_sum(v.clone().step(2))
+ });
+}
+
+#[bench]
+fn step_range_10(b: &mut test::Bencher) {
+ let v = black_box(0..1024);
+ b.iter(|| {
+ fast_integer_sum(v.clone().step(10))
+ });
+}
+
+#[bench]
+fn cartesian_product_iterator(b: &mut test::Bencher)
+{
+ let xs = vec![0; 16];
+
+ b.iter(|| {
+ let mut sum = 0;
+ for (&x, &y, &z) in iproduct!(&xs, &xs, &xs) {
+ sum += x;
+ sum += y;
+ sum += z;
+ }
+ sum
+ })
+}
+
+#[bench]
+fn cartesian_product_fold(b: &mut test::Bencher)
+{
+ let xs = vec![0; 16];
+
+ b.iter(|| {
+ let mut sum = 0;
+ iproduct!(&xs, &xs, &xs).fold((), |(), (&x, &y, &z)| {
+ sum += x;
+ sum += y;
+ sum += z;
+ });
+ sum
+ })
+}
+
+#[bench]
+fn multi_cartesian_product_iterator(b: &mut test::Bencher)
+{
+ let xs = [vec![0; 16], vec![0; 16], vec![0; 16]];
+
+ b.iter(|| {
+ let mut sum = 0;
+ for x in xs.into_iter().multi_cartesian_product() {
+ sum += x[0];
+ sum += x[1];
+ sum += x[2];
+ }
+ sum
+ })
+}
+
+#[bench]
+fn multi_cartesian_product_fold(b: &mut test::Bencher)
+{
+ let xs = [vec![0; 16], vec![0; 16], vec![0; 16]];
+
+ b.iter(|| {
+ let mut sum = 0;
+ xs.into_iter().multi_cartesian_product().fold((), |(), x| {
+ sum += x[0];
+ sum += x[1];
+ sum += x[2];
+ });
+ sum
+ })
+}
+
+#[bench]
+fn cartesian_product_nested_for(b: &mut test::Bencher)
+{
+ let xs = vec![0; 16];
+
+ b.iter(|| {
+ let mut sum = 0;
+ for &x in &xs {
+ for &y in &xs {
+ for &z in &xs {
+ sum += x;
+ sum += y;
+ sum += z;
+ }
+ }
+ }
+ sum
+ })
+}
diff --git a/third_party/rust/itertools-0.8.0/benches/extra/mod.rs b/third_party/rust/itertools-0.8.0/benches/extra/mod.rs
new file mode 100644
index 0000000000..5ddb5772f4
--- /dev/null
+++ b/third_party/rust/itertools-0.8.0/benches/extra/mod.rs
@@ -0,0 +1,4 @@
+
+
+pub use self::zipslices::ZipSlices;
+mod zipslices;
diff --git a/third_party/rust/itertools-0.8.0/benches/extra/zipslices.rs b/third_party/rust/itertools-0.8.0/benches/extra/zipslices.rs
new file mode 100644
index 0000000000..493a539fd6
--- /dev/null
+++ b/third_party/rust/itertools-0.8.0/benches/extra/zipslices.rs
@@ -0,0 +1,189 @@
+use std::cmp;
+
+// Note: There are different ways to implement ZipSlices.
+// This version performed the best in benchmarks.
+//
+// I also implemented a version with three pointes (tptr, tend, uptr),
+// that mimiced slice::Iter and only checked bounds by using tptr == tend,
+// but that was inferior to this solution.
+
+/// An iterator which iterates two slices simultaneously.
+///
+/// `ZipSlices` acts like a double-ended `.zip()` iterator.
+///
+/// It was intended to be more efficient than `.zip()`, and it was, then
+/// rustc changed how it optimizes so it can not promise improved performance
+/// at this time.
+///
+/// Note that elements past the end of the shortest of the two slices are ignored.
+///
+/// Iterator element type for `ZipSlices<T, U>` is `(T::Item, U::Item)`. For example,
+/// for a `ZipSlices<&'a [A], &'b mut [B]>`, the element type is `(&'a A, &'b mut B)`.
+#[derive(Clone)]
+pub struct ZipSlices<T, U> {
+ t: T,
+ u: U,
+ len: usize,
+ index: usize,
+}
+
+impl<'a, 'b, A, B> ZipSlices<&'a [A], &'b [B]> {
+ /// Create a new `ZipSlices` from slices `a` and `b`.
+ ///
+ /// Act like a double-ended `.zip()` iterator, but more efficiently.
+ ///
+ /// Note that elements past the end of the shortest of the two slices are ignored.
+ #[inline(always)]
+ pub fn new(a: &'a [A], b: &'b [B]) -> Self {
+ let minl = cmp::min(a.len(), b.len());
+ ZipSlices {
+ t: a,
+ u: b,
+ len: minl,
+ index: 0,
+ }
+ }
+}
+
+impl<T, U> ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ /// Create a new `ZipSlices` from slices `a` and `b`.
+ ///
+ /// Act like a double-ended `.zip()` iterator, but more efficiently.
+ ///
+ /// Note that elements past the end of the shortest of the two slices are ignored.
+ #[inline(always)]
+ pub fn from_slices(a: T, b: U) -> Self {
+ let minl = cmp::min(a.len(), b.len());
+ ZipSlices {
+ t: a,
+ u: b,
+ len: minl,
+ index: 0,
+ }
+ }
+}
+
+impl<T, U> Iterator for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ type Item = (T::Item, U::Item);
+
+ #[inline(always)]
+ fn next(&mut self) -> Option<Self::Item> {
+ unsafe {
+ if self.index >= self.len {
+ None
+ } else {
+ let i = self.index;
+ self.index += 1;
+ Some((
+ self.t.get_unchecked(i),
+ self.u.get_unchecked(i)))
+ }
+ }
+ }
+
+ #[inline]
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ let len = self.len - self.index;
+ (len, Some(len))
+ }
+}
+
+impl<T, U> DoubleEndedIterator for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ #[inline(always)]
+ fn next_back(&mut self) -> Option<Self::Item> {
+ unsafe {
+ if self.index >= self.len {
+ None
+ } else {
+ self.len -= 1;
+ let i = self.len;
+ Some((
+ self.t.get_unchecked(i),
+ self.u.get_unchecked(i)))
+ }
+ }
+ }
+}
+
+impl<T, U> ExactSizeIterator for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{}
+
+unsafe impl<T, U> Slice for ZipSlices<T, U>
+ where T: Slice,
+ U: Slice
+{
+ type Item = (T::Item, U::Item);
+
+ fn len(&self) -> usize {
+ self.len - self.index
+ }
+
+ unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item {
+ (self.t.get_unchecked(i),
+ self.u.get_unchecked(i))
+ }
+}
+
+/// A helper trait to let `ZipSlices` accept both `&[T]` and `&mut [T]`.
+///
+/// Unsafe trait because:
+///
+/// - Implementors must guarantee that `get_unchecked` is valid for all indices `0..len()`.
+pub unsafe trait Slice {
+ /// The type of a reference to the slice's elements
+ type Item;
+ #[doc(hidden)]
+ fn len(&self) -> usize;
+ #[doc(hidden)]
+ unsafe fn get_unchecked(&mut self, i: usize) -> Self::Item;
+}
+
+unsafe impl<'a, T> Slice for &'a [T] {
+ type Item = &'a T;
+ #[inline(always)]
+ fn len(&self) -> usize { (**self).len() }
+ #[inline(always)]
+ unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
+ debug_assert!(i < self.len());
+ (**self).get_unchecked(i)
+ }
+}
+
+unsafe impl<'a, T> Slice for &'a mut [T] {
+ type Item = &'a mut T;
+ #[inline(always)]
+ fn len(&self) -> usize { (**self).len() }
+ #[inline(always)]
+ unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
+ debug_assert!(i < self.len());
+ // override the lifetime constraints of &mut &'a mut [T]
+ (*(*self as *mut [T])).get_unchecked_mut(i)
+ }
+}
+
+#[test]
+fn zipslices() {
+
+ let xs = [1, 2, 3, 4, 5, 6];
+ let ys = [1, 2, 3, 7];
+ ::itertools::assert_equal(ZipSlices::new(&xs, &ys), xs.iter().zip(&ys));
+
+ let xs = [1, 2, 3, 4, 5, 6];
+ let mut ys = [0; 6];
+ for (x, y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) {
+ *y = *x;
+ }
+ ::itertools::assert_equal(&xs, &ys);
+}
+
diff --git a/third_party/rust/itertools-0.8.0/benches/tree_fold1.rs b/third_party/rust/itertools-0.8.0/benches/tree_fold1.rs
new file mode 100644
index 0000000000..b71589f3fe
--- /dev/null
+++ b/third_party/rust/itertools-0.8.0/benches/tree_fold1.rs
@@ -0,0 +1,126 @@
+#![feature(test)]
+
+extern crate test;
+extern crate itertools;
+
+use itertools::Itertools;
+use itertools::cloned;
+use test::Bencher;
+
+trait IterEx : Iterator {
+ // Another efficient implementation against which to compare,
+ // but needs `std` so is less desirable.
+ fn tree_fold1_vec<F>(self, mut f: F) -> Option<Self::Item>
+ where F: FnMut(Self::Item, Self::Item) -> Self::Item,
+ Self: Sized,
+ {
+ let hint = self.size_hint().0;
+ let cap = std::mem::size_of::<usize>() * 8 - hint.leading_zeros() as usize;
+ let mut stack = Vec::with_capacity(cap);
+ self.enumerate().foreach(|(mut i, mut x)| {
+ while (i & 1) != 0 {
+ x = f(stack.pop().unwrap(), x);
+ i >>= 1;
+ }
+ stack.push(x);
+ });
+ stack.into_iter().fold1(f)
+ }
+}
+impl<T:Iterator> IterEx for T {}
+
+macro_rules! def_benchs {
+ ($N:expr,
+ $FUN:ident,
+ $BENCH_NAME:ident,
+ ) => (
+ mod $BENCH_NAME {
+ use super::*;
+
+ #[bench]
+ fn sum(b: &mut Bencher) {
+ let v: Vec<u32> = (0.. $N).collect();
+ b.iter(|| {
+ cloned(&v).$FUN(|x, y| x + y)
+ });
+ }
+
+ #[bench]
+ fn complex_iter(b: &mut Bencher) {
+ let u = (3..).take($N / 2);
+ let v = (5..).take($N / 2);
+ let it = u.chain(v);
+
+ b.iter(|| {
+ it.clone().map(|x| x as f32).$FUN(f32::atan2)
+ });
+ }
+
+ #[bench]
+ fn string_format(b: &mut Bencher) {
+ // This goes quadratic with linear `fold1`, so use a smaller
+ // size to not waste too much time in travis. The allocations
+ // in here are so expensive anyway that it'll still take
+ // way longer per iteration than the other two benchmarks.
+ let v: Vec<u32> = (0.. ($N/4)).collect();
+ b.iter(|| {
+ cloned(&v).map(|x| x.to_string()).$FUN(|x, y| format!("{} + {}", x, y))
+ });
+ }
+ }
+ )
+}
+
+def_benchs!{
+ 10_000,
+ fold1,
+ fold1_10k,
+}
+
+def_benchs!{
+ 10_000,
+ tree_fold1,
+ tree_fold1_stack_10k,
+}
+
+def_benchs!{
+ 10_000,
+ tree_fold1_vec,
+ tree_fold1_vec_10k,
+}
+
+def_benchs!{
+ 100,
+ fold1,
+ fold1_100,
+}
+
+def_benchs!{
+ 100,
+ tree_fold1,
+ tree_fold1_stack_100,
+}
+
+def_benchs!{
+ 100,
+ tree_fold1_vec,
+ tree_fold1_vec_100,
+}
+
+def_benchs!{
+ 8,
+ fold1,
+ fold1_08,
+}
+
+def_benchs!{
+ 8,
+ tree_fold1,
+ tree_fold1_stack_08,
+}
+
+def_benchs!{
+ 8,
+ tree_fold1_vec,
+ tree_fold1_vec_08,
+}
diff --git a/third_party/rust/itertools-0.8.0/benches/tuple_combinations.rs b/third_party/rust/itertools-0.8.0/benches/tuple_combinations.rs
new file mode 100644
index 0000000000..4a14b1d0bd
--- /dev/null
+++ b/third_party/rust/itertools-0.8.0/benches/tuple_combinations.rs
@@ -0,0 +1,97 @@
+#![feature(test)]
+
+extern crate test;
+extern crate itertools;
+
+use test::{black_box, Bencher};
+use itertools::Itertools;
+
+// approximate 100_000 iterations for each combination
+const N1: usize = 100_000;
+const N2: usize = 448;
+const N3: usize = 86;
+const N4: usize = 41;
+
+#[bench]
+fn comb_for1(b: &mut Bencher) {
+ b.iter(|| {
+ for i in 0..N1 {
+ black_box(i);
+ }
+ });
+}
+
+#[bench]
+fn comb_for2(b: &mut Bencher) {
+ b.iter(|| {
+ for i in 0..N2 {
+ for j in (i + 1)..N2 {
+ black_box(i + j);
+ }
+ }
+ });
+}
+
+#[bench]
+fn comb_for3(b: &mut Bencher) {
+ b.iter(|| {
+ for i in 0..N3 {
+ for j in (i + 1)..N3 {
+ for k in (j + 1)..N3 {
+ black_box(i + j + k);
+ }
+ }
+ }
+ });
+}
+
+#[bench]
+fn comb_for4(b: &mut Bencher) {
+ b.iter(|| {
+ for i in 0..N4 {
+ for j in (i + 1)..N4 {
+ for k in (j + 1)..N4 {
+ for l in (k + 1)..N4 {
+ black_box(i + j + k + l);
+ }
+ }
+ }
+ }
+ });
+}
+
+#[bench]
+fn comb_c1(b: &mut Bencher) {
+ b.iter(|| {
+ for (i,) in (0..N1).tuple_combinations() {
+ black_box(i);
+ }
+ });
+}
+
+#[bench]
+fn comb_c2(b: &mut Bencher) {
+ b.iter(|| {
+ for (i, j) in (0..N2).tuple_combinations() {
+ black_box(i + j);
+ }
+ });
+}
+
+#[bench]
+fn comb_c3(b: &mut Bencher) {
+ b.iter(|| {
+ for (i, j, k) in (0..N3).tuple_combinations() {
+ black_box(i + j + k);
+ }
+ });
+}
+
+#[bench]
+fn comb_c4(b: &mut Bencher) {
+ b.iter(|| {
+ for (i, j, k, l) in (0..N4).tuple_combinations() {
+ black_box(i + j + k + l);
+ }
+ });
+}
diff --git a/third_party/rust/itertools-0.8.0/benches/tuples.rs b/third_party/rust/itertools-0.8.0/benches/tuples.rs
new file mode 100644
index 0000000000..b0f2990fdf
--- /dev/null
+++ b/third_party/rust/itertools-0.8.0/benches/tuples.rs
@@ -0,0 +1,190 @@
+#![feature(test)]
+
+extern crate test;
+extern crate itertools;
+
+use test::Bencher;
+use itertools::Itertools;
+
+fn s1(a: u32) -> u32 {
+ a
+}
+
+fn s2(a: u32, b: u32) -> u32 {
+ a + b
+}
+
+fn s3(a: u32, b: u32, c: u32) -> u32 {
+ a + b + c
+}
+
+fn s4(a: u32, b: u32, c: u32, d: u32) -> u32 {
+ a + b + c + d
+}
+
+fn sum_s1(s: &[u32]) -> u32 {
+ s1(s[0])
+}
+
+fn sum_s2(s: &[u32]) -> u32 {
+ s2(s[0], s[1])
+}
+
+fn sum_s3(s: &[u32]) -> u32 {
+ s3(s[0], s[1], s[2])
+}
+
+fn sum_s4(s: &[u32]) -> u32 {
+ s4(s[0], s[1], s[2], s[3])
+}
+
+fn sum_t1(s: &(&u32, )) -> u32 {
+ s1(*s.0)
+}
+
+fn sum_t2(s: &(&u32, &u32)) -> u32 {
+ s2(*s.0, *s.1)
+}
+
+fn sum_t3(s: &(&u32, &u32, &u32)) -> u32 {
+ s3(*s.0, *s.1, *s.2)
+}
+
+fn sum_t4(s: &(&u32, &u32, &u32, &u32)) -> u32 {
+ s4(*s.0, *s.1, *s.2, *s.3)
+}
+
+macro_rules! def_benchs {
+ ($N:expr;
+ $TUPLE_FUN:ident,
+ $TUPLES:ident,
+ $TUPLE_WINDOWS:ident;
+ $SLICE_FUN:ident,
+ $CHUNKS:ident,
+ $WINDOWS:ident;
+ $FOR_CHUNKS:ident,
+ $FOR_WINDOWS:ident
+ ) => (
+ #[bench]
+ fn $FOR_CHUNKS(b: &mut Bencher) {
+ let v: Vec<u32> = (0.. $N * 1_000).collect();
+ let mut s = 0;
+ b.iter(|| {
+ let mut j = 0;
+ for _ in 0..1_000 {
+ s += $SLICE_FUN(&v[j..(j + $N)]);
+ j += $N;
+ }
+ s
+ });
+ }
+
+ #[bench]
+ fn $FOR_WINDOWS(b: &mut Bencher) {
+ let v: Vec<u32> = (0..1_000).collect();
+ let mut s = 0;
+ b.iter(|| {
+ for i in 0..(1_000 - $N) {
+ s += $SLICE_FUN(&v[i..(i + $N)]);
+ }
+ s
+ });
+ }
+
+ #[bench]
+ fn $TUPLES(b: &mut Bencher) {
+ let v: Vec<u32> = (0.. $N * 1_000).collect();
+ let mut s = 0;
+ b.iter(|| {
+ for x in v.iter().tuples() {
+ s += $TUPLE_FUN(&x);
+ }
+ s
+ });
+ }
+
+ #[bench]
+ fn $CHUNKS(b: &mut Bencher) {
+ let v: Vec<u32> = (0.. $N * 1_000).collect();
+ let mut s = 0;
+ b.iter(|| {
+ for x in v.chunks($N) {
+ s += $SLICE_FUN(x);
+ }
+ s
+ });
+ }
+
+ #[bench]
+ fn $TUPLE_WINDOWS(b: &mut Bencher) {
+ let v: Vec<u32> = (0..1_000).collect();
+ let mut s = 0;
+ b.iter(|| {
+ for x in v.iter().tuple_windows() {
+ s += $TUPLE_FUN(&x);
+ }
+ s
+ });
+ }
+
+ #[bench]
+ fn $WINDOWS(b: &mut Bencher) {
+ let v: Vec<u32> = (0..1_000).collect();
+ let mut s = 0;
+ b.iter(|| {
+ for x in v.windows($N) {
+ s += $SLICE_FUN(x);
+ }
+ s
+ });
+ }
+ )
+}
+
+def_benchs!{
+ 1;
+ sum_t1,
+ tuple_chunks_1,
+ tuple_windows_1;
+ sum_s1,
+ slice_chunks_1,
+ slice_windows_1;
+ for_chunks_1,
+ for_windows_1
+}
+
+def_benchs!{
+ 2;
+ sum_t2,
+ tuple_chunks_2,
+ tuple_windows_2;
+ sum_s2,
+ slice_chunks_2,
+ slice_windows_2;
+ for_chunks_2,
+ for_windows_2
+}
+
+def_benchs!{
+ 3;
+ sum_t3,
+ tuple_chunks_3,
+ tuple_windows_3;
+ sum_s3,
+ slice_chunks_3,
+ slice_windows_3;
+ for_chunks_3,
+ for_windows_3
+}
+
+def_benchs!{
+ 4;
+ sum_t4,
+ tuple_chunks_4,
+ tuple_windows_4;
+ sum_s4,
+ slice_chunks_4,
+ slice_windows_4;
+ for_chunks_4,
+ for_windows_4
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-09 17:24:44 +0000