Raising awareness about guile-pfds status

Raising awareness about guile-pfds status

[Amirouche Boubekki]

The original maintainer of guile-pfds is sadly not responding to my mails.

Right now, guile-pfds is the goto solution for functional data structures
in Guile,
and prolly other Scheme implementations.

At least the hamt has a bug, see https://github.com/ijp/pfds/pull/6/files

I think this is a very important package especially for guile that doesn't
have a functional hashmaps.

Anyone willing to take ownership of the project?


ref: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=35518

-- 
Amirouche ~ amz3 ~ https://hyper.dev

Re: Raising awareness about guile-pfds status

[Nala Ginrut]

I'll rewrite a new one when I got time.

Amirouche Boubekki <amirouche.boubekki@gmail.com> 于 2019年7月16日周二 00:06写道：

> The original maintainer of guile-pfds is sadly not responding to my mails.
>
> Right now, guile-pfds is the goto solution for functional data structures
> in Guile,
> and prolly other Scheme implementations.
>
> At least the hamt has a bug, see https://github.com/ijp/pfds/pull/6/files
>
> I think this is a very important package especially for guile that doesn't
> have a functional hashmaps.
>
> Anyone willing to take ownership of the project?
>
>
> ref: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=35518
>
> --
> Amirouche ~ amz3 ~ https://hyper.dev
>

Re: Raising awareness about guile-pfds status

[Linus Björnstam]

If it is HAMTs or persistent vectors you want, I have a git repo of Andy's Fash and Fector (functional hashmaps and functional.vectors). Fash lacks some parts to become a fast implementation of (srfi 146 hash), like being able to properly delete keys. I would implement it myself if I had any friggin idea what the code did, but to my limited mind it is quite impenetrable.

Other than that, I have a decently fast implementation of a pairing heap in my Nietzsche repo, which I found is generally slightly faster than the height balanced leftist tree in the PFDS library (and, should be said, about an order of magnitude slower than a regular binary heap using vectors).

The Fector library: https://bitbucket.org/bjoli/guile-fector

The fash library: https://bitbucket.org/bjoli/guile-fash/

My pairing heap: https://bitbucket.org/bjoli/nietzsche/src/default/data/pairing-heap.scm

I don't know how using records compares to using cons pairs in guile, but there might be some speed gains. It also lacks a proper (as in fast) list->node because my 23 year old me didn't know how to implement it. It should be trivial. 

Fash and Fector are very fast. Andy likes speed :)


-- 
  Linus Björnstam

On Mon, 15 Jul 2019, at 18:06, Amirouche Boubekki wrote:
> The original maintainer of guile-pfds is sadly not responding to my mails.
> 
> Right now, guile-pfds is the goto solution for functional data structures
> in Guile,
> and prolly other Scheme implementations.
> 
> At least the hamt has a bug, see https://github.com/ijp/pfds/pull/6/files
> 
> I think this is a very important package especially for guile that doesn't
> have a functional hashmaps.
> 
> Anyone willing to take ownership of the project?
> 
> 
> ref: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=35518
> 
> -- 
> Amirouche ~ amz3 ~ https://hyper.dev
>

Re: Raising awareness about guile-pfds status

[John Cowan]

On Mon, Jul 15, 2019 at 4:50 PM Linus Björnstam <linus.internet@fastmail.se>
wrote:

If it is HAMTs or persistent vectors you want, I have a git repo of Andy's
> Fash and Fector (functional hashmaps and functional.vectors). Fash lacks
> some parts to become a fast implementation of (srfi 146 hash),


Is there a speed problem with the sample implementation of (srfi 146
hash)?  It's a HAMT package written by Art Gleckler.

Note that fectors are a bit specialized: they are very fast for both ref
and set if you don't change the "current branch" very often, but slower if
you do.  Ordinary tree functional vectors have the same big-O no matter
what.  There will be a fector SRFI.


John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
You are a child of the universe no less than the trees and all other acyclic
graphs; you have a right to be here.  --DeXiderata by Sean McGrath

Re: Raising awareness about guile-pfds status

[Linus Björnstam]

On Mon, 15 Jul 2019, at 23:19, John Cowan wrote:
> 
> 
> On Mon, Jul 15, 2019 at 4:50 PM Linus Björnstam 
> <linus.internet@fastmail.se> wrote:
> 
> > If it is HAMTs or persistent vectors you want, I have a git repo of Andy's Fash and Fector (functional hashmaps and functional.vectors). Fash lacks some parts to become a fast implementation of (srfi 146 hash), 
> 
> Is there a speed problem with the sample implementation of (srfi 146 
> hash)? It's a HAMT package written by Art Gleckler.

I didn't mean to sound like I was criticizing Arthur's implementation. What I meant was that fash currently lacks a fast way to delete keys. I could add a <fash-null> value and set a deleted value to that, but I would like to do it properly. 

Fash and Fector also does some things differently from the other HAMTs/pvectors I tried (note I did not try the reference implementation) that runs fast in guile. 

> Note that fectors are a bit specialized: they are very fast for both 
> ref and set if you don't change the "current branch" very often, but 
> slower if you do. Ordinary tree functional vectors have the same big-O 
> no matter what. There will be a fector SRFI.

Compared to Bagwell's VLists pvectors/fectors are generally slower, but adds the ability to set arbitrary values. I have been playing with the idea to create a fast, thread safe VList library with support for transients as I suspect it would be a slightly less capable, but much faster, alternative to fectors. Andy's fectors are actually faster than guiles VLists for everything except random access, but making the VLists support transients (and a way to iterate without using indexes) would change that.