GNU logs - #24937, boring messages

Message sent to bug-guix@HIDDEN:

Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Sun, 13 Nov 2016 17:42:02 +0000
Resent-Message-ID: <handler.24937.B.14790588776586 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 24937 <at> debbugs.gnu.org
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Date: Sun, 13 Nov 2016 18:41:01 +0100
Message-ID: <87wpg7ffbm.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

=E2=80=98LocalStore::removeUnusedLinks=E2=80=99 traverses all the entries in
/gnu/store/.links and calls lstat(2) on each one of them and checks
=E2=80=98st_nlink=E2=80=99 to determine whether they can be deleted.

There are two problems: lstat(2) can be slow on spinning disks as found
on hydra.gnu.org, and the algorithm is proportional in the number of
entries in /gnu/store/.links, which is a lot on hydra.gnu.org.

Ludo=E2=80=99.

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.505 (Entity 5.505)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Subject: bug#24937: Acknowledgement ("deleting unused links" GC phase is
 too slow)
Message-ID: <handler.24937.B.14790588776586.ack <at> debbugs.gnu.org>
References: <87wpg7ffbm.fsf@HIDDEN>
X-Gnu-PR-Message: ack 24937
X-Gnu-PR-Package: guix
Reply-To: 24937 <at> debbugs.gnu.org
Date: Sun, 13 Nov 2016 17:42:02 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-guix@HIDDEN

If you wish to submit further information on this problem, please
send it to 24937 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
24937: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D24937
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-guix@HIDDEN:

Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Fri, 09 Dec 2016 23:26:01 +0000
Resent-Message-ID: <handler.24937.B24937.148132591625091 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 24937 <at> debbugs.gnu.org
Cc: Mark H Weaver <mhw@HIDDEN>
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
References: <87wpg7ffbm.fsf@HIDDEN>
Date: Fri, 09 Dec 2016 23:43:57 +0100
In-Reply-To: <87wpg7ffbm.fsf@HIDDEN> ("Ludovic
 \=\?utf-8\?Q\?Court\=C3\=A8s\=22'\?\=
 \=\?utf-8\?Q\?s\?\= message of "Sun, 13 Nov 2016 18:41:01 +0100")
Message-ID: <87wpf867v6.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

ludo@HIDDEN (Ludovic Court=C3=A8s) skribis:

> =E2=80=98LocalStore::removeUnusedLinks=E2=80=99 traverses all the entries=
 in
> /gnu/store/.links and calls lstat(2) on each one of them and checks
> =E2=80=98st_nlink=E2=80=99 to determine whether they can be deleted.
>
> There are two problems: lstat(2) can be slow on spinning disks as found
> on hydra.gnu.org, and the algorithm is proportional in the number of
> entries in /gnu/store/.links, which is a lot on hydra.gnu.org.

On Dec. 2 on guix-sysadmin@HIDDEN, Mark described an improvement that
noticeably improved performance:

  The idea is to read the entire /gnu/store/.links directory, sort the
  entries by inode number, and then iterate over the entries by inode
  number, calling 'lstat' on each one and deleting the ones with a link
  count of 1.

  The reason this is so much faster is because the inodes are stored on
  disk in order of inode number, so this leads to a sequential access
  pattern on disk instead of a random access pattern.

  The difficulty is that the directory is too large to comfortably store
  all of the entries in virtual memory.  Instead, the entries should be
  written to temporary files on disk, and then sorted using merge sort to
  ensure sequential access patterns during sorting.  Fortunately, this is
  exactly what 'sort' does from GNU coreutils.

  So, for now, I've implemented this as a pair of small C programs that is
  used in a pipeline with GNU sort.  The first program simply reads a
  directory and writes lines of the form "<inode> <name>" to stdout.
  (Unfortunately, "ls -i" calls stat on each entry, so it can't be used).
  This is piped through 'sort -n' and then into another small C program
  that reads these lines, calls 'lstat' on each one, and deletes the
  non-directories with link count 1.

Regarding memory usage, I replied:

  Really?

  For each entry, we have to store roughly 70 bytes for the file name (or
  52 if we consider only the basename), plus 8 bytes for the inode number;
  let=E2=80=99s say 64 bytes.

  If we have 10 M entries, that=E2=80=99s 700 MB (or 520 MB), which is a lo=
t, but
  maybe acceptable?

  At worst, we may still see an improvement if we proceed by batches: we
  read 10000 directory entries (7 MB), sort them, and stat them, then read
  the next 10000 entries.  WDYT?

Ludo=E2=80=99.

Message received at control <at> debbugs.gnu.org:

Received: (at control) by debbugs.gnu.org; 9 Dec 2016 23:40:17 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Fri Dec 09 18:40:17 2016
Received: from localhost ([127.0.0.1]:36382 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cFUm0-00013X-Oi
	for submit <at> debbugs.gnu.org; Fri, 09 Dec 2016 18:40:16 -0500
Received: from eggs.gnu.org ([208.118.235.92]:59640)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <ludo@HIDDEN>) id 1cFU8f-0004Ph-GJ
 for control <at> debbugs.gnu.org; Fri, 09 Dec 2016 17:59:37 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <ludo@HIDDEN>) id 1cFTu1-0008Db-Ni
 for control <at> debbugs.gnu.org; Fri, 09 Dec 2016 17:44:34 -0500
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-3.0 required=5.0 tests=BAYES_20,RP_MATCHES_RCVD
 autolearn=disabled version=3.3.2
Received: from fencepost.gnu.org ([2001:4830:134:3::e]:47487)
 by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from <ludo@HIDDEN>)
 id 1cFTu1-0008DU-KP
 for control <at> debbugs.gnu.org; Fri, 09 Dec 2016 17:44:29 -0500
Received: from reverse-83.fdn.fr ([80.67.176.83]:37806 helo=pluto)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <ludo@HIDDEN>) id 1cFTu1-00060N-1V
 for control <at> debbugs.gnu.org; Fri, 09 Dec 2016 17:44:29 -0500
Date: Fri, 09 Dec 2016 23:44:27 +0100
Message-Id: <87vaus67uc.fsf@HIDDEN>
To: control <at> debbugs.gnu.org
From: ludo@HIDDEN (Ludovic =?utf-8?Q?Court=C3=A8s?=)
Subject: control message for bug #24937
MIME-version: 1.0
Content-type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2001:4830:134:3::e
X-Spam-Score: -8.0 (--------)
X-Debbugs-Envelope-To: control
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -8.0 (--------)

severity 24937 important

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
References: <87wpg7ffbm.fsf@HIDDEN>
In-Reply-To: <87wpg7ffbm.fsf@HIDDEN>
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Sun, 11 Dec 2016 13:51:01 +0000
Resent-Message-ID: <handler.24937.B24937.148146422513849 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: 24937 <at> debbugs.gnu.org
Cc: Mark H Weaver <mhw@HIDDEN>
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148146422513849
          (code B ref 24937); Sun, 11 Dec 2016 13:51:01 +0000
Received: (at 24937) by debbugs.gnu.org; 11 Dec 2016 13:50:25 +0000
Received: from localhost ([127.0.0.1]:37654 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cG4WH-0003bI-5M
	for submit <at> debbugs.gnu.org; Sun, 11 Dec 2016 08:50:25 -0500
Received: from eggs.gnu.org ([208.118.235.92]:53030)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <ludo@HIDDEN>) id 1cG4WC-0003as-TF
 for 24937 <at> debbugs.gnu.org; Sun, 11 Dec 2016 08:50:23 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <ludo@HIDDEN>) id 1cG4Vw-0005rg-7V
 for 24937 <at> debbugs.gnu.org; Sun, 11 Dec 2016 08:50:07 -0500
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-0.7 required=5.0 tests=BAYES_50,FAKE_REPLY_C,
 RP_MATCHES_RCVD autolearn=disabled version=3.3.2
Received: from fencepost.gnu.org ([2001:4830:134:3::e]:42762)
 by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from <ludo@HIDDEN>)
 id 1cG4Vh-0005jy-VM; Sun, 11 Dec 2016 08:49:50 -0500
Received: from [81.253.18.84] (port=43514 helo=pluto)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <ludo@HIDDEN>)
 id 1cG4Vc-000709-U4; Sun, 11 Dec 2016 08:49:49 -0500
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Date: Sun, 11 Dec 2016 14:46:13 +0100
Message-ID: <87lgvm4lzu.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
X-URL: http://www.fdn.fr/~lcourtes/
X-Revolutionary-Date: 21 Frimaire an 225 de la =?UTF-8?Q?R=C3=A9volution?=
X-PGP-Key-ID: 0x090B11993D9AEBB5
X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc
X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4  0CFB 090B 1199 3D9A EBB5
X-OS: x86_64-unknown-linux-gnu
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2001:4830:134:3::e
X-Spam-Score: -8.0 (--------)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -8.0 (--------)

--=-=-=
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Hello!

Here=E2=80=99s a proposed patch that follows your suggestion, Mark, but pla=
ces
an upper bound on the number of directory entries loaded in memory.

