I’ve been writing an immutable collections and STM library for Julia based on similar awesome libraries in scala and clojure (work in progress, but repo is here). As I’ve been writing it, I’ve noticed that some of the operations have a performance comparible with both Julia’s native types and clojure’s persistent types (e.g., for the persistent dictionary type PDict: get, in, haskey are very fast). However, other operations, despite being implemented very similarly to clojure’s, have many orders of magnitude lower performance in Julia: for example PDict is ~200-300x slower than Julia’s mutable Dict for insert and about 100x slower than clojure’s persistent map. To be clear, it shoud be slower than Julia’s mutable Dict but not this much slower.
In asking about performance in another thread it was suggested that most of the problem is due to my use of abstract types because some of the immutable types (especially the persistent vector type PVec, on the shoulders of which much of the library is built), encapsulate length in the type. This works approximately like this:
abstract type PVec{T} <: AbstractArray{T, 1} end
abstract type PSmallVec{T} <: PVec{T} end
# Length 0 vectors:
struct PVec0{T} <: PSmallVec{T} end
Base.length(::PVec0) = 0
Base.getindex(u::PVec0, k) = throw(BoundsError(u, [k]))
# Length 1 vectors:
struct PVec1{T} <: PSmallVec{T}
val::T
end
Base.length(::PVec1) = 1
Base.getindex(u::PVec1{T}, k::Integer) where {T} = begin
(k == 1) || throw(BoundsError(u, [k]))
return u.val
end
# ...
# PVec1 through PVec32 are actually generated by macro; they
# store data in NTuples and have a more complete set of methods.
# ...
# Vectors longer than 32 elements:
struct PBigVec{T} <: PVec{T}
n::Integer # vector length
# by using a vector of vectors, we ensure that update operations are
# O(log n) rather than O(n)
data::PVec{PSmallVec{T}}
end
Base.length(u::PBigVec) = u.n
Base.getindex(u::PBigVec{T}, k::Integer) where {T} = begin
if k < 1 || k > n
throw(BoundsError(u, [k]))
else
return u.data[((k - 1) >> 5) + 1][((k - 1) & 0x1f) + 1]
end
end
I would like to be able to avoid encapsulating the length in the type, but I don’t see a good way to do this; as far as I can tell:
- using either fields of an immutable struct to store the vector elements or using
Tuples orNTuples both require that the number of elements is known at compile time and that any vector of variable length be filtered through an abstract class (like in my implementation); - using an
Arraywould break immutability.
In theory, I could use an Array to store the elements and just keep the field “private” such that users can’t (trivially) mutate the objects. This might be okay but for two things. First, I don’t know to what extent this would sacrifice compiler optimizations for immutable types (is there documentation about this somewhere?). Second, it breaks the === operator and the objectid function. (Third, I suppose, is purity of the implementation, but I’m only passingly interested in that.)
My questions:
- Is there an alternative way to implement this I haven’t noticed that gets around the problem?
- If I use a type built on
Arrayinstead of thePSmallVectypes, what compiler optimization am I sacrificing? Are there other known side-effects of using a mutable field that will cause problems in an immutable collections library? - Assuming there isn’t an immutable array type I’m unaware of, is this something that could be added to Julia? (to be clear, I’m not asking for someone to go do this, I’m asking if a pull request adding this to the core would be well-received, or if there are reasons it’s not compatible with Julia’s design?)
- Any tips on how to tell, from the output of
ProfileandProfileView, that Julia is slow because of the abstract type system?