From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp0.migadu.com ([2001:41d0:403:4876::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms8.migadu.com with LMTPS id GLOtJ/CswmWglwAAqHPOHw:P1 (envelope-from ) for ; Tue, 06 Feb 2024 23:04:32 +0100 Received: from aspmx1.migadu.com ([2001:41d0:403:4876::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp0.migadu.com with LMTPS id GLOtJ/CswmWglwAAqHPOHw (envelope-from ) for ; Tue, 06 Feb 2024 23:04:32 +0100 X-Envelope-To: larch@yhetil.org Authentication-Results: aspmx1.migadu.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=k2H0ibNB; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (aspmx1.migadu.com: domain of "guix-devel-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-devel-bounces+larch=yhetil.org@gnu.org" ARC-Seal: i=1; s=key1; d=yhetil.org; t=1707257072; a=rsa-sha256; cv=none; b=ZzIlu7tTcMQzstoPADhros7jUk2MnahAhf1vF1oMWHgeiA941XB7oBA433Sq8zrfuDDvZC E6J8XpE/1znZtXC58NMr7+uwLABhJKh+o+QZeP24nv2qvPGyRAptqQGXtdZy5oargzKEAH 6E4eHMuO+U8eRJNT+lWVl8fQcODeJR/uwmuZHxk2aVwvjHaec4cIn5XrbX7hYKKnvyvWKt keuBiSQ+dAU5x5iZznzzpXLatgVRDRfi4d7Gu2SyTCF4oN/RFDhLTpIMYU34uryK500XUi tiNUAjAnJnJQoJJ/pFaHZ/bTqqGiiGpXPV5YqwImahGWBK5VToVP/V8MhQFqPQ== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=k2H0ibNB; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (aspmx1.migadu.com: domain of "guix-devel-bounces+larch=yhetil.org@gnu.org" designates 209.51.188.17 as permitted sender) smtp.mailfrom="guix-devel-bounces+larch=yhetil.org@gnu.org" ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1707257072; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:list-id:list-help: list-unsubscribe:list-subscribe:list-post:dkim-signature; bh=+zsmSfoqVe1D9yZWNYCVd490uRXznHNlxIu59a8I2Ss=; b=PKA21Fk30XzZMm8VhlBAENa5Sb9CzCEpIiyKUaptUzAwszN8UeFEICVSiLZ28B/Pa66qHU 7g1X7oRbKq3QzJwgi9uArpGnMUme3DKwbIxQakdv2+o/K3/tIUqcCVHgABPlzlym7TVJ3F K77BtOt0D5HUEpKTYAVNNMPhm2E8y1RkhiIej6v74zvenGbp0D5F3TCtF7/aqTZX7Qfxo7 Vbr0FogrTeDcMkN9WfXHx0WPPiHlTRbVZ+mc2mAB4H4tJ/662sl+pHxr8Y4ItpLLpKdCW/ P1FUrpJdK0RFn/sTDbrB2bTQeADvAl9H0hR3bH2iup4dBRJSTfUJJw14NUa9Sg== Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 751B821AC8 for ; Tue, 6 Feb 2024 23:04:32 +0100 (CET) Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1rXTY0-00064K-Hn; Tue, 06 Feb 2024 17:04:08 -0500 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 1rXTXz-000649-FX for guix-devel@gnu.org; Tue, 06 Feb 2024 17:04:07 -0500 Received: from mail-wm1-x32c.google.com ([2a00:1450:4864:20::32c]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1rXTXx-0001QX-53; Tue, 06 Feb 2024 17:04:07 -0500 Received: by mail-wm1-x32c.google.com with SMTP id 5b1f17b1804b1-40fb5f5fd84so8083965e9.1; Tue, 06 Feb 2024 14:04:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1707257041; x=1707861841; darn=gnu.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=+zsmSfoqVe1D9yZWNYCVd490uRXznHNlxIu59a8I2Ss=; b=k2H0ibNBNn5RHmyVgZFkbBQHRGTnrJ9hgn4Z0QMrVjcRNUmWoJ9VkArkbCvtUrjTY+ 8gUQrjdSg2DSzMHOTySQw9wbHwSjxP9O6AGTR2SQoUfkUSSttyRBCDOfDKcESEk3qMwM KfpqwMHdwrxsKGe1AbnaxUfanPVJmLGmBIKLhugzDpto7hg53hwECdEOsDwrIhGVIUNm PHj4qQ9+v8RlUlY8KzkvXrlHWhcgSELMQLR7JaRlX4m0Dox9733smICYcfdbt5hw2NkQ S927hmLj4lurDy+nhlIdfKIYX3r8Jo6Ko8qri5DpiRI/M2rVfWbPiGSYeFEJcKW7qiDR 3xwQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1707257041; x=1707861841; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=+zsmSfoqVe1D9yZWNYCVd490uRXznHNlxIu59a8I2Ss=; b=d0QiDeTm+fukSDu2zG7BHdyjzeBSQ9euc3G84lIH550WLV9a6ibRaQT3q2bU5X66Jf YtmfFlpL0Cu1iJ4MXBTYq+DBw717VgKlMWo4bJRtVrTv9rzDrzeN9taGYxylYEUmVIO3 IgjMlLS24/UdzZfdWSxv4FOJ5EKMBiYdXde0acudxsrL7PshJloS7vBtg7VDuqMYdmTw ga/3BBMw9IjsZ3Bo8pNo+X1+Fimffcdbj6tmhGNWPdptlBtHed/oJD1L0uGKSQlb6NNY mGhnjMi9am4m2igCyw1kzNHKKDpZ6U+BJMJR+HK9amIvj/hJIUKgZT4QkuGjB7SEW3zK TarQ== X-Gm-Message-State: AOJu0YzZRbG5QKg3Sb/J5icwYDUXpnoap8YrIyBYheXXBoNgud/d1+nX dV+W73jLL6I1nZAW+mT+c6HBXHbt5XxO3EKlZ5LbS8WajetmU9iC4HjVu5vL X-Google-Smtp-Source: AGHT+IHviKo1AqPMMN78buVIkX+GTeQeobO21SjB9vKfNRFWomggla4Y+YtVWfrYrlj1tL3MqESE9Q== X-Received: by 2002:a05:600c:4f54:b0:40f:db10:5f14 with SMTP id m20-20020a05600c4f5400b0040fdb105f14mr3038105wmq.1.1707257041137; Tue, 06 Feb 2024 14:04:01 -0800 (PST) Received: from lili ([2a01:e0a:59b:9120:7869:b96b:1cdb:a4a8]) by smtp.gmail.com with ESMTPSA id o36-20020a05600c512400b0040fdb244485sm3973wms.40.2024.02.06.14.04.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 06 Feb 2024 14:04:00 -0800 (PST) From: Simon Tournier To: Guix Devel Cc: Ludovic =?utf-8?Q?Court=C3=A8s?= Subject: ice-9 match penalty depending on pattern? Date: Tue, 06 Feb 2024 22:33:46 +0100 Message-ID: <87wmrh6zwl.fsf@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Received-SPF: pass client-ip=2a00:1450:4864:20::32c; envelope-from=zimon.toutoune@gmail.com; helo=mail-wm1-x32c.google.com 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_DNSWL_NONE=-0.0001, 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-BeenThere: guix-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Development of GNU Guix and the GNU System distribution." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-devel-bounces+larch=yhetil.org@gnu.org Sender: guix-devel-bounces+larch=yhetil.org@gnu.org X-Migadu-Flow: FLOW_IN X-Migadu-Country: US X-Migadu-Scanner: mx10.migadu.com X-Spam-Score: -8.98 X-Migadu-Queue-Id: 751B821AC8 X-Migadu-Spam-Score: -8.98 X-TUID: nL86gHve9coN Hi, >From Ludo=E2=80=99s mastodon message [1]: Re =E2=80=98match=E2=80=99 penalty: when using ellipses in patterns, th= e generated code checks for =E2=80=9Cproper lists=E2=80=9D, which is O(n). The tri= ck is to instead match a pair: =E2=9C=94 (match lst ((head . tail) =E2=80=A6)) =E2=9D=8E (match lst ((head tail ...) =E2=80=A6)) Therefore I have confused by some patterns. --8<---------------cut here---------------start------------->8--- 28 candidates: ./gnu/services/monitoring.scm:249: ((head tail ...) ./gnu/system/file-systems.scm:249: ((head1 tail1 ...) ./gnu/system/file-systems.scm:251: ((head2 tail2 ...) ./gnu/packages.scm:116: ((_ file head tail ...) ./gnu/build/activation.scm:85: ((head tail ...) ./gnu/build/linux-boot.scm:225: ((head tail ...) ./guix/http-client.scm:255: ((head tail ...) ./guix/records.scm:604: ((_ record field offset ((head normal) tail ..= .)) ./guix/records.scm:607: ((_ record field offset ((head delayed) tail .= ..)) ./guix/records.scm:610: ((_ record field offset ((head thunked) tail .= ..)) ./guix/read-print.scm:482: ((head tail ...) ./guix/read-print.scm:750: ((head tail ...) ./guix/lint.scm:1614: ((head tail ...) ./guix/scripts/package.scm:809: ((head tail ...) head))= )) ./guix/self.scm:160: ((head tail ...) ./guix/store.scm:1556: ((head tail ...) ./guix/store.scm:1764: ((head tail ...) ./guix/ui.scm:295: ((head tail ...) ./guix/ui.scm:2258: ((head tail ...) head))) ./guix/docker.scm:261: (((head ...) (tail ...) id) ./guix/build/store-copy.scm:72: ((head tail ...) ./guix/build/gremlin.scm:336: ((head tail ...) ./guix/build/graft.scm:330: ((head tail ...) ./guix/build/utils.scm:236: ((head tail ...) ./guix/build/utils.scm:405: ((head tail ...) ./guix/utils.scm:910: ((head1 tail1 ...) ./guix/utils.scm:913: ((head2 tail2 ...) ./build-aux/compile-all.scm:71: ((head tail ...) --8<---------------cut here---------------end--------------->8--- Maybe for some of them, it changes nothing for the user-visible performances. Maybe it does. :-) Well, I do not know the length of each match. However, some are part of some loop. Therefore, if we could save some cycles by simply replacing the ellipsis, as ((head tail ...) stuff that use head or tail) by ((head . tail) stuff that use head or tail) Why not? Do I miss something in the implementation of =E2=80=99match=E2=80= =99? Cheers, simon 1: https://social.sciences.re/@civodul@toot.aquilenet.fr/111885442823194970