gdalgorithms-list

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Charles N. <cha...@gm...>]

cast-through-union does violate the standard, but I think it's one of those
decisions where you draw the line at "what works on all of the compilers _i_
use" vs "conforming to the standard as written".  We're not all working on
boost! (thank god)  :-D
-charles

On Tue, Mar 3, 2009 at 10:08 PM, Alen Ladavac <ale...@cr...> wrote:

> Thanks. A template is a nice approach for abstracting this. Btw, I'd
> add a static_assert(sizeof(U)==sizeof(T)) there.
>
> But isn't union a not-completely-legal way to do this? From the
> remainder of the thread and from some experimentation, I'd say that
> the best way would be to use memcpy()...
>
> Alen
>
> Pal-Kristian wrote at 3/3/2009:
>
> > Try this useful template:
>
> > template<typename T, typename U>
> > static T bit_cast(const U val)
> > {
> >     union { U u; T t; } bits = { val };
> >     return bits.t;
> > }
>
> > Now:
> >     float f = ...;
> >     uint32_t u = bit_cast<uint32_t>(f);
>
> > Should work.
>
> > Alen Ladavac wrote:
> >> christer wrote at 3/3/2009:
> >>
> >>> It's not unusual, but most attempts to do so are most certainly
> >>> undefined. As already witnessed in this thread! ;P
> >>>
> >>
> >> What is your recommendation for a portable way to obtain a float's bits
> >> as an integer?
> >>
> >> Thanks,
> >> Alen
> >>
> >>
> >>
> ------------------------------------------------------------------------------
> >> Open Source Business Conference (OSBC), March 24-25, 2009, San
> Francisco, CA
> >> -OSBC tackles the biggest issue in open source: Open Sourcing the
> Enterprise
> >> -Strategies to boost innovation and cut costs with open source
> participation
> >> -Receive a $600 discount off the registration fee with the source code:
> SFAD
> >> http://p.sf.net/sfu/XcvMzF8H
> >> _______________________________________________
> >> GDAlgorithms-list mailing list
> >> GDA...@li...
> >> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> >> Archives:
> >>
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
> >>
> >>
>
>
>
>
>
> --
> Alen
>
>
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco,
> CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the
> Enterprise
> -Strategies to boost innovation and cut costs with open source
> participation
> -Receive a $600 discount off the registration fee with the source code:
> SFAD
> http://p.sf.net/sfu/XcvMzF8H
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Jeff R. <je...@8m...>]

if cast-through-union violates the standard, then why are unions in the
language? isn't storing bytes and interpreting them as different types what
unions are for?

Re: [Algorithms] How to get 3dvector largest coordinate index?

[<chr...@pl...>]

Jeff Russell wrote:

> if cast-through-union violates the standard, then why are unions in
> the language? isn't storing bytes and interpreting them as different
> types what unions are for?

No, that's not what unions are for. Unions are there to allow
you to store different type data in the same memory location
at DIFFERENT (nonoverlapping) TIMES.

Standard-violating aliasing is when you have different type
data in the same memory location at the SAME TIME.

The standard disallows same-time different-type aliasing,
because disallowing it allows for a lot of optimization
opportunities. This is a GOOD THING -- except programmers
need to learn to write standard-conforming code (which is
also a GOOD THING).


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Jon W. <jw...@gm...>]

Jeff Russell wrote:
> if cast-through-union violates the standard, then why are unions in 
> the language? isn't storing bytes and interpreting them as different 
> types what unions are for?

Unions are there to save storage space and/or simplify variant-record 
implementations, often in embedded, limited memory or systems 
programming situations. Comes up in file systems, network protocols, and 
all kinds of other low-level programming.

Sincerely,

jw

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Will V. <wi...@se...>]

On Thu, 05 Mar 2009 15:33:32 +1300, Jeff Russell <je...@8m...>  
wrote:
> isn't storing bytes and interpreting them as different types what unions  
> are for?

I think the original intent of unions is to store discrete instances of  
variant types, rather than as a mechanism for reinterpreting. So you read  
and write the same type through the union, rather than reading one and  
writing the other. Typically you wrap this up in a struct with a label  
field (to tell you what's in the union, so you don't read and write the  
wrong thing) plus the union payload itself.

Cheers,

Will

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Matt J <mjo...@gm...>]

Well, I guess it depends on what standard you use (so many to choose from).
But like I mentioned before in the latest C99 TC3 standard it adds a clause
that says it is okay to do "type punning" through a union. Here is an FFMPEG
post that discusses it in detail:

http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/2008-December/056962.html

Finally, even CERT thinks its okay:

https://www.securecoding.cert.org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.pdf?version=1

