h*b
发帖数: 209 | 1 【 以下文字转载自 Working 讨论区 】
发信人: htb (小牛 。。。妞。。。), 信区: Working
标 题: 问个面试问题
关键字: in
发信站: BBS 未名空间站 (Wed Jun 13 16:55:27 2012, 美东)
面试的时候问了下面的问题，没有回答上来：
下面的程序当N=64*1024的时候，run time是100 msec,
当N=70*1024的时候，time变成了74 msec。为什么N越大run time
越小？
如果run多次的时候，run time可能变成：
N=64： 100， 76， 500， 80， 90
N=70： 74， 80， 300， 63， 80
为什么会出现500/300这突变的数字？
把a，b,c,d,e初始化成0也会出现同样的现象。
#define N 64*1024
int a[N], b[N], c[N], d[N], e[N];
int main()
{
int i;
for (i = 0; i
a[i] = b[i] + c[i] + d[i] + e[i];
return 0;
} | A**l
发帖数: 2650 | 2 process context switch?
【在 h*b 的大作中提到】
: 【 以下文字转载自 Working 讨论区 】
: 发信人: htb (小牛 。。。妞。。。), 信区: Working
: 标 题: 问个面试问题
: 关键字: in
: 发信站: BBS 未名空间站 (Wed Jun 13 16:55:27 2012, 美东)
: 面试的时候问了下面的问题，没有回答上来：
: 下面的程序当N=64*1024的时候，run time是100 msec,
: 当N=70*1024的时候，time变成了74 msec。为什么N越大run time
: 越小？
: 如果run多次的时候，run time可能变成：
| t********e
发帖数: 143 | 3 All operation are independed of each other. Running on 2 different processor
in the second case probably. Notice time is almost cut in half in one case. | s***0
发帖数: 117 | 4 Seems like a memory question. I'm guessing you hit some special edge
conditions for tlb misses. Maybe faulting more in the longer runs. | c******g
发帖数: 69 | 5 单线程单进程程序没有context switch和multicore的问题
我猜想是cache performance的问题，假设L1 cache四路组相联（这个是一下推论的假
设，但应该属于cpu常规配置，可以搜搜主流cpu的配置）
#define N 64*1024
// 每个数组64KB
a[i] = b[i] + c[i] + d[i] + e[i];
// 每次循环读四个mem location,写一个mem location
那么在L1 cache来看, 由于每个数组64KB, a[0]-e[0]映射到同一组4路cache line，5
个memory address在4个cache line上冲突，每次循环都会因此出现cache miss
当数组size变成70时，a[0]-e[0]映射到不同的组上，5个mem address在L1 cache共存
，performance就上去了
运行都多次performance不一样，还没有想到解释。。。 | A**l
发帖数: 2650 | 6 这个解释很靠谱，赞一个！
PS:我是说波动是因为被别的进程抢占了（IO之类）
5
【在 c******g 的大作中提到】
: 单线程单进程程序没有context switch和multicore的问题
: 我猜想是cache performance的问题，假设L1 cache四路组相联（这个是一下推论的假
: 设，但应该属于cpu常规配置，可以搜搜主流cpu的配置）
: #define N 64*1024
: // 每个数组64KB
: a[i] = b[i] + c[i] + d[i] + e[i];
: // 每次循环读四个mem location,写一个mem location
: 那么在L1 cache来看, 由于每个数组64KB, a[0]-e[0]映射到同一组4路cache line，5
: 个memory address在4个cache line上冲突，每次循环都会因此出现cache miss
: 当数组size变成70时，a[0]-e[0]映射到不同的组上，5个mem address在L1 cache共存
|
|
