From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: "Dr. Arne Babenhauserheide" Newsgroups: gmane.lisp.guile.devel Subject: Re: hashtables Date: Wed, 06 Apr 2022 17:10:36 +0200 Message-ID: <87k0c2dyzr.fsf@web.de> References: Mime-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="28428"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: mu4e 1.6.10; emacs 27.2 Cc: guile-devel@gnu.org To: Stefan Israelsson Tampe Original-X-From: guile-devel-bounces+guile-devel=m.gmane-mx.org@gnu.org Wed Apr 06 17:15:58 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 1nc7O2-0007AX-E4 for guile-devel@m.gmane-mx.org; Wed, 06 Apr 2022 17:15:58 +0200 Original-Received: from localhost ([::1]:60942 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nc7O1-0001BF-1o for guile-devel@m.gmane-mx.org; Wed, 06 Apr 2022 11:15:57 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49702) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nc7Nq-0001B6-4C for guile-devel@gnu.org; Wed, 06 Apr 2022 11:15:46 -0400 Original-Received: from mout.web.de ([217.72.192.78]:60277) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nc7No-0006NV-9S for guile-devel@gnu.org; Wed, 06 Apr 2022 11:15:45 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1649258140; bh=K9If/caMRzhRRxL1nJc1ndNIIPDMFD34O1SDuYJYqO4=; h=X-UI-Sender-Class:References:From:To:Cc:Subject:Date:In-reply-to; b=Rbo/qYZicx5SyYwc7dpudNEcPge+8m/ZazZK/P+mc8mZiHJ6GuLoJlOsFs2MICn6L M0Fr48k8CB8wOV2NTQKzKdjTm/bbQtzt44kgjop6E3cbuPxCsr5hov2hVd9kUTcjdt PCWKsgctHdPYef99xEfOiJIPUtXNkvfJ9k6osvLI= X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9 Original-Received: from fluss ([84.149.92.66]) by smtp.web.de (mrweb105 [213.165.67.124]) with ESMTPSA (Nemesis) id 1Mtgyj-1nqbpM3lD5-00v86N; Wed, 06 Apr 2022 17:15:39 +0200 In-reply-to: X-Provags-ID: V03:K1:NreVqExR3CW/tNX2aEaYIFkZAtl+c2eeKp2x+mK+yq37Slwkfro KDWqjBamRZYaoQYkiNs3+m09iJiPJP++wbJYOqJUVPp515qEAINiFn31oHiOauHXjfl2IZm qNa8Fbh2Ot7O0PG8oHjFEuG/K4vTNpO1WQ/b1eggTQxKE1JNhTyqae8DF6bA3aV3hmBmTir 7fiqZqAMI32UPB8/qZrtA== X-UI-Out-Filterresults: notjunk:1;V03:K0:dSR7cJF5674=:dakIPON/FQBw/9J+3Bxng2 1iTQPm41RDY5CfyhkOs7IY8ECW72s2IqZvuW6G7E9/Id6pHUgE+XbAEG/lDaiMLvzaRaz8/Y3 6l0+Dc5m1P/Zq80xK9aPg7OjFS8mUI5TYI1UkXQgl9cnDXF7sI/r97IvgHEsC9B7XGNKxcdzJ hwA64dIL9VWMlVdWlCpZHKWwORlh8SCwgdxkR4Rqr2oEwYsSVGYfwPr91UWGPclEWKKrPQSQ1 9XGElDdVfbyUNIfkFxVnr9NAw+Q+ia9MDfQvmd2YEC9q878V5vw65tmPVhWFRnUd6y4PAlcm+ R6fdwR9smvh/VvVdo/EWwQIJPj0KByu+3+Km7v8Ec0bs5cLe88AEZ4EUgDE4ATYGlctKxutgC ij1TzZ3ijr3gsk4LHT0FsjKqCeoIzems54VqwPL/R/O58tkpbOloQlwm4SGRHYgpbaGaXe0No WS5EnnU6XTevEVE0Izlr/521GpR1PyHLlICNWkQO9Dv1eq4UAq2RhgmWB8BBBU4hhsdOmrPCF CuWBtuJxzweQuNtzJ4Iohdvf0+SxiYuURSxzLjy7m+rCuX0A0FO7/BcpuqlIAVh0Bu+4ps6wu U0pD10FneBTrDmSBZnN/zDU0QxyOlh0OOssEYhL0yQK9dluLZ9FSwz05GO1PnY5m0MXmxkFbT vaj9W5SLbzD1goz/1Tv/0s8pmn3WrxdY7244uPDFipfVGGITMZ1B8nbUVS+HYzD1mzSbnU2c5 OGUJ7lFUucYPEZJ/r+nGnku+FcLCqOY9yX0ICrm9oYzGJFOuyiMMvwVYf5GgbxT3a5MQEGVP Received-SPF: pass client-ip=217.72.192.78; envelope-from=arne_bab@web.de; helo=mout.web.de X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 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, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, 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:21189 Archived-At: --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Stefan Israelsson Tampe writes: > 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 What do you mean by "large taable scanning numbers"? (I don=E2=80=99t under= stand) > 3. + The general hash interface is faster also because it does not call S= CM from C > 4. + fast (2X) for relative large random working sets although the hashta= ble is large That would likely directly speed up code I have by factor 2.=20 > 5. - we do not suport the assoc generalisation (sort off though) What do you mean by assoc generalization? > 6. Compact (low memory overhead) All in all these improvements sound great! And low memory overhead is the icing on the cake. How big is the remaining overhead? (compared to storing the values in a vec= tor?) > 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 o= n small hashtables. Since I do not know the implications of this on the VM, I cannot give an answer. If Andy Wingo doesn=E2=80=99t object, then I think these improvements would= be awesome to have! Best wishes, Arne =2D-=20 Unpolitisch sein hei=C3=9Ft politisch sein, ohne es zu merken. draketo.de --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQJEBAEBCAAuFiEE801qEjXQSQPNItXAE++NRSQDw+sFAmJNrpgQHGFybmVfYmFi QHdlYi5kZQAKCRAT741FJAPD6y/fD/407gP83LIscRCu+pf2+3g5SdWn7dBKh7pt muvWaOzCDCU24fFZWdSb4WkH8f7paB9RP1tQpODJpUsyMlyMU1RTeb4asy8POJkh o34kmxeb0szkCIo0SdU9wHjhftKHiLk4SPgj8/ERy+3BQBPq/r6JYimfGwTi6otc QGkg9qRDm8LZT46P1nLSjMqQefmzSGUvldqJsnMVGyE9KU4hsLCd/nxNAOVAFlFw dAAaRgjJqfJzMEEFBC6VeptCSQb9+g+6B44fiLhI3iOVrS7gHJSXjy0/UETkSMVN NjoLUXS7A5ePul3JSo4U8oEQ5OztZXCgz40pKidkfUwjpf1kbihxyHNQHj46Z+AL VwStsUTpFACbntkon2IEs4oNYgSqJYC8ae7sJ6qrZNrKss01+BJJLhNuqs9ghgem 4Xf9FlnI+fAHq4aL2d+Yezzhr/LjoE+zLQbq1YKHmft/UdHe61Z6rjZO7OIKGsns x393TVN4xtFD/8qcwXR+9VKiEYp4vbzwUoaKstDVGO6Y4BW71pPnN6Y9K92ybA6X ctUshpluiu4s5xRQPQkq5/jiNJ5qq32e3Q/FSinKU94fn/1+Dtx5N0yKxoDxAQyw W9KSqBKAP4rLfue7h6IZWUCOMQ8vShxS8qcx5YcFZ8L1bgIeiixC2jMVuEdUfMCK fdSj80GUKYjEBAEBCAAuFiEE3Si95tmHXKvOSosd3M8NswvBBUgFAmJNrpsQHGFy bmVfYmFiQHdlYi5kZQAKCRDczw2zC8EFSHChA/4gEbJiLqeotPChFEcQUvn73u1m xHKMgH/skrR1oOeff6ZvLrD51g8m1/FbVM0tl+FnmLajTwGl/pvSfdEoz2neHRbA S+JxOJzv67WNYb0+kDQpIL7SqkQajaqt6xlfrCr6hWQO5g+NKTxu0nk3VOKnP0p0 tN42j0f70uT2XSk4qg== =lXiM -----END PGP SIGNATURE----- --=-=-=--