How to copy multi object array contents into single object arrays?

[Jorge]

Scott Sauyet wrote:
I collected the results at
   http://scott.sauyet.com/Javascript/Test/LoopTimer/1/
But I've done something screwy to IE on the page trying to be clever..
If anyone can tell me why the generated links are not working properly
in IE, I would love to know.
line 120:
| var size = parseInt(cells.textContent, 10) || 1,
                               ^^^^^^^^^^^
No such thing in mshtml

D'OH.  Self-administered dope-slap!  I guess that's what I guess for
throwing things together.

Updated version:

   http://scott.sauyet.com/Javascript/Test/LoopTimer/2/

Thanks again,

You can't compare a .push(value) with an = value; !

 

[Scott Sauyet]

Updated version:
   http://scott.sauyet.com/Javascript/Test/LoopTimer/2/
Thanks again,

You can't compare a .push(value) with an = value; !

Oh no? I believe I just did!

This was really a comparison of my solution to the original problem
and Thomas Lahn's follow-up.

I'm not trying to prove something in particular about what part of the
algorithm is speedy or slow, only to see what differences in speed
there are between them.

-- Scott

 

[Jorge]

You can't compare a .push(value) with an = value; !

Oh no?  I believe I just did!  

This was really a comparison of my solution to the original problem
and Thomas Lahn's follow-up.

I'm not trying to prove something in particular about what part of the
algorithm is speedy or slow, only to see what differences in speed
there are between them.

Ok. But don't believe what Pointy said: "Make benchmarks then, and you
will see that the simple post-decrement
increases efficiency considerably as well", because it's not true.

 

[Scott Sauyet]

Yes, http://jorgechamorro.com/cljs/093/

Thanks. I'm confused, though. You don't seem to assign anything to
"library". Am I missing somthing? If not, then the test seems to be
meaningless.

BTW, It's not faster i-- than i++.

No, I wouldn't expect it to be. But that doesn't imply that

