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 19:32:12 +0100 Message-ID: References: NNTP-Posting-Host: ciao.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="0000000000002f58b4057fe7f7d0" X-Trace: ciao.gmane.org 1548009199 258172 195.159.176.228 (20 Jan 2019 18:33:19 GMT) X-Complaints-To: usenet@ciao.gmane.org NNTP-Posting-Date: Sun, 20 Jan 2019 18:33:19 +0000 (UTC) Cc: Mark H Weaver , guile-devel , guile-devel , Amirouche Boubekki To: =?UTF-8?B?SsOpc3NpY2EgTWlsYXLDqQ==?= Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Jan 20 19:33:17 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 1glHuD-001543-3o for guile-devel@m.gmane.org; Sun, 20 Jan 2019 19:33:13 +0100 Original-Received: from localhost ([127.0.0.1]:43042 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glHuM-00010o-6g for guile-devel@m.gmane.org; Sun, 20 Jan 2019 13:33:22 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:43365) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1glHtn-0000wK-3M for guile-devel@gnu.org; Sun, 20 Jan 2019 13:32:52 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1glHti-0003LC-5J for guile-devel@gnu.org; Sun, 20 Jan 2019 13:32:47 -0500 Original-Received: from mail-vs1-xe42.google.com ([2607:f8b0:4864:20::e42]:32928) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1glHtS-00034I-De; Sun, 20 Jan 2019 13:32:26 -0500 Original-Received: by mail-vs1-xe42.google.com with SMTP id p74so11401796vsc.0; Sun, 20 Jan 2019 10:32:25 -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=7bVUbNZ67KiDUSA0RH9crh2rStqdnybbCt71DEpZ7l0=; b=JEgIvQbKIomVgMV3QeLSowM3AtaolqetN4IaofVm4lfpI/1sKU20h3vwnbnDvnooTi OP3n4rxHOx2D9HgLEjKMIJlDw4+wEIrJAl5CEJQh/x8RY3gobyMzQHRmUWMFN2CPCR9E 4wDvFafgRCtFKWLSpZsEwyLkwlj+aG+8OMbKb5pCLpG036tV6E703UsHuRqeywSZD9QE rENGAx6zQSAPlNiimJL5rqhnKMuORvx/JsQmJRheOa8EMNxv4asUcZtDHJNNnx2C5Gqo BMDsMc8FED/hDVQ38f87zRPvQA1bsOEDrt4nlbum5YEBoSfYL5WIkAsS7dtEXa5vDoaR nI0Q== 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=7bVUbNZ67KiDUSA0RH9crh2rStqdnybbCt71DEpZ7l0=; b=Q/ks+yuAGir8qUzfAxrsF6ZPxkQVlXuUTUU69WfQvfX4UYWbiib2m+YSebWA6WOEdJ ZB1y/nOKXfuCu3tr5hP69s4y9PJ4edLUJUOcK2XxmR26UlQy3CytQLHLEEOLJHKGlofs ZSLr3xJ8jBwNB47U3Z3T9wJLVGXsUKz2FF9tXHJ93QH4zMV42k/kqJyDRt8RCzwFsKYo lEBGpWPbm5CbA/5wOYrZiTYq+mIsD27N5GIGto8F8zYGhMqIdlRzZjETrBmgjVUPRsPx UBZ+3uqqR9zmFifqz5mhXunWCuCtpmA8xgZepYsTT4N6FXno4iyTRD0sE0W9QRsBrs2K 8wQQ== X-Gm-Message-State: AJcUukfgWEjpB6h4qQnL70deA7UN6aFl/FfilbRc8fGSNeC/NA3wHTrP ZfbFImD+o6R1psqEIS0gGQPyKMB7bZzrgZAM2DcUL0Af X-Google-Smtp-Source: ALg8bN6rlfcK/AKmx2FGqLv7vQBQ3VxzozxwlULkFwTNvD641f4ENesrC0W+lQf9GXqNNtKltkVB5Sw3bMcniHEuhFo= X-Received: by 2002:a67:6346:: with SMTP id x67mr11104381vsb.114.1548009144798; Sun, 20 Jan 2019 10:32:24 -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::e42 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:19800 Archived-At: --0000000000002f58b4057fe7f7d0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Thanks for the feedback! Also, if you are interested in r7rs in guile you might be interested in `r7rs-wip` branch of guile Le dim. 20 janv. 2019 =C3=A0 14:50, J=C3=A9ssica Milar=C3=A9 a =C3=A9crit : > > > 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 shou= ld >> 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 < >>> jessymilare@gmail.com> 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 pr= etty >>>> 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 agains= t it >>>>> so that I can directly comment in the pull requests. please. It's eas= ier 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= and >>>>>> weak hash tables, so the GENERIC-HASH-TABLES module don't need to ke= ep >>>>>> 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 HASHTA= BLES), >>>>>>> SRFI-126 and SRFI-125. Since SRFI-125 depends on SRFI-128, I've imp= lemented >>>>>>> it as well. My public repository already has SRFI-128, I'm just fin= ishing >>>>>>> some tests with SRFI-125 and, once they are done, I'll push it as w= ell. >>>>>>> >>>>>>> The module (ice-9 generic-hash-tables), is quite usable and all >>>>>>> exported procedures are documented. I've created tests for it and a= lso >>>>>>> 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 Schem= e. Can >>>>>>> that be changed? Then generic hash tables wouldn't need to also kee= p track >>>>>>> of the number of elements (like SRFI-69 currently does) and that wo= uld >>>>>>> simplify its code. >>>>>>> >>>>>>> Besides, what about creating new versions HASHX-* procedures that >>>>>>> accept an equivalence procedure instead of an assoc procedure? Perh= aps >>>>>>> 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 th= e >>>>>>> specification - so, for instance, HASH-TABLE=3D? checks if the equi= valence >>>>>>> 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 >>>>>>>> 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 >>>>>>>> > (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 kind= s >>>>>>>> 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 >>>>>>>> for >>>>>>>> > 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 >>>>>>>> >>>>>>> --0000000000002f58b4057fe7f7d0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks for the feedback!
<= div>
Also, if you are interested in r7rs in guile you might b= e interested in `r7rs-wip` branch of guile


