The memory model is a fascinating topic – it touches on hardware, concurrency, compiler optimizations, and even math.

The memory model defines what state a thread may see when it reads a memory location modified by other threads. For example, if one thread updates a regular non-volatile field, it is possible that another thread reading the field will never observe the new value. This program never terminates (in a release build):

class Test
{
    private bool _loop = true;

    public static void Main()
    {
        Test test1 = new Test();

        // Set _loop to false on another thread
        new Thread(() => { test1._loop = false;}).Start();

        // Poll the _loop field until it is set to false
        while (test1._loop == true) ;

        // The loop above will never terminate!
    }
}

There are two possible ways to get the while loop to terminate:

1. Use a lock to protect all accesses (reads and writes) to the _loop field
2. Mark the _loop field as volatile

There are two reasons why a read of a non-volatile field may observe a stale value: compiler optimizations and processor optimizations.

Compiler optimizations

The first reason why a non-volatile read may return a stale value has to do with compiler optimizations. In the infinite loop example, the JIT compiler optimizes the while loop from this:

while (test1._loop == true) ;

To this:

if (test1._loop) { while (true); }

This is an entirely reasonable transformation if only one thread accesses the _loop field. But, if another thread changes the value of the field, this optimization can prevent the reading thread from noticing the updated value.

If you mark the _loop field as volatile, the compiler will not hoist the read out of the loop. The compiler will know that other threads may be modifying the field, and so it will be careful to avoid optimizations that would result in a read of a stale value.

00000068  test        eax,eax
0000006a  jne         00000068

00000064  cmp         byte ptr [eax+4],0
00000068  jne         00000064

Processor optimizations

On some processors, not only must the compiler avoid certain optimizations on volatile reads and writes, it also has to use special instructions. On a multi-core machine, different cores have different caches. The processors may not bother to keep those caches coherent by default, and special instructions may be needed to flush and refresh the caches.

The mainstream x86 and x64 processors implement a strong memory model where memory access is effectively volatile. So, a volatile field forces the compiler to avoid some high-level optimizations like hoisting a read out of a loop, but otherwise results in the same assembly code as a non-volatile read.

The Itanium processor implements a weaker memory model. To target Itanium, the JIT compiler has to use special instructions for volatile memory accesses: LD.ACQ and ST.REL, instead of LD and ST. Instruction LD.ACQ effectively says, “refresh my cache and then read a value” and ST.REL says, “write a value to my cache and then flush the cache to main memory”. LD and ST on the other hand may just access the processor’s cache, which is not visible to other processors.

Volatile accesses in more depth

To understand how volatile and non-volatile memory accesses work, you can imagine each thread as having its own cache. Consider a simple example with a non-volatile memory location (i.e. a field) u, and a volatile memory location v.

A non-volatile write could just update the value in the thread’s cache, and not the value in main memory:

However, in C# all writes are volatile (unlike say in Java), regardless of whether you write to a volatile or a non-volatile field. So, the above situation actually never happens in C#.

A volatile write updates the thread’s cache, and then flushes the entire cache to main memory. If we were to now set the volatile field v to 11, both values u and v would get flushed to main memory:

Since all C# writes are volatile, you can think of all writes as going straight to main memory.

A regular, non-volatile read can read the value from the thread’s cache, rather than from main memory. Despite the fact that thread 1 set u to 11, when thread 2 reads u, it will still see value 10:

When you read a non-volatile field in C#, a non-volatile read occurs, and you may see a stale value from the thread’s cache. Or, you may see the updated value. Whether you see the old or the new value depends on your compiler and your processor.

Finally, let’s take a look at an example of a volatile read. Thread 2 will read the volatile field v:

Before the volatile read, thread 2 refreshes its entire cache, and then reads the updated value of v: 11. So, it will observe the value  that is really in main memory, and also refresh its cache as a bonus.

Note that the thread caches that I described are imaginary – there really is no such thing as a thread cache. Threads only appear to have these caches as an artifact of compiler and processor optimizations.

volatile string[] _args = null;

public void Write() {
    string[] a = new string[2];
    a[0] = "arg1";
    a[1] = "arg2";
    _args = a;
    ...
}

public void Read() {
    if (_args != null) {
        // Under weak volatile semantics, this assert could fail!
        Debug.Assert(_args[0] != null);
    }
}

Memory model and .NET operations

Here is a table of how various .NET operations interact with the imaginary thread cache:

For each operation, the table shows two things:

• Is the entire imaginary thread cache refreshed from main memory before the operation?
• Is the entire imaginary thread cache flushed to main memory after the operation?

Disclaimer and limitations of the model

This blog post reflects my personal understanding of the .NET memory model, and is based purely on publicly available information.

I find the explanation based on imaginary thread caches more intuitive than the more commonly used explanation based on operation reordering. The thread cache model is also accurate for most intents and purposes.

To be even more accurate, you should assume that the thread caches can form an arbitrary large hierarchy, and so you cannot assume that a read is served only from two possible places – main memory or the thread’s cache. I think that you would have to construct a somewhat of a clever case in order for the cache hierarchy to make a difference, though. If anyone is aware of a case where the hierarchical thread cache model makes a prediction different from the reordering-based model, I would love to hear about it.

If you are interested in the .NET memory model, I encourage you to read Understand the Impact of Low-Lock Techniques in Multithreaded Apps in the MSDN Magazine, and the Memory model blog post from Chris Brumme.

As a software developer, you certainly have a high-level picture of how web apps work and what kinds of technologies are involved: the browser, HTTP, HTML, web server, request handlers, and so on.

