diff options
Diffstat (limited to 'src/libcollections')
| -rw-r--r-- | src/libcollections/vec.rs | 525 |
1 files changed, 448 insertions, 77 deletions
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs index 6e2dc95cfd6..1e96588dac5 100644 --- a/src/libcollections/vec.rs +++ b/src/libcollections/vec.rs @@ -205,7 +205,9 @@ impl<T: Clone> Vec<T> { /// ``` #[inline] pub fn from_slice(values: &[T]) -> Vec<T> { - values.iter().map(|x| x.clone()).collect() + let mut vector = Vec::new(); + vector.push_all(values); + vector } /// Constructs a `Vec` with copies of a value. @@ -246,7 +248,21 @@ impl<T: Clone> Vec<T> { /// ``` #[inline] pub fn push_all(&mut self, other: &[T]) { - self.extend(other.iter().map(|e| e.clone())); + self.reserve_additional(other.len()); + + for i in range(0, other.len()) { + let len = self.len(); + + // Unsafe code so this can be optimised to a memcpy (or something similarly + // fast) when T is Copy. LLVM is easily confused, so any extra operations + // during the loop can prevent this optimisation. + unsafe { + ptr::write( + self.as_mut_slice().unsafe_mut_ref(len), + other.unsafe_ref(i).clone()); + self.set_len(len + 1); + } + } } /// Grows the `Vec` in-place. @@ -326,24 +342,7 @@ impl<T: Clone> Vec<T> { #[unstable] impl<T:Clone> Clone for Vec<T> { fn clone(&self) -> Vec<T> { - let len = self.len; - let mut vector = Vec::with_capacity(len); - // Unsafe code so this can be optimised to a memcpy (or something - // similarly fast) when T is Copy. LLVM is easily confused, so any - // extra operations during the loop can prevent this optimisation - { - let this_slice = self.as_slice(); - while vector.len < len { - unsafe { - let len = vector.len; - ptr::write( - vector.as_mut_slice().unsafe_mut_ref(len), - this_slice.unsafe_ref(len).clone()); - } - vector.len += 1; - } - } - vector + Vec::from_slice(self.as_slice()) } fn clone_from(&mut self, other: &Vec<T>) { @@ -359,8 +358,8 @@ impl<T:Clone> Clone for Vec<T> { // self.len <= other.len due to the truncate above, so the // slice here is always in-bounds. - let len = self.len(); - self.extend(other.slice_from(len).iter().map(|x| x.clone())); + let slice = other.slice_from(self.len()); + self.push_all(slice); } } @@ -1550,7 +1549,6 @@ pub mod raw { } } - #[cfg(test)] mod tests { extern crate test; @@ -1852,107 +1850,480 @@ mod tests { #[bench] fn bench_new(b: &mut Bencher) { b.iter(|| { - let v: Vec<int> = Vec::new(); + let v: Vec<uint> = Vec::new(); + assert_eq!(v.len(), 0); assert_eq!(v.capacity(), 0); - assert!(v.as_slice() == []); }) } - #[bench] - fn bench_with_capacity_0(b: &mut Bencher) { + fn do_bench_with_capacity(b: &mut Bencher, src_len: uint) { + b.bytes = src_len as u64; + b.iter(|| { - let v: Vec<int> = Vec::with_capacity(0); - assert_eq!(v.capacity(), 0); - assert!(v.as_slice() == []); + let v: Vec<uint> = Vec::with_capacity(src_len); + assert_eq!(v.len(), 0); + assert_eq!(v.capacity(), src_len); }) } + #[bench] + fn bench_with_capacity_0000(b: &mut Bencher) { + do_bench_with_capacity(b, 0) + } #[bench] - fn bench_with_capacity_5(b: &mut Bencher) { - b.iter(|| { - let v: Vec<int> = Vec::with_capacity(5); - assert_eq!(v.capacity(), 5); - assert!(v.as_slice() == []); - }) + fn bench_with_capacity_0010(b: &mut Bencher) { + do_bench_with_capacity(b, 10) } #[bench] - fn bench_with_capacity_100(b: &mut Bencher) { + fn bench_with_capacity_0100(b: &mut Bencher) { + do_bench_with_capacity(b, 100) + } + + #[bench] + fn bench_with_capacity_1000(b: &mut Bencher) { + do_bench_with_capacity(b, 1000) + } + + fn do_bench_from_fn(b: &mut Bencher, src_len: uint) { + b.bytes = src_len as u64; + b.iter(|| { - let v: Vec<int> = Vec::with_capacity(100); - assert_eq!(v.capacity(), 100); - assert!(v.as_slice() == []); + let dst = Vec::from_fn(src_len, |i| i); + assert_eq!(dst.len(), src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); }) } #[bench] - fn bench_from_fn_0(b: &mut Bencher) { + fn bench_from_fn_0000(b: &mut Bencher) { + do_bench_from_fn(b, 0) + } + + #[bench] + fn bench_from_fn_0010(b: &mut Bencher) { + do_bench_from_fn(b, 10) + } + + #[bench] + fn bench_from_fn_0100(b: &mut Bencher) { + do_bench_from_fn(b, 100) + } + + #[bench] + fn bench_from_fn_1000(b: &mut Bencher) { + do_bench_from_fn(b, 1000) + } + + fn do_bench_from_elem(b: &mut Bencher, src_len: uint) { + b.bytes = src_len as u64; + b.iter(|| { - let v: Vec<int> = Vec::from_fn(0, |_| 5); - assert!(v.as_slice() == []); + let dst: Vec<uint> = Vec::from_elem(src_len, 5); + assert_eq!(dst.len(), src_len); + assert!(dst.iter().all(|x| *x == 5)); }) } #[bench] - fn bench_from_fn_5(b: &mut Bencher) { + fn bench_from_elem_0000(b: &mut Bencher) { + do_bench_from_elem(b, 0) + } + + #[bench] + fn bench_from_elem_0010(b: &mut Bencher) { + do_bench_from_elem(b, 10) + } + + #[bench] + fn bench_from_elem_0100(b: &mut Bencher) { + do_bench_from_elem(b, 100) + } + + #[bench] + fn bench_from_elem_1000(b: &mut Bencher) { + do_bench_from_elem(b, 1000) + } + + fn do_bench_from_slice(b: &mut Bencher, src_len: uint) { + let src: Vec<uint> = FromIterator::from_iter(range(0, src_len)); + + b.bytes = src_len as u64; + b.iter(|| { - let v: Vec<int> = Vec::from_fn(5, |_| 5); - assert!(v.as_slice() == [5, 5, 5, 5, 5]); - }) + let dst = Vec::from_slice(src.clone().as_slice()); + assert_eq!(dst.len(), src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); + }); + } + + #[bench] + fn bench_from_slice_0000(b: &mut Bencher) { + do_bench_from_slice(b, 0) + } + + #[bench] + fn bench_from_slice_0010(b: &mut Bencher) { + do_bench_from_slice(b, 10) + } + + #[bench] + fn bench_from_slice_0100(b: &mut Bencher) { + do_bench_from_slice(b, 100) } #[bench] - fn bench_from_slice_0(b: &mut Bencher) { + fn bench_from_slice_1000(b: &mut Bencher) { + do_bench_from_slice(b, 1000) + } + + fn do_bench_from_iter(b: &mut Bencher, src_len: uint) { + let src: Vec<uint> = FromIterator::from_iter(range(0, src_len)); + + b.bytes = src_len as u64; + b.iter(|| { - let v: Vec<int> = Vec::from_slice([]); - assert!(v.as_slice() == []); - }) + let dst: Vec<uint> = FromIterator::from_iter(src.clone().move_iter()); + assert_eq!(dst.len(), src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); + }); + } + + #[bench] + fn bench_from_iter_0000(b: &mut Bencher) { + do_bench_from_iter(b, 0) + } + + #[bench] + fn bench_from_iter_0010(b: &mut Bencher) { + do_bench_from_iter(b, 10) + } + + #[bench] + fn bench_from_iter_0100(b: &mut Bencher) { + do_bench_from_iter(b, 100) } #[bench] - fn bench_from_slice_5(b: &mut Bencher) { + fn bench_from_iter_1000(b: &mut Bencher) { + do_bench_from_iter(b, 1000) + } + + fn do_bench_extend(b: &mut Bencher, dst_len: uint, src_len: uint) { + let dst: Vec<uint> = FromIterator::from_iter(range(0, dst_len)); + let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len)); + + b.bytes = src_len as u64; + b.iter(|| { - let v: Vec<int> = Vec::from_slice([1i, 2, 3, 4, 5]); - assert!(v.as_slice() == [1, 2, 3, 4, 5]); - }) + let mut dst = dst.clone(); + dst.extend(src.clone().move_iter()); + assert_eq!(dst.len(), dst_len + src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); + }); + } + + #[bench] + fn bench_extend_0000_0000(b: &mut Bencher) { + do_bench_extend(b, 0, 0) + } + + #[bench] + fn bench_extend_0000_0010(b: &mut Bencher) { + do_bench_extend(b, 0, 10) + } + + #[bench] + fn bench_extend_0000_0100(b: &mut Bencher) { + do_bench_extend(b, 0, 100) } #[bench] - fn bench_from_iter_0(b: &mut Bencher) { + fn bench_extend_0000_1000(b: &mut Bencher) { + do_bench_extend(b, 0, 1000) + } + + #[bench] + fn bench_extend_0010_0010(b: &mut Bencher) { + do_bench_extend(b, 10, 10) + } + + #[bench] + fn bench_extend_0100_0100(b: &mut Bencher) { + do_bench_extend(b, 100, 100) + } + + #[bench] + fn bench_extend_1000_1000(b: &mut Bencher) { + do_bench_extend(b, 1000, 1000) + } + + fn do_bench_push_all(b: &mut Bencher, dst_len: uint, src_len: uint) { + let dst: Vec<uint> = FromIterator::from_iter(range(0, dst_len)); + let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len)); + + b.bytes = src_len as u64; + b.iter(|| { - let v0: Vec<int> = vec!(); - let v1: Vec<int> = FromIterator::from_iter(v0.move_iter()); - assert!(v1.as_slice() == []); - }) + let mut dst = dst.clone(); + dst.push_all(src.as_slice()); + assert_eq!(dst.len(), dst_len + src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); + }); + } + + #[bench] + fn bench_push_all_0000_0000(b: &mut Bencher) { + do_bench_push_all(b, 0, 0) + } + + #[bench] + fn bench_push_all_0000_0010(b: &mut Bencher) { + do_bench_push_all(b, 0, 10) + } + + #[bench] + fn bench_push_all_0000_0100(b: &mut Bencher) { + do_bench_push_all(b, 0, 100) } #[bench] - fn bench_from_iter_5(b: &mut Bencher) { + fn bench_push_all_0000_1000(b: &mut Bencher) { + do_bench_push_all(b, 0, 1000) + } + + #[bench] + fn bench_push_all_0010_0010(b: &mut Bencher) { + do_bench_push_all(b, 10, 10) + } + + #[bench] + fn bench_push_all_0100_0100(b: &mut Bencher) { + do_bench_push_all(b, 100, 100) + } + + #[bench] + fn bench_push_all_1000_1000(b: &mut Bencher) { + do_bench_push_all(b, 1000, 1000) + } + + fn do_bench_push_all_move(b: &mut Bencher, dst_len: uint, src_len: uint) { + let dst: Vec<uint> = FromIterator::from_iter(range(0u, dst_len)); + let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len)); + + b.bytes = src_len as u64; + b.iter(|| { - let v0: Vec<int> = vec!(1, 2, 3, 4, 5); - let v1: Vec<int> = FromIterator::from_iter(v0.move_iter()); - assert!(v1.as_slice() == [1, 2, 3, 4, 5]); - }) + let mut dst = dst.clone(); + dst.push_all_move(src.clone()); + assert_eq!(dst.len(), dst_len + src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); + }); + } + + #[bench] + fn bench_push_all_move_0000_0000(b: &mut Bencher) { + do_bench_push_all_move(b, 0, 0) + } + + #[bench] + fn bench_push_all_move_0000_0010(b: &mut Bencher) { + do_bench_push_all_move(b, 0, 10) + } + + #[bench] + fn bench_push_all_move_0000_0100(b: &mut Bencher) { + do_bench_push_all_move(b, 0, 100) + } + + #[bench] + fn bench_push_all_move_0000_1000(b: &mut Bencher) { + do_bench_push_all_move(b, 0, 1000) } #[bench] - fn bench_extend_0(b: &mut Bencher) { + fn bench_push_all_move_0010_0010(b: &mut Bencher) { + do_bench_push_all_move(b, 10, 10) + } + + #[bench] + fn bench_push_all_move_0100_0100(b: &mut Bencher) { + do_bench_push_all_move(b, 100, 100) + } + + #[bench] + fn bench_push_all_move_1000_1000(b: &mut Bencher) { + do_bench_push_all_move(b, 1000, 1000) + } + + fn do_bench_clone(b: &mut Bencher, src_len: uint) { + let src: Vec<uint> = FromIterator::from_iter(range(0, src_len)); + + b.bytes = src_len as u64; + b.iter(|| { - let v0: Vec<int> = vec!(); - let mut v1: Vec<int> = vec!(1, 2, 3, 4, 5); - v1.extend(v0.move_iter()); - assert!(v1.as_slice() == [1, 2, 3, 4, 5]); - }) + let dst = src.clone(); + assert_eq!(dst.len(), src_len); + assert!(dst.iter().enumerate().all(|(i, x)| i == *x)); + }); } #[bench] - fn bench_extend_5(b: &mut Bencher) { + fn bench_clone_0000(b: &mut Bencher) { + do_bench_clone(b, 0) + } + + #[bench] + fn bench_clone_0010(b: &mut Bencher) { + do_bench_clone(b, 10) + } + + #[bench] + fn bench_clone_0100(b: &mut Bencher) { + do_bench_clone(b, 100) + } + + #[bench] + fn bench_clone_1000(b: &mut Bencher) { + do_bench_clone(b, 1000) + } + + fn do_bench_clone_from(b: &mut Bencher, times: uint, dst_len: uint, src_len: uint) { + let dst: Vec<uint> = FromIterator::from_iter(range(0, src_len)); + let src: Vec<uint> = FromIterator::from_iter(range(dst_len, dst_len + src_len)); + + b.bytes = (times * src_len) as u64; + b.iter(|| { - let v0: Vec<int> = vec!(1, 2, 3, 4, 5); - let mut v1: Vec<int> = vec!(1, 2, 3, 4, 5); - v1.extend(v0.move_iter()); - assert!(v1.as_slice() == [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]); - }) + let mut dst = dst.clone(); + + for _ in range(0, times) { + dst.clone_from(&src); + + assert_eq!(dst.len(), src_len); + assert!(dst.iter().enumerate().all(|(i, x)| dst_len + i == *x)); + } + }); + } + + #[bench] + fn bench_clone_from_01_0000_0000(b: &mut Bencher) { + do_bench_clone_from(b, 1, 0, 0) + } + + #[bench] + fn bench_clone_from_01_0000_0010(b: &mut Bencher) { + do_bench_clone_from(b, 1, 0, 10) + } + + #[bench] + fn bench_clone_from_01_0000_0100(b: &mut Bencher) { + do_bench_clone_from(b, 1, 0, 100) + } + + #[bench] + fn bench_clone_from_01_0000_1000(b: &mut Bencher) { + do_bench_clone_from(b, 1, 0, 1000) + } + + #[bench] + fn bench_clone_from_01_0010_0010(b: &mut Bencher) { + do_bench_clone_from(b, 1, 10, 10) + } + + #[bench] + fn bench_clone_from_01_0100_0100(b: &mut Bencher) { + do_bench_clone_from(b, 1, 100, 100) + } + + #[bench] + fn bench_clone_from_01_1000_1000(b: &mut Bencher) { + do_bench_clone_from(b, 1, 1000, 1000) + } + + #[bench] + fn bench_clone_from_01_0010_0100(b: &mut Bencher) { + do_bench_clone_from(b, 1, 10, 100) + } + + #[bench] + fn bench_clone_from_01_0100_1000(b: &mut Bencher) { + do_bench_clone_from(b, 1, 100, 1000) + } + + #[bench] + fn bench_clone_from_01_0010_0000(b: &mut Bencher) { + do_bench_clone_from(b, 1, 10, 0) + } + + #[bench] + fn bench_clone_from_01_0100_0010(b: &mut Bencher) { + do_bench_clone_from(b, 1, 100, 10) + } + + #[bench] + fn bench_clone_from_01_1000_0100(b: &mut Bencher) { + do_bench_clone_from(b, 1, 1000, 100) + } + + #[bench] + fn bench_clone_from_10_0000_0000(b: &mut Bencher) { + do_bench_clone_from(b, 10, 0, 0) + } + + #[bench] + fn bench_clone_from_10_0000_0010(b: &mut Bencher) { + do_bench_clone_from(b, 10, 0, 10) + } + + #[bench] + fn bench_clone_from_10_0000_0100(b: &mut Bencher) { + do_bench_clone_from(b, 10, 0, 100) + } + + #[bench] + fn bench_clone_from_10_0000_1000(b: &mut Bencher) { + do_bench_clone_from(b, 10, 0, 1000) + } + + #[bench] + fn bench_clone_from_10_0010_0010(b: &mut Bencher) { + do_bench_clone_from(b, 10, 10, 10) + } + + #[bench] + fn bench_clone_from_10_0100_0100(b: &mut Bencher) { + do_bench_clone_from(b, 10, 100, 100) + } + + #[bench] + fn bench_clone_from_10_1000_1000(b: &mut Bencher) { + do_bench_clone_from(b, 10, 1000, 1000) + } + + #[bench] + fn bench_clone_from_10_0010_0100(b: &mut Bencher) { + do_bench_clone_from(b, 10, 10, 100) + } + + #[bench] + fn bench_clone_from_10_0100_1000(b: &mut Bencher) { + do_bench_clone_from(b, 10, 100, 1000) + } + + #[bench] + fn bench_clone_from_10_0010_0000(b: &mut Bencher) { + do_bench_clone_from(b, 10, 10, 0) + } + + #[bench] + fn bench_clone_from_10_0100_0010(b: &mut Bencher) { + do_bench_clone_from(b, 10, 100, 10) + } + + #[bench] + fn bench_clone_from_10_1000_0100(b: &mut Bencher) { + do_bench_clone_from(b, 10, 1000, 100) } } |