Archive

Archive for December, 2010

Clearing up the confusion around JavaScript references

December 27th, 2010 8 comments

One question that seems to come up everywhere in discussions of JavaScript is:

Is JavaScript pass-by-reference or pass-by-value?

This is often asked by people who don’t really understand what pass-by-reference or pass-by-value really mean. One of the stock answers is:

Objects are passed by reference; primitives are passed by value.

I really don’t think this is the best way to describe the situation, so I’m going to try a new way.

What is a reference? (with cats)

I’m going to explain references with cats. Don’t worry, it’ll make purrfect sense.

Let’s say you have two cats, Bloopy and Floopy. Bloopy is a boy cat and Floopy is a girl cat. One day you announce to the world:

My favourite cat is Bloopy.

Let’s say you live your life as if you were inside a JavaScript interpreter. So you declare a new variable to hold your cat:

var fav_cat = Bloopy;

Imagine that this concept of “favourite” is like an invisible wire that links you to Bloopy. As long as Bloopy is your favourite cat you’ll be linked.

You can use this link to send messages to Bloopy. Say you bought Bloopy a new collar for Christmas. If you wanted him to wear it, you could say:

fav_cat.wear_collar();

You’re sending a message down your invisible wire telling Bloopy to wear his new collar. Because you’re living inside a JavaScript interpreter that works out fine.

One day, Bloopy makes a mess on your carpet. This upsets you, to the point that you decide that Floopy is now your favourite cat:

fav_cat = Floopy;

You’ve now re-assigned your favouritism. In terms of the invisible wire, you’ve detached it from Bloopy and attached it to Floopy. You can now ask Floopy to try on the new slippers you got her for her birthday:

fav_cat.wear_slippers();

One day, Floopy does something unmentionable. You now have no favourite cat:

fav_cat = null;

Mutability

So, what does that story tell us? Well, fav_cat is a JavaScript variable. At the beginning, it holds a reference to Bloopy. Later on, it holds a reference to Floopy. Don’t worry, nothing happened to Bloopy, but there wasn’t a reference to him stored in fav_cat any more. At two points in the story, we called methods on fav_cat. These methods mutated the underlying cat, in the first case to make it wear a collar, and in the second to make it wear slippers.

So, there’s two completely different things happening here; mutation and assignment. Mutation modifies the underlying object without affecting the link between the variable and the object, whereas assignment changes the link to a different object, but doesn’t modify any objects.

Immutability

Let’s continue the story. One day, you look up at the blue sky, and it inspires you to declare to the world that your favourite colour is blue:

var fav_col = "blue";

The next day you look at the grass, and declare that, in fact, this is the most beautiful colour:

fav_col = "green";

You can still think of this as there being an invisible wire between you and your favourite colour, but as colours (and JavaScript strings) are immutable, you can’t modify them using the wire – all you can do is re-assign your favourite colour to a new string.

So what does pass-by-reference mean?

In JavaScript, you never hold an object in a variable, you hold a reference to that object. It’s that invisible wire. You can send messages along the wire and you can tell the wire to attach to a different object, but that’s all. Let’s now look at passing a variable to a function:

function mutate(obj) {
    obj.name = 'Mutated';
}

var my_cat = { name: 'Floopy' };
mutate(my_cat);
alert(my_cat.name);

So, what’s happening here? When my_cat is passed into mutate, the parameter obj is given a reference to the same object that my_cat contains a reference to. So now my_cat and obj both have an invisible wire that links them to the object named ‘Floopy’. Inside the function, the name is changed to ‘Mutated’. The object that my_cat contained a reference to has been mutated by the function, so the last line will alert ‘Mutated’.

So, if that’s what happens with mutation, what happens with assignment? Here’s an example:

function reassign(obj) {
    obj = {};
}

var my_cat = { name: 'Floopy' };
reassign(my_cat);
alert(my_cat.name);

Ok, what’s going on here? When my_cat is passed into reassign, both obj and my_cat hold an invisible wire connecting them to the object named ‘Floopy’. Inside reassign, obj is reassigned to an empty object. So reassign has severed the invisible wire connecting obj to Floopy, and reattached the wire to a new, empty object. reassign doesn’t have any control over the link between my_cat and its object, so my_cat.name remains ‘Floopy’.

But what about pass-by-value?

Here’s what I say: forget what anyone ever told you about pass-by-value.

