Gallery of Processor Cache Effects

by

Most of my readers will understand that cache is a fast but small type of memory that stores recently accessed memory locations.  This description is reasonably accurate, but the “boring” details of how processor caches work can help a lot when trying to understand program performance.

In this blog post, I will use code samples to illustrate various aspects of how caches work, and what is the impact on the performance of real-world programs.

The examples are in C#, but the language choice has little impact on the performance scores and the conclusions they lead to.

Example 1: Memory accesses and performance

How much faster do you expect Loop 2 to run, compared Loop 1?

int[] arr = new int[64 * 1024 * 1024];

Read more

Human heart is a Turing machine, research on XBox 360 shows. Wait, what?

by

211px-CoeurHumain_svgDid you ever see one of those auto-generated random “academic papers” like this one? When I first saw the following title, my first thought was that it is a randomly-generated “paper”:

Implications of the Turing completeness of reaction-diffusion models, informed by GPGPU simulations on an XBox 360: Cardiac arrhythmias, re-entry and the Halting problem [PDF]

Turing completeness, cardiac arrhythmias, XBox 360… those things don’t seem to have much in common. But, I had my interest piqued. I looked up the paper and read through it. And, it turns out that not only is the paper serious, what it has to say is also quite interesting.

Read more

Program like a Quake developer

by

Not many developers have the insights of Michael Abrash. He is a game developer with decades of experience building commercial games, including a game you may recognize as "Quake". His Graphics Programming Black Book is years old, but much of it is just as interesting as it was at the time of writing. And, the … Read more

Efficient auto-complete with a ternary search tree

by

Over the past couple of years, auto-complete has popped up all over the web. Facebook, YouTube, Google, Bing, MSDN, LinkedIn and lots of other websites all try to complete your phrase as soon as you start typing.

Auto-complete definitely makes for a nice user experience, but it can be a challenge to implement efficiently. In many cases, an efficient implementation requires the use of interesting algorithms and data structures. In this blog post, I will describe one simple data structure that can be used to implement auto-complete: a ternary search tree.

Trie: simple but space-inefficient

Read more

7 tips for extending browser functionality to Silverlight apps

by

Silverlight 2 is an awesome platform for development of rich web applications. One issue to be aware of, though, is that some browser features do not extend into Silverlight apps. For example, the Back and Forward browser buttons do not always work as the user may expect with Silverlight apps. The set of browser features you’ll miss in Silverlight apps is pretty much identical to what you’d miss in Flash or AJAX, and some of them are about to be addressed in the Silverlight 3 release.

Let’s go over the affected browser features one by one, and discuss ways of getting them working in Silverlight apps.

Feature 1: Bookmarking and deep linking

Read more

My YouTube debut: a RoboZZle demo video

by

It took significantly longer than I expected, but the RoboZZle demo video is finally on YouTube. The video made the reddit front page, so you can read the usual mixture of insightful, funny, and outright insane comments on the reddit page and the YouTube page. My favorite funny comment is this one: And finally, this is … Read more

Precomputed view: A cool and useful SQL pattern

by

In database terminology, a view is a named query that typically aggregates data from multiple tables. When using views, it is important to remember that querying a view will evaluate the query that defines the view. Repeated evaluation of the view – say from within a nested query – may seriously impact or even kill the performance of your application.

One solution to this performance problem is to use a “precomputed view”. Unlike an ordinary view, a precomputed view is stored in a table rather than computed on demand. When data in one of the aggregated tables changes, the update operation also updates the precomputed view table.

Read more

Choose expression: proposal for a revolutionary C# construct

by

Notice that this post was published on April 1, 2009.

For decades, computer science students have been taught that so-called NP-hard problems do not have known efficient solutions. These problems include the infamous Travelling salesman problem, subset sum, 3SAT, and many more.

But – as is often the case – where theoretical Computer Science failed, sound software engineering practices will succeed. By using loosely-coupled OOP, agile methodologies and the model-view-controller architectural pattern, I developed a solution that someone trapped in the world of formulas and big Ohs would never dream of.

Enough with the background, and let’s take a deep dive into the intriguing design.

Read more