From owner-freebsd-hackers@FreeBSD.ORG Fri Dec 28 13:25:40 2007 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id EA24816A419; Fri, 28 Dec 2007 13:25:40 +0000 (UTC) (envelope-from aryeh.friedman@gmail.com) Received: from mta3.srv.hcvlny.cv.net (mta3.srv.hcvlny.cv.net [167.206.4.198]) by mx1.freebsd.org (Postfix) with ESMTP id AFE5E13C4F5; Fri, 28 Dec 2007 13:25:40 +0000 (UTC) (envelope-from aryeh.friedman@gmail.com) Received: from flosoft.no-ip.biz (ool-435559b8.dyn.optonline.net [67.85.89.184]) by mta3.srv.hcvlny.cv.net (Sun Java System Messaging Server 6.2-8.04 (built Feb 28 2007)) with ESMTP id <0JTR00D7GHANGGX0@mta3.srv.hcvlny.cv.net>; Fri, 28 Dec 2007 08:25:35 -0500 (EST) Received: from flosoft.no-ip.biz (localhost [IPv6:::1]) by flosoft.no-ip.biz (8.14.2/8.14.2) with ESMTP id lBSDPYJ0096590; Fri, 28 Dec 2007 08:25:34 -0500 Date: Fri, 28 Dec 2007 08:25:34 -0500 From: "Aryeh M. Friedman" In-reply-to: <9bbcef730712280518k56696002w1437ec3469e2eeb2@mail.gmail.com> To: Ivan Voras Message-id: <4774F94E.50203@gmail.com> MIME-version: 1.0 Content-type: text/plain; charset=UTF-8 Content-transfer-encoding: 7BIT X-Enigmail-Version: 0.95.5 References: <5950EE0C-383D-4D6B-9991-A0DEABD2ADE4@u.washington.edu> <20071228003716.GB48997@lor.one-eyed-alien.net> <4774EF27.90307@gmail.com> <9bbcef730712280454w6b6f5e17s33631223d5571f83@mail.gmail.com> <4774F42C.5030105@gmail.com> <9bbcef730712280510v14806e7exb960f5da5f05e4d@mail.gmail.com> <4774F651.7060905@gmail.com> <9bbcef730712280518k56696002w1437ec3469e2eeb2@mail.gmail.com> User-Agent: Thunderbird 2.0.0.9 (X11/20071217) Cc: freebsd-hackers@freebsd.org Subject: Re: BSD license compatible hash algorithm? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 28 Dec 2007 13:25:41 -0000 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Ivan Voras wrote: > On 28/12/2007, Aryeh M. Friedman wrote: > >> Depends on the size of the table... I work with a algrothem that >> regularly has tables between 2^32 and 2^64 buckets (even though >> the we use a slightly different terminology) > > This looks like an interesting project - are you using hashes not > for speed but as a generic storage organization algorithm? > > And, I think at least some of the popular non-crypto hash > algorithms could be easily extended to work with 64-bit integers - > are you really using the "big" hashes for this? > Yes using it as a DB table indexing, the exact details are under an NDA but I can give some numbers though like a table lookup on a 2^32 record table requires no more then 4 disk reads (averages out to between 3 and 4) and 2k or RAM [namely gives O(log_k(n)) we have, successfully used k>=256 even though k=256 is the most natural value, time performence and O(1) when considering primary store requirements only... in other words when the table size = 2^processor word size you need word size/8 lookups at most to find anything])... hopefully once the patents are in place I can give more details (I am hoping to make the reference implementation as FOSS as possible {while not invalidating the strength of the patent} [see my blog for details on the business model I am planning]) - -- Aryeh M. Friedman FloSoft Systems http://www.flosoft-systems.com Developer, not business, friendly -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.4 (FreeBSD) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFHdPlOzIOMjAek4JIRAgahAJ95GpzAS+e1607NcdHg6m33BokCSgCglgJG +BVo+ZCKvA1S3p2/HsNzyds= =MKKp -----END PGP SIGNATURE-----