In this article, we will take a deeper look at the sequence of events that take place when you visit a URL.

1. You enter a URL into the browser

It all starts here:

2. The browser looks up the IP address for the domain name

The first step in the navigation is to figure out the IP address for the visited domain. The DNS lookup proceeds as follows:

• Browser cache – The browser caches DNS records for some time. Interestingly, the OS does not tell the browser the time-to-live for each DNS record, and so the browser caches them for a fixed duration (varies between browsers, 2 – 30 minutes).
• OS cache – If the browser cache does not contain the desired record, the browser makes a system call (gethostbyname in Windows). The OS has its own cache.
• Router cache – The request continues on to your router, which typically has its own DNS cache.
• ISP DNS cache – The next place checked is the cache ISP’s DNS server. With a cache, naturally.
• Recursive search – Your ISP’s DNS server begins a recursive search, from the root nameserver, through the .com top-level nameserver, to Facebook’s nameserver. Normally, the DNS server will have names of the .com nameservers in cache, and so a hit to the root nameserver will not be necessary.

Here is a diagram of what a recursive DNS search looks like:

3. The browser sends a HTTP request to the web server

You can be pretty sure that Facebook’s homepage will not be served from the browser cache because dynamic pages expire either very quickly or immediately (expiry date set to past).

So, the browser will send this request to the Facebook server:

GET http://facebook.com/ HTTP/1.1
Accept: application/x-ms-application, image/jpeg, application/xaml+xml, [...]
User-Agent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; WOW64; [...]
Accept-Encoding: gzip, deflate
Connection: Keep-Alive
Host: facebook.com
Cookie: datr=1265876274-[...]; locale=en_US; lsd=WW[...]; c_user=2101[...]

The GET request names the URL to fetch: “http://facebook.com/”. The browser identifies itself (User-Agent header), and states what types of responses it will accept (Accept and Accept-Encoding headers). The Connection header asks the server to keep the TCP connection open for further requests.

The request also contains the cookies that the browser has for this domain. As you probably already know, cookies are key-value pairs that track the state of a web site in between different page requests. And so the cookies store the name of the logged-in user, a secret number that was assigned to the user by the server, some of user’s settings, etc. The cookies will be stored in a text file on the client, and sent to the server with every request.

4. The facebook server responds with a permanent redirect

This is the response that the Facebook server sent back to the browser request:

HTTP/1.1 301 Moved Permanently
Cache-Control: private, no-store, no-cache, must-revalidate, post-check=0,
      pre-check=0
Expires: Sat, 01 Jan 2000 00:00:00 GMT
Location: http://www.facebook.com/
P3P: CP="DSP LAW"
Pragma: no-cache
Set-Cookie: made_write_conn=deleted; expires=Thu, 12-Feb-2009 05:09:50 GMT;
      path=/; domain=.facebook.com; httponly
Content-Type: text/html; charset=utf-8
X-Cnection: close
Date: Fri, 12 Feb 2010 05:09:51 GMT
Content-Length: 0

The server responded with a 301 Moved Permanently response to tell the browser to go to “http://www.facebook.com/” instead of “http://facebook.com/”.

5. The browser follows the redirect

The browser now knows that “http://www.facebook.com/” is the correct URL to go to, and so it sends out another GET request:

GET http://www.facebook.com/ HTTP/1.1
Accept: application/x-ms-application, image/jpeg, application/xaml+xml, [...]
Accept-Language: en-US
User-Agent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.1; WOW64; [...]
Accept-Encoding: gzip, deflate
Connection: Keep-Alive
Cookie: lsd=XW[...]; c_user=21[...]; x-referer=[...]
Host: www.facebook.com

The meaning of the headers is the same as for the first request.

6. The server ‘handles’ the request

The server will receive the GET request, process it, and send back a response.

This may seem like a straightforward task, but in fact there is a lot of interesting stuff that happens here – even on a simple site like my blog, let alone on a massively scalable site like facebook.

• Web server software
  The web server software (e.g., IIS or Apache) receives the HTTP request and decides which request handler should be executed to handle this request. A request handler is a program (in ASP.NET, PHP, Ruby, …) that reads the request and generates the HTML for the response.

  In the simplest case, the request handlers can be stored in a file hierarchy whose structure mirrors the URL structure, and so for example http://example.com/folder1/page1.aspx URL will map to file /httpdocs/folder1/page1.aspx. The web server software can also be configured so that URLs are manually mapped to request handlers, and so the public URL of page1.aspx could be http://example.com/folder1/page1.

• Request handler
  The request handler reads the request, its parameters, and cookies. It will read and possibly update some data stored on the server. Then, the request handler will generate a HTML response.

7. The server sends back a HTML response

Here is the response that the server generated and sent back:

HTTP/1.1 200 OK
Cache-Control: private, no-store, no-cache, must-revalidate, post-check=0,
    pre-check=0
Expires: Sat, 01 Jan 2000 00:00:00 GMT
P3P: CP="DSP LAW"
Pragma: no-cache
Content-Encoding: gzip
Content-Type: text/html; charset=utf-8
X-Cnection: close
Transfer-Encoding: chunked
Date: Fri, 12 Feb 2010 09:05:55 GMT

2b3��������T�n�@����[...]

The entire response is 36 kB, the bulk of them in the byte blob at the end that I trimmed.

The Content-Encoding header tells the browser that the response body is compressed using the gzip algorithm. After decompressing the blob, you’ll see the HTML you’d expect:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"   
      "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"
      lang="en" id="facebook" class=" no_js">
