From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: =?UTF-8?B?SsOpc3NpY2EgTWlsYXLDqQ==?= Newsgroups: gmane.lisp.guile.devel Subject: Re: Proposal of a better hash table implementation based on SRFI 125 Date: Sun, 20 Jan 2019 11:50:06 -0200 Message-ID: References: NNTP-Posting-Host: ciao.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000388bcb057fe406e3" X-Trace: ciao.gmane.org 1547992235 32700 195.159.176.228 (20 Jan 2019 13:50:35 GMT) X-Complaints-To: usenet@ciao.gmane.org NNTP-Posting-Date: Sun, 20 Jan 2019 13:50:35 +0000 (UTC) Cc: Mark H Weaver , guile-devel , guile-devel , Amirouche Boubekki To: Amirouche Boubekki Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Jan 20 14:50:32 2019 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.84_2) (envelope-from ) id 1glDUd-0008V5-6F for guile-devel@m.gmane.org; Sun, 20 Jan 2019 14:50:31 +0100 Original-Received: from localhost ([127.0.0.1]:40120 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glDUm-0000c4-7N for guile-devel@m.gmane.org; Sun, 20 Jan 2019 08:50:40 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:50678) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glDUX-0000bk-QK for guile-devel@gnu.org; Sun, 20 Jan 2019 08:50:27 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1glDUV-0000LT-Mr for guile-devel@gnu.org; Sun, 20 Jan 2019 08:50:25 -0500 Original-Received: from mail-it1-x144.google.com ([2607:f8b0:4864:20::144]:55363) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1glDUR-0000GV-B0; Sun, 20 Jan 2019 08:50:19 -0500 Original-Received: by mail-it1-x144.google.com with SMTP id m62so13116197ith.5; Sun, 20 Jan 2019 05:50:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=ZduRspSwXJCcyTOXcpQ2A7MN0SpDQGmh+yw9HDvlthk=; b=YYCTJaaEYxsBoNCnPWl4Flp1hny314OcrEWpBg4uP8+kfRMVXFiZs5AsgnGEydxQEK noNWj5tRsl3Lg6DUN5oGw04QV7vwx3oTMoQvZ9rAegko56T9OMnXOlbqnB36QzCHtsgQ Mp84cccR8mA1LpHmnOIXrYNoUvsHY/qeFB6PYXBWG7Bb49l+LS5aPGG5yWhGNaLsdDV4 Omn1bSKyPHgEwHoooiOSiKujZpt3F0r9gEX58Y0/Zge5LRPyybLXTFtSBshwU/KmZLvZ qkiv09p1FDSswZIP/TKT/xSLKlMYDoDdxhNoRZVV6PlALuqen/nyiRv9u3joERSRos3C BkJg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ZduRspSwXJCcyTOXcpQ2A7MN0SpDQGmh+yw9HDvlthk=; b=ZVxXGLJhbsPmJesFo3tSUT6m5DELYtM0eOSfCGa88UH2FBZIjxpm7StQtmQUPe8tEs gB4APs3eVdXLLaSnsB099zIOpikin+QmeJfYEqwXhcLNa/rXy3U1LNQJUc4PbDN8dY6e +/1DtaujO8AEWYJ+YvgbYmQIaVYSRk+xXJiMLavYWrj4RkxZGdsUkJbep8Vxp9ufY8Q9 iE3lUxlcYFw0rlOrA5OAGPjWpoZZGhaS1m0cSU4rRyWuvbTFQmTeendVG+GivtrFnYHl s2TKRSh69WmFAA/2t2+A53uqPB5bLyH0sqlmm2SisWF170tOnZoOF1WmAg3oJ+00ZoZy Zg9g== X-Gm-Message-State: AJcUukfRctnmRQpqaj3kc5zq3aU3MY6Wc2uzdW7KFnHV94KRU/nKqGF1 ZiPMyBUQ8XC1uPqe+yQv1lcIpB4UqcO1uayoOm4= X-Google-Smtp-Source: ALg8bN6SMsnSNE8dBBBofY13eRlXQRWSDNCZOg1a/Ex8MpiPmPoi3Zq5dhcf+7ZzzIaPy3O7mtRBE+zUewQQ/QYPYYg= X-Received: by 2002:a02:330d:: with SMTP id c13mr15621759jae.95.1547992217192; Sun, 20 Jan 2019 05:50:17 -0800 (PST) In-Reply-To: X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4864:20::144 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.org gmane.lisp.guile.devel:19799 Archived-At: --000000000000388bcb057fe406e3 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Em dom, 20 de jan de 2019 =C3=A0s 10:58, Amirouche Boubekki < amirouche.boubekki@gmail.com> escreveu: > Thanks! > > I have done mostly a cosmetic review of your code. Here is the summary: > Your comments are very good, I'll do most of the suggested changes. > - There is two big procedures that I think should be split ` > get-hash-functions` and `hash-table` to help readability > - I am not very fond of generic-hash-table macros, I would rather use > apply / call-with-values, if there is an optimisation to be done it shoul= d > be done in the compiler... no? > These macros were copied from old SRFI-69 code. Regarding to optimizations, I don't ask myself if something *should be* done by the compiler, but if it *actually is* done by the compiler. Otherwise, we'll end in a discussion involving a "sufficiently smart compiler", not a real compiler. Otherwise: > > - You follow the GNU guidelines for commit message that is a good thing > (minor niptick, you should use present tense "Fix" instead of "Fixed", > "Implement" instead of "Implemented" > - The code is very readable > > I don't know about whether that code requires additions to the manual > since it's R7RS and SRFI. > > I cc'ed Mark Weaver. > > Le jeu. 17 janv. 2019 =C3=A0 22:14, J=C3=A9ssica Milar=C3=A9 a > =C3=A9crit : > >> *Note >> >> Em qui, 17 de jan de 2019 =C3=A0s 19:13, J=C3=A9ssica Milar=C3=A9 >> escreveu: >> >>> Done. >>> >>> Not that there are many commits. The first commit only fixes bug 33827 >>> of SRFI 69, and SRFI 69 is reimplemented in the third commit, which pre= tty >>> much erases the changes of the first commit. >>> >>> https://github.com/jessymilare/guile/pull/1 >>> >>> Em qua, 16 de jan de 2019 =C3=A0s 22:19, Amirouche Boubekki < >>> amirouche.boubekki@gmail.com> escreveu: >>> >>>> I will try to look at the commits. One last niptick, can you push guil= e >>>> master branch to you repository, and make a pull request against it so= that >>>> I can directly comment in the pull requests. please. It's easier to wa= y to >>>> see the overall changes in particular. >>>> >>>> Le dim. 13 janv. 2019 =C3=A0 23:52, J=C3=A9ssica Milar=C3=A9 >>>> a =C3=A9crit : >>>> >>>>> Finally finished the libraries. >>>>> >>>>> SRFI-125 is implemented. I took the liberty to create a procedure >>>>> scm_hash_n_items in 'libguile/hashtab.c' that works with both normal = and >>>>> weak hash tables, so the GENERIC-HASH-TABLES module don't need to kee= p >>>>> track of the hash table size anymore. >>>>> >>>>> `make check` runs everything ok. I believe it's ready for testing. An= y >>>>> feedback is welcome. >>>>> >>>>> Regards, >>>>> J=C3=A9ssica >>>>> >>>>> Em s=C3=A1b, 12 de jan de 2019 =C3=A0s 18:34, J=C3=A9ssica Milar=C3= =A9 < >>>>> jessymilare@gmail.com> escreveu: >>>>> >>>>>> (It seems I mistakenly responded only to a personal e-mail, sorry, >>>>>> responded now to everyone in the list with updates). >>>>>> >>>>>> So here are the news: >>>>>> >>>>>> I've created a module called (ice-9 generic-hash-tables), which is >>>>>> similar to SRFI-125, and used it to implement SRFI-69, (RNRS HASHTAB= LES), >>>>>> SRFI-126 and SRFI-125. Since SRFI-125 depends on SRFI-128, I've impl= emented >>>>>> it as well. My public repository already has SRFI-128, I'm just fini= shing >>>>>> some tests with SRFI-125 and, once they are done, I'll push it as we= ll. >>>>>> >>>>>> The module (ice-9 generic-hash-tables), is quite usable and all >>>>>> exported procedures are documented. I've created tests for it and al= so >>>>>> ported standard tests from SRFI-126. >>>>>> >>>>>> Now, I see that 'libguile/hashtab.h' code keeps track of the number >>>>>> of elements in hash tables, but the field is not visible from Scheme= . Can >>>>>> that be changed? Then generic hash tables wouldn't need to also keep= track >>>>>> of the number of elements (like SRFI-69 currently does) and that wou= ld >>>>>> simplify its code. >>>>>> >>>>>> Besides, what about creating new versions HASHX-* procedures that >>>>>> accept an equivalence procedure instead of an assoc procedure? Perha= ps >>>>>> prefixed by 'NEW-' or post-fixed by a '*'. >>>>>> >>>>>> I've also found inconsistencies between SRFI-125 and it's reference >>>>>> implementation and standard tests. I've implemented according to the >>>>>> specification - so, for instance, HASH-TABLE=3D? checks if the equiv= alence >>>>>> function of both hash tables are the same and HASH-TABLE returns an >>>>>> immutable hash table. >>>>>> >>>>>> Code is public and suggestions are always welcome :) >>>>>> https://github.com/jessymilare/guile >>>>>> >>>>>> Regargs, >>>>>> J=C3=A9ssica >>>>>> >>>>>> Em dom, 30 de dez de 2018 =C3=A0s 15:50, Amirouche Boubekki < >>>>>> amirouche@hypermove.net> escreveu: >>>>>> >>>>>>> Le 2018-12-28 17:11, J=C3=A9ssica Milar=C3=A9 a =C3=A9crit : >>>>>>> > Hello, >>>>>>> > >>>>>>> > As I said in a previous e-mail, currently SRFI-69 is broken for >>>>>>> weak >>>>>>> > hash tables - and I've sent a patch to fix it. However, I think >>>>>>> there >>>>>>> > are many other problems with current implementation of hash table= s. >>>>>>> > There are guile standard hash tables, SRFI-69 hash tables (which = is >>>>>>> > implemented on top of standard hash tables) and also R6RS hash >>>>>>> tables >>>>>>> > (which is implemented on top or SRFI-69 and completely lacks >>>>>>> support >>>>>>> > for weak keys and/or values). >>>>>>> > >>>>>>> > I think that should be fixed and guile should have only two kinds >>>>>>> of >>>>>>> > hash tables: the standard guile hash table and another extended >>>>>>> hash >>>>>>> > table type that will be used directly by R6RS, SRFI-125 and >>>>>>> SRFI-69. >>>>>>> > In my opinion, it should be based on SRFI-125, which is part of >>>>>>> R7RS >>>>>>> > Red Edition, but also supports some other procedures to make it >>>>>>> > compatible with R6RS and SRFI-69, supporting weakness and immutab= le >>>>>>> > hash tables. >>>>>>> > >>>>>>> > I'm already implementing the SRFI-125 based hash tables library f= or >>>>>>> > myself, so, if that is accepted, I can also make a patch for guil= e. >>>>>>> > >>>>>>> >>>>>>> Yes please make a patch and attach it to the bug report. >>>>>>> >>>>>>> Don't forget to send an announcement when you SRFI-125 implementati= on >>>>>>> is ready for testing. Is it already available anywhere? >>>>>>> >>>>>>> TIA >>>>>>> >>>>>> --000000000000388bcb057fe406e3 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable


=
Em dom, 20 de jan de 2019 =C3=A0s 10:= 58, Amirouche Boubekki <= amirouche.boubekki@gmail.com> escreveu:
Thanks!

I have done mostly a cosmetic review of your code. Here i= s the summary:

Your comments ar= e very good, I'll do most of the suggested changes.
=C2=A0
= - There is two big procedures that I think should be split `get-hash-functions` and `hash-table` to help readability
- I am not very fond of=C2=A0 generic-hash-table macros, I wo= uld rather use apply / call-with-values, if there is an optimisation to be = done it should be done in the compiler... no?
=
These macros were copied from old SRFI-69 code. Regarding to= optimizations, I don't ask myself if something=C2=A0should=C2=A0be<= /i> done by the compiler, but if it actually=C2=A0is=C2=A0done by th= e compiler. Otherwise, we'll end in a discussion involving a "suff= iciently smart compiler", not a real compiler.

Otherw= ise:

- You follow the GNU guidelines for commit me= ssage that is a good thing (minor niptick, you should use present tense &qu= ot;Fix" instead of "Fixed", "Implement" instead of= "Implemented"
- The code is very readable

I don't know about whether that code requires addition= s to the manual since it's R7RS and SRFI.

= I cc'ed Mark Weaver.

Le=C2=A0jeu. = 17 janv. 2019 =C3=A0=C2=A022:14, J=C3=A9ssica Milar=C3=A9 <jessymilare@gmail.com>= a =C3=A9crit=C2=A0:
*Note

Em qui, 17 de jan de 2019 =C3=A0s 19:13, J=C3=A9ssica Milar=C3=A9 <= ;jessymilare@gma= il.com> escreveu:
Done.

Not that there are many commits. = The first commit only fixes bug=C2=A033827 of SRFI 69, and SRFI 69 is reimp= lemented in the third commit, which pretty much erases the changes of the f= irst commit.


Em qua, 16 de jan de 2019 =C3=A0s 22:19, Amirouche Boubekki &= lt;amirou= che.boubekki@gmail.com> escreveu:
I will try to look at the co= mmits. One last niptick, can you push guile master branch to you repository= , and make a pull request against it so that I can directly comment in the = pull requests. please. It's easier to way to see the overall changes in= particular.

Le=C2=A0dim. 13 janv. 2019 =C3=A0=C2=A023:52, J=C3=A9ssica Milar=C3=A9= <jessymilare= @gmail.com> a =C3=A9crit=C2=A0:
Finally finished the libraries.
SRFI-125 is implemented. I took the liberty to create a pro= cedure scm_hash_n_items in 'libguile/hashtab.c' that works with bot= h normal and weak hash tables, so the GENERIC-HASH-TABLES module don't = need to keep track of the hash table size anymore.

`make check` runs everything ok. I believe it's ready for testing. Any= feedback is welcome.

Regards,
J=C3=A9ss= ica

Em s=C3=A1b,= 12 de jan de 2019 =C3=A0s 18:34, J=C3=A9ssica Milar=C3=A9 <jessymilare@gmail.com>= ; escreveu:
(It seems I mistakenly responded only to a personal e-mail, so= rry, responded now to everyone in the list with updates).

So here ar= e the news:

I've created a module called (ice-9 generic-hash-tab= les), which is similar to SRFI-125, and used it to implement SRFI-69, (RNRS= HASHTABLES), SRFI-126 and SRFI-125. Since SRFI-125 depends on SRFI-128, I&= #39;ve implemented it as well. My public repository already has SRFI-128, I= 'm just finishing some tests with SRFI-125 and, once they are done, I&#= 39;ll push it as well.

The module (ice-9 generic-hash-ta= bles), is quite usable and all exported procedures are documented. I've= created tests for it and also ported standard tests from SRFI-126.

Now, I see that 'libguile/hashtab.h' code kee= ps track of the number of elements in hash tables, but the field is not vis= ible from Scheme. Can that be changed? Then generic hash tables wouldn'= t need to also keep track of the number of elements (like SRFI-69 currently= does) and that would simplify its code.

Besides, = what about creating new versions HASHX-*=C2=A0procedures that accept an equ= ivalence procedure instead of an assoc procedure? Perhaps prefixed by '= NEW-' or post-fixed by a '*'.

I've= also found inconsistencies between SRFI-125 and it's reference impleme= ntation and standard tests. I've implemented according to the specifica= tion - so, for instance, HASH-TABLE=3D? checks if the equivalence function = of both hash tables are the same and HASH-TABLE returns an immutable hash t= able.

Code is public and suggestions are always we= lcome :)

