From owner-freebsd-hackers Mon Jan 29 13: 0:22 2001 Delivered-To: freebsd-hackers@freebsd.org Received: from renown.cnchost.com (renown.concentric.net [207.155.248.7]) by hub.freebsd.org (Postfix) with ESMTP id D958637B400 for ; Mon, 29 Jan 2001 13:00:03 -0800 (PST) Received: from bitblocks.com (ts016d06.sjc-ca.concentric.net [206.173.237.18]) by renown.cnchost.com id PAA27841; Mon, 29 Jan 2001 15:59:59 -0500 (EST) [ConcentricHost SMTP Relay 1.10] Message-ID: <3A75D9C9.1C59ACBA@bitblocks.com> Date: Mon, 29 Jan 2001 12:59:53 -0800 From: Bakul Shah X-Mailer: Mozilla 4.72 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Matt Dillon Cc: hackers@FreeBSD.ORG Subject: Re: [kernel patch] fcntl(...) to close many descriptors References: <200101290303.f0T33qg60603@earth.backplane.com> <200101281837.f0SIbGI24332@iguana.aciri.org> <200101290303.f0T33qg60603@earth.backplane.com> <4.3.0.20010129145823.023dfeb0@pop.free.fr> <20010129081455.B2390@hamlet.nectar.com> <4.3.0.20010129191139.064648d0@pop.free.fr> <200101291833.f0TIXDF67092@earth.backplane.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG This caught my eye: > Besides, there is no such thing as a > perfect hash ... at least not one that has a small enough index range > to be useful in a table lookup. If you can get to old CACMs see `Minimal Perfect Hash Functions Made Simple' by Richard J. Cichelli, Comm. of ACM, Jan 1980. AFAIK gperf uses some variation of that algorithm and may have some details. A minimal perfect hash function is only worth it (IMHO) when the set of input keys is mostly fixed and the hash function is used many many times (e.g. programming language keywords). As for a generic & extensible syscall, you'd have to pay the cost of finding a new minimal perfect hash function every time you load a kernel module that implements a new system call. AFAIK the best algo. to generate a new perfect hash function runs in O(n log n) time -- not too bad (kernel module loading doesn't have to be lightening fast) but even for an experimental syscall the time to reach syscall code should be minimized if it is to ever get past the experimental stage. Someone mentioned discovering the syscall name->index mapping via sysctl but that opens up a window where the mapping can change. For what its worth... -- bakul To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message