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 visited. 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 */ do { 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. Regards, Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.