|Array Internals (Advanced)|
This is a header only library that provides support for fixed/variable size single and multidimensional arrays. It provides specialized functions for small and large vectors and matrices and general arrays through a unified interface and intuitive syntax.
The following are the design goals for the array library:
An array of fixed size can be declared by providing the signature of the array as the template argument of the class lite::array. For example:
array<float> a; for (int i=0; i<10; i++) for (int j=0; j<10; j++) m(i, j) = i+j; std::cout << m << std::endl;
For arrays with non-constant dimension sizes, one can specify 1 as the size of the dimension with non-constant size. For example:
int n; std:::cin >> n; array<float> a(n, 4, 4); std::cin >> a; // read the array from std::cin
Most of the mathematical operations that make sense for arrays are also defined. For example:
array<float> a, b, c; // ... c += 1.5*a + 3*b + 1;
Matrix and vector operations are defined for 1 and 2 dimensional arrays. Specialized operations are also provided for arrays and vector of length 2 and 3 (i.e. 2d and 3d geometric operations).
array<float> m; array<float> v1, v2; // ... v2 += m*v1 + v2+ 1.5; // matrix-vector multiplication m = m*m; // matrix-matrix multiplication m = inverse(m); // matrix inverse float d = det(m); // matrix determinant m = rotation(v2, 3.14); // rotation matrix of 180 degrees around v2 v1 = m*v1; // rotate v1 v3 = v1%v2; // compute the cross product of v1 and v2 float inner = v1*v2; // inner product // etc ...
A rich set of transformations are also provided along with an extensible framework to add new types of transformations. For example:
array<float> a; array<float> m1, m2, m3; array<float> v1; // ... for (int i=0; i<10; i++) for (int j=0; j<10; j++) m3(i, j) = m1[row(i)]*m2[column(j)]; m2[transpose()] = m3; m1 = 0; m1[diagonal()] += 1; // add 1 to the diagonal of m1 a[row(2)] += 4*a[row(3)]+1; // add 4 times the row 3 plus 1 to row 2. Each row is actually a 10x10 array. a[row(2)] += (4*a+1)[row(3)]; // this is as efficient as the previous line due to to lazy evaluation. block<5,0,0> blk; // specifies a vector of size 5 along the first dimension // while dropping the other two dimensions a[blk(2,3,4)] += v1; // the block will start at index (2,3,4). // The result of the left hand side is a reference vector of size 5. int k; std::cin >> k; block<0,1,1> blk(0,k,k); // specifies a k by k matrix on the 2nd and 3rd dimensions // while dropping the first dimension a[blk(2,2,2)][diagonal()] += 1; // adds 1 to the diagonal of the k by k matrix at index (2,2,2) after // dropping the first dimension
The library uses lazy evaluation where feasible. For example the expression 1.5*a+3*b+1 does not evaluate the result by itself. It, however, returns a reference array such that when it is evaluated at any point it will evaluate the result at that point on demand. The library is aware of the evaluation costs and will use a temporary array to make copies of its arguments when doing so will improve the performance. For example:
int n; std::cin >> n; array<float> m1(n,n), m2(n,n), m3(n,n); array<float> v1(n), v2(n); // ... m3 = m1*m2; // m1 is used directly but m2 is copied to a local column-major matrix // to utilize cache (m2 is row-major) m3 = m1*m2[transpose()]; // m1 is row major and m2 column major so they are used directly. m3 = (2*m1+1)*m2; // (2*m1+1) is fully evaluated first. m3 = (2*m1+1)*m2[column(0)];// (2*m1+1) is evaluated lazily on demand but m2[column(1)] // is fully evaluated and cached because its elements are not adjacent // in memory and may not utilize cache well. v1 = (2*v21+1)*m2[column(0)];// no local copy is made. Both arguments of * are evaluated lazily on demand.
It is also aware of the storage order of the element of the arrays involved in an expression. It tries to evaluate the expressions in the order that maximizes CPU cache utilization.
The library is heavily specialized and optimized to take advantage of fixed sizes and compile time information and adds zero or minimal overhead. For example an object of type array<int> contains only a fixed size array of size 2. In other words, sizeof(array<int>)==sizeof(int). So, it is a light weight object that for example can be used to represent a coordinate in a 2D space. The library takes advantage of the fixed sizes also to unroll the loops whenever possible using meta-template technics. The library has been designed to aid the compiler in optimization as much as possible. The performance of the code produced by this library using a good optimizing compiler (e.g. MSVC++ 8) is the same as the performance of an optimized handwritten code using primitive arrays. See array_performance for more information.
A general multi-dimensional array can be represented by a multi-dimensional random access iterator pointing to the start of the array and a size tuple specifying how much the array extends along each dimension. The random access iterator should be capable of moving freely in every dimension.
In order to use the library effectively, it is helpful to have an understanding of the internal representation of arrays.
The rest of the introduction is organized as follows:
In order to use the library effectively, it is helpful to have an understanding of the internal representation of arrays. The following section provide a brief introduction to the internals of the library:
In order to change the limits of the library (e.g. to increase the maximum number of dimensions supported, etc) and/or to regenerate the header file from the template file, you should read the following section:
To get more information on the performance of this library and various kinds of optimization that are incorporated see the following section: