Re: benchmarks - sort

[David Bateman]

Hi Paul,

> For the indexed case, maybe you could create a vector
> of pointers to doubles.  That leads to an extra dereference
> in the code which will surely slow things down a bit, but it
> keeps the size of data you are shifting down to a word.
> You can recover the index by pointer subtraction.

Ok, I got this going the results are

Before
------
Test of the sorting function (merge_ieee754) with indexing

    \  N  |1.00e+02  1.00e+03  1.00e+04  1.00e+05  1.00e+06  
Test \    |
*sort     |5.86e-05  7.81e-04  8.33e-03  1.19e-01  1.45e+00  
\sort     |1.83e-05  1.78e-04  1.89e-03  3.18e-02  3.60e-01  
/sort     |1.72e-05  1.61e-04  1.77e-03  2.64e-02  3.05e-01  
3sort     |3.09e-05  1.86e-04  1.82e-03  3.04e-02  3.57e-01  
+sort     |2.28e-05  1.76e-04  2.19e-03  3.52e-02  4.13e-01  
=sort     |1.72e-05  1.62e-04  1.76e-03  2.70e-02  3.02e-01  

 Normalized times against Matlab

    \  N  |1.00e+02  1.00e+03  1.00e+04  1.00e+05  1.00e+06  
Test \    |
*sort     |2.47e+00  2.59e+00  2.25e+00  2.07e+00  1.73e+00  
\sort     |1.13e+00  9.57e-01  8.42e-01  9.98e-01  8.72e-01  
/sort     |1.23e+00  9.92e-01  8.79e-01  9.34e-01  8.43e-01  
3sort     |2.05e+00  1.14e+00  9.11e-01  1.08e+00  9.91e-01  
+sort     |1.09e+00  7.23e-01  7.49e-01  8.42e-01  7.38e-01  
=sort     |8.82e-01  6.19e-01  4.80e-01  5.27e-01  4.51e-01  

After
-----
Test of the sorting function (merge_ieee754) with indexing

    \  N  |1.00e+02  1.00e+03  1.00e+04  1.00e+05  1.00e+06  
Test \    |
*sort     |4.05e-05  5.31e-04  6.25e-03  8.94e-02  1.36e+00  
\sort     |1.76e-05  1.68e-04  1.86e-03  3.31e-02  3.60e-01  
/sort     |1.75e-05  1.68e-04  1.83e-03  2.97e-02  3.23e-01  
3sort     |2.60e-05  1.80e-04  1.90e-03  3.10e-02  3.52e-01  
+sort     |2.18e-05  1.77e-04  2.12e-03  3.54e-02  3.73e-01  
=sort     |1.73e-05  1.70e-04  1.86e-03  2.92e-02  3.28e-01  

 Normalized times against Matlab

    \  N  |1.00e+02  1.00e+03  1.00e+04  1.00e+05  1.00e+06  
Test \    |
*sort     |1.71e+00  1.76e+00  1.68e+00  1.55e+00  1.62e+00  
\sort     |1.09e+00  9.03e-01  8.32e-01  1.04e+00  8.72e-01  
/sort     |1.25e+00  1.04e+00  9.12e-01  1.05e+00  8.91e-01  
3sort     |1.72e+00  1.11e+00  9.52e-01  1.10e+00  9.79e-01  
+sort     |1.04e+00  7.28e-01  7.27e-01  8.47e-01  6.67e-01  
=sort     |8.87e-01  6.49e-01  5.06e-01  5.69e-01  4.89e-01  


It is significantly faster for random data, and about the same
for ordered data. This seems normal since we aren't limited by
the data movement in the partially ordered cases. I had to 
do the compares in a fucntion which itself added an overhead,
I'll see if I get get rid of this as well.....

This code is starting to look good...

Cheers
David

-- 
David Bateman                                address@hidden
Motorola CRM                                 +33 1 69 35 48 04 (Ph) 
Parc Les Algorithmes, Commune de St Aubin    +33 1 69 35 77 01 (Fax) 
91193 Gif-Sur-Yvette FRANCE

The information contained in this communication has been classified as: 

[x] General Business Information 
[ ] Motorola Internal Use Only 
[ ] Motorola Confidential Proprietary