#242 ✓invalid
John-David Dalton

Optimize $A()

Reported by John-David Dalton | July 28th, 2008 @ 06:18 AM | in 1.7

This optimizes $A by exiting early if the argument passes is an empty array.

Comments and changes to this ticket

  • John-David Dalton

    John-David Dalton July 28th, 2008 @ 06:18 AM

    • State changed from “new” to “enhancement”
  • Tobie Langel

    Tobie Langel July 28th, 2008 @ 07:48 PM

    • Tag changed from patched to needs_benchmarks, patched

    Are you sure that's faster ?

    Using instanceof also won't work for arrays coming from other frames. Should be using Object.isArray, and I'm not sure it won't be a lot slower then.

  • John-David Dalton
  • John-David Dalton

    John-David Dalton July 28th, 2008 @ 08:54 PM

    Ya its faster for the majority of array uses.

    Sure there are some cases but they don't suffer from this addition.

    (they just keep the same $A performance)

    Object.isArray() is slow and just calling a

    function makes it slow in the benchmarks I have conducted.

  • John-David Dalton

    John-David Dalton July 28th, 2008 @ 07:56 PM

    • Tag changed from needs_benchmarks, patched to patched

    Here is a quick test, you can modify it to test for arguments, nodeLists and what not:

    <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
    	"http://www.w3.org/TR/html4/loose...">
    <html>
    <head>
    <title>Test</title>
    <meta http-equiv="Content-Type" content="text/html;charset=utf-8">
    
    <script src="prototype.js" type="text/javascript"></script>
    
    <script type="text/javascript">
    
    function $$A(iterable) {
      // fast path
      if (!iterable || (iterable instanceof Array && 
        !iterable.length)) return [];
    
      // delegate
      if (iterable.toArray) return iterable.toArray();
      var length = iterable.length || 0, results = new Array(length);
      while (length--) results[length] = iterable[length];
      return results;
    }
    
    document.observe('dom:loaded', function() {
     
     (function() {
        var iterable = []; // arguments; //$$('*');
        var count = 100000;
        
        var time = new Date();
        for (var i=0; i < count; i++) {
          $A(iterable);
        }
        $('output').innerHTML = '1: '+(new Date() - time);
        
        time = new Date();
        for (var i=0; i < count; i++) {
          $$A(iterable);
        }
        $('output').innerHTML+= ';<br/>2: ' +(new Date() - time);
      })(1,2,3,4);
    });
    </script>
    </head>
    
    <div id="output"><div>
    </body>
    </html>
    
  • Tobie Langel

    Tobie Langel July 28th, 2008 @ 09:02 PM

    Also:

    (function(){ return arguments instanceof Array })()
    >>> false
    
  • Tobie Langel

    Tobie Langel July 28th, 2008 @ 08:42 PM

    • Tag changed from patched to needs_benchmarks, patched

    Could we we have those benchmarks inside the test suite?

  • John-David Dalton

    John-David Dalton July 28th, 2008 @ 09:02 PM

    @Tobie Langel
    > (function(){ return arguments instanceof Array })()
    > >>> false
    
    As i mentioned above 
    "Sure there are some <strike>edge</strike> cases but they don't suffer from this addition.
    (they just keep the same $A performance)"
    
    We shoudn't use $A for arguments anyways when
    Array.prototype.slice.call(arguments, 0) is around 42% faster.
    
    Using $A for arguments is like using a sledge hammer when a tooth pick is needed.
    (I have attached some speed tests).
    
    @Tobie Langel
    > Could we we have those benchmarks inside the test suite?
    
    Sure I will add the benchmarks to the unit tests and make a patch for them
    this $A patch is created by Juriy, I just posted it so we wouldn't forget about it :D
    
  • Juriy Zaytsev

    Juriy Zaytsev July 28th, 2008 @ 09:21 PM

    Just to clarify, the enhancement is sort of a fast-path for empty arrays.

    Currently, empty arrays go through somewhat unnecessary steps - checking toArray, then creating 2 variables (one of which is an array created via "new") and only then returning an empty result;

    This is definitely not an urgent enhancement but is something we could consider in the future.

  • Tobie Langel

    Tobie Langel July 28th, 2008 @ 11:15 PM

    kangax, variables will be created at the start of the function whether or not we return early. By returning early, we're avoiding assigning to those variables, but that's it.

    What about this instead:

    var $A = function(iterable) {
      if (!iterable) return [];
      if (iterable.toArray) return iterable.toArray();
      if (!iterable.length) return [];
      var length = iterable.length, results = new Array(length);
      while (length--) results[length] = iterable[length];
      return results;
    }
    

    Avoids the instanceof bit and has exactly the same functionality as the original $A function.

    Regarding the sledge hammer argument, I agree performance wise, however, the readability isn't exactly the same, don't you think ?

  • John-David Dalton

    John-David Dalton July 28th, 2008 @ 11:57 PM

    @Tobie Langel - Ya readability wise it totally isnt as good.
    I think thats where wrapping Prototype in a closure would be a big help.
    We could make temp variables for short references to methods things like:
    $args = Array.prototype.slice;
    (function(){ 
      var args = $args.call(arguments);
      console.log(args);
    })(1,2,3,4);
    
    to avoid a method call or
    
    $args = function(args) {
      return Array.prototype.slice(args, 0);
    };
    
    @Tobie Langel  putting the if (!iterable.length)
    after the toArray condition seems to cause equal to or slower performance of the standard $A.
    
    This is because Arrays get extended with Enumerable with has a toArray method.
    So its mapping the array...
    
    Using the benchmark from earlier the results are:
    $A: 1421; <-- Original
    $$A: 500; <-- Juriys
    $$$A: 1438 <-- Yours
    
  • Juriy Zaytsev

    Juriy Zaytsev July 28th, 2008 @ 11:49 PM

    kangax, variables will be created at the start of the function whether or not we return early. By returning early, we're avoiding assigning to those variables, but that's it.

    Tobie, you're right, but this assignment is exactly what matters here : )

    Yes, variables are initialized to `undefined` when a function enters execution context, but none of the objects are created (such as new array object - which is then referenced by `results` variable) and none of the identifier resolutions occur (as in `iterable.length` lookup).

    Last time we tested this patch, it seemed to yield ~30-50% speed increase.

    Avoids the instanceof bit and has exactly the same functionality as the original $A function

    I like it : )

    `instanceof` was just a way to check for an object existence before resolving its `length`

    Regarding the sledge hammer argument, I agree performance wise, however, the readability isn't exactly the same, don't you think ?

    I think that readability of such critical function is not as important as the way its performance affects the rest of the framework.

  • Juriy Zaytsev

    Juriy Zaytsev July 28th, 2008 @ 11:54 PM

    $A: 1421;

    Ahh...

    I forgot that Array#toArray does an array clone (with `concat`)

  • Juriy Zaytsev

    Juriy Zaytsev July 29th, 2008 @ 12:00 AM

    Looking at Array#toArray, is there a reason for concatenating with an empty array? Calling `concat` with 0 arguments should be enough to create a clone if I'm not mistaken.

  • Tobie Langel

    Tobie Langel July 29th, 2008 @ 01:02 AM

    Generally speaking, although I do get the perf argument - and I think it really is a valid one - I think we should be cleaning up and re-factoring parts of the framework (using a closure is a good idea, commenting code and stripping comments during build, etc.) before adding perf enhancements all over the place which make the source code less readable.

  • Tobie Langel

    Tobie Langel July 29th, 2008 @ 01:08 AM

    Calling `concat` with 0 arguments should be enough to create a clone if I'm not mistaken.

    Good point.

  • Tobie Langel

    Tobie Langel July 29th, 2008 @ 01:09 AM

    More seriously speaking, anybody who's actually passing an Array to $A is doing something stupid. Why should we be optimizing for that usecase?

  • Tobie Langel

    Tobie Langel July 29th, 2008 @ 01:10 AM

    • State changed from “enhancement” to “invalid”
  • John-David Dalton

    John-David Dalton July 29th, 2008 @ 02:39 AM

    Ahh good point (as long as we don't pass arrays to $A in prototype its cool to close this then :)

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 02:27 AM

    • Tag changed from needs_benchmarks, patched to missing:benchmarks, patched

    [not-tagged:"needs_benchmarks" tagged:"missing:benchmarks" bulk edit command]

  • Tobie Langel

    Tobie Langel July 24th, 2009 @ 03:39 AM

    • Tag changed from missing:benchmarks, patched to needs:benchmarks, patched

    [not-tagged:"missing:benchmarks" tagged:"needs:benchmarks" bulk edit command]

Please Sign in or create a free account to add a new ticket.

With your very own profile, you can contribute to projects, track your activity, watch tickets, receive and update tickets through your email and much more.

New-ticket Create new ticket

Create your profile

Help contribute to this project by taking a few moments to create your personal profile. Create your profile ยป

The Prototype JavaScript library.

Shared Ticket Bins

Pages