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.

Lately, I've been advocating to all my student friends to start a blog. Here's an article with the most common questions answered 🙂

What are the benefits?

Being known as an expert. The majority of my blog posts are about advanced Javascript topics. As a result, I'm being tagged as the "Javascript" guy by people that know (broad sense) me. Every time they have a question about Javascript or Web Development they go to me.

Expanding your relations. Through my activities with this blog, I had conversations with celebs such as Bjarne Stroustrup (C++), Brendan Eich (Javascript), Jeremy Ashkenas (CoffeeScript) and many other people that I didn't know before. No one in my close relations is deeply interested in what I am writing. But thanks to the internet, I can meet other people that shares the same interests.

Getting Recruited. As you become an expert in a field, people start to notice and will want you. My blog is barely known and still, I have received several job offers. However this happens at random, take it like a gift but don't expect it to happen, or it won't 🙂

Being better. I've been so much better at Javascript since I started writing about it. But maintaining this blog also helped me improve my writing skills as well as my English.

Benefits are long term. You should not start a blog and expect it to be rewarding the next week. A blog is a presence on the internet. During the first 6 months, I barely had more than 5 visitors per day, but this number slowly started growing as I wrote more articles and time passed. Now, I'm at 100 visitors a day. I'm still amazed to see that so many people come!

Who cares about my blog?

Your friends. The first thing I do when I am done writing an article is to paste the link to some of my MSN contacts that will be vaguely interested in. It is a powerful way to start a conversation with people you did not talk with for a long time. I often re-write parts of the article given the feedback I receive and it leads to great conversations.

People on the Internet. My girlfriend always says "If you thought about it, someone did it". On the same idea, I believe that the following statement is correct: "If you find something interesting, someone else does too". Here is a fact, there are over 100 visitors on my blog everyday. Google connects people with the same interests!

People that want to know about you. The extreme example is your recruiter, but it could be a co-worker or even just a friend. Your blog is the place where you can show who you are and what you are worth. It is much better than a resume as it isn't constrained by a strong standardization and a ridiculous 1-page constraint.

I don't know what to write

Projects you've done. The easiest way to start a blog is to write one article per school/personal projects you have done. Put a screenshot, a description of what it does and you are set. This way, if I want to know about you, I will quickly scroll over your blog and will see what you have done. If something interests me, I'm going to read the article more closely.

Techniques you have used. It is interesting to go over your projects and allocate one blog article for each technical problem you solved. For example, the project Guild Recruitment leaded me to write several articles such as Dynamic Query Throttling, Mysqli Wrapper, Search Optimizations. The latest eventually made me look deeper to write Sorting Table.

Follow-up a conversation. I am often debating with my friends on topics related to computer science. Those discussions are potential targets for a blog post! It is really interesting to go deeper and start writing about it. You'll get more arguments to crush your friends theories 🙂

Start writing and ideas will flow. Once you have an article written, it often generates new ideas. Now, every time I write some code, I ask myself if that would be worth blogging. If yes, I create a draft on WordPress for later. This way when I'm in the mood of writing, I have many things to write.

There are already many article on the subject, why should I write mine?

Influence people around you. I always love reading my friends blog because they are talking about subjects that I'm interested in but that I would not have willingly researched for. It helps expanding my Javascript-centric horizon.

If you write about it, it means you know it. For example I wrote an article about how to use makedepend in makefiles. It tells recruiter multiple things. I have experienced the problem of dependency management. I am confortable with Makefiles as I used them in a fancy way. This is invaluable compared to a Makefile entry in a resume.

Go deeper in the subject. I often find myself writing code pretty easily without too much thinking. Writing about this particular sexy technique in my blog more challenging. It requires me to state the exact problem I try to solve, think about alternatives, seek for already existing solutions ...

After the post has been written, I receive a lot of feedback. My friends almost always talk about how it would have been solved in their own language of predilection. They also provide more use-cases where the technique would and wouldn't work, leads to improve it ...

How long does it take?

Count one evening per post. I usually spend one full evening writing down an involved article like this one. However I think a lot about the subject in a passive way by reading related articles, thinking about it in my bed ... Articles that show off a project are much quicker to write, I'd say about 30 minutes.

Post as often as you want. When I have something I deeply want to share I write an article about it. Once I've written once, I often see myself writing some more about drafts I had. Then there is a period of silence. Overall, I'd say I write every two months, often during holidays.

How many articles. Each new article you write is not going to shadow the other but adds up. When I check my analytics, each article written slightly increases my daily viewer count. But even with one article a blog is worth it.

How do I start?

Install a WordPress. Even if you are a geek, I strongly recommend against you coding your own blog or using some nerdy blog software. I went over that myself and I found myself coding stuff every time I wanted to write an article. WordPress gives you all the tools you need to blog, and if you want to do something a bit special, chances are there's already an extension that does it.

Quickly write your first article. Don't spend so much time finding the perfect theme or installing many extensions you don't even need yet. The first article is the hardest! Write it down and send it to your friends. Listen to their feedback and instead of editing the article, write another article trying to fix those issues. Writing is hard so it'll take more than one shot to feel comfortable with it. The more you practice, the easier it will be.

Conclusion

If I managed to convince your starting a blog, please give me the link! I'd love to read about your stuff and may help you get started if you want.

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;
}

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