AS3 sorting algorithm faster than native sorting

Jun 14, 2009   //   by Tuomas Artman   //  22 Comments

There have been a number of people blogging about creating AS3 sorting algorithms. Most have come to the conclusion that it’s not possible to create a faster sorting algorithm than the native one provided for Vectors. And who can blame them? It seems very unlikely that the Flash Player’s native algorithm would be slower than any interpreted AS3 algorithm.

Well, it turns out everybody was wrong, and sorting with an AS3 algorithm is indeed almost twice as fast as it’s native counterpart!

Consider the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
package
{
  import flash.display.Sprite;
  import flash.events.Event;
  import flash.utils.getTimer;

  public class Sorting extends Sprite {
    public function Sorting() {
      addEventListener(Event.ENTER_FRAME, loop);
    }

    private function loop(e:Event):void {
      var data:Vector.<number> = new Vector.<number>();
      for(var i:int = 0; i<10000; i++){
        data.push(Math.random()*10000);
      }

      var data2:Vector.<number> = data.concat();
      var t:Number = getTimer();
      data.sort(sf);
      trace("Native sort", (getTimer()-t));

      t = getTimer();
      data.sort(sf);
      trace("Native sort on ordered elements", (getTimer()-t));

      t = getTimer();
      shellSort(data2);
      trace("AS3 Shell sort", (getTimer()-t));

      t = getTimer();
      shellSort(data2);
      trace("AS3 Shell sort on ordered elements", (getTimer()-t));
    }

    final private function sf(a:Number, b:Number):int {
      return (a==b ? 0 : (a < b) ? -1 : 1);
    }

    final private function shellSort(data:Vector.<number>):void {
      var n:int = data.length;
      var inc:int = int(n/2 + 0.5);

      while(inc) {
        for(var i:int=inc; i<n; i++) {
          var temp:Number = data[i], j:int = i;
          while(j >= inc && data[int(j - inc)] > temp) {
            data[j] = data[int(j - inc)];
            j = int(j - inc);
          }
          data[j] = temp
        }
        inc = int(inc / 2.2 + 0.5);
      }
    }
  }
}

The class will simply run two native sorts to test the performance on a totally random unordered and ordered Vector.<Number> and then run two sorts on the same data with a pure AS3 implementation of Shell Sort.

Shell sort has a good worst case resolve speed and works quiet well even when the origin data is already sorted or almost sorted.

The results

On my iMac native sort on the Vector with 10.000 Numbers took an average of 50 milliseconds. When sorting the already sorted Vector again, it took an average of 38 milliseconds.

The AS3 algorithm took an average of 31 milliseconds to sort the random Vector and only 15 milliseconds to sort the sorted Vector. (Update: in debug mode!)

In real life where Vectors that need to be sorted are usually not totally random, you’ll get a two-fold increase in sorting speed compared to the native algorithm.

Some things to consider, though: Shell sorting in this example gives you a head start over the native sorting algorithm that the data to be sorted are primitives. If you wanted to sort Objects (typed objects of course) based on one of their properties shellSort would no longer outperform Flash Player’s native sort, as the speed is eaten up by those numerous object property look-ups. However even then it comes very close and in programs that often sort Vectors with objects that are already almost in the right order, you’ll beat the native sorter by 10-30%.

But there’s one great type of project where speeding up sorting of Numerical Vectors will increase application performance greatly and that’s 3D. I started to dig into these algorithms after my profiler told me that 25% of all of my CPU time was going into sorting 3D polygons. Only the drawing operation was slower, but not by much.

P.S. If you want even better performance, don’t just rely on a single sorting algorithm. QuickSort is 20 times faster than Shell Sort if the Vector is already sorted, but absolutely freaking slow if the Vector sorting order is random. In 3D scenes it might be a good idea to switch between these, using Shell sort for your initial render, the user quick sort if your model rotates only slightly and thus only a few poly’s are out of place.

