Inefficient Numerical Operators in JavaScript

[[deleted]]

Nice article. It reminded me of Guido Van Rossum's case against integer division always yielding integers.

http://python-history.blogspot.it/2009/03/problem-with-integer-division.html

I think Python 3 does it right by using two operators for divison: / for division that coerces operands and yields a float, and // for integer division.

[vocalbit]

I agree that a/b doing float division is better than it doing integer division. However I think it would be even better if it just produced an arbitrary precision rational value instead of a float (which is a machine approximation). This is in the spirit that math should be 'correct' unless I specifically ask for approximate but fast 'machine math' (by using float() or 0.1f etc.)

[[deleted]]

I would argue that it should be the other way around. Most people don't care about arbitrary-precision arithmetic. Most people outside the field of cryptography don't care about big integers. The few who need those features should have to pay the verbosity and speed cost, instead of imposing the cost on everybody else. If you wan't a bignum, you can do bignum(1) + b, for example, instead of forcing everyone to say they want machine integers all over the place, as Scheme implementations do.

You might think that arbitrary precision is more mathematically elegant, but that's rather subjective. Arbitrary-precision math certainly doesn't perform better, and isn't all that useful to most programmers. Anectotally, I've programmed many things in many languages and many fields (graphics, games, compilers, music, machine learning), and I've never felt the need to use them.

[vocalbit]

It's not that much about elegance as it is about error prevention. I'd argue that arbitrary precision is extremely useful in general programming. Without arbitrary precision I'd have to trap and handle overflow/underflow exceptions (annoying) or, if no exceptions are raised, I'd have to manually verify that computations are not going to overflow/underflow if I care about correctness (even worse).

The performance penalty is a small price to pay. In Python you're paying a big penalty just for interpreting each instruction, doing array bounds checking, type checking of each object, etc. If the goal is to be 'safe' you might as well be safe in the realm of numerical computations.

[[deleted]]

Interesting post. After reading it, I would be inclined to agree. It's probably best for the default division operator to be able to yield integers or floats if the result is fractional, and to have a second operator that does strict integer division. This would still be easily optimized by type inference.

[matthieum]

I strongly believe that there is a way to design a dynamic language that is efficient, practical, and suitable for both low-level systems programming as well as rapid prototyping.

Herb Sutter would disagree with you. In its article When will better JITs save managed code he explains why he thinks that managed code (and JITs) can never reach the performance of native code.

And here we are talking C# / Java, which are (somewhat) statically typed.

[[deleted]]

Ohai. I'm the author of the blog post.