Regargs,
J=C3=A9ssica

Em dom, 30 de dez de 2018 =C3=A0s 15:50, Amirouche B= oubekki <am= irouche@hypermove.net> escreveu:
Le 2018-12-28 17:11, J=C3=A9ssica Milar=C3=A9 a =C3= =A9crit=C2=A0:
> Hello,
>
> As I said in a previous e-mail, currently SRFI-69 is broken for weak > hash tables - and I've sent a patch to fix it. However, I think th= ere
> are many other problems with current implementation of hash tables. > There are guile standard hash tables, SRFI-69 hash tables (which is > implemented on top of standard hash tables) and also R6RS hash tables<= br> > (which is implemented on top or SRFI-69 and completely lacks support > for weak keys and/or values).
>
> I think that should be fixed and guile should have only two kinds of > hash tables: the standard guile hash table and another extended hash > table type that will be used directly by R6RS, SRFI-125 and SRFI-69. > In my opinion, it should be based on SRFI-125, which is part of R7RS > Red Edition, but also supports some other procedures to make it
> compatible with R6RS and SRFI-69, supporting weakness and immutable > hash tables.
>
> I'm already implementing the SRFI-125 based hash tables library fo= r
> myself, so, if that is accepted, I can also make a patch for guile. >

Yes please make a patch and attach it to the bug report.

Don't forget to send an announcement when you SRFI-125 implementation is ready for testing. Is it already available anywhere?

TIA
--000000000000388bcb057fe406e3--