Type unstability in make_interval

[lbenet]

I just became across an issue that suggests that there is somewhere/somehow type instability in ValidatedNumerics.jl. The following example illustrates the problem:

julia> f(x) = 1+x
f (generic function with 1 method)

julia> @code_warntype f(Interval(1.0))
Variables:
  x::ValidatedNumerics.Interval{Float64}

Body:
  begin  # none, line 1:
      GenSym(2) = (ValidatedNumerics.make_interval)(Float64,1)::Any
      GenSym(1) = call(ValidatedNumerics.Float64,(top(getfield))(x::ValidatedNumerics.Interval{Float64},:lo)::Float64,ValidatedNumerics.RoundDown)::Float64
      GenSym(0) = call(ValidatedNumerics.Float64,(top(getfield))(x::ValidatedNumerics.Interval{Float64},:hi)::Float64,ValidatedNumerics.RoundUp)::Float64
      return GenSym(2) + call(ValidatedNumerics.Interval{Float64},GenSym(1),GenSym(0))::ValidatedNumerics.Interval{Float64}::Any
  end::Any

Note the Anys appearing in GenSym(2), that suggest looking at make_interval(), and going further, I think that split_interval_string() may be responsible.

Using, f(x)=x, or exp(x), is type stable.

[dpsanders]

But it finds the correct type in the end for x, so I don't think there's a real type instability.
Apparently it's known that this can happen.

[lbenet]

I'm not sure I understand what you mean; according to the output, f(x) is Any, instead of being Interval, which is what matters for the compiler. I think the desired outcome mimics what is obtained for x being a Float64, which is a Float64. For the application where I found this behavior, it does induce a performance penalty.

I'll try to push later what I've done so far; at least for this case, it solves the problem.

[dpsanders]

I can see that split_interval_string could be type unstable, you're right.
But it seems to get the type right for f:

julia> f(Interval(1.0))
[2.0, 2.0]

julia> typeof(ans)
ValidatedNumerics.Interval{Float64}

Or what am I missing?

[lbenet]

Ok, but this is not what the compiler gets. (The issue is like the problem to pass functions as arguments of functions: as I understand it, your function may be ok, but the compiler doesn't know it.)

What we should aim is to get something like

@code_warntype f(1.0)
Variables:
  #self#::#f
  x::Float64

Body:
  begin  # none, line 1:
      return (Base.box)(Base.Float64,(Base.add_float)((Base.box)(Float64,(Base.sitofp)(Float64,1)),x::Float64))
  end::Float64

That is, the compiler knows it will get a Float64 from a Float64

[dpsanders]

Yes you're right. What is not clear to me is why that's happening for f(x) with x an Interval.

[lbenet]

I think the problem is related to the use of macros and changes in the rounding modes. At least this is the common thing of the cases I've isolated; see #92.

This things do have a performance penalty, which I is improved, but not totally away.

[dpsanders]

Could you add some performance-related tests or notebooks in a new perf directory with some of these comparisons please?

[lbenet]

I'll add the kind of things I've tested, but I don't quite know how to make a nice comparison of the performance of the same module. workspace() sometimes pollutes too much the name-space.

[lbenet]

EDIT: I guess I will have to correct something; while the tests things work on v0.4, something (related to ^, which I touched) is creating problems in v0.5...

[lbenet]

I'm not quite sure why, but with the current master, this issue is not appearing in julia v0.5:

julia> VERSION
v"0.5.0-dev+3040"
julia> f(x) = 1+x
f (generic function with 1 method)
julia> @code_warntype f(Interval(1.0))
Variables:
  #self#::#f
  x::ValidatedNumerics.Interval{Float64}

Body:
  begin  # none, line 1:
      return (top(_apply))(Base.+,(Base.promote)(1,x::ValidatedNumerics.Interval{Float64})::Tuple{ValidatedNumerics.Interval{Float64},ValidatedNumerics.Interval{Float64}})::ValidatedNumerics.Interval{Float64}
  end::ValidatedNumerics.Interval{Float64}

Also, comparing this (julia v0.5) case with the first example quoted (julia v0.4), the number of intermediate generated variables is larger in v0.4, which is reflected in the allocation when f(Interval(1.0)) is timed:

• Version 0.4.4: 0.000041 seconds (41 allocations: 1.156 KB)
• Version 0.5 : 0.000029 seconds (21 allocations: 624 bytes)

Maybe all this is solved by JuliaLang/julia#13412

[dpsanders]

OK, that's good to know! Yes, issue 13412 seems to have solved a lot of problems!

The slow tests on 0.5 is a problem. I reported it as an issue but there doesn't seem to be any progress yet.

[lbenet]

One place where our tests hang for a long time is around "minimal_pow" tests...

[dpsanders]

Yes, the problem is that there is a very large number of tests in that set, and the time scales very badly with the number of tests for some reason: JuliaLang/julia#15346

[dpsanders]

That problem was introduced by JuliaLang/julia#13412 !

[dpsanders]

I think you are right that the root source of the type instability was passing functions to functions. However, this is fixed in 0.5 by JuliaLang/julia#13412, and I do not think that we should rewrite everything to avoid doing this.

(Unfortunately, that change also introduced the problem that the long test suites are extremely slow.)

[dpsanders]

Closing for now. Feel free to reopen if you think it's necessary.