Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Gevorg Voskanyan (v_gevorg_at_[hidden])
Date: 2008-12-16 08:03:09

Steven Ross wrote:

> On Mon, Dec 15, 2008 at 10:16 AM, Steven Watanabe wrote:
> 
> > AMDG
> >
> > Steven Ross wrote:
> >
> >> I encountered a compiler optimization bug with float_sort (but not
> >> integer_sort) on Cygwin with -O2 and -O3 options.  Does anyone know the
> >> best
> >> place to report that?  For now, I'm having float_sort call std::sort on
> >> Cygwin.
> >>
> >>
> >
> > I don't think this is a compiler bug.  The standard forbids
> > accessing floats as ints.
> >
> >
> That's a reasonable restriction for people who don't know what they're doing
> and higher-level languages, but to quickly radix sort a floating-point
> number requires treating it as an integer (or viewing its bits as one would
> an integer).  To avoid the casting restriction on the data type, I cast the
> pointer instead, then dereference it.
> Is there a better way to do this?
> Interestingly, I get a 5X speedup with -O1 optimizations for floating-point
> sorting on Cygwin vs. std::sort, so my algorithm should be quite useful on
> that platform, if I can get it to compile correctly.
> The actual problem appears to be y = x++ compiling as y = ++x, causing an
> incorrect memory access, based upon some printf statements I added in the
> area where it was crashing.  It's notable that putting a printf in the same
> scope as the increment causes the problem to dissappear, which strongly
> suggests along with the other evidence that there is some form of compiler
> bug.

This is not a compiler bug but a manifestation of undefined behavior. In general, you cannot access an object with an lvalue of different type than that it has been declared with. There are a few exceptions to this rule, listed in 3.10/15. Accessing a float through an int pointer does not fall under those exceptions, so you get undefined behavior.

> I've attached my latest source for reference.

I suggest modifying CastFloatIter() function to use memcpy for accessing floats as integers, as shown below:

WARNING: not tested!
<code>
//Casts a RandomAccessIter to the specified data type
template<class cast_type, class RandomAccessIter>
inline cast_type
CastFloatIter(const RandomAccessIter & floatiter)
{
    BOOST_STATIC_ASSERT( sizeof( cast_type ) == sizeof( *floatiter ) );
    cast_type dst;
    std::memcpy( &dst, &*floatiter, sizeof dst );
    return dst;
}
</code>

instead of
<code>
   return *((cast_type *)(&(*floatiter)));
</code>
which is not legal if e.g. cast_type is int and *floatiter is float.

HTH

Best Regards,
Gevorg