[armedbear-devel] Patch with improvements to stable-sort and sort

[Jorge Tavares]

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sort-benchmarks.txt
Type: application/octet-stream
Size: 5530 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/armedbear-devel/attachments/20120211/9b1fab13/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: sort-improvement.diff
Type: application/octet-stream
Size: 13295 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/armedbear-devel/attachments/20120211/9b1fab13/attachment-0001.obj>