Hi,
While trying to improve speed of a function which receives millions of
repetitive identical calls I realized that memoization is quite
promising for my situation. Furthermore, instead of issuing a (make-
hash-table :test #'equal) and using (gethash (cons arg0 arg1) cache),
I thought using a hash function for arg0/1 couple would perform better
than an EQUAL comparison. And after some more CPU cycles, I realized
that I can use a vector instead of the hash-table while I have unique
integer hash signatures produced for each input. And suprisingly
switching from hash-table to vector, reduced 80% of the runtime
overhead in SBCL 1.0.16. But I still think I can make vector access
perform better by removing redundant array elements:
MVG> (defparameter *tmp*
(loop for i below 500
nconc (loop for j below 500
collect (commutative-hash i j))))
*TMP*
MVG> (reduce #'max *tmp*)
255987
MVG> (length (remove-duplicates *tmp*))
125250
Because of COMMUTATIVE-HASH can return 255987, I need to create a
vector of 255987+1 elements. But on the other hand, I know that there
is only 125250 elements. Namely, 50% of the heap space is totally
wasted, and makes AREF perform worse. My current COMMUTATIVE-HASH
looks like below:
(let ((shift-offset (integer-length +input-pool-size+)))
(defun commutative-hash (u v)
(declare (optimize speed)
(type (integer 0 +input-pool-size+) u v))
(flet ((hash (small great)
(logior (the fixnum (ash small shift-offset))
great)))
(if (< u v)
(hash u v)
(hash v u)))))
Can anybody suggest any method to skip processing of redundant array
elements? A new memoization scheme is welcome too.
Regards.
On May 22, 8:29 am, Volkan YAZICI <·············@gmail.com> wrote:
>
> Namely, 50% of the heap space is totally
> wasted, and makes AREF perform worse. My current COMMUTATIVE-HASH
> looks like below:
>
> (let ((shift-offset (integer-length +input-pool-size+)))
> (defun commutative-hash (u v)
> (declare (optimize speed)
> (type (integer 0 +input-pool-size+) u v))
> (flet ((hash (small great)
> (logior (the fixnum (ash small shift-offset))
> great)))
> (if (< u v)
> (hash u v)
> (hash v u)))))
>
> Can anybody suggest any method to skip processing of redundant array
> elements? A new memoization scheme is welcome too.
This should work to reduce the memory requirements
(flet ((hash (min max)
(+ min (/ (* max (+ max 1)) 2)))) ; triangular numbers
---
Geoff
On May 22, 8:07 pm, Geoffrey Summerhayes <·······@gmail.com> wrote:
> This should work to reduce the memory requirements
>
> (flet ((hash (min max)
> (+ min (/ (* max (+ max 1)) 2)))) ; triangular numbers
Yes it certainly did. But this time it takes pretty longer (nearly x5
times) to compute the hash. (Yep, I placed required type
acknowledgements and sustained all SBCL notes/warnings.) I need to
find a trade off between available choices.
BTW, would you mind explaining how this hash function works?
Regards.
On May 23, 2:22 am, Volkan YAZICI <·············@gmail.com> wrote:
> On May 22, 8:07 pm, Geoffrey Summerhayes <·······@gmail.com> wrote:
>
> > This should work to reduce the memory requirements
>
> > (flet ((hash (min max)
> > (+ min (/ (* max (+ max 1)) 2)))) ; triangular numbers
>
> Yes it certainly did. But this time it takes pretty longer (nearly x5
> times) to compute the hash. (Yep, I placed required type
> acknowledgements and sustained all SBCL notes/warnings.) I need to
> find a trade off between available choices.
>
> BTW, would you mind explaining how this hash function works?
Pretty straightforward, since min is less than or equal
you end up with
max\min 0 1 2 3 4 5 6 7
0 x . . . . . . .
1 x x . . . . . .
2 x x x . . . . .
3 x x x x . . . .
4 x x x x x . . .
5 x x x x x x . .
6 x x x x x x x .
7 x x x x * x x x
Taking the hash as *s position in order starting
at zero, it's just the total of the rows above it
plus how far it's over. Basic algebra.
----
Geoff