From owner-freebsd-current Tue Mar 14 23:33:33 1995 Return-Path: current-owner Received: (from majordom@localhost) by freefall.cdrom.com (8.6.10/8.6.6) id XAA17557 for current-outgoing; Tue, 14 Mar 1995 23:33:33 -0800 Received: from balboa.eng.uci.edu (balboa.eng.uci.edu [128.200.61.2]) by freefall.cdrom.com (8.6.10/8.6.6) with SMTP id XAA17551 for ; Tue, 14 Mar 1995 23:33:32 -0800 Received: from localhost.uci.edu by balboa.eng.uci.edu with SMTP id AA07893 (5.65c/IDA-1.4.4 for current@freebsd.org); Tue, 14 Mar 1995 23:33:23 -0800 Message-Id: <199503150733.AA07893@balboa.eng.uci.edu> To: terry@cs.weber.edu (Terry Lambert) Cc: current@FreeBSD.org Subject: Re: MINFREE change to 8% In-Reply-To: Your message of "Tue, 14 Mar 1995 16:42:23 MST." <9503142342.AA09959@cs.weber.edu> Date: Tue, 14 Mar 1995 23:33:21 -0800 From: Steven Wallace Sender: current-owner@FreeBSD.org Precedence: bulk > You could probably do away with the reserve entirely (but killing the > ability to exercise administrative fiat in the process, it being a > side effect of the reserve) by moving from a vector hash to skiplists. > > The 10% is the 90% fill point for least acceptable performance on the > hash; anything over 90% is deemed unacceptable. The actual fall off > is expotential and starts sucking at 80-85% (Knuth). > > When you dick with the minfree, you are in fact lowering the bottom > watermark for acceptable performance for the system. It really doesn't > matter that you think you are "wasting" 100M on a 1G disk; what you > are paying for is a reduced average hash collision frequency. > > The only real difference on a 1G disk is that it become obvious that > you are tying up a lot of disk based on your choice of algorithms. > Could someone explain to the ignorant what in the world you are hashing? (you are searching for something and use some algorithm as your hash index into the 10% reserve space on the disk? (is this reserve distributed or continuous at a specific portion of the disk?) Then you find something... ?) How do skiplist compare and how would they be implemented? Steven