[armedbear-ticket] [armedbear] #196: STABLE-SORT is only stable for lists

[armedbear]

#196: STABLE-SORT is only stable for lists
--------------------------+-------------------------------------------------
  Reporter:  mevenson     |       Owner:  ehuelsmann      
      Type:  defect       |      Status:  reopened        
  Priority:  blocker      |   Milestone:  1.1.0           
 Component:  interpreter  |     Version:  1.0.1           
Resolution:               |    Keywords:  ansi-conformance
--------------------------+-------------------------------------------------

Comment(by mevenson):

 (In [13870]) See #196: further patch for STABLE-SORT from Jorge Tavares.

 easye: still seeing the ANSI failures, but this is a much more
 plausible "final" implementation with the appropiate optimizations
 which should be easier to fix modulo the possible hairy macro
 debugging part.  But that's why they call it trunk, right?

 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 t he
 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.

 [1]: http://article.gmane.org/gmane.lisp.armedbear.devel/2220

-- 
Ticket URL: <http://trac.common-lisp.net/armedbear/ticket/196#comment:3>
armedbear <http://common-lisp.net/project/armedbear>
armedbear