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.