Take the 2-minute tour ×

It's clear that there is no explicit way or certain system calls that help programmers to put a variable into the CPU cache.

But I think that a certain programming style or well designed algorithm can make it possible to increase the possibilities that the variable can be cached into the CPU caches.

Here is my example:

I want to append an 8 byte structure at the end of an array consisting of the same type of structures, declared in the global main memory region.

This process is continuously repeated for 4 million operations. This process takes 6 seconds, 1.5 us for each operation. I think this result tells that the two memory areas have not been cached.

I got some clues from a cache-oblivious algorithm, so I tried several ways to enhance this. Until now, no enhancement.

I think some clever codes can reduce the elapsed time, up to 10 to 100 times. Please show me the way.


Appended (2011-04-01)

Damon~ thank you for your comment!

After reading your comment, I analyzed my code again, and found several things that I missed. The following code that I attached is the abbreviated version of my original code.

To accurately measure each operation's execution time (in the original code, there are several different types of operations), I inserted the time measuring code using clock_gettime() function. I thought if I measure each operation's execution time and accumulate them, the additional cost by the main loop can be avoided.

In the original code, the time measuring code was hidden by a macro function, so I totally forgot about it.

The running time of this code is almost 6 seconds. But if I get rid of the time measuring function in the main loop, it becomes 0.1 seconds.

Since the clock_gettime() function supports very high precision (upto 1 nano second), executed on the basis of an independent thread, and also it requires very big structure, I think the function caused the cache-out of the main memory area where the consecutive insertions are performed.

Thank you again for your comment. For further enhancement, any suggestion will be very helpful for me to optimize my code.

I think the hierachically defined structure variable might cause unnecessary time cost, but first I want to know how much it would be, before I change it to the more C-style code.

typedef struct t_ptr {
    uint32 isleaf :1, isNextLeaf :1, ptr :30;
    t_ptr(void) {
        isleaf = false;
        isNextLeaf = false;
        ptr = NIL;
} PTR;

typedef struct t_key {
    uint32 op :1, key :31;
    t_key(void) {
        op = OP_INS;
        key = 0;
} KEY;

typedef struct t_key_pair {
    KEY key;
    PTR ptr;
    t_key_pair() {

    t_key_pair(KEY k, PTR p) {
        key = k;
        ptr = p;
} KeyPair;

typedef struct t_op {
    KeyPair keyPair;
    uint seq;
    t_op() {
        seq = 0;
} OP;

#define MAX_OP_LEN 4000000
typedef struct t_opq {
    OP ops[MAX_OP_LEN];
    int freeOffset;
    int globalSeq;
    bool queueOp(register KeyPair keyPair);
} OpQueue;

bool OpQueue::queueOp(register KeyPair keyPair) {
    bool isFull = false;
    if (freeOffset == (int) (MAX_OP_LEN - 1)) {
        isFull = true;
    ops[freeOffset].keyPair = keyPair;
    ops[freeOffset].seq = globalSeq++;

OpQueue opQueue;
#include <sys/time.h>
int main() {
    struct timespec startTime, endTime, totalTime;
    for(int i = 0; i < 4000000; i++) {
        clock_gettime(CLOCK_REALTIME, &startTime);
        clock_gettime(CLOCK_REALTIME, &endTime);
        totalTime.tv_sec += (endTime.tv_sec - startTime.tv_sec);
        totalTime.tv_nsec += (endTime.tv_nsec - startTime.tv_nsec);
    printf("\n elapsed time: %ld", totalTime.tv_sec * 1000000LL + totalTime.tv_nsec / 1000L);
share|improve this question
8 bytes * 4 million is roughly 32 MB. If this takes 6 seconds and your CPU is not 20 years old, this is not just caching, there must be something else wrong. A reasonably new CPU will write out several gigabytes per second sequentially with non-optimized code. Are you maybe reallocating memory every time? (Besides, caching works very well for the most part with fixed stride sequential access, CPUs do that automatically and very well, only not via page boundaries) –  Damon Mar 31 '11 at 13:58
You don't happen to push_back to a std::vector<yourstruct> or something by any chance? -- though not even that would take so long as it grows geometrically... –  Damon Mar 31 '11 at 14:03
Damon~ thank you for your comment! After reading your comment, I analyzed my code again, and found several things that I missed. I attached the missed things and abbreviated version of my code to the above. –  Nate Apr 1 '11 at 4:58
You would probably want to call clock_gettime once before and once after the loop, outside the {}. In the above code, you still call it 8 million times. If you want per-operation time instead of total time, divide by 4000000 (and, if you want to be super correct, time an empty loop, and subtract that). On my 3 year old computer, your code runs those 4 million iterations in 0.046 seconds (average value over 1000 runs), loop and resetting freeOffset inclusive. (Note: it did take some work to make your code compile, you should probably not use so many non-standard types and defines). –  Damon Apr 1 '11 at 14:47
Thank you for your comment Damon again. The purpose of inserting time checking code was to measure the exact total time of each operation (There are several types of operations like insert, search, delete in the original code). Therefore, it was inevitable choice to insert the time-checking code surrounding each operation inside the loop. Enlightened by your comment, I eliminated the time checking code, and just calculated the time cost by the loop. This time I think I got the right result. –  Nate Apr 4 '11 at 5:52

2 Answers 2

I have been unable to force caching, but you can force memory to be uncache-able. If you have large other datastructures you might exclude these so that they will not pollute your caches. This can be done by specifying PAGE_NOCACHE for the Windows VirutalAllocXXX functions.


share|improve this answer

YOU don't put the structure into any cache. The CPU does that automatically for you. The CPU is even more clever than that; if you access sequential memory, it will start putting things from memory into the cache before you read them.

And really, it should be common sense that for a simple bit of code like this, the time you spend on measuring is ten times more than the time to perform the code (apparently 60 times in your case).

Since you put so much confidence in clock_gettime (): I suggest you call it five times in a row and store the results, then print the differences. There's resolution, there's precision, and there's how long it takes to return the current time, which is pretty damned long.

share|improve this answer

Your Answer