See page 75. Which was written in 2009. I understand that is an argument
based on an appeal to authority, but the assumption here is these four guys
that wrote this understand good coding practices better than most. GCC holds
C++ code to C99 standards, from what I read. So.... code that tried to
optimize unions would be non-conforming not to mention break tons of legacy
code in C and C++


>
> > if cast-through-union violates the standard, then why are unions in
> > the language? isn't storing bytes and interpreting them as different
> > types what unions are for?
>
> No, that's not what unions are for. Unions are there to allow
> you to store different type data in the same memory location
> at DIFFERENT (nonoverlapping) TIMES.
>
> Standard-violating aliasing is when you have different type
> data in the same memory location at the SAME TIME.
>
> The standard disallows same-time different-type aliasing,
> because disallowing it allows for a lot of optimization
> opportunities. This is a GOOD THING -- except programmers
> need to learn to write standard-conforming code (which is
> also a GOOD THING).
>
>
>

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Jeff R. <je...@8m...>]

yea i was gonna say, use of unions to reinterpret types is fairly widespread
from what i can tell. if its wrong, a lot of software could have a lot of
trouble with a "correct" compiler. or is this one of those cases where no
compiler does it "right" anyway (at least by default) because so much
existing code would break?
the performance benefit of strict aliasing seems straightforward and hard to
argue with. but it also seems like there should be *something* though.
reinterpret_cast doesn't do the job either? seems odd that somehow the char*
would be magical...

jeff

On Thu, Mar 5, 2009 at 12:23 AM, Matt J <mjo...@gm...> wrote:

>
> Well, I guess it depends on what standard you use (so many to choose from).
> But like I mentioned before in the latest C99 TC3 standard it adds a clause
> that says it is okay to do "type punning" through a union. Here is an FFMPEG
> post that discusses it in detail:
>
> http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/2008-December/056962.html
>
> Finally, even CERT thinks its okay:
>
>
> https://www.securecoding.cert.org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.pdf?version=1
>
> See page 75. Which was written in 2009. I understand that is an argument
> based on an appeal to authority, but the assumption here is these four guys
> that wrote this understand good coding practices better than most. GCC holds
> C++ code to C99 standards, from what I read. So.... code that tried to
> optimize unions would be non-conforming not to mention break tons of legacy
> code in C and C++
>
>
>>
>> > if cast-through-union violates the standard, then why are unions in
>> > the language? isn't storing bytes and interpreting them as different
>> > types what unions are for?
>>
>> No, that's not what unions are for. Unions are there to allow
>> you to store different type data in the same memory location
>> at DIFFERENT (nonoverlapping) TIMES.
>>
>> Standard-violating aliasing is when you have different type
>> data in the same memory location at the SAME TIME.
>>
>> The standard disallows same-time different-type aliasing,
>> because disallowing it allows for a lot of optimization
>> opportunities. This is a GOOD THING -- except programmers
>> need to learn to write standard-conforming code (which is
>> also a GOOD THING).
>>
>>
>>
>
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco,
> CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the
> Enterprise
> -Strategies to boost innovation and cut costs with open source
> participation
> -Receive a $600 discount off the registration fee with the source code:
> SFAD
> http://p.sf.net/sfu/XcvMzF8H
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

[Algorithms] Strict Aliasing ( was Re: How to get 3dvector largest coordinate index? )

[Justin S. <jus...@ho...>]

FYI: I believe Mike Acton covered the issue pretty thoroughly here:
http://www.cellperformance.com/mike_acton/2006/06/understanding_strict_aliasing.html

No explanation of the specialness of char* however.

Cheers,
Justin.

On 05/03/2009, at 5:37 PM, Jeff Russell wrote:

