Re: [PATCH] revision: reallocate TOPO_WALK object flags

[Derrick Stolee <stolee@gmail.com>]

On 6/24/2020 9:05 AM, René Scharfe wrote:
> The bit fields in struct object have an unfortunate layout.  Here's what
> pahole reports on x86_64 GNU/Linux:
> 
> struct object {
> 	unsigned int               parsed:1;             /*     0: 0  4 */
> 	unsigned int               type:3;               /*     0: 1  4 */
> 
> 	/* XXX 28 bits hole, try to pack */
> 
> 	/* Force alignment to the next boundary: */
> 	unsigned int               :0;
> 
> 	unsigned int               flags:29;             /*     4: 0  4 */
> 
> 	/* XXX 3 bits hole, try to pack */
> 
> 	struct object_id           oid;                  /*     8    32 */
> 
> 	/* size: 40, cachelines: 1, members: 4 */
> 	/* sum members: 32 */
> 	/* sum bitfield members: 33 bits, bit holes: 2, sum bit holes: 31 bits */
> 	/* last cacheline: 40 bytes */
> };
> 
> Notice the 1+3+29=33 bits in bit fields and 28+3=31 bits in holes.

This is certainly unfortunate.

> There are holes inside the flags bit field as well -- while some object
> flags are used for more than one purpose, 22, 23 and 24 are still free.
> Use  23 and 24 instead of 27 and 28 for TOPO_WALK_EXPLORED and
> TOPO_WALK_INDEGREE.  This allows us to reduce FLAG_BITS by one so that
> all bitfields combined fit into a single 32-bit slot:
> 
> struct object {
> 	unsigned int               parsed:1;             /*     0: 0  4 */
> 	unsigned int               type:3;               /*     0: 1  4 */
> 	unsigned int               flags:28;             /*     0: 4  4 */
> 	struct object_id           oid;                  /*     4    32 */
> 
> 	/* size: 36, cachelines: 1, members: 4 */
> 	/* last cacheline: 36 bytes */
> };
> 
> With this tight packing the size of struct object is reduced by 10%.
> Other architectures probably benefit as well.

Excellent improvement!

> - * revision.h:               0---------10         15                   25----28
> + * revision.h:               0---------10         15             23------26
>   * fetch-pack.c:             01
>   * negotiator/default.c:       2--5
>   * walker.c:                 0-2
> @@ -79,7 +79,7 @@ struct object_array {
>   * builtin/show-branch.c:    0-------------------------------------------26

The only collision is here in builtin/show-branch.c, and when I added
the TOPO_WALK_* bits, I didn't understand that these bits were
sufficiently independent from the topo-walk logic that we could add
collisions here.

I think I realized this behavior when doing the commit-reach.c refactor,
but I never revisited these flag values.

>   * builtin/unpack-objects.c:                                 2021
>   */
> -#define FLAG_BITS  29
> +#define FLAG_BITS  28
> 
>  /*
>   * The object type is stored in 3 bits.
> diff --git a/revision.h b/revision.h
> index 93491b79d4..f412ae85eb 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -37,6 +37,10 @@
> 
>  /* WARNING: This is also used as REACHABLE in commit-graph.c. */
>  #define PULL_MERGE	(1u<<15)
> +
> +#define TOPO_WALK_EXPLORED	(1u<<23)
> +#define TOPO_WALK_INDEGREE	(1u<<24)
> +
>  /*
>   * Indicates object was reached by traversal. i.e. not given by user on
>   * command-line or stdin.
> @@ -48,9 +52,6 @@
>  #define TRACK_LINEAR	(1u<<26)
>  #define ALL_REV_FLAGS	(((1u<<11)-1) | NOT_USER_GIVEN | TRACK_LINEAR | PULL_MERGE)
> 
> -#define TOPO_WALK_EXPLORED	(1u<<27)
> -#define TOPO_WALK_INDEGREE	(1u<<28)
> -
>  #define DECORATE_SHORT_REFS	1
>  #define DECORATE_FULL_REFS	2

Thankfully, the changes are very simple!

Thanks,
-Stolee