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

On Fri, Aug 28, 2020 at 12:08 AM Jeff King <peff@peff.net> wrote:

Cool.

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'.)

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.