> yea i was gonna say, use of unions to reinterpret types is fairly  
> widespread from what i can tell. if its wrong, a lot of software  
> could have a lot of trouble with a "correct" compiler. or is this  
> one of those cases where no compiler does it "right" anyway (at  
> least by default) because so much existing code would break?
>
> the performance benefit of strict aliasing seems straightforward and  
> hard to argue with. but it also seems like there should be  
> *something* though. reinterpret_cast doesn't do the job either?  
> seems odd that somehow the char* would be magical...
>
> jeff
>
> On Thu, Mar 5, 2009 at 12:23 AM, Matt J <mjo...@gm...>  
> wrote:
>
> Well, I guess it depends on what standard you use (so many to choose  
> from). But like I mentioned before in the latest C99 TC3 standard it  
> adds a clause that says it is okay to do "type punning" through a  
> union. Here is an FFMPEG post that discusses it in detail:
>
> http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/2008-December/056962.html
>
> Finally, even CERT thinks its okay:
>
> https://www.securecoding.cert.org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.pdf?version=1
>
> See page 75. Which was written in 2009. I understand that is an  
> argument based on an appeal to authority, but the assumption here is  
> these four guys that wrote this understand good coding practices  
> better than most. GCC holds C++ code to C99 standards, from what I  
> read. So.... code that tried to optimize unions would be non- 
> conforming not to mention break tons of legacy code in C and C++
>
>
> > if cast-through-union violates the standard, then why are unions in
> > the language? isn't storing bytes and interpreting them as different
> > types what unions are for?
>
> No, that's not what unions are for. Unions are there to allow
> you to store different type data in the same memory location
> at DIFFERENT (nonoverlapping) TIMES.
>
> Standard-violating aliasing is when you have different type
> data in the same memory location at the SAME TIME.
>
> The standard disallows same-time different-type aliasing,
> because disallowing it allows for a lot of optimization
> opportunities. This is a GOOD THING -- except programmers
> need to learn to write standard-conforming code (which is
> also a GOOD THING).
>
>
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San  
> Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the  
> Enterprise
> -Strategies to boost innovation and cut costs with open source  
> participation
> -Receive a $600 discount off the registration fee with the source  
> code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San  
> Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the  
> Enterprise
> -Strategies to boost innovation and cut costs with open source  
> participation
> -Receive a $600 discount off the registration fee with the source  
> code: SFAD
> http://p.sf.net/sfu/XcvMzF8H_______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Strict Aliasing ( was Re: How to get 3dvector largest coordinate index? )

[<chr...@pl...>]

Justin Saunders wrote:
> FYI: I believe Mike Acton covered the issue pretty thoroughly here:
> http://www.cellperformance.
> com/mike_acton/2006/06/understanding_strict_aliasing.html
>
> No explanation of the specialness of char* however.

My memory talk from GDC'03 covered this pretty thoroughly too:

http://realtimecollisiondetection.net/pubs/GDC03_Ericson_Memory_Optimization.ppt

It's not like this is a new thing.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Conor S. <bor...@ya...>]

The point more is that just because it works some of the time as an artefact of a "correct" implementation (on most platforms, ints and floats being the same size etc), it doesn't mean that it will work everytime (and it isn't portable). One of the more important points is that (for example) in C++98 compilers, there is no guarantee on the number of bits for most of the integral data types other than a minimal possible size and representable range. 

http://en.wikibooks.org/wiki/C%2B%2B_Programming/Data_Types_Reference

Cheers,
Conor



________________________________
From: Jeff Russell <je...@8m...>
To: Game Development Algorithms <gda...@li...>
Sent: Thursday, 5 March, 2009 3:37:02 PM
Subject: Re: [Algorithms] How to get 3dvector largest coordinate index?

yea i was gonna say, use of unions to reinterpret types is fairly widespread from what i can tell. if its wrong, a lot of software could have a lot of trouble with a "correct" compiler. or is this one of those cases where no compiler does it "right" anyway (at least by default) because so much existing code would break?

the performance benefit of strict aliasing seems straightforward and hard to argue with. but it also seems like there should be *something* though. reinterpret_cast doesn't do the job either? seems odd that somehow the char* would be magical...

jeff


On Thu, Mar 5, 2009 at 12:23 AM, Matt J <mjo...@gm...> wrote:

 
Well, I guess it depends on what standard you use (so many to choose from). But like I mentioned before in the latest C99 TC3 standard it adds a clause that says it is okay to do "type punning" through a union. Here is an FFMPEG post that discusses it in detail:
 
http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/2008-December/056962.html
 
Finally, even CERT thinks its okay:
 
https://www.securecoding.cert.org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.pdf?version=1
 
See page 75. Which was written in 2009. I understand that is an argument based on an appeal to authority, but the assumption here is these four guys that wrote this understand good coding practices better than most. GCC holds C++ code to C99 standards, from what I read. So.... code that tried to optimize unions would be non-conforming not to mention break tons of legacy code in C and C++
 

> if cast-through-union violates the standard, then why are unions in
> the language? isn't storing bytes and interpreting them as different
> types what unions are for?

No, that's not what unions are for. Unions are there to allow
you to store different type data in the same memory location
at DIFFERENT (nonoverlapping) TIMES.

Standard-violating aliasing is when you have different type
data in the same memory location at the SAME TIME.

The standard disallows same-time different-type aliasing,
because disallowing it allows for a lot of optimization
opportunities. This is a GOOD THING -- except programmers
need to learn to write standard-conforming code (which is
also a GOOD THING).


 
------------------------------------------------------------------------------
Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
-OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
-Strategies to boost innovation and cut costs with open source participation
-Receive a $600 discount off the registration fee with the source code: SFAD
http://p.sf.net/sfu/XcvMzF8H
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list


      Stay connected to the people that matter most with a smarter inbox. Take a look http://au.docs.yahoo.com/mail/smarterinbox

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Matt J <mjo...@gm...>]

