Re: Wanted: standard Array function to append an array's elements to another array
Hi,
I have just noticed [1], read all messages on this thread and thought
that the JavaScript stack size limit for
Array.prototype.push.apply(firstArray, secondArray); was an
implementation concern rather than anything else and it really sounds
weird to me to add a method just because implementations aren't capable
of performing well with some methods.
Theorically speaking, why .pushAll would do better than
.push.apply+second argument? There is no reason I can think of.
I think that implementors did implement strictly ES5 definition of push:
Array.prototype.push ( [ item1 [ , item2 [ , … ] ] ] ) which considers
each item as a new argument, making the stack grow. Why would a .pushAll
do better? Because there is only one argument which is an array. So I
think that instead of adding pushAll, we'd rather redefine .push with
the great ...rest parameters [2]
Array.prototype.push = function(...items){
let O = ToObject(this);
let lenVal = O.length;
let n = ToUint32(lenVal);
let itemsList = ToList(items); // sorry for the bickshed
while(itemsList.length != 0){
let E = itemsList.pop(); // bickshed bis
O[n] = E;
n++;
O.length = n;
}
return n;
};
(which is pretty much Jeff's implementation of .pushAll in the initial
message)
As a matter of fact, maybe that all methods that where previously
defined as myFunction(a, b [, c1 [, c2 [ , … ] ] ]) would have rather
being re-specified in the form of myFunction(a, b, ...c). Should I
file a bug on that?
Regarding implementations of .push, if they can do as good as a .pushAll
could, then they are just buggy and should be fixed in my opinion.
What do you think?
David
[1] http://wiki.ecmascript.org/doku.php?id=strawman:array.prototype.pushall
[2] http://wiki.ecmascript.org/doku.php?id=harmony:rest_parameters
Le 25/07/2011 21:54, Jeff Walden a écrit :
If I have one array, and I want to append the contents of an arbitrary
array to it, and I don't need the unmodified first array after
appending the second array's elements to it, I have three options.
First, I can use Array.prototype.concat to create a new array
consisting of the first array, then the contents of the second. But
this creates a new array rather than mutating the first array, so it
potentially wastes memory proportional to the size of the first array,
barring complicated heuristics to recognize and avoid the waste.
Potentially worse, if any element of the second array is an Array,
instead of that array being appended, its elements will be appended.
Second, I can use Array.prototype.push:
Array.prototype.push.apply(firstArray, secondArray);
This avoids the memory-wastefulness concern, and it doesn't treat
Array items specially. But it introduces a third concern: the
JavaScript stack size limit, if the second array contains a
particularly large number of elements. This might manifest itself as
causing a stack overflow exception, or it might cause only some of the
elements of the second array to be appended (an arguably buggy
mitigation mechanism, but one some engines use, at least currently).
Third, I can use Array.prototype.splice, passing in |start = length|
and |deleteCount = 0|. But splice too encounters the stack size limit
problem. Worse, because its arguments are (start, deleteCount,
newElt1, newElt2, ...), constructing the array of arguments with which
to apply the splice method seems to require complicated copy-on-write
array-element-sharing to mutate the first array without consuming
twice the first array's memory, or some other tricky scheme. For such
schemes to be effective here, the programmer would have to structure
his code pretty carefully, being sure to only use
Array.prototype.unshift, say, to implement it. And there's a
bootstrapping problem to creating the array of arguments to supply to
splice in order to append the elements of an array to the first array.
I see no problem-free way to append an array's elements to another
array without doing it manually. That's not hard, but it's
error-prone, and it's much trickier to recognize and correctly
optimize. I think there should be a way to append elements of an
arbitrarily sized array to another array, mutating that array
in-place, without consuming excess memory. I'm not too concerned about
its precise semantics or about what it's named. For a starting point
I'll propose Array.prototype.pushAll (or extend, following Python, but
again, I don't really care about the exact name right now):
Object.defineProperty(Array.prototype, pushAll,
{
enumerable: false, configurable: true, writable: true,
value: function pushAll(other)
{
use strict;
var t = ToObject(this);
var length = ToUint32(t.length);
var otherLen = other.length;
for (var i = 0, j = length; i otherLen; i++, j++)
t[j] = other[i];
t.length = j;
return void 0;
},
});
Comments? Suggestions? Requests for changes?
I also had the thought that it might be nice to be able to push a
subrange of the elements of an array. You could do
Re: Wanted: standard Array function to append an array's elements to another array
Le 01/11/2011 22:17, David Bruant a écrit : (...) Regarding implementations of .push, if they can I meant *can't*, of course. do as good as a .pushAll could, then they are just buggy and should be fixed in my opinion. ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
On 07/31/2011 03:57 AM, Andrea Giammarchi wrote: I agree mine is more a workaround while we need a solution but it's not about Array here, it's about number of arguments limit per function so once we have pushAll in place, all other methods will still suffer the apply problem True. It seems to me the fundamental problem is exposing n-ary functionality solely through a variadic interface, and not through an interface accepting an array. Such interfaces are moderately handy for quick hacking. Yet since they're not much handier than adding [] around the variadic arguments, I don't see that they provide much value. Which still leaves the problem of the existing variadic methods, of course... Jeff ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
I agree mine is more a workaround while we need a solution but it's not
about Array here, it's about number of arguments limit per function so once
we have pushAll in place, all other methods will still suffer the apply
problem and it's not about apply either, e.g.
var tooMany = Array(0x).join(,$).replace(
/,\$/g,
function (m,i) {return m + i}
).slice(1);
alert(Function(
tooMany,
return [ + tooMany + ].length
)());
Too many parameters in function definition (only 32766 allowed)
So ... this is bad
On Sat, Jul 30, 2011 at 12:10 AM, Jeff Walden jwalden...@mit.edu wrote:
On 07/29/2011 05:22 AM, Andrea Giammarchi wrote:
to avoid apply limits is actually trivial
More or less, yes.
But it requires the developer to anticipate the concern in advance that the
elements being appended might consume all available stack space. I don't
think most developers think at all about the size of the stack, or about its
being limited, except when they write a recursive algorithm, intentionally
or inadvertently, and neglect to correctly implement the base case. I
certainly forgot about this concern when I wrote the buggy code which
initially triggered this request, and I think it's reasonably apparent
there's a problem when even a JS engine implementer makes this mistake.
Past that, your MAX_LENGTH constant would have to be lower than the max
length across all JS engines cared about. I find it concerning that
something as simple as extending an array with the elements of another array
would require an implementation-dependent workaround, when this operation is
built-in functionality in other mainstream languages where mutation is
common:
C++: vectorT::insert
http://www.cplusplus.com/**reference/stl/vector/insert/http://www.cplusplus.com/reference/stl/vector/insert/
C#: ListT.AddRange
http://msdn.microsoft.com/en-**us/library/z883w3dc.aspx#Y570http://msdn.microsoft.com/en-us/library/z883w3dc.aspx#Y570
Java: ListE.addAll
http://download.oracle.com/**javase/1.5.0/docs/api/java/**util/List.htmlhttp://download.oracle.com/javase/1.5.0/docs/api/java/util/List.html
Perl: push
http://perlmeme.org/howtos/**perlfunc/push_function.htmlhttp://perlmeme.org/howtos/perlfunc/push_function.html
Python: list.extend
http://docs.python.org/**tutorial/datastructures.htmlhttp://docs.python.org/tutorial/datastructures.html
Ruby: array.concat
http://www.ruby-doc.org/core/**classes/Array.html#M000224http://www.ruby-doc.org/core/classes/Array.html#M000224
Jeff
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's
I may be late here, but what's wrong with
firstArray = firstArray.concat(secondArray); ?
If there are still problems I would say no magic method can solve them,
isn't it?
On Fri, Jul 29, 2011 at 1:59 AM, Jeff Walden jwalden...@mit.edu wrote:
On 07/27/2011 01:26 PM, John-David Dalton wrote:
@Jeff In reply to
https://mail.mozilla.org/**pipermail/es-discuss/2011-**July/016124.htmlhttps://mail.mozilla.org/pipermail/es-discuss/2011-July/016124.html
,
which engines have problems with `firstArray.push.apply(**firstArray,
secondArray)` ?
Shouldn't a bug report be filed for the specific JS engine or the spec
be clarified on the subject (String.fromCharCode too) instead of
adding another method to Array.prototype?
Here's a testcase:
(function test() { var big = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb, 0xc,
0xd, 0xe, 0xf]; while (true) { try { var before = big.length;
big.push.apply(big, big); if (big.length !== before + before) throw before;
} catch (e) { return big.length + : + e; } } })()
If the apply call throws an exception, a string consisting of the array
length before the push failed, and the exception thrown, is returned. If
the push call doesn't push all the elements it should have pushed,a string
consisting of the array length after the push, and the array length before
the faulty push, is returned.
The testcase demonstrates failures with these engines:
SpiderMonkey's max argument-count is currently something like 480k, so
pushing an array of 512k elements onto another array will only push the
first 480k-ish. (This is being changed so that an exception is thrown,
shortly. It has caused at least two quite unexpected bugs. Probably
someone else has stumbled across the problem before, but I don't know for
sure.)
In v8 an exception is thrown sometime between secondArray having length
128k and 256k.
Nitro copied SpiderMonkey, although its max-arg-count isn't as high as
SpiderMonkey's, so it will only push the first N elements of a really big
array.
IE10 throws an exception for a push of the elements of an array somewhere
between 128k and 256k.
IE9 throws similarly, except between 256k and 512k.
Of the major engines, only Opera seems to have no problems here. I'm not
sure why this is. But ignoring Opera, everyone fails this. And the reason,
I believe, is not that it's a quality of implementation issue: it's that the
general way to implement this butts up against ingrained implementation
choices, and different engines will quite rationally behave in different
ways in response. push.apply is simply not a reliable substitute for a
built-in method to push the contents of an array into another array.
Jeff
__**_
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/**listinfo/es-discusshttps://mail.mozilla.org/listinfo/es-discuss
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
to avoid apply limits is actually trivial:
var fromCharCode = (function ($fromCharCode, MAX_LENGTH) {
return function fromCharCode(code) {
typeof code == number (code = [code]);
for (var
result = [],
i = 0,
length = code.length;
i length; i += MAX_LENGTH
) {
result.push($fromCharCode.apply(null, code.slice(i, i +
MAX_LENGTH)));
}
return result.join();
};
}(String.fromCharCode, 2048));
// example
alert(fromCharCode(80)); // P
alert(fromCharCode([80,81,82,83,84])); // PQRST
about the pushAll I wonder if concat does not do already exactly what you
are looking for, as I wrote in the other thread.
Best Regards,
Andrea Giammarchi
On Mon, Jul 25, 2011 at 10:17 PM, Jeff Walden jwalden...@mit.edu wrote:
It's perhaps worth noting that this problem also occurs with
String.fromCharCode. I suspect the need for a version of
|String.fromCharCode.apply(**null, codesArray)| that always works, even
for super-big |codesArray|, is rather smaller than for the similar
Array.prototype.push concern.
Jeff
__**_
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/**listinfo/es-discusshttps://mail.mozilla.org/listinfo/es-discuss
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's
On 07/29/2011 05:01 AM, Andrea Giammarchi wrote: I may be late here, but what's wrong with firstArray = firstArray.concat(secondArray); ? If there are still problems I would say no magic method can solve them, isn't it? That creates a new array rather than mutate the array originally referred to by |firstArray| here, and I originally specified that only mutation was acceptable, because creating a new array requires extra space proportional to the length of |firstArray|. But I assume you're arguing that an engine could recognize that the copy could be transformed into a mutation. You'd have to prove that was the *only* reference to the original array in order to perform that optimization, or prove that it was observably correct to do that. Such analysis is tricky and costly time-wise. Relying on it would also be performance-fragile. If you were pushing incrementally onto an array (say, because you were appending arrays of bytes read from a network stream, saving them up to be processed all at once), the entire process is O(n) in bytes processed with push-through-mutation. But it's O(n**2) with push-by-copying. Thus you'd have to require the developer to understand when the optimization could be applied, in order to structure his code such that it would be applied. That level of understanding of compilers, and of the algorithms actually used to implement them (which won't be publicly available for some engines), seems way way beyond wh at can reasonably be expected of web developers. Jeff ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
On 07/29/2011 05:22 AM, Andrea Giammarchi wrote: to avoid apply limits is actually trivial More or less, yes. But it requires the developer to anticipate the concern in advance that the elements being appended might consume all available stack space. I don't think most developers think at all about the size of the stack, or about its being limited, except when they write a recursive algorithm, intentionally or inadvertently, and neglect to correctly implement the base case. I certainly forgot about this concern when I wrote the buggy code which initially triggered this request, and I think it's reasonably apparent there's a problem when even a JS engine implementer makes this mistake. Past that, your MAX_LENGTH constant would have to be lower than the max length across all JS engines cared about. I find it concerning that something as simple as extending an array with the elements of another array would require an implementation-dependent workaround, when this operation is built-in functionality in other mainstream languages where mutation is common: C++: vectorT::insert http://www.cplusplus.com/reference/stl/vector/insert/ C#: ListT.AddRange http://msdn.microsoft.com/en-us/library/z883w3dc.aspx#Y570 Java: ListE.addAll http://download.oracle.com/javase/1.5.0/docs/api/java/util/List.html Perl: push http://perlmeme.org/howtos/perlfunc/push_function.html Python: list.extend http://docs.python.org/tutorial/datastructures.html Ruby: array.concat http://www.ruby-doc.org/core/classes/Array.html#M000224 Jeff ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
On 07/27/2011 10:12 PM, Mark S. Miller wrote: We could debate the pros and cons of this sort of chaining convention in general. However, in this case I think the more important issue is API consistency. I was thinking this might actually be more consistent, to return this. Consider Array.prototype.sort, for example. (Or maybe the new length would be more consistent with Array.prototype.push, on second thought.) It does seem a reasonable guideline to return something when something can be returned, and not to return nothing. Returning |undefined| was just my not having thought of an obviously meaningful and plausible value to return. But I'm fine with any of these return values -- the pushing-the-array-contents business is the only truly important part of the method to me. Jeff ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's
On 07/27/2011 01:26 PM, John-David Dalton wrote:
@Jeff In reply to
https://mail.mozilla.org/pipermail/es-discuss/2011-July/016124.html,
which engines have problems with `firstArray.push.apply(firstArray,
secondArray)` ?
Shouldn't a bug report be filed for the specific JS engine or the spec
be clarified on the subject (String.fromCharCode too) instead of
adding another method to Array.prototype?
Here's a testcase:
(function test() { var big = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0xa, 0xb, 0xc, 0xd, 0xe,
0xf]; while (true) { try { var before = big.length; big.push.apply(big, big); if
(big.length !== before + before) throw before; } catch (e) { return big.length + :
+ e; } } })()
If the apply call throws an exception, a string consisting of the array length
before the push failed, and the exception thrown, is returned. If the push
call doesn't push all the elements it should have pushed,a string consisting of
the array length after the push, and the array length before the faulty push,
is returned.
The testcase demonstrates failures with these engines:
SpiderMonkey's max argument-count is currently something like 480k, so pushing
an array of 512k elements onto another array will only push the first 480k-ish.
(This is being changed so that an exception is thrown, shortly. It has caused
at least two quite unexpected bugs. Probably someone else has stumbled across
the problem before, but I don't know for sure.)
In v8 an exception is thrown sometime between secondArray having length 128k
and 256k.
Nitro copied SpiderMonkey, although its max-arg-count isn't as high as
SpiderMonkey's, so it will only push the first N elements of a really big array.
IE10 throws an exception for a push of the elements of an array somewhere
between 128k and 256k.
IE9 throws similarly, except between 256k and 512k.
Of the major engines, only Opera seems to have no problems here. I'm not sure
why this is. But ignoring Opera, everyone fails this. And the reason, I
believe, is not that it's a quality of implementation issue: it's that the
general way to implement this butts up against ingrained implementation
choices, and different engines will quite rationally behave in different ways
in response. push.apply is simply not a reliable substitute for a built-in
method to push the contents of an array into another array.
Jeff
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
On 7/25/11 12:54 PM, Jeff Walden wrote:
Object.defineProperty(Array.prototype, pushAll,
{
enumerable: false, configurable: true, writable: true,
value: function pushAll(other)
{
use strict;
var t = ToObject(this);
var length = ToUint32(t.length);
var otherLen = other.length;
for (var i = 0, j = length; i otherLen; i++, j++)
t[j] = other[i];
t.length = j;
return void 0;
},
});
Comments? Suggestions? Requests for changes?
Could you return this instead of undefined so that we can chain calls?
For example:
a.pushAll(b).pushAll(c).sort()
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
RE: Wanted: standard Array function to append an array's
@Jeff In reply to https://mail.mozilla.org/pipermail/es-discuss/2011-July/016124.html, which engines have problems with `firstArray.push.apply(firstArray, secondArray)` ? Shouldn't a bug report be filed for the specific JS engine or the spec be clarified on the subject (String.fromCharCode too) instead of adding another method to Array.prototype? -JDD ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
On Wed, Jul 27, 2011 at 9:21 AM, David Flanagan dflana...@mozilla.comwrote: Could you return this instead of undefined so that we can chain calls? For example: a.pushAll(b).pushAll(c).sort() We could debate the pros and cons of this sort of chaining convention in general. However, in this case I think the more important issue is API consistency. The JS built ins are not defined in this style. It would make the API much less regular and predictable to have some use this chaining convention while others -- especially similar others like push -- don't. I think this applies whether pushAll were actually added to EcmaScript or if it were added as part of a library that makes it appear as if it is an additional built-in. -- Cheers, --MarkM ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
Wanted: standard Array function to append an array's elements to another array
If I have one array, and I want to append the contents of an arbitrary array to
it, and I don't need the unmodified first array after appending the second
array's elements to it, I have three options.
First, I can use Array.prototype.concat to create a new array consisting of the
first array, then the contents of the second. But this creates a new array
rather than mutating the first array, so it potentially wastes memory
proportional to the size of the first array, barring complicated heuristics to
recognize and avoid the waste. Potentially worse, if any element of the second
array is an Array, instead of that array being appended, its elements will be
appended.
Second, I can use Array.prototype.push:
Array.prototype.push.apply(firstArray, secondArray);
This avoids the memory-wastefulness concern, and it doesn't treat Array items
specially. But it introduces a third concern: the JavaScript stack size limit,
if the second array contains a particularly large number of elements. This
might manifest itself as causing a stack overflow exception, or it might cause
only some of the elements of the second array to be appended (an arguably buggy
mitigation mechanism, but one some engines use, at least currently).
Third, I can use Array.prototype.splice, passing in |start = length| and
|deleteCount = 0|. But splice too encounters the stack size limit problem.
Worse, because its arguments are (start, deleteCount, newElt1, newElt2, ...),
constructing the array of arguments with which to apply the splice method seems
to require complicated copy-on-write array-element-sharing to mutate the first
array without consuming twice the first array's memory, or some other tricky
scheme. For such schemes to be effective here, the programmer would have to
structure his code pretty carefully, being sure to only use
Array.prototype.unshift, say, to implement it. And there's a bootstrapping
problem to creating the array of arguments to supply to splice in order to
append the elements of an array to the first array.
I see no problem-free way to append an array's elements to another array
without doing it manually. That's not hard, but it's error-prone, and it's
much trickier to recognize and correctly optimize. I think there should be a
way to append elements of an arbitrarily sized array to another array, mutating
that array in-place, without consuming excess memory. I'm not too concerned
about its precise semantics or about what it's named. For a starting point
I'll propose Array.prototype.pushAll (or extend, following Python, but again, I
don't really care about the exact name right now):
Object.defineProperty(Array.prototype, pushAll,
{
enumerable: false, configurable: true, writable: true,
value: function pushAll(other)
{
use strict;
var t = ToObject(this);
var length = ToUint32(t.length);
var otherLen = other.length;
for (var i = 0, j = length; i otherLen; i++, j++)
t[j] = other[i];
t.length = j;
return void 0;
},
});
Comments? Suggestions? Requests for changes?
I also had the thought that it might be nice to be able to push a subrange of
the elements of an array. You could do that by adding optional |start, length|
or |start, end| arguments to the method, with corresponding implementation
changes. I'm not sure whether this would be useful enough to warrant the
complexity, but it would be easy to add if people thought it made sense.
Jeff
___
es-discuss mailing list
es-discuss@mozilla.org
https://mail.mozilla.org/listinfo/es-discuss
Re: Wanted: standard Array function to append an array's elements to another array
It's perhaps worth noting that this problem also occurs with String.fromCharCode. I suspect the need for a version of |String.fromCharCode.apply(null, codesArray)| that always works, even for super-big |codesArray|, is rather smaller than for the similar Array.prototype.push concern. Jeff ___ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
