Hash-tables

As I'm working with some memoization-macro in LISP, I turned on a performance-issue I've not really worked much with:

To make a general macro for memoization, I'm using hash-tables. If the value's already calculated before, it would be found in the hash-table. If it's not found, it will calculate the value and add this into the hash-table afterwards. Great stuff for recursive functions.

So, here's the thing: For multiple values in a memoization-function, would it be more handy to make hash-tables like this:

function (a, b, c):

 Hash-Table

 A = 1

 B = 1

 C = 1

65

 C = 2

874

 C = 3

5151

 B = 2

 C = 1

95

 C = 2

36

 C = 3

98

 B = 3

 C = 1

82

 C = 2

69

 C = 3

65

 A = 2

 B = 1

 C = 1

28

 C = 2

79

 C = 3

92

 B = 2

 C = 1

9338

 C = 2

298

 C = 3

98

 B = 3

 C = 1

197

 C = 2

287

 C = 3

982

 A = 3

 B = 1

 C = 1

9287

 C = 2

928

 C = 3

356

 B = 2

 C = 1

356

 C = 2

324

 C = 3

247

 B = 3

 C = 1

527

 C = 2

275

 C = 3

25

Or like this?

 Hash-Table

 1 1 1

65

 1 1 2

874

 1 1 3

5151

 1 2 1

95

 1 2 2

36

 1 2 3

98

 1 3 1

82

 1 3 2

69

 1 3 3

65

 2 1 1

28

 2 1 2

79

 2 1 3

92

 2 2 1

9338

 2 2 2

298

 2 2 3

98

 2 3 1

197

 2 3 2

287

 2 3 3

982

 3 1 1

9287

 3 1 2

928

 3 1 3

356

 3 2 1

356

 3 2 2

324

 3 2 3

247

 3 3 1

527

 3 3 2

275

 3 3 3

25

I would assume the first one would be the fastest. However, the thing here is that this is no 3d-array, this is a hash-tree. If I e.g. test out a new value here, say:
function (4, 1, 2);

To gather the information if existing, it will look if there's a key in the hash-table for A = 4. If this returns a hash-table, it will look if there's a hash-table for B = 1. If there is a hash-table for this value, it will then look for a result for C = 2. If there is, returns that value. If not, do the following:

Create a new hash-input in the first hash-table. Now, it has to create a new hash-table, and then a new hash-input in this new hash-table. Finally, it has to create a new hash-table and a new hash-input in this table, which will hold the answer when computed.

The other way would be to check if there's a hash-key 4 1 2 in the hash-table. If not, makes this hash-key and computes value for the function.


Now, what would be the fastest? Creating the hash-tables would take some time, but then again, looking up a value in a bigger hash-table would also take some time. What would take the most time?

errr...I would *think* the second would be faster since you're doing 1 lookup instead of 3. In a properly implemented hash table with a good hash function, lookup is O(1) with the size of the table.

If you're not sure, measure. Measure before optimizing to see if you even need to optimize, and measure after to make sure it actually makes it faster.

Premature optimization is the root of all evil.

errr...I would *think* the second would be faster since you're doing 1 lookup instead of 3. In a properly implemented hash table with a good hash function, lookup is O(1) with the size of the table.

If you're not sure, measure. Measure before optimizing to see if you even need to optimize, and measure after to make sure it actually makes it faster.

Heck, I tested it out. Adding up 1 random value not used in the fibonacci-function (fib (n x)), tested out the efficiency by looping from 1 to 100,000, with a constant x.

It seems like the second idea is 1.5 times faster than the first function, using these macros in LISP:

 Spoiler

Code:

(defmacro aif (test then &optional else) ; for defmemoiz1
    `(let ((it ,test))
        (if it ,then ,else)))

(defmacro with-gensyms (gensyms &body body)
    `(let ,(mapcar #'(lambda (s)
                    `(,s (gensym)))
                gensyms)
        ,@body))

(defmacro defmemoiz1 (fn val &body body)
    (with-gensyms (hash-lst lst elt hash get-last-hash)
    `(let ((,hash-lst (make-hash-table)))
    (labels ((,get-last-hash (hash args) ;; Creates hash if it doesn't exist. Returns value if it does.
                    (if (cdr args)
                        (,get-last-hash
                            (aif (gethash (car args) hash) it
                                (setf (gethash (car args) hash) (make-hash-table)))
                            (cdr args))
                        (gethash (car args) hash))))
(defun ,fn ,val
    (or
        (,get-last-hash ,hash-lst (list ,@val))
    (setf     ;; Supposed to get from the val-list the following
            ;; If args = (2 8 9 3), then this part should be (gethash 2 (gethash 8 (gethash 9 (gethash 3 hash-lst))))
        ,(labels ((recursive-hash (args)
            (list 'gethash (car args)
                (if (cdr args)
                    (recursive-hash (cdr args))
                    hash-lst))))
            (recursive-hash (eval `(reverse ',val))))
        ,@body)))))))


;; For multiple values
(defmacro defmemoize (fn val &body body)
    (with-gensyms (lst hash-code)
    `(let ((,lst (make-hash-table :test #'equal)))
        (defun ,fn ,val
        (let ((,hash-code (list ,@val)))
            (or
                (gethash ,hash-code ,lst)
                (setf (gethash ,hash-code ,lst)
                    ,@body)))))))

Then using them on the function:

 Spoiler

Code:

(defun fib (n)
    (if (<= n 2) ; first two = 1
        1
        (+ (fib (1- n))
           (fib (- n 2)))))

Just replacing defun with defmemoiz1 and defmemoize to make the functions memoizing. (Guess what, I used another macro to simplify redefining of the fibonacci-function. Sigh.)

For several values, time increased exponentially. For 8 different values, it took almost 4 times longer to calculate compared to the second idea. For 3, time barely changed. For one value, time was the same. (But then again, for one value, I make another kind of hash-table, which increases the speed noticeably.)

Since your question largely summarizes the competition between breadth first and depth first branching, I highly recommend you do some research on each form of branching to determine which will be the best method for your particular situation. Each type of branching has its unique advantages and disadvantages.

errr...I would *think* the second would be faster since you're doing 1 lookup instead of 3. In a properly implemented hash table with a good hash function, lookup is O(1) with the size of the table.

Main costs of hash table are overfull (lots of collisions -> slower lookup) or resizing (may have to recalculate all keys)

If you know how big it'll be, as in the given example, it won't be a problem. I'm not sure splitting into smaller tables helps though, as efficient hashing avoids clumping it'll tend to have to resize all the tables anyway if they become overfull.


In terms of seek time, I think having to follow more pointers would be slower than just having a big table (key 1->value 1, value 1->table 2, key 2->value 2, value 2->table 3, key 3->value 3) or (longer key -> final value)

The 1 big table does require some concatenation to make the key, but I don't think that takes long.



otoh if you can generalize some areas to less depth (eg. all lookups with a=b=0 return 0 instead of a c hash table) then being able to cut off at an earlier depth might be better than having to look up the full string every time.