On my laptop, which has ~500k entries in /gnu/store/.links, the result
is something like this (notice the inode numbers in =E2=80=98lstat=E2=80=99=
 calls):

--8<---------------cut here---------------start------------->8---
13738 write(4, "gmlo\0\0\0\0\31\0\0\0\0\0\0\0deleting unused "..., 48) =3D =
48
13738 open("/gnu/store/.links", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) =
=3D 8
13738 fstat(8, {st_dev=3Dmakedev(8, 2), st_ino=3D4014083, st_mode=3DS_IFDIR=
|0755, st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=
=3D119224, st_size=3D60977152, st_atime=3D2016/12/11-12:01:59, st_mtime=3D2=
016/12/11-09:39:45, st_ctime=3D2016/12/11-09:39:45}) =3D 0
13738 getdents(8, {{d_ino=3D4014083, d_off=3D4294967296, d_reclen=3D24, d_n=
ame=3D"."}
[...]
13738 lstat("/gnu/store/.links/1f2f3g8waxwymp9sl2slcfyara164i8w1y2sz3h9js2f=
cviv2rnc", {st_dev=3Dmakedev(8, 2), st_ino=3D47, st_mode=3DS_IFREG|0444, st=
_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D88, st_s=
ize=3D41482, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2015/11/25-11:29:20}) =3D 0
13738 lstat("/gnu/store/.links/1p25kpyfw354in4kykmgh5sy9h925hnil1jdzgxhz7n6=
abbws8px", {st_dev=3Dmakedev(8, 2), st_ino=3D65, st_mode=3DS_IFREG|0444, st=
_nlink=3D9, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si=
ze=3D2313, st_atime=3D2016/12/08-21:02:26, st_mtime=3D1970/01/01-01:00:01, =
st_ctime=3D2016/12/11-01:44:49}) =3D 0
13738 lstat("/gnu/store/.links/163187g637br9ys5pmshb01wjav53bs1g1a83m7c2alp=
dyx3yqz2", {st_dev=3Dmakedev(8, 2), st_ino=3D68, st_mode=3DS_IFREG|0444, st=
_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D32, st_s=
ize=3D13561, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2015/11/25-11:29:20}) =3D 0
[...]
13738 getdents(8, {{d_ino=3D4257114, d_off=3D1734093409898198492,
[...]
13738 lstat("/gnu/store/.links/1m6g06i01ybbkhjjbirjnj7fckw1b772cwygkvbd6v6z=
gkln7f7m", {st_dev=3Dmakedev(8, 2), st_ino=3D19, st_mode=3DS_IFREG|0444, st=
_nlink=3D4, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si=
ze=3D2553, st_atime=3D2016/12/08-21:02:54, st_mtime=3D1970/01/01-01:00:01, =
st_ctime=3D2016/12/07-00:05:19}) =3D 0
13738 lstat("/gnu/store/.links/1ml8n3q55ikn8h60sn67jq1y7z7mvdp5kwr33pqrid2r=
6kk1d4kb", {st_dev=3Dmakedev(8, 2), st_ino=3D30, st_mode=3DS_IFREG|0444, st=
_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si=
ze=3D2090, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01, =
st_ctime=3D2015/11/25-11:29:21}) =3D 0
13738 lstat("/gnu/store/.links/1c8cvwlqyyqby3k13cwm40g26pwca5iiz5dcj43xrgn9=
y91lfvc2", {st_dev=3Dmakedev(8, 2), st_ino=3D33, st_mode=3DS_IFREG|0444, st=
_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D16, st_s=
ize=3D7958, st_atime=3D2015/11/04-18:55:32, st_mtime=3D1970/01/01-01:00:01,=
 st_ctime=3D2016/01/05-11:35:49}) =3D 0
