Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!bionet!agate!darkstar!cs.umass.edu
From: moss%ibis@cs.umass.edu (Eliot Moss)
Newsgroups: comp.os.research
Subject: Re: Cache theory question (UNIX)
Message-ID: <1531@darkstar.ucsc.edu>
Date: 28 Feb 90 19:30:56 GMT
Sender: usenet@darkstar.ucsc.edu
Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)
Lines: 20
Approved: comp-os-research@jupiter.ucsc.edu


I suspect that 17 was chosen as being a prime close to the number of blocks
they expected to have in the cache in early systems (8k x 17 = 136k, a
reasonable chunk on a 1 or 2 megabyte system). With larger memory sizes
available today, it might pay to use a larger prime and cut down the cost of
searching the lists. If the size of the hash table is k and the number of
blocks in the cache is N, then the average number of probes it takes to find a
resident block is something like 1/2 * N/k and the average number for
non-resident blocks is N/k. Clearly, one desires large k for this, but pays an
overhead (a per-device one perhaps), so one must make an appropriate tradeoff.
Even on my machines with large amounts of memory, the chains are probably not
longer than 10 or 20 blocks ....					Eliot
--

		J. Eliot B. Moss, Assistant Professor
		Department of Computer and Information Science
		Lederle Graduate Research Center
		University of Massachusetts
		Amherst, MA  01003
		(413) 545-4206; Moss@cs.umass.edu