Hacker News Reader

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?

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.

I'm not one of the creators of Julia (though am a contributor), but I would argue that there are many algorithms which are much simpler when one can mutate in-place. For example

- many low-level linear algebra operations, such as Householder reflections or Givens rotations.

- sorting: a true implementation of QuickSort relies on being able to mutate the list. This is why naive implementations in Haskell are punitively slow (or at least they were last time I checked).

Now of course, a good compiler may be able to identify when it can safely mutate an existing structure vs copy to a new one. But this is far from easy to do, and can result in users writing complicated code in order to optimise against the compiler (which may no longer be optimal with the next version of the compiler).

In the specific case of Julia, I think it has settled to a fairly good compromise. It provides lots of immutable structures (structs, tuples, etc.), and has a convention of suffixing mutating functions with an exclamation mark (e.g. sort!(X)). I haven't seen too many cases where users have had problems with accidental mutation.

I agree that a language with Julia's goals needs to provide mutable vectors, matrices, etc. I just don't agree that these should be the most commonly used versions, or the ones that a newcomer to Julia learns about first.

Certainly, in my own work (admittedly in a different domain) I occasionally need a mutable map or set or list for some particular algorithm, but this is the relatively rare case. Most of the time, functional collections work just fine and make the algorithms more elegant rather than less so.

The most commonly used functions/methods are the non-mutating versions, that newcomers to Julia do learn about first. (The exception being assigning values to vectors and dictionaries using `setindex!`, as in `vector[i] = x` or `dict[key] = value`.)

A lot of user code just uses functional methods on types which have the potential to be mutated. OTOH, library methods that are called by the user often involves optimized code that might be doing mutation internally but presents a functional interface, such as `sort(vector)` (which basically uses `sort!(copy(vector))` internally).

In principle, I'm very much predisposed to collections that are purely functional. I know that Apache Arrow (https://arrow.apache.org/) aims to create an interoperable in-memory dataframe structure that tries to take into account CPU caches and other dark-magic-from-my-perspective things.

Any reason why a purely functional data structure shouldn't be able to achieve the aims that something like Arrow is attempting?

Incidentally fset looks really impressive.

"I think it's unfortunate that the Julia creators didn't realize this, and have gone back to imperative semantics for their collections."

I'm a fan of immutable containers. Makes all sorts of things just easier. But I was under the impression there is no known way to implement efficient graph algorithms using immutable containers - with performance on par with a mutable implementation that is.

This alone is a sufficient reason not to default on immutable for a language with performance as one of the key requirements, IMO.

The research I did was from a few years back and things might have changed. I'd like to know if this is the case :)

I disagree since it's suppose to be a scientific language. IMO it should aim to be a DSL to that effect; ergonomic for the purpose of analysing and calculating. Kind of like a declarative language; the hard stuff should be left to the compiler where it's possible. Again, I think Clojure does a good job at this.

"Kind of like a declarative language; the hard stuff should be left to the compiler where it's possible. "

That's the holy grail of numerics. I don't think that's feasible if they want to cater to researchers who need to hand tune their algorithms.

We are quite far off from "do what I mean" semantics. Clojure's approach works for a grammar of very limited set of very well understood container operations.

If you want symbolic computations use e.g. Mathematica, Macsyma, etc.

A while back I remember someone tried to write an alternative R implementation.

Can you call R from Julia yet? You can do it from Python, but converting between R and Python data structures can be painful. I imagine it would be less so with Julia being "more vectorized" than Python.

There's also the issue that vectorized operations tend to be very _fast_ but algorithmically inefficient. Even if expressions are evaluated lazily, there is no compiler to recognize that computing the value of

    any(is.na(x))

can short-circuit as soon as a single NA value is found. Instead all of `is.na(x)` is computed first, and then `any()` is computed on the result.

I imagine this a problem in any non-compiled (ahead-of-time or just-in-time) language. Wondering what your thoughts were, since it seems like a related issue.

> Can you call R from Julia yet?

Yes. There's even an R REPL mode.

https://github.com/JuliaInterop/RCall.jl

> A while back I remember someone tried to write an alternative R implementation.

Renjin? http://www.renjin.org/downloads.html

> Imperative collections are harder to reason about, especially for inexperienced programmers.

That's a blanket statement that is completely unsubstantiated.

In expect that, in reality both have strength and weaknesses and it depends very much on the person. Myself I always find imperative style much more manageable when programming in the small. And before you claim I was biased, I was exposed to functional programming almost from the start (and frankly I'm quite fond of it, but it's just another tool not a religion).

The real question is why you are conflating an execution style with a data structure.