<head>
<meta http-equiv="Content-type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-language" content="en" />
...

In addition to compression, headers specify whether and how to cache the page, any cookies to set (none in this response), privacy information, etc.

8. The browser begins rendering the HTML

Even before the browser has received the entire HTML document, it begins rendering the website:

9. The browser sends requests for objects embedded in HTML

As the browser renders the HTML, it will notice tags that require fetching of other URLs. The browser will send a GET request to retrieve each of these files.

Here are a few URLs that my visit to facebook.com retrieved:

• Images
  http://static.ak.fbcdn.net/rsrc.php/z12E0/hash/8q2anwu7.gif
  http://static.ak.fbcdn.net/rsrc.php/zBS5C/hash/7hwy7at6.gif
  …
• CSS style sheets
  http://static.ak.fbcdn.net/rsrc.php/z448Z/hash/2plh8s4n.css
  http://static.ak.fbcdn.net/rsrc.php/zANE1/hash/cvtutcee.css
  …
• JavaScript files
  http://static.ak.fbcdn.net/rsrc.php/zEMOA/hash/c8yzb6ub.js
  http://static.ak.fbcdn.net/rsrc.php/z6R9L/hash/cq2lgbs8.js
  …

Each of these URLs will go through process a similar to what the HTML page went through. So, the browser will look up the domain name in DNS, send a request to the URL, follow redirects, etc.

However, static files – unlike dynamic pages – allow the browser to cache them. Some of the files may be served up from cache, without contacting the server at all. The browser knows how long to cache a particular file because the response that returned the file contained an Expires header. Additionally, each response may also contain an ETag header that works like a version number – if the browser sees an ETag for a version of the file it already has, it can stop the transfer immediately.

10. The browser sends further asynchronous (AJAX) requests

In the spirit of Web 2.0, the client continues to communicate with the server even after the page is rendered.

For example, Facebook chat will continue to update the list of your logged in friends as they come and go. To update the list of your logged-in friends, the JavaScript executing in your browser has to send an asynchronous request to the server. The asynchronous request is a programmatically constructed GET or POST request that goes to a special URL. In the Facebook example, the client sends a POST request to http://www.facebook.com/ajax/chat/buddy_list.php to fetch the list of your friends who are online.

This pattern is sometimes referred to as “AJAX”, which stands for “Asynchronous JavaScript And XML”, even though there is no particular reason why the server has to format the response as XML. For example, Facebook returns snippets of JavaScript code in response to asynchronous requests.

Conclusion

Hopefully this gives you a better idea of how the different web pieces work together.

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

// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;

// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;

The first loop multiplies every value in the array by 3, and the second loop multiplies only every 16-th. The second loop only does about 6% of the work of the first loop, but on modern machines, the two for-loops take about the same time: 80 and 78 ms respectively on my machine.

The reason why the loops take the same amount of time has to do with memory. The running time of these loops is dominated by the memory accesses to the array, not by the integer multiplications. And, as I’ll explain on Example 2, the hardware will perform the same main memory accesses for the two loops.

Example 2: Impact of cache lines

Let’s explore this example deeper. We will try other step values, not just 1 and 16:

for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;

Here are the running times of this loop for different step values (K):

Notice that while step is in the range from 1 to 16, the running time of the for-loop hardly changes. But from 16 onwards, the running time is halved each time we double the step.

The reason behind this is that today’s CPUs do not access memory byte by byte. Instead, they fetch memory in chunks of (typically) 64 bytes, called cache lines. When you read a particular memory location, the entire cache line is fetched from the main memory into the cache. And, accessing other values from the same cache line is cheap!

Since 16 ints take up 64 bytes (one cache line), for-loops with a step between 1 and 16 have to touch the same number of cache lines: all of the cache lines in the array. But once the step is 32, we’ll only touch roughly every other cache line, and once it is 64, only every fourth.

Understanding of cache lines can be important for certain types of program optimizations. For example, alignment of data may determine whether an operation touches one or two cache lines. As we saw in the example above, this can easily mean that in the misaligned case, the operation will be twice slower.

Example 3: L1 and L2 cache sizes

Today’s computers come with two or three levels of caches, usually called L1, L2 and possibly L3. If you want to know the sizes of the different caches, you can use the CoreInfo SysInternals tool, or use the GetLogicalProcessorInfo Windows API call. Both methods will also tell you the cache line sizes, in addition to the cache sizes.

On my machine, CoreInfo reports that I have a 32kB L1 data cache, a 32kB L1 instruction cache, and a 4MB L2 data cache. The L1 caches are per-core, and the L2 caches are shared between pairs of cores:

Logical Processor to Cache Map:
*---  Data Cache          0, Level 1,   32 KB, Assoc   8, LineSize  64
*---  Instruction Cache   0, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Data Cache          1, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Instruction Cache   1, Level 1,   32 KB, Assoc   8, LineSize  64
**--  Unified Cache       0, Level 2,    4 MB, Assoc  16, LineSize  64
--*-  Data Cache          2, Level 1,   32 KB, Assoc   8, LineSize  64
--*-  Instruction Cache   2, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Data Cache          3, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Instruction Cache   3, Level 1,   32 KB, Assoc   8, LineSize  64
--**  Unified Cache       1, Level 2,    4 MB, Assoc  16, LineSize  64

Let’s verify these numbers by an experiment. To do that, we’ll step over an array incrementing every 16th integer – a cheap way to modify every cache line. When we reach the last value, we loop back to the beginning. We’ll experiment with different array sizes, and we should see drops in the performance at the array sizes where the array spills out of one cache level.

Here is the program:

