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: hashtable higher order interface Date: Thu, 7 Apr 2022 22:50:37 +0200 Message-ID: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000033c8c05dc16a2e2" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="25327"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Thu Apr 07 22:51:31 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 1ncZ6I-0006Lh-Rp for guile-devel@m.gmane-mx.org; Thu, 07 Apr 2022 22:51:30 +0200 Original-Received: from localhost ([::1]:39816 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ncZ6H-0005Rp-H2 for guile-devel@m.gmane-mx.org; Thu, 07 Apr 2022 16:51:29 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:33004) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ncZ5h-0005RU-BO for guile-devel@gnu.org; Thu, 07 Apr 2022 16:50:53 -0400 Original-Received: from mail-pl1-x633.google.com ([2607:f8b0:4864:20::633]:39728) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ncZ5f-0006nq-ET for guile-devel@gnu.org; Thu, 07 Apr 2022 16:50:53 -0400 Original-Received: by mail-pl1-x633.google.com with SMTP id f10so6104185plr.6 for ; Thu, 07 Apr 2022 13:50:50 -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=b+jPHzmcA0HxGI2XjfgEWmMQo685RsEDTCe39KlTis4=; b=fkj79lO/gFHZO69WNnWchVum9Tjg+ynPtntRCtW2Q+57ELZFTg0p2Aop/h6BIBFlsu G6jCuAcchEP5H2cbiH84yZqmN5WBccVjbeyxlIwgg9QzAx44tZ0MqNOjH1ctykdyzy67 Vmq263+7/mRNjCILh+Klvnj/Jau3kalSSzvdeetahAVegpp9w0Cijfn9DsQyq+zUccbT w9YZdrcC7T0A6xGEAI7XoAkHZcd5F1gcETF3dY3Tv4QsKYXigfMccThc5ugiaMOK3DYo iOzqM68q6mPEriRLPjT5Evo4Qf6i4x2IuxRF9G818UTl0m+hsZBU4OBZGdUpe5WFZ1uL gz1A== 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=b+jPHzmcA0HxGI2XjfgEWmMQo685RsEDTCe39KlTis4=; b=V7OvxN3/IGUEjCUr/xRToeW70hWqLUBRLkzqshgfolcJywAWzSKxyUe2bY4SYQIUoP NzEBl/bHEatqRLJYrPoYTSdmErrFGqhuj/Jvv1UXZrhpg/nfBZ8wwkdCOg+xg5V5U7dJ tCaxuHhRNkL9xMRWl2OrgfiDJ+G6CGWlCT+QdTSVU0CUOSYZr8GslKrS9K7CMORag3LZ tJ0fgjem9l+IlzH4QBI+MEQTDX01LUMP47cIOI9rq/XagLhI0n/sb3rnXMvx3CHdSDj3 ZDiD8uLxksVJEkTMXW34qibHbDAzlYiHbUd1ckOghWtOap9wgQRSbMQ0mxScN7MHBFjY F+Sg== X-Gm-Message-State: AOAM532o68bkyau2XB/bjhgpy0y0qThEXP1D6NbmbzWt4+r+r/7K0gOU 3LFl7yL1KV/BNfDceZHl0/RvAt4dMnvZqlhYSKuJQf2ITXc= X-Google-Smtp-Source: ABdhPJx8J1xDfAkGFcR6XAGIWrrRYkux+Rj953aPsYTc9QzTc7qNPTlVFWokQxutsXBsD90eo+obntbL2VTt7T76Mh8= X-Received: by 2002:a17:90b:1642:b0:1c7:2497:3807 with SMTP id il2-20020a17090b164200b001c724973807mr17804403pjb.176.1649364649064; Thu, 07 Apr 2022 13:50:49 -0700 (PDT) Received-SPF: pass client-ip=2607:f8b0:4864:20::633; envelope-from=stefan.itampe@gmail.com; helo=mail-pl1-x633.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:21190 Archived-At: --000000000000033c8c05dc16a2e2 Content-Type: text/plain; charset="UTF-8" ;; First of some benchmarking to show of some code (define n 10000000) (define (test) (with-stis-hash ((h ref)) (let lp ((i 0) (s 0)) (if (< i n) (lp (+ i 1) (+ s (ref h (modulo i 1000)))) s)))) (define (test2) (let lp ((i 0) (s 0)) (if (< i n) (lp (+ i 1) (+ s (hashq-ref H (modulo i 1000)))) s))) scheme@(guile-user)> ,time (test) $11 = 4995000000 ;; 0.268354s real time, 0.268264s run time. 0.000000s spent in GC. scheme@(guile-user)> ,time (test2) $12 = 4995000000 ;; 0.448963s real time, 0.448837s run time. 0.000000s spent in GC. Nice eh! ------------------------------------------------ API ------------------------------------------------ ;; Load the module, (use-modules (ice-9 stis-hash)) ;; Anyhow to create a stis hash table you need to use, (define m (make-stis-hash-table 'hashq 10000 #:name 'test)) ;; pre defined types are 'hashq 'hashv and 'hash ;; we can make a new type by (define myhash (lambda (x) (logxor (hashq x 10) (hashv x 10)))) (make-stis-hash-type 'my myhash equal?) ;; and use it by (define m (make-stis-hash-table 'my 10000 #:name 'test)) ;; We have stis-hash-ref stis-hash-set! stis-hash-remove! ;; which is similar to the guile interface. But in order to ;; be fast us with-stis-hash like (with-stis-hash ((h ref )) code ...) (with-stis-hash ((h ref set )) code ...) (with-stis-hash ((h ref set rem)) code ...) ;; we can use _ to indicate that this part is not used, ;; the the interface is the same as other hash accessors ;; but the hash-table is implicit and remeved as argument ;; Finally we can loop using functional constructions like stis-hash-for-each stis-hash-fold stis-hash-map ;; which are much much faster than guile vanilla hashes and ;; uses only pure scheme This uses a modified guile with v, instructions for hash-ref parts and hash calc functions. In that guile branch I also have the one shot continuation code as well. Refereces: https://gitlab.com/tampe/guile-persist/-/blob/master/ice-9/stis-hasch.scm https://gitlab.com/tampe/guile-persist/-/blob/master/src/hash/work.c --000000000000033c8c05dc16a2e2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
;; First of some benchmarkin= g to show of some code
(define n 10000= 000)
(define (test) =C2=A0
=C2=A0 (with-stis-hash ((h ref))
=C2=A0= =C2=A0 (let lp ((i 0) (s 0))
=C2=A0 =C2=A0 =C2=A0 (if (< i n)
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 (lp (+ i 1) (+ s (ref h (modulo i 1000))))<= br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0s))))