I do not think that is the point Christer is making. On P. 438 of his book
he has an example of code that removes an explicit check for divide by zero
(by assuming the behavior of IEEE and the behavior of NaN, which could be a
trap representation), and he suggests is not portable but can be used as a
'quick and dirty' solution, because you can check for an error using
exception handling and fall back to a more robust version. So why can't that
exact same argument be made with a union cast? Also, if that is legal code,
why isn't a union cast?  To me it seems like when you are trying to optimize
something for fun and by definition it is machine specific because your
interpreting an IEEE float as a series of bits, beating someone over the
head with a standards book is a little bit of a cheap shot - especially when
it is legal by the latest C99 TC3 standards and works on a wide range of
compilers including, but not limited to, GCC w/ strict aliasing


>  The point more is that just because it works some of the time as an
> artefact of a "correct" implementation (on most platforms, ints and floats
> being the same size etc), it doesn't mean that it will work everytime (and
> it isn't portable). One of the more important points is that (for example)
> in C++98 compilers, there is no guarantee on the number of bits for most of
> the integral data types other than a minimal possible size and representable
> range.
>
> http://en.wikibooks.org/wiki/C%2B%2B_Programming/Data_Types_Reference
>
> Cheers,
> Conor
>

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Gino v. d. B. <gin...@gm...>]

I tend to agree. When replacing a float compare by an integer compare on 
the bit representation of the floats, strict-aliasing is the least of 
your problems. (Other assumptions: sizeof(int32_t) == sizeof(float), 
floats are IEEE754-ish (PS2 included), floats are non-negative and 
finite) I don't see why the type-pun through a union is discredited so 
badly. I have yet to be bitten by a union type pun. To turn the argument 
around: Does anyone here know of a compiler for which type punning 
through a union does not give the proper result? The whole "union is 
considered harmful" debate seems to be a mostly religious one. In any 
way, how hard is it to create a rule in autoconf or cmake (build tools 
you would use in cross-platform projects) that checks whether the used 
compiler exploits strict-aliasing in unions and set a define accordingly?

Matt J wrote:
>  
> I do not think that is the point Christer is making. On P. 438 of his 
> book he has an example of code that removes an explicit check for 
> divide by zero (by assuming the behavior of IEEE and the behavior of 
> NaN, which could be a trap representation), and he suggests is not 
> portable but can be used as a 'quick and dirty' solution, because you 
> can check for an error using exception handling and fall back to a 
> more robust version. So why can't that exact same argument be made 
> with a union cast? Also, if that is legal code, why isn't a union 
> cast?  To me it seems like when you are trying to optimize something 
> for fun and by definition it is machine specific because your 
> interpreting an IEEE float as a series of bits, beating someone over 
> the head with a standards book is a little bit of a cheap shot - 
> especially when it is legal by the latest C99 TC3 standards and works 
> on a wide range of compilers including, but not limited to, GCC w/ 
> strict aliasing
>  
>
>     The point more is that just because it works some of the time as
>     an artefact of a "correct" implementation (on most platforms, ints
>     and floats being the same size etc), it doesn't mean that it will
>     work everytime (and it isn't portable). One of the more important
>     points is that (for example) in C++98 compilers, there is no
>     guarantee on the number of bits for most of the integral data
>     types other than a minimal possible size and representable range. 
>
>     http://en.wikibooks.org/wiki/C%2B%2B_Programming/Data_Types_Reference
>
>     Cheers,
>     Conor
>
>  
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
> -Strategies to boost innovation and cut costs with open source participation
> -Receive a $600 discount off the registration fee with the source code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] How to get 3dvector largest coordinate index?

[liam m. <lia...@go...>]

2009/3/6 Gino van den Bergen <gin...@gm...>

> The whole "union is
> considered harmful" debate seems to be a mostly religious one.
>
> It is really quite simple in that it is undefined behaviour to type cast
using a union. Now if you want to heed this information it is up to you,
just because something works on day X on compiler Y does not mean it will
work on a different version of the compiler or on a different compiler
altogether.

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Gino v. d. B. <gin...@gm...>]

Yes, I know. Call me reckless but I just do not believe that 
strict-aliasing on union fields will be exploited by a C++ compiler any 
time soon. It will break too much existing code (not only mine).

liam mail wrote:
>
>
> 2009/3/6 Gino van den Bergen <gin...@gm... 
> <mailto:gin...@gm...>>
>
>     The whole "union is
>     considered harmful" debate seems to be a mostly religious one.
>
> It is really quite simple in that it is undefined behaviour to type 
> cast using a union. Now if you want to heed this information it is up 
> to you, just because something works on day X on compiler Y does not 
> mean it will work on a different version of the compiler or on a 
> different compiler altogether.
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
> -Strategies to boost innovation and cut costs with open source participation
> -Receive a $600 discount off the registration fee with the source code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] How to get 3dvector largest coordinate index?