for (i = bound; i-- {/* ... */}

isn't faster than

for (i = 0; i < bound; i++) {/* ... */}

is, right? That's what Thomas was arguing.

-- Scott

 

[Jorge]

Thanks.  I'm confused, though.  You don't seem to assign anything to
"library".  Am I missing somthing?  If not, then the test seems to be
meaningless.

It's in the line #66: 2e5 elements.

(function (count) {
while (count--) {
library[count]= {img: 'img' + count + '.jpg', caption: 'Caption '
+ count};
}
})(window.JSLitmusMultiplier= 2e5);

 

[Garrett Smith]

Scott Sauyet wrote:
I collected the results at
http://scott.sauyet.com/Javascript/Test/LoopTimer/1/
But I've done something screwy to IE on the page trying to be clever.
If anyone can tell me why the generated links are not working properly
in IE, I would love to know.
line 120:
| var size = parseInt(cells.textContent, 10) || 1,
^^^^^^^^^^^
No such thing in mshtml

D'OH. Self-administered dope-slap! I guess that's what I guess for
throwing things together.

Updated version:

http://scott.sauyet.com/Javascript/Test/LoopTimer/2/

Thanks again,

There are too many variables in your test. The forwards loop body calls
`push` twice, while the reverse loop does not.

What is causing the performance difference? Is it the direction of the
loop or is it the call to `push`? You can't tell from that test, can you?

To test performance of loop direction loop body must be identical in
both loops.

 

[Garrett Smith]

Scott Sauyet wrote:
var photos = [], captions = [];
for (var i = 0, len = library.length; i < len; i++) {
photos.push(library["img"]);
captions.push(library["caption"]);
}
var
photos = [],
captions = [],
len = library.length;

photos.length = captions.length = len;

for (var i = len; i--
{
var o = library;
photos = o.img;
captions = o.caption;
}

Any of the suggestions will work, of course.

Alas, not all, as I have pointed out.

The differences have to do with readability versus performance.
Perhaps the most readable version would be something like this:

var photos = [];
var captions = [];
for (var i = 0; i < library.length; i++) {
var element = library;
photos.push(element.img);
captions.push(element.caption);
}

For people used to C-style languages, that loop will feel quite
familiar.

You don't know what you are talking about. First of all, for all intents
and purposes, ECMAScript is a C-style language. (If you have eyes to see
you can observed the similarities.)

(Therefore,) the backwards-counting loop will be familiar to "people used
to C-style languages", and it will also be a lot more efficient than the
one above.

You are making an assertion about observations you have made in
implementation-dependent, and of course, without proof.

After all there is no boolean type in C before C99, so you

would use `int' (and guess what, C's `for' statement works the same as in
ECMAScript save the implicit conversion!), and in C99 you would use
`(_Bool) i--' for maximum efficiency.

I'm failing to see how the unavailability of boolean type in C is
relevant to the discussion of loop performance in ECMAScript.

Perhaps you can provide further information as to how this proves that a
backwards loop in ECMAScript is more efficient.

If `photos` order matters, then that ought to be a motivating factor for
which way to loop.

The ascending order and the unnecessary push() calls will decrease
efficiency considerably, and the push() call will decrease compatibility,
too (JScript 5.0 does not have it).

The `push` method good for adding several elements at a time, as in:-

myArray.push(q,w,e,r,a,s,d,f,z,x,c,v);

That is not the case here. Calling `push` would be an extra function
call here. No need for it.

[...]

Make benchmarks then,

Did you retest your benchmarks?

and you will see that the simple post-decrement

increases efficiency considerably as well (else the pattern would not have
prevailed, would it?). We have been over this ad nauseam before.

Any observed difference in performance will be implementation-dependent.

Do you get a kick out of explaining the obvious even though nobody has
asked a question? And you are being imprecise after all: *All* numeric
values *except* 0 (+0 and -0, but these are only Specification mechanisms)
and NaN type-convert to `true'. We have discussed this numerous times as
well.


As in the more simple and more efficient i-- ...


Pretty according to whose standards? It could create misconceptions with
newcomers about a limit-type `-->' operator, and it is even less readable
or obvious than the versions you were incompetently whining about.


The browser does not matter (the ECMAScript implementation does), and this
discussion has been performed a hundred times or so already. So have
results been posted. Much you have to learn.

It appears that you have believed some observations in a few browsers
and incorrectly come to the conclusion that a backwards loop is faster.

Score adjusted

Nobody but you cares about your silly scorekeeping activities. They're
embarrassing. Best keep that to yourself and not tell anyone.

 

[Jorge]

No, I wouldn't expect it to be.  But that doesn't imply that

    for (i = bound; i-- {/* ... */}

isn't faster than

    for (i = 0; i < bound; i++) {/* ... */}

is, right?

Yes but no. On a good day we would be talking at best about an
infinitesimal of a µs.

That's what Thomas was arguing.

i<bound is a boolean, but i-- isn't, so what you've got to compare it
to is really ~ (i === 0) (i converted to a boolean). It might be true
that the test (i === 0) is some small fraction of a µs faster than
(i<bound), but for some reason (implementation ?) filling the arrays
upwards is faster than downwards and that weights much more than that
infinitesimal of µs in the end results.

The truth is that filling the arrays upwards is faster in most
browsers, and when not, they're ~ equally fast.

 

[Scott Sauyet]

There are too many variables in your test. The forwards loop body calls
`push` twice, while the reverse loop does not.

What is causing the performance difference? Is it the direction of the
loop or is it the call to `push`? You can't tell from that test, can you?

I was trying really hard not to get sucked into the navel-gazing
arguments so prevalent here. So much for my New Year's resolution, I
guess.

Thomas offered a suggested improvement to my function. My tests show
that for most reasonable cases it was an improvement, and also that
it's not as clear-cut as he suggested. I should have known better
than to distinguish one implementation from another on the basis of
one of their features (forward/backward), but I guess I'm stuck with
it now!

If I find some time tonight or tomorrow, I'll do a few more thorough
benchmarks of multiple versions of the algorithms and see what the
main issues are.

Thank you very much for your response.

-- Scott

 

[Garrett Smith]

I was trying really hard not to get sucked into the navel-gazing
arguments so prevalent here. So much for my New Year's resolution, I
guess.

The test you created cannot be used as a premise to a conclusion of loop
direction speed.

Thomas offered a suggested improvement to my function. My tests show
that for most reasonable cases it was an improvement, and also that
it's not as clear-cut as he suggested.

Your tests do not show that a forwards loop is faster than a reverse
loop. They do not show that `push` is slower than [[Put]] (though that
should be obvious). The tests you provided prove nothing.

Think about `myArray.push()` versus `[[Put]]` with property accessors.

To call `myArray.push()`, the ECMAScript interpreter must resolve the
push property. The push property is not resolved on the object, it is
resolved on the object's prototype, Array.prototype. After `push` has
been resolved to a value, the interpreter calls it `myArray` for the
`this` value and an internal `ArgumentList` of the arguments passed.

Compare that to Array [[Put]].

In Array [[Put]](p, v), if `myArray` does not have a property with name
p, then it is created and given the value v.

If converting the property name to a numeric representation (ToUnit32)
is >= length, then 'myArray.length` is increased to `ToUnit32(p) + 1`.

I should have known better

than to distinguish one implementation from another on the basis of
one of their features (forward/backward), but I guess I'm stuck with
it now!

It is a misleading test.

If I find some time tonight or tomorrow, I'll do a few more thorough
benchmarks of multiple versions of the algorithms and see what the
main issues are.

The loop backwards using arrays seems to be slower then the loop forwards.

Results:

Opera 10.10:
forwards()
353
backwards()
432

Firefox 3.5.5:
forwards()
64
backwards()
933

Seamonkey
forwards()
1927
backwards()
2600

IE7:
forwards()
2141
backwards()
2502

Safari 4:
forwards()
66
backwards()
3458

Safari 3:
forwards()
1079
backwards()
8646

Safari 2:
(out of memory errors).


<!doctype html>
<html lang="en">
<head>
<title>loop test</title>
</head>
<body>
<script type="text/javascript">
var ITERATIONS = 1000000;
function forwards(){
var x = [], d = +new Date, noise = Math.PI,
i, len = ITERATIONS, time;
x.length = len;
for(i = 0; i < len; i++){
x = i + noise;
}
time = new Date-d;
document.getElementById("f").innerHTML = String(time);
}

function backwards(){
var x = [], d = +new Date, noise = Math.PI,
len = ITERATIONS, time;
x.length = len;
for(i = len; i-- > 0{
x = i + noise;
}
time = new Date-d;
document.getElementById("b").innerHTML = String(time);
}
</script>
<button onclick="forwards();">forwards()</button>
<pre id="f">-</pre>

<button onclick="backwards();">backwards()</button>
<pre id="b">-</pre>
</body>
</html>

What is the explanation for Thomas' certainty that the backwards loop
would be faster? One possibility is irrational mentality. Another
possibility is that a backwards loop had been observed to be faster at
one point.

If a backwards loop had been observed to be faster, then it is worth
investigating the test that made such conclusion.

It is likely that that test did not set the `length` property of the
resulting array prior to looping. If that is the case, then the loop
forwards has a penalty of:

| 10. Change (or set) the value of the length property of A to
| ToUint32(P)+ 1.

Resetting the length on every iteration (implicitly, in step 10 of Array
[[Put]]), demands more work of the implementation.

The key to populating an array quickly is setting the length of the
array beforehand.

The direction of the loop should not be chosen based on speed, but by
the order desired of the resulting array.

 

[Lasse]

In Firefox and Chrome it was more complicated.  For array sizes of 10, 100, and
1000 in Chrome, the backward was faster than forward by factors
approximately 1.5 - 2.5.  But for 10000 elements, forward was faster
by a factor of about 1.25; I checked at 100000 elements too, and
forward was faster by a factor of about 1.5.

The probable reason for this is that you start filling out the array
from the back.
This means that the array starts out with only one element af index
9999 - a very
sparse array. Chrome and Firefox likely starts using an internal
representation
meant for sparse arrays, which is not as time efficient as linear
arrays.
If you fill out the result array from the start, it will always be
densely packed,
and will stay that way when the backing store is increased.

Try changing your array initialization to
var len = library.length, photos = new Array(len), captions = new
Array(len);
At least in Chrome this preallocates the array as a dense array with
the given length.

I also notice that the two algorithms differ in several ways.
The backward one only reads library once, whereas the forward one
reads it twice.
One uses foo.push(value), the other foo=value. Both could use foo
=value.
They also differ in how the the property is loaded: one uses
foo.caption, the other foo["caption"].
That shouldn't matter, but there is no reason to make the tests look
so different.

Also, I don't see nearly as big a difference in Chrome 4 (dev-channel
release, on Linux):
Algorithm: Plain, elements: 1000000, elements per millisecond: 3817
Algorithm: Reverse, elements: 1000000, elements per millisecond: 4259
(using 5 iterations).

/L

 

[Thomas 'PointedEars' Lahn]

Thanks. I'm confused, though. You don't seem to assign anything to
"library". Am I missing somthing? If not, then the test seems to be
meaningless.

^^^^^^^^^^^
As always.

No, I wouldn't expect it to be. But that doesn't imply that

for (i = bound; i-- {/* ... */}

isn't faster than

for (i = 0; i < bound; i++) {/* ... */}

is, right? That's what Thomas was arguing.

Exactly. It stands to reason that this applies simply because it takes one
operation less. It would appear that setting array elements biases the
result towards the incrementing loop because newer optimizations that
consider sparse arrays come into play.

var len = 100000;

/*
* WebKit throws a TypeError with this later;
* base object of call must be `console' there
*/
var dmsg = typeof console != "undefined" && console.log || window.alert;

var d = new Date();
for (var i = len; i-- ;
dmsg(new Date() - d);

d = new Date();
for (var i = 0; i < len; i++) ;
dmsg(new Date() - d);

The second one is always considerably slower here (TraceMonkey 1.9.1.6,
JScript 5.6.6626: > 100%; Opera 10.10: > 50%; JavaScriptCore 531.21.8: >
40%).


PointedEars

 

[Jorge]

Scott: learn to read code.

  ^^^^^^^^^^^
As always.

Pointy: you're an IDIOT.

The reality:

var i= 1e6, a= [], d= +new Date();
while (i--) { a= ""; }
console.log(+new Date()- d);

Safari4.0.4 --> 2012ms
FF3.6 --> 1730ms
ff3.5 --> 1674ms
ff3.0.15 --> 1810ms
Chrome --> 1114ms
Opera 10.5b --> 665ms

var len= 1e6, i= 0, a= [], d= +new Date();
while (i<len) { a[i++]= ""; }
console.log(+new Date()- d);

Safari4.0.4 --> 303ms 15% (!)
FF3.6 --> 1110ms 64%
ff3.5 --> 1236ms 73%
ff3.0.15 --> 921ms 50%
Chrome --> 1310ms 117%
Opera 10.5b --> 680ms 102%

 

[Thomas 'PointedEars' Lahn]

Pointy: you're an IDIOT.

Mirror, mirror ...

The reality:

var i= 1e6, a= [], d= +new Date();
while (i--) { a= ""; }
console.log(+new Date()- d);

Idiot. That's a *while* loop that *sets array elements*. Not a *for* loop
that *does not*.


PointedEars

 

[Jorge]

var i= 1e6, a= [], d= +new Date();
while (i--) { a= ""; }
console.log(+new Date()- d);

Idiot.  That's a *while* loop that *sets array elements*.  Not a *for* loop
that *does not*.

(load applause)

*You* posted this code:

for (var i = len; i-- {
var o = library;
photos = o.img;
captions = o.caption;
}

And *you* said: "Benchmarks suggest it would be about 20% faster in
TraceMonkey 1.9.1.6.".

 

[Thomas 'PointedEars' Lahn]

var i= 1e6, a= [], d= +new Date();
while (i--) { a= ""; }
console.log(+new Date()- d);

Idiot. That's a *while* loop that *sets array elements*. Not a *for*
loop that *does not*.

(load applause)

You are such a complete idiot.

*You* posted this code:

for (var i = len; i-- {
var o = library;
photos = o.img;
captions = o.caption;
}

And *you* said: "Benchmarks suggest it would be about 20% faster in
TraceMonkey 1.9.1.6.".

In < Which is exactly what I
measured. (Faster than *what*, stupid? Now what have I been referring to
there?).

Neither of which disproves the statement about `for' loops I made in the
precursor, <that you tried to
disprove with your flawed test case,
<news:a34ddd71-fee2-488e (e-mail address removed)>.

Get a brain, Jorge.


PointedEars

 

[Jorge]

(... whining ...)

Pointy, whine as much as you like, but your "optimized" code does in
fact run *slower*.

 

[Jorge]

(load applause)

s/load/loud/

 

[The Natural Philosopher]

s/load/loud/

s/applause/applause.wav/ ;-)

 

[Thomas 'PointedEars' Lahn]

var imgArray = library.map(filterByName("img"));
var captionArray = library.map(filterByName("caption"));
[...]

Where not supported, Array.prototype.map functionality can be added, as
indicated on MDC page[1].

What a waste. If an Array prototype method should be used here, then
Array.prototype.forEach().

Writing your own loop would be fastest here.

No argument there.


PointedEars