library/alloc/benches/vec.rs

   1 use rand::RngCore;
   2 use std::iter::{repeat, FromIterator};
   3 use test::{black_box, Bencher};
   4
   5 #[bench]
   6 fn bench_new(b: &mut Bencher) {
   7     b.iter(|| {
   8         let v: Vec<u32> = Vec::new();
   9         assert_eq!(v.len(), 0);
  10         assert_eq!(v.capacity(), 0);
  11         v
  12     })
  13 }
  14
  15 fn do_bench_with_capacity(b: &mut Bencher, src_len: usize) {
  16     b.bytes = src_len as u64;
  17
  18     b.iter(|| {
  19         let v: Vec<u32> = Vec::with_capacity(src_len);
  20         assert_eq!(v.len(), 0);
  21         assert_eq!(v.capacity(), src_len);
  22         v
  23     })
  24 }
  25
  26 #[bench]
  27 fn bench_with_capacity_0000(b: &mut Bencher) {
  28     do_bench_with_capacity(b, 0)
  29 }
  30
  31 #[bench]
  32 fn bench_with_capacity_0010(b: &mut Bencher) {
  33     do_bench_with_capacity(b, 10)
  34 }
  35
  36 #[bench]
  37 fn bench_with_capacity_0100(b: &mut Bencher) {
  38     do_bench_with_capacity(b, 100)
  39 }
  40
  41 #[bench]
  42 fn bench_with_capacity_1000(b: &mut Bencher) {
  43     do_bench_with_capacity(b, 1000)
  44 }
  45
  46 fn do_bench_from_fn(b: &mut Bencher, src_len: usize) {
  47     b.bytes = src_len as u64;
  48
  49     b.iter(|| {
  50         let dst = (0..src_len).collect::<Vec<_>>();
  51         assert_eq!(dst.len(), src_len);
  52         assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
  53         dst
  54     })
  55 }
  56
  57 #[bench]
  58 fn bench_from_fn_0000(b: &mut Bencher) {
  59     do_bench_from_fn(b, 0)
  60 }
  61
  62 #[bench]
  63 fn bench_from_fn_0010(b: &mut Bencher) {
  64     do_bench_from_fn(b, 10)
  65 }
  66
  67 #[bench]
  68 fn bench_from_fn_0100(b: &mut Bencher) {
  69     do_bench_from_fn(b, 100)
  70 }
  71
  72 #[bench]
  73 fn bench_from_fn_1000(b: &mut Bencher) {
  74     do_bench_from_fn(b, 1000)
  75 }
  76
  77 fn do_bench_from_elem(b: &mut Bencher, src_len: usize) {
  78     b.bytes = src_len as u64;
  79
  80     b.iter(|| {
  81         let dst: Vec<usize> = repeat(5).take(src_len).collect();
  82         assert_eq!(dst.len(), src_len);
  83         assert!(dst.iter().all(|x| *x == 5));
  84         dst
  85     })
  86 }
  87
  88 #[bench]
  89 fn bench_from_elem_0000(b: &mut Bencher) {
  90     do_bench_from_elem(b, 0)
  91 }
  92
  93 #[bench]
  94 fn bench_from_elem_0010(b: &mut Bencher) {
  95     do_bench_from_elem(b, 10)
  96 }
  97
  98 #[bench]
  99 fn bench_from_elem_0100(b: &mut Bencher) {
 100     do_bench_from_elem(b, 100)
 101 }
 102
 103 #[bench]
 104 fn bench_from_elem_1000(b: &mut Bencher) {
 105     do_bench_from_elem(b, 1000)
 106 }
 107
 108 fn do_bench_from_slice(b: &mut Bencher, src_len: usize) {
 109     let src: Vec<_> = FromIterator::from_iter(0..src_len);
 110
 111     b.bytes = src_len as u64;
 112
 113     b.iter(|| {
 114         let dst = src.clone()[..].to_vec();
 115         assert_eq!(dst.len(), src_len);
 116         assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
 117         dst
 118     });
 119 }
 120
 121 #[bench]
 122 fn bench_from_slice_0000(b: &mut Bencher) {
 123     do_bench_from_slice(b, 0)
 124 }
 125
 126 #[bench]
 127 fn bench_from_slice_0010(b: &mut Bencher) {
 128     do_bench_from_slice(b, 10)
 129 }
 130
 131 #[bench]
 132 fn bench_from_slice_0100(b: &mut Bencher) {
 133     do_bench_from_slice(b, 100)
 134 }
 135
 136 #[bench]
 137 fn bench_from_slice_1000(b: &mut Bencher) {
 138     do_bench_from_slice(b, 1000)
 139 }
 140
 141 fn do_bench_from_iter(b: &mut Bencher, src_len: usize) {
 142     let src: Vec<_> = FromIterator::from_iter(0..src_len);
 143
 144     b.bytes = src_len as u64;
 145
 146     b.iter(|| {
 147         let dst: Vec<_> = FromIterator::from_iter(src.clone());
 148         assert_eq!(dst.len(), src_len);
 149         assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
 150         dst
 151     });
 152 }
 153
 154 #[bench]
 155 fn bench_from_iter_0000(b: &mut Bencher) {
 156     do_bench_from_iter(b, 0)
 157 }
 158
 159 #[bench]
 160 fn bench_from_iter_0010(b: &mut Bencher) {
 161     do_bench_from_iter(b, 10)
 162 }
 163
 164 #[bench]
 165 fn bench_from_iter_0100(b: &mut Bencher) {
 166     do_bench_from_iter(b, 100)
 167 }
 168
 169 #[bench]
 170 fn bench_from_iter_1000(b: &mut Bencher) {
 171     do_bench_from_iter(b, 1000)
 172 }
 173
 174 fn do_bench_extend(b: &mut Bencher, dst_len: usize, src_len: usize) {
 175     let dst: Vec<_> = FromIterator::from_iter(0..dst_len);
 176     let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
 177
 178     b.bytes = src_len as u64;
 179
 180     b.iter(|| {
 181         let mut dst = dst.clone();
 182         dst.extend(src.clone());
 183         assert_eq!(dst.len(), dst_len + src_len);
 184         assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
 185         dst
 186     });
 187 }
 188
 189 #[bench]
 190 fn bench_extend_0000_0000(b: &mut Bencher) {
 191     do_bench_extend(b, 0, 0)
 192 }
 193
 194 #[bench]
 195 fn bench_extend_0000_0010(b: &mut Bencher) {
 196     do_bench_extend(b, 0, 10)
 197 }
 198
 199 #[bench]
 200 fn bench_extend_0000_0100(b: &mut Bencher) {
 201     do_bench_extend(b, 0, 100)
 202 }
 203
 204 #[bench]
 205 fn bench_extend_0000_1000(b: &mut Bencher) {
 206     do_bench_extend(b, 0, 1000)
 207 }
 208
 209 #[bench]
 210 fn bench_extend_0010_0010(b: &mut Bencher) {
 211     do_bench_extend(b, 10, 10)
 212 }
 213
 214 #[bench]
 215 fn bench_extend_0100_0100(b: &mut Bencher) {
 216     do_bench_extend(b, 100, 100)
 217 }
 218
 219 #[bench]
 220 fn bench_extend_1000_1000(b: &mut Bencher) {
 221     do_bench_extend(b, 1000, 1000)
 222 }
 223
 224 fn do_bench_extend_from_slice(b: &mut Bencher, dst_len: usize, src_len: usize) {
 225     let dst: Vec<_> = FromIterator::from_iter(0..dst_len);
 226     let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
 227
 228     b.bytes = src_len as u64;
 229
 230     b.iter(|| {
 231         let mut dst = dst.clone();
 232         dst.extend_from_slice(&src);
 233         assert_eq!(dst.len(), dst_len + src_len);
 234         assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
 235         dst
 236     });
 237 }
 238
 239 #[bench]
 240 fn bench_extend_recycle(b: &mut Bencher) {
 241     let mut data = vec![0; 1000];
 242
 243     b.iter(|| {
 244         let tmp = std::mem::take(&mut data);
 245         let mut to_extend = black_box(Vec::new());
 246         to_extend.extend(tmp.into_iter());
 247         data = black_box(to_extend);
 248     });
 249
 250     black_box(data);
 251 }
 252
 253 #[bench]
 254 fn bench_extend_from_slice_0000_0000(b: &mut Bencher) {
 255     do_bench_extend_from_slice(b, 0, 0)
 256 }
 257
 258 #[bench]
 259 fn bench_extend_from_slice_0000_0010(b: &mut Bencher) {
 260     do_bench_extend_from_slice(b, 0, 10)
 261 }
 262
 263 #[bench]
 264 fn bench_extend_from_slice_0000_0100(b: &mut Bencher) {
 265     do_bench_extend_from_slice(b, 0, 100)
 266 }
 267
 268 #[bench]
 269 fn bench_extend_from_slice_0000_1000(b: &mut Bencher) {
 270     do_bench_extend_from_slice(b, 0, 1000)
 271 }
 272
 273 #[bench]
 274 fn bench_extend_from_slice_0010_0010(b: &mut Bencher) {
 275     do_bench_extend_from_slice(b, 10, 10)
 276 }
 277
 278 #[bench]
 279 fn bench_extend_from_slice_0100_0100(b: &mut Bencher) {
 280     do_bench_extend_from_slice(b, 100, 100)
 281 }
 282
 283 #[bench]
 284 fn bench_extend_from_slice_1000_1000(b: &mut Bencher) {
 285     do_bench_extend_from_slice(b, 1000, 1000)
 286 }
 287
 288 fn do_bench_clone(b: &mut Bencher, src_len: usize) {
 289     let src: Vec<usize> = FromIterator::from_iter(0..src_len);
 290
 291     b.bytes = src_len as u64;
 292
 293     b.iter(|| {
 294         let dst = src.clone();
 295         assert_eq!(dst.len(), src_len);
 296         assert!(dst.iter().enumerate().all(|(i, x)| i == *x));
 297         dst
 298     });
 299 }
 300
 301 #[bench]
 302 fn bench_clone_0000(b: &mut Bencher) {
 303     do_bench_clone(b, 0)
 304 }
 305
 306 #[bench]
 307 fn bench_clone_0010(b: &mut Bencher) {
 308     do_bench_clone(b, 10)
 309 }
 310
 311 #[bench]
 312 fn bench_clone_0100(b: &mut Bencher) {
 313     do_bench_clone(b, 100)
 314 }
 315
 316 #[bench]
 317 fn bench_clone_1000(b: &mut Bencher) {
 318     do_bench_clone(b, 1000)
 319 }
 320
 321 fn do_bench_clone_from(b: &mut Bencher, times: usize, dst_len: usize, src_len: usize) {
 322     let dst: Vec<_> = FromIterator::from_iter(0..src_len);
 323     let src: Vec<_> = FromIterator::from_iter(dst_len..dst_len + src_len);
 324
 325     b.bytes = (times * src_len) as u64;
 326
 327     b.iter(|| {
 328         let mut dst = dst.clone();
 329
 330         for _ in 0..times {
 331             dst.clone_from(&src);
 332             assert_eq!(dst.len(), src_len);
 333             assert!(dst.iter().enumerate().all(|(i, x)| dst_len + i == *x));
 334         }
 335         dst
 336     });
 337 }
 338
 339 #[bench]
 340 fn bench_clone_from_01_0000_0000(b: &mut Bencher) {
 341     do_bench_clone_from(b, 1, 0, 0)
 342 }
 343
 344 #[bench]
 345 fn bench_clone_from_01_0000_0010(b: &mut Bencher) {
 346     do_bench_clone_from(b, 1, 0, 10)
 347 }
 348
 349 #[bench]
 350 fn bench_clone_from_01_0000_0100(b: &mut Bencher) {
 351     do_bench_clone_from(b, 1, 0, 100)
 352 }
 353
 354 #[bench]
 355 fn bench_clone_from_01_0000_1000(b: &mut Bencher) {
 356     do_bench_clone_from(b, 1, 0, 1000)
 357 }
 358
 359 #[bench]
 360 fn bench_clone_from_01_0010_0010(b: &mut Bencher) {
 361     do_bench_clone_from(b, 1, 10, 10)
 362 }
 363
 364 #[bench]
 365 fn bench_clone_from_01_0100_0100(b: &mut Bencher) {
 366     do_bench_clone_from(b, 1, 100, 100)
 367 }
 368
 369 #[bench]
 370 fn bench_clone_from_01_1000_1000(b: &mut Bencher) {
 371     do_bench_clone_from(b, 1, 1000, 1000)
 372 }
 373
 374 #[bench]
 375 fn bench_clone_from_01_0010_0100(b: &mut Bencher) {
 376     do_bench_clone_from(b, 1, 10, 100)
 377 }
 378
 379 #[bench]
 380 fn bench_clone_from_01_0100_1000(b: &mut Bencher) {
 381     do_bench_clone_from(b, 1, 100, 1000)
 382 }
 383
 384 #[bench]
 385 fn bench_clone_from_01_0010_0000(b: &mut Bencher) {
 386     do_bench_clone_from(b, 1, 10, 0)
 387 }
 388
 389 #[bench]
 390 fn bench_clone_from_01_0100_0010(b: &mut Bencher) {
 391     do_bench_clone_from(b, 1, 100, 10)
 392 }
 393
 394 #[bench]
 395 fn bench_clone_from_01_1000_0100(b: &mut Bencher) {
 396     do_bench_clone_from(b, 1, 1000, 100)
 397 }
 398
 399 #[bench]
 400 fn bench_clone_from_10_0000_0000(b: &mut Bencher) {
 401     do_bench_clone_from(b, 10, 0, 0)
 402 }
 403
 404 #[bench]
 405 fn bench_clone_from_10_0000_0010(b: &mut Bencher) {
 406     do_bench_clone_from(b, 10, 0, 10)
 407 }
 408
 409 #[bench]
 410 fn bench_clone_from_10_0000_0100(b: &mut Bencher) {
 411     do_bench_clone_from(b, 10, 0, 100)
 412 }
 413
 414 #[bench]
 415 fn bench_clone_from_10_0000_1000(b: &mut Bencher) {
 416     do_bench_clone_from(b, 10, 0, 1000)
 417 }
 418
 419 #[bench]
 420 fn bench_clone_from_10_0010_0010(b: &mut Bencher) {
 421     do_bench_clone_from(b, 10, 10, 10)
 422 }
 423
 424 #[bench]
 425 fn bench_clone_from_10_0100_0100(b: &mut Bencher) {
 426     do_bench_clone_from(b, 10, 100, 100)
 427 }
 428
 429 #[bench]
 430 fn bench_clone_from_10_1000_1000(b: &mut Bencher) {
 431     do_bench_clone_from(b, 10, 1000, 1000)
 432 }
 433
 434 #[bench]
 435 fn bench_clone_from_10_0010_0100(b: &mut Bencher) {
 436     do_bench_clone_from(b, 10, 10, 100)
 437 }
 438
 439 #[bench]
 440 fn bench_clone_from_10_0100_1000(b: &mut Bencher) {
 441     do_bench_clone_from(b, 10, 100, 1000)
 442 }
 443
 444 #[bench]
 445 fn bench_clone_from_10_0010_0000(b: &mut Bencher) {
 446     do_bench_clone_from(b, 10, 10, 0)
 447 }
 448
 449 #[bench]
 450 fn bench_clone_from_10_0100_0010(b: &mut Bencher) {
 451     do_bench_clone_from(b, 10, 100, 10)
 452 }
 453
 454 #[bench]
 455 fn bench_clone_from_10_1000_0100(b: &mut Bencher) {
 456     do_bench_clone_from(b, 10, 1000, 100)
 457 }
 458
 459 macro_rules! bench_in_place {
 460     ($($fname:ident, $type:ty, $count:expr, $init:expr);*) => {
 461         $(
 462             #[bench]
 463             fn $fname(b: &mut Bencher) {
 464                 b.iter(|| {
 465                     let src: Vec<$type> = black_box(vec![$init; $count]);
 466                     let mut sink = src.into_iter()
 467                         .enumerate()
 468                         .map(|(idx, e)| idx as $type ^ e)
 469                         .collect::<Vec<$type>>();
 470                     black_box(sink.as_mut_ptr())
 471                 });
 472             }
 473         )+
 474     };
 475 }
 476
 477 bench_in_place![
 478     bench_in_place_xxu8_0010_i0,   u8,   10, 0;
 479     bench_in_place_xxu8_0100_i0,   u8,  100, 0;
 480     bench_in_place_xxu8_1000_i0,   u8, 1000, 0;
 481     bench_in_place_xxu8_0010_i1,   u8,   10, 1;
 482     bench_in_place_xxu8_0100_i1,   u8,  100, 1;
 483     bench_in_place_xxu8_1000_i1,   u8, 1000, 1;
 484     bench_in_place_xu32_0010_i0,  u32,   10, 0;
 485     bench_in_place_xu32_0100_i0,  u32,  100, 0;
 486     bench_in_place_xu32_1000_i0,  u32, 1000, 0;
 487     bench_in_place_xu32_0010_i1,  u32,   10, 1;
 488     bench_in_place_xu32_0100_i1,  u32,  100, 1;
 489     bench_in_place_xu32_1000_i1,  u32, 1000, 1;
 490     bench_in_place_u128_0010_i0, u128,   10, 0;
 491     bench_in_place_u128_0100_i0, u128,  100, 0;
 492     bench_in_place_u128_1000_i0, u128, 1000, 0;
 493     bench_in_place_u128_0010_i1, u128,   10, 1;
 494     bench_in_place_u128_0100_i1, u128,  100, 1;
 495     bench_in_place_u128_1000_i1, u128, 1000, 1
 496 ];
 497
 498 #[bench]
 499 fn bench_in_place_recycle(b: &mut Bencher) {
 500     let mut data = vec![0; 1000];
 501
 502     b.iter(|| {
 503         let tmp = std::mem::take(&mut data);
 504         data = black_box(
 505             tmp.into_iter()
 506                 .enumerate()
 507                 .map(|(idx, e)| idx.wrapping_add(e))
 508                 .fuse()
 509                 .peekable()
 510                 .collect::<Vec<usize>>(),
 511         );
 512     });
 513 }
 514
 515 #[bench]
 516 fn bench_in_place_zip_recycle(b: &mut Bencher) {
 517     let mut data = vec![0u8; 1000];
 518     let mut rng = rand::thread_rng();
 519     let mut subst = vec![0u8; 1000];
 520     rng.fill_bytes(&mut subst[..]);
 521
 522     b.iter(|| {
 523         let tmp = std::mem::take(&mut data);
 524         let mangled = tmp
 525             .into_iter()
 526             .zip(subst.iter().copied())
 527             .enumerate()
 528             .map(|(i, (d, s))| d.wrapping_add(i as u8) ^ s)
 529             .collect::<Vec<_>>();
 530         assert_eq!(mangled.len(), 1000);
 531         data = black_box(mangled);
 532     });
 533 }
 534
 535 #[bench]
 536 fn bench_in_place_zip_iter_mut(b: &mut Bencher) {
 537     let mut data = vec![0u8; 256];
 538     let mut rng = rand::thread_rng();
 539     let mut subst = vec![0u8; 1000];
 540     rng.fill_bytes(&mut subst[..]);
 541
 542     b.iter(|| {
 543         data.iter_mut().enumerate().for_each(|(i, d)| {
 544             *d = d.wrapping_add(i as u8) ^ subst[i];
 545         });
 546     });
 547
 548     black_box(data);
 549 }
 550
 551 #[derive(Clone)]
 552 struct Droppable(usize);
 553
 554 impl Drop for Droppable {
 555     fn drop(&mut self) {
 556         black_box(self);
 557     }
 558 }
 559
 560 #[bench]
 561 fn bench_in_place_collect_droppable(b: &mut Bencher) {
 562     let v: Vec<Droppable> = std::iter::repeat_with(|| Droppable(0)).take(1000).collect();
 563     b.iter(|| {
 564         v.clone()
 565             .into_iter()
 566             .skip(100)
 567             .enumerate()
 568             .map(|(i, e)| Droppable(i ^ e.0))
 569             .collect::<Vec<_>>()
 570     })
 571 }
 572
 573 const LEN: usize = 16384;
 574
 575 #[bench]
 576 fn bench_chain_collect(b: &mut Bencher) {
 577     let data = black_box([0; LEN]);
 578     b.iter(|| data.iter().cloned().chain([1].iter().cloned()).collect::<Vec<_>>());
 579 }
 580
 581 #[bench]
 582 fn bench_chain_chain_collect(b: &mut Bencher) {
 583     let data = black_box([0; LEN]);
 584     b.iter(|| {
 585         data.iter()
 586             .cloned()
 587             .chain([1].iter().cloned())
 588             .chain([2].iter().cloned())
 589             .collect::<Vec<_>>()
 590     });
 591 }
 592
 593 #[bench]
 594 fn bench_nest_chain_chain_collect(b: &mut Bencher) {
 595     let data = black_box([0; LEN]);
 596     b.iter(|| {
 597         data.iter().cloned().chain([1].iter().chain([2].iter()).cloned()).collect::<Vec<_>>()
 598     });
 599 }
 600
 601 pub fn example_plain_slow(l: &[u32]) -> Vec<u32> {
 602     let mut result = Vec::with_capacity(l.len());
 603     result.extend(l.iter().rev());
 604     result
 605 }
 606
 607 pub fn map_fast(l: &[(u32, u32)]) -> Vec<u32> {
 608     let mut result = Vec::with_capacity(l.len());
 609     for i in 0..l.len() {
 610         unsafe {
 611             *result.get_unchecked_mut(i) = l[i].0;
 612             result.set_len(i);
 613         }
 614     }
 615     result
 616 }
 617
 618 #[bench]
 619 fn bench_range_map_collect(b: &mut Bencher) {
 620     b.iter(|| (0..LEN).map(|_| u32::default()).collect::<Vec<_>>());
 621 }
 622
 623 #[bench]
 624 fn bench_chain_extend_ref(b: &mut Bencher) {
 625     let data = black_box([0; LEN]);
 626     b.iter(|| {
 627         let mut v = Vec::<u32>::with_capacity(data.len() + 1);
 628         v.extend(data.iter().chain([1].iter()));
 629         v
 630     });
 631 }
 632
 633 #[bench]
 634 fn bench_chain_extend_value(b: &mut Bencher) {
 635     let data = black_box([0; LEN]);
 636     b.iter(|| {
 637         let mut v = Vec::<u32>::with_capacity(data.len() + 1);
 638         v.extend(data.iter().cloned().chain(Some(1)));
 639         v
 640     });
 641 }
 642
 643 #[bench]
 644 fn bench_rev_1(b: &mut Bencher) {
 645     let data = black_box([0; LEN]);
 646     b.iter(|| {
 647         let mut v = Vec::<u32>::new();
 648         v.extend(data.iter().rev());
 649         v
 650     });
 651 }
 652
 653 #[bench]
 654 fn bench_rev_2(b: &mut Bencher) {
 655     let data = black_box([0; LEN]);
 656     b.iter(|| example_plain_slow(&data));
 657 }
 658
 659 #[bench]
 660 fn bench_map_regular(b: &mut Bencher) {
 661     let data = black_box([(0, 0); LEN]);
 662     b.iter(|| {
 663         let mut v = Vec::<u32>::new();
 664         v.extend(data.iter().map(|t| t.1));
 665         v
 666     });
 667 }
 668
 669 #[bench]
 670 fn bench_map_fast(b: &mut Bencher) {
 671     let data = black_box([(0, 0); LEN]);
 672     b.iter(|| map_fast(&data));
 673 }