Memory benchmarks: Addendum tertium: the forgotten TLB

Obviously I have completely forgotten to consider the TLB. In Haswell processors, the L1 TLB contains 64 entries while the L2 TLB holds 1024 entries. All memory accesses must be translated from virtual to physical address, so every single read operation requires a TLB lookup. An L2 TLB miss implies retrieving the TLB entry from memory, so in the worst case a single memory read requires two (chained) memory accesses.

In .Net, page size is 4K, so 1024 TLB entries will cover only 4MB of memory. Remember that the benchmarks executed so far used 1 GB arrays, so in the case of random and chained memory accesses essentially all L2 TLB lookups should fail. But the access times observed don’t seem to exhibit such large delays. So what is going on here? The only explanation I have is that the L3 cache is actually holding all the TLB entries (this could be easily tested by disabling the L3 cache). On x64 a TLB entry is 8 bytes long, so a 25 MB cache will hold one eighth that many TLB entries covering at most 12.5 GB of memory. Hence, to feel the full effect of missed L3 caches we would have to work with arrays much larger than 12.5 GB. I added a few extra tests which deal with much larger arrays. Since I am using arrays of longs and in .Net arrays cannot have more than Int32.MaxValue elements, I have used an array of arrays of longs. Here is an extract of the code for a simplified version of chained reads:

var arrays = sizes.Max().EnumerateTo().Select(t => new long[max]).ToArray();
...
for (int i = 0; i < steps; i++) {
    next = arrays[i%size][(11587L*(i+next)) & mask]; 
    // first array should be retrieved from cache
    // integer division should be negligible 
}

The loop for the random reads is the same except for the next variable not appearing on the right hand side.

Here are the results for the 8 cores machine with 30 GB of memory for chained readd:

Well, the full impact of TLB misses is rather clear, memory access is gone from 110 ns to 185 ns and keeps increasing. Caches have become quite complex and I will not attempt to explain the results! Suffice to say that it exhibits a classic cache saturation curve. For 1GB arrays cache hit is close to 100% (1GB needs only 2 MB of TLB entries), while above 30GB cache hit will be close to 0% (30GB requires 60 MB of TLB entries).  Maximum values will be somewhere around 190 ns or 200 ns, which corresponds to a doubling of the access time (allowing for 10 or 15 ns for L3 access).

The other case to consider  is the random reads one:

For random reads, the shape of the curve is very different… and frankly, I have even less to says 🙂 But a few things are worth mentioning. Firstly it seems to start flat which was not the case for the chained reads. Secondly it saturates at already 10 GB with a latency over three times the starting value, while one could expect the maximum latency to be twice that starting value.

Unsurprisingly there, array size has no effect on the performance of sequential reads. Note that it takes about 500 ns to read 4KB. In the worst case, adding a 110 ns delay every 500 ns would increase the average latency by 20 percent. In practice, subsequent TLB entries (assuming linear organization) should be prefetched, and hence have no impact.

So it looks like some of my previous results will not be applicable to very large data sets, so I better rerun my previous benchmarks on much larger arrays!

Bottom line is that for very large arrays the impact of TLB misses due to the tiny pages has a massive effect on latency. Best solution would be to use larger pages, but, sadly enough, that option doesn’t seem to be available in .Net.

[ 10 April 2016] I have updated some previous posts with the latest version of the benchmarks which now share a single 1 GB array to minimize the impact of TLB misses.

Memory benchmarks: Addendum secundum: .Net Native

Windows 10 has been out for a while now and I eventually got a machine running it: the 4 cores machine I have used so far. So I was in a position to try out .Net Native as it seems, disappointingly enough, to be only supported for so-called universal applications on Windows 10. .Net Native uses the same optimization stages as the native C++ compiler, so one would expect to get (in some cases) the same performance level.

