[clang-format-diff.py] give clang-format-diff a job pool (10x speed)

[seanptmaher]

Summary

This patch changes the implementation of clang-format-diff.py to
start up many clang-format processes in parallel in order to speed
up clang-format-diff.py by several orders of magnitude on large
patches (less than a minute instead of several tens of minutes).

[seanptmaher]

Update python formatting

[MyDeveloperDay]

You've lost the first part of the patch in this latest diff

[seanptmaher]

Possibly fix the patchset? Sorry I've never used phabricator berfore.

[owenpan]

Can you add an option e.g. -j N where N is a positive integer and defaults to 1? Also, can you include a use case in which we can see the ~10x improvement on runtime?

[MyDeveloperDay]

On my laptop running

import os;
import multiprocessing


def main():
    num = len(os.sched_getaffinity(0))
    numcpu = multiprocessing.cpu_count()
    print ('affinity', num, '\n');
    print ('cpucount', numcpu, '\n');

if __name__ == '__main__':
  main()

produces

affinity 16

cpucount 16

Does the * 8 mean I might get 128?

Do I want 16 parallel clang-format processes running at once? (especially if some of the files are memory hungry)

I'm with @owenpan here I am happy to use a -j N option when I need more power, and N default should be 1 otherwise we could be causing a regression, I'm not a fan of processes that assume thats the only thing running on my machine (cough visual studio!), and there always should be some way of saying do what we did before.

clang/tools/clang-format/clang-format-diff.py

129

is this 128 parallel processes?

130

is 8 a good number here?

[seanptmaher]

Add jobs flag

[seanptmaher]

Yeah, the jobs flag is a much better implementation. Thanks for the comments. I've implemented that. I was indeed making the assumption that this is all that's running, etc. as you mentioned.

The use case I was using this with was running diff formatting of very large diffs (automated mass refactors changing thousands of files) on the chromium codebase -- I'm not sure how to "include" such a use case as you mentioned. I could write a benchmark if you'd like?

[seanptmaher]

fix the formatting

[owenpan]

In D141230#4048069, @seanptmaher wrote:

The use case I was using this with was running diff formatting of very large diffs (automated mass refactors changing thousands of files) on the chromium codebase -- I'm not sure how to "include" such a use case as you mentioned. I could write a benchmark if you'd like?

I was thinking about trying out whatever you did when reviewing this patch, so it would be helpful if you could share the steps/commands you used. A benchmark is unnecessary, but having some tests would be great.

[seanptmaher]

Fix bug in -j implementation where proper waiting wasn't happening

[seanptmaher]

It's slightly hard to test this because it involves making a huge diff of a git repo. If you're willing to jump through the hoops of cloning chromium (honestly, this is a pain in the ass. It's too much hard drive space and you've got to install depot_tools. If you don't already have google code on your machine, you're probably going to want this to be a temporary thing) and running a few commands, I think I've figured out how you could test this.

First, clone the repo using the instructions you find here: https://www.chromium.org/developers/how-tos/get-the-code/

Then, checkout commit hash 0e9d17d1b6414621228115ee535c7becf67e1c62.

Then, apply the patch file that I've just attached. It is a 6000-file change, where I've changed a bunch of includes.

0001-remove-ALL-INCLUDES.patch4 MBDownload

Then, finally, to format that patch using the clang-format-diff.py file, run the following:

$ time git diff -U0 --no-color --relative HEAD^ | buildtools/clang_format/script/clang-format-diff.py -p1 -i

On my machine, that gives:

________________________________________________________
Executed in   16.56 mins    fish           external
   usr time   15.01 mins    1.02 millis   15.01 mins
   sys time    1.70 mins    0.71 millis    1.70 mins

