From unknown Tue Sep 23 19:26:05 2025 X-Loop: help-debbugs@gnu.org Subject: bug#63412: Topological sorting in cuirass Resent-From: Andreas Enge Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Wed, 10 May 2023 10:07:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 63412 X-GNU-PR-Package: guix X-GNU-PR-Keywords: To: 63412@debbugs.gnu.org X-Debbugs-Original-To: bug-guix@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.168371321210136 (code B ref -1); Wed, 10 May 2023 10:07:02 +0000 Received: (at submit) by debbugs.gnu.org; 10 May 2023 10:06:52 +0000 Received: from localhost ([127.0.0.1]:45276 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pwgih-0002dP-PW for submit@debbugs.gnu.org; Wed, 10 May 2023 06:06:52 -0400 Received: from lists.gnu.org ([209.51.188.17]:34622) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pwgif-0002dH-Is for submit@debbugs.gnu.org; Wed, 10 May 2023 06:06:50 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pwgid-0002c0-Nf for bug-guix@gnu.org; Wed, 10 May 2023 06:06:47 -0400 Received: from hera.aquilenet.fr ([185.233.100.1]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pwgiW-0003XH-Hx for bug-guix@gnu.org; Wed, 10 May 2023 06:06:42 -0400 Received: from localhost (localhost [127.0.0.1]) by hera.aquilenet.fr (Postfix) with ESMTP id 03CD6354; Wed, 10 May 2023 12:06:32 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at hera.aquilenet.fr Received: from hera.aquilenet.fr ([127.0.0.1]) by localhost (hera.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7Ed9LQSqCVIA; Wed, 10 May 2023 12:06:30 +0200 (CEST) Received: from jurong (unknown [IPv6:2001:861:c4:f2f0::c64]) by hera.aquilenet.fr (Postfix) with ESMTPSA id 44FE45B; Wed, 10 May 2023 12:06:30 +0200 (CEST) Date: Wed, 10 May 2023 12:06:28 +0200 From: Andreas Enge Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Received-SPF: pass client-ip=185.233.100.1; envelope-from=andreas@enge.fr; helo=hera.aquilenet.fr X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) This is a wishlist bug, but it is important for architectures where we are currently short on build power, and where this issue can stall builds and waste an arbitrary amount of build power. Cuirass should sort builds and only offload derivations for which all inputs are available. In my current understanding, cuirass offloads arbitrary derivations, and the machine to which they are offloaded then starts building recursively all inputs. If this is true, then it is possible that at some point in time, all build slots are taken by the same package built as many times as there are machines; I have seen something like this when working on core-updates, where several machines were building the main gcc compiler at the same time. At worse, if cuirass asks every machine to build a leaf package, this may result in a simultaneous full bootstrap on all of them. The situation becomes worse when the package in question fails. Then as I understand it, each machine may receive a request to build something depending on the failing package and try the failing build and thus waste build power that will not be available to build other packages successfully. Solving this problem may also make reports of build failures more accurate and legible. For instance, doxygen currently fails to build on aarch64: https://ci.guix.gnu.org/build/969427/details and is reported as "Failed", and not as "Failed (dependency)". However, looking at the build log https://ci.guix.gnu.org/build/969427/log/raw shows this: ... building path(s) `/gnu/store/p5vqrwywz053r1vkiyw54dp9gj7vw9xd-ninja-1.11.1' ... builder for `/gnu/store/0zf7fqndzf2k595r4s6wblmpccdwr3nx-ninja-1.11.1.drv' failed with exit code 1 @ build-failed /gnu/store/0zf7fqndzf2k595r4s6wblmpccdwr3nx-ninja-1.11.1.drv - 1 builder for `/gnu/store/0zf7fqndzf2k595r4s6wblmpccdwr3nx-ninja-1.11.1.drv' failed with exit code 1 cannot build derivation `/gnu/store/hlscqram59id51hxg0fj15041v52h1kw-meson-1.1.0.drv': 1 dependencies couldn't be built cannot build derivation `/gnu/store/w8qxkrwpffd9qs5w1jggy1yi27ycm0xr-jsoncpp-1.9.5.drv': 2 dependencies couldn't be built cannot build derivation `/gnu/store/mss4yv015cil1vnjnglq506m83b7n3dy-cmake-bootstrap-3.24.2.drv': 1 dependencies couldn't be built cannot build derivation `/gnu/store/w0irp6xn30nlmpizhcbjnvhqmsba41jn-cmake-minimal-3.24.2.drv': 2 dependencies couldn't be built cannot build derivation `/gnu/store/rqk2rbnpjpcnqswz8hqari1rnw6r8v1m-doxygen-1.9.5.drv': 1 dependencies couldn't be built So it is indeed a different package that fails (and the last few lines give a list of dependencies between ninja and doxygen, each of which may or may not fail once ninja is fixed). Notice that this could be solved without a topological sorting of the dependency graph: It would be enough to keep an array deriv in which deriv[i] contains a list of derivations requiring i more inputs to be built, together with the list of inputs; elements in deriv[0] are ready to be sent to a build machine, and upon completion of a build, all derivations depending on it should be moved from deriv[i] to deriv[i-1] if the input has been built successfully, or marked as "Failed (dependency)" if the input has failed. (But this could be expensive, and may require appropriate data structures.) Alternatively, build jobs could be sorted topologically and then be kept in a list; then before sending out a job, all its inputs have been tried to be built; the job should then be sent if all inputs are available, or be marked as "Failed (dependency)" if any of them has failed. Andreas From unknown Tue Sep 23 19:26:05 2025 X-Loop: help-debbugs@gnu.org Subject: bug#63412: Topological sorting in cuirass Resent-From: "Dr. Arne Babenhauserheide" Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Wed, 10 May 2023 14:03:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 63412 X-GNU-PR-Package: guix X-GNU-PR-Keywords: To: Andreas Enge Cc: 63412@debbugs.gnu.org X-Debbugs-Original-Cc: 63412@debbugs.gnu.org, bug-guix@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.168372737427537 (code B ref -1); Wed, 10 May 2023 14:03:01 +0000 Received: (at submit) by debbugs.gnu.org; 10 May 2023 14:02:54 +0000 Received: from localhost ([127.0.0.1]:48525 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pwkP7-0007A5-LE for submit@debbugs.gnu.org; Wed, 10 May 2023 10:02:54 -0400 Received: from lists.gnu.org ([209.51.188.17]:33568) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pwkP6-00079y-I7 for submit@debbugs.gnu.org; Wed, 10 May 2023 10:02:52 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pwkP6-0004xd-CW for bug-guix@gnu.org; Wed, 10 May 2023 10:02:52 -0400 Received: from mout.web.de ([212.227.17.12]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pwkP4-0004zD-Jn for bug-guix@gnu.org; Wed, 10 May 2023 10:02:52 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=s29768273; t=1683727359; i=arne_bab@web.de; bh=ABqbhTGMSq6elPoT0qDNqcRs+SkA6Zy/beUo966ao68=; h=X-UI-Sender-Class:References:From:To:Cc:Subject:Date:In-reply-to; b=QLpuVc7m7iGxBtbDRFBa94sTTD6f/BAYbbqOg/RMsXkoCmb/vlEVzzjuGjTIt7pHI VFUTzR9hEbXartZ0b/8cewPlv+c1yXyb3KLgaDF+MLk3mHdpdXonxa+71ZcmPaixOQ cjVQxd6lZ2jux9O5zttfzwJJSdtwfbyahRG4D0RiA0vWxEgxBQR5VyNhcTaW5gtrC4 1dAkTigeCRX9UcIpjxDRs+nyL5//5+VoQiXiWSjj3o9GI8ZXPLLkG/HZ4Sm5ROEfkk 3u4A/3QIm+MfPlIyiXEcjViSXPeJ0GQuKzINI9UhkycbkAzuLK9JyiHmtGE2H/xeNm u+KqcuExOAR1A== X-UI-Sender-Class: 814a7b36-bfc1-4dae-8640-3722d8ec6cd6 Received: from fluss ([84.165.25.222]) by smtp.web.de (mrweb106 [213.165.67.124]) with ESMTPSA (Nemesis) id 1M604f-1ppLTI33H9-007WK7; Wed, 10 May 2023 16:02:39 +0200 References: User-agent: mu4e 1.10.2; emacs 29.0.90 From: "Dr. Arne Babenhauserheide" Date: Wed, 10 May 2023 15:59:45 +0200 In-reply-to: Message-ID: <87r0ro9tdt.fsf@web.de> MIME-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" X-Provags-ID: V03:K1:ZJEeCAxmsP+NdY2em04BD+xEYJNTK6L+4Da/PpXEbctsd2PhbRi K5hSpQbARETN1jehqZ6fF9O9lulMzjrbwOUVPAZy/sAIuRQKHTolarlcxQUWCLgQkezZwDR DQeidlSSp1Z/iKrqn14qkNlLxFYSXjijkpA/NZ50X9LsLJ+ktoONiC6TX2iY7U+86OioME8 n9PT8GIO54vaKdB4Wq6RA== X-Spam-Flag: NO UI-OutboundReport: notjunk:1;M01:P0:Lrz0rLQaqN0=;rwx3WkeOa2yvygJZARG0KFcMOE4 Z3Y3JsJlDQaqmBUgX5Hx5ENtCZB+1DUuTxdRmQJtrxsYqO4s2+6nRZbkUIy6QrgI5rYuZDQ3Y Vzq2QfAySzpfKqnsJkWxsKpHZaVfiSku0UNpfUWl42szc8nYDUOUDg3NkBdFsGCg8bG5BDMXA rvRS0k0gsiKSxSqmES2BE7np7TPxH1lHXAfc+a+bjBwDswdQtfmQ4Q+mWW3+2rXTbqWBpJpJ3 Y6KZiYBml4QHV5wV/FIjc5zL5ZdDVuk2KGGizBPYmuIuQWGC0ALd1rR2wp9GZp53d+Pot7Ao/ yBmx9BKZE2qFeF+zm+k0tAhIdeaYTPm0+cUXp+bSTS5VaQk9mtvFKxZ26bnaj2XeUZmoCGMzo Dt2EAb0xC2USUXfSctah9CSyJ2Xk2UnnUBdAt4o90zWX3h4J+gpplMI2kh9EFikXiN7iK40qN fjcQpJRsAya6ChUKu92l1P4JEWty6oZXaR56wbEpX3tL0MsRNqxpN9KyIu4HBZQA8ATGs1Tit 1K6GeqgPmHsjGo8q78Kkotvc5z+iBwzlH4bZNbsjawgR/rph2HDgaHVC2pXn+bZQO++lxPHjK Lgi7R/IEgArawSOqLLaLUzKFOo6Dzdn4fyRiR38RAJ2CbfVlegDiy7Bzm148EtASGs8cJuMp5 aCtmTxnDVU975ibR2EnUnBKr8pmN3JXL1jdOf0f8+8i03seTbFQmh4YrVLyA62xdLLJZ1zCJC PB3P+yMmFM1kkOttuwZ5rEN2NssY8OsNJygKKvj66KEjqwavS+EGzXCytoxrgnxX5KBo3KCFk Va6rkhSmH1SuDjLQxsxF0Y0loBHT14SmIO/+dtr6Sp4NvT3OflJD/LB2ZvmMGE6hLsiF3l17P GAuCVdkgnMlwfVebC95bEXRbzF9FXSg+OWLH77+oA0OwerLR4fwoeoLNYL3lLkmyJOEFGVrhZ DWk/Xw== Received-SPF: pass client-ip=212.227.17.12; envelope-from=arne_bab@web.de; helo=mout.web.de X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.4 (-) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.4 (--) --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Andreas Enge writes: > Cuirass should sort builds and only offload derivations for which all > inputs are available. ... > Alternatively, build jobs could be sorted topologically and then be kept > in a list; then before sending out a job, all its inputs have been tried > to be built; the job should then be sent if all inputs are available, or > be marked as "Failed (dependency)" if any of them has failed. If you want to try this out quickly, you could use code from the topological sorting SRFI I=E2=80=99m slowly finalizing: https://srfi.schemers.org/srfi-234/srfi-234.html For usage see: https://github.com/scheme-requests-for-implementation/srfi-2= 34/blob/main/srfi-234-test.scm Code: https://github.com/scheme-requests-for-implementation/srfi-234/blob/m= ain/srfi/234-impl.scm edgelist->graph should do the conversion from inputs per package to the input format. Best wishes, Arne =2D-=20 Unpolitisch sein hei=C3=9Ft politisch sein, ohne es zu merken. draketo.de --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQJEBAEBCAAuFiEE801qEjXQSQPNItXAE++NRSQDw+sFAmRbo/4QHGFybmVfYmFi QHdlYi5kZQAKCRAT741FJAPD61HYEAC0cngpr3CGwz0WIR08pCPoDJ4aqQZ5hLMJ NWCNS/UEa+svUUe8M3RTD0ULLu6bdPVIqapWxmU6eiCAWRR/Sw0yC//RwAHrrNEm HsWT9/yX44upkyG4jD1UI04FVo/4anOi87tcPVxoUl+07g3NTs4I682W/nv0WxDY 8OURhIwMe3eeHF7bSX9cLzx6QbfmUwP0Z6uwi7ZTyzOat8FuJNqLIF13WofMj3N3 osKQerCADYZrpWMeiFkHrBIFF2n0Bx61SwVrWkZJJt6CDf2lUQhjEOhZtPKRDCsW 8299sdPs6NY2bcsRAhi4I2ImFVhVdL15oFvk/Z0eYu180J1cPedvjgvxHKjnYGSH uvKWv6Yl8F7K1wNmkkV80OJwJfbbfYWE+YMoPAcMwBwCCfQh9HaErOF58tfoL18a W/xOZ1x80YC1zmdFS85FSzn6DCwK+OJXOUPiAgMwrpVWq6jKvEST17Lt40XTEZWG UM2vKd6anTMwdAYRjsioBDOHiV5EQCtK4gtCIjoodIu8UtZos1xW91GQ+jFYFFCy aia90PgwLKBDjQ8fWDFQ8GF2lo5CYGKk+dvXfc3SruzpRTJAunPT/X5utNcCjvV8 0NsOdFpdNE5u5C6snAwJQChGSI+5UDNw1rUI/oXEIniQaEuwB+wCiuYSeCsbN5+C WCVJqBjbK4jEBAEBCAAuFiEE3Si95tmHXKvOSosd3M8NswvBBUgFAmRbo/4QHGFy bmVfYmFiQHdlYi5kZQAKCRDczw2zC8EFSCYSA/9dFjzglwj8/z4++auf9c0iHIG6 ve33HOtv6FuZd8Uqs4lOZed7dpIjhXaIkPPApxtRwF3qacs7BbY0VZlx+V8+z0US fANOg45cha9eJJchXfQWWwussE/VePM5hY3I5gUZo6UaL0Pjrw4gEhJnHIhFxV0c mq+xD9Tiiac9roJsUw== =6oiM -----END PGP SIGNATURE----- --=-=-=-- From unknown Tue Sep 23 19:26:05 2025 X-Loop: help-debbugs@gnu.org Subject: bug#63412: Topological sorting in cuirass Resent-From: Ludovic =?UTF-8?Q?Court=C3=A8s?= Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Sun, 29 Oct 2023 17:03:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 63412 X-GNU-PR-Package: guix X-GNU-PR-Keywords: To: Andreas Enge Cc: 63412@debbugs.gnu.org Received: via spool by 63412-submit@debbugs.gnu.org id=B63412.1698598926472 (code B ref 63412); Sun, 29 Oct 2023 17:03:02 +0000 Received: (at 63412) by debbugs.gnu.org; 29 Oct 2023 17:02:06 +0000 Received: from localhost ([127.0.0.1]:43271 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qx9As-00007W-9h for submit@debbugs.gnu.org; Sun, 29 Oct 2023 13:02:06 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:44164) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1qx9Ao-00006t-60 for 63412@debbugs.gnu.org; Sun, 29 Oct 2023 13:02:04 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1qx9AB-0008Ek-C1; Sun, 29 Oct 2023 13:01:23 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-Version:Date:References:In-Reply-To:Subject:To: From; bh=RcMXtz0gXC9Q/I9/czPuwjPCxJCe6V1bjenF0BUlAos=; b=a/RuwpJbfRtQGFVVXHmc xY+LGw+02ja9N8wLsv6rDbK9kZiDs52dbO1sJlhUZywNuVcmdkTWWTFV/QJWl7hoVfNYccZnNJ84s ZW2MvH1ge+tpF1H6c1m/xilC5xEOzCNZk6iYdLMfTsSzM9WO/vk3zBLNV3jYjaVTDtCk/B613OEtk Ne5FYpduJNtlJ0HPIpRk7Y8MXH/Oupm0sddBFLhHKTtdk+3Q22E3a/4K3A0x9hz/HvN02xtejldy+ 6dMGocEWdAJ7WJGZs4wbM4hCW1D+7srp0BVSDamaGmibcDiLbP2E2Sc4/MpTAu3r919ffyuUJpoLM cgxQn5pieq5uRQ==; From: Ludovic =?UTF-8?Q?Court=C3=A8s?= In-Reply-To: (Andreas Enge's message of "Wed, 10 May 2023 12:06:28 +0200") References: Date: Sun, 29 Oct 2023 18:01:20 +0100 Message-ID: <87jzr5747z.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Hi, Andreas Enge skribis: > This is a wishlist bug, but it is important for architectures where we > are currently short on build power, and where this issue can stall builds > and waste an arbitrary amount of build power. > > Cuirass should sort builds and only offload derivations for which all > inputs are available. Cuirass has two build backends: talking to the build daemon, and using the ZeroMQ-based =E2=80=9Cremote worker=E2=80=9D protocol. In practice we = use the latter, which fixes scalability issues with the former. The worker protocol implements work stealing: workers periodically send messages to =E2=80=9Cremote server=E2=80=9D asking for work. Said server r= eplies with a derivation for one of the systems the worker supports; that derivation is chosen among the =E2=80=9Cbuilds=E2=80=9D whose dependencies have all be= en successfully built. And here=E2=80=99s the trick: the server is doing the right thing, but it h= as a partial view. Namely, the server sees =E2=80=9Cbuilds=E2=80=9D rather than =E2=80=9Cderivations=E2=80=9D. =E2=80=9CBuilds=E2=80=9D are the things exp= licitly declared in the jobset. If you have a declared build for GCC, but no build for MPC and MPFR, then the server will consider that GCC has zero non-built dependencies, even though MPFR and MPC may still need to be built. Having =E2=80=98remote-worker=E2=80=99 operate on derivations rather than b= uilds would address this impedance mismatch, though there are complications (there are bits of the database schema that amalgamate build/derivation). Food for thought! Ludo=E2=80=99. From unknown Tue Sep 23 19:26:05 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Andreas Enge Subject: bug#63412: closed (Close) Message-ID: References: X-Gnu-PR-Message: they-closed 63412 X-Gnu-PR-Package: guix Reply-To: 63412@debbugs.gnu.org Date: Sun, 06 Jul 2025 20:11:03 +0000 Content-Type: multipart/mixed; boundary="----------=_1751832663-22510-1" This is a multi-part message in MIME format... ------------=_1751832663-22510-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #63412: Topological sorting in cuirass which was filed against the guix package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 63412@debbugs.gnu.org. --=20 63412: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D63412 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1751832663-22510-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 63412-done) by debbugs.gnu.org; 6 Jul 2025 20:10:05 +0000 Received: from localhost ([127.0.0.1]:58969 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1uYVgZ-0005dR-S8 for submit@debbugs.gnu.org; Sun, 06 Jul 2025 16:10:04 -0400 Received: from hera.aquilenet.fr ([185.233.100.1]:45780) by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.84_2) (envelope-from ) id 1uYVgW-0005c3-JA; Sun, 06 Jul 2025 16:10:01 -0400 Received: from localhost (localhost [127.0.0.1]) by hera.aquilenet.fr (Postfix) with ESMTP id CA7681E5; Sun, 6 Jul 2025 22:09:53 +0200 (CEST) Authentication-Results: hera.aquilenet.fr; none X-Virus-Scanned: Debian amavis at hera.aquilenet.fr Received: from hera.aquilenet.fr ([127.0.0.1]) by localhost (hera.aquilenet.fr [127.0.0.1]) (amavis, port 10024) with ESMTP id fM73ukPQa6Nx; Sun, 6 Jul 2025 22:09:53 +0200 (CEST) Received: from jurong (86.56.141.77.rev.sfr.net [77.141.56.86]) by hera.aquilenet.fr (Postfix) with ESMTPSA id 5F0FA115; Sun, 6 Jul 2025 22:09:52 +0200 (CEST) Date: Sun, 6 Jul 2025 22:09:51 +0200 From: Andreas Enge To: 62992-done@debbugs.gnu.org, 63414-done@debbugs.gnu.org, 63412-done@debbugs.gnu.org Subject: Close Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline X-Spamd-Result: default: False [-3.22 / 15.00]; NEURAL_HAM(-3.00)[-1.000]; BAYES_HAM(-0.62)[82.05%]; MID_RHS_NOT_FQDN(0.50)[]; MIME_GOOD(-0.10)[text/plain]; RCVD_COUNT_TWO(0.00)[2]; FROM_EQ_ENVFROM(0.00)[]; MIME_TRACE(0.00)[0:+]; TO_DN_NONE(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; RCVD_TLS_ALL(0.00)[]; FROM_HAS_DN(0.00)[]; RCPT_COUNT_THREE(0.00)[3]; ARC_NA(0.00)[] X-Rspamd-Action: no action X-Rspamd-Queue-Id: CA7681E5 X-Rspamd-Server: hera X-Spamd-Bar: --- X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 63412-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Closing old issues. Andreas ------------=_1751832663-22510-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 10 May 2023 10:06:52 +0000 Received: from localhost ([127.0.0.1]:45276 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pwgih-0002dP-PW for submit@debbugs.gnu.org; Wed, 10 May 2023 06:06:52 -0400 Received: from lists.gnu.org ([209.51.188.17]:34622) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1pwgif-0002dH-Is for submit@debbugs.gnu.org; Wed, 10 May 2023 06:06:50 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pwgid-0002c0-Nf for bug-guix@gnu.org; Wed, 10 May 2023 06:06:47 -0400 Received: from hera.aquilenet.fr ([185.233.100.1]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1pwgiW-0003XH-Hx for bug-guix@gnu.org; Wed, 10 May 2023 06:06:42 -0400 Received: from localhost (localhost [127.0.0.1]) by hera.aquilenet.fr (Postfix) with ESMTP id 03CD6354; Wed, 10 May 2023 12:06:32 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at hera.aquilenet.fr Received: from hera.aquilenet.fr ([127.0.0.1]) by localhost (hera.aquilenet.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7Ed9LQSqCVIA; Wed, 10 May 2023 12:06:30 +0200 (CEST) Received: from jurong (unknown [IPv6:2001:861:c4:f2f0::c64]) by hera.aquilenet.fr (Postfix) with ESMTPSA id 44FE45B; Wed, 10 May 2023 12:06:30 +0200 (CEST) Date: Wed, 10 May 2023 12:06:28 +0200 From: Andreas Enge To: bug-guix@gnu.org Subject: Topological sorting in cuirass Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Received-SPF: pass client-ip=185.233.100.1; envelope-from=andreas@enge.fr; helo=hera.aquilenet.fr X-Spam_score_int: -18 X-Spam_score: -1.9 X-Spam_bar: - X-Spam_report: (-1.9 / 5.0 requ) BAYES_00=-1.9, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) This is a wishlist bug, but it is important for architectures where we are currently short on build power, and where this issue can stall builds and waste an arbitrary amount of build power. Cuirass should sort builds and only offload derivations for which all inputs are available. In my current understanding, cuirass offloads arbitrary derivations, and the machine to which they are offloaded then starts building recursively all inputs. If this is true, then it is possible that at some point in time, all build slots are taken by the same package built as many times as there are machines; I have seen something like this when working on core-updates, where several machines were building the main gcc compiler at the same time. At worse, if cuirass asks every machine to build a leaf package, this may result in a simultaneous full bootstrap on all of them. The situation becomes worse when the package in question fails. Then as I understand it, each machine may receive a request to build something depending on the failing package and try the failing build and thus waste build power that will not be available to build other packages successfully. Solving this problem may also make reports of build failures more accurate and legible. For instance, doxygen currently fails to build on aarch64: https://ci.guix.gnu.org/build/969427/details and is reported as "Failed", and not as "Failed (dependency)". However, looking at the build log https://ci.guix.gnu.org/build/969427/log/raw shows this: ... building path(s) `/gnu/store/p5vqrwywz053r1vkiyw54dp9gj7vw9xd-ninja-1.11.1' ... builder for `/gnu/store/0zf7fqndzf2k595r4s6wblmpccdwr3nx-ninja-1.11.1.drv' failed with exit code 1 @ build-failed /gnu/store/0zf7fqndzf2k595r4s6wblmpccdwr3nx-ninja-1.11.1.drv - 1 builder for `/gnu/store/0zf7fqndzf2k595r4s6wblmpccdwr3nx-ninja-1.11.1.drv' failed with exit code 1 cannot build derivation `/gnu/store/hlscqram59id51hxg0fj15041v52h1kw-meson-1.1.0.drv': 1 dependencies couldn't be built cannot build derivation `/gnu/store/w8qxkrwpffd9qs5w1jggy1yi27ycm0xr-jsoncpp-1.9.5.drv': 2 dependencies couldn't be built cannot build derivation `/gnu/store/mss4yv015cil1vnjnglq506m83b7n3dy-cmake-bootstrap-3.24.2.drv': 1 dependencies couldn't be built cannot build derivation `/gnu/store/w0irp6xn30nlmpizhcbjnvhqmsba41jn-cmake-minimal-3.24.2.drv': 2 dependencies couldn't be built cannot build derivation `/gnu/store/rqk2rbnpjpcnqswz8hqari1rnw6r8v1m-doxygen-1.9.5.drv': 1 dependencies couldn't be built So it is indeed a different package that fails (and the last few lines give a list of dependencies between ninja and doxygen, each of which may or may not fail once ninja is fixed). Notice that this could be solved without a topological sorting of the dependency graph: It would be enough to keep an array deriv in which deriv[i] contains a list of derivations requiring i more inputs to be built, together with the list of inputs; elements in deriv[0] are ready to be sent to a build machine, and upon completion of a build, all derivations depending on it should be moved from deriv[i] to deriv[i-1] if the input has been built successfully, or marked as "Failed (dependency)" if the input has failed. (But this could be expensive, and may require appropriate data structures.) Alternatively, build jobs could be sorted topologically and then be kept in a list; then before sending out a job, all its inputs have been tried to be built; the job should then be sent if all inputs are available, or be marked as "Failed (dependency)" if any of them has failed. Andreas ------------=_1751832663-22510-1--