sorting floats by casting to integer

[Steven Ross-3]

On Mon, Jul 6, 2009 at 3:33 PM, Christopher Jefferson <chris@...
> wrote:

>
>> I still have a problem: what's a good floating-point benchmark?
>>
>
> Possibly a stupid thing to say -- rather than trying to massage bits like
> this, why not just generate floats directly, something like rand() *
> pow((float)10, rand()%20) for example?
>

So that all possible bit combinations can be exercised, making sure there is
no corner-case where sorting is incorrect.
My tests do these things at the same time:
1) Verify correctness (most important)
2) Benchmark performance
3) Identify weak points to be used for tuning or so the user can know when
not to use the algorithm as appropriate for their system.

Additionally, the tests and testcase generation need to run quickly so they
can be both accurate and finish in a reasonable amount of time.
I think the best way to do this is to generate semi-random bits, and for the
case of floats, to specifically eliminate denormalized numbers and NaNs.
Generating them the way you suggest may be better for goal #2, but worse for
#1.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Steven Ross-3]

On Mon, Jul 6, 2009 at 8:37 AM, Vladimir Prus <vladimir@...>wrote:

> > I'll test with SSE and other compiler settings next.  Is there an easy
> way
> > to add these with bjam?
>
> Because bjam is actually a low-level build engine, it is pretty much
> impossible
> to do anything with it at all. Boost.Build allows you to pass any flags
> to compiler you see fit, my previous post gives the actual syntax I have
> used.
>

Thanks for the suggestion.
I ended up passing those flags you suggested, and obtained this result:
cl : Command line warning D9002 : ignoring unknown option '-march=nocona'
cl : Command line warning D9002 : ignoring unknown option '-mfpmath=sse'

I've checked and my cheap version of MSVC 8.0 apparently doesn't support
sse.  So I can't benchmark with your recommended options, without spending
more money on a volunteer project.
With default release optimizations, all 3 of my algorithms are roughly twice
as fast as std::sort on randomized data.  I'm stripping out denorms from the
float tests because they skew results so much and aren't realistic data, and
my floating-point performance improvement dropped from fantastic to
reasonable.
I've tested string_sort on a Dickens novel and had comparable results to
random data, relative to std::sort (a little better than 2X faster).  For
now I'm using random bits for all my performance testing, which tends to
generate long strings and I admit doesn't seem to be realistic string data,
though it does test corner-cases.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Cory Nelson]

On Sun, Jul 26, 2009 at 4:06 PM, Steven Ross<spreadsort@...> wrote:

> On Mon, Jul 6, 2009 at 8:37 AM, Vladimir Prus <vladimir@...>wrote:
>
>> > I'll test with SSE and other compiler settings next.  Is there an easy
>> way
>> > to add these with bjam?
>>
>> Because bjam is actually a low-level build engine, it is pretty much
>> impossible
>> to do anything with it at all. Boost.Build allows you to pass any flags
>> to compiler you see fit, my previous post gives the actual syntax I have
>> used.
>>
>
> Thanks for the suggestion.
> I ended up passing those flags you suggested, and obtained this result:
> cl : Command line warning D9002 : ignoring unknown option '-march=nocona'
> cl : Command line warning D9002 : ignoring unknown option '-mfpmath=sse'

Those are for GCC.  For VC++, you want to use /arch:SSE2.

--
Cory Nelson
http://int64.org
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Steven Ross-3]

On Sun, Jul 26, 2009 at 5:22 PM, Cory Nelson <phrosty@...> wrote:

> > Thanks for the suggestion.
> > I ended up passing those flags you suggested, and obtained this result:
> > cl : Command line warning D9002 : ignoring unknown option '-march=nocona'
> > cl : Command line warning D9002 : ignoring unknown option '-mfpmath=sse'
>
> Those are for GCC.  For VC++, you want to use /arch:SSE2.
>

Thanks Cory.  There was no warning with that option specified, but  there
was also no measurable performance change.  I verified that MSVC was being
called with the option, and that if I misspelled the option, a warning was
issued.  I think that SSE is deliberately disabled in the cheap version of
MSVC I bought, based upon the Microsoft documentation.
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Bo Persson]

Steven Ross wrote:

> On Sun, Jul 26, 2009 at 5:22 PM, Cory Nelson <phrosty@...>
> wrote:
>
>>> Thanks for the suggestion.
>>> I ended up passing those flags you suggested, and obtained this
>>> result: cl : Command line warning D9002 : ignoring unknown option
>>> '-march=nocona' cl : Command line warning D9002 : ignoring
>>> unknown option '-mfpmath=sse'
>>
>> Those are for GCC.  For VC++, you want to use /arch:SSE2.
>>
>
> Thanks Cory.  There was no warning with that option specified, but
> there
> was also no measurable performance change.  I verified that MSVC
> was being called with the option, and that if I misspelled the
> option, a warning was issued.  I think that SSE is deliberately
> disabled in the cheap version of MSVC I bought, based upon the
> Microsoft documentation.

No they are not disabled, not even in the free Express edition.


Disabled optimizations was true for older free versions, producing bad
benchmarks all over the place. Someone learned from this!  :-)


Bo Persson



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost