Intentional performance degradation through cache and branch-prediction misses

Question

I am experimenting with performance evaluation. From the hardware architecture point of view, two main factors are cache misses and incorrect prediction of conditional branches which can degrade the performance of an application.

I have considered a small application for each case:

Cache Misses:

In this application, I intentionally want to write such a piece of code that would cause a worst case scenario w.r.t. cache (i.e., induce cache misses). A cache miss can be a read miss or a write miss, so I have written the code for both.

Read Misses:

     int n = 32767;
     int arr[n];

     for (int i = 0; i < n ; i++) {
         int ri = rand() % n;
         int var=arr[ri];
     }

Write Misses:

     int n = 32767;
     int arr[n];

     for (int i = 0; i < n ; i++) {
         int ri = rand() % n;
         arr[ri] = ri;
     }

Branch Incorrect Predictions:

Here, I intentionally want to write such a piece of code that would cause a worst case scenario w.r.t. branch prediction (i.e., induce incorrect predictions). So, it will make the branch predictor fail badly. The code is as following: Source

    const unsigned arraySize = 1024;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c){
        data[c] = std::rand() % 256;
    }
    long sum = 0;
    for (int i = 0; i < 1024; ++i) {
         // Primary loop
         for (int c = 0; c < arraySize; ++c) {
             if (data[c] >= 128)
                 sum += data[c]; 
         }
    }

My question:

1. Can I make any improvements to these source codes?

(Since a flaw left at this level can make all my experimental results flawed.)

2. What are other possible codes that would have similar behavior(cache misses and branch incorrect predictions)?

(Maybe, a couple of other possible ways to do the same thing but with different apparent code.)

3. Last but not least; Is there any other potential factor (other than cache misses and branch incorrect predictions) that can cause such a huge performance degradation?

An example source code to demonstrate its effect on the performance.

Note: With regard to the third question, I can name factors e.g., interrupts, context switches etc., however, I am considering real-time paradigm where such events would presumably be controlled.

P.S. I know three different question should be asked in three different posts, nonetheless, the second question is an addendum to the first question and the third question alone will be dubious without the whole context.

Thanks.

EDIT: I am using gem5-simulator in my experiments. Just out of my mind, based on my previous studies and experiences, a brief description of the simulator is: It is a cycle-accurate simulator with the facility to configure customized platforms. The execution traces provided by this simulator does include the exact counts on most of the expected statistics (e.g., cache misses, branch incorrect predicted etc). The generation of these traces does not cause overhead on the actual execution of an application. It also provides overhead free instrumentation facility to added further counters in the traces as per user needs.

Nevertheless, @vnp: Adjoining thanks, I am getting the counts and considering the cache configurations.

Answer 1

I don't think the test results will be convincing. Should I be in this situation, I would be interested in not just performance figures, but the miss counts as well. And I would need the latter to be controlled - random access patterns are not enough.

Also, I'd need to know more about cache: line size, ways and associativity, tag width all affect the test setup (e.g., what is the significance of 32767?) and reliability of results.

The guaranteed way to get worst case cache performance is to disable the cache completely. Configure it as writearound, and you'd have a miss on any write or read. To get more granularity (or if writearound is not available on your CPU), play with writethrough and readthrough modes.

I have no say on branch prediction, however I'd insist on more controllable test setup.

As for question 3: it depends on the underlying architecture. If it has virtual memory, page misses are extremely expensive.

Answer 2

To expand a bit on vnp's answer:

Cache Miss

The random access will give you a hit rate that should reflect the ratio between the size of your array and the cache size. If you want to have 100% misses and don't want to turn off the cache, the solution would be to access in a pattern that ensures only uncached memory is read/written.

As vnp stated, there are several factors, like the cache size, associativity factor and update strategy, that would have to be considered. Additionally to these, the physical addresses where the array is stored might matter as well.

I think a near perfect solution would cycle through the array with a stride that is larger than the cache line size. The cycling ensures that the next cacheline will always be the least recently used one (which has very likely been elided). The stride ensures that subsequent reads/writes don't go to the same cache line.

Further you should also think about the instruction cache which can have misses as well.

The cache miss cost is dwarfed by a page miss so you should measure that too. This opens up the whole field of IO device speed of things like SSDs, HDDs, NICs, Tapes, ...

Incorrect Branch Prediction

Triggering a wrong branch prediction with 100% probability would probably require insight into the actual prediction algorithm. I don't think that you can do much better than truly random decision.

However, you should think about the reason for the cost of a misprediction: the introduced control hazard triggers a pipeline stall. There are other types of hazards that can trigger a pipeline stall and you might want to measure them as well.

Multicore Interaction

A problem that can happen on multicore systems is the cache coherency. When two threads are working simultaneously, they sometimes need to be synchronized with the help of synchronization variables. These variables have to be shared between the concurrent threads and caches get in the way of the synchronization. When the variable is written to in one CPU's (L1) cache, the copy in the other CPU's cache has to be invalidate/changed to make the read visible. This process has usually a higher cost than simple cache accesses.

On systems that support hyper-threading another problem might happen: The two virtual threads that run on the same physical processor compete for the same set of physical resources. Thus, using the same resources on both threads sequentializes them.

Obviously, once we are start multithreading we can run into problems like deadlocks, live locks, or waiting in general which can dominate the whole run time.

Uniform Random Numbers

You should be aware that the random numbers generated by rand() are not very random. Furthermore, using % 256 to map them to a smaller range does usually not result in a perfectly even distribution.

Instead, you should use an engine like the mersenne twister (mt19937) with the uniform_int_distribution from C++ 11's <random> header.

Magic Numbers

Your code is full of numbers like 32767, 1024, 256, 128. You should store them in constants and give them meaningful names. Like number_of_iterations or number_of_possible_values.

Compiler Optimizations

Finally, I want to note that you should inspect the generated assembly code. The compilers can do crazy optimizations that might interfere with your measurements.

For example, all loops in your code have a fixed size, which makes the compiler's job in loop unrolling even easier.

Eventually, it might be best to measure hand written assembly code where you know exactly what is going on.