Short-circuit evaluation for multiplication

210 views
Skip to first unread message

Jan Drugowitsch

unread,
Jul 2, 2015, 9:47:59 AM7/2/15
to julia...@googlegroups.com
Dear Julia users,

I am implementing an algorithm to solve a specific type of Volterra integral equation, and that simplifies significantly if some of its parameters are set to zero or one. The function implementing the algorithm takes quite a few arguments, such that writing specific versions for different arguments being zero/one would lead to too many different functions, which I would like to avoid. What I would rather like to do is to write one generic function and let the compiler prune different parts of the function, depending on the argument types.

A minimal example of what I would like to do is

immutable Zero <: Number; end

const _zero = Zero()

Base.promote_rule{T<:Number}(::Type{Zero}, ::Type{T}) = T
Base.convert{T<:Number}(::Type{T}, ::Zero) = zero(T)

*(::Zero, ::Zero) = _zero
*(::Zero, ::Bool) = _zero
*(::Bool, ::Zero) = _zero
*(::Zero, ::Number) = _zero
*(::Number, ::Zero) = _zero

f
(a, b, c) = a * (println("summing b + c"); b + c)

println
("Evaluating f(0, 1, 2)")
f
(0, 1, 2)
println
("Evaluating f(_zero, 1, 2)")
f
(_zero, 1, 2)

Running the above results in

Evaluating f(0, 1, 2)
summing b
+ c
Evaluating f(_zero, 1, 2)
summing b
+ c

even though the result of the second "summing b + c" is discarded, and therefore wouldn't need to be evaluated. This is no surprise, as *(.,.) is a standard function that evaluates its operands before applying the function. Is there any way to change this behavior and turn *(.,.) into a function that performs short-circuit evaluation? If not, is there an alternative approach that achieves this without writing tons of specialized functions?

Thanks,
Jan

Tom Breloff

unread,
Jul 2, 2015, 10:48:52 AM7/2/15
to julia...@googlegroups.com
Just curious... is there a reason simply checking for non-zero isn't enough?  Readability? Performance?

f(a,b,c) = (Bool(a) ? a * (b + c) : 0.0)

Yichao Yu

unread,
Jul 2, 2015, 10:55:33 AM7/2/15
to Julia Users
On Thu, Jul 2, 2015 at 10:48 AM, Tom Breloff <t...@breloff.com> wrote:
> Just curious... is there a reason simply checking for non-zero isn't enough?
> Readability? Performance?
>
> f(a,b,c) = (Bool(a) ? a * (b + c) : 0.0)

I'm guessing he want all code that gets his type automatically gets
this behavior? If yes, I don't think there's anyway you can do that.
If not, then just writing the branch or having a macro to rewrite that
in your own code is probably the best solution.

Jan Drugowitsch

unread,
Jul 2, 2015, 11:09:12 AM7/2/15
to julia...@googlegroups.com
On Thursday, 2 July 2015 16:55:33 UTC+2, Yichao Yu wrote:
On Thu, Jul 2, 2015 at 10:48 AM, Tom Breloff <t...@breloff.com> wrote:
> Just curious... is there a reason simply checking for non-zero isn't enough?
> Readability? Performance?
>
> f(a,b,c) = (Bool(a) ? a * (b + c) : 0.0)

I'm guessing he want all code that gets his type automatically gets
this behavior? If yes, I don't think there's anyway you can do that.
If not, then just writing the branch or having a macro to rewrite that
in your own code is probably the best solution.

Indeed, the reason why I don't want to check for zeros and ones explicitly is that some of these appear in inner loops and would reduce performance.

I already thought of macros as a possible solution, but I was wondering if the same could be achieved in a more implicit/elegant way.

Thanks,
Jan

Stefan Karpinski

unread,
Jul 2, 2015, 11:12:50 AM7/2/15
to Julia Users
Is this a toy reduction of a concept that you want to apply in a much more complex way?

Yichao Yu

unread,
Jul 2, 2015, 11:13:50 AM7/2/15
to Julia Users
On Thu, Jul 2, 2015 at 11:09 AM, Jan Drugowitsch <jdr...@gmail.com> wrote:
> On Thursday, 2 July 2015 16:55:33 UTC+2, Yichao Yu wrote:
>>
>> On Thu, Jul 2, 2015 at 10:48 AM, Tom Breloff <t...@breloff.com> wrote:
>> > Just curious... is there a reason simply checking for non-zero isn't
>> > enough?
>> > Readability? Performance?
>> >
>> > f(a,b,c) = (Bool(a) ? a * (b + c) : 0.0)
>>
>> I'm guessing he want all code that gets his type automatically gets
>> this behavior? If yes, I don't think there's anyway you can do that.
>> If not, then just writing the branch or having a macro to rewrite that
>> in your own code is probably the best solution.
>
>
> Indeed, the reason why I don't want to check for zeros and ones explicitly
> is that some of these appear in inner loops and would reduce performance.
>
> I already thought of macros as a possible solution, but I was wondering if
> the same could be achieved in a more implicit/elegant way.

Implicit and elegant sometimes conflict with each other =)

If you have control over the code that uses this, using a macro is the
way to go. A function can't possibly do this.

You could have a look at https://github.com/one-more-minute/Lazy.jl though.

