search

konsumlamm / rrb-vector

An implementation of a Relaxed Radix Balanced Vector in Haskell.
BSD 3-Clause "New" or "Revised" License
20 stars 5 forks source link

Unboxed RRB-Vector #5

Closed konsumlamm closed 2 years ago

konsumlamm commented 3 years ago

Originally proposed by u/sansboarders on reddit.

Using unboxed arrays in the tree structure would probably improve performance (note that I haven't done any benchmarks yet, so I'm not sure). There are a few different "kinds of unboxed values" to consider:

I don't know what the differences (in performance and ergonomics) between these three are or if it's possible to use these for the inner nodes (instead of only the leafs), so input on this is welcome.

One thing I'd like to avoid is duplicating too much code for this. One solution would be to implement a common typeclass, although this would probably make things slower (unless everything is specialized?) and type inference worse, so I'm not sure it's worth the trouble.

konsumlamm commented 3 years ago

I have done some naive benchmarking with using PrimArrays for the leafs and there was no relevant performance gain. As far as I can tell, it's not possible to make Prim/Unbox/Storable instances for the inner nodes, so unboxed RRB-Vectors are probably not worth it.

If someone has a design that shows notable performance improvements over standard RRB-Vectors, please let me know.

konsumlamm commented 3 years ago

@Boarders apparently you're u/sansboarders on reddit, so you might be interested in this.

konsumlamm commented 2 years ago

Closing, due to the problems described in https://github.com/konsumlamm/rrb-vector/issues/5#issuecomment-883721192. If anyone has an idea how to solve those, please leave a comment and I can reopen the issue.