Re: [RFC PATCH 2/5] Add delta-islands.{c,h}

From: Jeff King <peff@peff.net>
Date: Aug 6, 2018, 14:17 UTC
Message-ID: <20180806141733.GD31282@sigill.intra.peff.net>
In-Reply-To: <CAP8UFD2frOjmZoOfWW-93xewA6LS5zTEisNr4QDz2FNQE2DY_A@mail.gmail.com>

On Sun, Aug 05, 2018 at 08:53:19PM +0200, Christian Couder wrote:

Show 11 quoted lines

> - 'layer' is used in add_to_write_order() which is called from many
> places in add_descendants_to_write_order() and compute_write_order()
> for example like this:
> 
>             for (s = DELTA_SIBLING(e); s; s = DELTA_SIBLING(s)) {
>                 add_to_write_order(wo, endp, s);
>             }
> 
> So it seems to me that moving 'layer' to 'struct packing_data' would
> require changing the DELTA_SIBLING macros or adding a hack to easily
> find the index in an array corresponding to a 'struct object_entry'.

Right, that hack is how the various the existing memory-shrinking macros work. Every "struct object_entry *" that we deal with _must_ be in the list in "packing_data", so that we can compute an index as "entry - to_pack.objects".

So I think Duy is just suggesting:

  void oe_set_layer(struct packing_data *pack,
                    struct object_entry *entry,
		    int layer)
  {
          if (!pack->layers)
	          ALLOC_ARRAY(pack->layers, pack->nr_objects);
	  pack->layers[entry - pack->objects] = layer;
  }

  int oe_get_layer(struct packing_data *pack,
                   struct object_entry *entry)
  {
          if (!pack->layers)
	          return 0;
          return pack->layers[entry - pack->nr_objects];
  }

That said, I wonder if need to cache the layer at all. We compute the layers all at once in the new compute_pack_layers(). But it is just a linear walk over the objects, asking for each "is this in the core island?".

Could we just ask "is this in the core island?" when we consider each object? That's a hash lookup each time we ask instead of looking at our int, but I'd think we would only ask in linear proportion to the number of objects. So there's no algorithmic speedup, though maybe a constant-time one (for two layers, I'd expect we'd probably ask about each object twice).

Show 12 quoted lines

> - I don't see why it is different from other fields in 'struct
> object_entry' that are also used in compute_write_order(), for
> example:
> 
>     uint32_t delta_idx;    /* delta base object */
>     uint32_t delta_child_idx; /* deltified objects who bases me */
>     uint32_t delta_sibling_idx; /* other deltified objects who ... */
> 
> Would we also want to move these fields to 'struct packing_data'? Why
> or why not? If we want to move them, then it might be a good idea to
> do all the moving at the same time to make sure we get something
> coherent.

We actually use those multiple times. They're reset and used in compute_write_order(), but I think we use them earlier as part of the delta search (at the very least we use delta_idx; maybe no the child/sibling stuff).

-Peff