library/alloc/benches/vec.rs

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