3 ms·

Your work on FSet looks excellent! Working with purely functional collections is certainly a lovely, coherent design (and, for what it's worth, something we wer

Your work on FSet looks excellent! Working with purely functional collections is certainly a lovely, coherent design (and, for what it's worth, something we were aware of when we started Julia). I can't find any benchmarks on the FSet site comparing performance of functional collections with their standard mutable counterparts. As the most basic example, I'd be interested in seeing a comparison of getindex and setindex on functional vectors as compared with the same operations on simple contiguous-memory arrays. The asymptotic performance of FSet operations is well documented – and as the site says, quite "acceptable". However, every time I've investigated purely functional data structures in the past, I've found that while the asymptotic behavior is fine, the constant-factor overhead for some critical operations is just too high. Retrieving a single element from an array, for example, was about 10x slower using Clojure's functional vectors than Java arrays when I benchmarked it some years ago. Perhaps the gap has been closed much further since then, and if so I'd would definitely love to see benchmarks to that effect. Did I miss benchmarks on the FSet site?

ScottBurson 9y ago
Thanks! No, I don't have benchmarks. My guess is that FSet is not as fast as the Clojure collections, which use a newer data structure (Phil Bagwell's Hash Array-Mapped Trie) that I didn't know about when I wrote FSet. -- Um, that's for sets and maps. For seqs (functional vectors), I'm not sure but I think the Clojure data structure is very similar to FSet's. I think the odds that FSet is significantly faster than Clojure are small, though I suppose it's worth checking. For the domain I work in -- compilers and static analysis -- the additional overhead of functional collections has only rarely been an issue in practice. It's different from numerics, though, in that a lot of our collections are maps keyed by nonnumeric objects; the time spent hashing the object and testing it for equality with other objects is relatively much larger than when the keys are simply integers, and therefore the time spent traversing the data structure itself is a smaller part of the total. I concede that designing functional collections for use in high-performance numeric work is a harder problem, though I still suspect that solutions may exist. See my reply to your other post.

ScottBurson 9y ago

Thanks! No, I don't have benchmarks. My guess is that FSet is not as fast as the Clojure collections, which use a newer data structure (Phil Bagwell's Hash Array-Mapped Trie) that I didn't know about when I wrote FSet. -- Um, that's for sets and maps. For seqs (functional vectors), I'm not sure but I think the Clojure data structure is very similar to FSet's. I think the odds that FSet is significantly faster than Clojure are small, though I suppose it's worth checking. For the domain I work in -- compilers and static analysis -- the additional overhead of functional collections has only rarely been an issue in practice. It's different from numerics, though, in that a lot of our collections are maps keyed by nonnumeric objects; the time spent hashing the object and testing it for equality with other objects is relatively much larger than when the keys are simply integers, and therefore the time spent traversing the data structure itself is a smaller part of the total. I concede that designing functional collections for use in high-performance numeric work is a harder problem, though I still suspect that solutions may exist. See my reply to your other post.