Complex where clause in promote_rule

syntax

#1

I’d like to better understand what is possible to do in the where clause of a typed function.
In my case, I’m trying to enhance fixed-point arithmetics for a project that verifies an algorithm to be implemented on an embedded HW in fixed point arithmetics.

is it possible to define a promote rule for addition to take the fixed-point with greater “precision” (amount of decimal places) like this (do some arithmetics in the where clause) ?

promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed, f1, f2} where f1>f2 = Fixed{T,f1}
promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed, f1, f2} where f1<f2 = Fixed{T,f2}

This syntax errors with “error in where statement”. What works correctly - but produces a very slow code (1000x degradation) is

promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed, f1, f2} = Fixed{T,f1>f2?f1:f2}

If I try it with “hardcoded” not correct version that works only for f2 > f1 (but produces always the same type result)

promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed, f1, f2} = Fixed{T,f2}

it runs on full speed!

The full code snippet to test the problem:

julia> using BenchmarkTools
julia> using FixedPointNumbers
julia> import Base.convert
julia> import Base.promote_rule
julia> convert(::Type{TF}, x::Fixed{T2,f2}) where {TF <: Fixed{T1,f1},T2, f2} where {T1, f1} = Fixed{T1, f1}(x.i>>(f2-f1), 0)

julia> promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed,f1, f2} = Fixed{T,f1>f2?f1:f2}
julia> function benchmark(x,y)
           z = x
           for i = 1:1000
               z += i + x+y
           end
           z
       end
julia> a1 = convert(Fixed{Int64, 12}, 1.0)
julia> b1 = convert(Fixed{Int64, 20}, 2.0)
julia> a2 = 1.0
julia> b2 = 2.0
julia> @btime benchmark(a1,b1)
  4.627 ms (30029 allocations: 1.31 MiB)
503501.0Q43f20

julia> @btime benchmark(a2,b2)
  1.313 μs (1 allocation: 16 bytes)
503501.0

#2

This might be a use case for the Base.@pure macro:

Base.@pure Base.promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed, f1, f2} = Fixed{T,f1>f2 ? f1 : f2}

makes e.g. promote_type(Fixed{Int,12}, Fixed{Int,20}) type stable.


#3

Either that or something like the following (from stdlib Broadcast):


#4

The Jutho’s solution works great - finally fixed-point is beating the floating-point.
I’ve identified also an instability in my benchmark function, corrected version is here:

function benchmark(x,y)
    z = convert(promote_type(typeof(x), typeof(y)), 1)
    for i = 1:1000
        z += i + x + y
     end
     z
end

Thank you very much for the help.


#5

Thank you for the response. I’m sorry I don’t understand the direction you are pointing me. How can I use the _max() function in the case of the promote_rule definition? Could you elaborate it in a little bit more detail?
Thank you very much for your time - these where clauses are quite difficult for me to understand - similar to C++ templates:) Is there any blog that dives into the details what operations are allowed in the where clauses?


#6

For my reference, discussion on Base.@pure black magick:
https://discourse.julialang.org/t/pure-macro/3871


#7

Sorry, the point I was trying to make is that you could use this _max function to construct your promote_rule method without using @pure. On 0.6.2:

using Compat, FixedPointNumbers

# _max from Broadcast:
_max(V1::Val{Any}, V2::Val{Any}) = Val(Any)
_max(V1::Val{Any}, V2::Val{N}) where N = Val(Any)
_max(V1::Val{N}, V2::Val{Any}) where N = Val(Any)
_max(V1::Val, V2::Val) = __max(longest(ntuple(identity, V1), ntuple(identity, V2)))
__max(::NTuple{N,Bool}) where N = Val(N)
longest(t1::Tuple, t2::Tuple) = (true, longest(Base.tail(t1), Base.tail(t2))...)
longest(::Tuple{}, t2::Tuple) = (true, longest((), Base.tail(t2))...)
longest(t1::Tuple, ::Tuple{}) = (true, longest(Base.tail(t1), ())...)
longest(::Tuple{}, ::Tuple{}) = ()

# promote_rule using _max (note the lack of @pure):
Base.promote_rule(::Type{Fixed{T,f1}}, ::Type{Fixed{T,f2}}) where {T<:Signed, f1, f2} =
    Fixed{T, _max(Val(f1), Val(f2))}

This lifts the computation into the type system, so that the promote_rule infers correctly, this time without @pure:

julia> @code_warntype promote_rule(Fixed{Int, 3}, Fixed{Int, 4})
Variables:
  #self# <optimized out>
  #unused#@_2 <optimized out>
  #unused#@_3 <optimized out>

Body:
  begin 
      return FixedPointNumbers.Fixed{Int64,Val{4}()}
  end::Type{FixedPointNumbers.Fixed{Int64,Val{4}()}}

However, there are limits on how far you can take this:

julia> @code_warntype promote_rule(Fixed{Int, 3}, Fixed{Int, 15})
Variables:
  #self# <optimized out>
  #unused#@_2 <optimized out>
  #unused#@_3 <optimized out>

Body:
  begin 
      return (Core.apply_type)(Main.Fixed, $(Expr(:static_parameter, 1)), (Main.__max)((Core._apply)(Core.tuple, (true,), (Main.longest)((Core.tuple)(2, 3)::Tuple{Int64,Int64}, $(Expr(:invoke, MethodInstance for argtail(::Int64, ::Int64, ::Vararg{Int64,N} where N), :(Base.argtail), 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)))::Tuple{Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Vararg{Any,N} where N})::Tuple{Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Bool,Vararg{Any,N} where N})::Val{_} where _)::Type{FixedPointNumbers.Fixed{Int64,_}} where _
  end::Type{FixedPointNumbers.Fixed{Int64,_}} where _

I was mainly trying to point out that this kind of thing is possible, not that it’s the best solution in this case. In any case, don’t use Broadcast._max directly, as it’s an implementation detail that may be changed without warning in a later version.

Edit (man I edit my posts a lot): realized that the result should be of the form Fixed{Int, 4}, not Fixed{Int, Val(4)}, but the idea remains the same.