From: "brian m. carlson" <sandals@crustytoothpaste•net>
To: <git@vger•kernel.org>
Cc: Junio C Hamano <gitster@pobox•com>,
Patrick Steinhardt <ps@pks•im>, Derrick Stolee <stolee@gmail•com>
Subject: [PATCH 2/9] docs: update offset order for pack index v3
Date: Fri, 19 Sep 2025 01:09:04 +0000 [thread overview]
Message-ID: <20250919010911.649831-3-sandals@crustytoothpaste.net> (raw)
In-Reply-To: <20250919010911.649831-1-sandals@crustytoothpaste.net>
The current design of pack index v3 has items in two different orders:
sorted shortened object ID order and pack order. The shortened object
IDs and the pack index offset values are in the former order and
everything else is in the latter.
This, however, poses some problems. We have many parts of the packfile
code that expect to find out data about an object knowing only its index
in pack order. With the current design, to find the pack offset after
having looked up the index in pack order, we must then look up the full
object ID and use that to look up the shortened object ID to find the
pack offset, which is inconvenient, inefficient, and leads to poor cache
usage.
Instead, let's change the offset values to be looked up by pack order.
This works better because once we know the pack order offset, we can
find the full object name and its location in the pack with a simple
index into their respective tables. This makes many operations much
more efficient, especially with the functions we already have, and it
avoids the need for the revindex with pack index v3.
Signed-off-by: brian m. carlson <sandals@crustytoothpaste•net>
---
Documentation/technical/hash-function-transition.adoc | 10 ++++------
1 file changed, 4 insertions(+), 6 deletions(-)
diff --git a/Documentation/technical/hash-function-transition.adoc b/Documentation/technical/hash-function-transition.adoc
index f2df1d618d..11c4f2950a 100644
--- a/Documentation/technical/hash-function-transition.adoc
+++ b/Documentation/technical/hash-function-transition.adoc
@@ -260,12 +260,10 @@ network byte order):
compressed data to be copied directly from pack to pack during
repacking without undetected data corruption.
- * A table of 4-byte offset values. For an object in the table of
- sorted shortened object names, the value at the corresponding
- index in this table indicates where that object can be found in
- the pack file. These are usually 31-bit pack file offsets, but
- large offsets are encoded as an index into the next table with the
- most significant bit set.
+ * A table of 4-byte offset values. The index of this table in pack order
+ indicates where that object can be found in the pack file. These are
+ usually 31-bit pack file offsets, but large offsets are encoded as
+ an index into the next table with the most significant bit set.
* A table of 8-byte offset entries (empty for pack files less than
2 GiB). Pack files are organized with heavily used objects toward
next prev parent reply other threads:[~2025-09-19 1:09 UTC|newest]
Thread overview: 67+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-09-19 1:09 [PATCH 0/9] SHA-1/SHA-256 interoperability, part 1 brian m. carlson
2025-09-19 1:09 ` [PATCH 1/9] docs: update pack index v3 format brian m. carlson
2025-09-19 22:08 ` Junio C Hamano
2025-09-20 15:23 ` brian m. carlson
2025-09-20 17:01 ` Junio C Hamano
2025-09-24 7:55 ` Patrick Steinhardt
2025-09-25 21:39 ` brian m. carlson
2025-09-19 1:09 ` brian m. carlson [this message]
2025-09-19 1:09 ` [PATCH 3/9] docs: reflect actual double signature for tags brian m. carlson
2025-09-19 22:34 ` Junio C Hamano
2025-09-20 15:29 ` brian m. carlson
2025-09-20 17:04 ` Junio C Hamano
2025-09-24 7:55 ` Patrick Steinhardt
2025-09-25 21:46 ` brian m. carlson
2025-09-19 1:09 ` [PATCH 4/9] docs: improve ambiguous areas of pack format documentation brian m. carlson
2025-09-19 23:04 ` Junio C Hamano
2025-09-19 1:09 ` [PATCH 5/9] docs: add documentation for loose objects brian m. carlson
2025-09-19 19:10 ` Junio C Hamano
2025-09-19 19:13 ` Junio C Hamano
2025-09-19 19:15 ` brian m. carlson
2025-09-19 20:18 ` Junio C Hamano
2025-09-24 7:55 ` Patrick Steinhardt
2025-09-25 21:40 ` brian m. carlson
2025-09-19 23:16 ` Junio C Hamano
2025-09-24 7:55 ` Patrick Steinhardt
2025-09-30 16:39 ` brian m. carlson
2025-09-19 1:09 ` [PATCH 6/9] rev-parse: allow printing compatibility hash brian m. carlson
2025-09-19 23:24 ` Junio C Hamano
2025-09-24 7:55 ` Patrick Steinhardt
2025-09-25 21:48 ` brian m. carlson
2025-09-19 1:09 ` [PATCH 7/9] fsck: consider gpgsig headers expected in tags brian m. carlson
2025-09-19 23:31 ` Junio C Hamano
2025-09-22 21:38 ` brian m. carlson
2025-09-19 1:09 ` [PATCH 8/9] Allow specifying compatibility hash brian m. carlson
2025-09-24 7:56 ` Patrick Steinhardt
2025-09-30 16:44 ` brian m. carlson
2025-09-19 1:09 ` [PATCH 9/9] t: add a prerequisite for a " brian m. carlson
2025-09-24 7:56 ` Patrick Steinhardt
2025-10-02 22:38 ` [PATCH v2 0/9] SHA-1/SHA-256 interoperability, part 1 brian m. carlson
2025-10-02 22:38 ` [PATCH v2 1/9] docs: update pack index v3 format brian m. carlson
2025-10-03 17:00 ` Junio C Hamano
2025-10-02 22:38 ` [PATCH v2 2/9] docs: update offset order for pack index v3 brian m. carlson
2025-10-02 22:38 ` [PATCH v2 3/9] docs: reflect actual double signature for tags brian m. carlson
2025-10-02 22:38 ` [PATCH v2 4/9] docs: improve ambiguous areas of pack format documentation brian m. carlson
2025-10-03 17:07 ` Junio C Hamano
2025-10-03 21:06 ` brian m. carlson
2025-10-02 22:38 ` [PATCH v2 5/9] docs: add documentation for loose objects brian m. carlson
2025-10-03 17:05 ` Junio C Hamano
2025-10-02 22:38 ` [PATCH v2 6/9] rev-parse: allow printing compatibility hash brian m. carlson
2025-10-02 22:38 ` [PATCH v2 7/9] fsck: consider gpgsig headers expected in tags brian m. carlson
2025-10-02 22:38 ` [PATCH v2 8/9] t: allow specifying compatibility hash brian m. carlson
2025-10-03 17:14 ` Junio C Hamano
2025-10-03 20:45 ` brian m. carlson
2025-10-02 22:38 ` [PATCH v2 9/9] t1010: use BROKEN_OBJECTS prerequisite brian m. carlson
2025-10-09 21:56 ` [PATCH v3 0/9] SHA-1/SHA-256 interoperability, part 1 brian m. carlson
2025-10-09 21:56 ` [PATCH v3 1/9] docs: update pack index v3 format brian m. carlson
2025-10-09 21:56 ` [PATCH v3 2/9] docs: update offset order for pack index v3 brian m. carlson
2025-10-09 21:56 ` [PATCH v3 3/9] docs: reflect actual double signature for tags brian m. carlson
2025-10-09 21:56 ` [PATCH v3 4/9] docs: improve ambiguous areas of pack format documentation brian m. carlson
2025-10-09 21:56 ` [PATCH v3 5/9] docs: add documentation for loose objects brian m. carlson
2025-10-09 21:56 ` [PATCH v3 6/9] rev-parse: allow printing compatibility hash brian m. carlson
2025-10-09 21:56 ` [PATCH v3 7/9] fsck: consider gpgsig headers expected in tags brian m. carlson
2025-10-09 21:56 ` [PATCH v3 8/9] t: allow specifying compatibility hash brian m. carlson
2025-10-09 21:56 ` [PATCH v3 9/9] t1010: use BROKEN_OBJECTS prerequisite brian m. carlson
2025-10-13 15:24 ` [PATCH v3 0/9] SHA-1/SHA-256 interoperability, part 1 Junio C Hamano
2025-10-13 16:34 ` brian m. carlson
2025-10-14 5:53 ` Patrick Steinhardt
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250919010911.649831-3-sandals@crustytoothpaste.net \
--to=sandals@crustytoothpaste$(echo .)net \
--cc=git@vger$(echo .)kernel.org \
--cc=gitster@pobox$(echo .)com \
--cc=ps@pks$(echo .)im \
--cc=stolee@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox