[std-interval] PODs and parameter passing

[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: 2
> Date: 06 Apr 2006 00:25:57 +0200
> From: Gabriel Dos Reis <gdr at integrable-solutions.net>
> Subject: Re: [std-interval] Parameter passing
> To: For discussions concerning the C++ standardization of intervals
> 	<std-interval at compgeom.poly.edu>
> Message-ID: <m3fykrr762.fsf at uniton.integrable-solutions.net>
> Content-Type: text/plain; charset=iso-8859-1
> 
> first.i.last at comcast.net writes:
> 
> [...]
> 
> | A desirable property, but unnecessarily restrictive.  In particular interval 
> | objects with explicit properties might not be PODs.  
> 
> There are many PODs that do not have, nor need, a user-written copy
> constructor and destructor.  If the mental model of interval is that
> it is just a couple of floating point numbers, then Steve is
> exactly right.  Are you operating under the assumption that an
> interval is NOT essentially a couple of numbers?

Yes.

>  If yes, please be more specific.

First, there are properties that may need to be represented such as:
    -- openness of each end point
    -- domain filtration active flag (result is only partial)
    -- disjointness
    -- dependency list
    -- generative expression (built at run-time)
    -- and on non-IEEE machines, various flags/codes for
uninit, dead, and flavors of NaN (e.g., EIO, EDOM, ERANGE, div0, imag).

Second, and perhaps more important, while it is convenient to use a particular mental model of the internals of an interval, I doubt that it is strictly necessary.  Such a constraint upon the implementation will retard progress in developing innovative implementations. This is a non-trivial concern in that progress in the field is rapid and the goal of this effort is to establish a kind of best practice that will be emulated by implementations rather than to perform the classic standardization work of resolving conflicts among disparate existing implementations.

Third, the standard should not inhibit any existing practice without some consideration of the loss.  Algol's triplex type would be forbidden by the "an interval is two numbers" mental model.  It would still be a POD, and while natually substituable for an interval, could not comply with the "double interval[2]" mental model.  If necessary that kind of restriction is tolerable, but some showing of the necessity is called for.

> 
> [...]
> 
> | > Please note that our proposed interval type is meant to be a POD (plain
> | > old data) type and as such has no copy constructor nor destructor.
> | 
> | Is it your plan that the proposal include the POD-only requirement?  I would 
> | suggest that it is an obvious possibility that yeilds good performence 
> | improvements, but how important is it to get fat intervals quickly?
> | 
> | I would must prefer not to see such a requirement in the standard.
> 
> The proposal would need to be precise about whether internal<T> is a
> POD or not; that is unavoidable.

Why?  To the extent that concrete and abstract bound a range of degrees of specificity, what is lost by tending toward the abstract?

It appears to me that the fewer requirements we place upon implementations the greater the chance of acceptance and the greater the chance of implementors acting upon the opportunity.

In this regard I consider things like specific requirements of PODness to be a kind of fine print that should be minimized.

The only requirement for specificity I see would be to state whether or not the user is allowed to assume PODness.  And I would argue against that assumption.  But is such a statement in fact required?

> 
> [...]
> 
> | > Message: 3
> | > Date: Wed, 05 Apr 2006 05:49:41 -0700
> | > From: Lawrence.Crowl at Sun.com
> | > Subject: Re: [std-interval] Re: C++ interval std
> | > To: For discussions concerning the C++ standardization of intervals
> | > 	<std-interval at compgeom.poly.edu>
> | > Message-ID: <200604051249.k35Cnfbd008613 at philmont.sfbay.sun.com>
> | > 
> | > first.i.last at comcast.net writes:
> | >  >> 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 t reated as separate
> | >  >fields in software implementations of the run-time library).
> | > 
> | > The issue was the mechanism for passing the representation, not the
> | > logical opacity of the type.
> | 
> | The issue is the atomicity of the type.  Atomicity often implies effective 
> | opacity.  Opacity always implies atomicity.
> 
> Yet, at the end of the day the proposal needs to spell out the
> mechanism for passing the representation.  At the moment, I don't see
> how the committee would buy a proposal that is very vague about such
> issue.  Past experience with vagueness in that area has been a fertile
> source of programmer confusion, and defect reports (that the committee
> had to deal with).

