gdalgorithms-list

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

[Glenn F. <ga...@ga...>]

wow great post jim :)

On Fri, Mar 6, 2009 at 9:28 PM, Jim Tilander <jim...@gm...> wrote:

> 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
>
>
> ------------------------------------------------------------------------------
> 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?

[Matt P. <mat...@gm...>]

It seems to me that this thread has gone very far beyond any topics  
related to algorithms and is well into the realm of language  
lawyering.  Could I respectfully suggest that comp.std.c might be a  
better venue for it at this point?  They live for this stuff over there.

The (limited) algorithmic component of finding the largest component  
of a 3d vector has been well covered, especially insofar as no one has  
yet indicated that they have a measured situation where raw  
performance of this is a significant part of their computation.

(I personally understand and respect the value of understanding the  
definitions of the programming languages that one uses.  But that  
seems far from the charter of this list as I understand it.)

Sincerely,
-matt

On Mar 6, 2009, at 9:28 PM, Jim Tilander wrote:

> 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
>
> ------------------------------------------------------------------------------
> 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?

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

Unions are for variants (and trix are for kids!). They can be used to implement tagged variant types and even full algebraic data types (if you put a union inside of another construct), as well as the lower level uses (such as saving storage space, usually through some sort of implicit tagging).  

Cheers,
Conor



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

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?



      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?

[Anoop M. <cod...@gm...>]

It might be worth noting that gcc has a "may_alias" type attribute:

http://gcc.gnu.org/onlinedocs/gcc/Type-Attributes.html

Quoting the docs:

"Accesses through pointers to types with this attribute are not subject to
type-based alias analysis, but are instead assumed to be able to alias any
other type of objects. In the context of 6.5/7 an lvalue expression
dereferencing such a pointer is treated like having a character type. See
-fstrict-aliasing for more information on aliasing issues. This extension
exists to support some vector APIs, in which pointers to one vector type are
permitted to alias pointers to a different vector type."

Mike Acton has written a detailed article on the subject of type aliasing:

http://www.cellperformance.com/mike_acton/2006/06/understanding_strict_aliasing.html

Cheers,
Anoop.

On Wed, Mar 4, 2009 at 8:39 PM, Conor Stokes <
bor...@ya...> wrote:

> Unions are for variants (and trix are for kids!). They can be used to
> implement tagged variant types and even full algebraic data types (if you
> put a union inside of another construct), as well as the lower level uses
> (such as saving storage space, usually through some sort of implicit
> tagging).
>
> Cheers,
> Conor
>
> ------------------------------
> *From:* Jeff Russell <je...@8m...>
> *To:* Game Development Algorithms <gda...@li...
> >
> *Sent:* Thursday, 5 March, 2009 11:33:32 AM
> *Subject:* Re: [Algorithms] How to get 3dvector largest coordinate index?
>
> 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?
>
> ------------------------------
> Stay connected to the people that matter most with a smarter inbox. Take a
> look<http://au.rd.yahoo.com/galaxy/mail/tagline2/*http://au.docs.yahoo.com/mail/smarterinbox>
> .
>
>
> ------------------------------------------------------------------------------
> 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?

[Sylvain G. V. <vi...@ii...>]

And the LargerCoordinate version, using abs values:

unsigned int LargerCoordinate( const Vector3d &vf )
{
	const unsigned int SignMask = 0x80000000;
	const unsigned long *vi = (const unsigned long*)&vf.x;
	unsigned int x = vi[0] & ~SignMask;
	unsigned int y = vi[1] & ~SignMask;
	unsigned int z = vi[2] & ~SignMask;

#if 1
	unsigned int zx = (x-z)>>31;
	unsigned int zy = (y-z)>>31;
	unsigned int yx = (x-y)>>31;
	unsigned int yz = ~zy; // (z-y)>>31;
#else
	unsigned int zx = z>x;
	unsigned int zy = z>y;
	unsigned int yx = y>x;
	unsigned int yz = ~zy; // y>z;
#endif

	return ((zx & zy)<<1) | (yx&yz);
}



004010CC  mov         ecx,dword ptr [esp+34h] 
004010D0  mov         edx,dword ptr [esp+38h] 
004010D4  mov         eax,dword ptr [esp+3Ch] 
004010D8  and         edx,7FFFFFFFh 
004010DE  and         eax,7FFFFFFFh 
004010E3  and         ecx,7FFFFFFFh 
004010E9  mov         ebx,ecx 
004010EB  sub         ebx,eax 
004010ED  mov         edi,edx 
004010EF  sub         edi,eax 
004010F1  shr         edi,1Fh 
004010F4  shr         ebx,1Fh 
004010F7  and         edi,ebx 
004010F9  sub         eax,edx 
004010FB  add         edi,edi 
004010FD  shr         eax,1Fh 
00401100  sub         ecx,edx 
00401102  shr         ecx,1Fh 
00401105  and         eax,ecx 
00401107  or          edi,eax 
00401109  push        edi


From: Gino van den Bergen <gin...@gm...>
> I guess you're right (I'm referring to Marc Hernandez). Assigning 
> the 
> result of a float compare to a bool introduces a branch in VC8 as 
> well. 
> How about this trick then
> 
>   template <>
>   FORCEINLINE
>   int maxAxis(const Vector3<float>& v)
>   {
>       const int32_t* a = reinterpret_cast<const int32_t*>(&v[0]);
>       int c0 = a[0] < a[1];
>       int c1 = a[0] < a[2];
>       int c2 = a[1] < a[2];
>       return (c0 & ~c2) | ((c1 & c2) << 1);
>   }
> 
> If we take the binary values of the floats and do an integer 
> compare on 
> them the result should be equal to the float compare, that is, for 
> non-negative floats. I still have to check whether this will work 
> using 
> gcc version 4 and up, since I'm not sure if I'm breaking the 
> strict-aliasing rule here.
> 
> Gino
> 
> 
> Gino van den Bergen wrote:
> > I would like to share my approach. This code is copy-pasted 
> straight 
> > from my Vector3 class template so it may look a bit cluttered but 
> I 
> > hope the idea comes across:
> >
> >    template <typename Scalar>
> >    FORCEINLINE
> >    int maxAxis(const Vector3<Scalar>& a)
> >    {
> >        int c0 = a[0] < a[1];
> >        int c1 = a[0] < a[2];
> >        int c2 = a[1] < a[2];
> >        return (c0 & ~c2) | ((c1 & c2) << 1);
> >    }
> >
> >    template <typename Scalar>
> >    FORCEINLINE
> >    int minAxis(const Vector3<Scalar>& a)
> >    {
> >        int c0 = a[1] < a[0];
> >        int c1 = a[2] < a[0];
> >        int c2 = a[2] < a[1];
> >        return (c0 & ~c2) | ((c1 & c2) << 1);
> >    }
> >
> >    template <typename Scalar>
> >    FORCEINLINE
> >    int closestAxis(const Vector3<Scalar>& a)
> >    {
> >        return maxAxis(a * a);
> >    }
> >      template <typename Scalar>
> >    FORCEINLINE
> >    int furthestAxis(const Vector3<Scalar>& a)
> >    {
> >        return minAxis(a * a);
> >    }
> >
> > The function minAxis and maxAxis return  a value  0, 1, or 2, so 
> the 
> > result only needs two bits (00, 01, and 10 in base-2). The first 
> term 
> > of the "|" operator is bit-0 and the second term (the one with 
> the << 
> > 1) is bit-1. The nice thing about this approach is the fact that 
> its 
> > branchless. Three boolean values are computed but they are never 
> used 
> > to branch, so no code-cache misses can happen here.
> >
> > For finding the minimum of maximum *absolute* value I do not use 
> > "fabs" but I rather multiply the vector with itself, thus a * a  
> =  
> > (a.x  * a.x, a.y * a.y, a.z * a.z).  "closestAxis" returns the 
> world 
> > axis that is closest (as in most parallel) to vector "a". 
> > "furthestAxis" returns the most orthogonal world axis.
> >
> > Cheers,
> >
> > Gino
> >
> >  
> > Sylvain G. Vignaud wrote:
> >> Hi,
> >>
> >> I need to compute the index (not the actual value) of the largest
> >> coordinate of a normal, for some space hashing.
> >>
> >> I'm not sure how fast you guys usually find this index, but I've 
> just>> created the following trick which I think is quite fast:
> >>
> >>  
> >>> inline uint LargestCoordinate(const Vector3d &v)
> >>> {
> >>>     const float x = fabs(v.x);
> >>>     const float z = fabs(v.z);
> >>>     const float y = Maths::max( fabs(v.y), z );
> >>>     return uint(fabs(y)>fabs(x)) << uint(fabs(z)>=fabs(y));
> >>> }
> >>>     
> >>
> >> I didn't need such function before, so I'm not sure if this is
> >> considered fast or slow. Do you guys have something faster?
> >>
> >>
> >> -----------------------------------------------------------------
> ------------- 
> >>
> >> 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
>