Archive for December, 2010


Adaptive DNS pre-resolution in Google Chrome

I've stated it before, but I'm a big fan of the Google Chrome browser because it's so damn fast! Apart from the awesome V8 JavaScript engine, one of the things that makes it fly is some clever DNS resolution. It's a great example of using concurrent programming to hide latency. In other words, they can't make DNS resolution go any faster but they can pre-fetch and cache to give the illusion of increased speed when you need to resolve.

Here's a great short video from Jim Roskind to explain it in simple terms:


Classical Test Functions for Genetic Algorithms

Recently, I was talking to a rather intelligent chap who was quizzing me on some research I did many years ago. I gave him a simplistic explanation of discrete optimization and genetic algorithms and he fired back a very good question... how do you measure how good a genetic optimization algorithm is? Clearly, you test it on something that you know the global optimum of and see if the algorithm can find it. But there is more to it than that. We also need to use a problem that makes it hard for the algo to get to the "global optima". There are 2 such functions that come to mind that are often used precisely for this purpose...

The Rastrigin Function

where x can range from -5.12 to +5.12.

But it's best visualised as a plot:

As you can see, the external variable A controls the amplitude of the peaks. It should also be clear that this is a non-linear, multimodal function that is not convex. In other words, this function has been custom made to contain many "local minima". A local minimum is a value that is the smallest value in a given area but is not the global minimum. These local minima are the blue-shaded "valleys" in the plot. The global minimum is obviously the smallest value of the function over the entire area. In the case of the Rastrigin function the global minimum is 0 at (0,0) in the two-dimension version of this function.

At any local minimum other than (0,0) the value of Rastrigin's function is greater than 0. In fact, the farther the local minimum is from the origin the larger the value of the function is at that point. The presence of all of these local minima is precisely why this function is often used to test genetic algorithms, because the numerous local minima make it difficult for standard, gradient-based methods to find the global minimum.

Rosenbrock Function

You can read more about it at Wikipedia but again it's best illustrated with a plot:

From Wikipedia, "The global minimum is inside a long, narrow, parabolic shaped flat valley. To find the valley is trivial, however to converge to the global minimum is difficult."

There are others, but these 2 functions are a damn good test for any genetic / evolutionary algo you need to shake out.


20 Things About Web Apps

I love it when people explain complex topics in simple terms. Not because I'm a simpleton but because it makes the knowledge more accessible to the wider audience who really ought to know more about this stuff.

With the "Rich vs Reach" debate still raging between desktop and web developers (and firms with a vested interest in either. i.e. Microsoft and Google), the Google Chrome team put together this nice little booklet to convey information about web-delivered applications. Sure, they have a very strong preference for web apps but it is a fairly impartial summary.

Put simply web apps are moving forward in leaps and bounds because of many great innovations:

  • Developer tools like GWT (Java to JS) and WebSharper (F# to JS) are being created to allow developers to generate pesky JavaScript code from other higher-level languages, to accommodate folks who aren't JavaScript fans. This enables much easier development of web apps for those who are from a desktop development background;
  • Modern browsers, like Chrome (V8), FireFox and IE9 (Chakra), have much smarter JavaScript engines that compile rather than interpret JavaScript. This makes JavaScript code run a heck of a lot faster than it use to;
  • The slowest parts of web page rendering: image downloads and DNS resolution, are being addressed by new image compression techniques, like WebP, and browser features like DNS pre-fetching;
  • The new HTML5 standard includes many new features like the canvas tag, the video tag, and web sockets that make for a much richer in-browser user experience; and
  • New techniques help minimize the latency associated with server round-trips that typified web apps for many years. Currently, developers resort to Ajax and Comet techniques to hide or minimize the latency but Comet is hard to get right across all browsers. The HTML 5 WebSocket represents a standardized way to address the problem that has been targeted by Comet and Ajax in that it defines a single-socket full-duplex/bi-directional connection for pushing/pulling information between the browser and server. Thus, it avoids the connection and portability issues of Comet and provides a more efficient solution than Ajax polling.

The next 5 years is going to see some really cool web applications that are installation-free, have "desktop-like" user experience, and are backed by on-demand super computers. i.e the cloud. I can't wait to see where it goes from here!

Next »