From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Amirouche Boubekki Newsgroups: gmane.lisp.guile.devel Subject: Re: Proposal of a better hash table implementation based on SRFI 125 Date: Sun, 20 Jan 2019 13:57:48 +0100 Message-ID: References: NNTP-Posting-Host: ciao.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000004651e3057fe34bc0" X-Trace: ciao.gmane.org 1547989091 6295 195.159.176.228 (20 Jan 2019 12:58:11 GMT) X-Complaints-To: usenet@ciao.gmane.org NNTP-Posting-Date: Sun, 20 Jan 2019 12:58:11 +0000 (UTC) Cc: guile-devel , guile-devel , Amirouche Boubekki To: =?UTF-8?B?SsOpc3NpY2EgTWlsYXLDqQ==?= , Mark H Weaver Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Jan 20 13:58:08 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 1glCfw-0001bZ-Bi for guile-devel@m.gmane.org; Sun, 20 Jan 2019 13:58:08 +0100 Original-Received: from localhost ([127.0.0.1]:39268 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glCg5-000632-EW for guile-devel@m.gmane.org; Sun, 20 Jan 2019 07:58:17 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:41935) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glCfw-00062j-JM for guile-devel@gnu.org; Sun, 20 Jan 2019 07:58:10 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1glCfu-0006Es-QY for guile-devel@gnu.org; Sun, 20 Jan 2019 07:58:08 -0500 Original-Received: from mail-vk1-xa29.google.com ([2607:f8b0:4864:20::a29]:33504) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1glCfq-00069k-Ps; Sun, 20 Jan 2019 07:58:02 -0500 Original-Received: by mail-vk1-xa29.google.com with SMTP id d201so4048966vka.0; Sun, 20 Jan 2019 04:58:01 -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=Jk6wOdfAA7FKkDYtCkHcIboVAFjLNM2ea7smVGaCO7Q=; b=CPabVxcagHpCSQGJn8i0YWDKmvnTPCqF2lWumjfcxEUQcw9wtFC6nyBd40DcaqkuK2 uTYBq7Rew8AGbeMO0lnfAFVrDrF6pleeVJ8v6nzhJb/+vrBIdZ0IFv2Cokcv4wG4YSzt daG/ZQcqwR0NXU0IGfhDqAR5fCDLjtB77u5i7PQ6dt/22S0siVLYcJ/5343m6F5ZOSrU p3WV+6k/Bu8aaYE1GeytiLwbi/5LM/mKdgfPYUanVP+e//uvwVj94XS7Ly+5iOKl3vXb Ewf5LEFgPtG8HpgRbaJvjraYZTlnWwWQ+VkkSibGT4nojE+k7CkPdwrX4rCDsoetF26F fRnw== 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=Jk6wOdfAA7FKkDYtCkHcIboVAFjLNM2ea7smVGaCO7Q=; b=hLKRCizraVZXDawuQJfA3MDCAhlk+0xx72cvImCXIZ7FvUS+P8Xmzpk7MDqgqVyYa8 IqgR5w1fFyU4fe/j3DIIPP+12CpJMr05yOmKy05fLQQ+RRbqMHiqAxw6gdpcWUgZClJl X88PCb4LM5vhMUGXZa6qglwYxhQADrWmNQ2rlXsmkwKOzI18azT51SOJYzeFE6VW5mUN fhPHBcjxXC7b30rnKcZ0T0vstXSzX4LxhudHVspZcnQbO9BSiYJh5WRqfX5I/P/pGxdz 1F7NQxmgymcziNqUDzM3VMhRiiiouEququsykhek9UaoEA7r9kZZSxYqoZeZ5KSuSvDV PAZA== X-Gm-Message-State: AJcUukefNeQr6sKJBzVTfFygG+wTbFl0yDTAuCPAweJ0loQ3QIEWNty0 6EZceDr4zlFGigEOCZb4EDDU6e4e3bSk3AX/Bd0= X-Google-Smtp-Source: ALg8bN4WFyZiUr0Bora1bWQhF9xNThVGICpBbYm27jEX/UoENo1BdmtleOCepE5fWqiHrF3SiQ+053ZiEf9sLmkwXRQ= X-Received: by 2002:a1f:19d6:: with SMTP id 205mr9881443vkz.53.1547989080754; Sun, 20 Jan 2019 04:58:00 -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::a29 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:19798 Archived-At: --0000000000004651e3057fe34bc0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Thanks! I have done mostly a cosmetic review of your code. Here is the summary: - 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 should be done in the compiler... no? 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 o= f >> SRFI 69, and SRFI 69 is reimplemented in the third commit, which pretty >> 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 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 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 a= nd >>>> 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=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 HASHTABL= ES), >>>>> SRFI-126 and SRFI-125. Since SRFI-125 depends on SRFI-128, I've imple= mented >>>>> it as well. My public repository already has SRFI-128, I'm just finis= hing >>>>> some tests with SRFI-125 and, once they are done, I'll push it as wel= l. >>>>> >>>>> The module (ice-9 generic-hash-tables), is quite usable and all >>>>> exported procedures are documented. I've created tests for it and als= o >>>>> ported standard tests from SRFI-126. >>>>> >>>>> Now, I see that 'libguile/hashtab.h' code keeps track of the number o= f >>>>> elements in hash tables, but the field is not visible from Scheme. Ca= n 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-* procedures that >>>>> accept an equivalence procedure instead of an assoc procedure? Perhap= s >>>>> 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 equiva= lence >>>>> 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 we= ak >>>>>> > hash tables - and I've sent a patch to fix it. However, I think >>>>>> there >>>>>> > are many other problems with current implementation of hash tables= . >>>>>> > There are guile standard hash tables, SRFI-69 hash tables (which i= s >>>>>> > implemented on top of standard hash tables) and also R6RS hash >>>>>> tables >>>>>> > (which is implemented on top or SRFI-69 and completely lacks suppo= rt >>>>>> > 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 ha= sh >>>>>> > table type that will be used directly by R6RS, SRFI-125 and SRFI-6= 9. >>>>>> > In my opinion, it should be based on SRFI-125, which is part of R7= RS >>>>>> > Red Edition, but also supports some other procedures to make it >>>>>> > compatible with R6RS and SRFI-69, supporting weakness and immutabl= e >>>>>> > 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 implementatio= n >>>>>> is ready for testing. Is it already available anywhere? >>>>>> >>>>>> TIA >>>>>> >>>>> --0000000000004651e3057fe34bc0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks!

I have done mos= tly a cosmetic review of your code. Here is the summary:

- There is two big procedures that I think should be split `get-hash-functions` an= d `hash-table` to help readability
- I am not very fond of=C2=A0 generic-hash= -table macros, I would rather use apply / call-with-values, if there is an = optimisation to be done it should be done in the compiler... no?
=
Otherwise:

- You follow the GNU gui= delines for commit message that is a good thing (minor niptick, you should = use present tense "Fix" instead of "Fixed", "Imple= ment" instead of "Implemented"
- The code is v= ery readable

I don't know about whether that c= ode requires additions 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:
<= /div>
*No= te

Em qui, 17 de jan d= e 2019 =C3=A0s 19:13, J=C3=A9ssica Milar=C3=A9 <jessymilare@gmail.com> escreveu:<= br>
Done.

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

Em qua, 16 de= jan de 2019 =C3=A0s 22:19, Amirouche Boubekki <amirouche.boubekki@gmail.com&= gt; escreveu:
I will try to look at the commits. One last niptick, ca= n you push guile master branch to you repository, and make a pull request a= gainst it so that I can directly comment in the pull requests. please. It&#= 39;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 finishe= d the libraries.

SRFI-125 is implemented. I took the lib= erty 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-TABL= ES module don't need to keep track of the hash table size anymore.

`make check` runs everything ok. I believe it's re= ady for testing. Any 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 <jessy= milare@gmail.com> escreveu:
(It seems I mistakenly responded only t= o a personal e-mail, sorry, responded now to everyone in the list with upda= tes).

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 i= mplement SRFI-69, (RNRS HASHTABLES), SRFI-126 and SRFI-125. Since SRFI-125 = depends on SRFI-128, I'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'll push it as well.

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

Now, I see that 'libguile/= hashtab.h' code keeps track of the number of elements in hash tables, b= ut 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 would simplify its code.
<= br>
Besides, what about creating new versions HASHX-*=C2=A0proced= ures that accept an equivalence procedure instead of an assoc procedure? Pe= rhaps prefixed by 'NEW-' or post-fixed by a '*'.
=
I've also found inconsistencies between SRFI-125 and it&= #39;s reference implementation and standard tests. I've implemented acc= ording to the specification - so, for instance, HASH-TABLE=3D? checks if th= e equivalence function of both hash tables are the same and HASH-TABLE retu= rns an immutable hash table.

Code is public and su= ggestions are always welcome :)

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=A9= ssica 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
--0000000000004651e3057fe34bc0--