[std-interval] Re: Std-interval Digest, Vol 3, Issue 1

[first.i.last at comcast.net]

 -------------- Original message ----------------------
From: std-interval-request at compgeom.poly.edu
> Send Std-interval mailing list submissions to
> 	std-interval at compgeom.poly.edu
----------------------------------------------------------------------
> 
> Message: 1
> Date: Mon, 03 Apr 2006 20:13:45 -0500
> From: George Corliss <George.Corliss at marquette.edu>
> Subject: [std-interval] C++ interval std
> To: <std-interval at compgeom.poly.edu>
> Message-ID: <C0573279.37DC%George.Corliss at Marquette.edu>
> Content-Type: text/plain;	charset="US-ASCII"
> 

[snip]

> Lawrence feels strongly that the standard should be to pass by
> value.  Intervals are small data structures;

That perspective causes problems, just as it did for complex.  Intervals should be considered atomic types whose internal structure is opaque.  We don't consider fp types as structures even though they consist of three distinct fields (and in fact are treated as separate fields in software implementations of the run-time library).

> by value allows them
> to be passed in registers for speed.  That is how the current Sun
> C++ compiler works.  There is no reason to follow the C++ complex
> standard.  The library is often taken as an example by coders, and
> there is no good reason to follow the tradition of C from 20 years
> ago that structures should be passed by reference.

There may or may not be a good reason for it.  On FPUs with weak connections to the CPU, such as x87, passing by value is strongly preferred.  Yet on FPUs with strong connections to the main CPU passing by reference might be much more efficient.

If the standard syntax is pass by value then a compiler that prefered pass by reference would be free to do so internally (assuming appropriate referential safe guards).

> Uninitialized.  The convention in C/C++ is to initialize to zero,

Not quite.  The default initialization convention in C depends on the lifetime of the object.  Dynamic objects (typically stack and heap) are not initialized at all by default.  Static objects are initialized to zero, but that is not a special property of numerics.  All static objects lacking an initialization expression get a default expression of zero.

Intervals should work the same way.  Anything with an init expression gets it.  Anything without one gets default initialized.  Statics get zero and dynamics don't get touched (c.f. core constants).  Only the latter is a concern, and then only during development/debug.

Typical C programmer rant:  If I _wanted_ it initialized I would have done it _myself_ -- don't slow me down without my permission.

On platforms with NaN support uninitialized FP objects that will be initialized without the programmer's explicit permission should get a characteristic NaN.  On platforms without NaN support they should get HUGE_VAL because that is the standard diagnostic value.

So the default constructor should either use NaN, which would then be an empty interval or HUGE_VAL, which would match the existing standard for "something to think about here".

> but we agree that is not correct for intervals.  Whole is probably
> the best we can do.

Yuck.  Empty is clearly superior to whole in that it has less chance of accidentally producing apparently sensible results.  And for production an uninitialized interval should not be initialized.  After all,  C++ lacks basis support for array initialization so any default initialization effort, like touching every value in a big array, is just wasted time.

>  Aside: The next day, we visited Berkeley and
> talked with Jim Demmel and Bill Kahan.  Among other things, Kahan
> wants user-defined data types to be tagged.  If we have the
> Kahan-suggested tag, we can tag intervals as Uninitialized.

How will uninit tags be handled when they meet other values?  Will they have precedence as NaNs do?  If so then external tags are unnecessarily duplicative of internal values such as a characteristic NaN.

> 
> The 1999 C standard provides for access to IEEE hardware.  The
> next version of the C++ standard will also address features new
> in the 1999 C standard to be included in C++.
> 
> The current C++ standard does not discuss or acknowledge threads.
> They are working on the next revision of the standard, which will
> have something to say about threads in the language proper and in
> the standard library.  Probably the interval standard should say,
> "Intervals will be implemented in a thread-safe manner."