Jan Drugowitsch

unread,
Jul 2, 2015, 11:20:53 AM7/2/15
to julia...@googlegroups.com
Is this a toy reduction of a concept that you want to apply in a much more complex way?

Yes, it was just meant to illustrate the concept.

It should be applied to a function that has roughly the complexity of https://github.com/jdrugo/DiffModels.jl/blob/master/src/fpt.jl#L153
(in fact, it would be the first and second derivative of this function with respect to parameters of drift and bounds).

Jan 

Jan Drugowitsch

unread,
Jul 2, 2015, 11:22:40 AM7/2/15
to julia...@googlegroups.com
On Thursday, 2 July 2015 17:13:50 UTC+2, Yichao Yu wrote:
On Thu, Jul 2, 2015 at 11:09 AM, Jan Drugowitsch <jdr...@gmail.com> wrote:
> On Thursday, 2 July 2015 16:55:33 UTC+2, Yichao Yu wrote:
>>
>> On Thu, Jul 2, 2015 at 10:48 AM, Tom Breloff <t...@breloff.com> wrote:
>> > Just curious... is there a reason simply checking for non-zero isn't
>> > enough?
>> > Readability? Performance?
>> >
>> > f(a,b,c) = (Bool(a) ? a * (b + c) : 0.0)
>>
>> I'm guessing he want all code that gets his type automatically gets
>> this behavior? If yes, I don't think there's anyway you can do that.
>> If not, then just writing the branch or having a macro to rewrite that
>> in your own code is probably the best solution.
>
>
> Indeed, the reason why I don't want to check for zeros and ones explicitly
> is that some of these appear in inner loops and would reduce performance.
>
> I already thought of macros as a possible solution, but I was wondering if
> the same could be achieved in a more implicit/elegant way.

Implicit and elegant sometimes conflict with each other =)

If you have control over the code that uses this, using a macro is the
way to go. A function can't possibly do this.

You could have a look at https://github.com/one-more-minute/Lazy.jl though.

Thanks, I'll check it out.

Jutho

unread,
Jul 2, 2015, 11:47:16 AM7/2/15
to julia...@googlegroups.com
Depending on how much more complicated your actual use case is, could you not just write f(a,b,c) = a*b + a*c instead of a*(b+c)? I guess the former would be evaluated immediately at compile time if a is _zero ?

Stefan Karpinski

unread,
Jul 2, 2015, 7:51:19 PM7/2/15
to Julia Users
Can you elaborate on why that kind of code needs this unusual evaluation? It looks pretty reasonable as is to me.

Jan Drugowitsch

unread,
Jul 3, 2015, 2:47:28 AM7/3/15
to julia...@googlegroups.com
My aim is to write a Hamiltonian MCMC sampler that samples bound and drift parameter posteriors for bounded diffusion models while assuming some parametric form for how these bounds and the drift change over time. This requires the first and second derivative of the first-passage densities that are computed in https://github.com/jdrugo/DiffModels.jl/blob/master/src/fpt.jl#L153. For certain parametrization of drift and bound, partial derivatives will be one or zero, which would make some parts of the code computing the full derivatives drop out. To make this have an impact on performance, I thought of two approaches:
  • Write specialised functions for different parameterizations. This is the safe approach but would introduce many functions, as there are many possible combinations of drift and bound parameterizations. Also, it would not handle cases that I haven't thought of.
  • Write a generic function that only evaluates the parts of the code that influence the final result. Currently, it seems that macros are the best way to achieve this. The advantages would be that it only requires me to write the function once, avoiding code replication and associated bugs. Also, it should be able to handle cases that I haven't thought of.
Note that the code linked above currently does not compute the derivatives. Due to several exp(.), the code that computes the derivatives will be significantly longer, such that not evaluating parts of it should lead to faster execution (not in the big-O sense, but reducing the constant).

Jan

Simon Byrne

unread,
Jul 3, 2015, 5:25:30 AM7/3/15
to julia...@googlegroups.com
If the zeros are known at compile time, LLVM may optimise away some unnecessary operations:

julia> foo(x) = x + 0*(x*x + 2)

foo (generic function with 1 method)


julia> @code_llvm foo(1)


define i64 @julia_foo_21664(i64) {

top:

  ret i64 %0

}


Unfortunately, this doesn't work as is with floating point numbers:

julia> @code_llvm foo(1.0)


define double @julia_foo_21665(double) {

top:

  %1 = fmul double %0, %0

  %2 = fadd double %1, 2.000000e+00

  %3 = fmul double %2, 0.000000e+00

  %4 = fadd double %3, %0

  ret double %4

}


The problem here is that there are a few "special" values that may not give the correct answer, e.g. Inf. However we can use the @fastmath macro to tell LLVM to ignore these cases:

julia> foo(x) = @fastmath x + 0*(x*x + 2)

foo (generic function with 1 method)


julia> @code_llvm foo(1.0)


define double @julia_foo_21656(double) {

top:

  ret double %0

}


Unfortunately, this doesn't work correctly for more general functions (such as exp), as LLVM doesn't know these don't have side-effects (see https://github.com/JuliaLang/julia/issues/414).

-Simon
Reply all
Reply to author
Forward
0 new messages