Index mapping

Index mapping is a computer science term (also known as a "trivial hash function") that is used to describe the mapping^{[clarification needed]} of raw data, used directly as in array index, for an array. The technique can be most effective for mapping data with a small range^{[clarification needed]}. If the array encompasses all combinations of input, a range check is not required.

Applicable arrays

In practice there are many examples of data exhibiting a small range of valid values all of which are suitable for processing^{[clarification needed]} using a trivial hash function including:

month in the year (1–12) – see C examples below
day in the month (1–31)
day of the week (1–7)
human lifespan^{[clarification needed]} (0–130) – e.g. lifecover actuary tables, fixed term mortgage
ASCII characters ^{[clarification needed]} (0–127), encompassing common mathematical operator symbols, digits, punctuation marks and English language alphabet
EBCDIC characters ^{[clarification needed]} (0–255)

Examples

The following two examples demonstrate how a simple non-iterative table lookup, using a trivial hash function, can eliminate conditional testing & branching completely thereby reducing instruction path length significantly. Although both examples are shown here as functions, the required code would be better inlined to avoid function call overhead in view of their obvious simplicity.

C example 1

This example^[1] of a C function – returning TRUE if a month (x) contains 30 days (otherwise FALSE), illustrates the concept succinctly

 if ((unsigned)x > 11) return 0;                    /*x>12?*/                                                 
 static const int T[12] ={0,0,0,0,1,0,1,0,0,1,0,1}; /* 0-based table 'if 30 days =1,else 0'  */
 return T[x];                                       /* return with boolean 1 = true, 0=false */

C example 2

Example of another C function – incrementing a month number (x) by 1 and automatically resetting if greater than 12

                                            
 static const int M[12] ={2,3,4,5,6,7,8,9,10,11,12,1}; /* 1-based table to increment x          */
 return M[x];                                          /* return with new month number          */

References

^ "A Superoptimizer Analysis of Multiway Branch Code Generation" by Roger Anthony Sayle

External links

A Superoptimizer Analysis of Multiway Branch Code Generation by Roger Anthony Sayle

[1] "A Superoptimizer Analysis of Multiway Branch Code Generation" by Roger Anthony Sayle

[1]