McGill

Data Structure Metrics

Last updated: December 4, 2002
Sable


Dynamic metrics for program size and structure try to answer the question: how large is a program and how complex is its control structure?



Array Intensive Metrics

Many "scientific" benchmarks are deemed so because the dominant data structures are arrays. The looping and access patterns used for array operations are then expected to provide opportunities for optimization. Determining if a program is array intensive will then be a problem of determining if there are a significant, or dominant number of array accesses. Note that since Java multi-dimensional arrays are stored as arrays of arrays, the number of array access operations required for each multi-dimensional array element is magnified. To avoid skewing results, the type of element located at the array element should be inspected, and if it is an array type it should be discounted.


Back to Top


Floating-Point Intensive Metrics

Programs that do numerous floating point calculations also tend to be considered "scientific". Different optimizations apply though; including the choice of appropriate math libraries optimized for speed or compatibility, opportunities for more aggressive floating point transformations and so on. Fortunately, floating-point operations are quite rarely used in most applications that do not actually focus on floating-point data, and so identifying floating-point intensive benchmarks is relatively straightforward from a simple ratio of instruction types.


Back to Top


Pointer Intensive Metrics

Dynamic data structures are manipulated and traversed through pointers or object references. Programs that use dynamic data structures are thus expected to perform a greater number of object dereferences than a program which uses arrays as primary data structures; a basic metric can be developed from this observation. Of course a language such as Java which encourages object usage can easily skew this sort of measurement: an array-intensive program that stores array elements as objects (e.g., Complex objects) will result in as many object references as array references.


Back to Top