JuliaArrays / JuliaArrays/StaticArrays.jl

Haskell accelerate is intriguingly faster in some cases?

Open
#258 9 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance
Dominant language
Julia
Stars
844
Forks
159
Avg merge
3d 21h
Merged PRs (30d)
3

Description

As mentioned in passing on julialang slack, the following is an interesting and carefully considered blog post by @idontgetoutmuch, mainly about Haskell, but with an addendum comparing the speed of the resulting code to a julia implementation using StaticArrays:

https://idontgetoutmuch.wordpress.com/2017/06/02/1090/

It's a lot of LLVM assembly, but it's intriguing that there's possibly still a 2x speedup or so that we might be missing out on even for the following simple code (my interpretation of julia @idontgetoutmuch's implementation in julia idiom, possibly with added bugs):

@inline function oneStep(h, q, p)
    @inline nablaQQ(q) = q/norm(q)^3
    @inline nablaPP(p) = p
    p2   = p - h/2 * nablaQQ(q)
    qNew = q + h * nablaPP(p2)
    pNew = p2 - h/2 * nablaQQ(qNew)
    return qNew, pNew
end

function manyStepsFinal(f, n, h, q, p)
    for i in 1:n
        q, p = f(h, q, p)
    end
    return q,p
end


e = 0.6
q10 = 1 - e
q20 = 0.0
p10 = 0.0
p20 = sqrt((1 + e) / (1 - e))

h = 0.01

q0 = SVector{2,Float64}(q10, q20)
p0 = SVector{2,Float64}(p10, p20)

manyStepsFinal(oneStep, 1, h, q0, p0) # jit warm up
@time qf, pf = manyStepsFinal(oneStep, 10_000_000, h, q0, p0)

I tried a lot of tweaks to get the 2x speedup, including running with julia -O3 --math-mode=fast, and writing the oneStep() function in vectorized vs non-vectorized LLVM assembly by hand. None of these made things appreciably faster than just using the version above with julia-0.6. I'd probably need to actually benchmark the Haskell version locally to make any more progress...

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the linked blog post and the oneStep and manyStepsFinal benchmarks using StaticArrays.SVector, then reproduce the Julia 0.6 timing and benchmark the Haskell version locally. Done means identifying and documenting a reproducible performance gap or a concrete Julia optimization opportunity.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell, julia
Domain
performance
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.