Elektra  0.9.7
Enumerations | Functions | Variables
kdbopmphmpredictor.h File Reference

Defines for the Order Preserving Minimal Perfect Hash Map Predictor. More...

#include <stdint.h>
Include dependency graph for kdbopmphmpredictor.h:
This graph shows which files directly or indirectly include this file:

Enumerations

enum  predictorflag_t { OPMPHM_PREDICTOR_FLAG_MMAP_STRUCT = 1 , OPMPHM_PREDICTOR_FLAG_MMAP_PATTERNTABLE = 1 << 2 }
 OpmphmPredictor Flags. More...
 

Functions

OpmphmPredictor * opmphmPredictorNew (void)
 Basic functions. More...
 
void opmphmPredictorDel (OpmphmPredictor *op)
 Deletes the OpmphmPredictor. More...
 
void opmphmPredictorCopy (OpmphmPredictor *dest, OpmphmPredictor *source)
 Make a copy of the OpmphmPredictor. More...
 
size_t opmphmPredictorWorthOpmphm (size_t n)
 Heuristic function. More...
 
int opmphmPredictor (OpmphmPredictor *op, size_t n)
 Predictor functions. More...
 
void opmphmPredictorIncCountOpmphm (OpmphmPredictor *op)
 Increases the counter when the OPMPHM was used for the ksLookup (...) . More...
 
int opmphmPredictorIncCountBinarySearch (OpmphmPredictor *op, size_t n)
 Increases the counter when the Binary Search was used for the ksLookup (...) . More...
 

Variables

const uint16_t opmphmPredictorHistoryMask
 Order Preserving Minimal Perfect Hash Map Predictor. More...
 
const size_t opmphmPredictorActionLimit
 The opmphmPredictorActionLimit define the minimum KeySet size necessary for predictor actions.
 

Detailed Description

Defines for the Order Preserving Minimal Perfect Hash Map Predictor.

Enumeration Type Documentation

◆ predictorflag_t

OpmphmPredictor Flags.

Enumerator
OPMPHM_PREDICTOR_FLAG_MMAP_STRUCT 

OpmphmPredictor struct lies inside a mmap region. This flag is set for OpmphmPredictor structs inside a mapped region. It prevents erroneous free() calls on these OpmphmPredictors.

OPMPHM_PREDICTOR_FLAG_MMAP_PATTERNTABLE 

OpmphmPredictor patternTable lies inside a mmap region. This flag is set for OpmphmPredictor patternTables inside a mapped region. It prevents erroneous free() calls on these patternTables.

Function Documentation

◆ opmphmPredictor()

int opmphmPredictor ( OpmphmPredictor *  op,
size_t  n 
)

Predictor functions.

Predictor functions.

Uses the opmphmPredictorWorthOpmphm (...) to check if the previous sequence of ksLookup (...) invocations without alteration was worth using the OPMPHM. Updates the state with the predictionAutomata and the worth information of the previous history. Alters the history with the worth information and makes the prediction for the next sequence of ksLookup (...) invocations.

Parameters
opthe Predictor
nthe number of elements in the KeySet
Return values
1it is worth using the OPMPHM
0it is not worth using the OPMPHM

◆ opmphmPredictorCopy()

void opmphmPredictorCopy ( OpmphmPredictor *  dest,
OpmphmPredictor *  source 
)

Make a copy of the OpmphmPredictor.

Parameters
sourcethe OpmphmPredictor source
destthe OpmphmPredictor destination

◆ opmphmPredictorDel()

void opmphmPredictorDel ( OpmphmPredictor *  op)

Deletes the OpmphmPredictor.

Clears and frees all memory in OpmphmPredictor.

Parameters
opthe OpmphmPredictor

◆ opmphmPredictorIncCountBinarySearch()

int opmphmPredictorIncCountBinarySearch ( OpmphmPredictor *  op,
size_t  n 
)
inline

Increases the counter when the Binary Search was used for the ksLookup (...) .

Prevents also an endless Binary Search usage by a simple heuristic.

Parameters
opthe Predictor
nthe number of elements in the KeySet
Return values
1it is worth using the OPMPHM
0it is not worth using the OPMPHM

◆ opmphmPredictorIncCountOpmphm()

void opmphmPredictorIncCountOpmphm ( OpmphmPredictor *  op)
inline

Increases the counter when the OPMPHM was used for the ksLookup (...) .

Parameters
opthe Predictor

◆ opmphmPredictorNew()

OpmphmPredictor* opmphmPredictorNew ( void  )

Basic functions.

Basic functions.

Reserves for all possible values of opmphmPredictorHistoryMask two bits to store all 4 states of the Prediction Automata A2. Sets the initial state to 0.

Return values
OpmphmPredictor* success
NULLmemory error

◆ opmphmPredictorWorthOpmphm()

size_t opmphmPredictorWorthOpmphm ( size_t  n)
inline

Heuristic function.

Heuristic function.

This easy and fast computable heuristic function tells how many ksLookup (...) invocations without alteration of the KeySet need to be made to justify the OPMPHM usage. This heuristic function is developed and measured by benchmarks.

Parameters
nthe number of elements in the KeySet
Return values
size_tthe heuristic value

Variable Documentation

◆ opmphmPredictorHistoryMask

const uint16_t opmphmPredictorHistoryMask
extern

Order Preserving Minimal Perfect Hash Map Predictor.

A modified Global History Register and Global Pattern History Table branch prediction algorithm from

Tse-Yu Yeh and Yale N. Patt "Alternative Implementations of Two-Level Adaptive Branch Prediction" In: The 19th Annual International Symposium on Computer Architecture (1992), pp. 124-134

Maps the event of branch taken or not to a sequence of ksLookup (...) invocations without KeySet alteration that is worth using the OPMPHM or not. The predictor looks at past events to predict the future, to keep track of past events the lookupCount and the ksSize must be stored. opmphmPredictorHistoryMask defines the length and extraction mask of the global history register interpreted binary it must be a series of 1, with a minimum value of 0x3 and a maximum value of 0x7FFF.

Order Preserving Minimal Perfect Hash Map Predictor.