From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-wm1-f49.google.com (mail-wm1-f49.google.com [209.85.128.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9FF0B279793 for ; Fri, 16 May 2025 18:12:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.49 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747419140; cv=none; b=mFC7hQpzx0gA100U4erQ9uVYun0UK/jHrk8xg3YIAxYVTcPIuYPybPNg+lHSRb1uM2Hwqkdl3PkJGMo00z/F6x/IRvwa1mnoI3UZSKRdl3O7akAjQSUY8TLr3ILpa1rjJzojfjM/uk+HpZYqF6GGtSxftp9x1XBbvlH41KRdHaM= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1747419140; c=relaxed/simple; bh=yEPKY3FKkwyimBYSIk5dZIN630lfO3KRSuavgdiIGJw=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=q/QBLieqIhG0HCqZHlwqn7kjSPtfsLjmeYlwXl49PpgcBaNQupFFCdy9/RhWzwIr8gj97t0V1bgB80wRlryVI6i6CuAr8SLIJQ1959U7YgyG6Xor91/YrjTS32BMc4OXpRM1fkTfBrCzag43/BSerQJrq0UCdvXJt6s94e7bBmw= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=B7mOxR46; arc=none smtp.client-ip=209.85.128.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="B7mOxR46" Received: by mail-wm1-f49.google.com with SMTP id 5b1f17b1804b1-43ede096d73so17110515e9.2 for ; Fri, 16 May 2025 11:12:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1747419135; x=1748023935; darn=vger.kernel.org; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:from:to:cc:subject:date :message-id:reply-to; bh=/SALGZqgYKOgPafYYlYHHv2ldEIGold4kfTl9XpW3KE=; b=B7mOxR46pPD7RFPFFOz12n07IWPjXxyAbB5RTKsdPh57nJeHuiYiA2RbcqEs4zZihU 0l+HqqtGSKxT6zNVbSvvuFGVGPtqpt/V718xcCoInmVliJcCajpiJLKkW13vqIpdzv+b 9ONohcUOGE6IQROBqN+qdb/8VYlp7Fitwxqhkq8z5d0/CC67Lv0tGZVb7z4dxd5Ab+gE MetO64htphim6XfY5uCzdlChfOIMLvzOSAfsCVHxehuECTF8jbZWBEUxpchtXeiRqxfp 99sZn6iG7Vi8A8wiQss4MsQOkUi/pwedSn94L6ingwqc6el3rEtnWkR2RqyXWPVqkSx9 QDSA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1747419135; x=1748023935; h=cc:to:mime-version:content-transfer-encoding:fcc:subject:date:from :references:in-reply-to:message-id:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=/SALGZqgYKOgPafYYlYHHv2ldEIGold4kfTl9XpW3KE=; b=MyCDSis1xsk0/boIb2kaUNRm1mmIy5P4IPVjMrGv9o+l95wuejsu3r6g3+MkWNeJTH U85dqCNJiErsy3EjjMRAaUP/Qvgvn+hLsEzlf2rSzRUkgoCKV8+p5XadLmqfNXFP4v4Z kfgxKcw+I6kclaZXHXoIv35bokeIobqupeKcb94Q/LTfvz0C90mxwKqDq6CjvjVQC4oy +aqIRZbaK5zI8dx++aIXanyPXci1BW+K4Qrw36fGJCF02Yx9awyDZiIGWlQN+yXa2TKK H0ilLs4DAgkpdrPvTEWK5M7BUNkdx+atfO+9DBY1kGd7qe0G0zLdW7pmmoiNoRhO4cMV GNOQ== X-Gm-Message-State: AOJu0Yztk3X7AYH1saaZecHMQxQeanuhMf+/6rhe2OI6wFTTHmgrVVSr IEZdC9PeSdcN8QPkwitUXPm+T4AFimL+y4cqZ/fdqNXmgvKo/vBlEXob1pw73w== X-Gm-Gg: ASbGnctawisN5NZ1bJRIzMT2ZYh72L7M61BxKLETFGHQrCJvmexRt4CfTc2X1PyHMEC CQJ5Y6n5MOwgc3TcbkvAb4ZnOpbBhP5rcQyFV28vyaGQ64His4kVEXTlC4ez/RxHnSY5lO3jnmm 1cNZ3oSH8+XhjXvPVuxV0/VmgK4qwzG5M/FHjsqT7RBWC0ekMTZ314yiP2uOs79mV9JhRRZR3Ov cEf1+4BrTzVpWzsC5y26XZr2dKZUSiTnGTEGH9LsNbZZP6Pdx6L1kllraxnRsO5UFNckINWE+5f zbw73SyfEjQQ/FS977pGNLW5h9hHqiXDn453jCc0wZ26cCI2ghkk X-Google-Smtp-Source: AGHT+IG/PG7P62OFN0G4pDS/9MxDLeSm47hQs/RqcuaawYbDPk3jEYXG6Cp3dhYmaN5FEJJzicSWDA== X-Received: by 2002:a05:6000:1445:b0:3a3:643e:2542 with SMTP id ffacd0b85a97d-3a3643e256dmr1580524f8f.26.1747419135213; Fri, 16 May 2025 11:12:15 -0700 (PDT) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id ffacd0b85a97d-3a35ca62b47sm3669929f8f.58.2025.05.16.11.12.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 16 May 2025 11:12:13 -0700 (PDT) Message-Id: In-Reply-To: References: From: "Derrick Stolee via GitGitGadget" Date: Fri, 16 May 2025 18:11:52 +0000 Subject: [PATCH v3 02/13] pack-objects: add --path-walk option Fcc: Sent Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Precedence: bulk X-Mailing-List: git@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 To: git@vger.kernel.org Cc: christian.couder@gmail.com, gitster@pobox.com, johannes.schindelin@gmx.de, johncai86@gmail.com, jonathantanmy@google.com, karthik.188@gmail.com, kristofferhaugsbakk@fastmail.com, me@ttaylorr.com, newren@gmail.com, peff@peff.net, ps@pks.im, Derrick Stolee , Derrick Stolee From: Derrick Stolee In order to more easily compute delta bases among objects that appear at the exact same path, add a --path-walk option to 'git pack-objects'. This option will use the path-walk API instead of the object walk given by the revision machinery. Since objects will be provided in batches representing a common path, those objects can be tested for delta bases immediately instead of waiting for a sort of the full object list by name-hash. This has multiple benefits, including avoiding collisions by name-hash. The objects marked as UNINTERESTING are included in these batches, so we are guaranteeing some locality to find good delta bases. After the individual passes are done on a per-path basis, the default name-hash is used to find other opportunistic delta bases that did not match exactly by the full path name. The current implementation performs delta calculations while walking objects, which is not ideal for a few reasons. First, this will cause the "Enumerating objects" phase to be much longer than usual. Second, it does not take advantage of threading during the path-scoped delta calculations. Even with this lack of threading, the path-walk option is sometimes faster than the usual approach. Future changes will refactor this code to allow for threading, but that complexity is deferred until later to keep this patch as simple as possible. This new walk is incompatible with some features and is ignored by others: * Object filters are not currently integrated with the path-walk API, such as sparse-checkout or tree depth. A blobless packfile could be integrated easily, but that is deferred for later. * Server-focused features such as delta islands, shallow packs, and using a bitmap index are incompatible with the path-walk API. * The path walk API is only compatible with the --revs option, not taking object lists or pack lists over stdin. These alternative ways to specify the objects currently ignores the --path-walk option without even a warning. Future changes will create performance tests that demonstrate the power of this approach. Signed-off-by: Derrick Stolee --- Documentation/git-pack-objects.adoc | 13 +- Documentation/technical/api-path-walk.adoc | 1 + builtin/pack-objects.c | 148 +++++++++++++++++++-- t/t5300-pack-object.sh | 15 +++ 4 files changed, 168 insertions(+), 9 deletions(-) diff --git a/Documentation/git-pack-objects.adoc b/Documentation/git-pack-objects.adoc index 7f69ae4855f6..3b803d3a7830 100644 --- a/Documentation/git-pack-objects.adoc +++ b/Documentation/git-pack-objects.adoc @@ -16,7 +16,7 @@ SYNOPSIS [--cruft] [--cruft-expiration=