Is an abstract type for parameters vague?

> 
> [...]
> 
> | > Message: 7
> | > Date: 05 Apr 2006 15:37:20 +0200
> | > From: Gabriel Dos Reis <gdr at integrable-solutions.net>
> | > Subject: Re: [std-interval] passing by value vs reference
> | > To: For discussions concerning the C++ standardization of intervals
> | > 	<std-interval at compgeom.poly.edu>
> | > Message-ID: <m3d5fwcfe7.fsf at uniton.integrable-solutions.net>
> | > Content-Type: text/plain; charset=iso-8859-1
> | > 

> | > If done that way, in the typical cases, the "T" would then appear in
> | > non-deducible context. 
> | 
> | It need not be a dependent type.  It could easily by a parallel set of templates.
> 
> More specifically?

----- interval.h -----
    template< T > struct Interval    { ... };
    template< T > struct IntervalArg { ... };

Such an abstraction would require each implementor to document the calling convention actually used so that interfacing with other languages was possible, but implementations already have to document all kinds of calling convention properties of which parameter passing is only one.

Does the interval standard need to be specific about who cleans arguments off of the stack? Or whether external symbols get leading underbar warts? Or whether stack frame management is required (call/ret versus enter/leave).  Parameter access specs don't really belong in a high level language.  (I know, C is not a high level language and C++ drags much of that along, but we can try...).

> 
> 
> [ As I mentioned earlier, I'm not sure template aliases help in this
> case. ]

I don't understand the term template alias.  Coud you describe one?

> ------------------------------
> 
> Message: 3
> Date: Thu, 06 Apr 2006 09:18:02 +0200
> From: Guillaume Melquiond <guillaume.melquiond at ens-lyon.fr>
> Subject: Re: [std-interval] Parameter passing
> To: std-interval at compgeom.poly.edu
> Message-ID: <1144307882.3988.78.camel at saline>
> Content-Type: text/plain; charset=ISO-8859-1
> 
> Le mercredi 05 avril 2006 à 21:48 +0000, first.i.last at comcast.net a
> écrit :
>  
> > > Please note that our proposed interval type is meant to be a POD (plain
> > > old data) type and as such has no copy constructor nor destructor.
> > 
> > Is it your plan that the proposal include the POD-only requirement?  I would 
> > suggest that it is an obvious possibility that yeilds good performence 
> > improvements, but how important is it to get fat intervals quickly?
> > 
> > I would must prefer not to see such a requirement in the standard.
> 
> If an implementation follows the specification of our proposal, then the
> resulting type is necessarily a POD. The interface has been specially
> designed so that it happens. With respect to the scope of our proposal,
> I don't see the point of adding a non-POD field to the interval class
> (what would it contain?) or of saying that the copy constructor and the
> destructor have side effects (what would they do?). Maybe we missed
> something in writing the proposal, but at least our toy implementation
> was clearly a POD.

