Struct symbolic::debuginfo::pdb::pdb::ItemFinder [−]
pub struct ItemFinder<'t, I> { /* fields omitted */ }
In-memory index for efficient random-access to Item
s by index.
ItemFinder
can be obtained via ItemInformation::finder
. It starts out empty and must be
populated by calling ItemFinder::update
while iterating. There are two typedefs for easier
use:
TypeFinder
for findingType
s in aTypeInformation
(TPI stream).IdFinder
for findingId
s in aIdInformation
(IPI stream).
ItemFinder
allocates all the memory it needs when it is first created. The footprint is
directly proportional to the total number of types; see ItemInformation::len
.
Time/space trade-off
The naïve approach is to store the position of each Item
as they are covered in the stream.
The cost is memory: namely one u32
per Item
.
Compare this approach to an ItemFinder
that stores the position of every Nth item. Memory
requirements would be reduced by a factor of N in exchange for requiring an average of (N-1)/2
iterations per lookup. However, iteration is cheap sequential memory access, and spending less
memory on ItemFinder
means more of the data can fit in the cache, so this is likely a good
trade-off for small-ish values of N.
ItemFinder
is parameterized by shift
which controls this trade-off as powers of two:
- If
shift
is 0,ItemFinder
stores 4 bytes perItem
and always performs direct lookups. - If
shift
is 1,ItemFinder
stores 2 bytes perItem
and averages 0.5 iterations per lookup. - If
shift
is 2,ItemFinder
stores 1 byte perItem
and averages 1.5 iterations per lookup. - If
shift
is 3,ItemFinder
stores 4 bits perItem
and averages 3.5 iterations per lookup. - If
shift
is 4,ItemFinder
stores 2 bits perItem
and averages 7.5 iterations per lookup. - If
shift
is 5,ItemFinder
stores 1 bit perItem
and averages 15.5 iterations per lookup.
This list can continue but with rapidly diminishing returns. Iteration cost is proportional to item size, which varies, but typical numbers from a large program are:
- 24% of items are 12 bytes
- 34% of items are <= 16 bytes
- 84% of items are <= 32 bytes
A shift
of 2 or 3 is likely appropriate for most workloads. 500K items would require 1 MB or
500 KB of memory respectively, and lookups – though indirect – would still usually need only
one or two 64-byte cache lines.
Implementations
impl<'t, I> ItemFinder<'t, I> where
I: ItemIndex,
impl<'t, I> ItemFinder<'t, I> where
I: ItemIndex,
pub fn max_index(&self) -> I
Returns the highest index which is currently served by this ItemFinder
.
When iterating through the stream, you shouldn’t need to consider this. Items only ever reference lower indexes. However, when loading items referenced by the symbols stream, this can be useful to check whether iteration is required.
pub fn update(&mut self, iterator: &ItemIter<'t, I>)
Update this ItemFinder
based on the current position of a ItemIter
.
Do this each time you call .next()
. See documentation of ItemInformation
for an
example.
pub fn find(&self, index: I) -> Result<Item<'t, I>, Error>
Find an Item
by its index.
Errors
Error::TypeNotFound(index)
if you ask for an item that doesn’t exist.Error::TypeNotIndexed(index, max_index)
if you ask for an item that is known to exist but is not currently known by thisItemFinder
.
Trait Implementations
Auto Trait Implementations
impl<'t, I> RefUnwindSafe for ItemFinder<'t, I> where
I: RefUnwindSafe,
impl<'t, I> RefUnwindSafe for ItemFinder<'t, I> where
I: RefUnwindSafe,
impl<'t, I> Send for ItemFinder<'t, I> where
I: Sync,
impl<'t, I> Send for ItemFinder<'t, I> where
I: Sync,
impl<'t, I> Sync for ItemFinder<'t, I> where
I: Sync,
impl<'t, I> Sync for ItemFinder<'t, I> where
I: Sync,
impl<'t, I> Unpin for ItemFinder<'t, I>
impl<'t, I> Unpin for ItemFinder<'t, I>
impl<'t, I> UnwindSafe for ItemFinder<'t, I> where
I: RefUnwindSafe,
impl<'t, I> UnwindSafe for ItemFinder<'t, I> where
I: RefUnwindSafe,