The length of Julia’s IR/LLVM IR/Assembly doesn’t really directly determine complexity/better/worse. You gotta benchmark to see any effect unless you know that particular IR and your machine very well. All of these forms can call functions which can hide such complexity — and in this case I’d guess the inlined version and the impure version are probably performing about the same (definitely not much much worse).
Now, yes, in this case inlining and constant propagation didn’t work because you’re accessing (and modifying!) an array of arrays with non-constant values. I’d give up on the cache and just code it straight — it’s easier to see bugs this way, too:
function binomsum(n::Int, i::Int)
s = 0
for j in 0:i-1 # was this off-by-one intentional?
s += binomial(n, j)
end
s
end
Now, I think you may be able to mark this one Base.@pure. If you do so you get the same effect. If binomial got @inlined, then it can constant-propagate, but even still we aren’t using constants in our for-loop there. Probably easier to just @memoize things and not worry about the lookup branch unless you see it coming up as a major factor in a profiling run.
Nope, at least not as far as multi-threading goes:
julia> Base.@pure function binomsum(n::Int, i::Int)
s = 0
for j in 0:i-1 # was this off-by-one intentional?
s += binomial(n, j)
end
s
end
julia> Base.Threads.@threads for i ∈ 1:16
println(binomsum(i,2))
end
8
9
signal (11): Segmentation fault
in expression starting at no file:0
jl_apply_generic at /usr/bin/../lib/libjulia.so.1 (unknown line)
unknown function (ip: 0x7f544cd920cd)
unknown function (ip: 0xffffffffffffffff)
Allocations: 18824129 (Pool: 18819991; Big: 4138); GC: 55
Segmentation fault (core dumped)
Here’s how you can get constant propagation working:
# Mark binomial as `@inline` using the definition from Base:
julia> @eval Base @inline function binomial(n::T, k::T) where T<:Integer
...
end
# Define `binomsum` with some of the loops unrolled — this could be done via metaprogramming
julia> @inline function binomsum(n, i)
i == 0 && return 0
s = binomial(n, 0)
i == 1 && return s
s += binomial(n, 1)
i == 2 && return s
s += binomial(n, 2)
i == 3 && return s
s += binomial(n, 3)
i == 4 && return s
for j in 4:i-1
s += binomial(n, j)
end
s
end
binomsum (generic function with 1 method)
julia> f() = binomsum(5, 2)
f (generic function with 1 method)
julia> f()
6
julia> @code_warntype f()
Body::Int64
1 ─ return 6
This makes for a monstrously huge function body, though. It’d be nice if there were a better way.
Your segfault comes from println, which is not threadsafe.
@mbauman’s binomsum is almost @pure, except for the unfortunate side-effect that binomial decides to throw overflow errors on some inputs. I think this precludes @pure?
Without this execution path, the compiler would probably figure out that it is @pure without any “helpful” annotation.
Someone should maybe implement unsafe_binomial without overflow checking, or return -1 as a guard value for overflowing things.
help?> Base.@pure
@pure ex
@pure(ex)
@pure gives the compiler a hint for the definition of a pure function,
helping for type inference.
A function is pure if and only if Jameson Nash says that it is pure.
Now that I understand this, I found that the cached version is actually thread safe.
That issue can easily be resolved simply by making sure that binomsum gets called for the needed value of n at least once before it is used in multiple threads. If the method has been called once for the relevant value of n, then the method is thread safe since it doesn’t need to extend the array in that case. In my case, it would be enough to simply call binomsum(16,1) once at the beginning, and then all other calls should be thread safe (since I only handle n<17 in my package).
const binomsum_cache = [[1]]
Base.@pure function binomsum(n::Int, i::Int)
for k=length(binomsum_cache)+1:n
push!(binomsum_cache, cumsum([binomial(k,q) for q=0:k]))
end
i ≠ 0 ? binomsum_cache[n][i] : 0
end
no problem with @threads without println
julia> binomsum(16,1);
julia> Base.Threads.@threads for i ∈ 2:16
binomsum(i,2)
end
One solution is to simply put binomsum(16,1) into the __init__() script, where 16 is the max value of n encountered. This ensures that issues with @pure and multi-threading are avoided.
The phrase “copy constructor” is not used so much in Julia (it comes e.g. from C++), which is why I put it in quotes.
It means a constructor in which you pass in an argument of a given type and it constructs a new object of that type by copying the fields from the argument to the new object.
My point was that by default a Vector will not be copied if you do this; you will just have a reference to the same Vector as in the original object, so if you modify one the other gets modified too. You can use the copy function if you actually want a new copy.
We see that inc is an immutable struct <: Function, with a fancyful name and a single member field x, of type Core.Box.
In order to see the methods, let’s look at:
julia> tp.name.mt
# 1 method for generic function "(::inc)":
[1] (::getfield(Main, Symbol("#inc#6")))() in Main at REPL[78]:4
We see that inc has a single method without any arguments.
It would be nice if there was some pretty-printer for types in julia (give me a reconstructed julia-syntax like thing, with annotations for fieldoffsets and padding). Unfortunately I don’t know one
