diff options
| -rw-r--r-- | components/selectors/Cargo.toml | 1 | ||||
| -rw-r--r-- | components/selectors/bloom.rs | 112 | ||||
| -rw-r--r-- | components/selectors/lib.rs | 3 | ||||
| -rw-r--r-- | components/style/bloom.rs | 94 |
4 files changed, 136 insertions, 74 deletions
diff --git a/components/selectors/Cargo.toml b/components/selectors/Cargo.toml index 3894e3e21ad..dbaf0bdc2a2 100644 --- a/components/selectors/Cargo.toml +++ b/components/selectors/Cargo.toml @@ -20,6 +20,7 @@ doctest = false [features] gecko_like_types = [] +unstable = [] [dependencies] bitflags = "0.7" diff --git a/components/selectors/bloom.rs b/components/selectors/bloom.rs index 0f6fabbaa10..8caab9935cb 100644 --- a/components/selectors/bloom.rs +++ b/components/selectors/bloom.rs @@ -108,6 +108,18 @@ impl BloomFilter { self.counters = [0; ARRAY_SIZE] } + // Slow linear accessor to make sure the bloom filter is zeroed. This should + // never be used in release builds. + #[cfg(debug_assertions)] + pub fn is_zeroed(&self) -> bool { + self.counters.iter().all(|x| *x == 0) + } + + #[cfg(not(debug_assertions))] + pub fn is_zeroed(&self) -> bool { + unreachable!() + } + #[inline] pub fn insert_hash(&mut self, hash: u32) { { @@ -229,85 +241,75 @@ fn create_and_insert_some_stuff() { #[cfg(test)] mod bench { extern crate test; - - use std::hash::{Hash, Hasher, SipHasher}; use super::BloomFilter; + #[derive(Default)] + struct HashGenerator(u32); + + impl HashGenerator { + fn next(&mut self) -> u32 { + // Each hash is split into two twelve-bit segments, which are used + // as an index into an array. We increment each by 64 so that we + // hit the next cache line, and then another 1 so that our wrapping + // behavior leads us to different entries each time. + // + // Trying to simulate cold caches is rather difficult with the cargo + // benchmarking setup, so it may all be moot depending on the number + // of iterations that end up being run. But we might as well. + self.0 += (65) + (65 << super::KEY_SIZE); + self.0 + } + } + #[bench] fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) { b.iter(|| { + let mut gen1 = HashGenerator::default(); + let mut gen2 = HashGenerator::default(); let mut bf = BloomFilter::new(); - for i in 0_usize .. 1000 { - bf.insert(&i); + for _ in 0_usize .. 1000 { + bf.insert_hash(gen1.next()); } - for i in 0_usize .. 100 { - bf.remove(&i); + for _ in 0_usize .. 100 { + bf.remove_hash(gen2.next()); } - for i in 100_usize .. 200 { - test::black_box(bf.might_contain(&i)); + for _ in 100_usize .. 200 { + test::black_box(bf.might_contain_hash(gen2.next())); } }); } #[bench] - fn might_contain(b: &mut test::Bencher) { - let mut bf = BloomFilter::new(); - - for i in 0_usize .. 1000 { - bf.insert(&i); - } - - let mut i = 0_usize; - - b.bench_n(1000, |b| { - b.iter(|| { - test::black_box(bf.might_contain(&i)); - i += 1; - }); + fn might_contain_10(b: &mut test::Bencher) { + let bf = BloomFilter::new(); + let mut gen = HashGenerator::default(); + b.iter(|| for _ in 0..10 { + test::black_box(bf.might_contain_hash(gen.next())); }); } #[bench] - fn insert(b: &mut test::Bencher) { - let mut bf = BloomFilter::new(); - - b.bench_n(1000, |b| { - let mut i = 0_usize; - - b.iter(|| { - test::black_box(bf.insert(&i)); - i += 1; - }); - }); + fn clear(b: &mut test::Bencher) { + let mut bf = Box::new(BloomFilter::new()); + b.iter(|| test::black_box(&mut bf).clear()); } #[bench] - fn remove(b: &mut test::Bencher) { + fn insert_10(b: &mut test::Bencher) { let mut bf = BloomFilter::new(); - for i in 0_usize .. 1000 { - bf.insert(&i); - } - - b.bench_n(1000, |b| { - let mut i = 0_usize; - - b.iter(|| { - bf.remove(&i); - i += 1; - }); + let mut gen = HashGenerator::default(); + b.iter(|| for _ in 0..10 { + test::black_box(bf.insert_hash(gen.next())); }); - - test::black_box(bf.might_contain(&0_usize)); } #[bench] - fn hash_a_uint(b: &mut test::Bencher) { - let mut i = 0_usize; - b.iter(|| { - let mut hasher = SipHasher::default(); - i.hash(&mut hasher); - test::black_box(hasher.finish()); - i += 1; - }) + fn remove_10(b: &mut test::Bencher) { + let mut bf = BloomFilter::new(); + let mut gen = HashGenerator::default(); + // Note: this will underflow, and that's ok. + b.iter(|| for _ in 0..10 { + bf.remove_hash(gen.next()) + }); } } diff --git a/components/selectors/lib.rs b/components/selectors/lib.rs index 568e1aaba70..c2ad24ee73e 100644 --- a/components/selectors/lib.rs +++ b/components/selectors/lib.rs @@ -2,6 +2,9 @@ * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ +// Make |cargo bench| work. +#![cfg_attr(feature = "unstable", feature(test))] + #[macro_use] extern crate bitflags; #[macro_use] extern crate cssparser; #[macro_use] extern crate log; diff --git a/components/style/bloom.rs b/components/style/bloom.rs index c63cf88a76e..34b6b608962 100644 --- a/components/style/bloom.rs +++ b/components/style/bloom.rs @@ -46,8 +46,39 @@ pub struct StyleBloom<E: TElement> { /// The bloom filter per se. filter: Box<BloomFilter>, - /// The stack of elements that this bloom filter contains. - elements: Vec<SendElement<E>>, + /// The stack of elements that this bloom filter contains, along with the + /// number of hashes pushed for each element. + elements: SmallVec<[PushedElement<E>; 16]>, + + /// Stack of hashes that have been pushed onto this filter. + pushed_hashes: SmallVec<[u32; 64]>, +} + +/// The very rough benchmarks in the selectors crate show clear() +/// costing about 25 times more than remove_hash(). We use this to implement +/// clear() more efficiently when only a small number of hashes have been +/// pushed. +/// +/// One subtly to note is that remove_hash() will not touch the value +/// if the filter overflowed. However, overflow can only occur if we +/// get 255 collisions on the same hash value, and 25 < 255. +const MEMSET_CLEAR_THRESHOLD: usize = 25; + +struct PushedElement<E: TElement> { + /// The element that was pushed. + element: SendElement<E>, + + /// The number of hashes pushed for the element. + num_hashes: usize, +} + +impl<E: TElement> PushedElement<E> { + fn new(el: E, num_hashes: usize) -> Self { + PushedElement { + element: unsafe { SendElement::new(el) }, + num_hashes: num_hashes, + } + } } fn each_relevant_element_hash<E, F>(element: E, mut f: F) @@ -75,7 +106,8 @@ impl<E: TElement> StyleBloom<E> { pub fn new() -> Self { StyleBloom { filter: Box::new(BloomFilter::new()), - elements: vec![], + elements: Default::default(), + pushed_hashes: Default::default(), } } @@ -98,23 +130,36 @@ impl<E: TElement> StyleBloom<E> { /// Same as `push`, but without asserting, in order to use it from /// `rebuild`. fn push_internal(&mut self, element: E) { + let mut count = 0; each_relevant_element_hash(element, |hash| { + count += 1; self.filter.insert_hash(hash); + self.pushed_hashes.push(hash); }); - self.elements.push(unsafe { SendElement::new(element) }); + self.elements.push(PushedElement::new(element, count)); } /// Pop the last element in the bloom filter and return it. + #[inline] fn pop(&mut self) -> Option<E> { - let popped = self.elements.pop().map(|el| *el); + let (popped_element, num_hashes) = match self.elements.pop() { + None => return None, + Some(x) => (*x.element, x.num_hashes), + }; - if let Some(popped) = popped { - each_relevant_element_hash(popped, |hash| { - self.filter.remove_hash(hash); - }) + // Verify that the pushed hashes match the ones we'd get from the element. + let mut expected_hashes = vec![]; + if cfg!(debug_assertions) { + each_relevant_element_hash(popped_element, |hash| expected_hashes.push(hash)); } - popped + for _ in 0..num_hashes { + let hash = self.pushed_hashes.pop().unwrap(); + debug_assert_eq!(expected_hashes.pop().unwrap(), hash); + self.filter.remove_hash(hash); + } + + Some(popped_element) } /// Returns true if the bloom filter is empty. @@ -131,21 +176,32 @@ impl<E: TElement> StyleBloom<E> { /// Clears the bloom filter. pub fn clear(&mut self) { - self.filter.clear(); self.elements.clear(); + + if self.pushed_hashes.len() > MEMSET_CLEAR_THRESHOLD { + self.filter.clear(); + self.pushed_hashes.clear(); + } else { + for hash in self.pushed_hashes.drain() { + self.filter.remove_hash(hash); + } + debug_assert!(self.filter.is_zeroed()); + } } /// Rebuilds the bloom filter up to the parent of the given element. pub fn rebuild(&mut self, mut element: E) { self.clear(); + let mut parents_to_insert = SmallVec::<[E; 16]>::new(); while let Some(parent) = element.traversal_parent() { - self.push_internal(parent); + parents_to_insert.push(parent); element = parent; } - // Put them in the order we expect, from root to `element`'s parent. - self.elements.reverse(); + for parent in parents_to_insert.drain().rev() { + self.push(parent); + } } /// In debug builds, asserts that all the parents of `element` are in the @@ -156,7 +212,7 @@ impl<E: TElement> StyleBloom<E> { if cfg!(debug_assertions) { let mut checked = 0; while let Some(parent) = element.traversal_parent() { - assert_eq!(parent, *self.elements[self.elements.len() - 1 - checked]); + assert_eq!(parent, *(self.elements[self.elements.len() - 1 - checked].element)); element = parent; checked += 1; } @@ -169,7 +225,7 @@ impl<E: TElement> StyleBloom<E> { /// (if any) and its ancestors. #[inline] pub fn current_parent(&self) -> Option<E> { - self.elements.last().map(|el| **el) + self.elements.last().map(|ref el| *el.element) } /// Insert the parents of an element in the bloom filter, trying to recover @@ -238,7 +294,7 @@ impl<E: TElement> StyleBloom<E> { // Let's collect the parents we are going to need to insert once we've // found the common one. - let mut parents_to_insert = SmallVec::<[E; 8]>::new(); + let mut parents_to_insert = SmallVec::<[E; 16]>::new(); // If the bloom filter still doesn't have enough elements, the common // parent is up in the dom. @@ -266,7 +322,7 @@ impl<E: TElement> StyleBloom<E> { // // Thus it's possible with Gecko that we do not find any common // ancestor. - while **self.elements.last().unwrap() != common_parent { + while *(self.elements.last().unwrap().element) != common_parent { parents_to_insert.push(common_parent); self.pop().unwrap(); common_parent = match common_parent.traversal_parent() { @@ -284,7 +340,7 @@ impl<E: TElement> StyleBloom<E> { // Now the parents match, so insert the stack of elements we have been // collecting so far. - for parent in parents_to_insert.into_iter().rev() { + for parent in parents_to_insert.drain().rev() { self.push(parent); } |