Skip to content

Instantly share code, notes, and snippets.

@aldanor

aldanor/search-hashing.callgrind.rs

Last active September 11, 2015 21:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aldanor/e3d71d7e45b6470ded95 to your computer and use it in GitHub Desktop.
Save aldanor/e3d71d7e45b6470ded95 to your computer and use it in GitHub Desktop.
Download ZIP
search-hashing.callgrind.log
Raw
search-hashing.callgrind.rs
--------------------------------------------------------------------------------
Ir
--------------------------------------------------------------------------------
158,791,478,749 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir file:function
--------------------------------------------------------------------------------
10,231,292,690 collections::hash::map::robin_hood
9,273,922,532 collections::hash::table::RawBucket<_>::offset
8,290,422,816 collections::hash::table::FullBucket<_>::next
7,497,595,545 collections::hash::table::Bucket<_>::next
6,710,531,152 collections::hash::table::Bucket<_>::peek
6,706,954,240 hash::sip::SipHasher.Hasher::finish
4,000,136,316 collections::hash::table::FullBucket<_>::distance
3,925,540,864 hash::sip::SipHasher::write
3,582,008,589 collections::hash::map::HashMap<_>::insert_or_replace_with
3,312,115,190 ptr::<_>::offset
3,135,418,292 collections::hash::map::HashMap<_>::resize
3,057,582,080 num::u64::wrapping_add
2,690,695,140 ops::<_>.Deref::deref
2,658,571,186 collections::hash::map::HashMap<_>::insert_hashed_ordered
2,645,798,150 collections::hash::table::RawTable<_>::capacity
2,441,056,007 collections::hash::table::FullBucket<_>::into_bucket
2,388,818,420 collections::hash::table::RawTable<_>::first_bucket_raw
2,375,648,525 collections::hash::table::FullBucket<_>::replace
2,324,255,760 collections::hash::table::round_up_to_next
2,324,006,532 collections::hash::table::Bucket<_>::at_index
2,278,629,899 collections::hash::table::EmptyBucket<_>::put
2,209,345,418 raw::Repr::repr
2,066,058,096 num::usize::is_power_of_two
1,865,737,920 num::usize::wrapping_sub
1,804,959,744 raw_vec::RawVec<_>.Drop::drop
1,678,629,160 collections::hash::table::calculate_offsets
1,656,057,595 ptr::<_>::offset
1,561,804,842 collections::hash::table::FullBucket<_>::hash
1,400,562,632 vec::IntoIter<_>.Iterator::next
1,395,360,215 collections::hash::table::Bucket<_>::index
1,326,450,111 collections::hash::table::FullBucket<_>::take
1,183,580,160 num::i32::wrapping_sub
1,183,565,110 vec::Vec<_>::push
1,173,716,992 raw_vec::RawVec<_>::unsafe_no_drop_flag_needs_drop
1,144,127,488 slice::hack::into_vec
1,104,674,816 raw::Repr::repr
1,025,792,950 search::SearchSpace::dfs
1,025,769,472 slice::<_>.SliceExt::len
1,025,753,820 vec::Vec<_>::pop
986,387,881 collections::hash::table::RevMoveBuckets<_>.Iterator::next
950,259,410 ptr::replace
950,259,410 ptr::replace
908,482,700 collections::hash::table::FullBucket<_>::index
887,680,605 vec::Vec<_>.ops..DerefMut::deref_mut
828,506,112 vec::Vec<_>.Drop::drop
828,499,791 slice::<_>.SliceExt::last_mut
828,499,791 slice::<_>.ops..IndexMut<_>::index_mut
789,051,935 mem::transmute_copy
769,315,365 ptr::write
760,209,936 mem::swap
760,207,528 mem::swap
729,874,432 hash::sip::SipHasher::new_with_keys
710,148,096 vec::Vec<_>.IntoIterator::into_iter
710,142,678 slice::<_>.SliceExt::get_unchecked_mut
645,644,660 ptr::<_>::offset
641,105,920 BinaryTree.SearchSpace::expand
631,241,548 mem::transmute_copy
622,224,023 _platform_memset<_> [/usr/lib/system/libsystem_platfor
611,539,593 collections::hash::map::HashMap<_>::reserve
611,515,513 collections..vec..IntoIter<_>::drop.4926
611,339,729 collections::hash::table::Bucket<_>::new
552,337,408 raw::Repr::repr
512,884,736 slice::<_>.SliceExt::as_mut_ptr
512,585,281 collections::hash::table::EmptyBucket<_>::into_bucket
473,437,482 raw_vec::RawVec<_>::ptr
473,432,064 collections::hash::map::HashMap<_>::insert
473,430,258 ptr::<_>::is_null
457,131,710 ops::<_>.DerefMut::deref_mut
453,705,728 vec::Vec<_>.IntoIterator::into_iter
453,705,728 collections::hash::table::make_hash
433,979,392 vec::IntoIter<_>.Drop::drop
430,200,036 collections::hash::map::HashMap<_>::insert_hashed_ordered
421,476,585 collections::hash::table::RawTable<_>::size
414,341,550 option::Option<_>::expect
414,250,949 ptr::<_>::offset
394,532,740 nonzero::NonZero<_>.Deref::deref
394,526,720 mem::transmute_copy
355,074,048 slice::<_>.SliceExt::len
355,074,048 hash::sip::SipHasher::reset
355,074,048 Box<_>::drop.4475
355,074,048 collections..vec..Vec<_>::drop.4321
355,072,242 slice::from_raw_parts_mut
355,068,630 slice::<_>.SliceExt::get_unchecked
322,849,420 nonzero::NonZero<_>.Deref::deref
315,626,192 ptr::Unique<_>.Deref::deref
315,621,376 slice::<_>::into_vec
315,621,376 mem::transmute_copy
315,621,376 slice::<_>.SliceExt::get_unchecked
298,384,982 collections::hash::table::SafeHash...core..cmp..PartialEq::eq
295,900,458 heap::exchange_malloc
295,895,040 raw_vec::RawVec<_>::from_raw_parts
295,895,040 vec::Vec<_>.ops..DerefMut::deref_mut
295,890,525 vec::Vec<_>.ops..Deref::deref
277,881,695 ptr::write
276,168,704 vec::Vec<_>::from_raw_parts
276,168,704 collections::hash::map::RandomState.HashState::hasher
269,381,940 collections::hash::table::BucketState<_>::expect_full
258,279,536 ptr::Unique<_>.Deref::deref
256,446,281 slice::<_>.SliceExt::as_mut_ptr
256,442,368 search::Visited<_>::insert
236,716,032 iter::<_>.Iterator::next
236,716,032 mem::forget
236,716,032 ptr::<_>::is_null
236,716,032 num::u64::next_power_of_two
227,032,233 jemalloc/include/jemalloc/internal/tcache.
216,989,696 mem::forget
216,989,696 vec::Vec<_>.IntoIterator::into_iter
216,989,696 slice::<_>.SliceExt::len
197,368,059 jemalloc/src/jemalloc.
197,327,074 jemalloc/include/jemalloc/internal/arena.
197,263,360 mem::transmute_copy
179,250,015 collections::hash::table::EmptyBucket<_>::table
177,694,005 jemalloc/include/jemalloc/internal/tcache.
177,610,167 num::usize::checked_add
177,605,033 jemalloc/include/jemalloc/internal/arena.
177,539,733 collections::hash::map::DefaultResizePolicy::min_capacity
177,537,024 hash::Hasher::write_u64
157,887,216
157,810,688 slice::<_>::len
157,810,688 slice::<_>::as_mut_ptr
157,810,688 slice::<_>.SliceExt::len
157,810,688 num::u64::leading_zeros
157,810,688 mem::transmute_copy
157,809,484 slice::<_>::last_mut
148,019,265 jemalloc/src/jemalloc.
147,947,520 nonzero::NonZero<_>.Deref::deref
138,151,379 jemalloc/include/jemalloc/internal/tsd.
138,086,459 cmp::impls::u64.PartialEq::eq
138,084,352 hash::impls::u64.Hash::hash
138,084,352 option::Option<_>::is_some
138,084,352 ptr::<_>::offset
138,084,352 collections::hash::table::FullBucket<_>::into_mut_refs
129,125,320 collections::hash::table::calculate_offsets
118,415,412 jemalloc/include/jemalloc/internal/tsd.
118,358,016 slice::from_raw_parts_mut
118,358,016 hash::sip::load_u64_le
118,358,016 option::Option<_>::is_none
118,358,016 raw_vec::RawVec<_>::ptr
118,358,016 alloc..raw_vec..RawVec<_>::drop.4366
118,358,016 ptr::Unique<_>.Deref::deref
118,358,016 collections::hash::set::HashSet<_>::insert
118,358,016 ptr::<_>::offset
118,356,210 slice::from_raw_parts
99,066,023 collections::hash::table::RawTable<_>.Drop::drop
98,694,580 jemalloc/internal/jemalloc_internal.
98,679,510
98,631,680 num::u64::to_le
98,631,680 iter::I.IntoIterator::into_iter
98,631,680 collections::hash::map::HashMap<_>::len
98,631,680 ptr::<_>::offset
98,631,680 vec::Vec<_>::len
98,631,680 ptr::<_>::offset
98,631,680 ptr::Unique<_>::new
98,631,680 iter::Iterator::by_ref
98,631,680 num::u64::wrapping_sub
98,631,680 clone::u64.Clone::clone
98,631,680 vec::Vec<_>::len
98,630,175 raw_vec::RawVec<_>::cap
--------------------------------------------------------------------------------
-- Auto-annotated source: benches/bench.rs
--------------------------------------------------------------------------------
Ir
. #![feature(test)]
.
49,315,840 extern crate chappie;
. extern crate test;
.
. use chappie::search::SearchSpace;
. use test::{Bencher, black_box};
. use std::vec::IntoIter;
.
. enum Dir { Left, Right}
.
-- line 11 ----------------------------------------
-- line 14 ----------------------------------------
. const MAX_DEPTH: u64 = 16;
. const MAX_OFFSET: u64 = 1 << (MAX_DEPTH + 1);
.
. impl SearchSpace for BinaryTree {
. type State = u64;
. type Action = Dir;
. type Iterator = IntoIter<(Self::Action, Self::State)>;
.
157,810,688 fn expand(&self, state: &Self::State) -> Self::Iterator {
78,905,344 let offset = (*state + 2).next_power_of_two();
493,158,400 => num::u64::next_power_of_two (19726336x)
39,452,672 if offset >= MAX_OFFSET {
. return vec![].into_iter();
. }
9,863,168 let right = *state + offset;
19,726,336 let left = *state + offset / 2;
128,221,184 vec![(Dir::Left, left), (Dir::Right, right)].into_iter()
6,489,964,544 => vec::Vec<_>.IntoIterator::into_iter (19726336x)
6,075,711,488 => slice::<_>::into_vec (19726336x)
157,810,688 }
. }
.
. #[bench]
. fn dfs(b: &mut Bencher) {
. let tree = BinaryTree;
1,505 b.iter(|| { black_box(tree.dfs(0, 2)) });
. }
602 <counts for unidentified lines in benches/bench.rs>
--------------------------------------------------------------------------------
-- Auto-annotated source: src/search.rs
--------------------------------------------------------------------------------
Ir
. use std::iter::Iterator;
. use std::collections::HashSet;
11,137 use std::hash::Hash;
.
. struct Visited<T> {
. hash_set: HashSet<T>
. }
.
. impl<T> Visited<T> where T: Hash + Clone + Eq {
3,010 fn new() -> Visited<T> {
. Visited {
301 hash_set: HashSet::new()
339,499 => collections::hash::set::HashSet<_>::new (301x)
. }
. }
.
98,631,680 fn insert(&mut self, value: &T) -> bool {
157,810,688 self.hash_set.insert(value.clone())
98,631,680 => clone::u64.Clone::clone::h454dd431083d085315u (19726336x)
119,377,026,346 => collections::hash::set::HashSet<_>::insert (19726336x)
. }
. }
.
. pub trait SearchGoal<T> {
. fn is_goal(&self, state: &T) -> bool;
. }
.
. impl<T> SearchGoal<T> for T where T: PartialEq {
39,453,274 fn is_goal(&self, state: &T) -> bool {
39,453,274 *self == *state
138,086,459 => cmp::impls::u64.PartialEq::eq (19726637x)
. }
. }
.
. pub trait SearchSpace {
. type State: Hash + Clone + Eq;
. type Action;
. type Iterator: Iterator<Item=(Self::Action, Self::State)>;
.
. fn expand(&self, state: &Self::State) -> Self::Iterator;
.
. fn dfs<G>(&self, start: Self::State, goal: G) -> Option<Vec<Self::Action>>
9,331 where G: SearchGoal<Self::State> {
16,555 => collections..vec..Vec<_>..vec..IntoIter<_>..option..Option<_>::drop.4972 (301x)
2,803,091,726 => chappie..search..Visited<_>::drop.4960 (301x)
903 if goal.is_goal(&start) {
3,311 => search::T.SearchGoal<_>::is_goal (301x)
602 return Some(vec![]);
. }
.
301 let mut visited = Visited::new();
342,810 => search::Visited<_>::new (301x)
3,913 let mut stack = vec![(self.expand(&start), None)];
252,576 => BinaryTree.SearchSpace::expand (301x)
98,427 => slice::<_>::into_vec (301x)
.
. loop {
276,166,597 let next = match stack.last_mut() {
1,656,999,582 => vec::Vec<_>.ops..DerefMut::deref_mut (39452371x)
6,549,093,586 => slice::<_>::last_mut (39452371x)
. None => return None,
236,714,527 Some(&mut (ref mut iter, _)) => iter.next()
1,104,667,592 => vec::IntoIter<_>.Iterator::next (39452371x)
. };
. if let Some((action, state)) = next {
118,358,016 if !visited.insert(&state) {
119,732,100,394 => search::Visited<_>::insert (19726336x)
. continue;
. }
78,905,344 if goal.is_goal(&state) {
216,989,696 => search::T.SearchGoal<_>::is_goal (19726336x)
. return Some(
5,418 stack.into_iter()
101,738 => vec::Vec<_>.IntoIterator::into_iter (301x)
17,759 => iter::Iterator::chain (301x)
615,255 => iter::Iterator::collect (301x)
14,749 => iter::Iterator::filter_map (301x)
6,321 .filter_map(|(_, a)| a)
65,956 => <_>..vec..IntoIter<_>..option..Option<_>::drop.5513 (301x)
301 .chain(Some(action).into_iter())
1,505 => option::Option<_>.IntoIterator::into_iter (301x)
. .collect()
. )
. }
197,260,350 stack.push((self.expand(&state), Some(action)));
15,260,516,487 => BinaryTree.SearchSpace::expand (19726035x)
4,124,132,495 => vec::Vec<_>::push (19726035x)
. } else {
118,356,210 stack.pop();
3,129,246,950 => core..option..Option<_>..vec..IntoIter<_>..option..Option<_>::drop.5575 (19726035x)
3,175,891,635 => vec::Vec<_>::pop (19726035x)
. }
. }
. }
. }
.
. #[cfg(test)]
. pub mod tests {
. use std::vec::IntoIter;
-- line 74 ----------------------------------------
--------------------------------------------------------------------------------
Ir
--------------------------------------------------------------------------------
1 percentage of events annotated
Raw
search-no-hashing.callgrind.rs
--------------------------------------------------------------------------------
Ir
--------------------------------------------------------------------------------
36,155,999,257 PROGRAM TOTALS
--------------------------------------------------------------------------------
Ir file:function
--------------------------------------------------------------------------------
2,209,345,418 raw::Repr::repr
1,804,959,744 raw_vec::RawVec<_>.Drop::drop
1,400,562,632 vec::IntoIter<_>.Iterator::next
1,183,565,110 vec::Vec<_>::push
1,173,716,992 raw_vec::RawVec<_>::unsafe_no_drop_flag_needs_drop
1,144,127,488 slice::hack::into_vec
1,025,769,472 slice::<_>.SliceExt::len
1,025,753,820 vec::Vec<_>::pop
927,160,066 src/search.rs:search::SearchSpace::dfs
887,680,605 vec::Vec<_>.ops..DerefMut::deref_mut
828,506,112 vec::Vec<_>.Drop::drop
828,499,791 slice::<_>.SliceExt::last_mut
828,499,791 slice::<_>.ops..IndexMut<_>::index_mut
789,051,935 mem::transmute_copy
769,315,365 ptr::write
710,148,096 raw::Repr::repr
710,148,096 vec::Vec<_>.IntoIterator::into_iter
710,142,678 slice::<_>.SliceExt::get_unchecked_mut
641,105,920 benches/bench.rs:BinaryTree.SearchSpace::expand
631,241,548 mem::transmute_copy
611,515,513 collections..vec..IntoIter<_>::drop.4584
512,884,736 slice::<_>.SliceExt::as_mut_ptr
473,437,482 raw_vec::RawVec<_>::ptr
473,430,258 ptr::<_>::is_null
453,705,728 vec::Vec<_>.IntoIterator::into_iter
433,979,392 vec::IntoIter<_>.Drop::drop
414,250,949 ptr::<_>::offset
394,532,740 nonzero::NonZero<_>.Deref::deref
394,526,720 raw::Repr::repr
394,526,720 mem::transmute_copy
355,074,048 Box<_>::drop.4475
355,074,048 slice::<_>.SliceExt::len
355,074,048 collections..vec..Vec<_>::drop.4321
355,072,242 slice::from_raw_parts_mut
355,068,630 slice::<_>.SliceExt::get_unchecked
315,626,192 ptr::Unique<_>.Deref::deref
315,621,376 mem::transmute_copy
315,621,376 slice::<_>::into_vec
295,900,458 heap::exchange_malloc
295,895,040 raw_vec::RawVec<_>::from_raw_parts
295,895,040 vec::Vec<_>.ops..DerefMut::deref_mut
295,890,525 vec::Vec<_>.ops..Deref::deref
276,168,704 vec::Vec<_>::from_raw_parts
256,446,281 slice::<_>.SliceExt::as_mut_ptr
236,716,032 mem::forget
236,716,032 iter::<_>.Iterator::next
236,716,032 num::u64::next_power_of_two
236,716,032 ptr::<_>::is_null
226,990,010 jemalloc/include/jemalloc/internal/tcache.h:je_mallocx
216,989,696 mem::forget
216,989,696 vec::Vec<_>.IntoIterator::into_iter
197,286,789 jemalloc/src/jemalloc.c:je_mallocx
197,286,740 jemalloc/internal/arena.h:je_sdallocx
177,658,789 jemalloc/internal/tcache.h:je_sdallocx
177,558,077 jemalloc/internal/arena.h:je_mallocx
157,829,424 je_mallocx
157,810,688 num::u64::leading_zeros
157,810,688 slice::<_>::len
157,810,688 slice::<_>.SliceExt::len
157,810,688 slice::<_>::as_mut_ptr
157,809,484 slice::<_>::last_mut
147,965,085 jemalloc/src/jemalloc.c:je_sdallocx
147,947,520 nonzero::NonZero<_>.Deref::deref
138,100,811 jemalloc/include/jemalloc/internal/tsd.h:je_mallocx
138,086,459 cmp::impls::u64.PartialEq::eq
138,084,352 ptr::<_>::offset
118,372,068 jemalloc/include/jemalloc/internal/tsd.h:je_sdallocx
118,358,016 raw_vec::RawVec<_>::ptr
118,358,016 slice::from_raw_parts_mut
118,358,016 alloc..raw_vec..RawVec<_>::drop.4366
118,358,016 ptr::Unique<_>.Deref::deref
118,358,016 ptr::<_>::offset
118,356,210 slice::from_raw_parts
98,643,410 jemalloc/internal/jemalloc_internal.h:je_sdallocx
98,643,390 je_sdallocx
98,631,680 num::u64::wrapping_sub
98,631,680 ptr::Unique<_>::new
98,631,680 vec::Vec<_>::len
98,631,680 vec::Vec<_>::len
98,631,680 iter::I.IntoIterator::into_iter
98,631,680 ptr::<_>::offset
98,631,680 iter::Iterator::by_ref
98,630,175 raw_vec::RawVec<_>::cap
88,768,512 BinaryTree.SearchSpace::expand
78,914,712 __rust_allocate
78,914,712 __rust_deallocate
78,906,548 src/search.rs:search::T.SearchGoal<_>::is_goal
78,906,548 slice::<_>::as_mut_ptr
78,905,344 vec::IntoIter<_>.Iterator::next
78,905,344 <_>..vec..IntoIter<_>..option..Option<_>::drop.4581
78,904,140 slice::<_>::get_unchecked
69,050,385 jemalloc/internal/jemalloc_internal.h:je_mallocx
59,191,650 ptr::<_>::is_null
--------------------------------------------------------------------------------
-- Auto-annotated source: src/search.rs
--------------------------------------------------------------------------------
Ir
. use std::iter::Iterator;
. use std::collections::HashSet;
11,438 use std::hash::Hash;
.
. struct Visited<T> {
. hash_set: HashSet<T>
. }
.
. impl<T> Visited<T> where T: Hash + Clone + Eq {
. fn new() -> Visited<T> {
. Visited {
-- line 11 ----------------------------------------
-- line 18 ----------------------------------------
. }
. }
.
. pub trait SearchGoal<T> {
. fn is_goal(&self, state: &T) -> bool;
. }
.
. impl<T> SearchGoal<T> for T where T: PartialEq {
39,453,274 fn is_goal(&self, state: &T) -> bool {
39,453,274 *self == *state
138,086,459 => cmp::impls::u64.PartialEq::eq (19726637x)
. }
. }
.
. pub trait SearchSpace {
. type State: Hash + Clone + Eq;
. type Action;
. type Iterator: Iterator<Item=(Self::Action, Self::State)>;
.
. fn expand(&self, state: &Self::State) -> Self::Iterator;
.
. fn dfs<G>(&self, start: Self::State, goal: G) -> Option<Vec<Self::Action>>
8,729 where G: SearchGoal<Self::State> {
16,555 => collections..vec..Vec<_>..vec..IntoIter<_>..option..Option<_>::drop.4622 (301x)
903 if goal.is_goal(&start) {
3,311 => src/search.rs:search::T.SearchGoal<_>::is_goal (301x)
903 return Some(vec![]);
. }
.
. // let mut visited = Visited::new();
3,010 let mut stack = vec![(self.expand(&start), None)];
98,427 => slice::<_>::into_vec (301x)
252,576 => benches/bench.rs:BinaryTree.SearchSpace::expand (301x)
.
. loop {
276,166,597 let next = match stack.last_mut() {
6,549,093,586 => slice::<_>::last_mut (39452371x)
1,656,999,582 => vec::Vec<_>.ops..DerefMut::deref_mut (39452371x)
. None => return None,
256,440,863 Some(&mut (ref mut iter, _)) => iter.next()
1,104,667,592 => vec::IntoIter<_>.Iterator::next (39452371x)
. };
. if let Some((action, state)) = next {
. // if !visited.insert(&state) {
. // continue;
. // }
78,905,344 if goal.is_goal(&state) {
216,989,696 => src/search.rs:search::T.SearchGoal<_>::is_goal (19726336x)
. return Some(
5,418 stack.into_iter()
615,255 => iter::Iterator::collect (301x)
101,738 => vec::Vec<_>.IntoIterator::into_iter (301x)
14,749 => iter::Iterator::filter_map (301x)
17,759 => iter::Iterator::chain (301x)
6,321 .filter_map(|(_, a)| a)
65,956 => <_>..vec..IntoIter<_>..option..Option<_>::drop.4911 (301x)
301 .chain(Some(action).into_iter())
1,505 => option::Option<_>.IntoIterator::into_iter (301x)
. .collect()
. )
. }
197,260,350 stack.push((self.expand(&state), Some(action)));
4,124,129,826 => vec::Vec<_>::push (19726035x)
15,259,875,974 => benches/bench.rs:BinaryTree.SearchSpace::expand (19726035x)
. } else {
118,356,210 stack.pop();
3,128,588,463 => core..option..Option<_>..vec..IntoIter<_>..option..Option<_>::drop.4973 (19726035x)
3,175,891,635 => vec::Vec<_>::pop (19726035x)
. }
. }
. }
. }
.
. #[cfg(test)]
. pub mod tests {
. use std::vec::IntoIter;
-- line 74 ----------------------------------------
--------------------------------------------------------------------------------
-- Auto-annotated source: benches/bench.rs
--------------------------------------------------------------------------------
Ir
. #![feature(test)]
.
49,315,840 extern crate chappie;
. extern crate test;
.
. use chappie::search::SearchSpace;
. use test::{Bencher, black_box};
. use std::vec::IntoIter;
.
. enum Dir { Left, Right}
.
-- line 11 ----------------------------------------
-- line 14 ----------------------------------------
. const MAX_DEPTH: u64 = 16;
. const MAX_OFFSET: u64 = 1 << (MAX_DEPTH + 1);
.
. impl SearchSpace for BinaryTree {
. type State = u64;
. type Action = Dir;
. type Iterator = IntoIter<(Self::Action, Self::State)>;
.
157,810,688 fn expand(&self, state: &Self::State) -> Self::Iterator {
78,905,344 let offset = (*state + 2).next_power_of_two();
493,158,400 => num::u64::next_power_of_two (19726336x)
39,452,672 if offset >= MAX_OFFSET {
. return vec![].into_iter();
. }
9,863,168 let right = *state + offset;
19,726,336 let left = *state + offset / 2;
128,221,184 vec![(Dir::Left, left), (Dir::Right, right)].into_iter()
6,489,964,544 => vec::Vec<_>.IntoIterator::into_iter (19726336x)
6,075,711,488 => slice::<_>::into_vec (19726336x)
157,810,688 }
. }
.
. #[bench]
404 fn dfs(b: &mut Bencher) {
. let tree = BinaryTree;
1,606 b.iter(|| { black_box(tree.dfs(0, 2)) });
36,144,972,054 => Bencher::iter (101x)
303 }
602 <counts for unidentified lines in benches/bench.rs>
--------------------------------------------------------------------------------
Ir
--------------------------------------------------------------------------------
5 percentage of events annotated
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment