Warm-cache prefetching

I found an interesting paper improving index speed by prefetching memory
data to L1/L2 cache here (there is discussion about prefetching disk
data to memory several days ago "ice-breaker thread"):
http://www.cs.cmu.edu/~chensm/papers/index_pf_final.pdf

Also related technique used to speedup memcpy:
http://people.redhat.com/arjanv/pIII.c

I wonder if we could use it to speed up in-memory scan opertion for heap
or index. Tom's patch has made scan can handle a page (vs. row) every
time, which is a basis for this optimization.

I write a program try to simulate it, but I am not good at micro
optimization, and I just get a very weak but kind-of-stable improvement. I
wonder if any people here are interested to take a look.

Regards,
Qingqing

----------------------------------

Test results
--------------
Cache line size: 64
CPU: P4 2.4G
$#./prefetch 10 16
Sum: -951304192: with prefetch on - duration: 42.163 ms
Sum: -951304192: with prefetch off - duration: 42.838 ms
Sum: -951304192: with prefetch on - duration: 44.044 ms
Sum: -951304192: with prefetch off - duration: 42.792 ms
Sum: -951304192: with prefetch on - duration: 42.324 ms
Sum: -951304192: with prefetch off - duration: 42.803 ms
Sum: -951304192: with prefetch on - duration: 42.189 ms
Sum: -951304192: with prefetch off - duration: 42.801 ms
Sum: -951304192: with prefetch on - duration: 42.155 ms
Sum: -951304192: with prefetch off - duration: 42.827 ms
Sum: -951304192: with prefetch on - duration: 42.179 ms
Sum: -951304192: with prefetch off - duration: 42.798 ms
Sum: -951304192: with prefetch on - duration: 42.180 ms
Sum: -951304192: with prefetch off - duration: 42.804 ms
Sum: -951304192: with prefetch on - duration: 42.193 ms
Sum: -951304192: with prefetch off - duration: 42.827 ms
Sum: -951304192: with prefetch on - duration: 42.164 ms
Sum: -951304192: with prefetch off - duration: 42.810 ms
Sum: -951304192: with prefetch on - duration: 42.182 ms
Sum: -951304192: with prefetch off - duration: 42.826 ms

Test program
----------------

/** prefetch.c*        PostgreSQL warm-cache sequential scan simulator with prefetch*/

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <errno.h>
#include <sys/time.h>

typedef char bool;
#define true    ((bool) 1)
#define false    ((bool) 0)

#define BLCKSZ    8192
#define CACHESZ    64
#define NBLCKS    5000

int    sum;

int
main(int argc, char *argv[])
{int     i, rounds;char    *blocks;int    cpu_cost;
if (argc != 3){    fprintf(stderr, "usage: prefetch <rounds> <cpu_cost [1, 16]>\n");    exit(-1);}
rounds = atoi(argv[1]);cpu_cost  = atoi(argv[2]);if (cpu_cost > 16)    exit(-1);
for (i = 0; i < 2*rounds; i++){    int    j, k;    struct    timeval start_t, stop_t;    bool    enable =
i%2?false:true;   char    *blck;
 
    blocks = (char *)malloc(BLCKSZ*NBLCKS);    memset(blocks, 'a', BLCKSZ*NBLCKS);
    sum = 0;    gettimeofday(&start_t, NULL);
    for (j = 0; j < NBLCKS; j++)    {        blck = blocks + j*BLCKSZ;        for (k=0; k < BLCKSZ; k+=CACHESZ)
{           int    *s = (int *)(blck + k);            int    u = cpu_cost;
 
            if (enable)            {                /* prefetch ahead */                __asm__ __volatile__ (
                    "1: prefetchnta 128(%0)\n"                                   : : "r" (s) : "memory" );
}
            /* pretend to process current tuple */            while (u--) sum += (*(s+u))*(*(s+u));        }    }
gettimeofday(&stop_t,NULL);
 
    free(blocks);
    /* measure the time */    if (stop_t.tv_usec < start_t.tv_usec)    {        stop_t.tv_sec--;        stop_t.tv_usec
+=1000000;    }    fprintf (stdout, "Sum: %d: with prefetch %s - duration: %ld.%03ld ms\n",            sum,
enable?"on":"off",           (long) ((stop_t.tv_sec - start_t.tv_sec) * 1000 +                    (stop_t.tv_usec -
start_t.tv_usec)/ 1000),            (long) (stop_t.tv_usec - start_t.tv_usec) % 1000);
 
}
exit(0);
}