[liam m. <lia...@go...>]

2009/3/6 Gino van den Bergen <gin...@gm...>

> Yes, I know. Call me reckless but I just do not believe that
> strict-aliasing on union fields will be exploited by a C++ compiler any
> time soon. It will break too much existing code (not only mine).
>
> liam mail wrote:
> >
> >
> > 2009/3/6 Gino van den Bergen <gin...@gm...
> > <mailto:gin...@gm...>>
> >
> >     The whole "union is
> >     considered harmful" debate seems to be a mostly religious one.
> >
> > It is really quite simple in that it is undefined behaviour to type
> > cast using a union. Now if you want to heed this information it is up
> > to you, just because something works on day X on compiler Y does not
> > mean it will work on a different version of the compiler or on a
> > different compiler altogether.
> > ------------------------------------------------------------------------
> >
> >
> ------------------------------------------------------------------------------
> > Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco,
> CA
> > -OSBC tackles the biggest issue in open source: Open Sourcing the
> Enterprise
> > -Strategies to boost innovation and cut costs with open source
> participation
> > -Receive a $600 discount off the registration fee with the source code:
> SFAD
> > http://p.sf.net/sfu/XcvMzF8H
> > ------------------------------------------------------------------------
> >
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> >
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco,
> CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the
> Enterprise
> -Strategies to boost innovation and cut costs with open source
> participation
> -Receive a $600 discount off the registration fee with the source code:
> SFAD
> http://p.sf.net/sfu/XcvMzF8H
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

I am sorry I do not understand why you think this is to do with aliasing?
The standard guarantees that union fields occupy the same space yet that
only one maybe active.

9.5 Unions [class.union]
1 In a union, at most one of the data members can be active at any time,
that is, the value of at most one of
the data members can be stored in a union at any time. [Note: one special
guarantee is made in order to
simplify the use of unions: If a POD-union contains several POD-structs that
share a common initial
sequence (9.2), and if an object of this POD-union type contains one of the
POD-structs, it is permitted to
inspect the common initial sequence of any of POD-struct members; see 9.2. ]

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Gino v. d. B. <gin...@gm...>]

Aliasing is having multiple references to the same memory location. 
That's exactly what's happening when type punning. An example

    union Pun
    {
         float  f;
         int32_t i;
    };

...

    Pun pun;
    pun.f = x;
    int32_t result = pun.i;

According to the C++ standard a compiler would be allowed to fetch pun.i 
before pun.f has been written and the result would contain garbage 
instead of the bit-representation of x. I do not see this happening with 
gcc, so either gcc's optimizer has a flaw, or the developers 
deliberately chose not to exploit type strictness in this case. I assume 
the latter.

liam mail wrote:
>
> I am sorry I do not understand why you think this is to do with 
> aliasing? The standard guarantees that union fields occupy the same 
> space yet that only one maybe active.
>
> 9.5 Unions [class.union]
> 1 In a union, at most one of the data members can be active at any 
> time, that is, the value of at most one of
> the data members can be stored in a union at any time. [Note: one 
> special guarantee is made in order to
> simplify the use of unions: If a POD-union contains several 
> POD-structs that share a common initial
> sequence (9.2), and if an object of this POD-union type contains one 
> of the POD-structs, it is permitted to
> inspect the common initial sequence of any of POD-struct members; see 
> 9.2. ]
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
> -Strategies to boost innovation and cut costs with open source participation
> -Receive a $600 discount off the registration fee with the source code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] How to get 3dvector largest coordinate index?

[liam m. <lia...@go...>]

2009/3/6 Gino van den Bergen <gin...@gm...>

> Aliasing is having multiple references to the same memory location.



> "Call me reckless but I just do not believe that
> strict-aliasing on union fields will be exploited by a C++ compiler any
> time soon."

Thank you I know what aliasing is, but as I said I do not see what this has
to do with your comment as the standard guarantees the same space is in use.


> According to the C++ standard a compiler would be allowed to fetch pun.i
> before pun.f has been written



> and the result would contain garbage
> instead of the bit-representation of x.


Would you mind quoting or pointing me to the part of the standard which
implies this.

Liam

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Gino v. d. B. <gin...@gm...>]

My bad. It's the C99 standard, not the C++98 standard.

"The following are unspecified: ... The value of a union member other 
than the last one stored into (6.2.6.1)."

liam mail wrote:
>
>
> 2009/3/6 Gino van den Bergen <gin...@gm... 
> <mailto:gin...@gm...>>
>
>     Aliasing is having multiple references to the same memory location. 
>
>  
>
>     "Call me reckless but I just do not believe that
>     strict-aliasing on union fields will be exploited by a C++
>     compiler any
>     time soon."
>
> Thank you I know what aliasing is, but as I said I do not see what 
> this has to do with your comment as the standard guarantees the same 
> space is in use.
>
>
>     According to the C++ standard a compiler would be allowed to fetch
>     pun.i
>     before pun.f has been written 
>
>  
>
>     and the result would contain garbage
>     instead of the bit-representation of x. 
>
>
> Would you mind quoting or pointing me to the part of the standard 
> which implies this.
>
> Liam
> ------------------------------------------------------------------------
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
> -Strategies to boost innovation and cut costs with open source participation
> -Receive a $600 discount off the registration fee with the source code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> ------------------------------------------------------------------------
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Philip T. <ph...@za...>]

Gino van den Bergen wrote:
> Yes, I know. Call me reckless but I just do not believe that 
> strict-aliasing on union fields will be exploited by a C++ compiler any 
> time soon. It will break too much existing code (not only mine).

Exploiting strict aliasing for normal non-union variables breaks a lot 
of existing code too, but GCC does it by default anyway, presumably 
because the performance benefits are significant and because it can give 
adequate warnings for broken code.

It still seems unlikely that a compiler would break code using union, 
because the cost/benefit tradeoff isn't as worthwhile as for general 
pointer strict-aliasing (it probably wouldn't help performance in many 
programs, and it would probably be hard to emit warnings without lots of 
false positives or negatives). But what reasons are there to 
intentionally *not* write code that unambiguously respects the aliasing 
rules?

In the float-to-int case, instead of writing "i = *(int*)&f" you can 
simply write "memcpy(&i, &f, 4)", which (as far as I can tell) is 
perfectly valid in terms of aliasing, and usually just as efficient 
(sometimes a little more, sometimes a little less) as using *(int*)& or 
union, since the function call is entirely optimised away by common 
compilers. And then there's no need to continue arguing over the safety 
of union :-)

(And if you really care about performance in the float-to-int code then 
you'll use whatever compiler-specific tricks give the right result, and 
be careful to test its correctness and performance whenever you change 
compiler or compiler options, and none of the standards-related 
discussion matters.)

-- 
Philip Taylor
ph...@za...

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Bert P. <be...@bp...>]

Gino van den Bergen schreef:
> The whole "union is 
> considered harmful" debate seems to be a mostly religious one.

Well, I agree, and some leeway is certainly necessary in everyday
work just to get the job done.  Pressing hard for 100% compliant
code stops being productive at some point.

Nonetheless, a reason it's so easy to get upset over this, is that
there is definitely a slippery slope risk here.  If you set out to
write 100% bug-free code, then anybody with more than 1 week
experience will quickly realize that this is a dream and at best you
can hope for, say, 90% bug-free code.  However, if you accept this
from the start and set out to write 90% bug free code, you'll end up
with something that's 50% bugfree, just because people cut corners
and shuffle things under the carpet as "belonging to that shady 10%",
and it adds up.  It's a mentality shift, from aiming for perfection
and getting a little nervous when you cheat, to accepting cheating
as inherent to regular production, and off we all go.

I can certainly see how openly telling a team that it's okay to use
nonstandard practices if "they seem to work everywhere" may lead to a
situation where everybody is contributing code in what is essentially
their own personal approximation of c++.  We don't need that in an
industry that considers const correctness and /W4 -Wall clean code
as 'exotic' or 'unrealistic'.


end rant :)

bert

Re: [Algorithms] How to get 3dvector largest coordinate index?

[<chr...@pl...>]

Matt J wrote:
> [...] Finally, even CERT thinks its okay:
>
> https://www.securecoding.cert.
>
org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.

> pdf?version=1
>
> See page 75. Which was written in 2009.

You are confused. They are talking about gcc only, as
made clear by the reference to "-fstrict-aliasing" smack
in the middle of that slide.


Christer Ericson, Director of Tools and Technology
Sony Computer Entertainment, Santa Monica

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Charles N. <cha...@gm...>]

On Thu, Mar 5, 2009 at 10:37 AM, <chr...@pl...>wrote:

> Matt J wrote:
> > [...] Finally, even CERT thinks its okay:
> >
> > https://www.securecoding.cert.
> >
>
> org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.
>
> > pdf?version=1
> >
> > See page 75. Which was written in 2009.
>
> You are confused. They are talking about gcc only, as made clear by the
> reference to "-fstrict-aliasing" smack in the middle of that slide.


It looks to me like the CERT paper cited specifically refers to C99 (on gcc,
as Christer mentioned).  Matt, you made the point that gcc applies the
TSAA/strict-aliasing rules when running in C++ mode as well, but I think
that's even more evidence that this really is compiler-specific stuff here,
and that it's important to be aware + tread carefully when you move to a new
environment (gcc -> llvm, for a hypothetical example, given how much apple
is investing in llvm infrastructure these days).

Ultimately I think it matters most that you're very aware of when and where
you violate the standard, and make sure you test your violations on every
platform you're compiling on, with all your optimizations turned on.  If you
can wrap it up in a macro/function that you know works on all of your
platforms/compilers, so much the better.

-charles

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Charles N. <cha...@gm...>]

On Wed, Mar 4, 2009 at 10:23 PM, Matt J <mjo...@gm...> wrote:

>
> Well, I guess it depends on what standard you use (so many to choose from).
> But like I mentioned before in the latest C99 TC3 standard it adds a clause
> that says it is okay to do "type punning" through a union. Here is an FFMPEG
> post that discusses it in detail:
>

This C99 TC3 note you keep quoting doesn't guarantee that it will always
work, though, right?  The last sentence in the note reads:

"This might be a trap representation."

To me that means that you can't just trust it to always work, it might blow
up and is compiler-and-platform specific.  I don't think you have the
blessing of the C99 standards committee to cast-through-union whenever you
want and they promise it will be ok.

Plus I don't believe it's part of the C++03 standard, so even if gcc
implements it there's no guarantee that MSVC will (in C++ mode), if they
ever start exploiting TSAA-based optimizations by default.  (they don't
support C99 yet either).

-charles

 Finally, even CERT thinks its okay:
>
>
> https://www.securecoding.cert.org/confluence/download/attachments/26017980/SD+West+Dangerous+Optimizations.pdf?version=1
>
> See page 75. Which was written in 2009. I understand that is an argument
> based on an appeal to authority, but the assumption here is these four guys
> that wrote this understand good coding practices better than most. GCC holds
> C++ code to C99 standards, from what I read. So.... code that tried to
> optimize unions would be non-conforming not to mention break tons of legacy
> code in C and C++
>
>
>>
>> > if cast-through-union violates the standard, then why are unions in
>> > the language? isn't storing bytes and interpreting them as different
>> > types what unions are for?
>>
>> No, that's not what unions are for. Unions are there to allow
>> you to store different type data in the same memory location
>> at DIFFERENT (nonoverlapping) TIMES.
>>
>> Standard-violating aliasing is when you have different type
>> data in the same memory location at the SAME TIME.
>>
>> The standard disallows same-time different-type aliasing,
>> because disallowing it allows for a lot of optimization
>> opportunities. This is a GOOD THING -- except programmers
>> need to learn to write standard-conforming code (which is
>> also a GOOD THING).
>>
>>
>>
>
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco,
> CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the
> Enterprise
> -Strategies to boost innovation and cut costs with open source
> participation
> -Receive a $600 discount off the registration fee with the source code:
> SFAD
> http://p.sf.net/sfu/XcvMzF8H
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Jason H. <jas...@di...>]

So, how about a "standard friendly" version of Pal-Kristian's template 
from a few days ago:

template<typename T, typename U>
static T bit_cast(const U val)
{
    union { U u; T t; } bits = { val }, secondBits;
    secondBits = bits;
    return secondBits.t;
}

    float x = 3.1415926f;
    uint32 asUint = bit_cast<uint32>(x);

Wouldn't this satisfy the standard?  There's no situation when 
secondBits is accessed as two types, only as a union.

JH

Gino van den Bergen wrote:
> My bad. It's the C99 standard, not the C++98 standard.
>
> "The following are unspecified: ... The value of a union member other 
> than the last one stored into (6.2.6.1)."
>
> liam mail wrote:
>   
>> 2009/3/6 Gino van den Bergen <gin...@gm... 
>> <mailto:gin...@gm...>>
>>
>>     Aliasing is having multiple references to the same memory location. 
>>
>>  
>>
>>     "Call me reckless but I just do not believe that
>>     strict-aliasing on union fields will be exploited by a C++
>>     compiler any
>>     time soon."
>>
>> Thank you I know what aliasing is, but as I said I do not see what 
>> this has to do with your comment as the standard guarantees the same 
>> space is in use.
>>
>>
>>     According to the C++ standard a compiler would be allowed to fetch
>>     pun.i
>>     before pun.f has been written 
>>
>>  
>>
>>     and the result would contain garbage
>>     instead of the bit-representation of x. 
>>
>>
>> Would you mind quoting or pointing me to the part of the standard 
>> which implies this.
>>
>> Liam
>> ------------------------------------------------------------------------
>>
>> ------------------------------------------------------------------------------
>> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
>> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
>> -Strategies to boost innovation and cut costs with open source participation
>> -Receive a $600 discount off the registration fee with the source code: SFAD
>> http://p.sf.net/sfu/XcvMzF8H
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>     
>
>
> ------------------------------------------------------------------------------
> Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
> -OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
> -Strategies to boost innovation and cut costs with open source participation
> -Receive a $600 discount off the registration fee with the source code: SFAD
> http://p.sf.net/sfu/XcvMzF8H
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>   

