JuliaLang:master ← JuliaLang:kf/immutarray
opened 07:51PM - 05 Apr 19 UTC
This is part of a larger set of overhauls I'd like to do in the 2.0 timeframe (a…long with #21912 and other things along these lines). As such this is more of a straw-man implementation to play with various ideas. I doubt any of this code will get merged as is, but should provide a place for experimentation and we may start picking off good ideas from here.
The basic concept here is that I think we're missing a heap-allocated *immutable* array. We have Array (mutable and dynamically sized), StaticArray (immutable and statically sized) and MArray (mutable and statically sized), but we don't really have an immutable dynamically sized array. This PR adds that.
In my ideal world, most functions would return immutable arrays. In a lot of code, it is fairly rare to require semantically mutable arrays at the highest level of the API (of course operations are internally often implemented as mutating operations) and even in a good chunk of the cases that make use of them, they are used as a performance optimization rather than a semantic necessity.
On the other hand, having an immutability guarantee can be quite useful. For example, it would solve a lot of the performance problems around aliasing (the reason LLVM can't vectorize in a lot of cases is that it doesn't know that the output array doesn't overlap the input array - if the input array is immutable that obviously can't happen).
Immutability is also nice for higher level applications. Since views and slices are the same thing in immutable arrays, operations that would semantically be required to make copies on mutable arrays (say an AD system taking captures during the forward pass), can use views instead.
Now, the problem here of course is that sometimes you do want mutation, particularly during construction of various objects (i.e. you construct the object once by setting something to every memory location, but then it's immutable afterwards). This PR introduces the `freeze` function, which takes a mutable array and returns an immutable array with the same memory contents. Semantically this function is a copy, but the idea is that the compiler will be able to elide this copy in most circumstances, thus allowing immutable arrays to be constructed using mutating operations without overhead. Similarly, there is the `melt` function which does the opposite. Once this infrastructure is mature, it should be trivial to get either the immutable or the mutable version in a zero-overhead (after compiler optimizations) manner of any array function just by adding the appropriate freeze/melt function. The 2.0 goal would then be to actually make most array operations return the immutable versions of the array.
Another motivation here is to make it easier to write code that it generic over mutability in order to support things like XLA and other optimizing linear algebra compilers that operate on immutable tensors as their primitives. By having a well defined way to talk about mutability in the standard library, it should be easier to plug in those external implementations seamlessly.