From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Ted Zlatanov Newsgroups: gmane.emacs.devel Subject: bloom filters (was: concurrency suggestions for Gnus) Date: Tue, 08 Feb 2011 08:41:38 -0600 Organization: =?utf-8?B?0KLQtdC+0LTQvtGAINCX0LvQsNGC0LDQvdC+0LI=?= @ Cienfuegos Message-ID: <87fwry7fml.fsf_-_@lifelogs.com> References: <4D46E75E.7080503@harpegolden.net> <4D47E65E.1030901@gmail.com> <87pqr3vd6d.fsf_-_@lifelogs.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1297176127 15651 80.91.229.12 (8 Feb 2011 14:42:07 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 8 Feb 2011 14:42:07 +0000 (UTC) To: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Feb 08 15:42:02 2011 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1PmolV-00021A-C2 for ged-emacs-devel@m.gmane.org; Tue, 08 Feb 2011 15:42:01 +0100 Original-Received: from localhost ([127.0.0.1]:51749 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1PmolU-0004OJ-VK for ged-emacs-devel@m.gmane.org; Tue, 08 Feb 2011 09:42:01 -0500 Original-Received: from [140.186.70.92] (port=46355 helo=eggs.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1PmolQ-0004Mg-5R for emacs-devel@gnu.org; Tue, 08 Feb 2011 09:41:57 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1PmolP-0008GT-8J for emacs-devel@gnu.org; Tue, 08 Feb 2011 09:41:56 -0500 Original-Received: from lo.gmane.org ([80.91.229.12]:42414) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1PmolP-0008GM-1g for emacs-devel@gnu.org; Tue, 08 Feb 2011 09:41:55 -0500 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1PmolL-0001vG-AX for emacs-devel@gnu.org; Tue, 08 Feb 2011 15:41:51 +0100 Original-Received: from 38.98.147.130 ([38.98.147.130]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Tue, 08 Feb 2011 15:41:51 +0100 Original-Received: from tzz by 38.98.147.130 with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Tue, 08 Feb 2011 15:41:51 +0100 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 20 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 38.98.147.130 X-Face: bd.DQ~'29fIs`T_%O%C\g%6jW)yi[zuz6; d4V0`@y-~$#3P_Ng{@m+e4o<4P'#(_GJQ%TT= D}[Ep*b!\e,fBZ'j_+#"Ps?s2!4H2-Y"sx" User-Agent: Gnus/5.110011 (No Gnus v0.11) Emacs/24.0.50 (gnu/linux) Cancel-Lock: sha1:zLUIP681Y9snL/8CmIpghDZ/9+Q= X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 80.91.229.12 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:135748 Archived-At: On Tue, 08 Feb 2011 13:31:39 +0900 Miles Bader wrote: MB> Ted Zlatanov writes: Tom> If we went the "lock anything" route, I would suggest a weak hash table Tom> for locks, instead of putting the lock into the object. >> >> A bloom filter would guarantee no false negatives, which as you noted is >> the vast majority of the cases, requires very little space per element MB> A bloom filter...?! (changing the subject accordingly) Basically a fast membership query that uses pairwise independent hash functions. Runs in constant time, has no false negatives, and has a false positive rate correlated to the number of bits per element. It would actually be a nice addition to the Emacs core to have a C implementation. Ted