Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!husc6!hao!ames!ucbcad!ucbvax!CORY.BERKELEY.EDU!dillon
From: dillon@CORY.BERKELEY.EDU (Matt Dillon)
Newsgroups: comp.sys.amiga
Subject: Re: Facc mini-review
Message-ID: <8706051011.AA10783@cory.Berkeley.EDU>
Date: Fri, 5-Jun-87 06:11:00 EDT
Article-I.D.: cory.8706051011.AA10783
Posted: Fri Jun  5 06:11:00 1987
Date-Received: Tue, 9-Jun-87 04:35:27 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Lines: 31


>	I had considered the popularity based replacement algorithm but
>rejected it due  to  the simplicity inherent in the LRU algorithm which
>Facc *does* use. Actually,  there are three principal lists kept within
>the Facc buffer structure coming together in a data structure which al-
>lows Facc to  search  2048  buffers in the time AmigaDOS will search 16
>buffers allocated with AddBuffers.

	In other words, the implementation in AmigaDoG is probably a linear
search of its buffers...  which is a big no-no for buffer caches.  A hash
table of some sort (which is what I assume Perry is using) of acceptable
size usually provides an almost instantanious 'hit', and a somewhat 
slower (but still almost instantanious) 'miss'.  Nobody says you can't also
link each entry in a doubly linked list ordered for LRU.... That is, whenever 
a buffer is accessed it is moved to the head of the list.  Thus, the buffers
used the least float down to the end, and you remove them from the tail of
the d-list when you (A) reach your max buffer limit, or (B) are tight on
memory (etc...).  Straight LRU basically implies that to realize a speed
improvment on, say, a temporary file, the file blocks must fit completely in 
the buffer cache.  

	One modification (which I doubt Perry is using, but *hey*, here's an 
idea for an improvement!), is to remove data blocks from the cache in reverse 
order on the assumption that if the file is too big for the cache, the second 
reading of the file will still find some blocks in the cache... a sort of 
"meet me in the middle" approach instead of "follow my tail", which gives no 
cache hits on the second go around for the file.  Of course, there are many 
tradeoffs.  In the most simplistic case, the above would only work well if
the file blocks are sequentially accessed.

				-Matt