This will take quite some time. After it finishes, save a diff of the filesystem with git add . && git diff --cached > ../slow-diff, (important not to save it in your working directory or else you'd mess up the next diff!)
Then git reset . && git restore . to start over.

Then, run the same command but with the new clang-format-diff.py, and pass it as many jobs as your computer could handle.

$ time git diff -U0 --no-color --relative HEAD^ | path/to/the/new/clang-format-diff.py -p1 -i -j{16,128}

On my machine, that runs in just above 20 seconds.

________________________________________________________
Executed in   22.24 secs    fish           external
   usr time   16.71 mins    0.00 millis   16.71 mins
   sys time    2.37 mins    2.05 millis    2.37 mins

Finally, save a diff of this again, like something like so: git add . && git diff --cached > ../fast-diff

Then finally you can diff the two diffs:

spvw@this ~/Documents/code/chromium/src ((eb2c565c…))> diff ../slow-diff ../fast-diff
spvw@this ~/Documents/code/chromium/src ((eb2c565c…))>

Showing that the two are identical.

Are there other ways in which you'd want to test this?

i'm not sure how to write unit-test-like tests for this, so if you'd like me to, I'd appreciate a pointer...

[seanptmaher]

No need to include os anymore, I'm not checking number of cores

[seanptmaher]

Thanks a lot for the review, by the way.

I realize the patch wasn't up to snuff initially, but glad to get it in order with your help.

[MyDeveloperDay]

I can see why you have the desire for something that takes 22 seconds and not 16 mins!

[seanptmaher]

I can't actually commit this -- could one of you? Or has it already been done? I remember reading that someone had to manually push the patch upstream.

[seanptmaher]

Hey, bump on this. Still waiting on the commit.

[owenpan]

In D141230#4054768, @seanptmaher wrote:

I can't actually commit this -- could one of you? Or has it already been done? I remember reading that someone had to manually push the patch upstream.

Can we have the name and email you want to use for your patch? See https://llvm.org/docs/Phabricator.html#committing-someone-s-change-from-phabricator.

[seanptmaher]

Hey,

Sure. The name is Sean Maher and the email is [e-mail]

Thanks for your help.

clang/tools/clang-format/clang-format-diff.py

 import subprocess
 import sys
 
 if sys.version_info.major >= 3:
     from io import StringIO
 else:
     from io import BytesIO as StringIO
 
+def process_subprocess_result(proc, args):
+  stdout, stderr = proc.communicate()
+  if proc.returncode != 0:
+    sys.exit(proc.returncode)
+  if not args.i:
+    with open(filename) as f:
+      code = f.readlines()
+    formatted_code = StringIO(stdout).readlines()
+    diff = difflib.unified_diff(code, formatted_code,
+                                filename, filename,
+                                '(before formatting)',
+                                '(after formatting)')
+    diff_string = ''.join(diff)
+    if len(diff_string) > 0:
+      sys.stdout.write(diff_string)
 
 def main():
   parser = argparse.ArgumentParser(description=__doc__,
                                    formatter_class=
                                            argparse.RawDescriptionHelpFormatter)
   parser.add_argument('-i', action='store_true', default=False,
                       help='apply edits to files instead of displaying a diff')
   parser.add_argument('-p', metavar='NUM', default=0,
parser.add_argument('-style',
                       'Microsoft, Mozilla, WebKit)')
   parser.add_argument('-fallback-style',
                       help='The name of the predefined style used as a'
                       'fallback in case clang-format is invoked with'
                       '-style=file, but can not find the .clang-format'
                       'file to use.')
   parser.add_argument('-binary', default='clang-format',
                       help='location of binary to use for clang-format')
+  parser.add_argument('-j', default=1, type=int, metavar='N',
+                      help='number of concurrent clang-format processes to spawn in '
+                      'parallel')
   args = parser.parse_args()
 
   # Extract changed lines for each file.
   filename = None
   lines_by_file = {}
   for line in sys.stdin:
     match = re.search(r'^\+\+\+\ (.*?/){%s}(\S*)' % args.p, line)
     if match:
if match:
       # surrounding statements.
       end_line = start_line
       if line_count != 0:
         end_line += line_count - 1
       lines_by_file.setdefault(filename, []).extend(
           ['-lines', str(start_line) + ':' + str(end_line)])
 
   # Reformat files containing changes in place.
-  for filename, lines in lines_by_file.items():
+  lbf = list(lines_by_file.items())
+  procs = [None for i in range(args.j)]
+  while lbf:
+    spawned_one = False
+    for i, proc in enumerate(procs):
+      if not lbf:
+        break
+      if proc is not None and proc.poll() is not None:
+        process_subprocess_result(proc, args)
+        # Set to None to flag the slot as free to start a new process
+        procs[i] = None
+        proc = None
+      if proc is None:
+        filename, lines = lbf.pop()
+        spawned_one = True
         if args.i and args.verbose:
           print('Formatting {}'.format(filename))
         command = [args.binary, filename]
         if args.i:
           command.append('-i')
         if args.sort_includes:
           command.append('-sort-includes')
         command.extend(lines)
         if args.style:
           command.extend(['-style', args.style])
         if args.fallback_style:
           command.extend(['-fallback-style', args.fallback_style])
-
         try:
-      p = subprocess.Popen(command,
+          procs[i] = subprocess.Popen(command,
                                       stdout=subprocess.PIPE,
                                       stderr=None,
                                       stdin=subprocess.PIPE,
                                       universal_newlines=True)
         except OSError as e:
           # Give the user more context when clang-format isn't
           # found/isn't executable, etc.
           raise RuntimeError(
               'Failed to run "%s" - %s"' % (" ".join(command), e.strerror))
-
-    stdout, stderr = p.communicate()
-    if p.returncode != 0:
-      sys.exit(p.returncode)
-
-    if not args.i:
-      with open(filename) as f:
-        code = f.readlines()
-      formatted_code = StringIO(stdout).readlines()
-      diff = difflib.unified_diff(code, formatted_code,
-                                  filename, filename,
-                                  '(before formatting)', '(after formatting)')
-      diff_string = ''.join(diff)
-      if len(diff_string) > 0:
-        sys.stdout.write(diff_string)
+    # If we didn't spawn a single process after iterating through the whole
+    # list, wait on one of them to finish until we iterate through again, to
+    # prevent spinning in the case where we have a small number of jobs.
+    if not spawned_one:
+      procs[0].wait()
+  # Be sure not to leave any stray processes when exiting.
+  for proc in procs:
+    if proc:
+      proc.wait()
+      process_subprocess_result(proc, args)
 
 if __name__ == '__main__':
   main()