Re: [PATCH v2 09/20] merge-ort: record stage and auxiliary info for every path

[Elijah Newren <newren@gmail.com>]

On Wed, Nov 11, 2020 at 10:16 AM Elijah Newren <newren@gmail.com> wrote:
>
> On Wed, Nov 11, 2020 at 7:26 AM Derrick Stolee <stolee@gmail.com> wrote:
> >
> > On 11/2/2020 3:43 PM, Elijah Newren wrote:
> > > +static void setup_path_info(struct merge_options *opt,
> > > +                         struct string_list_item *result,
> > > +                         const char *current_dir_name,
> > > +                         int current_dir_name_len,
> > > +                         char *fullpath, /* we'll take over ownership */
> > > +                         struct name_entry *names,
> > > +                         struct name_entry *merged_version,
> > > +                         unsigned is_null,     /* boolean */
> > > +                         unsigned df_conflict, /* boolean */
> > > +                         unsigned filemask,
> > > +                         unsigned dirmask,
> > > +                         int resolved          /* boolean */)
> > > +{
> > > +     struct conflict_info *path_info;
> >
> > In addition to my concerns below about 'conflict_info' versus
> > 'merged_info', I was doubly confused that 'result' in the parameter
> > list is given a variable named 'pi' for "path info" and result->util
> > eventually is equal to this path_info. What if we renamed 'result'
> > to 'pi' for "path info" here, then operated on 'pi->util' in this
> > method?
>
> result->util (or pi->util if you rename) is void *, making it hard to
> operate on; you'd have to typecast at every usage.  Since it is used a
> *lot*, it makes sense to have a typed pointer, and then just set
> result->util to a copy of that value at the end.  That is what
> path_info is for.
>
> >
> > > +     path_info = xcalloc(1, resolved ? sizeof(struct merged_info) :
> > > +                                       sizeof(struct conflict_info));
> >
> > Hm. I'm happy to have a `struct merged_info *` pointing to a
> > `struct conflict_info`, but the opposite seems very dangerous.
>
> Yeah, this is perhaps the scariest bit, and if it were a side data
> structure rather than the fundamental main one that was central to the
> algorithm, then safety would trump performance concerns.  But since it
> is the main data structure and likely the biggest (once you count the
> various copies for each relevant path), then it might be worth the
> extra care needed to shave off the extra memory.  Maybe we can still
> tweak things to get some safety back without killing performance so
> let me consider each of your suggestions/questions.
>
> If I define it as a merged_info*, the compiler will only let me modify
> fields within the merged_info portion of the struct.  Should I
> typecast every line that touches the bits in the resolved==0 path
> where I need to set fields within the conflict_info portion?
> Alternatively, would a code flow like the following make you happier?
>
>     struct conflict_info *ci = NULL;
>     struct merge_info *mi = xcalloc(...);
>     result->util = mi;
>     /* Operate on mi */
>     ...
>     if (resolved)
>       return;
>    ci = mi;
>    /* Operate on ci */
>    ...
>
> In either case, the returned item has potentially different sizes, so
> the caller will still have to take care so I'm not sure how much extra
> this structure within setup_path_info() buys us.
>
> > Perhaps we should always use sizeof(struct conflict_info)?
>
> We could do that; it'd certainly waste memory as I expect many entries
> to be unmodified (on one or both sides of history).  But I'd way
> rather go this route than splitting or re-arranging this data
> structure.
>
> > We can use path_info->merged.clean to detect whether the rest of
> > the data is worth looking at. (Or, in your case, whether or not
> > it is allocated.)
>
> ci->merged.clean is used to determine whether to look at the rest of
> the data, yes -- and that's an enforced assumption throughout the code
> (as alluded to by the comment in the merge_options_internal data
> structure that "paths" maps pathanemes to merge_info and conflict_info
> types).  However, that is not quite the same as using the clean bit to
> determine if more data is allocated; something can be allocated as a
> conflict_info rather than a merged_info due to both sides making
> modifying the same path, but then a threeway content merge comes back
> clean and ci->merged.clean is updated from 0 to 1.  The extra data
> remains allocated, but nothing in the algorithm ever needs to use
> anything outside the merged bits for that path again.  (Actually, let
> me state that more forcefully: nothing is *allowed* to look outside
> the merged bits for that path once the clean bit is updated to 1).
>
> > I imagine that in a large repo we will need many of these structs,
> > but very few of them will actually need to be conflicts, so using
> > 'struct conflict_info' always will lead to memory bloat. But in
> > that case, would we not be better off with an array instead of a
> > scattering of data across the heap?
>
> Not sure what you're trying to solve here.  Putting them in an array
> would mean copying every single one of them every time the array is
> resized.  It would also make insertion or deletion very expensive.
> And it'd prevent O(1) lookup.  It'd be a horrible data structure all
> around.  Maybe you're assuming you know exactly how many entries you
> need and what they are before the merge algorithm starts?  I don't.
> In fact, I can't even give a good magnitude approximation of how many
> it'll be before a merge starts.  (Even if you assume it's a case where
> you have an index loaded and that index is related to the merge being
> done, the number can be and often is much smaller than the number of
> entries in the index.  And just to cover the extremes, in unusual
> cases the number might be much larger than the number of index entries
> if the merge base and side being merged in has far more paths).
>
> This was the whole point of the strmap API[1] I recently added --
> provide a hashmap specialized for the case where the key is a string.
> That way I get fast lookup, and relatively fast resize as the hash
> only contains pointers to the values, not a copy of the values.
>
> Is your concern that allocating many small structs is more expensive
> than allocating a huge block of them?  If so, yes that matters, but
> see the mem_pool related patches of the strmap API[1].
>
> [1] https://lore.kernel.org/git/pull.835.v5.git.git.1604622298.gitgitgadget@gmail.com/


