Bug#139838: marked as done ([PERF] dpkg: package database hash size too small)
Your message dated Tue, 3 Feb 2004 15:51:06 +0000
with message-id <20040203155105.GA29090@riva.ucam.org>
and subject line a bug filed against dpkg
has caused the attached Bug report to be marked as done.
This means that you claim that the problem has been dealt with.
If this is not the case it is now your responsibility to reopen the
Bug report if necessary, and/or fix the problem forthwith.
(NB: If you are a system administrator and have no idea what I am
talking about this indicates a serious mail system misconfiguration
somewhere. Please contact me immediately.)
Debian bug tracking system administrator
(administrator, Debian Bugs database)
--------------------------------------
Received: (at submit) by bugs.debian.org; 25 Mar 2002 14:37:38 +0000
>From cjwatson@flatline.org.uk Mon Mar 25 08:37:38 2002
Return-path: <cjwatson@flatline.org.uk>
Received: from rhenium.btinternet.com [194.73.73.93]
by master.debian.org with esmtp (Exim 3.12 1 (Debian))
id 16pVbO-0007a9-00; Mon, 25 Mar 2002 08:37:38 -0600
Received: from host217-35-28-203.in-addr.btopenworld.com ([217.35.28.203] helo=arborlon.lab.dotat.at)
by rhenium.btinternet.com with esmtp (Exim 3.22 #8)
id 16pVbM-0002Rz-00; Mon, 25 Mar 2002 14:37:36 +0000
Received: from cjwatson by arborlon.lab.dotat.at with local (Exim 3.35 #1 (Debian))
id 16pVaA-0007eG-00; Mon, 25 Mar 2002 14:36:22 +0000
Date: Mon, 25 Mar 2002 14:36:22 +0000
From: Colin Watson <cjwatson@debian.org>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: dpkg: performance problem - package database hash size too small
Message-ID: <20020325143622.GA29275@arborlon.riva.ucam.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.3.28i
X-Reportbug-Version: 1.99.10
X-Debbugs-Cc: Daniel Silverstone <dsilvers@debian.org>
Sender: Colin Watson <cjwatson@flatline.org.uk>
Delivered-To: submit@bugs.debian.org
Package: dpkg
Version: 1.9.20
Severity: normal
A profile of 'dpkg-query --status man-db' from CVS (1.9.20 behaves
similarly) shows this:
46.43 0.39 0.39 2 195.00 420.00 parsedb
27.38 0.62 0.23 91788 0.00 0.00 findpackage
4.76 0.66 0.04 72859 0.00 0.00 illegal_packagename
3.57 0.69 0.03 47854 0.00 0.00 convert_string
real 0m1.848s
user 0m1.770s
sys 0m0.060s
Investigation shows that the hash used to store available packages
(lib/database.c) has 128 bins, and was last tuned with a sample set of
141 packages in total. Since there are now over 9000 binary packages in
unstable, this could do with being tuned again.
Increasing the number of hash bins to 16384 shows a marked improvement:
46.27 0.31 0.31 2 155.00 335.00 parsedb
10.45 0.38 0.07 27891 0.00 0.00 f_filecharf
8.96 0.44 0.06 91788 0.00 0.00 findpackage
8.96 0.50 0.06 19503 0.00 0.01 f_dependency
real 0m1.538s
user 0m1.410s
sys 0m0.110s
A patch follows. We haven't tried to see what effect tuning the hash
function itself will have yet; it'll probably improve things a little
further, but not as much as reducing the enormous number of hash
collisions that take place at the moment.
--- lib/database.c.orig Mon Mar 25 14:29:00 2002
+++ lib/database.c Mon Mar 25 14:17:02 2002
@@ -26,7 +26,7 @@
#include <dpkg.h>
#include <dpkg-db.h>
-#define BINS (1 << 7)
+#define BINS (1 << 14)
/* This must always be a power of two. If you change it
* consider changing the per-character hashing factor (currently 5) too.
*/
Thanks,
--
Colin Watson [cjwatson@flatline.org.uk]
---------------------------------------
Received: (at 139838-done) by bugs.debian.org; 3 Feb 2004 15:51:12 +0000
>From cjwatson@flatline.org.uk Tue Feb 03 07:51:12 2004
Return-path: <cjwatson@flatline.org.uk>
Received: from chiark.greenend.org.uk [193.201.200.170] (mail)
by spohr.debian.org with esmtp (Exim 3.35 1 (Debian))
id 1Ao2pU-0004hY-00; Tue, 03 Feb 2004 07:51:12 -0800
Received: from [192.168.124.112] (helo=riva.lab.dotat.at)
by chiark.greenend.org.uk (Debian Exim 3.35 #1) with esmtp
id 1Ao2pS-0005Sj-00; Tue, 03 Feb 2004 15:51:10 +0000
Received: from cjwatson by riva.lab.dotat.at with local (Exim 3.35 #1 (Debian))
id 1Ao2pO-0007bI-00; Tue, 03 Feb 2004 15:51:06 +0000
Date: Tue, 3 Feb 2004 15:51:06 +0000
From: Colin Watson <cjwatson@debian.org>
To: Daniel Silverstone <dsilvers@debian.org>
Cc: 139838-done@bugs.debian.org
Subject: Re: a bug filed against dpkg
Message-ID: <20040203155105.GA29090@riva.ucam.org>
References: <1075732460.8728.5.camel@kenton.mips.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <1075732460.8728.5.camel@kenton.mips.com>
User-Agent: Mutt/1.3.28i
Delivered-To: 139838-done@bugs.debian.org
X-Spam-Checker-Version: SpamAssassin 2.60-bugs.debian.org_2004_02_01
(1.212-2003-09-23-exp) on spohr.debian.org
X-Spam-Status: No, hits=0.0 required=4.0 tests=none autolearn=no
version=2.60-bugs.debian.org_2004_02_01
X-Spam-Level:
On Mon, Feb 02, 2004 at 02:34:20PM +0000, Daniel Silverstone wrote:
> Bug 139838 is defunct since 1.10.11
>
> Can we close it?
Yes, it appears to be done due to the fix for #206416. Thanks!
--
Colin Watson [cjwatson@flatline.org.uk]
Reply to: