Struct mozpdb::TypeFinder

pub struct TypeFinder<'t> { /* fields omitted */ }

A TypeFinder is a secondary, in-memory data structure that permits efficiently finding types by TypeIndex. It starts out empty and must be populated by calling update(&TypeIter) while iterating.

TypeFinder allocates all the memory it needs when it is first created. The footprint is directly proportional to the total number of types; see TypeInformation.len().

Time/space trade-off

The naïve approach is to store the position of each Type as they are covered in the stream. The cost is memory: namely one u32 per Type.

Compare this approach to a TypeFinder that stores the position of every Nth type. 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 TypeFinder means more of the data can fit in the cache, so this is likely a good trade-off for small-ish values of N.

TypeFinder is parameterized by shift which controls this trade-off as powers of two:

• If shift is 0, TypeFinder stores 4 bytes per Type and always performs direct lookups.
• If shift is 1, TypeFinder stores 2 bytes per Type and averages 0.5 iterations per lookup.
• If shift is 2, TypeFinder stores 1 byte per Type and averages 1.5 iterations per lookup.
• If shift is 3, TypeFinder stores 4 bits per Type and averages 3.5 iterations per lookup.
• If shift is 4, TypeFinder stores 2 bits per Type and averages 7.5 iterations per lookup.
• If shift is 5, TypeFinder stores 1 bit per Type and averages 15.5 iterations per lookup.

This list can continue but with rapidly diminishing returns. Iteration cost is proportional to type size, which varies, but typical numbers from a large program are:

• 24% of types are 12 bytes
• 34% of types are <= 16 bytes
• 84% of types are <= 32 bytes

A shift of 2 or 3 is likely appropriate for most workloads. 500K types 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.

Methods

impl<'t> TypeFinder<'t>

pub fn max_indexed_type(&self) -> TypeIndex

Returns the highest TypeIndex which is currently served by this TypeFinder.

In general, you shouldn't need to consider this. Types always refer to types with lower TypeIndexes, and either:

• You obtained a Type by iterating, in which case you should be calling update() as you iterate, and in which case all types it can reference are <= max_indexed_type(), or
• You got a Type from this TypeFinder, in which case all types it can reference are still <= max_indexed_type().

pub fn update(&mut self, iterator: &TypeIter)

Update this TypeFinder based on the current position of a TypeIter.

Do this each time you call .next().

pub fn find(&self, type_index: TypeIndex) -> Result<Type<'t>>

Find a type by TypeIndex.

Errors

• Error::TypeNotFound(type_index) if you ask for a type that doesn't exist
• Error::TypeNotIndexed(type_index, max_indexed_type) if you ask for a type that is known to exist but is not currently known by this TypeFinder.

Trait Implementations

impl<'t> Debug for TypeFinder<'t>

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

Formats the value using the given formatter.