From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Israelsson Tampe Newsgroups: gmane.lisp.guile.devel Subject: hashtables Date: Wed, 6 Apr 2022 14:16:12 +0200 Message-ID: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000742d7905dbfb5466" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="31047"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Wed Apr 06 14:16:42 2022 Return-path: Envelope-to: guile-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nc4aV-0007im-Cm for guile-devel@m.gmane-mx.org; Wed, 06 Apr 2022 14:16:39 +0200 Original-Received: from localhost ([::1]:40514 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nc4aT-0003AI-Tb for guile-devel@m.gmane-mx.org; Wed, 06 Apr 2022 08:16:37 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:52816) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nc4aJ-0003A8-8l for guile-devel@gnu.org; Wed, 06 Apr 2022 08:16:27 -0400 Original-Received: from mail-pf1-x433.google.com ([2607:f8b0:4864:20::433]:43997) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nc4aH-0001Ea-GZ for guile-devel@gnu.org; Wed, 06 Apr 2022 08:16:26 -0400 Original-Received: by mail-pf1-x433.google.com with SMTP id x16so2273542pfa.10 for ; Wed, 06 Apr 2022 05:16:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:from:date:message-id:subject:to; bh=JQcBW0KE1DQGpQwRFc9AsYnK2tNt3czVngDWMFxUs08=; b=oq1/jGyoZecX88k0DQVQULvIjt8GPLcOiHKde6yh3dQdORtOspbjunNw51H7/0y3n/ qtHs+fK3khok2a/F4R9GNgqvGWtVvKrkPqLnxQpqoXD5y86qVRqADGZ+l0ZHddPzh0Pe sp23AW41PkC8ZKiP3mW2zUjkl+271JcB23hSeMYxuBYwRYyy5L5lOUpxikb4SBcBgfQk GEDCmzsq42LkEJWiShB0IVNIGtbnVOOgUPeD0tfrYUKuy/j5fDoEYQ/nYb2/G9jaVdNR 9tnnyeOURTc8XzfNmW35hSbURkmRRjw/nuLcT8XZzR0Vbr8BHV2KLiPYpKmZxzvQiH/H aNzA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=JQcBW0KE1DQGpQwRFc9AsYnK2tNt3czVngDWMFxUs08=; b=kZ8zRMAI1SrUZKe9fJzJTe9g6pCb+mfJZkezitVN3rxRuz3pb6Oo9Qz98Ial2RDt2Y gbAwTPSGJdW6TbqVuvRJbTLBHrJA51vG5BvVRSaj4fzAs+UDHmCP4rTHJ3jo+2zttQuS VQJdzUE/1uBhhuEO6Y3c5oGM0epMCTS3rkh0QZ9xR12Dq7upnrTfZS5F+dAFLQ2pNXFD LbwDu13xG5J4O3cP8nhQMJt3kIr0GeVR82LTPVgi0m8UcSKat5Sw2KZBvIYvOAESooBR zSuAp1JG34rP/IW7+WfAIHAuf6YfgZLNdyY0j7EaGTFM7u5V5Xyy8rOLL1VURotnwvK2 42mw== X-Gm-Message-State: AOAM531vvY85612EMewHMUP9luuVuTQkNKSzbyzeoD2A9dcRnfuj/zd8 duEJH8Xa1+07lDiHzP+OrvCx2woSII6geHRPCS20ffAMnH8= X-Google-Smtp-Source: ABdhPJyeDUC8kgRgATNYzFvMSSGmdXQ6DO/W07rfvcfp/a3CjPhIwf6o+nb0XeW8RHBHBbyWfZNOwgYhBWWcg8SaZWo= X-Received: by 2002:a63:447:0:b0:399:58c5:2cc2 with SMTP id 68-20020a630447000000b0039958c52cc2mr6943633pge.592.1649247383726; Wed, 06 Apr 2022 05:16:23 -0700 (PDT) Received-SPF: pass client-ip=2607:f8b0:4864:20::433; envelope-from=stefan.itampe@gmail.com; helo=mail-pf1-x433.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.io gmane.lisp.guile.devel:21188 Archived-At: --000000000000742d7905dbfb5466 Content-Type: text/plain; charset="UTF-8" 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) --000000000000742d7905dbfb5466 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi all,=C2=A0

After optim= ising the hashtable implementation I conclude the following,
1. + 0.25s=C2=A0 10M lookups in small hashtable= =C2=A0 (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.=C2= =A0+ fast (2X) for relative large random working sets although the hashtabl= e 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 strate= gies where integers just translate to integers.

This uses a d= atastructures=C2=A0that take advantage of SIMD instructions to quickly=C2= =A0find matches and vacant slots. Also an lru strategy is included for spee= dup 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 high= er level primitives.

<= /div>
Let me know if you want to have this sup= ported in guile as I have defined some vm operations that are needed else t= his will be about 1.5 2x slower on small hashtables.

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

;; stis-b-search v is hashtable, k is key, h= is hashvalue eq
;; the eqality p= redicate, stis-e-ref is the underlining lru
;; VM instruction used to lookup most (key . value)
(define-i= nlinable (stis-c-ref v k default h eq)
=C2=A0 (define (slow-ref) (stis-d= -ref v k default h eq))
=C2=A0 =C2=A0 (aif it (stis-e-search v h)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(if (pair? it)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0(if (eq (car it) k)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0it
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0(slow-ref))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0(slow-ref))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 default)= )
=C2=A0
;; This is the slow s= et where one needs to cons the pair
;; on the last slot that is the assoc
(define (stis-d-set! v k val h = eq)
=C2=A0 (let ((l (stis-b-alist-ref v h)))
=C2=A0 =C2=A0 (let lp ((= ll l))
=C2=A0 =C2=A0 =C2=A0 (if (pair? ll)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 (let ((it (car ll)))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0(if (eq k (car it))
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0(begin
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 (set-cdr! it val)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 it)
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(lp (cdr ll))))
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0(let* ((it (cons k val))
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0(l =C2=A0(cons it l)))
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0(stis-b-alist-set! v h l)
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0it)))))

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

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

--000000000000742d7905dbfb5466--