native functions often have to cover complicated edge cases from the ECMAScript specification [...] By optimising for the 99% use case, fast.js methods can be up to 5x faster than their native equivalents.
author of the library here. The native implementations have to follow the spec exactly, which means that they have to guard against specific edge cases. The reimplementations in fast.js do not follow the spec exactly, they optimise for 99.9% of use cases and totally ignore the 0.1%. This, combined with the fact that the JS is JITed straight into machine code anyway gives fast.js a significant advantage - it does less work and so is faster.
Why would it be meaningless? The comparison shows that fast.js works for what it was intended to do, it's doing stuff faster than it's native counterparts.
To say the comparison is meaningless is a little unfair.
Generally yes, the results are not expected to be 100% equivalent as these routines do not produce the same results for some inputs.
But as the range of inputs for which the results are expected to be the same is defined, the comparison is meaningful within those bounds (which covers quite a lot of the cases those functions will be thrown at).
They do slightly different varieties of apples -- ignore some BS edge cases that few ever use in the real world.
If I rewrite project X into X v2 and throw away 2-3 seldom used features in the process, it doesn't mean that comparing v1 and v2 is meaningless. You compare for what people actually use it for -- the main use cases. Not for everything nobody cares about.
From a computer science perspective it is formally 'meaningless' because the performance improvement was made by changing the requirements, not by a novel algorithm or data structure. This is always possible, but it ignores the original constraints of the problem and hence doesn't shed any additional meaning on how to solve the original problem.
From a programmer perspective, that might not change the fact that it's useful. It has 'meaning' to the programmer in that it helps us solve a particular problem. Typically, app programmers are not as concerned with how the problem was solved.
I like the library, but to avoid this kind of criticism, don't call it a reimplementation. Call it what it is, an alternative library of functions.
>From a computer science perspective it is formally 'meaningless' because the performance improvement was made by changing the requirements, not by a novel algorithm or data structure.
I've studied computer science and I don't recall seing any such "formal" definition of meaninglessness.
Nothing in computer science tells you you have to have the exact same behavior in 2 APIs in order to measure some common subset of functionality. You can always restrict your measuremnts to that. Computer science is not that concerned with APIs anyway.
So you can use very formal computer science to compare the performance in big-O of X vs Y implementation of the common supported cases (namely, contiguous arrays).
>This is always possible, but it ignores the original constraints of the problem and hence doesn't shed any additional meaning on how to solve the original problem.
There's no "original" problem that one has to take wholesale. There are use cases, and some care about X, others about Y.
Scientific papers in CS compare implementations of things like filesystems, memory managers, garbage collectors etc ALL THE TIME, despite them not having the same API and one having some more or less features. They just measure what they want to measure (e.g performance of X characteristic) and ignore the others.
Developers use forEach to apply a function to every element in an array. That is the main use case.
This faster version fails on some arrays (any array that isn't contiguous). This is a bug, not a feature. The library user is now responsible for checking that the array is contiguous before using the faster function.
Is it documented somewhere whether array returning/manipulating functions cause non-contiguity?
>This faster version fails on some arrays (any array that isn't contiguous). This is a bug, not a feature.
I'd argue it's actually a future.
For one, it's not forEach for one. It doesn't mask the native implementation. It exists in its own namespace.
Second, it's not like forEach doesn't have its own problems. Like not being backwards compatible to older browsers without shims.
Third, nobody (or very very small values of "somebody") use non contiguous arrays with forEach.
The speed is a great feature, especially if you don't sacrifice anything to achieve it.
>The library user is now responsible for checking that the array is contiguous before using the faster function.
The library user already knows if he is using contiguous arrays or not. After all, it can fuck him over in tons of other cases, even a simple for loop, or a length check, if he treats one like the other. So it's not like he doesn't already have to be vigilant about it.
Thanks, I hadn't come across this one before. Looks like they are expecting some API changes in the future though so I'll just bookmark this one for now.
I'm interested in what those edge cases are, to say it works in 99% of the cases but provide no caveats makes me think that I might be surprised by something if I use it.
Javascript. The language where you can reimplement basic functions such as map, each, reduce (which by the way are still available for objects in 2014) and have them be faster than their native counterparts.
It might be that I don't particularly like the language. but it's kind of frightening that we're building the world on that stuff.
Why isn't the native version doing less work? Isn't that what you expect from a language design, that the native version will be as close to optimal as possible in the first place?
Fair enough. Why doesn't the title of the post say so then? "Faster incomplete versions of Javascript native functions" would have been a better summary.
Or even discuss the fact that if this library is good enough for people to use then maybe the edge cases that the native versions are covering might not be so useful after all?
The native versions have to/should 100% support the language spec and historical behavior. In this instance, it means they can't optimize much that iterates over a sparse array.
That's not really fair, the author of this implementation is non-complainant with the spec by dropping edge cases in order to achieve these improvements.
A lot of it has to do with crossing boundaries between C++ and the JIT'd code and losing things like inlining. Doesn't really have to do with JS warts.
> In fact, native functions often have to cover complicated edge cases from the ECMAScript specification, which put them at a performance disadvantage.
Doing something complex on a simple platform requires complex code. https://en.wikipedia.org/wiki/Turing_tarpit Having a more complex platform can make things a lot easier for the programmer.
I can make the implementation simpler if the underlying specification is simpler. If a language is full of edge cases, it was not designed carefully. If there exists a significantly faster implementation in a significantly slower language that covers 99% of the specification, I'd look for opportunities to simplify.
On one hand, I'm a big proponent of "know your tools". I'll gladly use a fast sort function that falls apart when sorting arrays near UINT32_MAX size if I'm aware of that caveat ahead of time and I use it only in domains where the size of the array is logically limited to something much less than that, for example.
But on the other hand, I write operating system code in C. I need to know that the library functions I call are going to protect me against edge cases so I don't inadvertently introduce security holes or attack vectors.
If I know that some JS I'm interacting with is using fast.js, maybe there will be some input I can craft in order to force the system into a 1% edge case.
The lesson here is probably "don't use this for your shopping cart", but we need to be careful deriding Javascript's builtins for being slow when really they're just being safe.
This is actually unlikely to be a problem. The edge cases ignored here are actually the same as those ignored by underscore.js, which is obviously a very popular library.
I agree that it's unlikely to be a problem...until your site gets popular and a .01% corner case becomes a weekly occurrence or until someone sees that you're using fast and exploits an attack vector.
it's not that kind of edge case. It simply means that some very uncommon constructs are not supported. If you never use those constructs, which basically nobody does, then it will never fail. (and in fact the failure mode is pretty soft and unlikely to crash your application). If your code worked with this once, it will always work.
I think by all means use this for a shopping cart - it's namespaced by require (say under 'fast' as in the README) - you are, for all intents and purposes, calling just some library which just happens to reimplement JS builtins as its mode of operation.
It may even be _easier_ to determine the behaviour of these functions than builtins, since determining how fast works just means reading its source whereas to determine builtins' behaviour you must read the ECMAScript specification and then hope[1] that the browser actually matches it perfectly!
[1]: or read the JS engine source, but that's a whole lot more work. :P
I'm not sold that this will provide any user-measurable increase in performance. If you are sold by some personal app benchmark, there is a good chance you are writing too much client side JS. And what is to say of other dependencies like jQuery, Bootstrap, Knockout, Angular, etc that do NOT use fast.js under the hood? It seems that the only real "win" I get is a fast "map" command, which, IFAIK, has NEVER been the problem of writing good software.
Now, if fast.js made sure we had the correct requirements, no distractions, clear milestones, and a dedicated team with no turn over, I'd import it in a second.
No mention of relative memory usage though. I've been bitten by this kind of thing too many times in node in the past to not wonder about it here. Especially for such core functions.
I did this with CPython and psyco. It turns out that writing map() in python was faster than the builtin C version. Because the JIT was allowed to do some tricks, like inlining the function.
Premature optimization is the root of all evil -- Knuth
V8 has excellent profiling tools (exposed in chrome and in nodejs) which should be used first before considering fallbacks. Before seeking a third party library, be sure to check if the function is called many times or is taking a long time.
For example, I found that throwing map out and using a straight array (avoiding the function calls entirely) can be up to 50% faster than using the functional suspects. But that, in the eyes of some people, unnecessarily adds complexity to the code and may not be worth changing
I think it's a bit unfair to label using a known fast library over a known slow library as "premature optimization". I would much rather start a project or feature with the coding standard of, "use the fast ones", rather than have to go back through all the code, profile it, and replace only the ones hurting performance.
Yeah but it could be a premature optimization if you blindly decided to use a library because the cost of having to download it (in the case of browser JS) and/or parse (in the case of server JS) an extra script file may outweigh its performance benefits.
> start a project or feature with the coding standard of, "use the fast ones"
Ironically, that involves certain habit changes that completely obviate the library:
1) avoid map. Just create an array and write a for loop directly at the callsite, putting the code in a block rather than as a separate function
2) avoid indexOf. For single-character indexOf, it's much faster and much more efficient to match the character code (loop and check charCodeAt) than to use the function form
3) avoid lastIndexOf. Same as indexOf, except you loop in the opposite direction.
4) avoid forEach. Learn to love the for loop.
5) avoid reduce. See forEach
Anyone embracing fast.js is sacrificing some performance to begin with.
My opinion is that JavaScript applications aren't losing that much performance by the use of lodash or fast.js but the gain in code brevity and readability more than makes up for any slight performance reduction. (Especially in a large web app where the tiny lodash library can save you many KB of boilerplate).
And with regard to performance, for most Node.js code / webapps if you have a loop with so many iterations that _.map is significantly slower than a for loop then you might be doing something wrong.
The point of this library is that it provides the same behavior (for 99.99% of cases) and the same abstraction (so same readability / maintainability) as the functions it replaces, but with significantly better performance (for wildly varying degrees of "significantly" depending on usage).
I don't think the idea is that you profile your code and then micro-optimize it using this library. If you're doing that (which you should, for varying definition of "should"), then yes you will want to consider sacrificing the abstraction / brevity for performance.
However, this library seems like a handy way to maintain the abstraction, while gaining performance essentially for free without sacrificing anything worth mentioning. Then you profile (if you were going to / had time to / cared enough to) and optimize from a better starting point. Don't see anything wrong with that.
No, but using a non-spec compliant implementation across the board because "it's faster" is definitely premature optimisation. This is the sort of stuff that should be kept for performance critical bits, not used application wide.
It may be premature optimization to use a faster library when the faster library has known places where it differs from standard behaviour, and almost certainly lots of bugs.
I don't know much about fast.js in particular but in this case there might be an advantage of using the fast functions simply because they have simpler semantics. There are many bugs and inconsistencies that come up from people expecting that native methods behave the same as simple for-loops when they actually don't.
I'd agree with you if we were comparing apples to apples.
This is not the case with Fast.js as it breaks away from the language specifications. I'd much rather build, profile, and then optimize the few areas that actually require better performance than potentially introduce bugs by replacing the built-in methods.
> Premature optimization is the root of all evil -- Knuth
HN should have a bot that posts the full quote whenever this line is cited since it's so often abused.
"There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified."
Plus who said it was / should be used prematurely anyway?
> Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs
Isn't that essentially what I described? "Before seeking a third party library, be sure to check if the function is called many times or is taking a long time."
On the issue of this particular library: The problem is that you can do much much better by avoiding map, forEach and friends. The overhead of the function calls can be completely avoided by using a direct for loop at the callsite.
So yes, you may find it slightly faster to use this library rather than the native map, but with a small redesign you can avoid map entirely and get a massive performance win.
Swap to use a slightly faster function someone else already wrote, or rewrite your code. Seems like the latter is more guilty of premature optimisation if this library is fast enough for the particular use.
I think in most cases where you'd worry about JS array performance you should use actual numeric arrays [0] rather than the kitchen sink Array(). Also, I think those function abstractions have a pretty significant overhead?
I used this in a Firefox OS app, inside an implementation of Dijkstra's algorithm and an accompanying binary heap, and while I haven't run any rigorous benchmarks, I can say the runtime felt way better on my test phone when I rewrote the algorithm to use the typed arrays.
This is very often overlooked but extremely useful for implementations of fast algorithms in JavaScript that should scale to a lot of input data.
regarding your edit, you're exactly right, of course a for loop will be faster. Sometimes you really do need a function call though, in which case fast forEach and map implementations become more useful.
The next step for fast.js are some sweet.js macros which will make writing for loops a bit nicer, because it's pretty painful to write this every time you want to iterate over an object:
var keys = Object.keys(obj),
length = keys.length,
key, i;
for (i = 0; i < length; i++) {
key = keys[i];
// ...
}
I'd rather write:
every key of obj {
// ...
}
and have that expanded at compile time.
Additionally there are some cases where you must use inline for loops (such as when slicing arguments objects, see https://github.com/petkaantonov/bluebird/wiki/Optimization-k...) and a function call is not possible. These can also be addressed with sweet.js macros.
To be fair, it's not obvious if you're not a JS expert: coming from some other language, you could naively assume that function call gets inlined, with no overhead.
A few months ago, I tried some image processing with JS and the canvas object (big Arrays).
They have a structure like image[pixel].color
What I found was, always traversing the object structure was much slower than putting every pixel color as an argument in a function, that gets called every iteration.
So I had the impression, reasonable simple function, like a greyscale filter, get inlined by engines like V8.
Most of the array methods are explicitly defined in terms of indexing rather that iterators, so for(of) is incorrect. On the other hand indexing is still faster than iteration in the major implementations.
My comment were intended as a direct reply to phpnode's code, 'ignoring' the rest of the thread.
How do you mean when you state that for(of) is incorrect?
Perhaps this 'example' clears something up?
« for (value in {a:1,b:2,c:3,d:4,e:5}) console.log(value)
» undefined
"a"
"b"
"c"
"d"
"e"
« for (value of {a:1,b:2,c:3,d:4,e:5}) console.log(value)
× TypeError: ({a:1, b:2, c:3, d:4, e:5})['@@iterator'] is not a function
the only issue is i'd like to differentiate between iterating arrays and objects at the syntax level. Coffeescript uses `in` for arrays and `of` for objects, but I agree that becomes confusing. Open to other suggestions!
I've been spending some time thinking about CoffeeScript's choice for `in` and `of` and I think I have the answer: they should be more regular. One (probably `of`) should be used for the keys/indexes and the other (probably `in`) should be used for contents.
These are legal CoffeeScript examples:
for key, value of object
if key of object
for value in array
if value in array
for index, value of array
if index of array
The issue with coffeescript is that it uses the opposite syntax to JS - `in` for arrays instead of objects. ES6 introduces the `of` keyword for real iterators so i don't really want to use that for either of them. It's tricky.
There are other options but they're verbose
every element as key, value from arr {
console.log(key, value);
}
every property as key, value from obj {
console.log(key, value);
}
every [key, value] from arr {
console.log(key, value);
}
every {key, value} from obj {
console.log(key, value);
}
every [key] from arr {
console.log(key);
}
every {_, value} from obj {
console.log(value);
}
Looks a bit cramped to me but I get the impression that array comprehension is one of the major reasons that people use Coffeescript, so perhaps it's not too much trouble?
There's also the issue with some fonts making it hard to differentiate between { and [ but it's an idea that might be worth to think about at least.
I quite like this suggestion. If we flip the key, value around to make it inline with what forEach etc do, then we don't need the placeholder for iterating without the key:
fast-each [value] from arr {
}
fast-each {value} from obj {
}
fast-each [value, key] from arr {
}
fast-each {value, key} from obj {
}
The disadvantage is that this looks like array comprehension but isn't.
Alternative:
fast-properties key, value from obj {
}
fast-elements index, value from arr {
}
fast-properties value from obj {
}
fast-elements value from arr {
}
I actually didn't get any speedup with that one -- looks like V8 can optimize that already. But you're right, that's an important one on some browsers.
You can squeeze out another factor of 2 with typed arrays:
var input_typed = new Uint32Array(input)
exports['numeric typed array'] = function() {
var acc = 0;
for (var j=0; j<input_typed.length; ++j) {
acc += input_typed[j];
}
}
✓ Array::forEach() x 1,999,244 ops/sec ±2.93% (84 runs sampled)
✓ fast.forEach() x 5,161,137 ops/sec ±2.05% (85 runs sampled)
✓ explicit iteration x 27,851,200 ops/sec ±1.32% (86 runs sampled)
✓ explicit iteration w/precomputed array limit x 28,567,527 ops/sec ±1.33% (86 runs sampled)
✓ numeric typed array x 42,951,837 ops/sec ±0.97% (88 runs sampled)
Winner is: numeric typed array (2048.40% faster)
And probably more still if you can figure out the asm.js incantation that makes everything statically typed.
The optimisation mentioned by the grandparent is specific to looping overso-called "live" collections of the DOM. NodeList [0] is sometimes a live collection, and is the return type of querySelectorAll, so it's likely you've dealt with this type of collection.
The reason it incurs an overhead is because the DOM is traversed every single time the property is read, to ensure nothing has changed. You can see why caching the length is a reasonable optimisation, as you're unlikely to be modifying the collection while looping.
Exactly. Although, I am curious if there's a reason the JS engine (possibly working with the DOM implementation) can't optimize that to one look-up, if the JS in the loop doesn't change that part of the DOM or call anything that forces it to yield.
I suspect a lot of the optimization opportunity in browsers today is less about JS or DOM in isolation but more about ways they could work together to improve situations like this one.
(Note: I understand this one is solvable by a proficient/attentive developer, but not all developers are like that, and not all such DOM/JS transition problems are as easily solvable from your JS code)
It's fairly well-known that Array#forEach is up to an order of magnitude slower than a for-loop, across browsers. The usual reason given is the overhead of invoking a closure from the VM. A JS implementation of forEach ought to be somewhere in the middle.
The speed-up for "concat" is surprising to me. I wonder if it holds for "splice" and if that is true across browsers.
A while back I was programming for a naive but well-written JS interpreter for set top box apps, where map was generally being avoided because of performance.
I wrote quite a fast "map" (along with the others) that looked a bit like:
exports.map = function fastMap (subject, fn, thisContext) {
var i = subject.length,
result = new Array(i);
if (thisContext) {
while (i--) {
result[i] = fn.call(thisContext, subject[i], i, subject);
}
} else {
while (i--) {
result[i] = fn(subject[i], i, subject);
}
}
return result;
};
I'm not sure if I just used "result = []", but on modern browsers I think that'd be recommended. But yeah, if you're programming for a web browser then using another impl of map is probably going to be a waste of time.
no, but I could probably have worded it better. What I mean to say is that if you do this in JS:
function add (a, b) {
return a + b;
}
and this in C:
int add(int a,int b)
{
return a + b;
}
you're going to get essentially the same performance.
The latter sentence you quoted refers to the specific builtin functions that fast.js re-implements. So we first get close to native performance in JS, then we beat the builtin functions by doing less work overall.
So looking at this in Firefox, the "fast" version underperforms the native one for forEach, bind, map, reduce, and concat. It outperforms native for indexOf/lastIndexOf.
In Chrome the "fast" version does better than the native one for indexOf, lastIndexOf, forEach, map, and reduce. It does worse on bind and concat.
It's interesting to compare the actual numbers across the browsers too. In Firefox, the numbers I see for forEach are:
"fast": 47,688
native: 123,187
and the Chrome ones are:
"fast": 71,070
native: 20,112
Similarly, for map in Firefox I see:
"fast": 17,532
native: 62,268
and in Chrome:
"fast": 38,286
native: 19,521
Interestingly, these two methods are actually implemented in self-hosted JS in both SpiderMonkey and V8, last I checked, so this is really comparing the performance of three different JS implementations.
So the forEach magic that is so much faster is... a normal for loop:
exports.forEach = function fastForEach (subject, fn, thisContext) {
var length = subject.length,
i;
for (i = 0; i < length; i++) {
fn.call(thisContext, subject[i], i, subject);
}
};
I knew that forEach was slower than a normal for loop but I was expecting something more.
Reminds me of this comment by Petka Antonov on native V8 Promises being way slower than Bluebird[1]:
>I'd expect native browser methods to be an order of magnitude faster.
Built-ins need to adhere to ridiculous semantic complexity which only gets worse as more features get added into the language. The spec is ruthless in that it doesn't leave any case as "undefined behavior" - what happens when you use splice on an array that has an indexed getter that calls Object.observe on the array while the splice is looping?
If you implemented your own splice, then you probably wouldn't even think of supporting holed arrays, observable arrays, arrays with funky setters/getters and so on. Your splice would not behave well in these cases but that's ok because you can just document that. Additionally, since you pretty much never need the return value of splice, you can just not return anything instead of allocating a wasted array every time (you could also make this controllable from a parameter if needed).
Already with the above, you could probably reach the perf of "native splice" without even considering the fact that user code is actually optimized and compiled into native code. And when you consider that, you are way past any "native" except when it comes to special snowflakes like charCodeAt, the math functions and such.
Thirdly, built-ins are not magic that avoid doing any work, they are normal code implemented by humans. This is biggest reason for the perf difference specifically in the promise case - bluebird is extremely carefully optimized and tuned to V8 optimizing compiler expectations whereas the V8 promise implementation[2] is looking like it's directly translated from the spec pseudo-code, as in there is no optimization effort at all.
> Additionally, since you pretty much never need the return value of splice, you can just not return anything instead of allocating a wasted array every time
That kind of optimization seems easily done with a builtin as well: have an option to return the array, and only do so if the JavaScript engine indicates that the calling code actually uses the return value.
That seems like something well suited to compile-to-js languages like Coffeescript. It could substitute cases as you mentioned with fast.js equivalent functions.
This itself reminds me of similar performance issues hidden in C++. The float->int cast on x86 with Microsoft's compiler called a helper library function 'ftol'. Turns out this does loads of stuff to be spec compliant. Replacing it with a single not-spec-but-works-for-us x86 assembly instruction to convert was way faster.
So not just JS - it seems language built-ins are often slowed down by bureaucratic spec compliance, and hand-rolling code can help you get a speedup.
From what I remember, a primary reason Lodash was created as a fork of underscore was to address the "solution" that fastjs provides - underscore had problems with edge cases like sparse arrays, so lodash was created as a spec-compliant alternative. http://stackoverflow.com/a/13898916/1869609
lodash is as fast as fast: see the JSPerf results posted elsewhere. John manages lodash well. He has managed it well for quite a while. Why switch to another library with no track record for little or no gain?
I think the forEach issue is a bad example, and something that could (and arguably should) be handled by the native implementation. The reason they get faster execution here is by breaking the spec.
A native implementation could have a single flag associated with the array recording whether it is sparse, and use the more efficient code path given here in the common space where it's non-sparse.
The point I took away from that one example was: The native functions have to deal with lots of edge cases, which causes them to be slower. By implementing similar functions which, per their spec, do not handle those edge cases, we can gain a significant performance improvement.
Hey I'm not bashing here, I thing it's kind cool for learning purposes attempts to do such thing, but I truly wonder if there is an actual production need for such thing.
167 comments
[ 3.6 ms ] story [ 194 ms ] threadThe two functions do not necessarily work the same way - the native implementation handles edge cases that the fast version drops.
Generally yes, the results are not expected to be 100% equivalent as these routines do not produce the same results for some inputs.
But as the range of inputs for which the results are expected to be the same is defined, the comparison is meaningful within those bounds (which covers quite a lot of the cases those functions will be thrown at).
It's not like they do apples and oranges.
They do slightly different varieties of apples -- ignore some BS edge cases that few ever use in the real world.
If I rewrite project X into X v2 and throw away 2-3 seldom used features in the process, it doesn't mean that comparing v1 and v2 is meaningless. You compare for what people actually use it for -- the main use cases. Not for everything nobody cares about.
From a programmer perspective, that might not change the fact that it's useful. It has 'meaning' to the programmer in that it helps us solve a particular problem. Typically, app programmers are not as concerned with how the problem was solved.
I like the library, but to avoid this kind of criticism, don't call it a reimplementation. Call it what it is, an alternative library of functions.
I've studied computer science and I don't recall seing any such "formal" definition of meaninglessness.
Nothing in computer science tells you you have to have the exact same behavior in 2 APIs in order to measure some common subset of functionality. You can always restrict your measuremnts to that. Computer science is not that concerned with APIs anyway.
So you can use very formal computer science to compare the performance in big-O of X vs Y implementation of the common supported cases (namely, contiguous arrays).
>This is always possible, but it ignores the original constraints of the problem and hence doesn't shed any additional meaning on how to solve the original problem.
There's no "original" problem that one has to take wholesale. There are use cases, and some care about X, others about Y.
Scientific papers in CS compare implementations of things like filesystems, memory managers, garbage collectors etc ALL THE TIME, despite them not having the same API and one having some more or less features. They just measure what they want to measure (e.g performance of X characteristic) and ignore the others.
This faster version fails on some arrays (any array that isn't contiguous). This is a bug, not a feature. The library user is now responsible for checking that the array is contiguous before using the faster function.
Is it documented somewhere whether array returning/manipulating functions cause non-contiguity?
I'd argue it's actually a future.
For one, it's not forEach for one. It doesn't mask the native implementation. It exists in its own namespace.
Second, it's not like forEach doesn't have its own problems. Like not being backwards compatible to older browsers without shims.
Third, nobody (or very very small values of "somebody") use non contiguous arrays with forEach.
The speed is a great feature, especially if you don't sacrifice anything to achieve it.
>The library user is now responsible for checking that the array is contiguous before using the faster function.
The library user already knows if he is using contiguous arrays or not. After all, it can fuck him over in tons of other cases, even a simple for loop, or a length check, if he treats one like the other. So it's not like he doesn't already have to be vigilant about it.
They say some in their readme. Because the native versions have some extra baggage (sparse array checks, etc).
But to answer in general:
1) JS functions also get compiled to native code for often used code paths. That's what the JIT does after all.
2) A JS function might use a better algorithm compared to a native function.
3) Native is not some magic spell that is always speedier than non-native. Native code can also be slow if it carries too much baggage.
https://code.google.com/p/v8/source/browse/trunk/src/array.j...
These fall outside of the common uses of these methods, and most people don't even know they exist.
It might be that I don't particularly like the language. but it's kind of frightening that we're building the world on that stuff.
* as long as you make it do less work
Or even discuss the fact that if this library is good enough for people to use then maybe the edge cases that the native versions are covering might not be so useful after all?
There is a great, amusing, borderline sci-fi talk by Gary Bernhardt about the future of Javascript and traditional languages compiled to Javascript. My recommendations: https://www.destroyallsoftware.com/talks/the-birth-and-death...
This would likely get even faster if you manually specialized a map/forEach/etc for each caller, but then you might as well just write the loop out by hand: http://rfrn.org/~shu/2013/03/20/two-reasons-functional-style...
What. Is. This. I don’t even.
Why can't we build software on simpler platforms with better implementations?
For example, Haskell provides only a handful of constructs but allows the developer to build sophisticated systems.
Though I agree complex platforms are not necessarily complicated.
I can make the implementation simpler if the underlying specification is simpler. If a language is full of edge cases, it was not designed carefully. If there exists a significantly faster implementation in a significantly slower language that covers 99% of the specification, I'd look for opportunities to simplify.
On one hand, I'm a big proponent of "know your tools". I'll gladly use a fast sort function that falls apart when sorting arrays near UINT32_MAX size if I'm aware of that caveat ahead of time and I use it only in domains where the size of the array is logically limited to something much less than that, for example.
But on the other hand, I write operating system code in C. I need to know that the library functions I call are going to protect me against edge cases so I don't inadvertently introduce security holes or attack vectors.
If I know that some JS I'm interacting with is using fast.js, maybe there will be some input I can craft in order to force the system into a 1% edge case.
The lesson here is probably "don't use this for your shopping cart", but we need to be careful deriding Javascript's builtins for being slow when really they're just being safe.
It may even be _easier_ to determine the behaviour of these functions than builtins, since determining how fast works just means reading its source whereas to determine builtins' behaviour you must read the ECMAScript specification and then hope[1] that the browser actually matches it perfectly!
[1]: or read the JS engine source, but that's a whole lot more work. :P
Now, if fast.js made sure we had the correct requirements, no distractions, clear milestones, and a dedicated team with no turn over, I'd import it in a second.
I just take objection to the perspective given by the parent post on the _safety_ situation surrounding this library.
[1]: ... not recently, anyway.
I'm sure that is a statistically valid way to measure performance.
V8 has excellent profiling tools (exposed in chrome and in nodejs) which should be used first before considering fallbacks. Before seeking a third party library, be sure to check if the function is called many times or is taking a long time.
For example, I found that throwing map out and using a straight array (avoiding the function calls entirely) can be up to 50% faster than using the functional suspects. But that, in the eyes of some people, unnecessarily adds complexity to the code and may not be worth changing
Ironically, that involves certain habit changes that completely obviate the library:
1) avoid map. Just create an array and write a for loop directly at the callsite, putting the code in a block rather than as a separate function
2) avoid indexOf. For single-character indexOf, it's much faster and much more efficient to match the character code (loop and check charCodeAt) than to use the function form
3) avoid lastIndexOf. Same as indexOf, except you loop in the opposite direction.
4) avoid forEach. Learn to love the for loop.
5) avoid reduce. See forEach
Anyone embracing fast.js is sacrificing some performance to begin with.
And with regard to performance, for most Node.js code / webapps if you have a loop with so many iterations that _.map is significantly slower than a for loop then you might be doing something wrong.
It simply refers to 'unrolling' that function call, so a new function doesn't need to be added to the stack.
JS's iteration methods aren't currently recursive, at least in V8[0]. But that's probably due to lack of TCO!
0. https://github.com/v8/v8/blob/master/src/array.js#L1378
The point of this library is that it provides the same behavior (for 99.99% of cases) and the same abstraction (so same readability / maintainability) as the functions it replaces, but with significantly better performance (for wildly varying degrees of "significantly" depending on usage).
I don't think the idea is that you profile your code and then micro-optimize it using this library. If you're doing that (which you should, for varying definition of "should"), then yes you will want to consider sacrificing the abstraction / brevity for performance.
However, this library seems like a handy way to maintain the abstraction, while gaining performance essentially for free without sacrificing anything worth mentioning. Then you profile (if you were going to / had time to / cared enough to) and optimize from a better starting point. Don't see anything wrong with that.
http://kitcambridge.be/blog/say-hello-to-lo-dash/
This is not the case with Fast.js as it breaks away from the language specifications. I'd much rather build, profile, and then optimize the few areas that actually require better performance than potentially introduce bugs by replacing the built-in methods.
HN should have a bot that posts the full quote whenever this line is cited since it's so often abused.
"There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified."
Plus who said it was / should be used prematurely anyway?
Isn't that essentially what I described? "Before seeking a third party library, be sure to check if the function is called many times or is taking a long time."
On the issue of this particular library: The problem is that you can do much much better by avoiding map, forEach and friends. The overhead of the function calls can be completely avoided by using a direct for loop at the callsite.
So yes, you may find it slightly faster to use this library rather than the native map, but with a small redesign you can avoid map entirely and get a massive performance win.
[0] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Type...
(edit): Yeah, the abstraction overhead is ridiculous. Here's the forEach() benchmark again, compared to an explicit for loop (no function calls):
(I ran this on Node "v0.11.14-pre", fresh from github).This is very often overlooked but extremely useful for implementations of fast algorithms in JavaScript that should scale to a lot of input data.
The next step for fast.js are some sweet.js macros which will make writing for loops a bit nicer, because it's pretty painful to write this every time you want to iterate over an object:
I'd rather write: and have that expanded at compile time.Additionally there are some cases where you must use inline for loops (such as when slicing arguments objects, see https://github.com/petkaantonov/bluebird/wiki/Optimization-k...) and a function call is not possible. These can also be addressed with sweet.js macros.
They have a structure like image[pixel].color
What I found was, always traversing the object structure was much slower than putting every pixel color as an argument in a function, that gets called every iteration.
So I had the impression, reasonable simple function, like a greyscale filter, get inlined by engines like V8.
How do you mean when you state that for(of) is incorrect?
Perhaps this 'example' clears something up?
But if Coffescript can walk away with its choice then I don't think you'll have anything to worry about.
These are legal CoffeeScript examples:
The one that's missing is:There's also the issue with some fonts making it hard to differentiate between { and [ but it's an idea that might be worth to think about at least.
Alternative:
You can squeeze out another factor of 2 with typed arrays:
And probably more still if you can figure out the asm.js incantation that makes everything statically typed.The reason it incurs an overhead is because the DOM is traversed every single time the property is read, to ensure nothing has changed. You can see why caching the length is a reasonable optimisation, as you're unlikely to be modifying the collection while looping.
[0] https://developer.mozilla.org/en/docs/Web/API/NodeList
I suspect a lot of the optimization opportunity in browsers today is less about JS or DOM in isolation but more about ways they could work together to improve situations like this one.
(Note: I understand this one is solvable by a proficient/attentive developer, but not all developers are like that, and not all such DOM/JS transition problems are as easily solvable from your JS code)
http://stackoverflow.com/questions/17989270/for-loop-perform...
The speed-up for "concat" is surprising to me. I wonder if it holds for "splice" and if that is true across browsers.
http://jsperf.com/fast-iter
Microbenchmarks like that require a lot of care to measure something correctly. Check out my talk from LXJS2013 for more details: slides http://mrale.ph/talks/lxjs2013/ and video https://www.youtube.com/watch?v=65-RbBwZQdU
I wrote quite a fast "map" (along with the others) that looked a bit like:
I'm not sure if I just used "result = []", but on modern browsers I think that'd be recommended. But yeah, if you're programming for a web browser then using another impl of map is probably going to be a waste of time.> native functions often have to cover complicated edge cases from the ECMAScript specification, which put them at a performance disadvantage.
Aren't these opposing statements?
The latter sentence you quoted refers to the specific builtin functions that fast.js re-implements. So we first get close to native performance in JS, then we beat the builtin functions by doing less work overall.
http://jsperf.com/fast-vs-lodash/3
So looking at this in Firefox, the "fast" version underperforms the native one for forEach, bind, map, reduce, and concat. It outperforms native for indexOf/lastIndexOf.
In Chrome the "fast" version does better than the native one for indexOf, lastIndexOf, forEach, map, and reduce. It does worse on bind and concat.
It's interesting to compare the actual numbers across the browsers too. In Firefox, the numbers I see for forEach are:
and the Chrome ones are: Similarly, for map in Firefox I see: and in Chrome: Interestingly, these two methods are actually implemented in self-hosted JS in both SpiderMonkey and V8, last I checked, so this is really comparing the performance of three different JS implementations.bind - fast 2,565,227 ±2.19%
bind - lodash 4,923,373 ±1.51%
bind - native 9,022,396 ±2.12%
on iPad this difference is even larger.
>I'd expect native browser methods to be an order of magnitude faster.
Built-ins need to adhere to ridiculous semantic complexity which only gets worse as more features get added into the language. The spec is ruthless in that it doesn't leave any case as "undefined behavior" - what happens when you use splice on an array that has an indexed getter that calls Object.observe on the array while the splice is looping?
If you implemented your own splice, then you probably wouldn't even think of supporting holed arrays, observable arrays, arrays with funky setters/getters and so on. Your splice would not behave well in these cases but that's ok because you can just document that. Additionally, since you pretty much never need the return value of splice, you can just not return anything instead of allocating a wasted array every time (you could also make this controllable from a parameter if needed).
Already with the above, you could probably reach the perf of "native splice" without even considering the fact that user code is actually optimized and compiled into native code. And when you consider that, you are way past any "native" except when it comes to special snowflakes like charCodeAt, the math functions and such.
Thirdly, built-ins are not magic that avoid doing any work, they are normal code implemented by humans. This is biggest reason for the perf difference specifically in the promise case - bluebird is extremely carefully optimized and tuned to V8 optimizing compiler expectations whereas the V8 promise implementation[2] is looking like it's directly translated from the spec pseudo-code, as in there is no optimization effort at all.
[1]: https://github.com/angular/angular.js/issues/6697#issuecomme...
[2]: https://github.com/v8/v8/blob/master/src/promise.js
That kind of optimization seems easily done with a builtin as well: have an option to return the array, and only do so if the JavaScript engine indicates that the calling code actually uses the return value.
Whereas the builtin ones implemented in C++ do keep all the code in there.
This is why even full implementations written in JavaScript can be faster than C++.
So not just JS - it seems language built-ins are often slowed down by bureaucratic spec compliance, and hand-rolling code can help you get a speedup.
http://www.youtube.com/watch?v=65-RbBwZQdU Vyacheslav Egorov - LXJS 2013 talk
i don't know if he actually said these word, but it was the overall theme of this (very entertaining and very enlightening) talk.
lodash is as fast as fast: see the JSPerf results posted elsewhere. John manages lodash well. He has managed it well for quite a while. Why switch to another library with no track record for little or no gain?
A native implementation could have a single flag associated with the array recording whether it is sparse, and use the more efficient code path given here in the common space where it's non-sparse.
Hey I'm not bashing here, I thing it's kind cool for learning purposes attempts to do such thing, but I truly wonder if there is an actual production need for such thing.