JacksonDunstan.com

Comments

• #1 by Vic on February 28th, 2011 · Reply

  I love you man.

• #2 by Elliot Chong on February 28th, 2011 · Reply

  Great insights, thank you for compiling such an extensive benchmark!

• #3 by skyboy on February 28th, 2011 · Reply

  The isNaN speed up seems like a bit of fowl play to me, if function calls can be so fast they execute in the same amount of time as !=, then why don’t all function calls execute this fast? However, the conditionals and as speedups are nice to see.
  Though in the last couple days I’ve split off DenseMap’s sorting routines into a new class with a couple generic-ized versions that can sort any Object that has numeric indexes and a length property as an alternative for Array::sortOn. While normally slower when randomly sorted with no null values, pre-sorted is often the same or faster on machines with smaller cache sizes. The larger the cache, the better Adobe’s method performs, while the opposite is true for my code; So odd how they’re different.
  However, Adobe’s method takes major performance hits when you introduce null (and possibly all the same number elements) elements, getting as far as performing at O(n^2) (which can take up to several hours to complete, locking flash player at the same time) while my method performs at O(n log n).

  As an example to reinforce how bad it is:

    Windows XP x86 10.2.152.26(VM: 1.4 cyclone) Release PlugIn
  // 500000 elements each.
  create (1 operations): 716 ms
  sortOn (1 operations): 1515 ms Array / 1357 ms Array / 1650 ms Object / 1686 ms Dictionary / 1404 ms Vector
  sortOn (1 operations): 855 ms Array / 690 ms Array / 686 ms Object / 711 ms Dictionary / 656 ms Vector
  
  // code:
  for (i = 0; i < SIZE; ++i) (vec[i] = dic[i] = obj[i] = arr[i] = new Object)[SORT_ON_PROP_NAME] = ((j = (i * 9301 + 49297) % 233280) < 20000 ? (null) : j);

  The first result for Array is the sortOn method, and the remaining tests are a call to fastSort; which doubles as both sortOn and sort based on the second parameter’s type.

  • #4 by jackson on February 28th, 2011 · Reply

    I too thought it a little fishy how fast isNaN runs now. Perhaps I should test some other top-level functions to see if this optimization has been done for them…

    Glad to see your DenseMap and sorting is going well. Those results are truly fast! It’s great to have such an alternative for heavy sorting loads (3D engine polygon sorting?). Not to get too off-topic, but do you think you’ll ever set up a source code repository on Google Code, GitHub, or the like?

    • #5 by skyboy on February 28th, 2011 · Reply

      The only problem with the results is that they’re only so competitive on systems where 3D is virtually impossible to have at high frame rates(or is this a plus?). Systems better suited, and with larger cache sizes show dramatically improved performance for Adobe’s method (excluding nulls, those still kill it). Unsorted running only 18% longer than sorted, while my method is 30% slower on sorted and 60% slower on unsorted.

      My method also doesn’t return results exactly the same as Array’s method all the time either: on numeric sort, it’s a perfect match, but on string sort, nulls, NaN and undefined aren’t in the same order as how Array returns them. Personally, I think Array should be consistent with those values like my method is (they’re actually pre-sorted to not only get them in the right order, but to avoid the above O(n^2) running time).

      And I have indeed set up a GitHub repository for the various things I create: https://github.com/skyboy/AS3-Utilities/tree/master/skyboy/
      Though, not many of the classes are as useful as I’d like. Hopefully with time, I’ll get more useful classes like DenseMap.

• #6 by skyboy on March 4th, 2011 · Reply

  An idea occurred to me related to switch statements.

  Testing a haXe compiled switch with the others, or an Apparat switch, and combing it with Apparat’s macro inlining to increase the number of tests per loop while keeping it legible. The speed up of not using if statements and just the lookupswitch command could be more dramatic in an unrolled loop.
  Especially around 15-ish cases, perhaps to the point where not using it in those cases would almost be a joke.

  • #7 by jackson on March 4th, 2011 · Reply

    Really, MXMLC should just detect when a lookupswitch can be used directly and do it rather than always doing some kind of pointless hybrid mode. It’s good to hear that raw lookupswitch is fast though since that means a future MXMLC can do just that optimization. Can you post bytecode for your haXe and Apparat versions?

    • #8 by skyboy on March 4th, 2011 · Reply

      Unfortunately the only place I have either is in my JSON class, and the sheer amount of bytecode in it causes nearly every decompiler to crash (even Nemo440). The best I can manage currently is some Apparat ASM:

              GetLocal(3),
              ConvertInt,
              LookupSwitch("L1", "L2", "L2", "L3", "L4", "L5", "L6", "L7", "L8", "L9", "L10", "L11", "L8", "L12"),