Hi, It seems that scipy_core (0.9.0.1713) is far more slower than numarray (1.5.0) when sorting arrays: In [43]: t5=timeit.Timer('a=sc.empty(shape=10000);a.sort()', 'import scipy.base as sc') In [44]: t5.repeat(3,100) Out[44]: [0.40603208541870117, 0.41605615615844727, 0.39800286293029785] In [45]: t4=timeit.Timer('a=na.array(None, shape=10000);a.sort()', 'import numarray as na') In [46]: t4.repeat(3,100) Out[46]: [0.090479135513305664, 0.086208105087280273, 0.086167097091674805] i.e. numarray is roughly 5x faster than scipy_core. As PyTables uses extensively this kind of sorting for indexing, it would be nice to see scipy_core with at least the speed of numarray in this sense. Nevertheless, as this only affects to the array package in the core, and there are no plans to migrate to scipy_core anytime soon, this is not a high priority for me. Just wanted to point it out. Thanks, --
0,0< Francesc Altet http://www.carabos.com/ V V Cárabos Coop. V. Enjoy Data "-"
Francesc Altet wrote:
Hi,
It seems that scipy_core (0.9.0.1713) is far more slower than numarray (1.5.0) when sorting arrays:
In [43]: t5=timeit.Timer('a=sc.empty(shape=10000);a.sort()', 'import scipy.base as sc')
In [44]: t5.repeat(3,100) Out[44]: [0.40603208541870117, 0.41605615615844727, 0.39800286293029785]
In [45]: t4=timeit.Timer('a=na.array(None, shape=10000);a.sort()', 'import numarray as na')
In [46]: t4.repeat(3,100) Out[46]: [0.090479135513305664, 0.086208105087280273, 0.086167097091674805]
i.e. numarray is roughly 5x faster than scipy_core.
There are many sorting algorithms in numarray. I'm not sure which one is being used regularly, but I'd like to see them brought over, though, which shouldn't be too big of a deal and is on the radar. Another opportunity for someone to get their hands dirty.... -Travis
Travis Oliphant wrote:
There are many sorting algorithms in numarray. I'm not sure which one is being used regularly, but I'd like to see them brought over, though, which shouldn't be too big of a deal and is on the radar.
It may be worth noting that the sort code in python's core, for somelist.sort(), is to my understanding, state of the art. Tim Peters a while ago (py2.2, I think) brought the full weight of his considerable algorithmic talent to bear on this problem, as well as some recent academic results. I don't know how this compares to what numarray uses, but it may be worth investigating/copying. If Tim's work is as good as it is claimed to be (and I have much respect for his claims), it might be a good idea to use a stripped version of his code which doesn't have to deal with the generalities of python lists (and all the per-item typechecking needed there). Just an idea... Best, f
Fernando Perez wrote:
Travis Oliphant wrote:
There are many sorting algorithms in numarray. I'm not sure which one is being used regularly, but I'd like to see them brought over, though, which shouldn't be too big of a deal and is on the radar.
It may be worth noting that the sort code in python's core, for somelist.sort(), is to my understanding, state of the art. Tim Peters a while ago (py2.2, I think) brought the full weight of his considerable algorithmic talent to bear on this problem, as well as some recent academic results. I don't know how this compares to what numarray uses, but it may be worth investigating/copying.
If Tim's work is as good as it is claimed to be (and I have much respect for his claims), it might be a good idea to use a stripped version of his code which doesn't have to deal with the generalities of python lists (and all the per-item typechecking needed there).
Thanks for the suggestions. This sounds good. The only possible drawback is that timsort (as he calls it --- a modified mergesort) requires temporary storage on the order of N//2 * sizeof(basic_element). So, I could see it being a choice to consider when more sorting algorithms are added. It's also more complicated to grab his sorting algorithm then the nicely laid out numarray versions :-) Definitely something to think about. Anybody want a fun project :-) -Travis
On 12/30/05, Fernando Perez <Fernando.Perez@colorado.edu> wrote:
Travis Oliphant wrote:
There are many sorting algorithms in numarray. I'm not sure which one is being used regularly, but I'd like to see them brought over, though, which shouldn't be too big of a deal and is on the radar.
It may be worth noting that the sort code in python's core, for somelist.sort(), is to my understanding, state of the art. Tim Peters a while ago (py2.2, I think) brought the full weight of his considerable algorithmic talent to bear on this problem, as well as some recent academic results. I don't know how this compares to what numarray uses, but it may be worth investigating/copying.
If Tim's work is as good as it is claimed to be (and I have much respect for his claims), it might be a good idea to use a stripped version of his code which doesn't have to deal with the generalities of python lists (and all the per-item typechecking needed there).
My (limited) understanding is that timsort is specifically optimized for sorting Python lists as they are generally used. Thus, compare operations are minimized because comparison operations are potentially expensive for general Python objects where they are relatively very cheap for numeric arrays. Also, timsort scans for runs, so sorting a list that is entirely sorted except for the last item is quite fast. Since one can append to lists, this is very useful for lists, but one cannot append to arrays so it would be less useful to us. The benefits of adopting timsort are probably less than they were for Python lists. -- Robert Kern robert.kern@gmail.com
Robert Kern wrote:
My (limited) understanding is that timsort is specifically optimized for sorting Python lists as they are generally used. Thus, compare operations are minimized because comparison operations are potentially expensive for general Python objects where they are relatively very cheap for numeric arrays. Also, timsort scans for runs, so sorting a list that is entirely sorted except for the last item is quite fast. Since one can append to lists, this is very useful for lists, but one cannot append to arrays so it would be less useful to us. The benefits of adopting timsort are probably less than they were for Python lists.
That was my impression as well after looking at the code for a bit. I've moved on. -Travis
Francesc Altet wrote:
Hi,
It seems that scipy_core (0.9.0.1713) is far more slower than numarray (1.5.0) when sorting arrays:
In [43]: t5=timeit.Timer('a=sc.empty(shape=10000);a.sort()', 'import scipy.base as sc')
In [44]: t5.repeat(3,100) Out[44]: [0.40603208541870117, 0.41605615615844727, 0.39800286293029785]
In [45]: t4=timeit.Timer('a=na.array(None, shape=10000);a.sort()', 'import numarray as na')
In [46]: t4.repeat(3,100) Out[46]: [0.090479135513305664, 0.086208105087280273, 0.086167097091674805]
i.e. numarray is roughly 5x faster than scipy_core.
Scipy core is still using the old Numeric algorithm for sorting which uses the generic qsort function and the compare function pointer. It looks like numarray is in-lining the sorting algorithm (and the argsort) for each data-type. I suspect this could be the source of the impressive speed-up. What do others think? Also, numarray has at least three different sorting algorithms (quicksort, heapsort, and mergesort). These could certainly be brought over fairly easily. Initially, I think I will try in-lining the quicksort algorithm for each data-type similar to numarray. Thoughts? -Travis
On Fri, 30 Dec 2005, Francesc Altet apparently wrote:
numarray is roughly 5x faster than scipy_core
On my computer, it seems almost all that difference is due to the time difference in initializing the arrays. (I.e., much of it disappears if I put the array creation in the setup statement.) fwiw, Alan
Alan G Isaac wrote:
On Fri, 30 Dec 2005, Francesc Altet apparently wrote:
numarray is roughly 5x faster than scipy_core
On my computer, it seems almost all that difference is due to the time difference in initializing the arrays. (I.e., much of it disappears if I put the array creation in the setup statement.)
Could you show your results. This is surprising. -Travis
Alan G Isaac wrote:
On my computer, it seems almost all that difference is due to the time difference in initializing the arrays. (I.e., much of it disappears if I put the array creation in the setup statement.)
Sorry; that was overstated. (I compared against Fransesco's results.) Here's the proper comparison. At least, I thought it was revealing ... Am I misinterpreting it? Alan Isaac ########### script ################ t1=timeit.Timer('a=sc.empty(shape=10000);a.sort()', 'import scipy.base as sc') print "Scipy with initialization", min(t1.repeat(30,100)) t2=timeit.Timer('a=na.array(None, shape=10000);a.sort()', 'import numarray as na') print "numarray with initialization", min(t2.repeat(30,100)) t3=timeit.Timer('a.sort()', 'import scipy.base as sc;a=sc.empty(shape=10000)') print "Scipy without initialization", min(t3.repeat(30,100)) t4=timeit.Timer('a.sort()', 'import numarray as na;a=na.array(None, shape=10000)') print "numarray without initialization", min(t4.repeat(30,100)) ########### output ################ Scipy with initialization 0.300570603247 numarray with initialization 0.177719793996 Scipy without initialization 0.215004420953 numarray without initialization 0.150071587311
Alan G Isaac wrote:
On Fri, 30 Dec 2005, Francesc Altet apparently wrote:
numarray is roughly 5x faster than scipy_core
On my computer, it seems almost all that difference is due to the time difference in initializing the arrays. (I.e., much of it disappears if I put the array creation in the setup statement.)
Hmm... This is strange to me. Look at my times for array creation...
t4 = timeit.Timer('res = na.array(None,shape=10000)','import numarray as na') t5 = timeit.Timer('res = sc.empty(shape=10000)','import scipy as sc')
t5.repeat(5,10000) [0.1860051155090332, 0.13622808456420898, 0.12397193908691406, 0.13260793685913086, 0.13042497634887695]
t4.repeat(5,10000) [1.9458281993865967, 1.9462640285491943, 1.8813719749450684, 1.8477518558502197, 1.8829448223114014]
Which seems to indicate that scipy is about 10x faster at array creation. But, in this instance the sorting is way more time consuming than array creation and so the improved numarray sort-times are holding sway. On my system for pure sorting (with new SVN which does in-place sorting --- but still the old way using generic sort algorithm with compare function pointers) I get that numarray (with it's data-type specific sorting) is about 3x faster in this case:
t1 = timeit.Timer('a.sort()', 'import numarray as na; a = na.array(None,shape=10000)') t2 = timeit.Timer('a.sort()', 'import scipy as sc; a = sc.empty(shape=10000)') t1.repeat(3,100) [0.26560115814208984, 0.25392889976501465, 0.25759387016296387] t2.repeat(3,100) [0.66517782211303711, 0.6185309886932373, 0.65760207176208496]
It could be that the 5x numbers were due to the copying of information over to a new array. But still, I think 3x leaves room for improvement which no doubt specific (rather than generic) sorting algorithms would provide. -Travis
Travis Oliphant wrote:
t1 = timeit.Timer('a.sort()', 'import numarray as na; a = na.array(None,shape=10000)') t2 = timeit.Timer('a.sort()', 'import scipy as sc; a = sc.empty(shape=10000)') t1.repeat(3,100) [0.26560115814208984, 0.25392889976501465, 0.25759387016296387] t2.repeat(3,100) [0.66517782211303711, 0.6185309886932373, 0.65760207176208496]
It could be that the 5x numbers were due to the copying of information over to a new array. But still, I think 3x leaves room for improvement which no doubt specific (rather than generic) sorting algorithms would provide.
In the fixsort branch I've added the necessary tools to fix sort and argsort incrementally. This means that there is a generic sort in-place which will be called and works if the compare method is defined. However, there are hooks for adding new sorting functions and if this type-specific sort is found it is called. I just tested this on the example Francesc gave and the type-specific sorting function matches the speed of numarray. It will not be difficult to add more type-specific sorting functions. -Travis
Try this little experiment, though to see numarray performance on sorting N-d arrays:
t1 = timeit.Timer('a = empty(shape=(100,100));a.sort(0)','from scipy import empty') t2 = timeit.Timer('a = array(None,shape=(100,100));a.sort(0)','from numarray import array') t1.repeat(3,100) t2.rep[0.58475184440612793, 0.63138318061828613, 0.61224198341369629] t2.repeat(3,100) [3.3455381393432617, 3.2438080310821533, 3.2775850296020508] import scipy.base._sort t1.repeat(3,100) [0.26787090301513672, 0.21700596809387207, 0.21253395080566406]
The last one changes to a type-specific sort for int32 arrays, leading to about a 3x speed up. This is sorting over the first axis. So, it looks like even without changing the sorting, for Nd arrays sorting is much faster in scipy_core. If we improve to type-specific sorting, then the sorting is much, much faster in scipy_core. -Travis
I've checked in sorting improvements to scipy_core SVN. I've also added a benchmarks directory for storing little benchmark programs. The attached program is already there. It's output for me is: 1-D length = 10000 Numarray: [0.26125383377075195, 0.26763486862182617, 0.25728297233581543] SciPy: [0.22897696495056152, 0.2154390811920166, 0.2216179370880127] Numeric: [0.3624110221862793, 0.37320113182067871, 0.3526921272277832] 2-D shape = (100,100), last-axis Numarray: [1.013077974319458, 0.93102908134460449, 1.0637660026550293] SciPy: [0.15087985992431641, 0.094407081604003906, 0.093811988830566406] Numeric: [0.29771900177001953, 0.23210597038269043, 0.22986793518066406] 2-D shape = (100,100), first-axis Numarray: [3.3508830070495605, 4.4938950538635254, 3.2825040817260742] SciPy: [0.25642704963684082, 0.18298697471618652, 0.18323087692260742] Numeric: [0.3815300464630127, 0.30514788627624512, 0.31459379196166992] I think scipy is sorting faster now.... -Travis
A Dissabte 31 Desembre 2005 05:06, Travis Oliphant va escriure:
I've checked in sorting improvements to scipy_core SVN.
Wow! my numbers: In [60]: t1 = timeit.Timer('a=array(None,shape=10000);a.sort()','from numarray import array') In [61]: t1.repeat(3,1000) Out[61]: [0.63181209564208984, 0.60971593856811523, 0.61994194984436035] In [62]: t2 = timeit.Timer('a=empty(shape=10000);a.sort()','from scipy.base import empty') In [63]: t2.repeat(3,1000) Out[63]: [0.55068111419677734, 0.52086997032165527, 0.52183318138122559] So, I can reproduce this also: scipy_core is more than 10% faster now :-) But, interestingly enough: In [65]: t3 = timeit.Timer('a=array(None,shape=10000);a.argsort()','from numarray import array') In [66]: t3.repeat(3,1000) Out[66]: [1.2611861228942871, 1.2791898250579834, 1.2521131038665771] In [67]: t4 = timeit.Timer('a=empty(shape=10000);a.argsort()','from scipy.base import empty') In [68]: t4.repeat(3,1000) Out[68]: [0.77948904037475586, 0.76528811454772949, 0.81097602844238281] so, argsort() is more than 60% faster in scipy_core than numarray. Awesome! And argsort() is what PyTables actually use for create indexes. Thank you very much not only for your responsiveness, but also for the gorgeous quality of your work. I think I'll have to adhere to the long list willing to buy your book, Travis ;-) --
0,0< Francesc Altet http://www.carabos.com/ V V Cárabos Coop. V. Enjoy Data "-"
participants (5)
-
Alan G Isaac -
Fernando Perez -
Francesc Altet -
Robert Kern -
Travis Oliphant