Comments (44)
Thinking about it, I think convert(Interval{Float64}, x::Float64)
also needs to be fast, e.g. for
julia> x = 1..2
[1, 2]
julia> x * 0.3
Here, 0.3
gets convert
ed to the type of x
in the promotion.
from intervalarithmetic.jl.
However, we still want some way of making the smallest interval around 0.3.
This is currently @interval(0.3)
; however, that uses convert(Interval, 0.3)
internally.
from intervalarithmetic.jl.
Thanks to bring this up again; perfect timing!
The idea of this comment is to exploit dispatch rather than conversion. I think that such an approach may be better and "more julian".
Just to recall it, we should have two types, one which is "safe" (in the sense of checks and correct rounding), and the other that is "fast". Both should be subtypes of AbstractInterval{T}
. Naming such types could be Interval
or SafeInterval
, and FastInterval
or UnsafeInterval
, or whatever you prefer. In terms of constructors, I think we would essentially need one internal constructor for SafeInterval
which checks the correct order of the bounds, and could also handle rounding.
From what you propose above, I think I like the idea of using different short-forms for each type, for example, a..b
could build a FastInterval
.
from intervalarithmetic.jl.
Refactor of ..
in PR #37
from intervalarithmetic.jl.
I'm playing with the idea above, or having a fast constructor for intervals (FastInterval
). Do you have some benchmark case?
from intervalarithmetic.jl.
On master:
julia> using BenchmarkTools
julia> @btime Interval(1, 2)
7.994 ns (0 allocations: 0 bytes)
On simplify_constructor
branch:
julia> @btime Interval(1, 2) # without checks
1.393 ns (0 allocations: 0 bytes)
julia> @btime interval(1, 2) # with checks
8.908 ns (0 allocations: 0 bytes)
We should actually make a proper benchmark suite.
from intervalarithmetic.jl.
(Edited above to add interval
)
from intervalarithmetic.jl.
Note that any benchmark that includes arithmetic will currently be dominated by those arithmetic operations, since they are currently really slow! That is what the fast_rounding
branch solves (which is included in simplify_constructor
, possibly unfortunately).
from intervalarithmetic.jl.
Having said that, it is no longer clear to me that removing the checks from the constructor really has that much influence on the overall time for a real calculation, which will indeed be dominated by other costs.
from intervalarithmetic.jl.
For example,
julia> f1(N) = sum(Interval(1) / (i^2) for i in 1:N)
f1 (generic function with 1 method)
julia> f2(N) = sum(interval(1) / (i^2) for i in 1:N)
f2 (generic function with 1 method)
julia> f1(10)
[1.54976, 1.54977]
julia> f2(10)
[1.54976, 1.54977]
julia> @btime f1(100)
3.627 μs (3 allocations: 96 bytes)
[1.63498, 1.63499]
julia> @btime f2(100)
4.399 μs (3 allocations: 96 bytes)
[1.63498, 1.63499]
There is a 20% increase in time due to the extra checks in the constructor.
(Note that the constructor is called, for example, to create the result of the division.)
from intervalarithmetic.jl.
This is what I get:
julia> @btime Interval(pi, 7pi)
11.307 ns (0 allocations: 0 bytes)
[3.14159, 21.9912]
julia> @btime @interval(pi, 7pi)
1.122 μs (7 allocations: 192 bytes)
[3.14159, 21.9912]
julia> @btime FastInterval(pi, 7pi)
8.488 ns (0 allocations: 0 bytes)
IntervalArithmetic.FastInterval{Float64}(3.141592653589793, 21.991148575128552)
FastInterval
does not check the proper bounds of the interval, so it is the simplest possible constructor, Interval
does check the bounds but performs no rounding, and @interval
does both. This is consistent with your last remark, that checking the bounds does influence the timing, but not too crucially, while the rounding business is what costs allocations and time.
Let me advance further and then I push it to GitHub.
from intervalarithmetic.jl.
Among others, I still have to adapt the arithmetic definitions...
from intervalarithmetic.jl.
There is some time being spent in 7*pi
. Try with just numbers.
The fact that you have to adapt the arithmetic definitions is one reason why this doesn't seem to me to be an attractive direction to take!
from intervalarithmetic.jl.
The pi
and 7*pi
was on purpose. The following is another example:
julia> @btime Interval(1, 2)
11.307 ns (0 allocations: 0 bytes)
[1, 2]
julia> @btime FastInterval(1, 2)
8.487 ns (0 allocations: 0 bytes)
IntervalArithmetic.FastInterval{Float64}(1.0, 2.0)
julia> @btime @interval(1, 2)
756.105 ns (5 allocations: 128 bytes)
[1, 2]
from intervalarithmetic.jl.
Regarding adapting the operations, the idea is to exploit that both Interval
and FastInterval
are subtypes of AbstractInterval
.
from intervalarithmetic.jl.
Not related to FastInterval
, but still interesting:
julia> @btime convert(Interval{Float64}, 0.1)
303.565 ns (3 allocations: 128 bytes)
[0.0999999, 0.100001]
julia> @btime @interval 0.1
675.000 ns (5 allocations: 192 bytes)
[0.0999999, 0.100001]
from intervalarithmetic.jl.
Yes, that is interesting -- it seems to be due to this:
julia> @macroexpand @interval 0.1
:((IntervalArithmetic.Interval)((IntervalArithmetic.convert)((IntervalArithmetic.Interval){IntervalArithmetic.parameters.precision_type}, 0.1)))
i.e. it must do a dynamic dispatch (i.e. at runtime) to convert
to the correct type.
from intervalarithmetic.jl.
Note the following (with simplify_constructor
), that seems to be due to instruction pipelining:
julia> using AdjacentFloats
julia> @btime Interval(prev_float(1.0), next_float(2.0))
1.386 ns (0 allocations: 0 bytes)
[0.999999, 2.00001]
from intervalarithmetic.jl.
I just pushed the fastinterval
branch, where the idea of having Interval
or FastInterval
is basically implemented. I didn't implement any tests yet. Both (as well as DecoratedInterval
) are subtypes of AbstractInterval
, which is used whenever possible to extend the methods.
Here are some benchmarks using Julia v0.6.0-rc2, as we outlined above:
julia> using IntervalArithmetic, BenchmarkTools
julia> @btime Interval(1, 2)
11.307 ns (0 allocations: 0 bytes)
[1, 2]
julia> @btime FastInterval(1, 2) # no checks
8.173 ns (0 allocations: 0 bytes)
IntervalArithmetic.FastInterval{Float64}(1.0, 2.0)
julia> f1(N) = sum(Interval(1) / (i^2) for i in 1:N)
f1 (generic function with 1 method)
julia> f2(N) = sum(FastInterval(1) / (i^2) for i in 1:N)
f2 (generic function with 1 method)
julia> setformat(:full)
6
julia> f1(10)
Interval(1.5497677311665397, 1.549767731166541)
julia> f2(10)
IntervalArithmetic.FastInterval{Float64}(1.5497677311665408, 1.5497677311665408)
julia> @btime f1(100) # uses Interval; slow
17.795 μs (3 allocations: 96 bytes)
Interval(1.634983900184882, 1.6349839001849027)
julia> @btime f2(100) # uses FastInterval
2.876 μs (3 allocations: 96 bytes)
IntervalArithmetic.FastInterval{Float64}(1.6349839001848923, 1.6349839001848923)
from intervalarithmetic.jl.
I was just about to write that I didn't understand why FastInterval
was so much faster, but it is not doing any rounding?
from intervalarithmetic.jl.
The amazing thing about the fastrounding branch is that doing correct rounding is almost as fast as no rounding at all. There is one bug left to fix before it is ready.
from intervalarithmetic.jl.
You are right, it is doing no rounding. The subtlety is related to @round
that returns an Interval
. I'll try to implement it in such a way that it rounds correctly.
from intervalarithmetic.jl.
You could change @round
so that it just returns the tuple of rounded values, and then wrap that in the correct type inside each function. Painful... I really don't think that this is the right way to go.
from intervalarithmetic.jl.
I thought that changing @round(expr1, expr2)
to @round(T, expr1, expr2)
, with T
being either Interval
or FastInterval
would work, but I am having problems...
from intervalarithmetic.jl.
I rewrote @round
to get rid of putting explicit types in...
from intervalarithmetic.jl.
I don't like my solution to include rounding, but it's up there. Currently, I get the following
julia> using IntervalArithmetic, BenchmarkTools
julia> @btime Interval(1, 2)
11.307 ns (0 allocations: 0 bytes)
[1, 2]
julia> @btime FastInterval(1, 2)
8.173 ns (0 allocations: 0 bytes)
IntervalArithmetic.FastInterval{Float64}(1.0, 2.0)
julia> f1(N) = sum(Interval(1) / (i^2) for i in 1:N)
f1 (generic function with 1 method)
julia> f2(N) = sum(FastInterval(1) / (i^2) for i in 1:N)
f2 (generic function with 1 method)
julia> setformat(:full)
6
julia> f1(10), f2(10)
(Interval(1.5497677311665397, 1.549767731166541), IntervalArithmetic.FastInterval{Float64}(1.5497677311665397, 1.549767731166541))
julia> @btime f1(100) # uses Interval; slow
17.632 μs (3 allocations: 96 bytes)
Interval(1.634983900184882, 1.6349839001849027)
julia> @btime f2(100) # uses FastInterval
16.094 μs (3 allocations: 96 bytes)
IntervalArithmetic.FastInterval{Float64}(1.634983900184882, 1.6349839001849027)
From this, it seems to me that the whole issue is not so much to check the bounds, but to round faster. And currently we don't do it.
from intervalarithmetic.jl.
Yes, I completely agree -- this is all pointless with the current slooow rounding.
That's why it's urgent to get the fastrounding
branch ready!
(Actually that branch is not the problem; there are two remaining bugs to fix in the packages that it will depend on.)
from intervalarithmetic.jl.
I partially agree with you: I think there are two points here:
- Are the checks (in
Interval
) relevant? (The point of this issue.) The answer is "not quite" - Make an efficient rounding scheme (independent of checking or not the end-points).
I'll take a look on #25.
from intervalarithmetic.jl.
I'm not sure what you mean by "not quite". (Or by "revelant".)
from intervalarithmetic.jl.
What I mean by "not quite" is that using Interval
(that checks the correctness of the bounds and rounds) and FastInterval
(that does not check the bounds but rounds) yields timings that differ in ~10%. On the other hand, the differences of the naive benchmarks when FastInterval
includes rounding and when it doesn't yields a factor 8x in speed-up.
from intervalarithmetic.jl.
You can try mixing your branch and fast_rounding
. Something like
git checkout fast_rounding
git checkout -b fast_rounding_fast_interval
git merge fast_interval
from intervalarithmetic.jl.
While I managed to merge both branches (only needed to correct two conflicts) I am having problems with FastRounding (actually on Nemo)...
from intervalarithmetic.jl.
I'm not sure what you mean by "on nemo". I guess youve done Pkg.add("FastRounding")?
from intervalarithmetic.jl.
I'm not sure what was I doing wrong...
Anyway, here are the new benchmarks:
julia> using IntervalArithmetic, BenchmarkTools
julia> setrounding(Interval, :errorfree)
julia> @btime Interval(1, 2)
10.992 ns (0 allocations: 0 bytes)
[1, 2]
julia> @btime FastInterval(1, 2)
8.173 ns (0 allocations: 0 bytes)
IntervalArithmetic.FastInterval{Float64}(1.0, 2.0)
julia> f1(N) = sum(Interval(1) / (i^2) for i in 1:N)
f1 (generic function with 1 method)
julia> f2(N) = sum(FastInterval(1) / (i^2) for i in 1:N)
f2 (generic function with 1 method)
julia> setformat(:full)
6
julia> f1(10), f2(10)
(Interval(1.5497677311665397, 1.549767731166541), IntervalArithmetic.FastInterval{Float64}(1.5497677311665397, 1.549767731166541))
julia> @btime f1(100)
8.307 μs (3 allocations: 96 bytes)
Interval(1.634983900184882, 1.6349839001849027)
julia> @btime f2(100)
5.963 μs (3 allocations: 96 bytes)
IntervalArithmetic.FastInterval{Float64}(1.634983900184882, 1.6349839001849027)
So, f1
is 2.1x faster, and f2
is 2.7x faster. Pretty impressive.
All our tests pass; ITF1788 tests also pass, except for two tests related with cancelPlus
and cancelMinus
. I'll check this (and push to github the fast_rounding_fastinterval
branch.
from intervalarithmetic.jl.
That's a bit disappointing -- I was expecting a better speedup.
Those two tests are from a (very) subtle bug that is on my radar: JeffreySarnoff/FastRounding.jl#11
from intervalarithmetic.jl.
Although the code for cancelplus
and cancelminus
seems to be surprisingly complicated.
(And I still don't really understand the need for those two functions, to be honest.)
from intervalarithmetic.jl.
These function provide something like the inverse for addition and subtraction; I included them because they are in the standard. The complicated programing was the way I found to get the tests passing...
from intervalarithmetic.jl.
I just pushed another commit where cancelminus
is rewritten. This current version does not plays with the precision, and seems to work for both setrounding(Interval, :correct)
and setrounding(Interval, :errorfree)
. All tests should pass.
from intervalarithmetic.jl.
I can make a new PR with the sole correction of cancelminus
, which I think is worth to have in master.
from intervalarithmetic.jl.
That would be great, yes! And cancelplus
is in terms of cancelminus
?
from intervalarithmetic.jl.
Yes: cancelplus(a,b) = cancelminus(a,-b)
.
I will prepare a separate PR to handle this.
from intervalarithmetic.jl.
Is there anything left to do here @lbenet ?
from intervalarithmetic.jl.
I must admit that I completely forgot about this discussion. I think the discussion is quite outdated and a lot has changed since we were talking about this: For instance, we have now atomic
, and convert
behaves quite differently.
Maybe your question was related to cancelminus
and cancelplus
. If so, I can look up again into the fastinterval
branch and try to rescue the relevant PRs related to those functions.
from intervalarithmetic.jl.
The current behaviour is now roughly what was sketched at the start of the thread and is documented in the docs.
from intervalarithmetic.jl.
Related Issues (20)
- Clarification on 'NG' Decoration HOT 2
- Warning seriously (using Logging.jl and with user settings)
- Don't display `NG` when `decorations = false` HOT 1
- ForwardDiff with min, max, and clamp HOT 3
- `string(x::Interval)` is not working correctly HOT 1
- Unclear error for malformed interval
- Can't multiply a `BareInterval` by a scalar HOT 5
- Document `in` behaviour HOT 2
- Define ` ∩` and `∪` for `BareInterval` HOT 6
- Define and export Heaviside function HOT 2
- No mechanism to define functions restricted to a domain HOT 2
- Piecewise functions HOT 5
- Add `\infty` symbol to Symbols module HOT 1
- `zero(emptyinterval())` should be empty HOT 1
- Expose domain of functions HOT 5
- `hull` with `NaI` gives non-NaI HOT 1
- Reinstate fast rounding with `prevfloat` and `nextfloat` HOT 2
- Give a hand to downstream packages to update to v0.22
- Define `x // 3` for an interval `x` HOT 2
- Document the decoration and flag system HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from intervalarithmetic.jl.