Re: [PATCH 4/5] strmap: add strdup_strings option

[Elijah Newren <newren@gmail.com>]

On Fri, Aug 28, 2020 at 12:08 AM Jeff King <peff@peff.net> wrote:
>
> On Fri, Aug 21, 2020 at 03:25:44PM -0700, Elijah Newren wrote:
>
> > >   - That sounds like a lot of maps. :) I guess you've looked at
> > >     compacting some of them into a single map-to-struct?
> >
> > Oh, map-to-struct is the primary use.  But compacting them won't work,
> > because the reason for the additional maps is that they have different
> > sets of keys (this set of paths meet a certain condition...).  Only
> > one map contains all the paths involved in the merge.
>
> OK, I guess I'm not surprised that you would not have missed such an
> obvious optimization. :)
>
> > Also, several of those maps don't even store a value; and are really
> > just a set implemented via strmap (thus meaning the only bit of data I
> > need for some conditions is whether any given path meets it).  It
> > seems slightly ugly to have to call strmap_put(map, string, NULL) for
> > those.  I wonder if I should have another strset type much like your
> > suggesting for strintmap.  Hmm...
>
> FWIW, khash does have a "set" mode where it avoids allocating the value
> array at all.

Cool.

> What's the easiest way to benchmark merge-ort?

Note that I discovered another optimization that I'm working on
implementing; when finished, it should cut down a little more on the
time spent on inexact rename detection.  That should have the side
effect of having the time spent on strmaps stick out some more in the
overall timings (as a percentage of overall time anyway).  So, I'm
focused on that before I do other benchmarking work (which is part of
the reason I mentioned my strmap/hashmap benchmarking last week might
take a while).

Anyway, on to your question:

=== If you just want to be able to run the ort merge algorithm ===

Clone git@github.com:newren/git and checkout the 'ort' branch and
build it.  It currently changes the default merge algorithm to 'ort'
and even ignores '-s recursive' by remapping it to '-s ort' (because I
wanted to see how regression tests fared with ort as a replacement for
recrusive).  It should pass the regression tests if you want to run
those first.  But note that if you want to compare 'ort' to
'recursive', then currently you need to have two different git builds,
one of my branch and one with a different checkout of something else
(e.g. 2.28.0 or 'master' or whatever).

=== Decide the granularity of your timing ===

I suspect you know more than me here, but maybe my pointers are useful anyway...

Decide if you want to measure overall program runtime, or dive into
details.  I used both a simple 'time' and the better 'hyperfine' for
the former, and used both 'perf' and GIT_TRACE2_PERF for the latter.
One nice thing about GIT_TRACE2_PERF was I wrote a simple program to
aggregate the times per region and provide percentages, in a script at
the toplevel named 'summarize-perf' that I can use to prefix commands.
Thus, I could for example run from my linux clone:
    $ ../git/summarize-perf git fast-rebase --onto HEAD base hwmon-updates
and I'd get output that looks something like (note that this is a
subset of the real output):
    1.400 : 35 : label:inmemory_nonrecursive
       0.827 : 41 : ..label:renames
          0.019 : <unmeasured> ( 2.2%)
          0.803 : 37 : ....label:regular renames
          0.004 : 31 : ....label:directory renames
          0.001 : 31 : ....label:process renames
       0.513 : 41 : ..label:collect_merge_info
       0.048 : 35 : ..label:process_entries
    0.117 : 1 : label:checkout
    0.000 : 1 : label:record_unmerged
and where those fields are <time> : <count> : <region label>.

=== If you want to time the testcases I used heavily while developing ===

The rebase-testcase/redo-timings script (in the ort branch) has
details on what I actually ran, though it has some paranoia around
attempting to make my laptop run semi-quietly and try to avoid all the
variance that I wished I could control a bit better.  And it assumes
you are running in a linux clone with a few branches set up a certain
way.  Let me explain those tests without using that script, as simply
as I can:

The setup for the particular cases I was testing is as follows:
  * Clone the linux kernel, and run the following:
  $ git branch hwmon-updates fd8bdb23b91876ac1e624337bb88dc1dcc21d67e
  $ git branch hwmon-just-one fd8bdb23b91876ac1e624337bb88dc1dcc21d67e~34
  $ git branch base 4703d9119972bf586d2cca76ec6438f819ffa30e
  $ git switch -c 5.4-renames v5.4
  $ git mv drivers pilots
  $ git commit -m "Rename drivers/ to pilots/"

And from there, there were three primary tests I was comparing:

  * Rename testcase, 35 patches:
  $ git checkout 5.4-renames^0
  $ git fast-rebase --onto HEAD base hwmon-updates

  * Rename testcase, just 1 patch:
  $ git switch 5.4-renames^0
  $ git fast-rebase --onto HEAD base hwmon-just-one

  * No renames (or at least very few renames) testcase, 35 patches:
  $ git checkout v5.4^0
  $ git branch -f hwmon-updates
fd8bdb23b91876ac1e624337bb88dc1dcc21d67e # Need to reset
hwmon-updates, due to fast-rebase done above
  $ git fast-rebase --onto HEAD base hwmon-updates

(If you want to compare with 'recursive' from a different build of
git, just replace 'fast-rebase' with 'rebase'.  You can also use
'rebase' instead of 'fast-rebase' on the ort branch and it'll use the
ort merge algorithm, but you get all the annoying
working-tree-updates-while-rebasing rather than just having the
working tree updated at the end of the rebase.  You also get all the
annoying forks of 'git checkout' and 'git commit' that sequencer is
guilty of spawning.  But it certainly supports a lot more options and
can save state to allow resuming after conflicts, unlike
'fast-rebase'.)

> I suspect I could swap out hashmap for khash (messily) in an hour or less.

Well, you might be assuming I used sane strmaps, with each strmap
having a fixed type for the stored value.  That's mostly true, but
there were two counterexamples I can think of: "paths" (the biggest
strmap) is a map of string -> {merged_info OR conflict_info}, because
merged_info is a smaller subset of conflict_info and saves space for
each path that can be trivially merged.  Also, in diffcore-rename,
"dir_rename" starts life as a map of string -> strmap, but later
transitions to string -> string, because I'm evil and didn't set up a
temporary strmap like I probably should have.

Also, the code is littered with FIXME comments, unnecessary #ifdefs,
and is generally in need of lots of cleanup.  Sorry.