Le=C2=A0dim. = 20 janv. 2019 =C3=A0=C2=A014:50, J=C3=A9ssica Milar=C3=A9 <jessymilare@gmail.com> a =C3=A9crit=C2= =A0:


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

I have done mostly a co= smetic review of your code. Here is the summary:

Your comments are very good, I'll do most of the sugg= ested changes.
=C2=A0
- There is two big procedures that I thin= k should be split `get-hash-functi= ons` and `hash-table` to help readabili= ty
- I am not very fond of=C2=A0 generic= -hash-table macros, I would rather use apply / call-with-values, if there i= s an optimisation to be done it should be done in the compiler... no?
=

These macros were copied from old SR= FI-69 code. Regarding to optimizations, I don't ask myself if something= =C2=A0should=C2=A0be done by the compiler, but if it actually=C2= =A0is=C2=A0done by the compiler. Otherwise, we'll end in a discussi= on 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 sho= uld use present tense "Fix" instead of "Fixed", "I= mplement" instead of "Implemented"
- The code = is very readable

I don't know about whether th= at code requires additions to the manual since it's R7RS and SRFI.
<= /div>

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@gmail.com> escre= veu:
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 = commit, which pretty much erases the changes of the first commit.
<= br>

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 niptic= k, can you push guile master branch to you repository, and make a pull requ= est 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 <jessy= milare@gmail.com> a =C3=A9crit=C2=A0:
Finally finished the librarie= s.

SRFI-125 is implemented. I took the liberty to create= a procedure scm_hash_n_items in 'libguile/hashtab.c' that works wi= th both normal and weak hash tables, so the GENERIC-HASH-TABLES module don&= #39;t need to keep track of the hash table size anymore.

`make check` runs everything ok. I believe it's ready for testin= g. 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.co= m> 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-6= 9, (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 SRF= I-128, I'm just finishing some tests with SRFI-125 and, once they are d= one, I'll push it as well.

The module (ice-9 generic= -hash-tables), 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 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 wou= ldn't need to also keep track of the number of elements (like SRFI-69 c= urrently does) and that would simplify its code.

B= esides, what about creating new versions HASHX-*=C2=A0procedures that accep= t an equivalence 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= implementation and standard tests. I've implemented according to the s= pecification - so, for instance, HASH-TABLE=3D? checks if the equivalence f= unction of both hash tables are the same and HASH-TABLE returns an immutabl= e hash table.

Code is public and suggestions are a= lways welcome :)
<= br>
Regargs,
J=C3=A9ssica

Em dom, 30 de dez de 2018 =C3=A0s 15:50, Amir= ouche Boubekki <amirouche@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
--0000000000002f58b4057fe7f7d0--