Math.minmax
- Improve performance
I doubt that this sequence of calls:
min = Math.min(min, value) max = Math.max(max, value)
Is slower than this:
[min,max] = Math.minmax([min,max,value])
Because while the former can get inlined by JIT, the latter can't, and on top, it allocates 2 objects which then have to be GC'ed.
On Thu, Jun 29, 2017 at 9:19 AM, Florian Bösch <pyalot at gmail.com> wrote:
Improve performance
I doubt that this sequence of calls:
min = Math.min(min, value) max = Math.max(max, value)
Is slower than this:
[min,max] = Math.minmax([min,max,value])
Because while the former can get inlined by JIT, the latter can't, and on top, it allocates 2 objects which then have to be GC'ed.
I was going to make that very point, backed by a jsPerf, but the jsPerf doesn't back it up: jsperf.com/two-calls-vs-one-returning-array It says the minmax is faster on a 10-entry array (it reports the separate calls as 46-48% slower on V8 and SpiderMonkey).
Now, that's comparing making calls to functions defined in userland, not ones provided by the engine, so that's an important difference. And there's basically no memory pressure, whereas in real life there may be. And it's a synthetic benchmark. But there we are.
-- T.J. Crowder
A proper test would do this on a few hundred million elements interrupted every 16.6ms with a RAF so as to give the GC a chance to run and run about 30 seconds so as to trigger at least a couple GC cycles.
The results is expected (in the naive way at least). You loop just one time instead of two on the array.
Now I'm not enough involved in how JS engines work at a lower level to make more hypothesis.
On 6/29/17 1:49 AM, T.J. Crowder wrote:
I was going to make that very point, backed by a jsPerf, but the jsPerf doesn't back it up: jsperf.com/two-calls-vs-one-returning-array It says the minmax is faster on a 10-entry array (it reports the separate calls as 46-48% slower on V8 and SpiderMonkey).
See jsperf.com/two-calls-vs-one-no-destructuring/1 which is the same as the above-linked testcase but doesn't do destructuring of an array into an arglist and the collapsing of an arglist into an array for every call. In that one the two-call version is in fact faster.
That is, the cost of allocating and filling the two-element return value array is much smaller than the cost of allocating and filling the 20-element array. Since the two-call testcase in jsperf.com/two-calls-vs-one-returning-array does the latter twice, it ends up slower than the version that only does it once.
On Fri, Jun 30, 2017 at 7:53 AM, Boris Zbarsky <bzbarsky at mit.edu> wrote:
On 6/29/17 1:49 AM, T.J. Crowder wrote:
I was going to make that very point, backed by a jsPerf, but the jsPerf doesn't back it up: jsperf.com/two-calls-vs-one-returning-array It says the minmax is faster on a 10-entry array (it reports the separate calls as 46-48% slower on V8 and SpiderMonkey).
See jsperf.com/two-calls-vs-one-no-destructuring/1 which is the same as the above-linked testcase but doesn't do destructuring of an array into an arglist and the collapsing of an arglist into an array for every call. In that one the two-call version is in fact faster.
That is, the cost of allocating and filling the two-element return value array is much smaller than the cost of allocating and filling the 20-element array. Since the two-call testcase in jsperf.com/two-calls-vs-one-returning-array does the latter twice, it ends up slower than the version that only does it once.
I was just sticking to how Math.min and Math.max work (e.g., they use
discrete arguments). A better test probably would have passed them those
args discretely rather than as ...nums.
Interestingly, V8 still does the minmax faster than the separate calls to min and max in your test, rating the two calls version 21% slower than the minmax. As you noted, SpiderMonkey runs the minmax much slower than the two calls (61%).
This is all a bit by-the-bye, performance is unlikely to be a big deal for minmax in the typical case, and when it is in a specific situation, a tailored solution to that specific situation would probably be best. The number of numbers being tested would have to be very large for two native-code loops to be the bottleneck in the code. I'd just drop the performance motivation from the proposal.
-- T.J. Crowder
I just removed performance from goals of the proposal, given how it seems to depend about how min and max are called.
Thanks for feedbacks.
I'm honestly not convinced how this is actually useful. And also, just
based on the name, I'd expect it to be something closer to [min, max] = Math.minMax(foo, bar), which could effectively compile down for
integers to up to two register movs followed by a single cmpxchggt
(compare and exchange if greater than).
Not that engines couldn't similarly reduce this equivalent, but engines are usually way dumber than they could be with some of the more complex reductions:
// This should compile to the same thing assuming `foo` and
// `bar` are both integers, but no engine AFAIK does this.
var min = foo, max = bar;
if (min > max) { var tmp = max; max = min; min = tmp }
// This should also compile similarly, provided `foo` and `bar`
// are both integers and constant reference reads.
var min = Math.min(foo, bar)
var max = Math.max(foo, bar)
Isiah Meadows me at isiahmeadows.com
Looking for web consulting? Or a new website? Send me an email and we can get started. www.isiahmeadows.com
Even if I think it should be a performance improvement, the main goal actually is to improve readability and conciseness of the code.
When you say "I'd expect it to be something closer to [min, max] = Math.minMax(foo, bar)", are you saying that minmax (or minMax) should only take two arguments ? I think that if it's implemented like this, it would obviously be not so usefull.
Some questions about the proposal process :
-
Are champions reading and commenting this feed ? Can we have a comment on this proposal maybe ?
-
Is the purpose of proposals to question how the proposal would be implemented by JS engines ?
-
Talking about tests previously quoted : Is an JS implementation of this proposal just approaching how efficient (or not) would be the proposal after being implemented by JS engines ?
Thanks for your feedback.
To me it seems like minmax is less readable - between repeating the RHS (with min and max) vs condensing them and having nonobvious LHS syntax (with minmax), I'd prefer the current situation.
It's more concise and if you're comfortable with destructuring assignment syntax, I think it's also more readable.
Whatever, differents folks, differents strokes. This proposal offer the possibility to reduce by two the length of a "get min and max" operation, and probably improve the performance of the operation when used with large amounts of numbers.
To have that be worth a language change, I think you'd have to make a compelling argument that the performance of Math.min and Math.max, used together on the same large set of numbers, was sufficiently slow as to make widely used use cases untenable without your proposal.
I'd be happy to review the results of that research.
You can run three tests here : esbench.com/bench/595c1b1899634800a03488b9
Running minMax polyfill and min max with two instructions on 2, 1000 or 100000 numbers.
Thanks, that's helpful.
The results I get range from a 2x improvement for 2 numbers, to a 3x improvement for 1000 numbers (both 100K number examples get me a RangeError in Safari).
What concrete use cases are possible with the performance of minmax that aren't possible with a separate min and max?
The result is not so obvious on V8 (x0.9 on 2 numbers and x2 improvement for 1000 and 100000 numbers).
It would be helpful, for example, in the case of system monitoring. A friend of mine receives raw datas and he regularly needs to get min and max to handle those datas.
He could do that with both min and max, but he clearly told me that when he's working with one year of QoS datas, x2 improvement can't be ignored.
On 7/4/17 9:34 PM, Jordan Harband wrote:
The results I get range from a 2x improvement for 2 numbers, to a 3x improvement for 1000 numbers
Again, did you test without the array destructuring and recreation bits? I expect those dominate here, just like in the jsbench benchmarks posted before.
Sorry for the delay!
I just added some benchmarks, please tell me what you think about them!
Is there anybody here?
Doesn't performance matter?
As adviced by annevk on IRC, I'm gonna explains the results better.
Minmax is more efficient that a min and a max : you loop one time instance of two. Seems logic.
To not destructurate the array of arguments is of course better because at the end, by destructurating you're gonna work on an arguments array.
I actually made the proposal this way to fit with existing min and max (taking arguments separately). Gonna edit the proposal to accept an array directly.
Don't know what Boris mean when he talks about recreation bits
Using both min and max is a regular use case of these functions, so x2 improvement on this is an existing need. I mentioned an example of use above.
On 10/2/17 7:10 AM, Xavier Stouder wrote:
Don't know what Boris mean when he talks about recreation bits
Fwiw, it looks like the code at esbench.com/bench/595c1b1899634800a03488b9 does not have the array recreation bits (function whatever(...args)) that earlier benchmarks for this had.
I would just use reduce for this. Reason: I think any multi var result format is a little messy. I find it better to let the dev decide on the result format, e.g.:
const minMax =
array.reduce(
(accumulator, currentValue)=>{
return {
min: Math.min(currentValue, accumulator.min),
max: Math.max(currentValue, accumulator.max)
}
},
{
min: Infinity,
max: -Infinity
}
)
Good thing is, this can easily be refactored to accept arrays with objects that contain the values, instead of just an array of numbers, as well as the ability to calculator other accumulated values (e.g. mean average etc.) in the same call.
Do let me know if you think I'm missing the point
I think your approach is fine, but just to be that guy I'll condense it some more (could be output as a hash but, if we're going to condense, well...):
const minMax = arr => arr.reduce(
([ min, max ], curr) => [ Math.min(curr, min), Math.max(curr, max) ],
[ Infinity, -Infinity ]
)Oh, and of course if I'm going to be that guy I should immediately post a slightly better version just to annoy people more:
const minMax = (arr=[]) => arr.reduce(
([ min=Infinity, max=-Infinity ], curr) => [ Math.min(curr, min),
Math.max(curr, max) ], []
)No problem Boris, I edited this times a long time ago.
Naveen, you missed he point. In fact, I just added your code the benchmark (link aboce) and it has catastrophic performances.
Same for Michael. Useless to not use a reducer instead of Math.min and Math.max if it has worth performance.
Just to be clear, the fact is that your function approximately costs: Math.min: one loop over the array Math.max: one loop over the array Math.minMax: one loop over the array
Math.minMax do in one pass what Math.min and Math.max do in two passes. That's the key point.
On Mon, Oct 2, 2017 at 8:49 AM, Xavier Stouder <xavier at stouder.io> wrote:
No problem Boris, I edited this times a long time ago.
Naveen, you missed he point. In fact, I just added your code the benchmark (link aboce) and it has catastrophic performances.
Ya, that's a lot of array creations, not to mention the callback in the reduce()...
const minMax = (arr=[]) => { let result=[Infinity, -Infinity]; for( let
i=0;i < arr.length;i++ ) {
result[0] = Math.min(arr[i], result[0]);
result[1] = Math.max(arr[i], result[1]);
}
return result;
}
although I suspect this will be faster...
const minMax = (arr=[]) => { let result=[Infinity, -Infinity]; for( let
i=0;i < arr.length;i++ ) {
result[0] = arr[i] < result[0] ? arr[i]:result[0];
result[1] = arr[i] > result[1]? arr[i]: result[1];
}
return result;
}
i've attached some screenshots to explain why Math.minmax has little performance impact on a webapp as a whole.
here's a screenshot showing it takes 1) 30ms to run a single Math.min() operation one million times and 2) 50ms to run both Math.min() and Math.max() one million times. assuming the hypothetical Math.minmax() ideally runs as fast as Math.min(), it will save you 20ms for every one million operations.
/*jslint node: true*/
/*globals Float64Array*/
'use strict';
var ii, list1, list2, result, time;
list1 = new Float64Array(1000000);
list2 = new Float64Array(1000000);
for (ii = 0; ii < 1000000; ii += 1) {
list1[ii] = Math.random();
list2[ii] = Math.random();
}
// pre-trial run to get vm-optimization shenanigans out of the way
for (ii = 0; ii < 1000000; ii += 1) {
result = Math.min(list1[ii], list2[ii]);
result = Math.max(list1[ii], list2[ii]);
}
time = Date.now();
for (ii = 0; ii < 1000000; ii += 1) {
result = Math.min(list1[ii], list2[ii]);
}
console.log((Date.now() - time) + 'ms - 1,000,000 min calculations');
time = Date.now();
for (ii = 0; ii < 1000000; ii += 1) {
result = Math.min(list1[ii], list2[ii]);
result = Math.max(list1[ii], list2[ii]);
}
console.log((Date.now() - time) + 'ms - 1,000,000 min and max calculations');
here's a screenshot showing how long it takes to load a google-search webpage (arguably the fastest-loading real-use webpage in the world), under ideal conditions with pre-caching and all. as you can see, it takes on average ~700ms to load the entire page with caching.
think about it. the performance savings of 20ms for one million Math.minmax operations is at best gonna improve your webapp performance by less than 3% (assuming a 700ms load-time is all the webapp does).
Ah yes, woods, I was looking at the trees.
Still, to carry on with the concise style:
const minMax = (arr=[]) => arr.reduce(
([min=Infinity, max=-Infinity], curr) => [ min < curr ? min : curr, max >
curr ? max : curr ], []
)
JDecker: Just added your solution on the benchmark, it beats every others solution and it's a elegant solution.
Kai Zhu: We can't see the screenshot. But please take in consideration that it's been a long time that ECMAScript isn't only used in webapp, and that some of applications using it can eat more than a million numbers.
Taking a step back from the details of this proposal, I have some thoughts about why it seems to be struggling to find support.
In no particular order, I would say this proposal
- relies on microbenchmarks, which can be misleading tomdale.net/2017/07/adventures-in-microbenchmarking
- dis Amdahl's Law en.wikipedia.org/wiki/Amdahl's_law, by pretending that real-world JS CPU usage is commonly/ever dominated by min/max computations
- replaces two O(n) loops with another O(n) loop that does slightly more work on each iteration, resulting in no complexity improvement, and a fairly modest (< 2x) constant factor improvement
- doesn't seem to provide usability/learnability improvements for any particular group of JS developers (for example, novice programmers)
- doesn't seem to prevent any common bugs in JS code
As a member of TC39, I regret that we have not provided a clearer set of criteria for what it takes to get a new function into the standard library. While I can't speak for the committee as a whole, my suspicion is that this proposal is unlikely to meet that standard. It's a fine idea, but so are many other functions that you can implement in a normal (non-standard) library.
I would also challenge the committee to think about (or link to!) any concrete written criteria that someone with an idea for a proposal could use to assess its chances of acceptance. Imagine how much time we could save!
Ben
I would be curious about the reduce version that doesn't create a new object/array on every iteration:
const minMax =
array.reduce(
(accumulator, currentValue)=>{
accumulator.min = Math.min(currentValue, accumulator.min);
accumulator.max = Math.max(currentValue, accumulator.max);
return accumulator;
},
{
min: Infinity,
max: -Infinity
}
)
If you could let me know the relative performance of this in the benchmark it would be great.
can I ask why nobody is using Math.min/max signature at their full potentials ?
const [min, max] = [
Math.min.apply(null, array),
Math.max.apply(null, array)
];
also, why are benchmarks using Date.now() instead of the more accurate
performance.now() or the dedicated console.time('bench') / console.timeEnd('bench') utility?
Another important characteristic we look for in proposals is orthogonality: en.wikipedia.org/wiki/Orthogonality#Computer_science, en.wikipedia.org/wiki/Orthogonality#Computer_science
const minMax = (arr=[]) => { if( arr.length==1 ) return [arr[0],arr[0]];
const result=[Infinity, -Infinity];
for( let i=0;i < arr.length;i++ ) {
result[0] = arr[i] < result[0] ? arr[i]: ((result[1] = arr[i] >
result[1]? arr[i]: result[1]), result[0]) ;
}
return result;
}
Would be slightly faster to only do the max if it's not a min. Which fails
if there's only 1 number to compare.On Mon, Oct 2, 2017 at 6:38 PM, Ben Newman <benjamin at cs.stanford.edu> wrote:
I would also challenge the committee to think about (or link to!) any concrete written criteria that someone with an idea for a proposal could use to assess its chances of acceptance. Imagine how much time we could save!
That would be fantastic. When I brought this up earlier this year, the answer seemed to be that there were none and that there was no consensus amongst the committee.
-- T.J. Crowder
If you're reading on esdiscuss.org, that link got munged and I don't seem able to edit my posts anymore. Here's a shortened version: goo.gl/fioZmj
-- T.J.
Thank you for your answer Ben! I hope that TC39 will make the set of criteria clearer for a bright futur.
Thank you for your answer Ben! I hope that TC39 will make the set of criteria clearer for a brighter futur.
on tc39 criterias, this applies more to language-spec than library changes, but i think another criteria that can showstop stage 2-3 proposals is finding out whether a new syntax creates subtle engine de-optimizations that breaks the web.
around mid-2016, i recall sites like github.com and npmjs.com using readme.md as their landing-page would frequently freeze and crash in chrome. each time, i basically could not use chrome to visit these sites for a week or so until chrome auto-updated. this issue may or may not be related to javascript, but it hardened my conservative-perspective on proposals that can negatively impact the web.
oh fyi, here are 2016 screenshots of the crash in chrome i took when reporting it (showing it works fine in canary, but broken in stable)
Had a relatively simple idea tonight : Xstoudi/proposal-math-minmax
Please take a look, comment and tell me if you're an interested tc39 champion.