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: Hatables are slow Date: Mon, 21 Feb 2022 14:18:00 +0100 Message-ID: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000767aa405d8871010" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="36564"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Mon Feb 21 14:55:51 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 1nM9AN-0009OJ-7m for guile-devel@m.gmane-mx.org; Mon, 21 Feb 2022 14:55:51 +0100 Original-Received: from localhost ([::1]:50776 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nM9AM-0003ya-0D for guile-devel@m.gmane-mx.org; Mon, 21 Feb 2022 08:55:50 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:37222) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nM8a0-0006qT-Fg for guile-devel@gnu.org; Mon, 21 Feb 2022 08:18:17 -0500 Original-Received: from [2607:f8b0:4864:20::533] (port=40471 helo=mail-pg1-x533.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nM8Zy-0005d2-J6 for guile-devel@gnu.org; Mon, 21 Feb 2022 08:18:15 -0500 Original-Received: by mail-pg1-x533.google.com with SMTP id w37so7883330pga.7 for ; Mon, 21 Feb 2022 05:18:13 -0800 (PST) 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=+frtPWGzwq4cxeYaXmBdxfZxqdxVfmjaDcPKoVfGAn8=; b=gdhF6a8r+8h7J4ZYl2sdjFYdQJCtUAJ5eOIpxSEXF8i4HYf+gwPVAXWXf4IezrgZbC mczYoKDjiO+lcVTIjwelJS9byXJkKpAei/qzSqBX+RiU/KD862Hn8oMDJVIaaKaX6fTZ ncudDrOQDMD6yn1IiLzt9BW/gD7C/mnWQgRmccM0htOjiFKSSwhADeFp7/LQik/E/NOj szzPQ7yTlkLvtQgaT7srDVlGB2+g5NQvbP+ZLHxE7++H6rUNg2pJ5XcFPkhj/wqURscG gCJL2ErzHfwr7jJLBDnsNUFu8cA8EsqlRgbygsJ317HaekQSzl5zS+S7AZWi4ry4ezJv J6Uw== 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=+frtPWGzwq4cxeYaXmBdxfZxqdxVfmjaDcPKoVfGAn8=; b=FaafV/neKlkrOfGJDh6S28cGa8+gXkYPcTQSM9jfJcgZLL8I9Bk8oVUAw+MbTzUENE ljReW36KdlvtBmLHHMrhJ+eWEjxPUWG6B/a2BxEpwfqD8yQsjjKmB5t8Xpv9pCMI3/95 mCO0mP0TJ3zgw7r5y5A4Oi2FuAEu1cP/HQwYwQrFNaZxAxHaTIjBbZ+GThJ1e9N0RQvz Z2btm7WZCYFZj1h7klhnf8YCrrLXmsI/UOz9ohW0NsXbPZ4Y+2/0tjYBeCoj7G2Ye7PX 25loILznYgosi3A4dzb8f5ELa+3c0F08pstjVWxEkJ7ZJ8jIi/qJsHq4wOsRdWY5SaEO wKqQ== X-Gm-Message-State: AOAM531LLMHabki4xS7pMyD/YJgL05yDJ9ucSjSJf+LyKkx6fik+V6Et KRQOJBtMYYn7o5ZWEzDYFshf1UTSsE2ZTLvMHsmHMMJO2JU= X-Google-Smtp-Source: ABdhPJwcNOZYVHiiEGIO8+16RdjTxxS1wOyutpXG/aQtG1UHul05ttdC1XlCJ1z/FqrGflukH9w1lGa2/0f3duHAaIY= X-Received: by 2002:a65:6045:0:b0:368:e62c:cdc4 with SMTP id a5-20020a656045000000b00368e62ccdc4mr15979624pgp.138.1645449491936; Mon, 21 Feb 2022 05:18:11 -0800 (PST) X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::533 (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::533; envelope-from=stefan.itampe@gmail.com; helo=mail-pg1-x533.google.com X-Spam_score_int: -6 X-Spam_score: -0.7 X-Spam_bar: / X-Spam_report: (-0.7 / 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, PDS_HP_HELO_NORDNS=0.659, RCVD_IN_DNSWL_NONE=-0.0001, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=no 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:21137 Archived-At: --000000000000767aa405d8871010 Content-Type: text/plain; charset="UTF-8" A datastructure I fancy is hash tables. But I found out that hashtables in guile are really slow, How? First of all we make a hash table (define h (make-hash-table)) Then add values (for-each (lambda (i) (hash-set! h i i)) (iota 20000000)) Then the following operation cost say 5s (hash-fold (lambda (k v s) (+ k v s)) 0 h) It is possible with the foreign interface to speedt this up to 2s using guiles internal interface. But this is slow for such a simple application. Now let's change focus. Assume the in stead an assoc, (define l (map (lambda (i) (cons i i)) (iota 20000000))) Then ime (let lp ((l ll) (s 0)) (if (pair? l) (lp (cdr l) (+ s (caar l))) s)) $5 = 199999990000000 ;; 0.114530s real time, 0.114391s run time. 0.000000s spent in GC. That's 20X faster. What have happened?, Well hashmaps has terrible memory layout for scanning. So essentially keeping a list of the created values consed on a list not only get you an ordered hashmap, you also have 20X increase in speed, you sacrifice memory, say about 25-50% extra. The problem actually more that when you remove elements updating the ordered list is very expensive. In python-on-guile I have solved this by moving to a doubly linked list when people start's to delete single elements. For small hashmap things are different. I suggest that guile should have a proper faster standard hashmap implemention of such kind in scheme. Stefan --000000000000767aa405d8871010 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
A datastructure I fancy is hash tables. But I found out th= at hashtables in guile are really slow, How? First of all we make a hash ta= ble

(define h (make-hash-table))

Then add values
(for-each (lambda (i) (hash-set! h i i)) (iota = 20000000))

Then the following operation cost say 5= s
(hash-fold (lambda (k v s) (+ k v s)) 0 h)

=
It is possible with the foreign interface to speedt this up to 2s usin= g guiles internal interface. But this is slow for such a simple application= . Now let's change focus. Assume the in stead an assoc,

<= /div>
(define l (map (lambda (i) (cons i i)) (iota 20000000)))

Then
ime (let lp ((l ll) (s 0)) (if (pair? l) (lp (c= dr l) (+ s (caar l))) s))
$5 =3D 199999990000000
;; 0.114530s real time, 0.114391s run time. =C2=A00.000000s spent in GC= .

That's 20X = faster. What have happened?, Well hashmaps has terrible memory layout for s= canning. So essentially keeping a list of the created values consed on a li= st not only get you an ordered hashmap, you also have 20X increase in speed= , you sacrifice memory, say about 25-50% extra. The problem actually more t= hat when you remove elements updating the ordered list is very expensive. I= n python-on-guile I have solved this by moving to a doubly linked list when= people start's to delete single elements. For small hashmap things are= different.

I suggest that guile sh= ould have a proper faster standard hashmap implemention of such kind in sch= eme.

Stefan



--000000000000767aa405d8871010--