Date: Mon, 29 Jan 2001 12:59:53 -0800 From: Bakul Shah <bakul@bitblocks.com> To: Matt Dillon <dillon@earth.backplane.com> Cc: hackers@FreeBSD.ORG Subject: Re: [kernel patch] fcntl(...) to close many descriptors Message-ID: <3A75D9C9.1C59ACBA@bitblocks.com> References: <200101290303.f0T33qg60603@earth.backplane.com> <200101281837.f0SIbGI24332@iguana.aciri.org> <200101290303.f0T33qg60603@earth.backplane.com> <p05010400b69ac2c32903@[128.113.24.47]> <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>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3A75D9C9.1C59ACBA>