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 pub fn vec_cast<T, U>(input: Vec<T>) -> Vec<U> {
 552     input.into_iter().map(|e| unsafe { std::mem::transmute_copy(&e) }).collect()
 553 }
 554
 555 #[bench]
 556 fn bench_transmute(b: &mut Bencher) {
 557     let mut vec = vec![10u32; 100];
 558     b.bytes = 800; // 2 casts x 4 bytes x 100
 559     b.iter(|| {
 560         let v = std::mem::take(&mut vec);
 561         let v = black_box(vec_cast::<u32, i32>(v));
 562         let v = black_box(vec_cast::<i32, u32>(v));
 563         vec = v;
 564     });
 565 }
 566
 567 #[derive(Clone)]
 568 struct Droppable(usize);
 569
 570 impl Drop for Droppable {
 571     fn drop(&mut self) {
 572         black_box(self);
 573     }
 574 }
 575
 576 #[bench]
 577 fn bench_in_place_collect_droppable(b: &mut Bencher) {
 578     let v: Vec<Droppable> = std::iter::repeat_with(|| Droppable(0)).take(1000).collect();
 579     b.iter(|| {
 580         v.clone()
 581             .into_iter()
 582             .skip(100)
 583             .enumerate()
 584             .map(|(i, e)| Droppable(i ^ e.0))
 585             .collect::<Vec<_>>()
 586     })
 587 }
 588
 589 const LEN: usize = 16384;
 590
 591 #[bench]
 592 fn bench_chain_collect(b: &mut Bencher) {
 593     let data = black_box([0; LEN]);
 594     b.iter(|| data.iter().cloned().chain([1].iter().cloned()).collect::<Vec<_>>());
 595 }
 596
 597 #[bench]
 598 fn bench_chain_chain_collect(b: &mut Bencher) {
 599     let data = black_box([0; LEN]);
 600     b.iter(|| {
 601         data.iter()
 602             .cloned()
 603             .chain([1].iter().cloned())
 604             .chain([2].iter().cloned())
 605             .collect::<Vec<_>>()
 606     });
 607 }
 608
 609 #[bench]
 610 fn bench_nest_chain_chain_collect(b: &mut Bencher) {
 611     let data = black_box([0; LEN]);
 612     b.iter(|| {
 613         data.iter().cloned().chain([1].iter().chain([2].iter()).cloned()).collect::<Vec<_>>()
 614     });
 615 }
 616
 617 pub fn example_plain_slow(l: &[u32]) -> Vec<u32> {
 618     let mut result = Vec::with_capacity(l.len());
 619     result.extend(l.iter().rev());
 620     result
 621 }
 622
 623 pub fn map_fast(l: &[(u32, u32)]) -> Vec<u32> {
 624     let mut result = Vec::with_capacity(l.len());
 625     for i in 0..l.len() {
 626         unsafe {
 627             *result.get_unchecked_mut(i) = l[i].0;
 628             result.set_len(i);
 629         }
 630     }
 631     result
 632 }
 633
 634 #[bench]
 635 fn bench_range_map_collect(b: &mut Bencher) {
 636     b.iter(|| (0..LEN).map(|_| u32::default()).collect::<Vec<_>>());
 637 }
 638
 639 #[bench]
 640 fn bench_chain_extend_ref(b: &mut Bencher) {
 641     let data = black_box([0; LEN]);
 642     b.iter(|| {
 643         let mut v = Vec::<u32>::with_capacity(data.len() + 1);
 644         v.extend(data.iter().chain([1].iter()));
 645         v
 646     });
 647 }
 648
 649 #[bench]
 650 fn bench_chain_extend_value(b: &mut Bencher) {
 651     let data = black_box([0; LEN]);
 652     b.iter(|| {
 653         let mut v = Vec::<u32>::with_capacity(data.len() + 1);
 654         v.extend(data.iter().cloned().chain(Some(1)));
 655         v
 656     });
 657 }
 658
 659 #[bench]
 660 fn bench_rev_1(b: &mut Bencher) {
 661     let data = black_box([0; LEN]);
 662     b.iter(|| {
 663         let mut v = Vec::<u32>::new();
 664         v.extend(data.iter().rev());
 665         v
 666     });
 667 }
 668
 669 #[bench]
 670 fn bench_rev_2(b: &mut Bencher) {
 671     let data = black_box([0; LEN]);
 672     b.iter(|| example_plain_slow(&data));
 673 }
 674
 675 #[bench]
 676 fn bench_map_regular(b: &mut Bencher) {
 677     let data = black_box([(0, 0); LEN]);
 678     b.iter(|| {
 679         let mut v = Vec::<u32>::new();
 680         v.extend(data.iter().map(|t| t.1));
 681         v
 682     });
 683 }
 684
 685 #[bench]
 686 fn bench_map_fast(b: &mut Bencher) {
 687     let data = black_box([(0, 0); LEN]);
 688     b.iter(|| map_fast(&data));
 689 }
 690
 691 fn random_sorted_fill(mut seed: u32, buf: &mut [u32]) {
 692     let mask = if buf.len() < 8192 {
 693         0xFF
 694     } else if buf.len() < 200_000 {
 695         0xFFFF
 696     } else {
 697         0xFFFF_FFFF
 698     };
 699
 700     for item in buf.iter_mut() {
 701         seed ^= seed << 13;
 702         seed ^= seed >> 17;
 703         seed ^= seed << 5;
 704
 705         *item = seed & mask;
 706     }
 707
 708     buf.sort();
 709 }
 710
 711 fn bench_vec_dedup_old(b: &mut Bencher, sz: usize) {
 712     let mut template = vec![0u32; sz];
 713     b.bytes = std::mem::size_of_val(template.as_slice()) as u64;
 714     random_sorted_fill(0x43, &mut template);
 715
 716     let mut vec = template.clone();
 717     b.iter(|| {
 718         let len = {
 719             let (dedup, _) = vec.partition_dedup();
 720             dedup.len()
 721         };
 722         vec.truncate(len);
 723
 724         black_box(vec.first());
 725         vec.clear();
 726         vec.extend_from_slice(&template);
 727     });
 728 }
 729
 730 fn bench_vec_dedup_new(b: &mut Bencher, sz: usize) {
 731     let mut template = vec![0u32; sz];
 732     b.bytes = std::mem::size_of_val(template.as_slice()) as u64;
 733     random_sorted_fill(0x43, &mut template);
 734
 735     let mut vec = template.clone();
 736     b.iter(|| {
 737         vec.dedup();
 738         black_box(vec.first());
 739         vec.clear();
 740         vec.extend_from_slice(&template);
 741     });
 742 }
 743
 744 #[bench]
 745 fn bench_dedup_old_100(b: &mut Bencher) {
 746     bench_vec_dedup_old(b, 100);
 747 }
 748 #[bench]
 749 fn bench_dedup_new_100(b: &mut Bencher) {
 750     bench_vec_dedup_new(b, 100);
 751 }
 752
 753 #[bench]
 754 fn bench_dedup_old_1000(b: &mut Bencher) {
 755     bench_vec_dedup_old(b, 1000);
 756 }
 757 #[bench]
 758 fn bench_dedup_new_1000(b: &mut Bencher) {
 759     bench_vec_dedup_new(b, 1000);
 760 }
 761
 762 #[bench]
 763 fn bench_dedup_old_10000(b: &mut Bencher) {
 764     bench_vec_dedup_old(b, 10000);
 765 }
 766 #[bench]
 767 fn bench_dedup_new_10000(b: &mut Bencher) {
 768     bench_vec_dedup_new(b, 10000);
 769 }
 770
 771 #[bench]
 772 fn bench_dedup_old_100000(b: &mut Bencher) {
 773     bench_vec_dedup_old(b, 100000);
 774 }
 775 #[bench]
 776 fn bench_dedup_new_100000(b: &mut Bencher) {
 777     bench_vec_dedup_new(b, 100000);
 778 }