Vjeux

In World of Raids Guild Recruitment Tool, we wanted the search to be instant! We achieved this goal by not having a single page refresh or ajax call while updating the settings. Since it runs in the browser, performance was a real concern. We will see in this article what were the tricks used to make this real.

Sorting

In order to sort the guilds, each guild is given a matching score (between 0 and 65535) based on the current filters. At start, each guild has the maximum points. Then, each filter is giving a malus. For example when a specialization doesn't match, the guild loses 10%.

This means that everytime you change a filter, you have to recompute that matching score for all the guilds. Instead of recomputing the whole matching score, the guild holds the result of each filter. Everytime a filter is updated, the value of this filter is upated on every guild. The global matching score is now recalculated by summing all the partial precomputed scores.

Every bit of code in the matching function has been optimized, no more jquery code, loops are unrolled and great use of lazy boolean expression evaluation. The sort function itself also got boosted thanks to a trick I commented on my previous article Speed Up Javascript Sort().

Display

Once we have the data sorted, it has to be displayed! And this is another big time eater. When it takes 50ms to sort the data, it takes about 150ms to display 10 guilds!

Since we wanted performances, DOM elements are created at page loading, they are then only being updated as the guilds change. And still, only the required changes are made, for example tooltips are created as the user trigger the mouseover event.

The main problem with this is that we are not able to make bulk changes. Everytime you make the slightest change, the whole UI has to be redrawn which is a waste of time. I hope there will be such API in the future.

Since it's a web application, we had to maintain the url up to date, this is done using SmallHash, a small library of mine that compresses filter data into the smallest possible hash.

Scaling

Having all the data being sent at page loading is a pain, it makes it load slowly. One way to avoid this problem would be to use the localstorage to keep these data accross sessions and only send the updated guilds. However at the time I started developping the application there was no released browser supporting HTML5.

However, the application is focused on World of Warcraft guilds. This is a limited audience and there is no need on heavy scaling there. So we decided that it was a good option to go.

Up to 3000 guilds, this is pretty much instant in every browser in my MacBook Pro. When increasing that number to 10 000 it is taking more than a second to update on IE8. It requires 50 000 guilds for Chrome 3 to get slow, which is a pretty good score. It means that it is possible to do heavy processing, the bandwith now being the limiting factor.

World of Raids Guild Recruitment Search

World of Raids Guild Recruitment

Guild recruitment is a recurrent problem in World of Warcraft, many attempt have been made but none succedeed so far. After a brainstorming we decided that the following points were crucial.

• The guild recruiter has to spend less time as possible to set-up a guild and maintain it.
• The guild search must be easy and focus on what people expect from their guild.

With these points in mind, we had to find technical responses in order to make the World of Raids Guild Recruitment Tool.

• What You See Is What You Get: The guild management interface is the final display, there is no intermediate step.
• Tailored Widgets: About every widget has been heavily customized to fit the user need.
• Automatic Save: Every time you make a change, it is automatically published and available to anyone!
• Javascript Search: Having all the guilds fetched during the loading allows to have a complex filtering system instantly updated.

Guild Search

Looking for a guild should no more be a pain! You just have to tweak the filters and result appear sorted as you edit them! No more long page reload or even ajax requests. It is instant!

We focused hard on making filters one click away. We also took great care of the raid time filter, it is an important aspect of the guild choice that is too often avoided because of its complexity.

For more details on the optimizations made, see the post Guild Recruitement – Search Optimizations.

Guild Management

Our original goal was to be able to create a guild in less than a minute (yes, 60 seconds!) and we pretty much did it. The proof in the following video.

In order to achieve this, we opted for a Wysiwyg approach to remove the need of making two interfaces for both display and edition. Every widget has been tailored to fit the user needs. For example, as soon as you enter your name and realm, it automatically gathers your progression from the official website.

Having to deal with dependencies in Makefile is a real pain, there are a lot of examples of way to deal with it on the web but none of them is satisfying.

For example using gcc -MM does not work with subfolders, a depend rule requires the user to use it everytimes he adds new files ...

Here is what is wanted:

