-
Notifications
You must be signed in to change notification settings - Fork 22
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Fast JS RRB-tree #31
Comments
Hi @paldepind! Really fantastic work on this implementation, that is wonderful to see! I think I am going to leave this library as-is for now, because I think it's useful that it doesn't use the FFI. This means that people compiling to languages other than JS can still use it. However, having a nice set of bindings to this library would be fantastic! I realise it has taken me a really long time to respond so this might not be useful at this point, but perhaps |
@hdgarrood link to the PR for bindings funkia/list#27. Note that the existing docs are straight from |
Thanks for asking :) |
Thank you for the reply @hdgarrood. Good point about this library not being reliant on JavaScript. I think the name |
Right, yeah. If it was up to me I’d probably prefer |
Hello @hdgarrood
I've implemented a highly optimized immutable JavaScript list/sequence that I think could be useful to the PureScript community. I'd love to get your feedback. In particular, I don't know what name to publish the package under.
The library is an implementation of a data-structure called relaxed radix balanced trees. RRB-trees have essentially the same complexities as finger tree and I've also experimented with creating a highly optimized finger tree implementation. But, I've found that RRB-trees offer significantly lower constant factors. I have a benchmark suite here that compares the performance of List to native arrays and other JS libraries. I also ran List with your benchmark suite and I've included the results below. As you can see the performance is very good 😄
Since the JS library simply is called List the obvious name for the PureScript package would be purescript-list. But that is already the name of something else. Thus I'm wondering, what would be a good name to pick? As the graphs below show the performance of List is better than
Data.Sequence
. So one option would be to replace the currentpurescript-sequences
with a wrapper around List. What do you think about that? Alternatively, is there some other name that would "make sense" and follow the module naming conventions?Btw, @gabejohnson has created the PureScript bindings for List. He had the great idea to make the API identical to the
Data.Array
API. Therefore it can serve as a faster drop-in replacement forData.Array
.Benchmark results:
The text was updated successfully, but these errors were encountered: