vendor/itertools/benches/bench1.rs

   1 #![feature(test)]
   2
   3 extern crate test;
   4 #[macro_use] extern crate itertools;
   5
   6 use test::{black_box};
   7 use itertools::Itertools;
   8
   9 use itertools::free::cloned;
  10
  11 use std::iter::repeat;
  12 use std::cmp;
  13 use std::ops::Add;
  14
  15 mod extra;
  16
  17 use extra::ZipSlices;
  18
  19 #[bench]
  20 fn slice_iter(b: &mut test::Bencher)
  21 {
  22     let xs: Vec<_> = repeat(1i32).take(20).collect();
  23     b.iter(|| for elt in xs.iter() {
  24         test::black_box(elt);
  25     })
  26 }
  27
  28 #[bench]
  29 fn slice_iter_rev(b: &mut test::Bencher)
  30 {
  31     let xs: Vec<_> = repeat(1i32).take(20).collect();
  32     b.iter(|| for elt in xs.iter().rev() {
  33         test::black_box(elt);
  34     })
  35 }
  36
  37 #[bench]
  38 fn zip_default_zip(b: &mut test::Bencher)
  39 {
  40     let xs = vec![0; 1024];
  41     let ys = vec![0; 768];
  42     let xs = black_box(xs);
  43     let ys = black_box(ys);
  44
  45     b.iter(|| {
  46         for (&x, &y) in xs.iter().zip(&ys) {
  47             test::black_box(x);
  48             test::black_box(y);
  49         }
  50     })
  51 }
  52
  53 #[bench]
  54 fn zipdot_i32_default_zip(b: &mut test::Bencher)
  55 {
  56     let xs = vec![2; 1024];
  57     let ys = vec![2; 768];
  58     let xs = black_box(xs);
  59     let ys = black_box(ys);
  60
  61     b.iter(|| {
  62         let mut s = 0;
  63         for (&x, &y) in xs.iter().zip(&ys) {
  64             s += x * y;
  65         }
  66         s
  67     })
  68 }
  69
  70 #[bench]
  71 fn zipdot_f32_default_zip(b: &mut test::Bencher)
  72 {
  73     let xs = vec![2f32; 1024];
  74     let ys = vec![2f32; 768];
  75     let xs = black_box(xs);
  76     let ys = black_box(ys);
  77
  78     b.iter(|| {
  79         let mut s = 0.;
  80         for (&x, &y) in xs.iter().zip(&ys) {
  81             s += x * y;
  82         }
  83         s
  84     })
  85 }
  86
  87 #[bench]
  88 fn zip_default_zip3(b: &mut test::Bencher)
  89 {
  90     let xs = vec![0; 1024];
  91     let ys = vec![0; 768];
  92     let zs = vec![0; 766];
  93     let xs = black_box(xs);
  94     let ys = black_box(ys);
  95     let zs = black_box(zs);
  96
  97     b.iter(|| {
  98         for ((&x, &y), &z) in xs.iter().zip(&ys).zip(&zs) {
  99             test::black_box(x);
 100             test::black_box(y);
 101             test::black_box(z);
 102         }
 103     })
 104 }
 105
 106 #[bench]
 107 fn zip_slices_ziptuple(b: &mut test::Bencher)
 108 {
 109     let xs = vec![0; 1024];
 110     let ys = vec![0; 768];
 111
 112     b.iter(|| {
 113         let xs = black_box(&xs);
 114         let ys = black_box(&ys);
 115         for (&x, &y) in itertools::multizip((xs, ys)) {
 116             test::black_box(x);
 117             test::black_box(y);
 118         }
 119     })
 120 }
 121
 122 #[bench]
 123 fn zipslices(b: &mut test::Bencher)
 124 {
 125     let xs = vec![0; 1024];
 126     let ys = vec![0; 768];
 127     let xs = black_box(xs);
 128     let ys = black_box(ys);
 129
 130     b.iter(|| {
 131         for (&x, &y) in ZipSlices::new(&xs, &ys) {
 132             test::black_box(x);
 133             test::black_box(y);
 134         }
 135     })
 136 }
 137
 138 #[bench]
 139 fn zipslices_mut(b: &mut test::Bencher)
 140 {
 141     let xs = vec![0; 1024];
 142     let ys = vec![0; 768];
 143     let xs = black_box(xs);
 144     let mut ys = black_box(ys);
 145
 146     b.iter(|| {
 147         for (&x, &mut y) in ZipSlices::from_slices(&xs[..], &mut ys[..]) {
 148             test::black_box(x);
 149             test::black_box(y);
 150         }
 151     })
 152 }
 153
 154 #[bench]
 155 fn zipdot_i32_zipslices(b: &mut test::Bencher)
 156 {
 157     let xs = vec![2; 1024];
 158     let ys = vec![2; 768];
 159     let xs = black_box(xs);
 160     let ys = black_box(ys);
 161
 162     b.iter(|| {
 163         let mut s = 0i32;
 164         for (&x, &y) in ZipSlices::new(&xs, &ys) {
 165             s += x * y;
 166         }
 167         s
 168     })
 169 }
 170
 171 #[bench]
 172 fn zipdot_f32_zipslices(b: &mut test::Bencher)
 173 {
 174     let xs = vec![2f32; 1024];
 175     let ys = vec![2f32; 768];
 176     let xs = black_box(xs);
 177     let ys = black_box(ys);
 178
 179     b.iter(|| {
 180         let mut s = 0.;
 181         for (&x, &y) in ZipSlices::new(&xs, &ys) {
 182             s += x * y;
 183         }
 184         s
 185     })
 186 }
 187
 188
 189 #[bench]
 190 fn zip_checked_counted_loop(b: &mut test::Bencher)
 191 {
 192     let xs = vec![0; 1024];
 193     let ys = vec![0; 768];
 194     let xs = black_box(xs);
 195     let ys = black_box(ys);
 196
 197     b.iter(|| {
 198         // Must slice to equal lengths, and then bounds checks are eliminated!
 199         let len = cmp::min(xs.len(), ys.len());
 200         let xs = &xs[..len];
 201         let ys = &ys[..len];
 202
 203         for i in 0..len {
 204             let x = xs[i];
 205             let y = ys[i];
 206             test::black_box(x);
 207             test::black_box(y);
 208         }
 209     })
 210 }
 211
 212 #[bench]
 213 fn zipdot_i32_checked_counted_loop(b: &mut test::Bencher)
 214 {
 215     let xs = vec![2; 1024];
 216     let ys = vec![2; 768];
 217     let xs = black_box(xs);
 218     let ys = black_box(ys);
 219
 220     b.iter(|| {
 221         // Must slice to equal lengths, and then bounds checks are eliminated!
 222         let len = cmp::min(xs.len(), ys.len());
 223         let xs = &xs[..len];
 224         let ys = &ys[..len];
 225
 226         let mut s = 0i32;
 227
 228         for i in 0..len {
 229             s += xs[i] * ys[i];
 230         }
 231         s
 232     })
 233 }
 234
 235 #[bench]
 236 fn zipdot_f32_checked_counted_loop(b: &mut test::Bencher)
 237 {
 238     let xs = vec![2f32; 1024];
 239     let ys = vec![2f32; 768];
 240     let xs = black_box(xs);
 241     let ys = black_box(ys);
 242
 243     b.iter(|| {
 244         // Must slice to equal lengths, and then bounds checks are eliminated!
 245         let len = cmp::min(xs.len(), ys.len());
 246         let xs = &xs[..len];
 247         let ys = &ys[..len];
 248
 249         let mut s = 0.;
 250
 251         for i in 0..len {
 252             s += xs[i] * ys[i];
 253         }
 254         s
 255     })
 256 }
 257
 258 #[bench]
 259 fn zipdot_f32_checked_counted_unrolled_loop(b: &mut test::Bencher)
 260 {
 261     let xs = vec![2f32; 1024];
 262     let ys = vec![2f32; 768];
 263     let xs = black_box(xs);
 264     let ys = black_box(ys);
 265
 266     b.iter(|| {
 267         // Must slice to equal lengths, and then bounds checks are eliminated!
 268         let len = cmp::min(xs.len(), ys.len());
 269         let mut xs = &xs[..len];
 270         let mut ys = &ys[..len];
 271
 272         let mut s = 0.;
 273         let (mut p0, mut p1, mut p2, mut p3, mut p4, mut p5, mut p6, mut p7) =
 274             (0., 0., 0., 0., 0., 0., 0., 0.);
 275
 276         // how to unroll and have bounds checks eliminated (by cristicbz)
 277         // split sum into eight parts to enable vectorization (by bluss)
 278         while xs.len() >= 8 {
 279             p0 += xs[0] * ys[0];
 280             p1 += xs[1] * ys[1];
 281             p2 += xs[2] * ys[2];
 282             p3 += xs[3] * ys[3];
 283             p4 += xs[4] * ys[4];
 284             p5 += xs[5] * ys[5];
 285             p6 += xs[6] * ys[6];
 286             p7 += xs[7] * ys[7];
 287
 288             xs = &xs[8..];
 289             ys = &ys[8..];
 290         }
 291         s += p0 + p4;
 292         s += p1 + p5;
 293         s += p2 + p6;
 294         s += p3 + p7;
 295
 296         for i in 0..xs.len() {
 297             s += xs[i] * ys[i];
 298         }
 299         s
 300     })
 301 }
 302
 303 #[bench]
 304 fn zip_unchecked_counted_loop(b: &mut test::Bencher)
 305 {
 306     let xs = vec![0; 1024];
 307     let ys = vec![0; 768];
 308     let xs = black_box(xs);
 309     let ys = black_box(ys);
 310
 311     b.iter(|| {
 312         let len = cmp::min(xs.len(), ys.len());
 313         for i in 0..len {
 314             unsafe {
 315             let x = *xs.get_unchecked(i);
 316             let y = *ys.get_unchecked(i);
 317             test::black_box(x);
 318             test::black_box(y);
 319             }
 320         }
 321     })
 322 }
 323
 324 #[bench]
 325 fn zipdot_i32_unchecked_counted_loop(b: &mut test::Bencher)
 326 {
 327     let xs = vec![2; 1024];
 328     let ys = vec![2; 768];
 329     let xs = black_box(xs);
 330     let ys = black_box(ys);
 331
 332     b.iter(|| {
 333         let len = cmp::min(xs.len(), ys.len());
 334         let mut s = 0i32;
 335         for i in 0..len {
 336             unsafe {
 337             let x = *xs.get_unchecked(i);
 338             let y = *ys.get_unchecked(i);
 339             s += x * y;
 340             }
 341         }
 342         s
 343     })
 344 }
 345
 346 #[bench]
 347 fn zipdot_f32_unchecked_counted_loop(b: &mut test::Bencher)
 348 {
 349     let xs = vec![2.; 1024];
 350     let ys = vec![2.; 768];
 351     let xs = black_box(xs);
 352     let ys = black_box(ys);
 353
 354     b.iter(|| {
 355         let len = cmp::min(xs.len(), ys.len());
 356         let mut s = 0f32;
 357         for i in 0..len {
 358             unsafe {
 359             let x = *xs.get_unchecked(i);
 360             let y = *ys.get_unchecked(i);
 361             s += x * y;
 362             }
 363         }
 364         s
 365     })
 366 }
 367
 368 #[bench]
 369 fn zip_unchecked_counted_loop3(b: &mut test::Bencher)
 370 {
 371     let xs = vec![0; 1024];
 372     let ys = vec![0; 768];
 373     let zs = vec![0; 766];
 374     let xs = black_box(xs);
 375     let ys = black_box(ys);
 376     let zs = black_box(zs);
 377
 378     b.iter(|| {
 379         let len = cmp::min(xs.len(), cmp::min(ys.len(), zs.len()));
 380         for i in 0..len {
 381             unsafe {
 382             let x = *xs.get_unchecked(i);
 383             let y = *ys.get_unchecked(i);
 384             let z = *zs.get_unchecked(i);
 385             test::black_box(x);
 386             test::black_box(y);
 387             test::black_box(z);
 388             }
 389         }
 390     })
 391 }
 392
 393 #[bench]
 394 fn group_by_lazy_1(b: &mut test::Bencher) {
 395     let mut data = vec![0; 1024];
 396     for (index, elt) in data.iter_mut().enumerate() {
 397         *elt = index / 10;
 398     }
 399
 400     let data = test::black_box(data);
 401
 402     b.iter(|| {
 403         for (_key, group) in &data.iter().group_by(|elt| **elt) {
 404             for elt in group {
 405                 test::black_box(elt);
 406             }
 407         }
 408     })
 409 }
 410
 411 #[bench]
 412 fn group_by_lazy_2(b: &mut test::Bencher) {
 413     let mut data = vec![0; 1024];
 414     for (index, elt) in data.iter_mut().enumerate() {
 415         *elt = index / 2;
 416     }
 417
 418     let data = test::black_box(data);
 419
 420     b.iter(|| {
 421         for (_key, group) in &data.iter().group_by(|elt| **elt) {
 422             for elt in group {
 423                 test::black_box(elt);
 424             }
 425         }
 426     })
 427 }
 428
 429 #[bench]
 430 fn slice_chunks(b: &mut test::Bencher) {
 431     let data = vec![0; 1024];
 432
 433     let data = test::black_box(data);
 434     let sz = test::black_box(10);
 435
 436     b.iter(|| {
 437         for group in data.chunks(sz) {
 438             for elt in group {
 439                 test::black_box(elt);
 440             }
 441         }
 442     })
 443 }
 444
 445 #[bench]
 446 fn chunks_lazy_1(b: &mut test::Bencher) {
 447     let data = vec![0; 1024];
 448
 449     let data = test::black_box(data);
 450     let sz = test::black_box(10);
 451
 452     b.iter(|| {
 453         for group in &data.iter().chunks(sz) {
 454             for elt in group {
 455                 test::black_box(elt);
 456             }
 457         }
 458     })
 459 }
 460
 461 #[bench]
 462 fn equal(b: &mut test::Bencher) {
 463     let data = vec![7; 1024];
 464     let l = data.len();
 465     let alpha = test::black_box(&data[1..]);
 466     let beta = test::black_box(&data[..l - 1]);
 467     b.iter(|| {
 468         itertools::equal(alpha, beta)
 469     })
 470 }
 471
 472 #[bench]
 473 fn merge_default(b: &mut test::Bencher) {
 474     let mut data1 = vec![0; 1024];
 475     let mut data2 = vec![0; 800];
 476     let mut x = 0;
 477     for (_, elt) in data1.iter_mut().enumerate() {
 478         *elt = x;
 479         x += 1;
 480     }
 481
 482     let mut y = 0;
 483     for (i, elt) in data2.iter_mut().enumerate() {
 484         *elt += y;
 485         if i % 3 == 0 {
 486             y += 3;
 487         } else {
 488             y += 0;
 489         }
 490     }
 491     let data1 = test::black_box(data1);
 492     let data2 = test::black_box(data2);
 493     b.iter(|| {
 494         data1.iter().merge(&data2).count()
 495     })
 496 }
 497
 498 #[bench]
 499 fn merge_by_cmp(b: &mut test::Bencher) {
 500     let mut data1 = vec![0; 1024];
 501     let mut data2 = vec![0; 800];
 502     let mut x = 0;
 503     for (_, elt) in data1.iter_mut().enumerate() {
 504         *elt = x;
 505         x += 1;
 506     }
 507
 508     let mut y = 0;
 509     for (i, elt) in data2.iter_mut().enumerate() {
 510         *elt += y;
 511         if i % 3 == 0 {
 512             y += 3;
 513         } else {
 514             y += 0;
 515         }
 516     }
 517     let data1 = test::black_box(data1);
 518     let data2 = test::black_box(data2);
 519     b.iter(|| {
 520         data1.iter().merge_by(&data2, PartialOrd::le).count()
 521     })
 522 }
 523
 524 #[bench]
 525 fn merge_by_lt(b: &mut test::Bencher) {
 526     let mut data1 = vec![0; 1024];
 527     let mut data2 = vec![0; 800];
 528     let mut x = 0;
 529     for (_, elt) in data1.iter_mut().enumerate() {
 530         *elt = x;
 531         x += 1;
 532     }
 533
 534     let mut y = 0;
 535     for (i, elt) in data2.iter_mut().enumerate() {
 536         *elt += y;
 537         if i % 3 == 0 {
 538             y += 3;
 539         } else {
 540             y += 0;
 541         }
 542     }
 543     let data1 = test::black_box(data1);
 544     let data2 = test::black_box(data2);
 545     b.iter(|| {
 546         data1.iter().merge_by(&data2, |a, b| a <= b).count()
 547     })
 548 }
 549
 550 #[bench]
 551 fn kmerge_default(b: &mut test::Bencher) {
 552     let mut data1 = vec![0; 1024];
 553     let mut data2 = vec![0; 800];
 554     let mut x = 0;
 555     for (_, elt) in data1.iter_mut().enumerate() {
 556         *elt = x;
 557         x += 1;
 558     }
 559
 560     let mut y = 0;
 561     for (i, elt) in data2.iter_mut().enumerate() {
 562         *elt += y;
 563         if i % 3 == 0 {
 564             y += 3;
 565         } else {
 566             y += 0;
 567         }
 568     }
 569     let data1 = test::black_box(data1);
 570     let data2 = test::black_box(data2);
 571     let its = &[data1.iter(), data2.iter()];
 572     b.iter(|| {
 573         its.iter().cloned().kmerge().count()
 574     })
 575 }
 576
 577 #[bench]
 578 fn kmerge_tenway(b: &mut test::Bencher) {
 579     let mut data = vec![0; 10240];
 580
 581     let mut state = 1729u16;
 582     fn rng(state: &mut u16) -> u16 {
 583         let new = state.wrapping_mul(31421) + 6927;
 584         *state = new;
 585         new
 586     }
 587
 588     for elt in &mut data {
 589         *elt = rng(&mut state);
 590     }
 591
 592     let mut chunks = Vec::new();
 593     let mut rest = &mut data[..];
 594     while rest.len() > 0 {
 595         let chunk_len = 1 + rng(&mut state) % 512;
 596         let chunk_len = cmp::min(rest.len(), chunk_len as usize);
 597         let (fst, tail) = {rest}.split_at_mut(chunk_len);
 598         fst.sort();
 599         chunks.push(fst.iter().cloned());
 600         rest = tail;
 601     }
 602
 603     // println!("Chunk lengths: {}", chunks.iter().format_with(", ", |elt, f| f(&elt.len())));
 604
 605     b.iter(|| {
 606         chunks.iter().cloned().kmerge().count()
 607     })
 608 }
 609
 610
 611 fn fast_integer_sum<I>(iter: I) -> I::Item
 612     where I: IntoIterator,
 613           I::Item: Default + Add<Output=I::Item>
 614 {
 615     iter.into_iter().fold(<_>::default(), |x, y| x + y)
 616 }
 617
 618
 619 #[bench]
 620 fn step_vec_2(b: &mut test::Bencher) {
 621     let v = vec![0; 1024];
 622     b.iter(|| {
 623         fast_integer_sum(cloned(v.iter().step(2)))
 624     });
 625 }
 626
 627 #[bench]
 628 fn step_vec_10(b: &mut test::Bencher) {
 629     let v = vec![0; 1024];
 630     b.iter(|| {
 631         fast_integer_sum(cloned(v.iter().step(10)))
 632     });
 633 }
 634
 635 #[bench]
 636 fn step_range_2(b: &mut test::Bencher) {
 637     let v = black_box(0..1024);
 638     b.iter(|| {
 639         fast_integer_sum(v.clone().step(2))
 640     });
 641 }
 642
 643 #[bench]
 644 fn step_range_10(b: &mut test::Bencher) {
 645     let v = black_box(0..1024);
 646     b.iter(|| {
 647         fast_integer_sum(v.clone().step(10))
 648     });
 649 }
 650
 651 #[bench]
 652 fn cartesian_product_iterator(b: &mut test::Bencher)
 653 {
 654     let xs = vec![0; 16];
 655
 656     b.iter(|| {
 657         let mut sum = 0;
 658         for (&x, &y, &z) in iproduct!(&xs, &xs, &xs) {
 659             sum += x;
 660             sum += y;
 661             sum += z;
 662         }
 663         sum
 664     })
 665 }
 666
 667 #[bench]
 668 fn cartesian_product_fold(b: &mut test::Bencher)
 669 {
 670     let xs = vec![0; 16];
 671
 672     b.iter(|| {
 673         let mut sum = 0;
 674         iproduct!(&xs, &xs, &xs).fold((), |(), (&x, &y, &z)| {
 675             sum += x;
 676             sum += y;
 677             sum += z;
 678         });
 679         sum
 680     })
 681 }
 682
 683 #[bench]
 684 fn multi_cartesian_product_iterator(b: &mut test::Bencher)
 685 {
 686     let xs = [vec![0; 16], vec![0; 16], vec![0; 16]];
 687
 688     b.iter(|| {
 689         let mut sum = 0;
 690         for x in xs.into_iter().multi_cartesian_product() {
 691             sum += x[0];
 692             sum += x[1];
 693             sum += x[2];
 694         }
 695         sum
 696     })
 697 }
 698
 699 #[bench]
 700 fn multi_cartesian_product_fold(b: &mut test::Bencher)
 701 {
 702     let xs = [vec![0; 16], vec![0; 16], vec![0; 16]];
 703
 704     b.iter(|| {
 705         let mut sum = 0;
 706         xs.into_iter().multi_cartesian_product().fold((), |(), x| {
 707             sum += x[0];
 708             sum += x[1];
 709             sum += x[2];
 710         });
 711         sum
 712     })
 713 }
 714
 715 #[bench]
 716 fn cartesian_product_nested_for(b: &mut test::Bencher)
 717 {
 718     let xs = vec![0; 16];
 719
 720     b.iter(|| {
 721         let mut sum = 0;
 722         for &x in &xs {
 723             for &y in &xs {
 724                 for &z in &xs {
 725                     sum += x;
 726                     sum += y;
 727                     sum += z;
 728                 }
 729             }
 730         }
 731         sum
 732     })
 733 }