Author: Robert Hyatt
Date: 15:25:51 07/16/03
Go up one level in this thread
On July 16, 2003 at 16:12:45, Dieter Buerssner wrote: >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. You are talking about the TLB. The memory mapping hardware needs two memory references to compute a real address before it can be accessed. The TLB keeps the most recent N of these things around. If you go wild with random accessing, you will _certainly_ make memory latency 3x what it should be, because the TLB entries are 100% useless. Of course that is not sensible because 90+ percent of the memory references in a chess program are _not_ scattered all over memory. > >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 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.