That is a tall order.  Intervals should be thread safe when the underlying language is thread-safe.  Consider errno and matherr() for intervals.

> IEEE 754R is nearly over.  It is likely to include
>    Decimal formats for floating point
>        (Should C++ IA standard permit decimal intervals?)

Of course.  For every floating point type we need a corresponding interval type.  The radix is irrelevant.

>    Quad precision
>        (Should C++ IA standard quad intervals?)

Of course.  For every floating point type we need a corresponding interval type.  The mantissa width is irrelevant.

>    Fused Multiply and Add
>        (I assume with directed rounding?
>         Great for interval linear algebra, too)
>    min/max
>        (I wonder how they handle NaN, infinity, etc.)

In the proposal only NaNs are special.  In min() NaNs are greater than all numbers. In max() NaNs are lesser than all numbers.

>    expression evaluation
>        (Don't remember what that means)

Mainly control over the width or temporaries used during calculation (implict promotion to double or extended double causes problems such as multiple rounding and can be orders of magnitude slower if the wider types are not supported in hardware).

This is a complex area.  There are other aspects under consideration such as programmer control of order of evaluation and programmer permission for various optimization transforms.

_____________________________________________
> > Std-interval mailing list
> > Std-interval at compgeom.poly.edu
> > http://compgeom.poly.edu/mailman/listinfo/std-interval
> 
> ------------------------------
> Message: 3
> Date: Tue, 04 Apr 2006 11:11:58 +0200
> From: Sylvain Pion <Sylvain.Pion at sophia.inria.fr>
> Subject: Re: [std-interval] C++ interval std
> To: For discussions concerning the C++ standardization of intervals
> 	<std-interval at compgeom.poly.edu>
> Message-ID: <4432385E.4050805 at sophia.inria.fr>
> Content-Type: text/plain; charset=ISO-8859-1; format=flowed

> George Corliss wrote:
> > Lawrence feels strongly that the standard should be to pass by value.  Intervals are small data structures; by value allows them to be passed in registers for speed.  That is how the current Sun C++ compiler works.  There is no reason to follow the C++ complex standard.  The library is often taken as an example by coders, and there is no good reason to follow the tradition of C from 20 years ago that structures should be passed by reference.
 
> I don't have any strong opinion on this. I only did a very local experiment on some code of mine on x86, and changing to pass-by-value slowed the code down a bit.

Some compilers give the programmer little control over parameter passing.  Others give a great deal of control, including offering both stack and register passing for atomic types, putting small structs in registers, and even hybrids with part in registers and part on the stack.

This matters because the implementor _must_ have the freedom to optimize parameter passing.  So the standard should be as quiet as possible on the issue.  The _syntax_ should be by-value because that imposes the least (i.e., no actual) constraints.  But the code generated could be either at the discretion of the implementor.

The best approach is probably a second set of types that are specifically used for argument passing.  Portable code often uses this approach.  It allows an implementor to alter the parameter passing convention on a platform-by-platform basis.

So non-inline interval functions would take arguments of type IntervalArg<double> from which the function could obtain the actual argument.

> > Uninitialized.  The convention in C/C++ is to initialize to zero,
> > but we agree that is not correct for intervals.  Whole is probably
> > the best we can do.
> 
> I'm not convinced.  Initilization to [0,0] seems nice to me for
> intervals because of homogeneity reasons with floating-point.

But it's not homogeneous except in the case of static variables.  The default constructor simply needs an _isBSS() predicate or something similar to determine whether to initialize the value to binary zero, which might or might not be tge numeric value [0,0], or to leave the value uninitialized.

> I could even imagine that the empty interval would make as much sense as whole.

More IMHO.

>  >  Aside: The next day, we visited Berkeley and
> > talked with Jim Demmel and Bill Kahan.  Among other things, Kahan
> > wants user-defined data types to be tagged.  If we have the
> > Kahan-suggested tag, we can tag intervals as Uninitialized.
> 
> Could you elaborate on this tag ?  What would it do ?
> Would this be a run-time feature of the objects telling if
> they are initialized or not ?  Can't this be left to some
> "debug mode" ?

The concept includes things like the openness of the ends of the intervals and the possiblity of including dependency info (or links) to enable run-time narrowing of exaggerated interval widths caused by inconsistent expression evaluation (commony called multiple dependency).  It also includes the possiblity of representing the full set of function results rather than only the results of domain-filtered parameters.

> > IEEE 754R is nearly over.  It is likely to include
> >    Decimal formats for floating point
> >        (Should C++ IA standard permit decimal intervals?)
> 
> We have explicitly asked this question (at the Mont-Tremblant meeting)
> to the IBM representant supporting the decimal floating-point proposal.
> He agreed that, at least currently, there is no need for this
> compatibility as the corresponding user communities targetted are
> a priori separate.

If you adopt this reasoning then there should be no interval standard.  Consider that a standard based upon the above rationale would maintain and/or increase that division within the user community.  I consider that to be a Bad Thing(tm).

> >    Fused Multiply and Add
> >        (I assume with directed rounding?
> >         Great for interval linear algebra, too)
> 
> I guess it also depends if there appears a function for doing fma
> on floating-point types in C++, in which case a natural overload
> for intervals would be nice and natural.

This is an iceberg issue.  It is not only the existence of an explicit fma function that is at issue.  The hidden part of this issue is that the compiler may transform ordinary algebraic expressions into fma instructions rather than just add & mul instructions.  If the code generation works for fp types but not for interval types then users will not want to use intervals.

The hidden part of this issue is not a library issue, but a compiler/code generator issue.  If fma support makes it into the language (which is mostly an issue of how to tell the compiler when it is forbidden to generate the fma instruction) then inline and template implementations of intervals will need to be written so they work no matter how the controls are set.  That can be fairly subtle due to the fact that the effect of outward rounding on an fma instruction is sometimes murky.

> ------------------------------
> 
> Message: 4
> Date: Tue, 04 Apr 2006 03:33:53 -0700
> From: Lawrence.Crowl at Sun.com
> Subject: Re: [std-interval] C++ interval std 
> To: For discussions concerning the C++ standardization of intervals
> 	<std-interval at compgeom.poly.edu>
> Message-ID: <200604041033.k34AXrbd008489 at philmont.sfbay.sun.com>
> 
> Sylvain Pion <Sylvain.Pion at sophia.inria.fr> writes:
>  >Well, if we're arguing that passsing-by-value is fundamentally important
>  >for speed, and that adding a few more tests is not because speed is less
>  >important... ;)
> 
> Pass-by-value is also a correctness issue.

How so?

> 
>  >> Uninitialized.  The convention in C/C++ is to initialize to zero,
>  >> but we agree that is not correct for intervals.  Whole is probably
>  >> the best we can do.
>  >
>  >I'm not convinced.  Initilization to [0,0] seems nice to me for
>  >intervals because of homogeneity reasons with floating-point.
>  >I could even imagine that the empty interval would make as much
>  >sense as whole.
>  >
>  >What makes you think that [0,0] is "not correct", and why 'whole'
>  >would be better than 'empty' ?
> 
> Note that on modern systems, initialization to [0,0] is more efficient.

Please state the reasoning behind the above statement.

> 
>  >>    Quad precision
>  >>        (Should C++ IA standard quad intervals?)
>  >
>  >I would say that it depends if quads appear in the C++ language
>  >(or is this supposed to be the already existing "long double" ?).
>  >But if they appear, probably support for interval<quads> should
>  >be added, yes.
> 
> The meaning of long double is implementation-dependent.  On Solaris
> SPARC, it is 128 bits.  On Solaris x86, it is 80 bits.

And some compilers accept the syntax of long double but don't implement it (long double becomes a synonym for double).

===================