unnecessary slow code generated by if-then statement

[StephenVavasis]

The function t2() below runs much more slowly than t1() apparently because a lot of extra unnecessary code is being generated by the compiler.

module testcodegen1

function t1(x::Float64)
    s = 0.0
    for i = 1 : 20000000
        s += sin(x)
    end
    s
end

function t2(x::Float64)
    s = 0.0
    for i = 1 : 20000000
        if true
            s += sin(x)
        else
            s += sin(2*x)
        end
    end
    s
end

end


julia> tic(); testcodegen1.t1(3.0);  toc()
tic(); testcodegen1.t1(3.0);  toc()
elapsed time: 0.216690647 seconds
0.216690647

julia> tic(); testcodegen1.t2(3.0);  toc()
tic(); testcodegen1.t2(3.0);  toc()
elapsed time: 0.53437478 seconds
0.53437478

[quinnj]

See other issues where this has been brought up:

• eliminate constant dead branches earlier? #6822
• Do some constant propagation before type inference runs #5560

[Keno]

I'm surprised this isn't caught by llvm's constant folding though.

[timholy]

Thanks @StephenVavasis!

Because of branch-point prediction, it's basically irrelevant whether constant folding works or not---the CPU will learn that only one branch is ever taken.

The far more serious issue is a type inference problem. Check the memory allocation under @time and look at the variable types returned by code_typed.

julia> code_typed(t2, (Float64,))
1-element Array{Any,1}:
 :($(Expr(:lambda, {:x}, {{:s,symbol("#s121"),symbol("#s120"),symbol("#s119"),:i,:_var0,:_var1,:_var2},{{:x,Any,0},{:s,Any,2},{symbol("#s121"),UnitRange{Int64},18},{symbol("#s120"),Int64,2},{symbol("#s119"),(Int64,Int64),18},{:i,Int64,18},{:_var0,Float64,18},{:_var1,Int64,18},{:_var2,Int64,18}},{}}, :(begin  # none, line 2:

What are those Anys doing in there?

[StephenVavasis]

According to Tim Holy, the problem is not just with dead code elimination.
He says the compiler is actually generating a lot of additional
unnecessary type-conversion code.

-- Steve Vavasis

On Mon, 4 Aug 2014, Jacob Quinn wrote:

See other issues where this has been brought up:

• eliminate constant dead branches earlier? #6822
• Do some constant propagation before type inference runs #5560

—
Reply to this email directly or view it onGitHub.[7881863__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyMjgwNzM4OCwiZGF0YSI6eyJ
pZCI6Mzg3ODgwNDN9fQ==--e47371c60459afa2ed2659e12d109d1b48f697d4.gif]

[JeffBezanson]

Yes it looks like the unreachable code is poisoning something. Should be possible to fix this.

[timholy]

You probably already discovered this yourself, but if you change it to

function t2(x::Float64, b::Bool)
    s = 0.0
    for i = 1:20000000
        if b
            s += sin(x)
        else
            s += sin(2*x)
        end
    end
end

then the type inference is perfect. So it's the fact that it knows at compile time that it's unreachable that triggers the poisoning.

[StephenVavasis]

I would like to add: you might wonder why I would put "if true" in a Julia
code. The reason is that I am trying to use a single source-code file to
generate two versions, the "production" and "debug" version. In C++ this
is ordinarily accomplished by making a compiler option -DDEBUGGING
available and then using the preprocessor: #ifdef DEBUGGING ... #else ...
#endif. It should be possible to accomplish something similar in Julia,
except using macros, ordinary "if" statements and unreachable-code
elimination.

-- Steve Vavasis

On Mon, 4 Aug 2014, Tim Holy wrote:

You probably already discovered this yourself, but if you change it to

function t2(x::Float64, b::Bool)
s = 0.0
for i = 1:20000000
if b
s += sin(x)
else
s += sin(2*x)
end
end
end

then the type inference is perfect. So it's the fact that it knows at compile time that it's
unreachable that triggers the poisoning.

—
Reply to this email directly or view it onGitHub.[7881863__eyJzY29wZSI6Ik5ld3NpZXM6QmVhY29uIiwiZXhwaXJlcyI6MTcyMjgxMDczNywiZGF0YSI6eyJ
pZCI6Mzg3ODgwNDN9fQ==--9a29d1d376a639d0ce7fe1ac784c1949e866b2cc.gif]

[kmsquire]

Steve, as an aside, the Logging.jl package has a @debug macro which might do what you want. See https://github.com/kmsquire/Logging.jl.

[StefanKarpinski]

@StephenVavasis – that's a totally reasonable thing to do and obviously should work :-)

[JeffBezanson]

I have a fix for this.

[timholy]

Yay, very nice!