[...]
13738 getdents(8, {{d_ino=3D328672,
[...]
13738 lstat("/gnu/store/.links/1l55l59dxb74himmkfzx5v63cv7287i6rjhdns1fdlwa=
jqd73lnz", {st_dev=3Dmakedev(8, 2), st_ino=3D21, st_mode=3DS_IFREG|0444, st=
_nlink=3D31, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_s=
ize=3D615, st_atime=3D2016/12/08-21:02:30, st_mtime=3D1970/01/01-01:00:01, =
st_ctime=3D2016/12/11-01:44:47}) =3D 0
13738 lstat("/gnu/store/.links/1c7mm5amw743mb45f1zg4d4r3g549ch35wks9izkcgkx=
0jirpxsg", {st_dev=3Dmakedev(8, 2), st_ino=3D48, st_mode=3DS_IFREG|0444, st=
_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D360, st_=
size=3D176750, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:=
01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
13738 lstat("/gnu/store/.links/0z5s7b0yk8mfn1np6gk3cdbmpnjgxg1g0l8vfq1aa01z=
wp06d3f0", {st_dev=3Dmakedev(8, 2), st_ino=3D61, st_mode=3DS_IFREG|0444, st=
_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_si=
ze=3D1440, st_atime=3D2016/11/03-20:37:50, st_mtime=3D1970/01/01-01:00:01, =
st_ctime=3D2016/11/07-00:01:57}) =3D 0
--8<---------------cut here---------------end--------------->8---

I can=E2=80=99t tell exactly how this affects performance because my machin=
e has
an SSD where this operation takes ~3 seconds on a cold cache.  I suspect
it has performance comparable to that of doing all the =E2=80=98readdir=E2=
=80=99 at once
followed by all the =E2=80=98lstat=E2=80=99.

Mark, how does that sound?

I=E2=80=99d like to commit it soon if there are no objections.

Thanks,
Ludo=E2=80=99.


--=-=-=
Content-Type: text/x-patch
Content-Disposition: inline

diff --git a/nix/libstore/gc.cc b/nix/libstore/gc.cc
index 72eff52..db58603 100644
--- a/nix/libstore/gc.cc
+++ b/nix/libstore/gc.cc
@@ -545,6 +545,9 @@ void LocalStore::tryToDelete(GCState & state, const Path & path)
 }
 
 
+/* Like 'dirent', but with just what we need.  */
+typedef std::pair<Path, ino_t> MiniDirEntry;
+
 /* Unlink all files in /nix/store/.links that have a link count of 1,
    which indicates that there are no other links and so they can be
    safely deleted.  FIXME: race condition with optimisePath(): we
@@ -555,32 +558,57 @@ void LocalStore::removeUnusedLinks(const GCState & state)
     AutoCloseDir dir = opendir(linksDir.c_str());
     if (!dir) throw SysError(format("opening directory `%1%'") % linksDir);
 
+    /* Maximum number of entries stored in memory; each 'MiniDirEntry' takes
+       ~80 bytes.  */
+    const size_t maxEntries = 100000;
+
     long long actualSize = 0, unsharedSize = 0;
 
-    struct dirent * dirent;
-    while (errno = 0, dirent = readdir(dir)) {
-        checkInterrupt();
-        string name = dirent->d_name;
-        if (name == "." || name == "..") continue;
-        Path path = linksDir + "/" + name;
-
-        struct stat st;
-        if (lstat(path.c_str(), &st) == -1)
-            throw SysError(format("statting `%1%'") % path);
-
-        if (st.st_nlink != 1) {
-            unsigned long long size = st.st_blocks * 512ULL;
-            actualSize += size;
-            unsharedSize += (st.st_nlink - 1) * size;
-            continue;
-        }
-
-        printMsg(lvlTalkative, format("deleting unused link `%1%'") % path);
-
-        if (unlink(path.c_str()) == -1)
-            throw SysError(format("deleting `%1%'") % path);
-
-        state.results.bytesFreed += st.st_blocks * 512;
+    bool endOfDir = false;
+
+    while (!endOfDir) {
+	/* Read as many entries as possible at once, up to 'maxEntries'.  */
+	std::list<MiniDirEntry> entries;
+	struct dirent * dirent;
+	while (errno = 0,
+	       (entries.size() < maxEntries) && (dirent = readdir(dir))) {
+	    checkInterrupt();
+	    string name = dirent->d_name;
+	    if (name == "." || name == "..") continue;
+	    entries.emplace_back(MiniDirEntry(name, dirent->d_ino));
+	}
+
+	endOfDir = (dirent == NULL);
+
+	/* Sort entries by inode number to minimize disk seeks induced by the
+	   following 'lstat' calls.  */
+	entries.sort([] (const MiniDirEntry& e1, const MiniDirEntry& e2) {
+		return e1.second < e2.second;
+	    });
+
+	for (auto && item: entries) {
+	    checkInterrupt();
+
+	    Path path = linksDir + "/" + item.first;
+
+	    struct stat st;
+	    if (lstat(path.c_str(), &st) == -1)
+		throw SysError(format("statting `%1%'") % path);
+
+	    if (st.st_nlink != 1) {
+		unsigned long long size = st.st_blocks * 512ULL;
+		actualSize += size;
+		unsharedSize += (st.st_nlink - 1) * size;
+		continue;
+	    }
+
x+	    printMsg(lvlTalkative, format("deleting unused link `%1%'") % path);
+
+	    if (unlink(path.c_str()) == -1)
+		throw SysError(format("deleting `%1%'") % path);
+
+	    state.results.bytesFreed += st.st_blocks * 512;
+	}
     }
 
     struct stat st;

--=-=-=--

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: Mark H Weaver <mhw@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Sun, 11 Dec 2016 14:24:02 +0000
Resent-Message-ID: <handler.24937.B24937.148146622916996 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148146622916996
          (code B ref 24937); Sun, 11 Dec 2016 14:24:02 +0000
Received: (at 24937) by debbugs.gnu.org; 11 Dec 2016 14:23:49 +0000
Received: from localhost ([127.0.0.1]:37674 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cG52a-0004Q3-VV
	for submit <at> debbugs.gnu.org; Sun, 11 Dec 2016 09:23:49 -0500
Received: from world.peace.net ([50.252.239.5]:41388)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1cG52Z-0004Pm-5c
 for 24937 <at> debbugs.gnu.org; Sun, 11 Dec 2016 09:23:47 -0500
Received: from [10.1.10.193] (helo=jojen)
 by world.peace.net with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <mhw@HIDDEN>)
 id 1cG52S-0003Lf-MS; Sun, 11 Dec 2016 09:23:40 -0500
From: Mark H Weaver <mhw@HIDDEN>
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
Date: Sun, 11 Dec 2016 09:23:38 -0500
In-Reply-To: <87lgvm4lzu.fsf@HIDDEN> ("Ludovic
 \=\?utf-8\?Q\?Court\=C3\=A8s\=22'\?\=
 \=\?utf-8\?Q\?s\?\= message of "Sun, 11 Dec 2016 14:46:13 +0100")
Message-ID: <87twaaa6j9.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: 0.0 (/)

ludo@HIDDEN (Ludovic Court=C3=A8s) writes:

> Here=E2=80=99s a proposed patch that follows your suggestion, Mark, but p=
laces
> an upper bound on the number of directory entries loaded in memory.
>
> On my laptop, which has ~500k entries in /gnu/store/.links, the result
> is something like this (notice the inode numbers in =E2=80=98lstat=E2=80=
=99 calls):
>
> 13738 write(4, "gmlo\0\0\0\0\31\0\0\0\0\0\0\0deleting unused "..., 48) =
=3D 48
> 13738 open("/gnu/store/.links", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC=
) =3D 8
> 13738 fstat(8, {st_dev=3Dmakedev(8, 2), st_ino=3D4014083, st_mode=3DS_IFD=
IR|0755, st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=
=3D119224, st_size=3D60977152, st_atime=3D2016/12/11-12:01:59, st_mtime=3D2=
016/12/11-09:39:45, st_ctime=3D2016/12/11-09:39:45}) =3D 0
> 13738 getdents(8, {{d_ino=3D4014083, d_off=3D4294967296, d_reclen=3D24, d=
_name=3D"."}
> [...]
> 13738 lstat("/gnu/store/.links/1f2f3g8waxwymp9sl2slcfyara164i8w1y2sz3h9js=
2fcviv2rnc", {st_dev=3Dmakedev(8, 2), st_ino=3D47, st_mode=3DS_IFREG|0444, =
st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D88, st=
_size=3D41482, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:=
01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
> 13738 lstat("/gnu/store/.links/1p25kpyfw354in4kykmgh5sy9h925hnil1jdzgxhz7=
n6abbws8px", {st_dev=3Dmakedev(8, 2), st_ino=3D65, st_mode=3DS_IFREG|0444, =
st_nlink=3D9, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_=
size=3D2313, st_atime=3D2016/12/08-21:02:26, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2016/12/11-01:44:49}) =3D 0
> 13738 lstat("/gnu/store/.links/163187g637br9ys5pmshb01wjav53bs1g1a83m7c2a=
lpdyx3yqz2", {st_dev=3Dmakedev(8, 2), st_ino=3D68, st_mode=3DS_IFREG|0444, =
st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D32, st=
_size=3D13561, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:=
01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
> [...]
> 13738 getdents(8, {{d_ino=3D4257114, d_off=3D1734093409898198492,
> [...]
> 13738 lstat("/gnu/store/.links/1m6g06i01ybbkhjjbirjnj7fckw1b772cwygkvbd6v=
6zgkln7f7m", {st_dev=3Dmakedev(8, 2), st_ino=3D19, st_mode=3DS_IFREG|0444, =
st_nlink=3D4, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_=
size=3D2553, st_atime=3D2016/12/08-21:02:54, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2016/12/07-00:05:19}) =3D 0
> 13738 lstat("/gnu/store/.links/1ml8n3q55ikn8h60sn67jq1y7z7mvdp5kwr33pqrid=
2r6kk1d4kb", {st_dev=3Dmakedev(8, 2), st_ino=3D30, st_mode=3DS_IFREG|0444, =
st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_=
size=3D2090, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2015/11/25-11:29:21}) =3D 0
> 13738 lstat("/gnu/store/.links/1c8cvwlqyyqby3k13cwm40g26pwca5iiz5dcj43xrg=
n9y91lfvc2", {st_dev=3Dmakedev(8, 2), st_ino=3D33, st_mode=3DS_IFREG|0444, =
st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D16, st=
_size=3D7958, st_atime=3D2015/11/04-18:55:32, st_mtime=3D1970/01/01-01:00:0=
1, st_ctime=3D2016/01/05-11:35:49}) =3D 0
> [...]
> 13738 getdents(8, {{d_ino=3D328672,
> [...]
> 13738 lstat("/gnu/store/.links/1l55l59dxb74himmkfzx5v63cv7287i6rjhdns1fdl=
wajqd73lnz", {st_dev=3Dmakedev(8, 2), st_ino=3D21, st_mode=3DS_IFREG|0444, =
st_nlink=3D31, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st=
_size=3D615, st_atime=3D2016/12/08-21:02:30, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2016/12/11-01:44:47}) =3D 0
> 13738 lstat("/gnu/store/.links/1c7mm5amw743mb45f1zg4d4r3g549ch35wks9izkcg=
kx0jirpxsg", {st_dev=3Dmakedev(8, 2), st_ino=3D48, st_mode=3DS_IFREG|0444, =
st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D360, s=
t_size=3D176750, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:0=
0:01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
> 13738 lstat("/gnu/store/.links/0z5s7b0yk8mfn1np6gk3cdbmpnjgxg1g0l8vfq1aa0=
1zwp06d3f0", {st_dev=3Dmakedev(8, 2), st_ino=3D61, st_mode=3DS_IFREG|0444, =
st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st_=
size=3D1440, st_atime=3D2016/11/03-20:37:50, st_mtime=3D1970/01/01-01:00:01=
, st_ctime=3D2016/11/07-00:01:57}) =3D 0
>
> I can=E2=80=99t tell exactly how this affects performance because my mach=
ine has
> an SSD where this operation takes ~3 seconds on a cold cache.  I suspect
> it has performance comparable to that of doing all the =E2=80=98readdir=
=E2=80=99 at once
> followed by all the =E2=80=98lstat=E2=80=99.
>
> Mark, how does that sound?

I think we should sort the entire directory using merge sort backed to
disk files.  If we load chunks of the directory, sort them and process
them individually, I expect that this will increase the amount of I/O
required by a non-trivial factor.  In each pass, we would load blocks of
inodes from disk, almost all of which are likely to be present in the
store and thus linked from the directory, but in this scheme we will
process only a small number of them and drop the rest on the floor to be
read again in the next pass.  Given that even my fairly optimal
implementation takes about 35 minutes to run on Hydra, I'd prefer to
avoid multiplying that by a non-trivial factor.

Why not just use GNU sort?  It already exists, and does exactly what we
need.

If you object to using an external program for some reason, I would
prefer to re-implement a similar algorithm in the daemon.

     Thanks,
       Mark

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Sun, 11 Dec 2016 18:03:01 +0000
Resent-Message-ID: <handler.24937.B24937.148147938111766 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: Mark H Weaver <mhw@HIDDEN>
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148147938111766
          (code B ref 24937); Sun, 11 Dec 2016 18:03:01 +0000
Received: (at 24937) by debbugs.gnu.org; 11 Dec 2016 18:03:01 +0000
Received: from localhost ([127.0.0.1]:38362 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cG8Si-00033i-R9
	for submit <at> debbugs.gnu.org; Sun, 11 Dec 2016 13:03:01 -0500
Received: from eggs.gnu.org ([208.118.235.92]:35597)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <ludo@HIDDEN>) id 1cG8Sh-00033V-Sq
 for 24937 <at> debbugs.gnu.org; Sun, 11 Dec 2016 13:03:00 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <ludo@HIDDEN>) id 1cG8SZ-0002tq-LC
 for 24937 <at> debbugs.gnu.org; Sun, 11 Dec 2016 13:02:54 -0500
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-2.2 required=5.0 tests=BAYES_50,RP_MATCHES_RCVD
 autolearn=disabled version=3.3.2
Received: from fencepost.gnu.org ([2001:4830:134:3::e]:45379)
 by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from <ludo@HIDDEN>)
 id 1cG8SZ-0002tm-Is; Sun, 11 Dec 2016 13:02:51 -0500
Received: from [37.120.80.33] (port=38208 helo=pluto)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <ludo@HIDDEN>)
 id 1cG8SX-0003jn-M5; Sun, 11 Dec 2016 13:02:51 -0500
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
 <87twaaa6j9.fsf@HIDDEN>
X-URL: http://www.fdn.fr/~lcourtes/
X-Revolutionary-Date: 21 Frimaire an 225 de la =?UTF-8?Q?R=C3=A9volution?=
X-PGP-Key-ID: 0x090B11993D9AEBB5
X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc
X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4  0CFB 090B 1199 3D9A EBB5
X-OS: x86_64-unknown-linux-gnu
Date: Sun, 11 Dec 2016 19:02:42 +0100
In-Reply-To: <87twaaa6j9.fsf@HIDDEN> (Mark H. Weaver's message of "Sun, 11
 Dec 2016 09:23:38 -0500")
Message-ID: <87twaa2vjx.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2001:4830:134:3::e
X-Spam-Score: -8.0 (--------)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -8.0 (--------)

Mark H Weaver <mhw@HIDDEN> skribis:

> ludo@HIDDEN (Ludovic Court=C3=A8s) writes:
>
>> Here=E2=80=99s a proposed patch that follows your suggestion, Mark, but =
places
>> an upper bound on the number of directory entries loaded in memory.
>>
>> On my laptop, which has ~500k entries in /gnu/store/.links, the result
>> is something like this (notice the inode numbers in =E2=80=98lstat=E2=80=
=99 calls):
>>
>> 13738 write(4, "gmlo\0\0\0\0\31\0\0\0\0\0\0\0deleting unused "..., 48) =
=3D 48
>> 13738 open("/gnu/store/.links", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXE=
C) =3D 8
>> 13738 fstat(8, {st_dev=3Dmakedev(8, 2), st_ino=3D4014083, st_mode=3DS_IF=
DIR|0755, st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_block=
s=3D119224, st_size=3D60977152, st_atime=3D2016/12/11-12:01:59, st_mtime=3D=
2016/12/11-09:39:45, st_ctime=3D2016/12/11-09:39:45}) =3D 0
>> 13738 getdents(8, {{d_ino=3D4014083, d_off=3D4294967296, d_reclen=3D24, =
d_name=3D"."}
>> [...]
>> 13738 lstat("/gnu/store/.links/1f2f3g8waxwymp9sl2slcfyara164i8w1y2sz3h9j=
s2fcviv2rnc", {st_dev=3Dmakedev(8, 2), st_ino=3D47, st_mode=3DS_IFREG|0444,=
 st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D88, s=
t_size=3D41482, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00=
:01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
>> 13738 lstat("/gnu/store/.links/1p25kpyfw354in4kykmgh5sy9h925hnil1jdzgxhz=
7n6abbws8px", {st_dev=3Dmakedev(8, 2), st_ino=3D65, st_mode=3DS_IFREG|0444,=
 st_nlink=3D9, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st=
_size=3D2313, st_atime=3D2016/12/08-21:02:26, st_mtime=3D1970/01/01-01:00:0=
1, st_ctime=3D2016/12/11-01:44:49}) =3D 0
>> 13738 lstat("/gnu/store/.links/163187g637br9ys5pmshb01wjav53bs1g1a83m7c2=
alpdyx3yqz2", {st_dev=3Dmakedev(8, 2), st_ino=3D68, st_mode=3DS_IFREG|0444,=
 st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D32, s=
t_size=3D13561, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00=
:01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
>> [...]
>> 13738 getdents(8, {{d_ino=3D4257114, d_off=3D1734093409898198492,
>> [...]
>> 13738 lstat("/gnu/store/.links/1m6g06i01ybbkhjjbirjnj7fckw1b772cwygkvbd6=
v6zgkln7f7m", {st_dev=3Dmakedev(8, 2), st_ino=3D19, st_mode=3DS_IFREG|0444,=
 st_nlink=3D4, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st=
_size=3D2553, st_atime=3D2016/12/08-21:02:54, st_mtime=3D1970/01/01-01:00:0=
1, st_ctime=3D2016/12/07-00:05:19}) =3D 0
>> 13738 lstat("/gnu/store/.links/1ml8n3q55ikn8h60sn67jq1y7z7mvdp5kwr33pqri=
d2r6kk1d4kb", {st_dev=3Dmakedev(8, 2), st_ino=3D30, st_mode=3DS_IFREG|0444,=
 st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st=
_size=3D2090, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:00:0=
1, st_ctime=3D2015/11/25-11:29:21}) =3D 0
>> 13738 lstat("/gnu/store/.links/1c8cvwlqyyqby3k13cwm40g26pwca5iiz5dcj43xr=
gn9y91lfvc2", {st_dev=3Dmakedev(8, 2), st_ino=3D33, st_mode=3DS_IFREG|0444,=
 st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D16, s=
t_size=3D7958, st_atime=3D2015/11/04-18:55:32, st_mtime=3D1970/01/01-01:00:=
01, st_ctime=3D2016/01/05-11:35:49}) =3D 0
>> [...]
>> 13738 getdents(8, {{d_ino=3D328672,
>> [...]
>> 13738 lstat("/gnu/store/.links/1l55l59dxb74himmkfzx5v63cv7287i6rjhdns1fd=
lwajqd73lnz", {st_dev=3Dmakedev(8, 2), st_ino=3D21, st_mode=3DS_IFREG|0444,=
 st_nlink=3D31, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, s=
t_size=3D615, st_atime=3D2016/12/08-21:02:30, st_mtime=3D1970/01/01-01:00:0=
1, st_ctime=3D2016/12/11-01:44:47}) =3D 0
>> 13738 lstat("/gnu/store/.links/1c7mm5amw743mb45f1zg4d4r3g549ch35wks9izkc=
gkx0jirpxsg", {st_dev=3Dmakedev(8, 2), st_ino=3D48, st_mode=3DS_IFREG|0444,=
 st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D360, =
st_size=3D176750, st_atime=3D2015/03/10-11:29:06, st_mtime=3D1970/01/01-01:=
00:01, st_ctime=3D2015/11/25-11:29:20}) =3D 0
>> 13738 lstat("/gnu/store/.links/0z5s7b0yk8mfn1np6gk3cdbmpnjgxg1g0l8vfq1aa=
01zwp06d3f0", {st_dev=3Dmakedev(8, 2), st_ino=3D61, st_mode=3DS_IFREG|0444,=
 st_nlink=3D2, st_uid=3D0, st_gid=3D0, st_blksize=3D4096, st_blocks=3D8, st=
_size=3D1440, st_atime=3D2016/11/03-20:37:50, st_mtime=3D1970/01/01-01:00:0=
1, st_ctime=3D2016/11/07-00:01:57}) =3D 0
>>
>> I can=E2=80=99t tell exactly how this affects performance because my mac=
hine has
>> an SSD where this operation takes ~3 seconds on a cold cache.  I suspect
>> it has performance comparable to that of doing all the =E2=80=98readdir=
=E2=80=99 at once
>> followed by all the =E2=80=98lstat=E2=80=99.
>>
>> Mark, how does that sound?
>
> I think we should sort the entire directory using merge sort backed to
> disk files.  If we load chunks of the directory, sort them and process
> them individually, I expect that this will increase the amount of I/O
> required by a non-trivial factor.  In each pass, we would load blocks of
> inodes from disk, almost all of which are likely to be present in the
> store and thus linked from the directory, but in this scheme we will
> process only a small number of them and drop the rest on the floor to be
> read again in the next pass.  Given that even my fairly optimal
> implementation takes about 35 minutes to run on Hydra, I'd prefer to
> avoid multiplying that by a non-trivial factor.

Sure, though it=E2=80=99s not obvious to me how much of a difference it mak=
es;
my guess is that processing in large chunks is already a win, but we=E2=80=
=99d
have to measure.

> Why not just use GNU sort?  It already exists, and does exactly what we
> need.

Does =E2=80=98sort=E2=80=99 manage to avoid reading whole files in memory? =
 If not, I
think it wouldn=E2=80=99t buy us anything to use it.

> If you object to using an external program for some reason, I would
> prefer to re-implement a similar algorithm in the daemon.

Yeah, I=E2=80=99d rather avoid serializing the list of file names/inode num=
ber
pairs just to invoke =E2=80=98sort=E2=80=99 on that.

Also, what algorithm are you referring to?

Thanks for the quick feedback!

Ludo=E2=80=99.

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: Mark H Weaver <mhw@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Sun, 11 Dec 2016 19:28:02 +0000
Resent-Message-ID: <handler.24937.B24937.148148446126281 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148148446126281
          (code B ref 24937); Sun, 11 Dec 2016 19:28:02 +0000
Received: (at 24937) by debbugs.gnu.org; 11 Dec 2016 19:27:41 +0000
Received: from localhost ([127.0.0.1]:38429 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cG9mf-0006pp-7K
	for submit <at> debbugs.gnu.org; Sun, 11 Dec 2016 14:27:41 -0500
Received: from world.peace.net ([50.252.239.5]:44137)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1cG9md-0006pc-Fc
 for 24937 <at> debbugs.gnu.org; Sun, 11 Dec 2016 14:27:39 -0500
Received: from [10.1.10.104] (helo=jojen)
 by world.peace.net with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <mhw@HIDDEN>)
 id 1cG9mX-00075t-PJ; Sun, 11 Dec 2016 14:27:33 -0500
From: Mark H Weaver <mhw@HIDDEN>
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
 <87twaaa6j9.fsf@HIDDEN> <87twaa2vjx.fsf@HIDDEN>
Date: Sun, 11 Dec 2016 14:27:33 -0500
In-Reply-To: <87twaa2vjx.fsf@HIDDEN> ("Ludovic
 \=\?utf-8\?Q\?Court\=C3\=A8s\=22'\?\=
 \=\?utf-8\?Q\?s\?\= message of "Sun, 11 Dec 2016 19:02:42 +0100")
Message-ID: <87lgvm9sgq.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: 0.0 (/)

ludo@HIDDEN (Ludovic Court=C3=A8s) writes:

> Mark H Weaver <mhw@HIDDEN> skribis:
>
>> I think we should sort the entire directory using merge sort backed to
>> disk files.  If we load chunks of the directory, sort them and process
>> them individually, I expect that this will increase the amount of I/O
>> required by a non-trivial factor.  In each pass, we would load blocks of
>> inodes from disk, almost all of which are likely to be present in the
>> store and thus linked from the directory, but in this scheme we will
>> process only a small number of them and drop the rest on the floor to be
>> read again in the next pass.  Given that even my fairly optimal
>> implementation takes about 35 minutes to run on Hydra, I'd prefer to
>> avoid multiplying that by a non-trivial factor.
>
> Sure, though it=E2=80=99s not obvious to me how much of a difference it m=
akes;
> my guess is that processing in large chunks is already a win, but we=E2=
=80=99d
> have to measure.

I agree, it would surely be a win.  Given that it currently takes on the
order of a day to run this phase on Hydra, if your proposed method takes
2 hours, that would be a huge win, but still not good, IMO.  Even 35
minutes is slower than I'd like.

>> Why not just use GNU sort?  It already exists, and does exactly what we
>> need.
>
> Does =E2=80=98sort=E2=80=99 manage to avoid reading whole files in memory?

Yes, it does.  I monitored the 'sort' process when I first ran my
optimized pipeline.  It created about 10 files in /tmp, approximately 70
megabytes each as I recall, and then read them all concurrently while
writing the sorted output.

My guess is that it reads a manageable chunk of the input, sorts it in
memory, and writes it to a temporary file.  I guess it repeats this
process, writing multiple temporary files, until the entire input is
consumed, and then reads all of those temporary files, merging them
together into the output stream.

>> If you object to using an external program for some reason, I would
>> prefer to re-implement a similar algorithm in the daemon.
>
> Yeah, I=E2=80=99d rather avoid serializing the list of file names/inode n=
umber
> pairs just to invoke =E2=80=98sort=E2=80=99 on that.

Sure, I agree that it would be better to avoid that, but IMO not at the
cost of using O(N) memory instead of O(1) memory, nor at the cost of
multiplying the amount of disk I/O by a non-trivial factor.

> Also, what algorithm are you referring to?

The algorithm I described above, which I guess is close to what GNU sort
does.

    Thanks,
      Mark

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Tue, 13 Dec 2016 00:01:02 +0000
Resent-Message-ID: <handler.24937.B24937.148158722127895 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: Mark H Weaver <mhw@HIDDEN>
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148158722127895
          (code B ref 24937); Tue, 13 Dec 2016 00:01:02 +0000
Received: (at 24937) by debbugs.gnu.org; 13 Dec 2016 00:00:21 +0000
Received: from localhost ([127.0.0.1]:39753 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cGaW5-0007Fq-EA
	for submit <at> debbugs.gnu.org; Mon, 12 Dec 2016 19:00:21 -0500
Received: from eggs.gnu.org ([208.118.235.92]:40034)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <ludo@HIDDEN>) id 1cGaW3-0007Fc-WC
 for 24937 <at> debbugs.gnu.org; Mon, 12 Dec 2016 19:00:20 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <ludo@HIDDEN>) id 1cGaVv-0007QN-Pl
 for 24937 <at> debbugs.gnu.org; Mon, 12 Dec 2016 19:00:14 -0500
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_50,RP_MATCHES_RCVD
 autolearn=disabled version=3.3.2
Received: from fencepost.gnu.org ([2001:4830:134:3::e]:36654)
 by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from <ludo@HIDDEN>)
 id 1cGaVv-0007QG-M6; Mon, 12 Dec 2016 19:00:11 -0500
Received: from [37.120.80.33] (port=40034 helo=pluto)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <ludo@HIDDEN>)
 id 1cGaVu-0003f7-Tm; Mon, 12 Dec 2016 19:00:11 -0500
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
 <87twaaa6j9.fsf@HIDDEN> <87twaa2vjx.fsf@HIDDEN>
 <87lgvm9sgq.fsf@HIDDEN>
X-URL: http://www.fdn.fr/~lcourtes/
X-Revolutionary-Date: 22 Frimaire an 225 de la =?UTF-8?Q?R=C3=A9volution?=
X-PGP-Key-ID: 0x090B11993D9AEBB5
X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc
X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4  0CFB 090B 1199 3D9A EBB5
X-OS: x86_64-unknown-linux-gnu
Date: Tue, 13 Dec 2016 01:00:07 +0100
In-Reply-To: <87lgvm9sgq.fsf@HIDDEN> (Mark H. Weaver's message of "Sun, 11
 Dec 2016 14:27:33 -0500")
Message-ID: <87d1gwvgu0.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="=-=-="
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2001:4830:134:3::e
X-Spam-Score: -8.1 (--------)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -8.1 (--------)

--=-=-=
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

Mark H Weaver <mhw@HIDDEN> skribis:

> ludo@HIDDEN (Ludovic Court=C3=A8s) writes:
>
>> Mark H Weaver <mhw@HIDDEN> skribis:
>>
>>> I think we should sort the entire directory using merge sort backed to
>>> disk files.  If we load chunks of the directory, sort them and process
>>> them individually, I expect that this will increase the amount of I/O
>>> required by a non-trivial factor.  In each pass, we would load blocks of
>>> inodes from disk, almost all of which are likely to be present in the
>>> store and thus linked from the directory, but in this scheme we will
>>> process only a small number of them and drop the rest on the floor to be
>>> read again in the next pass.  Given that even my fairly optimal
>>> implementation takes about 35 minutes to run on Hydra, I'd prefer to
>>> avoid multiplying that by a non-trivial factor.
>>
>> Sure, though it=E2=80=99s not obvious to me how much of a difference it =
makes;
>> my guess is that processing in large chunks is already a win, but we=E2=
=80=99d
>> have to measure.
>
> I agree, it would surely be a win.  Given that it currently takes on the
> order of a day to run this phase on Hydra, if your proposed method takes
> 2 hours, that would be a huge win, but still not good, IMO.  Even 35
> minutes is slower than I'd like.

Of course.

I did some measurements with the attached program on chapters, which is
a Xen VM with spinning disks underneath, similar to hydra.gnu.org.  It
has 600k entries in /gnu/store/.links.

Here=E2=80=99s a comparison of the =E2=80=9Coptimal=E2=80=9D mode (bulk sta=
ts after we=E2=80=99ve
fetched all the dirents) vs. the =E2=80=9Csemi-interleaved=E2=80=9D mode (d=
oing bulk
stats every 100,000 dirents):

--8<---------------cut here---------------start------------->8---
ludo@guix:~$ gcc -std=3Dgnu99 -Wall links-traversal.c  -DMODE=3D3
ludo@guix:~$ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
ludo@guix:~$ time ./a.out
603858 dir_entries, 157 seconds
stat took 1 seconds

real    2m38.508s
user    0m0.324s
sys     0m1.824s
ludo@guix:~$ gcc -std=3Dgnu99 -Wall links-traversal.c  -DMODE=3D2
ludo@guix:~$ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
ludo@guix:~$ time ./a.out=20
3852 dir_entries, 172 seconds (including stat)

real    2m51.827s
user    0m0.312s
sys     0m1.808s
--8<---------------cut here---------------end--------------->8---

Semi-interleaved is ~12% slower here (not sure how reproducible that is
though).

>>> Why not just use GNU sort?  It already exists, and does exactly what we
>>> need.
>>
>> Does =E2=80=98sort=E2=80=99 manage to avoid reading whole files in memor=
y?
>
> Yes, it does.  I monitored the 'sort' process when I first ran my
> optimized pipeline.  It created about 10 files in /tmp, approximately 70
> megabytes each as I recall, and then read them all concurrently while
> writing the sorted output.
>
> My guess is that it reads a manageable chunk of the input, sorts it in
> memory, and writes it to a temporary file.  I guess it repeats this
> process, writing multiple temporary files, until the entire input is
> consumed, and then reads all of those temporary files, merging them
> together into the output stream.

OK.  That seems to be that the comment above =E2=80=98sortlines=E2=80=99 in=
 sort.c
describes.

>>> If you object to using an external program for some reason, I would
>>> prefer to re-implement a similar algorithm in the daemon.
>>
>> Yeah, I=E2=80=99d rather avoid serializing the list of file names/inode =
number
>> pairs just to invoke =E2=80=98sort=E2=80=99 on that.
>
> Sure, I agree that it would be better to avoid that, but IMO not at the
> cost of using O(N) memory instead of O(1) memory, nor at the cost of
> multiplying the amount of disk I/O by a non-trivial factor.

Understood.

sort.c in Coreutils is very big, and we surely don=E2=80=99t want to duplic=
ate
all that.  Yet, I=E2=80=99d rather not shell out to =E2=80=98sort=E2=80=99.

Do you know how many entries are in .links on hydra.gnu.org?  If it
performs comparably to chapters, the timings suggests it should have
around 10.5M entries.

Thanks!

Ludo=E2=80=99.


--=-=-=
Content-Type: text/plain
Content-Disposition: inline; filename=links-traversal.c
Content-Description: the code

#include <unistd.h>
#include <dirent.h>
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>
#include <string.h>
#include <sys/stat.h>
#include <assert.h>

#define STAT_INTERLEAVED 1
#define STAT_SEMI_INTERLEAVED 2
#define STAT_OPTIMAL 3

struct entry
{
  char *name;
  ino_t inode;
};

#define MAX_ENTRIES 1000000
static struct entry dir_entries[MAX_ENTRIES];

int
main ()
{
  struct timeval start, end;

  /* For useful timings, do:
     sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'  */
  gettimeofday (&start, NULL);
  DIR *links = opendir ("/gnu/store/.links");

  size_t count = 0;

#if MODE != STAT_INTERLEAVED
  void sort_entries (void)
  {
    int entry_lower (const void *a, const void *b)
    {
      return ((struct entry *)a)->inode < ((struct entry *)b)->inode;
    }

    qsort (dir_entries, count, sizeof (struct entry),
	   entry_lower);
  }
#endif

  void stat_entries (void)
  {
    for (size_t i = 0; i < count; i++)
      {
	struct stat st;
	lstat (dir_entries[i].name, &st);
      }
  }

  for (struct dirent *entry = readdir (links);
       entry != NULL;
       entry = readdir (links))
    {
      assert (count < MAX_ENTRIES);
      dir_entries[count].name = strdup (entry->d_name);
      dir_entries[count].inode = entry->d_ino;
#if MODE == STAT_INTERLEAVED
      struct stat st;
      lstat (entry->d_name, &st);
#endif

#if MODE == STAT_SEMI_INTERLEAVED
      if (count++ >= 100000)
	{
	  sort_entries ();
	  stat_entries ();
	  count = 0;
	}
#else
      count++;
#endif
    }

#if MODE == STAT_SEMI_INTERLEAVED
  sort_entries ();
  stat_entries ();
#endif

  gettimeofday (&end, NULL);
  printf ("%zi dir_entries, %zi seconds"
#if MODE != STAT_OPTIMAL
	  " (including stat)"
#endif
	  "\n", count,
	  end.tv_sec - start.tv_sec);

#if MODE == STAT_OPTIMAL
  sort_entries ();
  gettimeofday (&start, NULL);
  stat_entries ();
  gettimeofday (&end, NULL);

  printf ("stat took %zi seconds\n", end.tv_sec - start.tv_sec);
#endif

  return EXIT_SUCCESS;
}

--=-=-=--

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: Mark H Weaver <mhw@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Tue, 13 Dec 2016 04:10:02 +0000
Resent-Message-ID: <handler.24937.B24937.148160219025000 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148160219025000
          (code B ref 24937); Tue, 13 Dec 2016 04:10:02 +0000
Received: (at 24937) by debbugs.gnu.org; 13 Dec 2016 04:09:50 +0000
Received: from localhost ([127.0.0.1]:39986 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cGePV-0006VA-OU
	for submit <at> debbugs.gnu.org; Mon, 12 Dec 2016 23:09:49 -0500
Received: from world.peace.net ([50.252.239.5]:51363)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1cGePU-0006Uv-8Z
 for 24937 <at> debbugs.gnu.org; Mon, 12 Dec 2016 23:09:48 -0500
Received: from pool-72-93-37-34.bstnma.east.verizon.net ([72.93.37.34]
 helo=jojen)
 by world.peace.net with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <mhw@HIDDEN>)
 id 1cGePO-0003bl-Jn; Mon, 12 Dec 2016 23:09:42 -0500
From: Mark H Weaver <mhw@HIDDEN>
In-Reply-To: <87d1gwvgu0.fsf@HIDDEN>
References: <87d1gwvgu0.fsf@HIDDEN> <87wpg7ffbm.fsf@HIDDEN>
 <87lgvm4lzu.fsf@HIDDEN> <87twaaa6j9.fsf@HIDDEN>
 <87twaa2vjx.fsf@HIDDEN> <87lgvm9sgq.fsf@HIDDEN>
Date: Mon, 12 Dec 2016 23:09:30 -0500
Message-ID: <8737hs1nd1.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: 0.0 (/)

Do as you wish.  I don't have time to continue discussing this.

     Mark

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: Mark H Weaver <mhw@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Tue, 13 Dec 2016 12:49:02 +0000
Resent-Message-ID: <handler.24937.B24937.148163332012744 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148163332012744
          (code B ref 24937); Tue, 13 Dec 2016 12:49:02 +0000
Received: (at 24937) by debbugs.gnu.org; 13 Dec 2016 12:48:40 +0000
Received: from localhost ([127.0.0.1]:40198 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cGmVb-0003JT-Ut
	for submit <at> debbugs.gnu.org; Tue, 13 Dec 2016 07:48:40 -0500
Received: from world.peace.net ([50.252.239.5]:53464)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1cGmVa-0003JG-GU
 for 24937 <at> debbugs.gnu.org; Tue, 13 Dec 2016 07:48:38 -0500
Received: from pool-72-93-37-34.bstnma.east.verizon.net ([72.93.37.34]
 helo=jojen)
 by world.peace.net with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <mhw@HIDDEN>)
 id 1cGmVU-0005xj-0E; Tue, 13 Dec 2016 07:48:32 -0500
From: Mark H Weaver <mhw@HIDDEN>
In-Reply-To: <87d1gwvgu0.fsf@HIDDEN> ("Ludovic
 \=\?utf-8\?Q\?Court\=C3\=A8s\=22'\?\=
 \=\?utf-8\?Q\?s\?\= message of "Tue, 13 Dec 2016 01:00:07 +0100")
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
 <87twaaa6j9.fsf@HIDDEN> <87twaa2vjx.fsf@HIDDEN>
 <87lgvm9sgq.fsf@HIDDEN> <87d1gwvgu0.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
Date: Tue, 13 Dec 2016 07:48:19 -0500
Message-ID: <87wpf4yoz0.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: 0.0 (/)

ludo@HIDDEN (Ludovic Court=C3=A8s) writes:

> I did some measurements with the attached program on chapters, which is
> a Xen VM with spinning disks underneath, similar to hydra.gnu.org.  It
> has 600k entries in /gnu/store/.links.

I just want to point out that 600k inodes use 150 megabytes of disk
space on ext4, which is small enough to fit in the cache, so the disk
I/O will not be multiplied for such a small test case.

> Here=E2=80=99s a comparison of the =E2=80=9Coptimal=E2=80=9D mode (bulk s=
tats after we=E2=80=99ve
> fetched all the dirents) vs. the =E2=80=9Csemi-interleaved=E2=80=9D mode =
(doing bulk
> stats every 100,000 dirents):
>
> ludo@guix:~$ gcc -std=3Dgnu99 -Wall links-traversal.c  -DMODE=3D3
> ludo@guix:~$ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
> ludo@guix:~$ time ./a.out
> 603858 dir_entries, 157 seconds
> stat took 1 seconds
>
> real    2m38.508s
> user    0m0.324s
> sys     0m1.824s
> ludo@guix:~$ gcc -std=3Dgnu99 -Wall links-traversal.c  -DMODE=3D2
> ludo@guix:~$ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
> ludo@guix:~$ time ./a.out=20
> 3852 dir_entries, 172 seconds (including stat)
>
> real    2m51.827s
> user    0m0.312s
> sys     0m1.808s
>
> Semi-interleaved is ~12% slower here (not sure how reproducible that is
> though).

This directory you're testing on is more than an order of magnitude
smaller than Hydra's when it's full.  Unlike in your test above, all of
the inodes in Hydra's store won't fit in the cache.

In my opinion, the reason Hydra performs so poorly is because efficiency
and scalability are apparently very low priorities in the design of the
software running on it.  Unfortunately, I feel that my advice in this
area is discarded more often than not.

>>>> Why not just use GNU sort?  It already exists, and does exactly what we
>>>> need.
>>>
>>> Does =E2=80=98sort=E2=80=99 manage to avoid reading whole files in memo=
ry?
>>
>> Yes, it does.  I monitored the 'sort' process when I first ran my
>> optimized pipeline.  It created about 10 files in /tmp, approximately 70
>> megabytes each as I recall, and then read them all concurrently while
>> writing the sorted output.
>>
>> My guess is that it reads a manageable chunk of the input, sorts it in
>> memory, and writes it to a temporary file.  I guess it repeats this
>> process, writing multiple temporary files, until the entire input is
>> consumed, and then reads all of those temporary files, merging them
>> together into the output stream.
>
> OK.  That seems to be that the comment above =E2=80=98sortlines=E2=80=99 =
in sort.c
> describes.

Also, see <https://en.wikipedia.org/wiki/External_sorting>.  This is a
well-studied problem with a long history.

>>>> If you object to using an external program for some reason, I would
>>>> prefer to re-implement a similar algorithm in the daemon.
>>>
>>> Yeah, I=E2=80=99d rather avoid serializing the list of file names/inode=
 number
>>> pairs just to invoke =E2=80=98sort=E2=80=99 on that.

I'm fairly sure that the overhead of serializing the file names and
inode numbers is *far* less than the overhead you would add by iterating
over the inodes in multiple passes.

>> Sure, I agree that it would be better to avoid that, but IMO not at the
>> cost of using O(N) memory instead of O(1) memory, nor at the cost of
>> multiplying the amount of disk I/O by a non-trivial factor.
>
> Understood.
>
> sort.c in Coreutils is very big, and we surely don=E2=80=99t want to dupl=
icate
> all that.  Yet, I=E2=80=99d rather not shell out to =E2=80=98sort=E2=80=
=99.

The "shell" would not be involved here at all, just the "sort" program.
I guess you dislike launching external processes?  Can you explain why?

Guix-daemon launches external processes for building derivations, so why
is using one for garbage collection a problem?  Emacs, a program that
you cite in your talks as having many qualities that we seek to emulate,
does not shy away from using external programs.

> Do you know how many entries are in .links on hydra.gnu.org?

"df -i /gnu" indicates that it currently has about 5.5M inodes, but
that's with only 29% of the disk in use.  A few days ago, when the disk
was full, assuming that the average file size is the same, it may have
had closer to 5.5M / 0.29 ~=3D 19M inodes, which is over 30 times as many
as used in your measurements above.  On ext4, which uses 256-byte
inodes, that's about 5 gigabytes of inodes.

      Mark

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Tue, 13 Dec 2016 17:03:01 +0000
Resent-Message-ID: <handler.24937.B24937.14816485604771 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: Mark H Weaver <mhw@HIDDEN>
Cc: Ricardo Wurmus <rekado@HIDDEN>, 24937 <at> debbugs.gnu.org, Roel Janssen <roel@HIDDEN>
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.14816485604771
          (code B ref 24937); Tue, 13 Dec 2016 17:03:01 +0000
Received: (at 24937) by debbugs.gnu.org; 13 Dec 2016 17:02:40 +0000
Received: from localhost ([127.0.0.1]:40938 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cGqTP-0001Es-KB
	for submit <at> debbugs.gnu.org; Tue, 13 Dec 2016 12:02:39 -0500
Received: from eggs.gnu.org ([208.118.235.92]:50638)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <ludo@HIDDEN>) id 1cGqTO-0001Eg-7Q
 for 24937 <at> debbugs.gnu.org; Tue, 13 Dec 2016 12:02:38 -0500
Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71)
 (envelope-from <ludo@HIDDEN>) id 1cGqTE-0006Q7-Pb
 for 24937 <at> debbugs.gnu.org; Tue, 13 Dec 2016 12:02:32 -0500
X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org
X-Spam-Level: 
X-Spam-Status: No, score=-2.3 required=5.0 tests=BAYES_50,RP_MATCHES_RCVD
 autolearn=disabled version=3.3.2
Received: from fencepost.gnu.org ([2001:4830:134:3::e]:47565)
 by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from <ludo@HIDDEN>)
 id 1cGqT7-0006OQ-Rp; Tue, 13 Dec 2016 12:02:21 -0500
Received: from 212-91-237-188.dynamic.dns-net.de ([212.91.237.188]:54652
 helo=pluto)
 by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256)
 (Exim 4.82) (envelope-from <ludo@HIDDEN>)
 id 1cGqT6-0000aA-VC; Tue, 13 Dec 2016 12:02:21 -0500
From: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
 <87twaaa6j9.fsf@HIDDEN> <87twaa2vjx.fsf@HIDDEN>
 <87lgvm9sgq.fsf@HIDDEN> <87d1gwvgu0.fsf@HIDDEN>
 <87wpf4yoz0.fsf@HIDDEN>
X-URL: http://www.fdn.fr/~lcourtes/
X-Revolutionary-Date: 23 Frimaire an 225 de la =?UTF-8?Q?R=C3=A9volution?=
X-PGP-Key-ID: 0x090B11993D9AEBB5
X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc
X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4  0CFB 090B 1199 3D9A EBB5
X-OS: x86_64-unknown-linux-gnu
Date: Tue, 13 Dec 2016 18:02:18 +0100
In-Reply-To: <87wpf4yoz0.fsf@HIDDEN> (Mark H. Weaver's message of "Tue, 13
 Dec 2016 07:48:19 -0500")
Message-ID: <87fulrsqxx.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic]
X-Received-From: 2001:4830:134:3::e
X-Spam-Score: -8.1 (--------)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -8.1 (--------)

Hello Mark,

Mark H Weaver <mhw@HIDDEN> skribis:

> ludo@HIDDEN (Ludovic Court=C3=A8s) writes:
>
>> I did some measurements with the attached program on chapters, which is
>> a Xen VM with spinning disks underneath, similar to hydra.gnu.org.  It
>> has 600k entries in /gnu/store/.links.
>
> I just want to point out that 600k inodes use 150 megabytes of disk
> space on ext4, which is small enough to fit in the cache, so the disk
> I/O will not be multiplied for such a small test case.

Right.  That=E2=80=99s the only spinning-disk machine I could access without
problem.  :-/

Ricardo, Roel: would you be able to run that links-traversal.c from
<https://debbugs.gnu.org/cgi/bugreport.cgi?filename=3Dlinks-traversal.c;bug=
=3D24937;msg=3D25;att=3D1>
on a machine with a big store, as described at
<https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D24937#25>?

>> Semi-interleaved is ~12% slower here (not sure how reproducible that is
>> though).
>
> This directory you're testing on is more than an order of magnitude
> smaller than Hydra's when it's full.  Unlike in your test above, all of
> the inodes in Hydra's store won't fit in the cache.

Good point.  I=E2=80=99m trying my best to get performance figures, there=
=E2=80=99s no
doubt we could do better!

> In my opinion, the reason Hydra performs so poorly is because efficiency
> and scalability are apparently very low priorities in the design of the
> software running on it.  Unfortunately, I feel that my advice in this
> area is discarded more often than not.

Well, as you know, I=E2=80=99m currently traveling, yet I take the time to
answer your email at night; I think this should suggest that far from
discarding your advice, I very much value it.

I=E2=80=99m a maintainer though, so I=E2=80=99m trying to understand the pr=
oblem better.
It=E2=80=99s not just about finding the =E2=80=9Coptimal=E2=80=9D solution,=
 but also about
finding a tradeoff between the benefits and the maintainability costs.

>> sort.c in Coreutils is very big, and we surely don=E2=80=99t want to dup=
licate
>> all that.  Yet, I=E2=80=99d rather not shell out to =E2=80=98sort=E2=80=
=99.
>
> The "shell" would not be involved here at all, just the "sort" program.
> I guess you dislike launching external processes?  Can you explain why?

I find that passing strings around among programs is inelegant
(subjective), but I don=E2=80=99t think you=E2=80=99re really looking to ar=
gue about
that, are you?  :-)

It remains that, if invoking =E2=80=98sort=E2=80=99 appears to be preferabl=
e *both* from
performance and maintenance viewpoints, then it=E2=80=99s a good choice.  T=
hat
may be the case, but again, I prefer to have figures to back that.

>> Do you know how many entries are in .links on hydra.gnu.org?
>
> "df -i /gnu" indicates that it currently has about 5.5M inodes, but
> that's with only 29% of the disk in use.  A few days ago, when the disk
> was full, assuming that the average file size is the same, it may have
> had closer to 5.5M / 0.29 ~=3D 19M inodes,

OK, good to know.

Thanks!

Ludo=E2=80=99.

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: Ricardo Wurmus <ricardo.wurmus@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Tue, 13 Dec 2016 17:20:01 +0000
Resent-Message-ID: <handler.24937.B24937.14816495686219 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: Ludovic =?UTF-8?Q?Court=C3=A8s?= <ludo@HIDDEN>
Cc: Mark H Weaver <mhw@HIDDEN>, 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.14816495686219
          (code B ref 24937); Tue, 13 Dec 2016 17:20:01 +0000
Received: (at 24937) by debbugs.gnu.org; 13 Dec 2016 17:19:28 +0000
Received: from localhost ([127.0.0.1]:40959 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cGqjg-0001cF-Ge
	for submit <at> debbugs.gnu.org; Tue, 13 Dec 2016 12:19:28 -0500
Received: from sinope.bbbm.mdc-berlin.de ([141.80.25.23]:42371)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <Ricardo.Wurmus@HIDDEN>) id 1cGqjf-0001c6-8A
 for 24937 <at> debbugs.gnu.org; Tue, 13 Dec 2016 12:19:28 -0500
Received: from localhost (localhost [127.0.0.1])
 by sinope.bbbm.mdc-berlin.de (Postfix) with ESMTP id F2CF0A894A;
 Tue, 13 Dec 2016 18:19:25 +0100 (CET)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=mdc-berlin.de; h=
 content-transfer-encoding:content-type:content-type:mime-version
 :message-id:date:date:in-reply-to:subject:subject:from:from
 :user-agent:references:received:received:received; s=mdc; t=
 1481649559; x=1483463960; bh=YMu6NtX1ZnmlGcwmhJ2Cw4MUCmkE/LX0JLt
 rrnfnVCA=; b=LMdVFxVUKLaAX98PEKDm5bptcC18Qbdd8k4Rs4wyaQ1oQJOVnvS
 RhedB4HAWFnceREd0dzTi66UAe++MtIBBYgvqBLV0EL1hSHwQBfWsO6quk0H3V3u
 C8uEqu7lyTzNE7tXjB4fvZJXzZSr43Sqt0naO2L1cYp210tGpG8BqlUI=
X-Virus-Scanned: amavisd-new at mdc-berlin.de
Received: from sinope.bbbm.mdc-berlin.de ([127.0.0.1])
 by localhost (sinope.bbbm.mdc-berlin.de [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id USUQSi6KjIHv; Tue, 13 Dec 2016 18:19:19 +0100 (CET)
Received: from HTCAONE.mdc-berlin.net (puck.citx.mdc-berlin.de [141.80.36.101])
 (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits))
 (No client certificate requested)
 by sinope.bbbm.mdc-berlin.de (Postfix) with ESMTPS;
 Tue, 13 Dec 2016 18:19:19 +0100 (CET)
Received: from localhost (141.80.180.135) by HTCAONE.mdc-berlin.net
 (141.80.180.125) with Microsoft SMTP Server (TLS) id 14.3.319.2; Tue, 13 Dec
 2016 18:19:18 +0100
References: <87wpg7ffbm.fsf@HIDDEN> <87lgvm4lzu.fsf@HIDDEN>
 <87twaaa6j9.fsf@HIDDEN> <87twaa2vjx.fsf@HIDDEN>
 <87lgvm9sgq.fsf@HIDDEN> <87d1gwvgu0.fsf@HIDDEN>
 <87wpf4yoz0.fsf@HIDDEN> <87fulrsqxx.fsf@HIDDEN>
User-agent: mu4e 0.9.16; emacs 25.1.1
From: Ricardo Wurmus <ricardo.wurmus@HIDDEN>
In-Reply-To: <87fulrsqxx.fsf@HIDDEN>
Date: Tue, 13 Dec 2016 18:18:57 +0100
Message-ID: <87vaunbvcu.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
X-Originating-IP: [141.80.180.135]
X-TM-AS-Product-Ver: SMEX-11.0.0.4283-8.000.1202-22758.006
X-TM-AS-Result: No--0.114700-0.000000-31
X-TM-AS-MatchedID: 150567-703786-703731-139010-706249-139705-707904-861157-7
 03385-105700-711664-701202-710480-701719-709009-702942-701604-700862-701296
 -700756-148004-148133-42000-42003
X-TM-AS-User-Approved-Sender: Yes
X-TM-AS-User-Blocked-Sender: No
X-Spam-Score: -8.1 (--------)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -8.1 (--------)


Ludovic Courtès <ludo@HIDDEN> writes:

> Ricardo, Roel: would you be able to run that links-traversal.c from
> <https://debbugs.gnu.org/cgi/bugreport.cgi?filename=links-traversal.c;bug=24937;msg=25;att=1>
> on a machine with a big store, as described at
> <https://debbugs.gnu.org/cgi/bugreport.cgi?bug=24937#25>?

I just ran this on my workstation in the office where I regularly build
packages.  Here’s the output of “df -i /gnu”

  Filesystem               Inodes   IUsed   IFree IUse% Mounted on
  /dev/mapper/fedora-root 3301376 1098852 2202524   34% /

Probably not large enough to derive conclusions about hydra’s behaviour.

[I can’t run it on the shared store at the MDC because NFS performance is
too poor.  I recently ran “guix gc --optimize” to dedupe the shared
store (post-build deduplication is disabled since a few weeks) and it’s
at 3,197,489 used inodes.]

Here are the results of running the link-traversal code on my
workstation:

--8<---------------cut here---------------start------------->8---
rwurmus in ~: gcc -std=gnu99 -Wall links-traversal.c  -DMODE=3
rwurmus in ~: sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
rwurmus in ~: time ./a.out 
412825 dir_entries, 107 seconds
stat took 0 seconds

real	1m47.264s
user	0m0.214s
sys	0m1.314s

rwurmus in ~: gcc -std=gnu99 -Wall links-traversal.c  -DMODE=2
rwurmus in ~: sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches'
rwurmus in ~: time ./a.out 
12821 dir_entries, 107 seconds (including stat)

real	1m46.475s
user	0m0.201s
sys	0m1.309s
--8<---------------cut here---------------end--------------->8---


-- 
Ricardo

Message sent to bug-guix@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#24937: "deleting unused links" GC phase is too slow
Resent-From: Mark H Weaver <mhw@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-guix@HIDDEN
Resent-Date: Thu, 15 Dec 2016 01:20:02 +0000
Resent-Message-ID: <handler.24937.B24937.148176478030866 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 24937
X-GNU-PR-Package: guix
X-GNU-PR-Keywords: 
To: ludo@HIDDEN (Ludovic =?UTF-8?Q?Court=C3=A8s?=)
Cc: 24937 <at> debbugs.gnu.org
Received: via spool by 24937-submit <at> debbugs.gnu.org id=B24937.148176478030866
          (code B ref 24937); Thu, 15 Dec 2016 01:20:02 +0000
Received: (at 24937) by debbugs.gnu.org; 15 Dec 2016 01:19:40 +0000
Received: from localhost ([127.0.0.1]:42229 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1cHKhw-00081m-F7
	for submit <at> debbugs.gnu.org; Wed, 14 Dec 2016 20:19:40 -0500
Received: from world.peace.net ([50.252.239.5]:60268)
 by debbugs.gnu.org with esmtp (Exim 4.84_2)
 (envelope-from <mhw@HIDDEN>) id 1cHKhu-00081M-R3
 for 24937 <at> debbugs.gnu.org; Wed, 14 Dec 2016 20:19:39 -0500
Received: from pool-72-93-37-34.bstnma.east.verizon.net ([72.93.37.34]
 helo=jojen)
 by world.peace.net with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <mhw@HIDDEN>)
 id 1cHKho-0001nB-Vm; Wed, 14 Dec 2016 20:19:33 -0500
From: Mark H Weaver <mhw@HIDDEN>
References: <87d1gwvgu0.fsf@HIDDEN> <87wpg7ffbm.fsf@HIDDEN>
 <87lgvm4lzu.fsf@HIDDEN> <87twaaa6j9.fsf@HIDDEN>
 <87twaa2vjx.fsf@HIDDEN> <87lgvm9sgq.fsf@HIDDEN>
 <8737hs1nd1.fsf@HIDDEN>
Date: Wed, 14 Dec 2016 20:19:21 -0500
In-Reply-To: <8737hs1nd1.fsf@HIDDEN> (Mark H. Weaver's message of "Mon, 12
 Dec 2016 23:09:30 -0500")
Message-ID: <87h9663s6e.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.1 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: 0.0 (/)

I apologize for losing my patience earlier.

     Mark

Last modified: Mon, 25 Nov 2019 12:00:02 UTC

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997 nCipher Corporation Ltd, 1994-97 Ian Jackson.