Re: [Algorithms] How to get 3dvector largest coordinate index?

[Jim T. <jim...@gm...>]

It's sad to see that so many people have no knowledge of the C++
language, or even worse, disdain for that knowledge and taking the
attitude that it doesn't matter. Yes, the standard is pretty nasty,
long and full of language that takes way too long to interpret. But
it's *the* only source of authoritative answers to many of the
questions we can encounter while coding. It's like a workman who
doesn't like or want to understand his tools. Oh, wait -- it's exactly
like that.

Now don't get me wrong, I've by no means an expert at the language,
but I've tried to preach 3.10.15 over the years (I saw that Charles
beat me to it posting it). The very first reaction to the paragraph
should be to read it again. Here it is:

3.10.15:
If a program attempts to access the stored value of an object through
an lvalue of other than one of the following
types the behavior is undefined:
— the dynamic type of the object,
— a cv-qualified version of the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to the
dynamic type of the object,
— a type that is the signed or unsigned type corresponding to a
cv-qualified version of the dynamic type of
the object,
— an aggregate or union type that includes one of the aforementioned
types among its members (including,
recursively, a member of a subaggregate or contained union),
— a type that is a (possibly cv-qualified) base class type of the
dynamic type of the object,
— a char or unsigned char type.

Note the wording of the first sentence (read it again, how many of you
guys did read it the time Charles posted it? :). *Any other* access
than the ones listed are invalid (actually undefined behavior, which
in standard speak is run away and hide). Actually, Philip Taylor wrote
an earlier email explaining most of this in plain talk, read his post
again :) People try to get around this and read the following very
liberally, but it turns out that no, the way you can access memory is
very limited. The above can be summarize in short as:

"Only one type can ever live at one memory address at the same time"

Now, as many noted, char* are intentionally left there as a loophole.
You can always access things through a char* and it will be fine. But
you need to treat it as char, and not go around doing things like:

  float f;
  int* bad = (int*)(char*)(float*)&f; // this is bad.

If you want an integer representing your IEEE 754 number, you need to
do (assuming a long is 32 bits of course and endianess):

  float f;
  unsigned char* p = (unsigned char*)&f;
  long i = p[0] << 24 | p[1] << 16 | p[2] << 8 | p[3];

The union trick does not work. No really, it doesn't. It's undefined
behavior meaning that the compiler is free to do whatever it likes.
Even erase your hard drive or start tetris. It so happens that the gcc
guys usually doesn't want people to hunt them down and strangle them
so in this case they are trying to do the right thing, through turning
off most of the optimizations.

Another point to make is that the bit_cast that Pal mentioned (I think
it has been mentioned before as union_cast) has one terrible flaw
apart from the obvious that it's undefined since it uses the union
trick: it works by copying r-values. It can thus be abused like this:

  int* i = union_cast<float*>( &f );

Which will just yield the original error while optimizing since it
copies the r-value of the pointer, but not that of the value itself. I
think I saw this usage on the thread as well, stay away from it --
pain an misery will ensue.

Now some people question the need to actually bother with stuff like
this, and continue on casting like we programmed in C89. They will get
bitten by the decent compilers that does perform the most basic
optimizations. They will be very slow on in-order processor by nature
of the compiler having no chance to figure out aliasing. Aliasing btw
is the big reason why FORTRAN is 2x as fast as regular C89 in most of
the cases. Aliasing a large reason why C99 came about and why C++ has
the draconian rule 3.10.15.  There is a *reason* why this all matters
and that is speed.

Why would we bother with the whole union-type punning illegalities?
Because it breaks the standard! That's why we are in this whole mess
to start with, remember we broke the standard by casting float* to
int* and then using it? The proposed solution was a bug in the
compiler that could be exploited by using unions. It just seems
incredibly shortsighted to me, to go and break the same rule again and
then stick the head in the sand pretending that it's not a problem.
It's a fundamental problem with how we write code if we can not follow
something that's in the basics of the language (oh, god don't bring
templates into this if we can't even handle the basics like using
r-values and l-values).

Note that the TBAA (Type Based Alias Analysis) have been present in
gcc for a long time, it's only recently (ok, really not so recently)
that they decided to make it default in -O2, even though it would
break a lot of code. The fact that people think that they can break
the standard and be safe just because nobody will want to break their
code is just naive. Compiler vendors will "break" your code, and if
you turn around and complain I bet the answer will be "turn off
optimizations to fix it". Which I bet those people will not be willing
to do and then will turn to scramble to fix their code. Only, we are
talking about basic assumptions here. All the l-value accesses. Those
are a ton of accesses. It could potentially be a complete rewrite of a
major part of the codebase. That's what we've faced on the current
platforms and it just burned everybody badly. Why would you after this
advocate breaking the same rule again?

/j