Struct pdb::ItemFinder

pub struct ItemFinder<'t, I> { /* private fields */ }

In-memory index for efficient random-access to Items 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 finding Types in a TypeInformation (TPI stream).
• IdFinder for finding Ids in a IdInformation (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 per Item and always performs direct lookups.
• If shift is 1, ItemFinder stores 2 bytes per Item and averages 0.5 iterations per lookup.
• If shift is 2, ItemFinder stores 1 byte per Item and averages 1.5 iterations per lookup.
• If shift is 3, ItemFinder stores 4 bits per Item and averages 3.5 iterations per lookup.
• If shift is 4, ItemFinder stores 2 bits per Item and averages 7.5 iterations per lookup.
• If shift is 5, ItemFinder stores 1 bit per Item 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, 

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>>

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 this ItemFinder.

Trait Implementations

impl<'t, I: Debug> Debug for ItemFinder<'t, I>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.