Another example:

function changeColour(col) {
    col = 'green';
}

var fav_col = 'blue';
changeColour(fav_col);
alert(fav_col);

I don’t think you’re going to be surprised that fav_col remains ‘blue’. That’s because chageColour reassigned – it didn’t mutate. And why is this called pass-by-value when the object example was called pass-by-reference? Because strings are immutable. You can’t mutate a string inside a function so there’s no way to change fav_col from inside changeColour.

And finally, the conclusion (with no cats)

The point is, it doesn’t matter whether the JavaScript interpreter holds a reference to the string ‘blue’, and passes a reference into changeColour or whether it passes the actual string into the function – either way the string can’t be mutated. The only way to change fav_col is to reassign fav_col.

There’s no point making a distinction between objects and primitive types when you’re passing into a function. The important distinction to make is between mutable and immutable types. A function can mutate a mutable object passed in (making changes to an object the caller passed in) but it can’t mutate an immutable object. A function can reassign a mutable or an immutable object, but the caller won’t see these changes, because all reassignment does is move the invisible wire attached to the parameter.

Further reading

Ecma-262-5 in detail: Name binding Dmitry Soshnikov talks about the same issues here but in a lot more detail. He uses the more strictly correct term “rebinding” where I have said reassignment, as the variable name is “bound” to an object. Definitely worth reading if you want a more in-depth discussion.

ECMA-262-3 in detail: Evaluation strategy A discussion of all the different types of evaluation strategy, including call by value, call by reference, and call by sharing. JavaScript is noted to be call by sharing, or “call by value where value is the reference copy”.

Call by sharing on Wikipedia Wikipedia notes that the Python community is the only one to have widespread use of this term, even though the same semantics are shared by Java, Ruby, Scheme, JavaScript etc.

Categories: Programming Tags: ,

JS1k: Making a very small game in JavaScript part 2 – optimisations

December 2nd, 2010 4 comments

This is part 2 of a series. See part 1 here.

Two types of optimisation

There are three types of optimisation when you’re trying to reduce the size of the code. The first two are “defactoring” techniques: they change the code but not the functionality. The third changes code and functionality.

1. Optimising for the compiler

One of the major optimisations the Closure compiler carries out is the renaming of identifiers. Closure will, wherever possible, rename your variables and functions with one letter names. This means you can keep using the nice long descriptive names and know that in the final file they won’t take up any more space than if you called everything x and y. So, how can you help with this?

One tiny optimisation I discovered was that I was using the literal 50 in a number of places. I defined a new variable fifty in the global scope and assigned it the value 50. Replacing all appearances of 50 with fifty increased the size of my un-minified code, but when minified, fifty became a single letter identifier and saved me a byte each time. Of course, there’s some extra code overhead to allow this, so there have to be enough occurrences for it to be worth it. Even a single byte’s worth it though.

I discovered I was using a.lineTo(x,y); a lot, where a is the canvas context. Closure can’t rename a.lineTo, so I needed to give it something it could rename:

function lineTo(x,y) {
  a.lineTo(x,y);
}

Again, there’s some overhead involved in setting this up, but with enough use of a.lineTo it’s well worth it.

I had to work round a bug with the compiler here. When it gets to the definition of lineTo it makes the assumption that inlining it will save space. So every occurrence of lineTo(x,y) in the code is replace by a.lineTo(x,y), and it removes the lineTo definition. To stop it doing this, I had to add the following line:

window['lineTo'] = lineTo;

This line forces the compiler to keep the lineTo definition, and when compiled produces window.x=x;. This is good and bad news – lineTo is now kept (in minified form) but there’s a useless line added. The way I got round that was to add a post-compilation step to my Makefile:

    sed -i 's/window\.[a-zA-Z]*=.;//g' kave-min.js

(Yes, I learned sed for this. That’s dedication.)

2. Optimising the code

Some code optimisations just make the code size smaller, full stop. One is true and false. In a lot of cases, 1 and 0 will do just fine, at a quarter of the size.

Code organisation matters too. You may be used to writing nice modular code with no global variables and loose coupling between each module. All those good intentions need to be completely suppressed. Make everything a global unless it absolutely has to be local. Everything should know about everything else. Couple wherever possible.

An example of coupling comes in the rendering stage of the game loop. The context fillstyle is set to white. After this, the snowball is rendered, followed by the snow. Then the fillstyle is set to blue, and the icicles and walls are rendered. The order of these rendering functions is tightly coupled in terms of order of execution. Trying to render the icicles before the snow would make the icicles white, unless we changed the fillstyle to blue then back to white for the snow.

3. Changing the behaviour

I said that the first two techniques “defactored” the code, leaving the behaviour unchanged. Sometimes the current behaviour is essentially complex, and needs to be simplified to reduce its code size. The simplest solution is to just leave out functionality, but sometimes that’s a compromise too far. Following are some less drastic options.

Here’s a really simple example. I picked a nice blue for the icicles with the following line:

a.fillStyle = "rgb(190,230,255)";

Unfortunately, the syntax for writing arbitrary rgb colours is relatively verbose. Much shorter are the colour names, like “yellow” or “blue”. “blue” was the wrong colour, but using Doug Crockford’s nice CSS colour chart I was able to find “lightblue”, which was pretty close to the original colour, but saved me 7 valuable bytes over “rgb(190,230,255)”.

The snow falls diagonally, but with a little bit of added randomness. I wanted it to follow a sinusoidal curve as it fell, but the additional code to enable this was too long, so I cut it. The snow’s not as natural as I’d like, but I had to compromise.

The collision detection algorithm’s pretty simple. I used the context.isPointInPath(x,y) method, passing the front middle point of the snowball. I could then call the detectCollision() function every time I drew a new path that I wanted to check (i.e. the walls and the icicles). It would be nice to check the top, front and bottom points of the snowball, but that would have been too much code.

Don’t try this at home

Coding is usually about weighing things up: readability/maintainability, execution speed, memory use, code size, etc. When you’re doing a JS1k submission, the only one of these that matters is code size (well, execution speed can matter as well, but only as a secondary concern). The important thing to remember though, is that this kind of optimisation is wrong, just plain wrong. It’s almost never a good idea to sacrifice maintainability for code size. If it were, we’d all be writing Perl. I’ll leave you with that thought.

Categories: Programming Tags: ,

JS1k: Making a very small game in JavaScript part 1 – tools

December 2nd, 2010 30 comments

Well, that was fun. I’ve just submitted my JS1k Xmas edition demo. I only heard late on when the first JS1K happened, and I wasn’t up to coding anything decent at that stage anyway. So when I heard about this new one, I jumped on the task, working all weekend on it (except when I had to help move a piano). By the end of Sunday it was done, and I was mostly happy with it.

Before I started, I wanted to see if there were any good resources out there for this kind of thing, so I asked on Stack Overflow. I got a few good tips there, but the most useful one was probably:

You need to have the extreme small file size in mind when you write the code. So in part, you need to learn all the tricks yourself.

Show me the code!

Here’s the minified source of my submission. Trying to read minified JavaScript is a bit like reading assembly language when you’re used to C, or bytecode when you’re used to Java, so don’t try to understand it too much. Have a look at the un-minified code to see what it originally looked like.

It’s all up on github as well if you want to see the commit history.

Tools of the trade

I realised early on that I needed to have a quick way of minifying my code and checking its size. I started off playing with the Google Closure Compiler web interface but it was too slow to continually copy-paste my code in there. I downloaded it as a CLI app. Next off, I wrote this Makefile:

default:
    java -jar compiler.jar --compilation_level ADVANCED_OPTIMIZATIONS --js kave.js --js_output_file kave-min.js
    stat -c%s kave-min.js

The first line uses Closure to compile with advanced optimisations, and the second outputs the size of the minified file. With this, all I had to do was type make to see what the minified filesize would be. Being able to do this after every tiny optimisation was extremely useful, as I could quickly experiment with new techniques and see if they were worthwhile.

Learning the tools

It’s important to understand what the compiler is actually doing, and what it’s able to do. Reading through the Advance Topics in the Closure docs was essential. Closure will do some pretty advanced optimisations, but it needs help. For example, it doesn’t touch strings (thankfully). That means if you refer to a method in one place as obj.meth and in another as obj['meth'], it can’t rename obj.meth.

Another big no-no is with, which is good, because it just confuses things anyway. Using with means Closure can’t distinguish between properties and local variables, so there are a lot of name shortenings it just can’t do.


In Part 2, I’ll look at some of the specific optimisations that I used.

Categories: Programming Tags: ,