From patchwork Fri Dec 20 17:19:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Derrick Stolee X-Patchwork-Id: 13917164 Received: from mail-wr1-f49.google.com (mail-wr1-f49.google.com [209.85.221.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 1C39C21C192 for ; Fri, 20 Dec 2024 17:20:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734715203; cv=none; b=PZSmXTFbCtLOTkKYW/zXMQACJNyKKT1lnuhHTeB2VRtY5FI/JyIzDeJKE3bY9Fzt4IZvUCY1yxXpYyV4+mFso25eHqQRfHJfCcqSVA2llxoJ7Jo6PFkj7MdAUZz2VvbDnKUTwItDhec1SfxzUIBGlagrsHcMtEo0WH5X//gI/CM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734715203; c=relaxed/simple; bh=yKiLqgSSThEMnZI3WBPPa4bUr1sjaHFxQLKdd2wyPf4=; h=Message-Id:In-Reply-To:References:From:Date:Subject:Content-Type: MIME-Version:To:Cc; b=qS4RlH6/v+tPzlmTBbh9kc+0HW/3KrENTYIoC7U0mVat1rONk2vtCUBrXMmIr/Fhy4a/wEipka/LQpgvKNVFHbhKan7ujG7sWRoUTFZLxEqgV9UfApGnBiq8ytsqymesFRNGSUg+Kqvnx8dVbG9sxtI67lSGBgJHe//ixhr5DhY= 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=Oke+e3mg; arc=none smtp.client-ip=209.85.221.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="Oke+e3mg" Received: by mail-wr1-f49.google.com with SMTP id ffacd0b85a97d-3862d161947so1124019f8f.3 for ; Fri, 20 Dec 2024 09:20:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734715199; x=1735319999; 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=zRyM+efCIVNr5zfeFLfApVvj4fwKDdYbdXJrWPLwvb0=; b=Oke+e3mgPi6DG2HPEEa95zM5F/CG3Q57L0w6SKx6LqcIvzZtCkciylwTRf1hbqUZw6 r9dTU9bkj0BvxjanDeLG2YWT0zeYVwUBZif7Z7ybCjn1caZ/vgGtbNQBRsbtZtAZMzUE zxDLkjt3VykbAGNn175d70pbvXCKceY9HHCsgs9pZC9Fow4Rg2t1EsDPx9nQzMynFt7f 1CSSgP4xngKgyZHXIiqaKFrqCJWdhFzFVoGmHvVK+2xDAE4D/UzTjI+vixm8mO75Cz0i BgS6zAMXsVswn7wSJzWyq8wtya3Fp3fDOZ2jW1FpFI86WDH/W0NJCxX6/k6FdYNiIyDU XW3g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734715199; x=1735319999; 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=zRyM+efCIVNr5zfeFLfApVvj4fwKDdYbdXJrWPLwvb0=; b=GbVYdD3t08eHWTSd5M8W5GRpUQ2S3f39QBpXhKBtiESdEkxn8EyrXWtSqwHot3tpqC E6k/IFxjcnLjesfFi3JOUcgPp/Oc8gSTwihbBHwJXKl1XSbiD8zT3LSmxTBpd33X5cZG 67MDGdfrgFcs3+9uEOGaSTJCyoX7jFSQJPx9Ha9X9xU0lTig6lGBKQPAdkwnGmTdgpWu r4rPE4igw0i5dKlP9mI28vrPfBVaHZRBW8cIJ7vIwpjM/atRT8cI52wfetaA2pzVTrpv r7SFmnbvsIUtqoLxx4bTlEFLIxkSrbLmGz+Xk497XJ8uo8xE3Cx90KqQHLrHD7sA60kD 9xPA== X-Gm-Message-State: AOJu0YzCj75mDbRG4AuobslkQzwnV8o8dwCi7CYioXGOuIexfZy4gBY/ SSfTV2UCruAeLtyMNE0wkNJivs37XRwKItYjc4jcH2lHeRjRNWTognYr7Q== X-Gm-Gg: ASbGncvcHUZBhy7UPw5ldJOpiuku7+CRZeKHcIFJ5Zpr8CM9fbC7SGC+c1isF2zWaAC ZySd4Wf41WAa8X5gaUoyN/pXrx7t4p/6eWovfrz5+5JwodZlDxzq+87ArLeYS8GtDuvSjhjtYoH kr5AIsV3E57t3lIvH5V/vhQtO1MM6rrYjI/nlsL+AYjIAOVxx9/lC0BwXMs3EdvqgQWGlg7wyPs xjjS3oEy9YJj1TDUOYpM1s3ikDQvqHZgrMd+m/EnM3YhjRM2z/gG9hBhQ== X-Google-Smtp-Source: AGHT+IFBJsZEirmmLOcERemnAuWftZcwv0rlockMCnpe/AHQKAAtcj5DYJYhr6TVkN0rZaT8OYEdZQ== X-Received: by 2002:a05:6000:178c:b0:386:4a24:1914 with SMTP id ffacd0b85a97d-38a223f7219mr3284127f8f.37.1734715198950; Fri, 20 Dec 2024 09:19:58 -0800 (PST) Received: from [127.0.0.1] ([13.74.141.28]) by smtp.gmail.com with ESMTPSA id 5b1f17b1804b1-43661219611sm51524335e9.23.2024.12.20.09.19.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 20 Dec 2024 09:19:58 -0800 (PST) Message-Id: In-Reply-To: References: Date: Fri, 20 Dec 2024 17:19:48 +0000 Subject: [PATCH v3 2/8] pack-objects: add --name-hash-version option Fcc: Sent 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: gitster@pobox.com, johannes.schindelin@gmx.de, peff@peff.net, ps@pks.im, me@ttaylorr.com, johncai86@gmail.com, newren@gmail.com, jonathantanmy@google.com, karthik nayak , Derrick Stolee , Derrick Stolee From: Derrick Stolee From: Derrick Stolee The previous change introduced a new pack_name_hash_v2() function that intends to satisfy much of the hash locality features of the existing pack_name_hash() function while also distinguishing paths with similar final components of their paths. This change adds a new --name-hash-version option for 'git pack-objects' to allow users to select their preferred function version. This use of an integer version allows for future expansion and a direct way to later store a name hash version in the .bitmap format. For now, let's consider how effective this mechanism is when repacking a repository with different name hash versions. Specifically, we will execute 'git pack-objects' the same way a 'git repack -adf' process would, except we include --name-hash-version= for testing. On the Git repository, we do not expect much difference. All path names are short. This is backed by our results: | Stage | Pack Size | Repack Time | |-----------------------|-----------|-------------| | After clone | 260 MB | N/A | | --name-hash-version=1 | 127 MB | 129s | | --name-hash-version=2 | 127 MB | 112s | This example demonstrates how there is some natural overhead coming from the cloned copy because the server is hosting many forks and has not optimized for exactly this set of reachable objects. But the full repack has similar characteristics for both versions. Let's consider some repositories that are hitting too many collisions with version 1. First, let's explore the kinds of paths that are commonly causing these collisions: * "/CHANGELOG.json" is 15 characters, and is created by the beachball [1] tool. Only the final character of the parent directory can differentiate different versions of this file, but also only the two most-significant digits. If that character is a letter, then this is always a collision. Similar issues occur with the similar "/CHANGELOG.md" path, though there is more opportunity for differences In the parent directory. * Localization files frequently have common filenames but differentiates via parent directories. In C#, the name "/strings.resx.lcl" is used for these localization files and they will all collide in name-hash. [1] https://github.com/microsoft/beachball I've come across many other examples where some internal tool uses a common name across multiple directories and is causing Git to repack poorly due to name-hash collisions. One open-source example is the fluentui [2] repo, which uses beachball to generate CHANGELOG.json and CHANGELOG.md files, and these files have very poor delta characteristics when comparing against versions across parent directories. | Stage | Pack Size | Repack Time | |-----------------------|-----------|-------------| | After clone | 694 MB | N/A | | --name-hash-version=1 | 438 MB | 728s | | --name-hash-version=2 | 168 MB | 142s | [2] https://github.com/microsoft/fluentui In this example, we see significant gains in the compressed packfile size as well as the time taken to compute the packfile. Using a collection of repositories that use the beachball tool, I was able to make similar comparisions with dramatic results. While the fluentui repo is public, the others are private so cannot be shared for reproduction. The results are so significant that I find it important to share here: | Repo | --name-hash-version=1 | --name-hash-version=2 | |----------|-----------------------|-----------------------| | fluentui | 440 MB | 161 MB | | Repo B | 6,248 MB | 856 MB | | Repo C | 37,278 MB | 6,755 MB | | Repo D | 131,204 MB | 7,463 MB | Future changes could include making --name-hash-version implied by a config value or even implied by default during a full repack. It is important to point out that the name hash value is stored in the .bitmap file format, so we must force --name-hash-version=1 when bitmaps are being read or written. Later, the bitmap format could be updated to be aware of the name hash version so deltas can be quickly computed across the bitmapped/not-bitmapped boundary. Signed-off-by: Derrick Stolee --- Documentation/git-pack-objects.txt | 32 ++++++++++++++++++- builtin/pack-objects.c | 49 +++++++++++++++++++++++++++--- t/t5300-pack-object.sh | 31 +++++++++++++++++++ 3 files changed, 106 insertions(+), 6 deletions(-) diff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt index e32404c6aae..7f69ae4855f 100644 --- a/Documentation/git-pack-objects.txt +++ b/Documentation/git-pack-objects.txt @@ -15,7 +15,8 @@ SYNOPSIS [--revs [--unpacked | --all]] [--keep-pack=] [--cruft] [--cruft-expiration=