• Completly automatic: No user interaction is required when adding new files
• Works with an arbitrary amount of files
• Works with an arbitrary amount of level of folders
• Is not recalculated when nothing changed
• Use only one file to store dependencies
• Do not depend on complicated regular expressions

Here is the result:

BINARY  = project.exe
CC      = gcc
CFLAGS  = 
FILES   = $(shell find src/ -name "*.c")
HEADERS = $(shell find src/ -name "*.h")
OBJS    = $(FILES:.c=.o)
 
all: $(BINARY)
 
-include Makefile.deps
 
$(BINARY): Makefile.deps $(OBJS)
        $(CC) $(CFLAGS) $(OBJS) -o $(BINARY)
 
Makefile.deps: $(FILES) $(HEADERS)
        makedepend -- $(CFLAGS) -- $(FILES) -f- > Makefile.deps

This is in fact really easy. In your $(BINARY) rule, you add Makefile.deps as a prerequisite.

In order to generate the Makefile.deps you mark all $(FILES) and $(HEADERS) as prerequisite, so every time you change a file or header it will recompile the list.
We use makedepend to generate the dependencies list. It works like gcc -MM except that it outputs the correct file path when used with folders.

Then all is required is to include the Makefile.deps. We include it with -include so it does work the first time you compile.

Thanks to Lemoine Gauthier who helped me to discover this technique.

Prime number recognition is a very hard problem and yet no good enough solution has been found using classical algorithms. There are two ways to get around those limitations: find an algorithm with a better complexity or find a way to compute faster. The first one has already been researched by a large amount of people so I decided to give a shot to the second one.

We are limited by the speed of the electricity, so my idea is to use speed of light to improve speed by a great factor. I've come up with a simple example of how to use it to compute prime numbers.

We set up 2 mirrors with light sources that are directed.

We first set the sensor to the position lower 2

2 had no light so we create a new one that is going to en-light all the multiples of 2

3 had no light so we create a new one that is going to en-light all the multiples of 3

4 is already in the light, we skip it

hasLight(n):
// Sensor placed at lower n that tells weither if it is enlightened or not
 
newLight(n):
// Creates a light that starts from lower n, targeted at the upper n + n/2,
// that first reflects to lower 2n and then to all the multiples of n.
 
isPrime(n):
for i = 2 to sqrt(n)
  if not hasLight(i)
    newLight(i)
 
return not hasLight(n)

This method allows us to recognize prime numbers with light sources, mirrors, sensors and a bit of programming.

Recognizing if a number is prime or not requires to have a lot of lasers and sensors. I don't think that is a viable process, however this could be interesting to do multiplications. You want to fire 2 lights and then see in what point they cross. However there are 2 main problems:

• It requires to have 2 really long mirrors possibly infinite which is not possible in practice. It may be possible to add a vertical mirror in order to work in a bounded area. Yet to know how many times the light hit that mirror.
• We are required either to have an infinite number of sensors. We could have only one sensor that checks all positions sequentially but then we loose the speed of light! What is wanted instead are mirrors in each position that would redirect light to a unique sensor capable of knowing where it came from.

This is an experiment and it is not at the moment near to be faster than actual methods but this is a new way to think about programming. I don't know if anything useful is going to be deviated from this but it shows how to use the light to compute things.

In SQL, this is a common issue to query the previous and next entries of the database. In order to achieve this, we are going to use a table that is sorted by the `id` field. To get the previous, the technique consists in sorting all the fields that are lower that the current one and taking the first one.

SELECT *
FROM `table`
WHERE `id` < $current_id
ORDER BY `id` DESC
LIMIT 1

Let's take an example with the values [8, 3, 4, 9, 6, 1]. We want to get the previous of 8.

• WHERE `id` < $current_id
  We first take all the values strictly lower than 8
  Result: [3, 4, 1, 6]
• ORDER BY `id` DESC
  We then sort them in descending order
  Result: [6, 4, 3, 1]
• LIMIT 1
  We take the first one
  Result: 6

You can apply the same method for the next entry:

SELECT *
FROM `table`
WHERE `id` > $current_id
ORDER BY `id` ASC
LIMIT 1