[Numpy-discussion] String sort

[Francesc Altet]

A Wednesday 13 February 2008, Charles R Harris escrigué:
> On Feb 13, 2008 10:56 AM, Francesc Altet <faltet at carabos.com> wrote:
> > Be warned, I'd like to stress out that these are my figures for my
> > _own laptop_.  It would be nice if you can verify all of this with
> > other achitectures (your Core2 machine seems different enough).  I
> > can run the benchmarks on Windows (installed in the same laptop)
> > too.  Tell me if you are interested on me doing this.
>
> Its easy enough to test if you compile from svn, just add your new
> copy function and change the name in this line:
>
>    #copy=copy_string, copy_ucs4#
>
> to use your function instead of copy_string.

I've spoken too fast.  I've never compiled NumPy on Windows before, and 
had problems when trying to compile it using MSVC 7.1 and a recent copy 
of the repository.  Well, in any case, I've exercised the Opteron 
platform, using gcc 4.1.3 (i.e. the one that can optimize newqsort 
correctly), and this brings new light to our study.

From the plot (attached), it can be drawn the next conclusions:

1) copy_string2 (the combination of manual copy and memcpy) is not 
better than memcpy for *any* value of the string length in our Opteron 
platform.  Also, the improvements with Pentium4 was not that big 
(<20%).  In consequence, I'd choose to always use memcpy and discard 
copy_string2.

2) Curiously enough, the indirect sort in Opterons is *always* faster 
than newqsort+memcpy.  For large values of string lengths (> 256), the 
speed-up can be up to 3x, which is a lot.  And I'd say that this keeps 
true also for most modern processors (read Core2, Barcelona).  For older 
processors (Pentium4), the indirect method can be slower than direct 
plot for small lengths, but by a very few extent (<10%).

Conclusion 2 makes me wonder if it wouldn't be useful the introduction 
of a new flag in sort, like:

"""
`indirect` - Use the indirect method for sorting.  This requires more 
memory (4/8 bytes per array element), but for sorting arrays of strings 
it is almost always faster than the direct approach (default). Beware: 
this is not the case when using numerical values, where the use of this 
method for sorting is not recommendable.
"""

Agreed, that could introduce some confusion, but as this flag would 
be 'False' by default, not many people should bother about its 
existence, and can definitely help to people who cares about sorting 
string performance.

Cheers,

-- 
>0,0<   Francesc Altet     http://www.carabos.com/
V   V   Cárabos Coop. V.   Enjoy Data
 "-"

-------------------------------------------------------

-- 
>0,0<   Francesc Altet     http://www.carabos.com/
V   V   Cárabos Coop. V.   Enjoy Data
 "-"
-------------- next part --------------
A non-text attachment was scrubbed...
Name: suse-opteron-newqsort.pdf
Type: application/pdf
Size: 20365 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20080214/19717ac1/attachment.pdf>