I just re-read what I wrote, here and below...and I need to apologize.
I tend to write, edit, revise, and repeat while composing emails and
the end result of my emails doesn't tend to reflect the path to get
there; I looped through that cycle more times than most on this email.
But, even worse, I added in a sentence or two that just shouldn't be
included regardless.  I think in particular this one sounds extremely
aggressive and dismissive which was not at all my intent.

I find your reviews to be very helpful, and I don't want to discourage
them.  Hopefully my comments didn't come across anywhere near as
strongly as they did to me on a second reading, but if they did, I'm
sorry.

> > Perhaps 'struct conflict_info' shouldn't contain a 'struct merged_info'
> > and instead be just the "extra" data. Then we could have a contiguous
> > array of 'struct merged_info' values for most of the paths, but heap
> > pointers for 'struct conflict_info' as necessary.
> >
> > It's also true that I haven't fully formed a mental model for how these
> > are used in your algorithm, so I'll keep reading.
>
> I don't understand how contiguous arrays are practical or desirable
> (I'm close to saying they're not possible, but one could employ some
> extremes to get them, as mentioned above).
>
> I could possibly have two strmaps; one mapping paths to a merge_info,
> and another (with fewer entries) mapping paths to a conflict_info.
> Seems like a royal pain, and would make for some pretty ugly code (I
> have other places that had to use two strmaps and I've hated it every
> time -- but those were cases of strmaps that were used much, much less
> than the "paths" one).  Might also slightly hurt perf
>
> > > +     path_info->merged.directory_name = current_dir_name;
> > > +     path_info->merged.basename_offset = current_dir_name_len;
> > > +     path_info->merged.clean = !!resolved;
> > > +     if (resolved) {
> > > +             path_info->merged.result.mode = merged_version->mode;
> > > +             oidcpy(&path_info->merged.result.oid, &merged_version->oid);
> > > +             path_info->merged.is_null = !!is_null;
> > > +     } else {
> > > +             int i;
> > > +
> > > +             for (i = 0; i < 3; i++) {
> > > +                     path_info->pathnames[i] = fullpath;
> > > +                     path_info->stages[i].mode = names[i].mode;
> > > +                     oidcpy(&path_info->stages[i].oid, &names[i].oid);
> > > +             }
> > > +             path_info->filemask = filemask;
> > > +             path_info->dirmask = dirmask;
> > > +             path_info->df_conflict = !!df_conflict;
> > > +     }
> > > +     strmap_put(&opt->priv->paths, fullpath, path_info);
> > > +     result->string = fullpath;
> > > +     result->util = path_info;
> >
> > This is set in all cases, so should we use it everywhere? Naturally,
> > there might be a cost to the extra pointer indirection, so maybe we
> > create a 'struct conflict_info *util' to operate on during this
> > method, but set 'result->util = util' right after allocating so we
> > know how it should behave?
>
> result->util is void*, so it's not just an extra pointer indirection,
> it's also the need to cast it to the appropriate type every time you
> want to use it.  It's easier to have that done via another copy of the
> pointer with the correct type, which is the reason for path_info.  So,
> essentially, I did use util everywhere, it's just that I spelled it as
> "path_info".  If I had named "path_info" "util" as you suggest,
> wouldn't everyone be annoyed that I used a lame name that didn't name
> the variable's purpose?
>
> Perhaps I should just add a comment saying that path_util is a typed
> alias/copy of result->util when I define it?
>
> > > @@ -91,10 +136,12 @@ static int collect_merge_info_callback(int n,
> > >        */
> > >       struct merge_options *opt = info->data;
> > >       struct merge_options_internal *opti = opt->priv;
> > > -     struct conflict_info *ci;
> > > +     struct string_list_item pi;  /* Path Info */
> > > +     struct conflict_info *ci; /* pi.util when there's a conflict */
>
> Perhaps here I should mention that ci is just a typed copy of pi.util
> (since pi.util is a void*).
>
> > ...
> >
> > > +     setup_path_info(opt, &pi, dirname, info->pathlen, fullpath,
> > > +                     names, NULL, 0, df_conflict, filemask, dirmask, 0);
> > > +     ci = pi.util;
> >
> > Here is the use of 'pi' that I was talking about earlier.
>
> ...although, to be fair, I don't actually have all that many uses of
> ci (at least not anymore) in this function.  So maybe typecasting
> pi.util each of the three-or-so times it is used isn't so bad?