Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!uwm.edu!bionet!agate!darkstar!csl.sri.com
From: caveh@csl.sri.com (Caveh Jalali)
Newsgroups: comp.os.research
Subject: Re: Cache theory question (UNIX)
Message-ID: <1521@darkstar.ucsc.edu>
Date: 28 Feb 90 08:28:16 GMT
Sender: usenet@darkstar.ucsc.edu
Organization: Computer Science Lab, SRI International, Menlo Park, CA
Lines: 49
Approved: comp-os-research@jupiter.ucsc.edu


In article <1456@darkstar.ucsc.edu> cjp%megatek.UUCP@ucsd.edu (Chris Pikus) writes:
>
...
>
>	To wit, when one wishes to access/add a particular block
>in the buffer cache, the kernel performs a hashing function
>on BLKNO (usually a mod( 17) i beleive) and then walks down
>the that list to find said BLKNO.
>
>	My question is thus: WHY mod 17???
...

the choice of 17 is probably arbitrary.  given that there is (hopefully)
no preference for any particular block #s, i will go as far as claiming
that a power of 2 would have been a better choice.

as long as your hash key is distributed EVENLY, who cares what you
divide by -- pick a power of 2 that gives you the desired residency!

just because a number is prime doesn't mean you're going to have fewer
collisions.  you'll simply be sensitive to a different "beat"
frequency than with other numbers:  with 17, it's multiples of 17,
with 16 it would be multiples of 16 which defeat your hashing.

again, i see no reason to believe that block allocation is not
random.  there may be some clustering toward one or more areas
on the disk such as cylinder group boundaries in the BSD file
system, and probably toward the "beginning" of the partition
on older file systems, but within each cluster, the distribution
of blocks should be random.


as to why 17 seems to be the number chosen:  "old" disks used to
have 17 blocks/track.  this is still true for all MFM drives on
PC, etc... ie.  anything that's 3600 rpm, and 5Mbit/sec data rate,
and 512 byte sector.  someone might want to check how many
sectors/track there were on the old PDP-11 drives!
if they still use 17 today, something is badly WRONG:
"old" systems didn't have enough memory to afford more than say... 30
blocks of cache, hence the small value.  today, one might
choose a value in the 100's.

00c
--
00c -- Who was that masked interrupt?
Internet: caveh@csl.sri.com
UUCP: {ames|decwrl|pyramid|sun}!fernwood!hercules!caveh
ICBM: 37d 27' 14" North, 122d 10' 52" West