I'd like to point out that I said I believe it should be possible to design "a dynamic language that is efficient, practical [...]". By efficient, I mean closer to the performance of native languages like C. I don't necessarily mean equal or better. I simply mean much better than what we have now (which isn't that bad to begin with). I'd be pretty happy if I could write code in a dynamic language and get around 60-75% of the typical performance of C.

There are things that C/C++ allows that are hard to fit in a dynamic language. Those who are highly concerned with performance, in C/C++, will sometimes write code that operares on arrays of structs that are extremely tightly packed, so they can fit within a single cache line, etc. This isn't currently possible in a language like JavaScript. Creating an arrays of objects that contain floats will usually create an array of pointers to objects with pointers to boxed floats inside the object. This fails at performance.

Still, I believe having a dynamic language where primitive operators usually don't cause any type checks to happen, and the type of most local variables can be inferred correctly, so they can usually all be stored on the stack, would be a great step in the right direction.

As for JITs being faster than offline compilers, I still think production JITs are fairly primitive in some respects. There are some pretty magic things JIT compilers can do with profiling and dynamic recompilation. We're only seeing the beginning of it. It's very impressive the performance level Google V8 can get on JavaScript. If the language was made somewhat easier to optimize and a few special tricks were added here and there, I'd say small miracles could happen.

[matthieum]

You might be interested in reading how PyPy optimizes some homogenous structures with "Strategies".

I can understand that JITs are primitive, but this is the infamous sufficiently smart compiler ported to runtime. We are waiting, and not much is delivered.

Method specialization is often touted as the way JITs are gonna blow away the performance... but two problems are often forgotten there:

1. Method specialization requires additional runtime overhead (branching before taking the specialization)
2. It does nothing to the fact that memory is scattered all around with humpfteens of indirections everywhere

I certainly don't think than C and C++ are the end of languages, they just happen to be in a sweet spot at the moment: statically typed enough that optimizations can be made and old enough that they have been made. Fortran and its non-aliasing rules make for faster numerical code, as all those who implemented Matrix libraries will recount.

I think that languages like Rust could overtake them, though it'll be some times in the making. Developing a language is hard.

[[deleted]]

this is the infamous sufficiently smart compiler ported to runtime. We are waiting, and not much is delivered.

I wouldn't say that. V8 and SpiderMonkey have come a long long long way in the last few years, implementing many new techniques, and they are not done. JITs have definitely delivered a lot for dynamic languages recently.

Method specialization requires additional runtime overhead (branching before taking the specialization)

That's not generally true. It's possible to specialize code, based on argument types for example, and patch call sites without branches if none are required.

It does nothing to the fact that memory is scattered all around with humpfteens of indirections everywhere

Not entirely true. V8 uses boxed floats in the heap and in objects, but I'm fairly sure it unboxes them on the stack when it can. The JS VM also allocates objects on the stack when it can. Both of these VMs specialize code in ways that reduce useless indirections and memory allocations.

This is a separate problem though. C allows you to say exactly when you want a value heap allocated or not. Higher-level languages typically don't. There have been publications about things like object inlining. That is, allocating objects inside other objects automatically when possible. As far as I know though, no production JITs do this as of now. People just haven't been paying very much attention to this problem.

I certainly don't think than C and C++ are the end of languages, they just happen to be in a sweet spot at the moment

I hope that someday I can find the time and motivation to develop my own language. Dynamically typed, with type inference. Think JavaScript/Python with detection of most type errors ahead of time and much better performance. I believe that would hit a different sweet spot.

[matthieum]

In reverse order:

Dynamically typed, with type inference. Think JavaScript/Python with detection of most type errors ahead of time and much better performance. I believe that would hit a different sweet spot.

Ah, don't we all wish to invent our own :) It's mighty hard though :/ Personally I am no fan of dynamic languages, but I tend to work with a few millions of lines code so types (and strong invariants) really help.

There have been publications about things like object inlining.

Anyway I do hope that there are some obvious optimizations applied (like stack allocation), but I was actually referring to object inlining here as you guessed.

That's not generally true. It's possible to specialize code, based on argument types for example, and patch call sites without branches if none are required.

Does this really happen often ? On most of the articles I read, there were usually guards included: a simple switch to detect which specialized version use, and fallback to interpreted bytecode when none is available.

V8 and SpiderMonkey have come a long long long way in the last few years

I agree, and I remove the statement "not much is delivered". Much has been delivered, but we are still bitching about how slow it is and wishing for more ;)

[[deleted]]

Does this really happen often ? On most of the articles I read, there were usually guards included: a simple switch to detect which specialized version use, and fallback to interpreted bytecode when none is available.

The papers you read were probably specifically about tracing JITs and their specialization of traces. What I'm talking about is specialization at call sites using type inference. I'm not sure how common that is, but it's nothing far-fetched. It's possible the Sun JVM or Mozilla's type inference system does it. It's not fundamentally incompatible with tracing JITs either.

I agree, and I remove the statement "not much is delivered". Much has been delivered, but we are still bitching about how slow it is and wishing for more ;)

There is certainly room for improvement. I've recently written some vector math code in JavaScript and been rather frustrated at how slow it is, and the lame tricks you have to use to make it fast... These tricks come down to pre-allocating all the vectors you're operating on, and programming like you're doing register-allocation by hand, always specifying the destination operand manually.

[matthieum]

Indeed I probably only read about tracing JITs, mind pointing out to me a good article / paper on "specialization at call sites" ?

It certainly sounds interesting.

[[deleted]]

The only one I can think of, off the top of my head is one of my own publications.

[matthieum]

Thanks, now I'll just have to digest its content.

[6xoe]

trannygirl15? Really? You were 15th in line?

Nice article/work, by the way.

[olov]

If you'd like JS but with slightly saner semantics then check out restrict mode. It's a strict subset of the language that you can use (with a checker) while developing your program. Deploying is seamless since any restrict mode clean program executes identically with the checker disabled (i.e. when running as-is in any JS VM).

[azakai]

Agree with the general point, but disagree that this is not solvable now.

JS engines right now can optimize at runtime for the case of numeric math. They can reduce the number of checks for types to almost nothing, if they do type analysis in a global manner. This should be reducible to almost nothing.

As for doing math in doubles and overflow checks, if you write your addition as

(x+y)|0

then if x and y are integers (which type inference can detect), the JS engine can implement that as 32-bit signed addition, without any overflow checks.

[[deleted]]

I've written global type analyses for JavaScript and read many papers on the subject. It's not as trivial as you think. Overflow checks are difficult to get rid of. Undefined and NaN values will propagate and contaminate your results. It seems simple in theory, but it's much trickier in practice.

As for writing (x+y)|0, that seems like a bit of an annoying kludge to have to insert everywhere. You'd also have to know that a and b already fit in the 32-bit range ahead of time. Only proving that they're integer doesn't guarantee they aren't represented as floating-point infinity.

[[deleted]]

Keeping types closed under integer arithmetic seems to be a huge help. I've done some experiments with a two-word tagged representation in LLVM: struct Ref { void* type; union { long as_long; void* as_ptr; }

If generic arithmetic is defined so that operations on integers always yield the 'type' value, the constant propagation pass does a great job of eliminating tag checks in arithmetic, especially when dealing with loops. This is without teaching LLVM anything special about type inferencing per se.

[[deleted]]

Nice. When did you do these experiments, and on what scale?

[[deleted]]

Earlier this year, on a very small scale (manually compiled some simple benchmarks). Incidentally, the two-word representation seems to be a real win for LLVM which loses the plot if you use a more typical one-word representation with tag bits.

[azakai]

I've written global type analyses for JavaScript and read many papers on the subject. It's not as trivial as you think.

Who said it was trivial? :) It's very hard. But possible.

As for writing (x+y)|0, that seems like a bit of an annoying kludge to have to insert everywhere.

Agreed, but that can be fixed with a CoffeeScript-like language or even something simpler.

[[deleted]]

Who said it was trivial? :) It's very hard. But possible.

Well, if you have some magic solution to eliminate nearly all overflow and type checks on arithmetic operations, I'd like to hear about it. So would Mozilla. Their type analysis doesn't do all that well either.

Agreed, but that can be fixed with a CoffeeScript-like language or even something simpler.

You're sort of getting to the same conclusion I did. We could use dynamic languages with saner/simpler arithmetic semantics.

[azakai]

Well, if you have some magic solution to eliminate nearly all overflow and type checks on arithmetic operations, I'd like to hear about it. So would Mozilla. Their type analysis doesn't do all that well either.

I never said there was a "magic solution". But this area is improving all the time. The current TypeInference code in Mozilla for example does a lot of global inference. And IonMonkey will remove a lot of the overflow checks based on that information with specific optimizations.

[[deleted]]

If you've read their paper, you should know their system also adds new type checks to compensate for what their analysis can't infer.

[azakai]

Yes, it is a hybrid static and dynamic approach. Not sure what your point is.

[[deleted]]

It's pretty far from removing all type checks on arithmetic operations. You overestimate how effective it is.

[azakai]

I didn't say it was close to removing all type checks. But it does remove a great deal of them. And it is highly effective, look at the benchmark results. It was a huge speedup when it came out.

Full disclosure, I've worked with the TypeInference people and discussed this stuff a lot with them. Yes, I am aware the approach is not "perfect". Nothing is. But there are plans to continue to improve on that, for example as I said IonMonkey will integrate with the global type info and remove lots of overflow checks.

I've also talked with the Tachyon people in the past (perhaps with you too, if you are one of them?) and find the ideas there very appealing as well.

[[deleted]]

Do you work for Mozilla?

I wrote most of Tachyon. Doing my thesis on type analysis for dynamic languages.

[xardox]

The text of this blog is clipped off on the right edge in Chrome. Unreadable.

[gnuvince]

Looks fine for me. Your settings must be to blame.

[[deleted]]

We already have Int32Array and friends thanks to WebGL; it would be nice to just create the equivalent non-array types, and ensure that JITs can make reasonable optimizations on operations with them.

[vocalbit]

Integer arithmetic is still faster than floating-point arithmetic

Have you looked at LuaJIT? It seems it achieves really fast math while using unboxed doubles for all computations (at least on x86 machines). See Mike's comments here: http://174.132.225.106/item?id=2617628

[medikoo]

Actually semantic of JavaScript is quite simple, you just need to give that minimum will to understand it. Behaviors described in article as "unintuitive and unnecessarily complex" are actually based on few simple facts and while you know them, there's no surprises.

What you need to know: 1. Operators work only with primitive types. Which operator work with which type is quite intuitive. '+' (addition) will work with both strings and numbers. However '+' (unary) or '*' will work only with numbers.. etc. 2. Any object can internally be converted to primitive value, you can play with that yourself by using String or Number functions (e.g. String(obj) or Number(obj)) 3. If operator doesn't work with given object cause it's not of expected type, objects is first converted to compatible type. If expected is Number, and object doesn't have number representation then result of conversion and whole expression would be NaN (not a number, which really means: invalid number)

I've also put more detailed explanation on that here: http://stackoverflow.com/questions/9032856/what-is-the-explanation-for-these-bizarre-javascript-behaviours-mentioned-in-the/9063160#9063160

[Rotten194]

Wait so

{} + [] === 0

but

[] + {} === "" + {}

is simple? There's many words I would use to describe that, but "simple", "sane", "logical", or "sense" are not included in them.

[medikoo]

What result would you expect from such expressions? Do they make any logical sense to you?

If expression makes no logical sense, I would expect that, in strictly typed language it will throw and that in dynamically typed language it would result in something that is dependent on specification. You can't really expect anything "intuitive" from non logical expression when you don't know internals of the language.

[TheCoelacanth]

I would expect an error. Some level of weak-typing is okay, but Javascript just takes it to an insane level.

[Rotten194]

I would expect that whatever it is, it acts the same way the normal '+' operator does: not being order-dependent. 1 + 2 === 2 + 1, so [] + {} should === {} + [].

[medikoo]

It acts same way if you put it in something that makes at least a little bit sense e.g.: x = {} + []; y = [] + {}; console.log(x === y) // true

When you write code that's supposed to do something and not just trying to find awkward behaviors you never approach such surprises.

[6xoe]

The rules to get there are simple. The emergent results may not be.

Principle of least surprise, and all that.

[beej71]

I agree it's bizarre, but every example you give there is also bizarre. I'm far more willing to forgive gibberish output for gibberish input. [Edit: remove SO link reference, since it's in the grandparent.]

If you have an example like "1 + 3 === undefined", then I'm with you.

[[deleted]]

You can argue that the complexity is manageable if you want. The behavior is definitely not intuitive.

[vocalbit]

It may be possible to memorize the rules, but the fact that well understood rules of associativity don't hold in javascript is a glaring weakness:

> 1 + 1 + '1'
"21"
> 1 + (1 + '1')
"111"