Computer Chess Club Archives




Subject: Re: Another memory latency test

Author: Dieter Buerssner

Date: 12:29:56 07/17/03

Go up one level in this thread

On July 17, 2003 at 10:06:20, Vincent Diepeveen wrote:

>On July 17, 2003 at 09:16:10, Dieter Buerssner wrote:

>>Random access:  30.864 s, 308.640 ns/access

>>Vincent's program reports 325 ns, which is not too far off from the
>>random access number.

You access 8 bytes, while my code accesses (on typical PC hardware) 4 bytes. So
you can basically add the offset 1 number to make it (a bit) more comparable.

>>void *access_loop(void **buf)
>>  size_t n;

Should better be:
  unsigned long n;

>>void setup_random(void **buf, size_t n)
>>  size_t i, r;
>>  void *tmp;
>>  setup_seq(buf, n, 1);
>>  for (i=n-1; i>0; i--)
>>  {
>>    do
>>    {
>>      r = rand_range(i+1);
>>      tmp = buf[r];
>>    }
>>    while (tmp == buf+i); /* Can this happen? */
>>    buf[r] = buf[i];
>>    buf[i] = tmp;
>>  }

This method has a flaw. The idea was, to set up a
linked list in random order. It is done. But the linked list can
cycle, before all memory cells were accessed (I doubt very much, that this
will make a difference). One example, assume 7 pointers. (I give indices
instead of pointers). We shuffle the indices in random order, so for
example (memory size is 7*sizeof pointer) from 0 1 2 3 4 5 6 to 3 6 1 2 5 4
0. So, we would traverse the memory from element 0 -> 3 -> 2 -> 1 -> 6 ->
0. So the cycle length is only 5 instead of 7.

When memory is much bigger than N_LOOPS, you cannot access every
memory cell anyway. Most probably, no 2 the same cells will be

I have other ideas, to avoid the early cycling. But I first should
think about it.

I added some code, to detect the cycle length. For the numbers I
reported, it was (more than) sufficiently big.

>>int main(int argc, char *argv[])
>>  int offset;
>>  size_t memsiz, n;
>>  void **buf;
>>  char prompt[256];
>>  if (argc != 2)
>>    return EXIT_FAILURE;
>>  memsiz = atol(argv[1]);
>>  n = memsiz/sizeof *buf;
>>  buf = malloc(memsiz);
>>  if (buf == NULL)
>>    return EXIT_FAILURE;

One could add another interesting loop.

 Do a sequential offset
like test, with a very big offset in the order of magnitude of 1/4 to 1/2
of the memory size. I am not too confident about the mathematics anymore,
but the following code showed a full cycle on my computer in few tests (probably
it would be better to make sure, that offset and n have no common divisors):

  /* Don't use with very small n */
    offset = n/4 + rand_range(n/4);
  while (n%offset == 0);
  setup_seq(buf, n, offset);
  sprintf(prompt, "Sequential access offset %d", offset);
  /* test_circle(buf, n); */
  time_access(prompt, buf);

To make it more portable, offset probably
should be a long throughout the prog, when using such large offsets.


This page took 0.1 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.