tracking if a result has already been computed using hash table

Question

My application would perform a large number of matrix operations (e.g., add/ multiply) on dense matrices. I would like to cache unique results in order to avoid duplicate computations.

Dense matrix:

typdef struct denseMatrix{
 int m;
 int n;
 double **d;            // actual matrix
 multiplyTable **entry; // key & result
} dns;

Table-entry:

typedef struct multiplyTable{
 dns *rightOperand; // key
 dns *result;       // value
} multiplyTable;   // or something like that

dns *A, *B, *C, *D...; // allocated internally

C = mult(A,B); //may be called many many times.

In this case, mult would add an entry (operand, result) pair to the table

add(A->entry, B, C); //B is the right operand and C is the result

Later if D = mult(A, B) were to be called again, search(A->entry,B) would retrieve C. If on the other hand, the specific operand is not in the list, it would be added along with the pointer to the result matrix.

I have never done anything like this before and I am not even sure if this is the way to approach the problem. From my limited understanding, hash-tables may be used to implement something like this.

Among the practical questions I have are: (a) Is hash-table the appropriate solution to the problem in the first place? Do they allow pointer addresses as keys and values??

(b) Does it make sense to keep the "hash-table" as a "field" in the struct? That way, I already have the left operand, I just need to search for the rightOperand in the multiplication table. Or, should there be an independent table with both the left and right operands as keys?

(c) Do I create separate tables for addition/multiplication etc., or should there be a single table, with operands and operators?

(d) Wht would be the best way of keeping track of all the objects that are created so that these could be freed appropriately??

(e) What publicly available library (in c) would be suitable for implementing something like this?

I am seeking input/suggestions regarding (a) alternative ways in which the problem could be approached, and (b) advantages/disadvantages of such alternatives.

Lastly, I have found this forum to be immensely helpful and wanted to express my gratitude. ++Thanks.

Answer 1

You have to be very careful with hashes. If you have a collision (same hash value for different original values) you may end up with wrong results. Are you sure that calculating hash of a matrix will be much more efficient than performing the actual operations (it all depends on the number/complexity of these operations obviously)

Second concern - you haven't said anything about your cache eviction policy. Are you going to just add to the hash table without removing? Depending on the number of different matrices you potentially may run out of memory...

Answer 2

Answering the easy part first: For a C++ library of matrix operations have a look at newmat which has a large range of functionality built-in, and performance-wise is pretty efficient.

For your specific case of building a hash to speed up computations - caching is only worthwhile unless you are going to be performing operations on a very limited set of matrices. To build a unique hash for the matrix you will need to visit every entry - and calculate the hash based on each entry's location and value. Worse still, matrices are not always commutative, e.g. A*B != B*A except in special cases.

This means your cache would have to store one entry for each specific calculation. So unless you're dealing with a very small range of input matrices the memory cost of holding all the results will be huge.

1. For very small matrices or column/row vectors, the marginal overhead of the full computation vs. calculating a hash is tiny... so caching will offer little extra benefit unless you are doing so many calculations that fractions of a millisecond difference in time will accumulate enough to make a difference.
2. For very large matrices, it's possible that you could see a benefit from caching if your possible input matrices are very limited. If they could be anything, the likely benefit is outweighed by the rarity of getting a repeat strike on the cache, as well as the memory cost and complexity of managing the cache.

Caching would speed up the results, but only in a very limited set of circumstances.

Given that you've asked for advice on a library as well, this sounds like a case of premature optimisation. I would implement your program without caching, performance profile it, and if you find a performance bottleneck in the array arithmetic, then consider ways to optimise the number crunching.

Edit: on calculating the hash: if you have a n-by-m matrix X, then calculating the hash for that one matrix is at least as complicated as the operation R*X*C where R is the row vector [1,..,n] and C is the column vector [1,..,m]. I haven't worked out the optimal payoff, but for really small matrices on the order of 2x2, 3x3 doing the raw calc is going to be cheaper than calculating the hash.

Answer 3

This feature is called memoization - see wikipedia article for details.

This article also mentions some libraries that can help you.