en en en pt es en en en en cv az en en en en en en en en en en en en en en en en en en en en en ca es en es ne en en en tr en en en en fr en en en en en en en en en en en en en en en en en en en en en en en en en fr en zh nl en en en en en en en en en en en en en en it en en en en en en en pt en en en en en en en en en
In this post I’m going to talk about a performance disadvantage inherent to most (if not all) current implementations of dynamic languages and, more generally, languages that make use of garbage collection. This problem affects JavaScript, but also Python, Lua, Scheme and even Java to some extent. Surprisingly, this performance issue is one that is seldom talked about. When you ask someone why JavaScript code is slower than C, they will mention dynamic typing, run-time checks, number types and other sources of overhead, but they will seldom mention indirection.
As a simple example, suppose you wanted to define and instantiate an object representing a car and its 4 wheels, with each wheel having angles of direction and rotation. In C, you could do the following:
In JavaScript, this could be done as follows:
Both of these accomplish the same goal. In either language, one can write car.wheels[0].direction = 0.32, for example. In practice, there are several differences as to how this will be implemented, however:
In C, the car object is explicitly allocated on the stack. In JavaScript, it is implicitly allocated on the heap.
The C object, including the wheel objects and the rotation angles, is one contiguous piece of memory. This is not the case in JavaScript. Modern JS engines will allocate a car object, a string object, an array object to store the wheels, and individual objects for each wheel. The JS car object only contains pointers.
In C, the rotation angles are contained within the wheel objects, in the same contiguous piece of memory.  Under Google V8, this would not be so, the rotation angles, if they are floating-point, would each be stored in objects of their own.
These differences have a performance impact. In C, accessing a wheel rotation angle only requires accessing the stack pointer at some fixed offset. There is only one level of indirection. In JavaScript, there is indirection from the car variable to the car object, from the car object to the wheel array, from the wheel array to the wheel objects, and potentially from the wheel objects to the rotation angles. Concretely, this means:
Allocating all of the needed JavaScript objects will be slower. There may need to be multiple calls to the allocator. Object headers and pointers may need to be initialized.
Accessing object properties will also be slower in JavaScript. This is not so relevant in this toy example, but you could imagine that if we were updating a list of car objects in a game engine loop there could be a significant impact on performance.
The JavaScript representation will use more memory. In addition to storing the wheel objects, we have to store a header for these objects and pointers to the said wheels. Memory alignment constraints might impose additional memory waste as well.
Because the JavaScript representation is larger, it will not fit in as few cache lines as the C representation, this can cause further performance losses when dealing with large sets of objects.
In Google V8, incrementing a wheel rotation angle would cause a new floating-point object to be allocated.
I’m well aware that there are ways to deal with some of these issues in JavaScript. Perhaps the objects could be represented differently (we could have avoided the array). Perhaps we could have used the new Float64Array extension for rotation angles. The point is simply that often, the intuitive JavaScript representation performs worse due to the various reasons I’ve outlined. The programmer can do some things to recoup part of the performance, but this is often at the cost of readability. Ideally, one would want the (JIT) compiler to be able to mitigate or eliminate these performance issues without the code having to be changed.
One of the main reasons why I wrote this post is because I know that compilers can do more in this regard, and more would probably be done if compiler writers were more aware of these issues. The Java VM can do escape analysis and automatically allocate some objects on the stack when this is found to be safe. Papers have also been published, on the topic of automatic object inlining, that is, automatically allocating child objects inside of parent objects when possible. Such optimizations can help eliminate indirection and memory usage overhead. However, these techniques are not widespread in modern JIT compilers, and more research could be used to refine them.
From → Compilers, JavaScript, Programming, Programming Languages
I think many people underestimate the performance loss due to indirection and discontiguous memory. Even in C++ it’s the reason why a vector can often outperform a set despite a higher time complexity: the locality of data, and minimal redirects, just lets the CPU execute it so much faster.
You mentioned GC, so it should be pointed out that a moving GC may actually suffer double indirection. The outermost pointer is actually a pointer to another pointer which can be moved/changed when the GC kicks in. Of course, this moving should, in theory, be able to help with memory locality.
I’m reminded of a feature from the haXe language. I used it to do Flash programming and objects are very expensive in Flash. So a feature was added which could inline structures. So if you had a Point { int x; int y; } class, but your code didn’t actually need the Point itself, the compiler would remove the Point type and inline x and y. I haven’t used the language in a while, but it’s maintainer was good at finding ways to make it execute faster in less than optimal VMs.
I read Henrik Wann Jensen’s book on photon mapping. The guy actually spent quite a bit of time designing a kd-tree data structure to hold photons where each entry was tiny enough to fit in a single cache line and the whole tree was stored in a flat array. This was to maximize performance in an algorithm that can require hundreds of millions of lookups in a data structure with thousands or even millions of entries.
A straightforward reimplementation of this in JavaScript would probably be scarily slow. I wouldn’t be too surprised if it was actually 100 times slower. I’m not sure Java would fare that much better either.
Won Chun (@won3d) permalink
Compiler writers (at least as far back as the LISP machine days) are quite well aware of this issue. I do agree that JS does makes indirection difficult to avoid.
We got bit by a linked list used for undo. We would remove redundant undo steps from the middle of the list so we used a simple linked list. When we switched to STL vectors everything ran several times faster.
On the other hand too much locality with a concurrent program can cause big performance hits. I have seen problems on a 16 core 32 thread workstation.
Leave a Reply Cancel reply
Enter your comment here...
Fill in your details below or click an icon to log in:
Email (required) (Address never made public)
You are commenting using your WordPress.com account. ( Log Out /  Change )
You are commenting using your Twitter account. ( Log Out /  Change )
You are commenting using your Facebook account. ( Log Out /  Change )
Notify me of new comments via email.
Notify me of new posts via email.
« MusicToy – Music Made Simple
Why LISP Never Took Off »
Typed vs Untyped Virtual Machines
Minimalism in Programming Language Design
Democracy, Dictatorships and Access to Information
Code that Doesn’t Rot
The Internet Changed My Life
What’s Could You Use Tesla Bot For?
NoiseCraft: a Browser-Based Visual Programming Language for Sound & Music
Art Artificial Intelligence Artificial Life Assembly Biology Compilers Creativity D Language Electronics Future Game Development Genetic Algorithms Grad studies Graphics Higgs JavaScript Microcontrollers Microprocessors Music Programming Programming Languages Psychology Rant Robotics Tachyon Technology Uncategorized work x86 Zeta
Archives Select Month June 2022  (1) May 2022  (1) March 2022  (1) February 2022  (2) January 2022  (2) December 2021  (1) June 2021  (1) February 2021  (2) December 2020  (1) September 2020  (1) January 2020  (1) November 2019  (2) October 2019  (2) June 2019  (1) January 2019  (1) December 2018  (1) May 2018  (2) February 2018  (1) January 2018  (1) December 2017  (1) October 2017  (1) June 2017  (1) April 2017  (1) January 2017  (1) December 2016  (1) November 2016  (2) September 2016  (2) May 2016  (1) March 2016  (1) February 2016  (2) January 2016  (1) November 2015  (4) October 2015  (1) September 2015  (3) August 2015  (2) July 2015  (3) June 2015  (1) May 2015  (3) April 2015  (2) March 2015  (1) February 2015  (1) December 2014  (1) November 2014  (2) October 2014  (2) September 2014  (3) July 2014  (3) May 2014  (1) April 2014  (1) March 2014  (1) February 2014  (1) January 2014  (3) December 2013  (3) October 2013  (2) September 2013  (1) August 2013  (2) July 2013  (3) June 2013  (2) May 2013  (3) March 2013  (2) February 2013  (1) January 2013  (3) December 2012  (4) November 2012  (1) October 2012  (1) September 2012  (3) July 2012  (4) June 2012  (2) May 2012  (2) April 2012  (4) March 2012  (2) February 2012  (3) January 2012  (6) December 2011  (2) November 2011  (3) October 2011  (8) September 2011  (4) August 2011  (3)