bodil
commented
6 years ago I caught your paper at ICFP last year, it was easily my favourite presentation of the conference (but obviously I'm biased by the topic). 👍
Yeah, I'm boxing and reference counting values, it's not at all great for cache locality, and I'm not sure there's an easy way around it for complex values. The difference when using primitive values without boxing is dramatic (see #12 for one) but I'm still trying to figure out a clean API that would easily enable both. One could leave the boxing of complex types to the end user at the cost of a little cognitive overhead, but I'd prefer a best of both worlds solution. It hasn't yet presented itself...
I'm looking at RRB trees as well as this interesting finger tree variant right now. RRB trees seem a lot easier to implement in Rust than finger trees.
I'll be sure to let you know when I think I have code that's good enough to benchmark. 😊
Hi!
First of all: this is amazing work. I was long waiting for someone to go ahead and do this. The code looks very good and you also seem to be very fast in making progress! :smile:
I myself have been doing some work on bringing Clojure-like data-structures to system languages, but in the ugly land of C++, which resulted in the Immer library and this paper. One of the things that took most effort there (and brought most complexity) is to try achieve the most cache locality possible. In particular, vector elements are not boxed individually but live in the same array block. Studying your code, it seems to me that you are boxing the elements individually, and it seems to me that it would be impossible to do otherwise without adding ridiculous amounts of
unsafe {}code. Do you have some thoughts on that?Also, do you plan to implement catenable vectors (Relaxed Radix Balanced trees)?
Once again, congrats! I would be interested also in trying to do some benchmarking between the libraries. Let me know eventually if you would like to work together on that to try to find useful and fair benchmarks!
Cheers!