Note that in the context of these memory benchmarks, I wouldn’t be expecting much improvements as in most cases we are memory bandwidth limited. The most obvious exception being the sequential reads, as we already know, can be executed faster with vector instructions (15 GB/s versus 11 GB/s on the 4 cores machine). Having said that, I might try the concurrent random reads case of my Addendum primum. I haven’t updated the code which needs various changes to compile on the universal platform. The code as it stands now in Github sums the values in the array and then discards the result. This, obviously, won’t go down very well with a good optimizing compiler, which will just avoid carrying out the calculation. Actually the impact wasn’t always quite as drastic, but still better safe than sorry.

So here is the latest greatest chart for sequential access on the four cores machine using .Net Native:As expected, or hoped for, .Net Native gives similar performance to C++ or AVX2.

Memory benchmarks: Addendum primum

You might have noticed that I missed one case in my previous blog post: performing multiple independent random reads within a single thread. The code was expanded:

switch (inThreadParallelismLevel) {
    case 1: {
        for (int i = 0; i < steps; i++) {
        total0 += array[(11587L*i) &amp; mask]; 
    }
    break;
 }
 case 2: {
    for (int i = 0; i < steps; i++) {
        total0 += array[(24317L * i) &amp; mask];
        total1 += array[(14407L * i) &amp; mask];
    }
    break;
 }
.
.
.

We saw that the random reads performance scaled nicely with number of threads up (kind of linearly up to 5 threads on the 6 cores CPU). So the question is whether we can achieve the same when performing  multiple independent random reads within a thread.

Rather disappointingly this is not the case, here are the results for the 8 cores machine, the graph represents the memory bandwidth versus the number of concurrent requests within the single thread:

So, a bit of a surprise, there is absolutely no advantage here in running multiple reads within a thread. The scaling observed in the case of chained reads doesn’t happen here. Mind you it is going about 4 times faster here, so there is less scaling potential.  More importantly the scaling across threads/cores is not present here. So it looks like this will only scale if the memory read requests originate from different cores rather than from a single one.

Memory benchmarks

I have often wondered how the current many-core CPUs can retrieve enough data from memory to feed all its cores. So I decided to carry out a few simple experiments.

I looked at three different scenarios, sequential memory access, dependent chain memory access and random memory access. The second being the case where the result of a read determines the address of the subsequent read (load-to-use).

In the first case, we expect to reach very high memory bandwidth, potentially hitting the maximum specified in the CPU spec with relatively few threads. In the case of chained memory access the bandwidth will reflect the memory’s full (huge) latency. In the third case the bandwidth should be higher but probably not by much. In all cases I am mainly interested in the scalability aspects, i.e. how does the single thread/core bandwidth scale as more threads/cores hit the memory bus.

Note that the code was put together fairly quickly, far more care should be taken to get accurate results, however this should be good enough to understand the scalability aspects I am interested in.

As the goal is to measure main memory access as opposed to cache access, to minimize the impact of the limited TLB buffer, each thread accesses these same 1GB array of 64 bit longs. The code is available on Github. For the sequential case the core loop is simply:

    for (int i = 0; i < max; i++) total += array[i];

The next benchmark is where the addresses of a memory access depends on the value of the previous read:

    for (int i = 0; i < max/8; i++) index = array[index];

where the array has been initialized so that the index performs a random walk through the whole array. This models the case where one walks down a dependency path, e.g.

    var x = a.b.c.d.e.f;

The code for the random access performance test is:

    for (int i = 0; i < max/8; i++) total += array[(i * 11587L) & (max-1)];

where we take large, non-periodic, steps to avoid prefetch and cache effects. Note that since the reads are much slower we perform 8 times fewer memory accesses.

In all of these benchmarks ten runs of one hundred such loops are executed and the best, lowest, time is taken.

I executed this code on three different machines with the following specs:

1. 4 cores – i7 2600K 3.4- 3.5 GHz with 16GB DDR3
2. 6 cores – Xeon E5 1650 v3 – 3.4 – 3.5 GHz with 16GB of four channels DDR4
3. 8 cores – Xeon E5 2666 v3 – 2.9 – 3.2 GHz with 30GB of four channels DDR4

The Xeon E5 2666 v3 is a custom Intel CPU for AWS, you can find more details in The Register.

All the results can be found on Github next to the actual code. Here are the results for sequential access which represents the bandwidth in GB/s as a function of the number of concurrent threads:

First thing to mention is that there is no massive difference between the memory bandwidth of the various systems in the single threaded case. Beyond that the memory bandwidth scales similarly on all CPUs. Where the difference is however significant is how far each system scales. The oldest CPU stops at 20 GB/s (21 GB/s in the spec), while the Xeon 1650 supports double that much (spec says 68 GB/s) and the socket Xeon 2666 with 8 cores reaches 50 GB/s with 8 threads (spec says 68 GB/s). Note that the old CPU uses DDR3 with two channels while the two Haswell CPUs use DDR4 with 4 channels, so no big surprise there.

Althoug not linear, the scalability of each of these is pretty good. The slowest and oldest system scales only up to twice its single threaded performance. The 1650 scales up nearly five times its single threaded performance, while the 2666 goes up to about six or seven times the single threaded performance (albeit starting lower). Note that neither of the Haswell CPUs reaches anywhere close to their spec-ed memory bandwidth of 68 GB/s on the tested systems.

In terms of memory access time, in the single threaded case, the memory bandwidth for the 1650 is equivalent to 0.83 ns access time per long! This number is most impressive, and is down to the quality of the CPUs prefetch unit (actually the streamer) which detects the sequential read pattern and accordingly prefetches aggressively (up to 20 cache lines ahead). You can read all the details (well the ones they made public) about the prefetch unit in Intel’s manual.

Let’s move on onto the chained reads:

where the difference with sequential reads is striking, roughly speaking chained reads are one hundred times slower than the sequential case. This corresponds to a latency of about 90 ns, which is pretty much what one can expect from DRAM nowadays. Note that the bandwidth increases almost linearly with the number of threads and shows no sign of saturating.

Here are the results for random reads. Single threaded bandwidth start a bit below 0.4 GB/s which corresponds to a latency of about 18 ns. Note that in this case the bandwidth increases fairly linearly with the number of threads to saturate at around 2.4-2.6 GB/s.

The difference with the chained reads, a factor of four or five, is due to the fact that since the reads are independent, the CPU can dispatch several of them to the memory controller pretty much concurrently. The memory controller can then take full advantage of the channel and bank-level parallelism as well as memory pipelining to perform concurrent memory reads.

Since this last result seems to indicate that the memory controller is able to dispatch maybe up to five (independent) memory requests concurrently, we could try to take advantage of this by executing multiple chained reads within a given thread:

    for (int i = 0; i < max/8; i++) { 
        index0 = array[index0];
        index1 = array[index1];
    }

I have implemented this code with up to eight concurrent indices. Since all of these dependent chains access the same array, I made sure that all indices are sufficiently distant from each to exclude any caching effect. The code was executed on up to 8 threads on the 8 cores machine. The abscissa (x-coordinate)  is the product of the number of threads and the concurrency level:

In the single threaded case, the maximum bandwidth is 255 MB/s which is very close to the single threaded random reads result of 283 MB/s. When running multithreaded, the maximum bandwidth reaches 1.94 GB/s, again close to the multithreaded random reads of 2.04 GB/s. So, in principle, and possibly at almost not cost at all, one can gain a factor of four in memory bandwidth by executing multiple chained reads within a single loop.

So the bottom line is:

• sequential access is the king, by a factor of twenty to one hundred
• chained reads can be made to run four times faster

In the case of chained reads, the huge 90 ns delay between consecutive memory reads should permit the execution of a large number of instructions, potentially hundreds of them, allowing quite a lot of processing of the retrieved data. This is also the case, albeit on a smaller scale, for random reads.

Many thanks to Asier for suggestions, comments,  discussions and comparisons between C++ and C# performance!

[10 April 2016] This graphs in this post have been replaced with the latest version of the benchmark that minimize TLB impact. The text has been edited accordingly.