Re: Let's gather some evidence!
Hi John & P1788,
My rationale for voting No was indeed focused on efficiency, but it's probably
not the main point.
It actually depends on what we get in return of the additional computations.
I would be ready to accept a price depending on the features we get back, and
the main problem is that we don't get much out of NaI(s), and there are even
arguments against it in principle.
More precisely, I never needed NaI for the simple forward-error propagations I do
with IA, and it appears from the discussions that others, more experts in the
area, do not agree on the general usefulness of NaI. So it means that if
it has any non-zero efficiency cost at all, we really need to make sure its
usages are worth it. If the useful cases are too rare, we can always say
that those special cases need to handle the issue some other way, and the
default should ignore it and go full speed.
The argument against NaI in principle is that it adds a cost in terms of the
complexity of the specification. Suddenly it introduces special cases everywhere.
Look at floating-point : it is complex to use (you need to read Goldberg),
because of special cases and rounding issues. With IA, we have a chance
to define a model of computation with approximations of reals which is
greatly simpler, and it should be a selling point.
Somehow, the empty set is in the same boat : not everybody needs it ! So why
should we support it in the standard ? Well, it has the advantages that
introducing it actually *simplifies* the specifications by closing the model
under some operations, and it can be implemented at basically zero-cost
with (NaN, NaN).
John Pryce a écrit :
Sylvain and P1788
On 8 Sep 2009, at 09:59, Sylvain Pion wrote:
Introducing NaI(s) has a cost in the implementation of
basic operations (+, *) due to the propagation rules.
I can see how to propagate the empty set at zero cost
(if implemented as (NaN, NaN)), but I fail to see how
to generalize it for NaI : neither with NaN payloads
(how do you combine them?), nor with a non-NaN as second
member (needs fixups for e.g. the unary minus operator).
I think it is very important that the IA standard be
efficiently implementable with current hardware,
because it is through software implementations that it
has a chance of being adopted first, to later have a chance
of seeing hardware support appear. So I would need a much
stronger rationale to support NaI(s) at this stage.
The alternatives mentioned for reporting "errors" appear
to be enough for me now (variants of the functions
returning more information besides an interval, "flags"...).
These are important considerations now we are getting closer to level 3
issues of choosing representations for special values like Empty and
NaI. But I'ld like your view on these points:
- With current hardware, how do you envisage "flags" being implemented
efficiently?
I think IEEE1788 should not say more about a "domain error" flag for example,
than what IEEE754 says about its inexact/underflow/... flags.
IMO, those flags should not be part of the specification of the binary
representation of intervals, just like they are not part of the representation
for floating-point. They are too rarely useful, and should be zero-cost
if you don't need them.
In terms of concrete implementation, when you need the information, one can
imagine decorated/encapsulated intervals as mentioned, or maybe re-using
one of the IEEE754 flags, I don't know. Dedicated hardware can of course
do better. IMO, it's not really the business of our specification.
In terms of specification, why don't we simply try to be consistent
with the way IEEE754 defines its flags ? (I'm not familiar with all
the details of it)
- How do you envisage "returning more information besides an interval"
being implemented? If it is by the mechanism of an extra output
argument, so c = a + b becomes c = plus(a,b,flag) as I believe is the
scheme in the draft C++ interval standard, how should one remedy the
huge inconvenience to the user, who has to rewrite existing function code?
If you want convenience, you can wrap the type, as has been suggested.
IMO, this is a higher-level issue with programming languages, and IEEE1788
should try to be agnostic about it.
- I reported to P1788 on 13 October 2008, results of performance
comparisons in C++ of BIAS in various versions. Actually just the lowest
level Bias0.c (scalar operations, not vector). One was equivalent to the
official distribution, with neither Empty nor NaI. The other had both
Empty and NaI (and actually implemented csets, which one would expect to
slow it down further).
Running a serious benchmark test with Nedialkov's VNODE-LP interval ODE
code, taking about 150 seconds on my 2.33 GHz Intel Mac. Result: the
overhead of the more complicated version was less than 6 percent.
Defects of my comparison:
* It's on only one platform.
* No Empty's or NaI's were actually created, because VNODE-LP
uses a "classical" interval model.
* No vector-optimised operations were used. Even in the linear
algebra, VNODE-LP calls the Bias0 scalar arithmetic operations.
Your benchmark was fine and conclusive enough, I think.
It showed there is a little price. The question is whether it's worth it,
if we want NaI(s) at all.
Moreover, on the more "philosophical" ground, I think the
reasons for introducing NaNs in FP do not hold for IA,
as the IA system is more naturally closed. Introducing
a cost in all interval operations mostly to handle cases
coming from FP->IA conversions seems like a wrong trade-off
to me.
"IA system is more naturally closed" is fair enough. Against this, the
requirement for correctness in IA is _much_ greater. We claim to write
code that gives mathematically proven enclosures.
It's not clear to me that introducing NaI(s) will make our system "more correct".
Correctness only means that you use the system according to its specification.
Therefore a way to improve on that front is also to simplify the model, so as
to reduce the chances that users get it wrong. The simpler the specs, the
better. Removing NaI(s) simplifies the big picture of what is an interval.
In terms of automatic formal prooving techniques, I guess that it's also
much better to avoid such special cases. And IA is used there a lot.
FP->IA conversions _will_ occur. If we don't have NaI, what? The
possible choices of return Empty, return Entire, throw exception, etc.,
were discussed at length in the C++ interval forum, and all were found
deficient.
In terms of IEEE754/IEEE1788 relation, maybe we could raise IEEE754's inexact
flag (or another IEEE754 flag) in case the FP value is not finite ?
Together with returning Empty or Entire, this seems good enough to me:
we provide a way to detect the mistake, fitting in the existing framework,
and at zero-cost when you know you won't have any such issue.
The good thing with the "flag" model, as defined in IEEE754, is that you
can imagine that you do parallel FP->IA conversions, and you get to test
only one flag in the end, which tells if one of the conversions was bad.
The IEEE754 flags are global enough that they allow to take several operations
into account using some stickiness, but they are not global to the point
of raising thread-safety issues (that's my rough mental model of them,
that's the reality of hardware implementations, and hopefully I'm not
too wrong).
I think it really is time to have some objective evidence of the
performance consequences of various choices on current platforms. Here
are some hypotheses that may be worth testing:
H1. On some important platforms, the presence of code for NaI seriously
affects speed even when no NaIs are generated.
H2. Same, but when a significant number of NaIs are generated and then
propagated through a computation.
H3. H2 may not be true for purely scalar computations, but is true when
using interval elementary functions that have been vector-optimised.
Who will take up the challenge? Sylvain, I guess you have the ability to
provide such evidence, I am sure your C++ proficiency is many times
mine. One could use (variations on) BIAS, or Filib++, etc. I suggest
some basic linear algebra would be an appropriate benchmark.
I hope my explanations above motivate the reasons why I don't feel like
doing this.
--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/