Update: Erik correctly pointed out that I should test the sorting algorithm in the release player instead of the debug player in debug mode, as this might affect results. And indeed it did. It made Shell sorting became much faster. A vector with 100.000 random Numbers took:

Native sort: 338 ms

Native sort on ordered Vector: 245 ms

AS3 Shell sort: 98 ms

AS3 Shell sort on ordered Vector: 49 ms

Who would have thought that interpreted code can do the job 3-5 times more quickly than a native call.

Update: I forgot to mention the license of the source code. Consider it Public Domain.

Update 2: Doh. I ported the code too quickly. inc should have been rounded, not floored. Updated the code to work properly.

22 Comments

  • Hm… That’s very surprising results. You should try with differing amounts in the for loop. Maybe even graph from n=2 to n=100000.

  • Eskil Steenburg (Creator of Love) on Sorting with relation to 3D Graphics:
    I never sort. My feeling is that if you store your data properly you almost never have to sort it. In graphics you often need to sort objects back-to-front and front-to-back and what i do is that i keep a sorted list of all objects and for each frame i do a single pass of bubble sort. I simply check is this object closer to the camera then the last, if they are i switch their places.

  • You never sort? Lucky guy.

  • Danny, the same performance multiplier holds true no matter how long the sortable array is.

  • Did you test this in the release player as well? The debug player is not allways a good indicator for performance tests.

  • Erik, good point, I always forget this. I’ll have to try it out once I get back to my machine. My guess is that the AS3 variant will work even faster on the release player, as there’s less debugger overhead.

  • It’s amaze, if is the while circulation

  • A sidenote: ++i is faster than i++
    Also, _very_ impressive. Can we use it?

  • Yeah, sure, go ahead an use it wherever you like. Indeed, I forgot to mention the license of the source. It’s Public Domain.

  • Thanks!

  • Adobe did everything wrong. EVERYTHING. If I try to code the Flash core as bad as they did, it will still be faster. -.-

  • Native sort 979
    Native sort on ordered elements 613
    AS3 Shell sort 5538
    AS3 Shell sort on ordered elements 2654

    got this result with arrays

  • Well yeah, arrays are slow as hell as the Player needs to do a type check for every access, so you are better of using native sort there. On the other hand if you need toss sort stuff, just go with vectors.

  • so amazing.The complier is so ……bad

  • The Array.sort method takes 9ms when passed the Array.NUMERIC value.
    Nothing can beat that.

  • I was curious to see what the difference in performance would be if I modified the shell sort function to operate on a property of an object, so I can sort vectors of non-primitives. My takeaway was that the shell sort is faster on vectors of Number or other primitive types, but slower if you want to sort different types of objects. Anyway I’d love for someone to prove me wrong on this.

    Very cool article, thanks for sharing.

  • Hey i know it’s an old post, however since it’s easy to find it on google i would like to clarify something :

    What cost a lot of time on the native sort is the call to your compareFunction.

    Unfortunately the sort function of the Vector doesn’t have the same property than the sort function of Array, by using the array sort function (with Array.numeric) you get a lot more performance, even if you have to convert your vector to array and reconvert it to vector after.

  • Shell sort is faster than Vector.sort in my tests too, but slower in my tests than the native Array.sort

    But here a much faster sorting, flashSort which is 4 times faster than the Array.sort, and much faster than the Shell sort !
    http://guihaire.com/code/?p=552

  • Wow, wonderful blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is excellent, as well as the content!. Thanks For Your article about AS3 sorting algorithm faster than native sorting Tuomas Artman & .

  • Wow, fantastic blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is great, as well as the content!. Thanks For Your article about AS3 sorting algorithm faster than native sorting Tuomas Artman & .

  • Wow, superb blog layout! How long have you been blogging for? you make blogging look easy. The overall look of your web site is wonderful, let alone the content!. Thanks For Your article about AS3 sorting algorithm faster than native sorting Tuomas Artman & .

Leave a comment