{"thread":{"id":"53748","subject":"[PATCH] revision: reallocate TOPO_WALK object flags","startedAt":"2020-06-24T13:05:59Z","lastAt":"2020-06-24T19:39:34Z","messageCount":4,"participants":["René Scharfe","Derrick Stolee","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"400500","messageId":"29f8b1fc-fac7-12c6-4bfe-28aed7e709c3@web.de","threadId":"53748","inReplyTo":null,"subject":"[PATCH] revision: reallocate TOPO_WALK object flags","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2020-06-24T13:05:38Z","receivedAt":"2020-06-24T13:05:59Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"The bit fields in struct object have an unfortunate layout. Here's what\npahole reports on x86_64 GNU/Linux:\n\nstruct object {\n\tunsigned int parsed:1; /* 0: 0 4 */\n\tunsigned int type:3; /* 0: 1 4 */\n\n\t/* XXX 28 bits hole, try to pack */\n\n\t/* Force alignment to the next boundary: */\n\tunsigned int :0;\n\n\tunsigned int flags:29; /* 4: 0 4 */\n\n\t/* XXX 3 bits hole, try to pack */\n\n\tstruct object_id oid; /* 8 32 */\n\n\t/* size: 40, cachelines: 1, members: 4 */\n\t/* sum members: 32 */\n\t/* sum bitfield members: 33 bits, bit holes: 2, sum bit holes: 31 bits */\n\t/* last cacheline: 40 bytes */\n};\n\nNotice the 1+3+29=33 bits in bit fields and 28+3=31 bits in holes.\n\nThere are holes inside the flags bit field as well -- while some object\nflags are used for more than one purpose, 22, 23 and 24 are still free.\nUse 23 and 24 instead of 27 and 28 for TOPO_WALK_EXPLORED and\nTOPO_WALK_INDEGREE. This allows us to reduce FLAG_BITS by one so that\nall bitfields combined fit into a single 32-bit slot:\n\nstruct object {\n\tunsigned int parsed:1; /* 0: 0 4 */\n\tunsigned int type:3; /* 0: 1 4 */\n\tunsigned int flags:28; /* 0: 4 4 */\n\tstruct object_id oid; /* 4 32 */\n\n\t/* size: 36, cachelines: 1, members: 4 */\n\t/* last cacheline: 36 bytes */\n};\n\nWith this tight packing the size of struct object is reduced by 10%.\nOther architectures probably benefit as well.\n\nSigned-off-by: René Scharfe \n---\n object.h | 4 ++--\n revision.h | 7 ++++---\n 2 files changed, 6 insertions(+), 5 deletions(-)\n\ndiff --git a/object.h b/object.h\nindex a496d2e4e1..b207f550b2 100644\n--- a/object.h\n+++ b/object.h\n@@ -59,7 +59,7 @@ struct object_array {\n\n /*\n * object flag allocation:\n- * revision.h: 0---------10 15 25----28\n+ * revision.h: 0---------10 15 23------26\n * fetch-pack.c: 01\n * negotiator/default.c: 2--5\n * walker.c: 0-2\n@@ -79,7 +79,7 @@ struct object_array {\n * builtin/show-branch.c: 0-------------------------------------------26\n * builtin/unpack-objects.c: 2021\n */\n-#define FLAG_BITS 29\n+#define FLAG_BITS 28\n\n /*\n * The object type is stored in 3 bits.\ndiff --git a/revision.h b/revision.h\nindex 93491b79d4..f412ae85eb 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -37,6 +37,10 @@\n\n /* WARNING: This is also used as REACHABLE in commit-graph.c. */\n #define PULL_MERGE\t(1u<<15)\n+\n+#define TOPO_WALK_EXPLORED\t(1u<<23)\n+#define TOPO_WALK_INDEGREE\t(1u<<24)\n+\n /*\n * Indicates object was reached by traversal. i.e. not given by user on\n * command-line or stdin.\n@@ -48,9 +52,6 @@\n #define TRACK_LINEAR\t(1u<<26)\n #define ALL_REV_FLAGS\t(((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR | PULL_MERGE)\n\n-#define TOPO_WALK_EXPLORED\t(1u<<27)\n-#define TOPO_WALK_INDEGREE\t(1u<<28)\n-\n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\n\n--\n2.27.0\n"},{"id":"400503","messageId":"8e5b6b9f-a778-7b20-2c67-2d5d8ff0d8a0@gmail.com","threadId":"53748","inReplyTo":"29f8b1fc-fac7-12c6-4bfe-28aed7e709c3@web.de","subject":"Re: [PATCH] revision: reallocate TOPO_WALK object flags","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2020-06-24T13:51:01Z","receivedAt":"2020-06-24T13:51:06Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 6/24/2020 9:05 AM, René Scharfe wrote:\n> The bit fields in struct object have an unfortunate layout. Here's what\n> pahole reports on x86_64 GNU/Linux:\n> \n> struct object {\n> \tunsigned int parsed:1; /* 0: 0 4 */\n> \tunsigned int type:3; /* 0: 1 4 */\n> \n> \t/* XXX 28 bits hole, try to pack */\n> \n> \t/* Force alignment to the next boundary: */\n> \tunsigned int :0;\n> \n> \tunsigned int flags:29; /* 4: 0 4 */\n> \n> \t/* XXX 3 bits hole, try to pack */\n> \n> \tstruct object_id oid; /* 8 32 */\n> \n> \t/* size: 40, cachelines: 1, members: 4 */\n> \t/* sum members: 32 */\n> \t/* sum bitfield members: 33 bits, bit holes: 2, sum bit holes: 31 bits */\n> \t/* last cacheline: 40 bytes */\n> };\n> \n> Notice the 1+3+29=33 bits in bit fields and 28+3=31 bits in holes.\n\nThis is certainly unfortunate.\n\n> There are holes inside the flags bit field as well -- while some object\n> flags are used for more than one purpose, 22, 23 and 24 are still free.\n> Use 23 and 24 instead of 27 and 28 for TOPO_WALK_EXPLORED and\n> TOPO_WALK_INDEGREE. This allows us to reduce FLAG_BITS by one so that\n> all bitfields combined fit into a single 32-bit slot:\n> \n> struct object {\n> \tunsigned int parsed:1; /* 0: 0 4 */\n> \tunsigned int type:3; /* 0: 1 4 */\n> \tunsigned int flags:28; /* 0: 4 4 */\n> \tstruct object_id oid; /* 4 32 */\n> \n> \t/* size: 36, cachelines: 1, members: 4 */\n> \t/* last cacheline: 36 bytes */\n> };\n> \n> With this tight packing the size of struct object is reduced by 10%.\n> Other architectures probably benefit as well.\n\nExcellent improvement!\n\n> - * revision.h: 0---------10 15 25----28\n> + * revision.h: 0---------10 15 23------26\n> * fetch-pack.c: 01\n> * negotiator/default.c: 2--5\n> * walker.c: 0-2\n> @@ -79,7 +79,7 @@ struct object_array {\n> * builtin/show-branch.c: 0-------------------------------------------26\n\nThe only collision is here in builtin/show-branch.c, and when I added\nthe TOPO_WALK_* bits, I didn't understand that these bits were\nsufficiently independent from the topo-walk logic that we could add\ncollisions here.\n\nI think I realized this behavior when doing the commit-reach.c refactor,\nbut I never revisited these flag values.\n\n> * builtin/unpack-objects.c: 2021\n> */\n> -#define FLAG_BITS 29\n> +#define FLAG_BITS 28\n> \n> /*\n> * The object type is stored in 3 bits.\n> diff --git a/revision.h b/revision.h\n> index 93491b79d4..f412ae85eb 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -37,6 +37,10 @@\n> \n> /* WARNING: This is also used as REACHABLE in commit-graph.c. */\n> #define PULL_MERGE\t(1u<<15)\n> +\n> +#define TOPO_WALK_EXPLORED\t(1u<<23)\n> +#define TOPO_WALK_INDEGREE\t(1u<<24)\n> +\n> /*\n> * Indicates object was reached by traversal. i.e. not given by user on\n> * command-line or stdin.\n> @@ -48,9 +52,6 @@\n> #define TRACK_LINEAR\t(1u<<26)\n> #define ALL_REV_FLAGS\t(((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR | PULL_MERGE)\n> \n> -#define TOPO_WALK_EXPLORED\t(1u<<27)\n> -#define TOPO_WALK_INDEGREE\t(1u<<28)\n> -\n> #define DECORATE_SHORT_REFS\t1\n> #define DECORATE_FULL_REFS\t2\n\nThankfully, the changes are very simple!\n\nThanks,\n-Stolee\n"},{"id":"400538","messageId":"xmqq8sgc8n3v.fsf@gitster.c.googlers.com","threadId":"53748","inReplyTo":"8e5b6b9f-a778-7b20-2c67-2d5d8ff0d8a0@gmail.com","subject":"Re: [PATCH] revision: reallocate TOPO_WALK object flags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2020-06-24T16:06:28Z","receivedAt":"2020-06-24T16:06:32Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n>> @@ -79,7 +79,7 @@ struct object_array {\n>> * builtin/show-branch.c: 0-------------------------------------------26\n>\n> The only collision is here in builtin/show-branch.c, and when I added\n> the TOPO_WALK_* bits, I didn't understand that these bits were\n> sufficiently independent from the topo-walk logic that we could add\n> collisions here.\n\nThe show-branch subcommand does its own walking without using any of\nthe usual revision machinery, and uses a bit per starting point (so\nthe number of starting points is limited by the wordsize), so it\nshould be safe.\n\nIt would be wonderful if the bits used by it can be moved to a slab\nso that it can work from more starting points, or deprecate the\nsubcommand altogether. With better visualization tools (including\n\"log --graph --oneline\"), I suspect that it outlived its usefulness.\n\n"},{"id":"400554","messageId":"20200624193931.GA3336639@coredump.intra.peff.net","threadId":"53748","inReplyTo":"29f8b1fc-fac7-12c6-4bfe-28aed7e709c3@web.de","subject":"Re: [PATCH] revision: reallocate TOPO_WALK object flags","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2020-06-24T19:39:31Z","receivedAt":"2020-06-24T19:39:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jun 24, 2020 at 03:05:38PM +0200, René Scharfe wrote:\n\n> The bit fields in struct object have an unfortunate layout. Here's what\n> pahole reports on x86_64 GNU/Linux:\n> \n> struct object {\n> \tunsigned int parsed:1; /* 0: 0 4 */\n> \tunsigned int type:3; /* 0: 1 4 */\n> \n> \t/* XXX 28 bits hole, try to pack */\n> \n> \t/* Force alignment to the next boundary: */\n> \tunsigned int :0;\n> \n> \tunsigned int flags:29; /* 4: 0 4 */\n> \n> \t/* XXX 3 bits hole, try to pack */\n> \n> \tstruct object_id oid; /* 8 32 */\n> \n> \t/* size: 40, cachelines: 1, members: 4 */\n> \t/* sum members: 32 */\n> \t/* sum bitfield members: 33 bits, bit holes: 2, sum bit holes: 31 bits */\n> \t/* last cacheline: 40 bytes */\n> };\n> \n> Notice the 1+3+29=33 bits in bit fields and 28+3=31 bits in holes.\n\nGood catch. The original FLAG_BITS was intended to pack with parsed and\ntype, and we should have caught this in review when it got bumped in\nb45424181e (revision.c: generation-based topo-order algorithm,\n2018-11-01).\n\nThe patch looks correct to me.\n\n> There are holes inside the flags bit field as well -- while some object\n> flags are used for more than one purpose, 22, 23 and 24 are still free.\n> Use 23 and 24 instead of 27 and 28 for TOPO_WALK_EXPLORED and\n> TOPO_WALK_INDEGREE. This allows us to reduce FLAG_BITS by one so that\n> all bitfields combined fit into a single 32-bit slot:\n> \n> struct object {\n> \tunsigned int parsed:1; /* 0: 0 4 */\n> \tunsigned int type:3; /* 0: 1 4 */\n> \tunsigned int flags:28; /* 0: 4 4 */\n> \tstruct object_id oid; /* 4 32 */\n> \n> \t/* size: 36, cachelines: 1, members: 4 */\n> \t/* last cacheline: 36 bytes */\n> };\n\nWith 20-byte hashes, this put us at 24 bytes, which is 8-byte aligned. I\nhad always assumed once we moved to 32-byte hashes that we'd be stuck\nwith a 40-byte \"struct object\" to keep 8-byte alignment on 64-bit\nsystems. But it seems that at least on x86_64 Linux, we're happy with\n4-byte alignment. That's useful to know (I had wondered if we might be\nable to put those extra bytes to a good use, but I guess not).\n\n> /*\n> * object flag allocation:\n> - * revision.h: 0---------10 15 25----28\n> + * revision.h: 0---------10 15 23------26\n> * fetch-pack.c: 01\n> * negotiator/default.c: 2--5\n> * walker.c: 0-2\n\nDefinitely not a new problem, but I think we should consider \"rotating\"\nthis table. The point of it is for two branches that get merged to cause\na conflict if they allocate the same bit to two uses. And we _might_ get\nsee such a conflict if the allocations are on adjacent lines, but we\nwouldn't if they're far away. E.g., imagine one side does:\n\n -* revision.h 0---------10\n +* revision.h 0----------11\n * fetch-pack.c 01\n * foo.c 2\n * bar.c 3\n\nand the other does:\n\n * revision.h 0---------10\n * fetch-pack.c 01\n * foo.c 2\n * bar.c 3\n +* uh-oh.c 11\n\nNow we have two possibly conflicting uses of bit 11 (a semantic\nconflict), but no matching textual conflict.\n\nWhereas if we wrote:\n\n * bit 0: revision.h, fetch-pack.c\n * bit 1: revision.h\n * bit 2: revision.h, foo.c\n * bit 3: revision.h, bar.c\n [etc...]\n\nthen we'd get a conflict on the \"bit 11\" line. It does mean that\nunrelated modules get written on the same line, but that's the point.\nThey're only allowed to be on the same line after somebody determines\nthat they're mutually exclusive and won't stomp on each other.\n\n-Peff\n"}]}