I understand that the current version of the proposal requires that
intervals bs PODs and further than they are just two floating point values.  I suggest that both of those constraints be relaxed.
> 
> > > As a
> > > consequence, on some architectures and with non-broken compilers, they
> > > will behave no differently than if the function arguments were simply
> > > integers; except that the register will probably be bigger, or two
> > > registers will be used. When this happens, passing by value will be
> > > faster than passing by const-reference. Indeed there is no architecture
> > > such that foo(int) is slower than bar(int const &).
> > 
> > Of course there is.  When addresses are narrow (fit in a register) and ints 
> are 
> > wide (don't fit in a register).  64-bit code on 32-bit hardware.  32-bit code 
> on 
> > 16-bit hardware.  16-bit code on 8-bit hardware.  I've even worked on a 
> > bit-slice machine with 20-bit ints and 16-bit addresses.
> 
> It is not enough to consider only the part where the caller writes the
> arguments. You are missing the part where the callee reads the
> arguments. This requires an indirection when passing an argument by
> reference. Let us consider a non-trivial example like the successor
> function:
> 
>   int foo(int a)        { return a + 1; }
>   int bar(int const &a) { return a + 1; }
> 
> So I state it again, slightly modified: there is no architecture such
> that foo(int) is slower than bar(int const &) if the functions use the
> integer argument.

If the function call hierarchy is deep then many functions will accept and pass on parameters with only the leaf functions actually "using" the values.

But this is far afield from the real issue because floats aren't ints and many compilers will not pass floats in registers, much less structs in registers.  The standard should not make unnecessary assumptions about what implementations are willing and able to do at the lower levels.

> 
> > > I don't see any additional complexity in 4 with respect to 3. As already
> > > mentioned by Bill Clarke, you could simply have a typedef member in
> > > interval<T> to express the calling convention of the functions of the
> > > interval library: typedef interval<T> const &param_type;
> > > 
> > > This requires all the functions of the library to use the same calling
> > > convention.
> > 
> > How do you derive this requirement?  I don't see it.
> 
> If you have two functions with different calling conventions:
> 
>   interval foo(interval, interval);
>   interval bar(interval const &, interval const &);
> 
> then one of them is obviously not of the type
> 
>   interval binary_function(param_type, param_type);

Of course.

Does the existence of the type definition _require_ its use?  I think not.  On the assumption that some strange function (of which I am at present unable to conceive an example) needs to use the "other" convention, it can simply do so.  The only value in standardizing the convention lies in the assumption that users will emulate it.  If the library sets a default convention either implicitly via bare argument declarations or explicitly with a specific argument type definition then users will adopt the default convention.  That does not require that there be no exceptions to the default convention.

My dispute is with: "This REQUIRES [emphais added] all the functions of the library to use the same calling convention."  It permits/encourages the use of the same convention, but does not mandate it.

> ------------------------------
> 
> Message: 4
> Date: Thu, 06 Apr 2006 09:18:09 +0200
> From: Guillaume Melquiond <guillaume.melquiond at ens-lyon.fr>
> Subject: Re: [std-interval] passing by value vs reference
> To: std-interval at compgeom.poly.edu
> Message-ID: <1144307889.3988.80.camel at saline>
> Content-Type: text/plain; charset=ISO-8859-1
> 
> Le mercredi 05 avril 2006 à 13:55 -0300, Fernando Cacciola a écrit :
> 
> > If  the FPU registers are stacked, like in the x86 family, it wouldn't
> > be too uncommon, IMHO, for a compiler to do:
> 
> [...]
> 
> As a matter of fact, it would be really uncommon. For example, x86 ABIs
> require the FPU stack to be empty (except maybe for arguments) at the
> beginning of every functions.

There are x86 systems without the (draconian) requirement for an empty FPU stack on function entry.  It is vary hard to evaluate a substantial expression efficiently under that requirement.

> Otherwise the functions would cause FPU
> stack overflows since they would have very little or no space left to do
> their computations.

That is what the stack overflow trap is for.

> Thanks to the empty stack, the compiler knows that
> it can use eight FPU registers without crashing the whole process. So
> for the particular example of (a*b)*(c*d), there is no way for a
> compiler to avoid temporarily storing the result of a*b on the memory stack.

Of course there is.  Pseudo code using FPU stack only with depth comments:

mulltree:      ; 0
    push a      ; 1
    push b      ; 2
    mul          ; 1
    push c      ; 2
    push d      ; 3
    mul          ; 2
    mul          ; 1

> 
> > That is, stacked FPU registers allows the compiler to allocate the
> > function frames (which is the problem in your example) without using
> > the external memory-based stack or rearranging the registers
> > manually. 
> 
> As a side note on this topic, stacked FPU registers seemed like a good
> idea thirty years ago. But now that the technology has evolved and has
> gone past GHz speeds, this good idea has become a nightmare for
> processor designers. Translating stack positions to standard bank
> positions incur a huge latency in decoding FPU instructions in the
> processor. This translation work is better done once and for all at
> compilation time. I would be really surprised if a modern processor
> (that is not plagued by backward compatibility concerns) implements
> stacked FPU registers.

If that were true (I am agnostic) then compilers would be better off generating explict register access instructions instead of implicit stack access instructions.  Even the x87 has both.

My understanding is that the opposite is occurring.  For instance, one well regarded compiler used to reserve some of the registers for explicit access and used the rest as a stack.  Fairly recently they discarded the direct access area and now use the entire register set as a stack.  This in a compiler known for decades to generate tight, fast code.

Point is that we should not be trying to shoehorn intervals into a single theoretical platform model unless it is absolutely necessary.

> ------------------------------
> 
> Message: 6
> Date: Thu, 06 Apr 2006 00:31:20 -0700
> From: Steve Clamage <Stephen.Clamage 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: <4434C3C8.7050808 at sun.com>
> Content-Type: text/plain; charset=us-ascii; format=flowed
> 
> Alan Eliasen wrote:
> > Steve Clamage wrote:
> > 
> > 
> > 
> >>>Bill Clarke wrote:
> >>>
> >>>
> >>>>This experiment is extremely platform specific, as you probably are
> >>>>aware.  Most platforms in use today other than x86 will be the other way
> >>>>around (add-by-value will be faster than add-by-const-ref).
> > 
> > 
> > Alan Eliasen wrote:
> > 
> >>>   How can that assertion possibly be made?  As you know, if a parameter
> >>>is passed by value, then the copy constructor is automatically called
> >>>for each object (e.g. twice for an add operator) on function entry, and
> >>>then the destructor is called (twice) on function exit.
> >>
> > 
> > Steve Clamage wrote:
> > 
> >>A simple object like complex or interval should have no user-defined
> >>copy constructor or destructor. That is, the default copy constructor
> >>generated by the compiler does the right thing and does not need to be
> >>user-defined. The destructor has nothing to do, and so should not be
> >>user-defined. In that case, pass-by-value can be optimized into register
> >>passing with no additional copying.
> > 
> > 
> >    You still agree, though, that even if the implementation doesn't do
> > memory allocation in the constructor, the compiler will still generate a
> > copy constructor and a destructor, (perhaps pretty simple and efficient)
> > and these will get normally get called in a pass-by-value.  Again, a
> > very smart compiler can optimize these away if it realizes that the copy
> > is unnecessary, but by simply specifying call-by-constant-reference, we
> > don't have to hope that the compiler is very smart.  We simply eliminate
> > even the possibility of calling the copy constructor and destructor.
> 
> In C++, every type (including int) has a constructor and destructor. This point 
> of definition simplifies the exposition of language rules. We are saved from 
> hopelessly inefficient implementations by the "as-if rule." It says the 
> implementation can do what is wants as long as observable behavior is preserved. 
> Multiple copies of temporary objects (as in parameter and returned-value 
> passing) are not counted in "observable behavior" -- extra copies can be elided.
> 
> For POD types, I have never seen or heard of a compiler that actually generated 
> a real constructor or destructor. Compilers perform a simple copy by whatever 
> means is most efficient.

You have stated the key point quite well.  It means that one writes code for correctness and efficiency (algorithm selection) but one leaves the low-level details to the compiler.

We can trust that the implementors will have at least as much interest in fast code as we do and that they will be far better informed as to what matters on their target platforms.  So the issue should be delegated to the implementors.

> ******************************************

-- Lee Winter