From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/9227 Path: main.gmane.org!not-for-mail From: Jim Meyering Newsgroups: gmane.emacs.gnus.general Subject: Re: Red Gnus v0.76 is released Date: 16 Dec 1996 22:36:33 -0600 Sender: meyering@appaloosa.asic.sc.ti.com Message-ID: References: Reply-To: meyering@asic.sc.ti.com, meyering@na-net.ornl.gov NNTP-Posting-Host: coloc-standby.netfonds.no Mime-Version: 1.0 (generated by tm-edit 7.94) Content-Type: text/plain; charset=US-ASCII X-Trace: main.gmane.org 1035149283 17176 80.91.224.250 (20 Oct 2002 21:28:03 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sun, 20 Oct 2002 21:28:03 +0000 (UTC) Return-Path: Original-Received: from ifi.uio.no (0@ifi.uio.no [129.240.64.2]) by deanna.miranova.com (8.8.4/8.8.4) with SMTP id UAA23793 for ; Mon, 16 Dec 1996 20:46:35 -0800 Original-Received: from dragon.ti.com (dragon.ti.com [192.94.94.61]) by ifi.uio.no with ESMTP (8.6.11/ifi2.4) id for ; Tue, 17 Dec 1996 05:36:21 +0100 Original-Received: from asic.sc.ti.com ([156.117.183.136]) by dragon.ti.com (8.6.13) with ESMTP id WAA01178 for ; Mon, 16 Dec 1996 22:35:50 -0600 Original-Received: from appaloosa.asic.sc.ti.com (appaloosa [156.117.183.236]) by asic.sc.ti.com (8.7.6/8.7.3) with ESMTP id WAA16920 for ; Mon, 16 Dec 1996 22:36:35 -0600 (CST) Original-Received: (from meyering@localhost) by appaloosa.asic.sc.ti.com (8.7.6/8.7.3) id WAA05568; Mon, 16 Dec 1996 22:36:33 -0600 (CST) Original-To: ding@ifi.uio.no In-Reply-To: Lars Magne Ingebrigtsen's message of 16 Dec 1996 23:47:43 +0100 Original-Lines: 28 X-Mailer: Red Gnus v0.74/Emacs 19.34 Xref: main.gmane.org gmane.emacs.gnus.general:9227 X-Report-Spam: http://spam.gmane.org/gmane.emacs.gnus.general:9227 Lars Magne Ingebrigtsen writes: | Thu Dec 12 18:18:11 1996 David Moore | | * gnus-util.el (gnus-create-hash-size): Power of 2 hashtables can | be _significantly_ faster than 2^x-1 tables on many risc | machines. Any gains of 2^x-1 are comparably small on other | machines. Hi. Have you considered any other implications of changing the table size to be a power of 2? It's pretty generally accepted that hash tables get better key distributions (fewer collisions) when the table size is a prime -- or has relatively few factors. A bad table size (and powers of 2 are notoriously bad) can make the normally-very-efficient (O(1)) insert/delete/lookup operations abyssymally slow O(n) ones. I suspect that choosing table size == 2^N (rather than the usually-good and sometimes-even-prime 2^N - 1) would degrade the efficiency due to the increased frequency of collisions. Whether this matters depends on how full the tables may become. If they're always nearly empty, then don't worry. If they ever contain more than say, 0.6 * table_size elements, I'd start to worry. In general, if you have the memory, it's best to keep your tables under 75% full. That latter is from Knuth. The 0.6 is my gut feeling. The 2^N business is from memory of Knuth and probably others.