int steps = 64 * 1024 * 1024; // Arbitrary number of steps
int lengthMod = arr.Length - 1;
for (int i = 0; i < steps; i++)
{
    arr[(i * 16) & lengthMod]++; // (x & lengthMod) is equal to (x % arr.Length)
}

And here are the timings:

You can see distinct drops after 32kB and 4MB – the sizes of L1 and L2 caches on my machine.

Example 4: Instruction-level parallelism

Now, let’s take a look at something different. Out of these two loops, which one would you expect to be faster?

int steps = 256 * 1024 * 1024;
int[] a = new int[2];

// Loop 1
for (int i=0; i<steps; i++) { a[0]++; a[0]++; }

// Loop 2
for (int i=0; i<steps; i++) { a[0]++; a[1]++; }

It turns out that the second loop is about twice faster than the first loop, at least on all of the machines I tested. Why? This has to do with the dependencies between operations in the two loop bodies.

In the body of the first loop, operations depend on each other as follows:

But in the second example, we only have these dependencies:

The modern processor has various parts that have a little bit of parallelism in them: it can access two memory locations in L1 at the same time, or perform two simple arithmetic operations. In the first loop, the processor cannot exploit this instruction-level parallelism, but in the second loop, it can.

[UPDATE]: Many people on reddit are asking about compiler optimizations, and whether { a[0]++; a[0]++; } would just get optimized to { a[0]+=2; }. In fact, the C# compiler and CLR JIT will not do this optimization – not when array accesses are involved. I built all of the tests in release mode (i.e. with optimizations), but I looked at the JIT-ted assembly to verify that optimizations aren’t skewing the results.

Example 5: Cache associativity

One key decision in cache design is whether each chunk of main memory can be stored in any cache slot, or in just some of them.

There are three possible approaches to mapping cache slots to memory chunks:

1. Direct mapped cache

   Each memory chunk can only be stored only in one particular slot in the cache. One simple solution is to map the chunk with index chunk_index to cache slot (chunk_index % cache_slots). Two memory chunks that map to the same slot cannot be stored simultaneously in the cache.

2. N-way set associative cache

   Each memory chunk can be stored in any one of N particular slots in the cache. As an example, in a 16-way cache, each memory chunk can be stored in 16 different cache slots. Commonly, chunks with indices with the same lowest order bits will all share 16 slots.

3. Fully associative cache

   Each memory chunk can be stored in any slot in the cache. Effectively, the cache operates like a hash table.

Direct mapped caches can suffer from conflicts – when multiple values compete for the same slot in the cache, they keep evicting each other out, and the hit rate plummets. On the other hand, fully associative caches are complicated and costly to implement in the hardware. N-way set associative caches are the typical solution for processor caches, as they make a good trade off between implementation simplicity and good hit rate.

For example, the 4MB L2 cache on my machine is 16-way associative. All 64-byte memory chunks are partitioned into sets (based on the lowest order bits of the chunk index), and chunks in the same set compete for 16 slots in the L2 cache.

Since the L2 cache has 65,536 slots, and each set will need 16 slots in the cache, we will have 4,096 sets. So, the lowest 12 bits of the chunk index will determine which set the chunk belongs to (2¹² = 4,096). As a result, cache lines at addresses that differ by a multiple of 262,144 bytes (4096 * 64) will compete for the same slot in the cache. The cache on my machine can hold at most 16 such cache lines.

In order for the effects of cache associativity to become apparent, I need to repeatedly access more than  16 elements from the same set. I will demonstrate this using the following method:

public static long UpdateEveryKthByte(byte[] arr, int K)
{
    Stopwatch sw = Stopwatch.StartNew();
    const int rep = 1024*1024; // Number of iterations – arbitrary

    int p = 0;
    for (int i = 0; i < rep; i++)
    {
        arr[p]++;
        p += K;
        if (p >= arr.Length) p = 0;
    }

    sw.Stop();
    return sw.ElapsedMilliseconds;
}

This method increments every K-th value in the array. Once the it reaches the end of the array, it starts again from the beginning. After running sufficiently long (2^20 steps), the loop stops.

I ran UpdateEveryKthByte() with different array sizes (in 1MB increments) and different step sizes. Here is a plot of the results, with blue representing long running time, and white representing short:

The blue areas (long running times) are cases where the updated values could not be simultaneously held in the cache as we repeatedly iterated over them. The bright blue areas correspond to running times of ~80 ms, and the nearly white areas to ~10 ms.

Let’s explain the blue parts of the chart:

1. Why the vertical lines?The vertical lines show the step values that touch too many memory locations (>16) from the same set. For those steps, we cannot simultaneously hold all touched values in the 16-way associative cache on my machine.

   Some bad step values are powers of two: 256 and 512. As an example, consider step 512 on an 8MB array. An 8MB cache line contains 32 values that are spaced by 262,144 bytes apart. All of those values will be updated by each pass of our loop, because 512 divides 262,144.

   And since 32 > 16, those 32 values will keep competing for the same 16 slots in the cache.

   Some values that are not powers of two are simply unfortunate, and will end up visiting disproportionately many values from the same set. Those step values will also show up as as blue lines.

2. Why do the vertical lines stop at 4MB array length?On arrays of 4MB or less, a 16-way associative cache is just as good as a fully associative one.

   A 16-way associative cache can hold at most 16 cache lines that are a multiple of 262,144 bytes apart. There is no set of 17 or more cache lines all aligned on 262,144-byte boundaries within 4MB, because 16 * 262,144 = 4,194,304.

3. Why the blue triangle in upper left?In the triangle area, we cannot hold all necessary data in cache simultaneously … not due to the associativity, but simply because of the L2 cache size limit.

   For example, consider the array length 16MB with step 128. We are repeatedly updating every 128th byte in the array, which means that we touch every other 64-byte memory chunk. To store every other cache line of a 16MB array, we’d need 8MB cache. But, my machine only has 4MB of cache.

   Even if the 4MB cache on my machine was fully associative, it still wouldn’t be able to hold 8MB of data.

4. Why does the triangle fade out in the left?Notice that the gradient goes from 0 to 64 bytes – one cache line! As explained in examples 1 and 2, additional accesses to same cache line are nearly free. For example, when stepping by 16 bytes, it will take 4 steps to get to the next cache line. So, we get four memory accesses for the price of one.

   Since the number of steps is the same for all cases, a cheaper step results in a shorter running time.

These patterns continue to hold as you extend the chart:

Cache associativity is interesting to understand and can certainly be demonstrated, but it tends to be less of a problem compared to the other issues discussed in this article. It is certainly not something that should be at the forefront of your mind as you write programs.

Example 6: False cache line sharing

On multi-core machines, caches encounter another problem – consistency. Different cores have fully or partly separate caches. On my machine, L1 caches are separate (as is common), and there are two pairs of processors, each pair sharing an L2 cache. While the details vary, a modern multi-core machine will have a multi-level cache hierarchy, where the faster and smaller caches belong to individual processors.

When one processor modifies a value in its cache, other processors cannot use the old value anymore. That memory location will be invalidated in all of the caches. Furthermore, since caches operate on the granularity of cache lines and not individual bytes, the entire cache line will be invalidated in all caches!

To demonstrate this issue, consider this example:

private static int[] s_counter = new int[1024];
private void UpdateCounter(int position)
{
    for (int j = 0; j < 100000000; j++)
    {
        s_counter[position] = s_counter[position] + 3;
    }
}

On my quad-core machine, if I call UpdateCounter with parameters 0,1,2,3 from four different threads, it will take 4.3 seconds until all threads are done.

On the other hand, if I call UpdateCounter with parameters 16,32,48,64 the operation will be done in 0.28 seconds!

Why? In the first case, all four values are very likely to end up on the same cache line. Each time a core increments the counter, it invalidates the cache line that holds all four counters. All other cores will suffer a cache miss the next time they access their own counters. This kind of thread behavior effectively disables caches, crippling the program’s performance.

Example 7: Hardware complexities

Even when you know the basics of how caches work, the hardware will still sometimes surprise you. Different processors differ in optimizations, heuristics, and subtle details of how they do things.

On some processors, L1 cache can process two accesses in parallel if they access cache lines from different banks, and serially if they belong to the same bank. Also, processors can surprise you with clever optimizations. For example, the false-sharing example that I’ve used on several machines in the past did not work well on my machine without tweaks – my home machine can optimize the execution in the simplest cases to reduce the cache invalidations.

Here is one odd example of “hardware weirdness”:

private static int A, B, C, D, E, F, G;
private static void Weirdness()
{
    for (int i = 0; i < 200000000; i++)
    {
        <something>
    }
}

When I substitute three different blocks for “<something>”, I get these timings:

Incrementing fields A,B,C,D takes longer than incrementing fields A,C,E,G. And what’s even weirder, incrementing just A and C takes longer than increment A and C and E and G!

I don’t know for sure what is the reason behind these numbers, but I suspect it is related to memory banks. If someone can explain these numbers, I’d be very curious to hear about it.

The lesson of this example is that can be difficult to fully predict hardware performance. There is a lot that you can predict, but ultimately, it is very important to measure and verify your assumptions.

Conclusion

Hopefully all of this helps you understand how caches work, and apply that knowledge when tuning your programs.

The video of my session is available as Silverlight video, and also as high-quality WMV and standard-quality WMV. Here are the slides. Check it out and let me know how I did!

And, here are videos of all PDC sessions related to parallel programming.

Never having presented at PDC before, I didn’t know how many people to expect at my session. I was happy with the turn out – this is a view of my session from the back of the room:

Around two weeks ago, I found this email in my inbox, with the subject “Complaint about Robozzle”:

Hi Igor

Robozzle is really cute, I like it, but why on earth is it polluted with hundreds of invisible links to porn sites? From a guy like you I don’t expect to do such dirty things. pls remove them.

David

Hoping for a simple explanation, I looked at the source of the RoboZZle front page. And my heart sunk as I saw hundreds of spam links on the bottom:

<a href=”<a hijacked site>.com/files/cms/7/pornhud.com-20076.html”>porn hud.com</a>
<a href=”<a hijacked site>.com/files/cms/7/www.tube.com8-5852.html”>www.tube.com 8</a>
…

The links were inside a <p> tag with visibility set to “hidden”, so the links were only visible to search engines, not to human visitors.

I wondered if this affected how my site shows up in search engines. So, I searched for RoboZZle on Google (results in Bing or Yahoo! were not affected), and here is what I got:

Oh crap. This sucks. How did it happen?

Site infestation

So what did the hackers do to my poor game? I looked around to find what has changed:

1. Planted links
   Multiple pages on my site have been modified to import a planted config.ini file. The config.ini file contained hundreds of fake links, and was updated every couple hours with a new set of links. The links all pointed to spammy content planted on another hijacked site.
    
