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: hashes Date: Tue, 5 Apr 2022 23:43:37 +0200 Message-ID: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000df140705dbef23c7" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="35244"; mail-complaints-to="usenet@ciao.gmane.io" To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Tue Apr 05 23:44:21 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 1nbqyK-00093V-W3 for guile-devel@m.gmane-mx.org; Tue, 05 Apr 2022 23:44:21 +0200 Original-Received: from localhost ([::1]:44596 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nbqyJ-0003vX-KL for guile-devel@m.gmane-mx.org; Tue, 05 Apr 2022 17:44:19 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49416) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nbqxs-0003v9-R2 for guile-devel@gnu.org; Tue, 05 Apr 2022 17:43:52 -0400 Original-Received: from mail-pg1-x52e.google.com ([2607:f8b0:4864:20::52e]:36816) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nbqxr-0002td-8I for guile-devel@gnu.org; Tue, 05 Apr 2022 17:43:52 -0400 Original-Received: by mail-pg1-x52e.google.com with SMTP id r66so526093pgr.3 for ; Tue, 05 Apr 2022 14:43: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=+MkI+/anhBslIWNBPF8fnCOUztsBtvJ4bNbLXOwBuoY=; b=MdiDpokopGY5o1tzGh0mx/Oc+bIGiNgI5tPY+JNbBNegTVNfV5pTiTjde4XA3rwY6Q HLoAH/m/cffwI3nh3SZQj6Wd9fA6cObrkdAe1a6c//kQXHbqxA2mMQbDZyF5Fz3F2MYG S0978l2WO+ofhKxoi1NZlMDoDyOy5wB/K7fHk+V8nFLWFRQ4JcsyxlKrS/J/1BCBiIa8 HrPOIhOz5iRYnWIzCY9qlMZPB5rYFKITJLwNvCHV9AfCPgo7fctm6nhU0RVxWso8Tn6q ftl2Kf+urnhE0qgUKuVQvennV0Ggq4fgLExJ9Fcj+cYkfX83h854MlIPrJCsVbTWfSK4 H5oQ== 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=+MkI+/anhBslIWNBPF8fnCOUztsBtvJ4bNbLXOwBuoY=; b=SMOqofx8ZLbZrhrGxadEIh9sH7exOyrODr0A3XqtDRok4TbDzf08cPxG6jW6/KUSdW tZL0It1QpqfCCtGg+o1Hjyh3e1ce9ohcrSQFMyLO5QLrkucQTZ5kJz60sidY6kmZgkAN pzOuvQ83pZwdNCIcOYePQpXVl46KzGLYaYcvDFVRP/aj57RUQXBq2Gb9RWN0Yk20o0/Q 4fZ23ingu61k9CU9OvpziGbYY20S9H8I+7gskuofcFwkxvqob4ZtQM1cSEtDR6zCv5Ck aC5r/+kTOP3GB9tfYu3PlayErE7Nqh/lbcQ9KVxnA6RtLq8nFe52o3BD3PjzrMcOgCE9 R7pg== X-Gm-Message-State: AOAM532wpo4PYU6JXLmZAeToxERpIGeo7BuSTCRMsiOCXl2klMjQjR2x hIfWs2hTFJuYmOrzxEv1zgBy8uVXF5hhrn8NqdCOTz+R X-Google-Smtp-Source: ABdhPJx/8Ge0GvyI7uooPDgA+MS2dELBBZ6SpMmzQAh9kpY+H+/1Vey5yniMhP1b7iWhTp0Kz+RqwIZd3yysX+Kc82E= X-Received: by 2002:a63:a804:0:b0:398:e7d7:29ab with SMTP id o4-20020a63a804000000b00398e7d729abmr4416638pgf.138.1649195029040; Tue, 05 Apr 2022 14:43:49 -0700 (PDT) Received-SPF: pass client-ip=2607:f8b0:4864:20::52e; envelope-from=stefan.itampe@gmail.com; helo=mail-pg1-x52e.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:21187 Archived-At: --000000000000df140705dbef23c7 Content-Type: text/plain; charset="UTF-8" I can now demonstrate that the hash implementation is around as fast as guile internal implementation. But for some workloads like if we have a hash with millions of elements. And lookups a working set of about 10000 key hash pairs the speed is doubled compared to guiles internal. Now this is maybe not as interesting. But the implementation is decoupled and allows one to construct custom hashing algorithms that are fast compared to guile's current speed when it comes to the hash tables (hash,eq,assoc) is never called from the inside of the hash function which means that any custom implementation lives in scheme totally. The fast execution was enabled by implementing the hash function as a vm operation and compiling it with a size 1<<60 (% is efficiently optimized as a logand) and hence we got essentially the same speed using a vm-op for hashq. Next I will see how fast we can make hashtables when pushing the hash-ref equivalent to a vm-operation. With this we can now get a hash algo that mimics the python algo. --000000000000df140705dbef23c7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I can now demonstrate that the hash implementation is arou= nd as fast as guile internal implementation. But for some workloads like if= we have a hash with millions of elements. And lookups a working set of abo= ut 10000 key hash pairs the speed is doubled compared to guiles internal. N= ow this is maybe not as interesting. But the implementation is decoupled=C2= =A0and allows one to construct custom hashing algorithms that are fast comp= ared to guile's current speed when it comes to the hash tables (hash,eq= ,assoc) is never called from the inside of the hash function which means th= at any custom implementation lives in scheme totally. The fast execution wa= s enabled by implementing the hash function as a vm operation and compiling= it with a size 1<<60 (% is efficiently optimized as a logand) and he= nce we got essentially the same speed using a vm-op for hashq. Next I will = see how fast we can make hashtables when pushing=C2=A0the hash-ref equivale= nt to a vm-operation. With this we can now get a hash algo that mimics the = python algo.
--000000000000df140705dbef23c7--