hashtables

[Stefan Israelsson Tampe <stefan.itampe@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 3271 bytes --]

Hi all,

After optimising the hashtable implementation I conclude the following,
1. + 0.25s  10M lookups in small hashtable  (0.36s for guiles current)
2. + 6X faster for a large table scanning numbers
3. + The general hash interface is faster also because it does not call SCM
from C
4. + fast (2X) for relative large random working sets although the
hashtable is large
5. - we do not suport the assoc generalisation (sort off though)
6. Compact (low memory overhead)

To note the design allows high performance for non uniform hashes e.g. we
can allow it to not spread out the hashes as optimal e.g. we can grow the
bins quite well and still maintain speed. This is especially well suited
for python hash strategies where integers just translate to integers.

This uses a datastructures that take advantage of SIMD instructions to
quickly find matches and vacant slots. Also an lru strategy is included for
speedup when the hash is large and the working set is not as large.

This is with the low level primitives. I will continue now with the higher
level primitives.

Let me know if you want to have this supported in guile as I have defined
some vm operations that are needed else this will be about 1.5 2x slower on
small hashtables.

Code:
;; This is the slow path where the bin is larger than 15
;; elements
(define (stis-d-ref v k default h eq)
  (let ((l (stis-b-alist-ref v h)))
    (let lp ((ll l))
      (if (pair? ll)
          (let ((it (car ll)))
             (if (eq k (car it))
                  it
                  (lp (cdr ll))))
          default))))


;; stis-b-search v is hashtable, k is key, h is hashvalue eq
;; the eqality predicate, stis-e-ref is the underlining lru
;; VM instruction used to lookup most (key . value)
(define-inlinable (stis-c-ref v k default h eq)
  (define (slow-ref) (stis-d-ref v k default h eq))
    (aif it (stis-e-search v h)
         (if (pair? it)
             (if (eq (car it) k)
                 it
                 (slow-ref))
             (slow-ref))
          default))

;; This is the slow set where one needs to cons the pair
;; on the last slot that is the assoc
(define (stis-d-set! v k val h eq)
  (let ((l (stis-b-alist-ref v h)))
    (let lp ((ll l))
      (if (pair? ll)
          (let ((it (car ll)))
             (if (eq k (car it))
                 (begin
                    (set-cdr! it val)
                    it)
                 (lp (cdr ll))))
           (let* ((it (cons k val))
             (l  (cons it l)))
             (stis-b-alist-set! v h l)
             it)))))

;; This is the storing of a (k . val) pair in the
;; stis hash data structure
;; if we find a handle, set it else if the key hash is
;; missmatching, store it on the assoc, else if not a match
;; add it to the list via the c-primitive stis-b-add!
(define-inlinable (stis-c-set! v k val h eq)
  (define (slow-set!) (stis-d-set! v k val h eq))
    (aif it (stis-e-search v h)
         (if (pair? it)
             (if (eq (car it) k)
                 (begin
                   (set-cdr! it val)
                   it)
                 (slow-set!))
             (slow-set!))
         (let ((it (cons k val)))
            (stis-b-add! v h it)
            it)))

Code:
see my previous post, but it's in guile-persist (gitlab)

[-- Attachment #2: Type: text/html, Size: 5078 bytes --]