[armedbear-devel] Patch with improvements to stable-sort and sort
Hi, I send in attach a patch with further improvements to sort and stable-sort for sequences other than lists. In short, the patch includes a merge sort for vectors. To allow different types I've written the algorithm using macros and these generate the appropriate code according to the vector type. This way the algorithm is in a single place avoiding duplication of code. The macros also take care of the situation of when no key is present, avoiding the use of unnecessary funcalls. The quicksort algorithm was also refactored in the same way. I've tested the algorithms and they seem to be working correct. Stable sort is now considerably faster since the fix before converted the sequences to a list and used the sort-list function. I've made some benchmarking to verify how fast is sort and stable-sort. The tables with the results are also in a file sent in attach [1]. For stable-sort I've compare the current trunk version with the patched one while for sort I've compared 1.0.1, the trunk and with the patch. For unsorted vectors sort has a speed up of 7.5 from 1.0.1 and this considers only vectors of size 8 to 8192 (1.0.1 hits the worst-case quite fast). For stable-sort the speed up is around 90.2 from vectors of size 8 to 32768. The sort functions become even faster for the nearly sorted vectors. I think the tables clearly show the speed-ups :-) Naturally these benchmarks cannot be used to draw definite conclusions since they lack rigorous testing but I think they can provide some indications. With this patch, I think ABCL gets good performant sorting functions, especially for large vectors. As for lists, I haven't looked at them so probably they can also be improved (but I really don't know). Cheers, Jorge [1] The tables result from the generation of simple-vectors of sizes 8 to 524288 (powers of 2 from 3 to 19) with distinct integer: unsorted, nearly sorted (distances 0, 4 and 16), sorted and reversed sorted. The nearly sorted vectors were constructed by selecting pairs where they would swap with a neighbor at a certain distance. I did 100 runs and timed only the sorting operation. The tables contain the averages of the 100 runs. They were performed in an iMac (2.5GHz i5, 4GB) with Mac OS X 10.7.3. -- http://jorgetavares.com
On 2/11/12 11:04 AM, Jorge Tavares wrote:
I send in attach a patch with further improvements to sort and stable-sort for sequences other than lists. In short, the patch includes a merge sort for vectors. To allow different types I've written the algorithm using macros and these generate the appropriate code according to the vector type. This way the algorithm is in a single place avoiding duplication of code. The macros also take care of the situation of when no key is present, avoiding the use of unnecessary funcalls. The quicksort algorithm was also refactored in the same way.
I've tested the algorithms and they seem to be working correctly
[…] As noted earlier, while Jorge's patches mostly seemed to work, they cause failures in the ANSI tests which invoked CL:STABLE-SORT on a BIT-VECTOR or a STRING. After a bit of delving into the macrology to obtain a minimum understanding of what was going on, I was able to to kludge together [r13931][1] which now relaxes the type used for sequences as VECTOR rather than SIMPLE-VECTOR. Although I suspect that such a distinction is not really used at the present time by our compiler, it is a bit of a shame to lose information that could potentially be useful in the future, but I don't think I will make further useful progress on this issue at the present time so I have closed [ticket #196][2]. [1]: http://trac.common-lisp.net/armedbear/changeset/13931 [2]: http://trac.common-lisp.net/armedbear/ticket/196 Those whose macro-fu is better than mine are invited to submit a less kludgey fix.
Hi Mark, On Sunday, May 6, 2012 at 15:45 , Mark Evenson wrote:
As noted earlier, while Jorge's patches mostly seemed to work, they cause failures in the ANSI tests which invoked CL:STABLE-SORT on a BIT-VECTOR or a STRING. After a bit of delving into the macrology to obtain a minimum understanding of what was going on, I was able to to kludge together [r13931][1] which now relaxes the type used for sequences as VECTOR rather than SIMPLE-VECTOR. Although I suspect that such a distinction is not really used at the present time by our compiler, it is a bit of a shame to lose information that could potentially be useful in the future, but I don't think I will make further useful progress on this issue at the present time so I have closed [ticket #196][2].
[1]: http://trac.common-lisp.net/armedbear/changeset/13931 [2]: http://trac.common-lisp.net/armedbear/ticket/196
Those whose macro-fu is better than mine are invited to submit a less kludgey fix.
I missed those tests and I'm sorry for that! I will try and review the code and see if I can come up with a solution. I'm busy at the moment so it won't be immediately but I will look into this. Jorge -- http://jorgetavares.com
participants (2)
-
Jorge Tavares -
Mark Evenson