2. Planted content
   My site also contained thousands of small planted HTML files, similar to the spammy stuff that the planted links pointed to. An odd folder (something like http://robozzle.com/old/old2/) contained the HTML files, all with links to suspicious content, and all infested with spammy keywords.
    
3. Backdoor PHP scripts
   And finally, my site also contained a couple of PHP backdoor scripts. If you visited a particular URL on the robozzle.com domain, you’d get a file manager that lets you upload, delete, and manage files on my site, no passwords needed. As I found out later, the hackers actually knew my FTP password so they didn’t need the backdoors, but they left the backdoors so that they can get in once I change my password.

I carefully checked my site and removed all of this stuff. Even after I removed the PHP backdoors, the config.ini file continued to get updated until I changed my FTP password. From that point, I was pretty sure that the attackers somehow got my FTP password.

Looking for other hijacked sites

After cleaning up my site, one of the first things I did was notify the other compromised site, which hosted the planted content linked from my site.

I also wondered if more sites have been hacked in a similar way. I tried various online tools to find other sites that contain the same links that have been planted on my site.

I found a handful of hacked sites right away. The fact that the links change every few hours made the task more difficult, though. The newest links generally point to content that has not yet been crawled by search engines. But, there is a simple solution. By looking at older versions of several compromised sites in a service like Google Cache, I eventually found older links that lead me to many more hijacked sites.

After repeating the process for a couple hours, I ended up with a list of over a 150 infected sites, including some fairly major sites. The larger sites generally removed the infestation quickly, though. Here are a few sites that haven’t cleaned up, despite the fact that I alerted them at least two weeks ago:

• bayonnenj.org – City of Bayonne, NJ
• steinercollege.edu – Rudolf Steiner College
• dillard.senategop.org – GOP Senator Kirk Dillard
• egnc-ibm.gov.eg – Egypt-IBM Nanotechnology Research Center

Don’t go to these sites unless you know what you are doing. At the time of writing this post, these sites appear to be compromised, so they may well contain viruses or malware.

UPDATE: Most of the sites are suddenly not showing the links. My guess is that the hacker group distributed an empty config.ini file after this story became popular on reddit. I don’t believe that so many obscure sites on my list would be fixed over night when they have been infected for months before. Some sites still contain the planted links, but those seem to be the ones that haven’t been updating the links regularly. These are probably the sites that the hackers only have partial control over at this point (e.g., FTP password changed, but there is still a backdoor on the site somewhere). You should be able to view the planted links on all infected sites by looking at Google Cache.

I did my best to contact owners of as many hijacked sites as I could. Looking for contact information on that many sites – most of them not in English – is a time-consuming endeavor, though.

Tools I used

I found these tools useful when tracking down other sites that have been hijacked:

And how did I get hacked in the first place?

Of course, I have been wondering about how the hackers got my FTP password in the first place. It wasn’t really guessable or discoverable by brute force, and I didn’t use the same password on other sites.

And then I got an email from my webhost, notifying me that FTP passwords may have been stolen due to a vulnerability. They tracked down the issue to a particular software package they use.

So, I assume that my password got stolen this way. If not, it is also possible that I logged into my site on a computer with a particular virus. Apparently, that’s how many FTP passwords get stolen.

If you liked this article, check out these ones:

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

Numbers that cannot be computed

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.

Heart and logic circuits

I had to take author’s word on the medical aspects of the article, since I know nothing about cardiology. Apparently, understanding of electrical signals between cells in a human heart is important for research into heart arrhythmias. Makes sense.

The important insight of the article is that a logic NOR gate can be simulated using electrical signals between heart cells. Constructing a NOR gate is a powerful result, because similarly to NAND, NOR is a universal logic gate. That means that all other logic gates like AND, OR and NOT can be built out of NORs:

NOT(A)    = NOR(A, A)
OR(A, B)  = NOR(NOR(A, B), NOR(A, B))
AND(A, B) = NOR(NOR(A, A), NOR(B, B))

So, since you can simulate a NOR gate using cardiac cells, you can simulate an arbitrary logic circuit in heart tissue.

Heart and Turing machines

But, there has to be more to the story. The paper title mentioned Turing machines, and logic circuits are not Turing-complete. Halting problem doesn’t even make sense when applied to boolean expressions!

The missing part is the passage of time. See, a logic circuit is not Turing-complete. But, if you take a logic circuit with multiple inputs, the same number of outputs as inputs, and repeatedly apply the circuit over the results of the previous iteration, you get a Turing-complete system. This type of a system can be modeled with behavior of a heart tissue over a period of time.

The most intuitive explanation that I can think of is via Game of Life. In the Game of Life, each cell dies, becomes alive or stays alive depending on how many live neighbors it had in the previous generation.  Here is one example of a Game of Life board in action:

Now, the important observation is that the Game of Life rules can be encoded using a logic circuit. For example, if the eight neighbors of a particular cell are represented as A, B … H, then the rule that the cell becomes alive if it has exactly three neighbors can be encoded as  ((A and B and C and not(D) and … and not(H)) or (A and B and not(C) and D and not(E) … and not(H)) or …). This expression will be combined with an OR together with the situations under which the cell remains alive, rather than becoming alive. This will be a pretty ugly logic circuit, but it should be clear that it can be constructed.

Since Game of Life is known to be Turing-complete, then an “iterated logic circuit” is also Turing-complete, and the behavior of cardiac tissue is … Turing-complete.

Why is this useful?

Proving that a particular behavior of cardiac tissue is Turing-complete is a useful result because it shows that the cardiac tissue is in a certain sense “unpredictable”.

For example, since Game of Life is Turing-complete, the Halting problem applies. So, it is a proven fact that there is no general algorithm that can look at a particular Game of Life board and decide whether the movement will eventually stop or continue forever.

Similarly, there is no algorithm that can decide any of these properties for all Game-of-Life boards:

• Whether the board will ever reach a particular configuration
• Whether the number of live cells will ever exceed X
• Whether the game will ever enter a cycle
• etc.

Since the studied behavior of cardiac tissue is also Turing-complete, there is no general algorithm that can look at the state of cardiac tissue and decide whether the activity will ever stop, enter a regular pattern, achieve a particular configuration, etc. That is certainly a worthwhile result!

What about the XBox?

Constructing a NOR gate out of cardiac cells is computationally intensive, and the researcher used a GPU in an XBox 360 for that task.

However, the paper doesn’t conclusively show that using an XBox was a real benefit. The paper says that a C++ implementation that was originally “designed more for ease of expansion […] than for speed” ran slower on an XBox 360 CPU than an “unoptimized” shader-based implementation on an XBox 360 GPU. Comparing implementations not designed for speed is unconvincing. If the goal was to speed up the computation, why not first try to optimize the original code instead of porting it to shaders, which is undoubtedly a much more difficult task?

Also, the article doesn’t say how did XBox 360 CPU compare against an ordinary x86 machine, or against say a CUDA-based implementation on a common NVidia card. So, the paper doesn’t come close to showing that the researchers gained much by coding against the XBox 360 GPU, rather than following the current state-of-the-art approaches.

But, it is still a cool paper, and adding XBox 360 into the picture certainly attracted attention. The paper was reported in press, with titles such as these:

• How Xbox Can Help Fight Heart Disease [time.com].
• Parallel processor computing of XBox chip could save thousands [techshout.com].

And, if it weren’t for the sensational articles, I wouldn’t have found out about the paper at all, so I guess I shouldn’t complain.

The book consists of 70 chapters on optimization, graphics, and assembly programming. The entire book is insightful and interesting, but my favorite chapters are these:

• The Best Optimizer Is between Your Ears
• There Ain’t No Such Thing as the Fastest Code
• Optimizing for 286 and 386, 486 (continued), and Pentium (continued here and here).
• Algorithms for fast drawing of lines, anti-aliased lines, polygons, fast convex polygons, and 3d objects (continued)
• Quake’s visible-surface determination, 3D clipping, hidden-surface removal, span sorting, lighting, surface caching and post-mortem.

Enjoy! Again, the entire book is accessible here: Graphics Programming Black Book.

pre.code { margin-left: 40px; }

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

Before discussing ternary search trees, let’s take a look at a simple data structure that supports a fast auto-complete lookup but needs too much memory: a trie. A trie is a tree-like data structure in which each node contains an array of pointers, one pointer for each character in the alphabet. Starting at the root node, we can trace a word by following pointers corresponding to the letters in the target word.

Each node could be implemented like this in C#:

class TrieNode
{
    public const int ALPHABET_SIZE = 26;
    public TrieNode[] m_pointers = new TrieNode[ALPHABET_SIZE];
    public bool m_endsString = false;
}

Here is a trie that stores words AB, ABBA, ABCD, and BCD. Nodes that terminate words are marked yellow:

Implementing auto complete using a trie is easy. We simply trace pointers to get to a node that represents the string the user entered. By exploring the trie from that node down, we can enumerate all strings that complete user’s input.

But, a trie has a major problem that you can see in the diagram above. The diagram only fits on the page because the trie only supports four letters {A,B,C,D}. If we needed to support all 26 English letters, each node would have to store 26 pointers. And, if we need to support international characters, punctuation, or distinguish between lowercase and uppercase characters, the memory usage grows becomes untenable.

Our problem has to do with the memory taken up by all the null pointers stored in the node arrays. We could consider using a different data structure in each node, such as a hash map. However, managing thousands and thousands of hash maps is generally not a good idea, so let’s take a look at a better solution.

Ternary search tree to the rescue

A ternary tree is a data structure that solves the memory problem of tries in a more clever way. To avoid the memory occupied by unnecessary pointers, each trie node is represented as a tree-within-a-tree rather than as an array. Each non-null pointer in the trie node gets its own node in a ternary search tree.

For example, the trie from the example above would be represented in the following way as a ternary search tree:

The ternary search tree contains three types of arrows. First, there are arrows that correspond to arrows in the corresponding trie, shown as dashed down-arrows. Traversing a down-arrow corresponds to “matching” the character from which the arrow starts. The left- and right- arrow are traversed when the current character does not match the desired character at the current position. We take the left-arrow if the character we are looking for is alphabetically before the character in the current node, and the right-arrow in the opposite case.

For example, green arrows show how we’d confirm that the ternary tree contains string ABBA:

And this is how we’d find that the ternary string does not contain string ABD:

Ternary search tree on a server

On the web, a significant chunk of the auto-complete work has to be done by the server. Often, the set of possible completions is large, so it is usually not a good idea to download all of it to the client. Instead, the ternary tree is stored on the server, and the client will send prefix queries to the server.

The client will send a query for words starting with “bin” to the server:

And the server responds with a list of possible words:

Implementation

Here is a simple ternary search tree implementation in C#:

public class TernaryTree
{
    private Node m_root = null;

    private void Add(string s, int pos, ref Node node)
    {
        if (node == null) { node = new Node(s[pos], false); }

        if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
        else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
        else
        {
            if (pos + 1 == s.Length) { node.m_wordEnd = true; }
            else { Add(s, pos + 1, ref node.m_center); }
        }
    }

    public void Add(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        Add(s, 0, ref m_root);
    }

    public bool Contains(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        int pos = 0;
        Node node = m_root;
        while (node != null)
        {
            int cmp = s[pos] - node.m_char;
            if (s[pos] < node.m_char) { node = node.m_left; }
            else if (s[pos] > node.m_char) { node = node.m_right; }
            else
            {
                if (++pos == s.Length) return node.m_wordEnd;
                node = node.m_center;
            }
        }

        return false;
    }
}

And here is the Node class:

class Node
{
    internal char m_char;
    internal Node m_left, m_center, m_right;
    internal bool m_wordEnd;

    public Node(char ch, bool wordEnd)
    {
        m_char = ch;
        m_wordEnd = wordEnd;
    }
}

Remarks

For best performance, strings should be inserted into the ternary tree in a random order. In particular, do not insert strings in the alphabetical order. Each mini-tree that corresponds to a single trie node would degenerate into a linked list, significantly increasing the cost of lookups. Of course, more complex self-balancing ternary trees can be implemented as well.

And, don’t use a fancier data structure than you have to. If you only have a relatively small set of candidate words (say on the order of hundreds) a brute-force search should be fast enough.

Further reading

Another article on tries is available on DDJ (careful, their implementation assumes that no word is a prefix of another):

http://www.ddj.com/windows/184410528

If you like this article, also check out these posts on my blog:

• Skip lists are fascinating!
• Numbers that cannot be computed
• Quicksort killer

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

Users like to be able to copy the link from the address bar, email it to a friend, bookmark it, or post it on Twitter or Facebook.

A Silverlight app will typically transition between different views without redirecting the user to a different URL. This makes the user experience smooth and polished. As an unfortunate consequence, a user that copies the URL from the address bar or bookmarks the page will not get a link to the current active view, but instead a link to the initial view of the app.

Thankfully, there is a solution in Silverlight. A Silverlight app can modify the “bookmark” section of the URL, which is the part of the URL following the # character. The app can update the URL each time the user transitions to a different view, and read the bookmark on startup. See this article for details on how to implement this.

The Navigation Framework feature in the upcoming Silverlight 3 release will provide an easy-to-use solution to this problem.

Feature 2: Search engine discoverability

If your Silverlight app links to another page, that link is invisible to search engines. As a result, pages on your site that cannot be reached via traditional HTML links will likely not get listed in search results.

The solution is simple: list all pages on your site in an XML document called a Sitemap. Host the Sitemap on your site, and submit the Sitemap link to search engines. Once you do that, the search engines should include all pages on your site in their indexes.

For details, see the Wikipedia article on Sitemaps.

Feature 3: Back and Forward browser buttons

The Back and Forward browser buttons do not work in Silverlight apps. Switching to a different view in a Silverlight app does not insert a bookmark into the browser history, so the user can’t go to the previous view by clicking the Back button.

The problem is similar to the bookmarking issue (Feature 1), except that the solution is more complicated. If the Silverlight app modifies the bookmark part of the URL, the previous bookmark does not get recorded in the browser history, so the user still cannot use the Back button to return to the previous view.

It is in fact possible to get the Back and Forward buttons working. As of SP1 3.5, ASP.NET exposes a History Control that simplifies the solution significantly (see Control Silverlight by Using Browser Back and Forward Buttons). There is a variety of solutions available online in case you are not using ASP.NET 3.5 SP1, but beware that they typically involve hacks that don’t necessarily work in all browsers.

Or, you can wait until Silverlight 3, because browser history is properly handled in the Navigation Framework.

Feature 4: Support of external tools (translation, accessibility, …)

Automated translation, special browsers for people with disabilities, automated RSS aggregating… these are just some examples of useful tools that consume web content. These tools typically process HTML, but don’t peek inside Silverlight applications.

Since HTML is the standard representation of online documents, consider whether it would make sense to expose a simplified version of your content as a simple HTML page, in addition to your Silverlight application.

Feature 5: Printing

Silverlight does not currently have much support for printing. In Internet Explorer 7, Silverlight applications show up on the printout, but in Firefox or Safary they do not.

So, a Firefox or Safari user will not be able to print out the information displayed by your Silverlight application (at least not without taking screenshots, etc).

If you need to support printing, you can try two different solution approaches. If you only need to print content that can be represented using HTML (e.g., no Silverlight-generated charts and such), see this solution. An alternate approach is to convert XAML to an image format on the server.

Feature 6: Open link in new tab

There doesn’t seem to be a very good way to implement the ‘Open link in new tab’ feature in Silverlight. You can use a HyperlinkButton with a Target set to _blank, which seems to open a new tab in Firefox and a new Window in IE 7. But that still won’t allow the user to choose whether to open the page in the same or different tab/window.

If you are committed enough, you can probably implement a HyperlinkButton with a context menu allowing the user to open the link in a new tab/window. Right-clicking is not directly supported in Silverlight, but workarounds do exist.

Or, use hyperlinks sparingly in Silverlight apps.

Feature 7: Find on this page

I use the ‘Find on this page’ feature (CTRL+F) extensively when browsing the web. But, content inside Silverlight apps is not searched by the browser.

A mitigation is to carefully design the app UI in a way that minimizes the user’s need to search. Data should be sortable and searchable in various ways, and important information should be shown prominently (e.g., the user’s own position on a scoreboard should be highlighted).

These are all good practices regardless of your development platform, but unavailability of the ‘Find on this page’ feature makes them even more important.

Conclusion

Hopefully you’ll find these points helpful when designing your next Silverlight application. If you have other tips on extending browser features into Silverlight apps, let me know in the comments!

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 the video: