Author: Dieter Buerssner
Date: 13:12:45 07/16/03
Go up one level in this thread
On July 16, 2003 at 15:40:07, Gerd Isenberg wrote: >Yes i see, but to do exactly Vincent's sequence, calling RanrotA 100 million >times in a loop, you need a rather huge list ;-) Hi Gerd, for 100 millions, I would need 400 Mb RAM (which I can). I need 100e6*sizeof(pointer). But thatis not really the point. My idea (one alternative at least) is to start with a cyclic linked list, that just connects the elements in order at first, and last entry goes back to start. Then use a typical card shuffling routine, to randomize this list. If the mem is over 400 Mb, it would mean, that we don't visit each cell. If it is lower, we will visit the cells serveral timed. I would suspect, as long as memory is much bigger than cache sizes, it makes little difference. But does it make a difference to lmbench type sequential testing (with the same linked list method)? And, after all, we use virtual memory nowadays. Doesn't this include one more indirection (done by hardware). Without knowing much about it, I wouldn't be surprized, that hardware time for those indirections is needed more often with the random access style pattern. BTW. To shuffle a deck of N cards, one needs N calls to the PRNG. Often people, who try this first, do it rather wrong. They randomly choose 2 indices, and swap those cards. This is a very inefficient method, and even with many more than N calls to the PRNG, the deck is not shuffled well. I did not start yet. When I have the results, I can think about possible problems with mod, loop unrolling, etc. (I will use loop unrolling for the random linked list test). Cheers, Dieter
This page took 0.01 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.