From mboxrd@z Thu Jan 1 00:00:00 1970 From: Jeff Garzik Subject: Re: Design challenges in chunkd self-checking Date: Tue, 05 Jan 2010 16:53:55 -0500 Message-ID: <4B43B4F3.8070500@garzik.org> References: <20091222144111.789a5b91@redhat.com> <4B314BAE.4010805@garzik.org> <20091222184014.22c5d1c5@redhat.com> <4B319030.9070906@garzik.org> <20100105134702.1e72ced2@redhat.com> <4B43A902.5070105@garzik.org> <20100105143935.69adb51e@redhat.com> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit Return-path: DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:sender:message-id:date:from :user-agent:mime-version:to:cc:subject:references:in-reply-to :content-type:content-transfer-encoding; bh=Iiaa0ACgsY1/pmLsGlc4MJDwvZW8USHmfwP+x7PUPmA=; b=rNP5PTlPAZB5zgeZdSXiZI1122WiHSNRepCv0BGnidH0pZQkSBc6tUPcaD5VWEFaY3 JyZLf+YwU0lnwDpnK3e4F6zCzLZwHYbaxSmJC9WEZyHIezH7z/Ex1b4+llCzijH2ielC AXs3Jdr3LKkvBeSw0z2HJWhzmFDjHu/vbYJ1Y= In-Reply-To: <20100105143935.69adb51e@redhat.com> Sender: hail-devel-owner@vger.kernel.org List-ID: Content-Type: text/plain; charset="us-ascii"; format="flowed" To: Pete Zaitcev Cc: Project Hail List On 01/05/2010 04:39 PM, Pete Zaitcev wrote: > On Tue, 05 Jan 2010 16:02:58 -0500 > Jeff Garzik wrote: >> On 01/05/2010 03:47 PM, Pete Zaitcev wrote: >>> On Tue, 22 Dec 2009 22:36:16 -0500 >>> Jeff Garzik wrote: >>> >>>> Seems like a mutex-wrapped GLib hash table would work... >>> >>> I dunno about this... See, I think it's like kernel timers: there's a >>> lot of premium on having add and remove quick, and the rest is whatever. >>> The important part is not to penalize the latency of normal requests >>> only to make self-checking faster. That process takes hours to loop >>> anyway, maybe days. >>> >>> I went with a list for now. >> >> How is an O(n) list faster than an O(1) hash table? > > Do you know what the constant is in that hash table (which is not > O(1) in case of conflicts)? The GLib implementation does its best to ensure each hash slot contains either zero or one entries, resizing the hash table if need be, as entries are inserted. It is O(1) except in extremely pathological cases. > Notice that the glib's hash table does NOT include a hash function. > This is something I wanted to discuss too. What would you use? > I researched what's available, and all of them come with rather > weird licenses (well, ok, Google hash is under the new BSD, which > works for us... or does it?). If you have a constant pointer value [for the lifetime of the hash table entry], use g_direct_hash. If you have a nul-terminated string, GLib also has g_str_hash. Otherwise, I would pick something simple like djb's hash. There is a version in nfs4d/main.c that you can grab. djb put his code into the public domain, which makes licensing easy. Jeff