Skip to content

Instantly share code, notes, and snippets.

@vyzo
Created January 15, 2018 17:00
Show Gist options
  • Save vyzo/e3c9c13cbe4b72c148ce1149a0014077 to your computer and use it in GitHub Desktop.
Save vyzo/e3c9c13cbe4b72c148ce1149a0014077 to your computer and use it in GitHub Desktop.
generic-cache-lookup
;; The cache is a perfect hash table represented as a vector containing
;; cache entries. A cache entry is an inverted arg type id improper list
;; terminating to the the method procedure.
;; This allows for lock-free allocation-free recursive lookup
;; and reasonably fast dispatch
(def (generic-cache-lookup cache args)
(def (lookup hash rest)
(match rest
([arg . rest]
(let* ((tid (generic-type-id arg))
(hash (##fxxor hash (##symbol-hash tid))))
(match (lookup hash rest)
([xtid . xrest]
(and (##eq? tid xtid)
xrest))
(else #f))))
(else
(let* ((len (##vector-length cache))
(ix (##fxmodulo hash len)))
(##vector-ref cache ix)))))
(let (proc (lookup 0 args))
(and (##procedure? proc) proc)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment