Vjeux

In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances.

Common pattern

In order to test if the key is already in the cache, the usual pattern is to use key in cache. This leads to the following code:

function cachedValue(key) {
  if (key in cache) {
    return cache[key];
  } else {
    var result;
    /* generate result */
    return cache[key] = result;
  }
}

Ideal cache lookup

The expensive operation with a cache is to traverse the data structure in order to find the position where the element should be. In the previous code, there are three independent lookups: key in cache and 2x cache[key].

In order to improve performance, the ideal would be to make that expensive lookup once, and do the test/get/set directly at that position.

function cachedValue(key) {
  var position = cache.lookup(key);
  if (cache.has(position)) {
    return cache.get(position);
  } else {
    var result;
    /* generate result */
    cache.set(position, result);
  }
}

Javascript Workaround

However, there is no API to directly manipulate the lookup and position. We have to find workarounds.

We remark that cache[key] will either return the value or undefined if not present in the cache. The belonging test no longer requires a full lookup, you only have to compare the value with undefined.

function cachedValue(key) {
  var result = cache[key];
  if (result === undefined) {
    /* generate result */
    cache[key] = result;
  }
  return result;
}

There is only one drawback: it is no longer possible to use undefined as a value in your cache.

Without temporary

If the result can be generated inline and your cache will never contains falsy values, you can use a shorter version. It should not impact performance however.

function cachedValue(key) {
  return cache[key] || (cache[key] = /* generate result */);
}

Conclusion

There are still two lookups done in case of a cache miss. If you find a way to factor the code in a way that removes it, I’m really interested in knowing 🙂

At the time of writing, the described technique is faster on all the tested browsers. As performance in browser rapidly evolve, check out the jsPerf entry before you decide to use it in your application.

Let’s go back 5 years ago during the World of Warcraft beta. I was working on Cosmos UI, a projects that aimed to improve the World of Warcraft interface.

As interface modification was not officially supported by Blizzard, we went ahead and directly modify the game files written in Lua and XML. We provided the new edited files for the thousands of people using Cosmos.

Previous Method

Let’s take a concrete example. We need to analyze the combat log in order to display a damage chart. The game calls the function ProcessChatMessage with all the required information.

function ProcessChatMessage(message, source, channel) {
  // ... Default Code ...
}

Note: World of Warcraft uses Lua as its programming language but I will use Javascript for this blog post as you, my readers, are most familiar with it. The technique remains exactly the same.

In order to process the combat log, we simply add some code at the beginning of the function in order to execute some action if the channel is COMBAT_LOG_CHANNEL. Nothing really extraordinary.

function ProcessChatMessage(message, source, channel) {
  if (channel == COMBAT_LOG_CHANNEL) {
    // ... Addon Code ...
  }
 
  // ... Default Code ...
}

However this solution is extremely intrusive as you have to change alter the code. Every time Blizzard releases a new version, we had to make a diff of all the files that changed and manually update all our code base. While we were doing this process, all the user of our interface could no longer play as they depended on us. This was an extremely stressful process on both parts.

This issue along with Blizzard servers being unstable helped start the meme Patch Day, No Play.

Hook Solution

I found out a non-intrusive way to alter the behavior of the game. With that technology unlocked, we started to modularize our codebase. Blizzard noticed and when our migration was nearly over, they added the ability to officially use modules (called Addons).

The technique is extremely simple. It only requires the language to have first class function. You store the function you want to alter in a variable (1). Then you override that function with yours (2), that will call the stored one to keep the default behavior (3).

// (1) Backup the function
var defaultProcessChatMessage = ProcessChatMessage;
 
// (2) Override the function
ProcessChatMessage = function(message, source, channel) {
  if (channel == COMBAT_LOG_CHANNEL) {
    // ... Addon Code ...
  }
 
  // (3) Call Default Code
  defaultProcessChatMessage(message, source, channel);
}

This solution gives you a great control as you can add pre and post processing and even skip the old code if you need to. It works for most use-cases unless you have to modify what is inside of the function.

The technique has several important features:

• The target function does not need to be written in a special form. It does not require to support hooking and does not need to be registered as being hookable somewhere.
• Multiple hooks can be added independently. For example if another addon called VjeuxAddon wants to manage all the messages that start with VjeuxAddon:, you can just write the following code somewhere in the addon:

  var defaultProcessChatMessage = ProcessChatMessage; ProcessChatMessage = ProcessChatMessage(message, source, channel) { if (message.match(/^VjeuxAddon:/) { VjeuxAddon.processChatMessage(message, source, channel); } else { defaultProcessChatMessage(message, source, channel); } }

  var defaultProcessChatMessage = ProcessChatMessage;
  ProcessChatMessage = ProcessChatMessage(message, source, channel) {
  if (message.match(/^VjeuxAddon:/) {
  VjeuxAddon.processChatMessage(message, source, channel);
  } else {
  defaultProcessChatMessage(message, source, channel);
  }
  }

• The technique is decentralized. You don’t have to have a system that coordinates all the hooks. Each addon sees only his own hooks.
• No library is required to use this technique.

Bonus Links

See these links for non-intrusive hooking techniques in other languages:

• :around of Common Lisp CLOS
• C++ Detours library (PDF)

There is an open problem in porting real game into the web browser related to cursor handling. But before we jump into that, you might actually find these selection of casino bonuses fascinating. You can get free spins and credits by registering an account as a welcome bonus for new players like you.

Problem

Many games such as First-Person Shooters require the mouse to freely move, without the constraints of screen edges. However there is no such API in the browser to make this work.

If you don’t know what I mean, you can experience it yourself on the CopperLicht Quake 3 Map Demo. You will find it really hard to move because there is no way to reproduce the standard FPS cursor behavior.

This important issue does not occur only on First-Person Shooter games. For example in World of Warcraft, you can Left/Right-click and drag in order to move the camera. During the dragging operation the cursor is hidden. When the operation is over, the cursor re-appears at the position it was when the dragging started.

Proposal

The behavior is usually implemented moving back the cursor to the center of the screen at every moment. Therefore, a way to solve the problem would be to implement an API that lets us set the cursor position.

However, in most games, we don’t need to actually control the mouse. Instead, we want to hide the cursor and make the mouse freely move around, without being limited by the size of the screen.

This is why I suggest the addition of a mouseFreeze function. The mouse will be anchored to that position and the mousemove events are going to set a virtual position.

window.mouseFreeze()
// The cursor is hidden
 
addEventListener(window, 'mousemove', function (event) {
  // Everytime the user moves the mouse
  //   The delta is added to "virtual[X/Y]"
  //   The cursor is moved to the center of the screen
 
  event.pageX, event.pageY // Cursor Real Position
  event.virtualX, event.virtualY // Cursor Virtual Position
});
 
window.mouseUnfreeze()
// The cursor is shown
// The cursor is moved to the position it was frozen

Open Questions

I believe that mouseFreeze API is a solution that enables a wide range of games to be ported into the browser while being an order of magnitude less dangerous than giving total mouse control.

The mouseFreeze is currently only an idea and it raises many questions such as

• How to make sure you can’t get stuck in frozen state?
• Can it be exploited?
• What if the user scrolls?
• What if the user alt-tabs?
• Add events onmousefreeze, onmouseunfreeze?
• Allow it only on fullscreen applications?

I am welcoming any feedback on this idea. If you believe it is a good one and are interested in writing a patch for Chrome/Firefox/Opera, I would love to help you out.

References

mashu on Hacker News mentioned that this issue is being worked on in a Chrome Bug. This is an interesting read that proposes alternative solutions and gives more use cases.

JSLint imposes us to do manual hoisting of variables. What if we did it but at the end of the function? 😛

function print_array (array) {
  var length = array.length;
  for (var i = 0; i < length; ++i) {
    var elem = array[i];
    console.log(elem);
  }
}

function print_array (array) {
  var length, elem, i;
 
  length = array.length;
  for (i = 0; i < length; ++i) {
    elem = array[i];
    console.log(elem);
  }
}

function print_array (array) {
  length = array.length;
  for (i = 0; i < length; ++i) {
    elem = array[i];
    console.log(elem);
  }
 
  var length, elem, i;
}

$(‘.highlightvar span:contains(var)’).css(‘background-color’, ‘yellow’).css(‘color’, ‘red’)

I have no idea if that could be of any use but it amused me 🙂

Writing a parser for a structured binary format such as a 3D model is extremely annoying. You have first to declare your file structure, and then go over every structure again and make a proper code to parse it. This is mainly caused because the lack of introspection of C/C++ and for performance reasons.

In Javascript, it does not have to be that way! jParser is a class that only asks you to write a JSON version of the structure. It will parse the file automatically for you.

Here is an example of what you could write with jParser:

var description = {
  header: {
    magic: ['string', 4],
    version: 'uint32'
  },
  model: {
    header: 'header'
  }
};
 
var model = new jParser(file, description).parse('model');
console.log(model);
// {
//   header: {
//     magic: 'MD20',
//     version: 272
//   }
// }

Description

Standard Structure

The description object defines blocks that needs to be parsed. In the previous example, we define two blocks header and model where each block is a list of labelled sub-blocks.

Default blocks such as int32, char, double are provided by jDataView.

This organization makes it easy to reproduce C structures. Let’s see the description of the BMP format.

// Javascript Description
header: {
  header_sz: 	'uint32',
  width: 	'int32',
  height: 	'int32',
  nplanes: 	'uint16',
  bitspp: 	'uint16',
  compress_type:'uint32',
  bmp_bytesz: 	'uint32',
  hres: 	'int32',
  vres: 	'int32',
  ncolors: 	'uint32',
  nimpcolors: 	'uint32'
}

// C Structure
typedef struct {
  uint32_t header_sz;
  int32_t  width;
  int32_t  height;
  uint16_t nplanes;
  uint16_t bitspp;
  uint32_t compress_type;
  uint32_t bmp_bytesz;
  int32_t  hres;
  int32_t  vres;
  uint32_t ncolors;
  uint32_t nimpcolors;
} BITMAPINFOHEADER;

Reference Structures

As you already noticed, instead of using basic blocks, we can use our own blocks. In the following example, uvAnimation uses animationBlock that uses nofs:

nofs: {
  count: 'uint32',
  offset: 'uint32'
},
 
animationBlock: {
  interpolationType: 'uint16',
  globalSequenceID: 'int16',
  timestamps: 'nofs',
  keyFrame: 'nofs'
},
 
uvAnimation: {
  translation: 'animationBlock',
  rotation: 'animationBlock',
  scaling: 'animationBlock'
}

Functions

At this point, it is possible to express any C structure and parse files that could be loaded using a simple read. We now need to integrate a logic within our parser using anonymous functions.

Recursive Parsing

It is a common operation to read consecutive blocks. It is possible to make an array block that takes a block name and a count. It parses all theses blocks and aggregates them into a Javascript array.

array: function (type, length) {
  var array = [];
  for (var i = 0; i < length; ++i) {
    array.push(this.parse(type));
  }
  return array;
},

In order to call a function, we use an array literal where the first element is the block name and the rest are the arguments. We can easily define float[234].

float2: ['array', 'float', 2],
float3: ['array', 'float', 3],
float4: ['array', 'float', 4]

We can use the array block to build a string block. We parse an array of char and join it.

string: function (length) {
  return this.parse(['array', 'char', length]).join('');
},
 
filename: ['string', 32]

Seek & Tell

In the World of Warcraft models, there is a small structure called nofs that tells us “There are [count] consecutive [type] at [offset]”. We build a struct block in order to parse this pattern. It will use seek and tell to navigate through the file.

nofs: {
  count: 'uint32',
  offset: 'uint32'
},
 
struct: function (type) {
  // Read the count & offset
  var nofs = this.parse('nofs');
 
  // Save the current offset & Seek to the new one
  var pos = this.tell();
  this.seek(nofs.offset);
 
  // Read the array
  var result = this.parse(['array', type, nofs.count]);
 
  // Seek back & Return the result
  this.seek(pos);
  return result;
},
 
triangles: ['struct', 'uint16'],
properties: ['struct', 'boneIndices']

Code

The code that powers this is only 30 lines long (70 including the standard integral types). It just handles each possible data type.

parse: function (description, param) {
  var type = typeof description;
 
  // Function
  if (type === 'function') {
    return description.apply(this, [this.param].concat(param));
  }
 
  // Shortcut: 'string' == ['string']
  if (type === 'string') {
    description = [description];
  }
 
  // Array: Function Call
  if (description instanceof Array) {
    return this.parse(this.description[description[0]], description.slice(1));
  }
 
  // Object: Structure
  if (type === 'object') {
    var output = {};
    for (var key in description) {
      if (description.hasOwnProperty(key)) {
        output[key] = this.parse(description[key]);
      }
    }
    return output;
  }
 
  throw new Error('Unknown description type ' + description);
}

Conclusion

This little parser is an example of how to extensively use all the dynamic characteristics of Javascript such as Object Literals, Anonymous Functions and Dynamic Typing in order to build a powerful and easy to use tool.

I don’t want to release the library just yet as I need to explore more use cases and find elegant solution for them too. But I hope it will give you inspiration to use full Javascript power.

Demo

You can see it in action in my 0.1% completed Javascript WoW Model Viewer demo. The two following files are important:

• m2.js: The model description
• jParser.js: The parsing library

Everywhere on the web we read that Javascript has prototypal inheritance. However Javascript only provides by default a specific case of prototypal inheritance with the new operator. Therefore, most of the explanations are really confusing to read. This article aims to clarify what is prototypal inheritance and how to really use it on Javascript.

Prototypal Inheritance Definition

When you read about Javascript prototypal inheritance, you often see a definition like this:

When accessing the properties of an object, JavaScript will traverse the prototype chain upwards until it finds a property with the requested name. Javascript Garden

Most Javascript implementations use __proto__ property to represent the next object in the prototype chain. We will see along this article what is the difference between __proto__ and prototype.

The following code shows how the Javascript engine retrieves a property (for reading).

function getProperty(obj, prop) {
  if (obj.hasOwnProperty(prop))
    return obj[prop]
 
  else if (obj.__proto__ !== null)
    return getProperty(obj.__proto__, prop)
 
  else
    return undefined
}

Let’s take the usual class example: a 2D Point. A Point has two coordinates x, y and a method print.

Using the definition of the prototypal inheritance written before, we will make an object Point with three properties: x, y and print. In order to create a new point, we just make a new object with __proto__ set to Point.

var Point = {
  x: 0,
  y: 0,
  print: function () { console.log(this.x, this.y); }
};
 
var p = {x: 10, y: 20, __proto__: Point};
p.print(); // 10 20

Javascript Weird Prototypal Inheritance

What is confusing is that everyone teaches Javascript prototypal inheritance with this definition but does not give this code. Instead they give something like this:

function Point(x, y) {
  this.x = x;
  this.y = y;
}
Point.prototype = {
  print: function () { console.log(this.x, this.y); }
};
 
var p = new Point(10, 20);
p.print(); // 10 20

This is completely different from the code given above. Point is now a function, we use a prototype property, the new operator. What the hell!?

How new works

Brendan Eich wanted Javascript to look like traditional Object Oriented programming languages such as Java and C++. In those, we use the new operator to make a new instance of a class. So he wrote a new operator for Javascript.

• C++ has the notion of constructor, that initializes the instance attributes. Therefore, the new operator must target a function.
• We need to put the methods of the object somewhere. Since we are working on a prototypal language, let’s put it in the prototype property of the function.

The new operator takes a function F and arguments: new F(arguments...). It does three easy steps:

1. Create the instance of the class. It is an empty object with its __proto__ property set to F.prototype.
2. Initialize the instance. The function F is called with the arguments passed and this set to be the instance.
3. Return the instance

Now that we understand what the new operator does, we can implement it in Javascript.

     function New (f) {
/*1*/  var n = { '__proto__': f.prototype };
       return function () {
/*2*/    f.apply(n, arguments);
/*3*/    return n;
       };
     }

And just a small test to see that it works.

function Point(x, y) {
  this.x = x;
  this.y = y;
}
Point.prototype = {
  print: function () { console.log(this.x, this.y); }
};
 
var p1 = new Point(10, 20);
p1.print(); // 10 20
console.log(p1 instanceof Point); // true
 
var p2 = New (Point)(10, 20);
p2.print(); // 10 20
console.log(p2 instanceof Point); // true

Real Prototypal Inheritance in Javascript

The Javascript specifications only gives us the new operator to work with. However, Douglas Crockford found a way to exploit the new operator to do real Prototypal Inheritance! He wrote the Object.create function.

Object.create = function (parent) {
  function F() {}
  F.prototype = parent;
  return new F();
};

This looks really strange but what it does is really simple. It just creates a new object with its prototype set to whatever you want. It could be written as this if we allow the use of __proto__:

Object.create = function (parent) {
  return { '__proto__': parent };
};

The following code is our Point example with the use of real prototypal inheritance.

var Point = {
  x: 0,
  y: 0,
  print: function () { console.log(this.x, this.y); }
};
 
var p = Object.create(Point);
p.x = 10;
p.y = 20;
p.print(); // 10 20

Conclusion

We have seen what prototypal inheritance is and how Javascript implements only a specific way to do it.

However, the use of real prototypal inheritance (Object.create and __proto__) has some downsides:

• Not standard: __proto__ is non-standard and even deprecated. Also native Object.create and Douglas Crockford implementation are not exactly equivalent.
• Not optimized: Object.create (native or custom) has not yet been as heavily optimized as the new construction. It can be up to 10 times slower.

Some further reading:

• Douglas Crockford: Prototypal Inheritance
• MDC Documentation: __proto__
• John Resig: getPrototypeOf
• Javascript Garden: Object.prototype
• Dmitry Shoshnikov: OOP: ECMAScript Implementation
• Angus Croll: Understanding Javascript prototypes
• Yehuda Katz: Understanding JavaScript Function Invocation and “this”

Bonus

If you can understand with this picture (from the ECMAScript standard) how Prototypal Inheritance works, you get a free cookie!