(define (test2)=C2=A0 (let lp ((i 0) (s 0))
=C2=A0 =C2=A0 (if (< i n)
=C2=A0 =C2= =A0 =C2=A0 =C2=A0 (lp (+ i 1) (+ s (hashq-ref H (modulo i 1000))))
=C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0s)))

sch= eme@(guile-user)> ,time (test)
$11 =3D 4995000000
;; 0.268354s real time, 0.268264s run time. =C2=A00.000000s spent in GC= .
scheme@(guile-user)> ,time (test2)
$12 =3D 4995000000
;; 0.448963s real time, 0.448837s run time. =C2=A00.000000s spent in GC= .

Nice eh!=
--------------------------= ----------------------
API
-------------= -----------------------------------
;; Load the module,
(use-modules (ice-9 st= is-hash))

;; Anyhow to create a stis hash table you need to use,
<= span style=3D"font-family:monospace">(define m (make-stis-hash-table 'h= ashq 10000 #:name 'test))

;; pr= e defined types are 'hashq 'hashv and 'hash

;; we can make a new type by
(define myhash=C2=A0(lambda (x) (logxo= r (hashq x 10) (hashv x 10))))
(make-stis-hash-type 'my=C2=A0 myhash equal?)

=
;; and use it by
(define m (make-stis-hash-table 'my 10000 #:name 'test))

;; We have
stis-hash-ref
stis-hash-set!
stis-hash-remove!

<= div>;; which is similar to the guile = interface. But in order to=C2=A0
;; be fast us with-stis-hash like
(with-stis-hash ((h ref=C2=A0 =C2=A0 =C2=A0 =C2= =A0 )) code ...)
(wi= th-stis-hash ((h ref set=C2=A0 =C2=A0 )) code ...)
(with-stis-hash ((h ref set rem)) code ...)

;; we can use _ to indicate that this part is not used,
;; the the interface = is the same as other hash accessors
;; but the hash-table is implicit and remeved as argument

;; Finally we can loop using functio= nal constructions like
stis-hash-= for-each
stis-hash-fold
stis-hash-map

;;= which are much much faster than guile vanilla hashes and=C2=A0
;; uses only pure scheme

This uses a modified guile with v, instructions for ha= sh-ref parts and hash calc functions. In that guile branch I also have the = one shot continuation code as well.

Refereces:



=
--000000000000033c8c05dc16a2e2--