DiffAlgorithms.java

  1. /*
  2.  * Copyright (C) 2010, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  10. package org.eclipse.jgit.pgm.debug;

  11. import static java.lang.Integer.valueOf;
  12. import static java.lang.Long.valueOf;

  13. import java.io.File;
  14. import java.lang.management.ManagementFactory;
  15. import java.lang.management.ThreadMXBean;
  16. import java.lang.reflect.Field;
  17. import java.util.ArrayList;
  18. import java.util.Collections;
  19. import java.util.List;

  20. import org.eclipse.jgit.diff.DiffAlgorithm;
  21. import org.eclipse.jgit.diff.HistogramDiff;
  22. import org.eclipse.jgit.diff.MyersDiff;
  23. import org.eclipse.jgit.diff.RawText;
  24. import org.eclipse.jgit.diff.RawTextComparator;
  25. import org.eclipse.jgit.errors.LargeObjectException;
  26. import org.eclipse.jgit.lib.AbbreviatedObjectId;
  27. import org.eclipse.jgit.lib.Constants;
  28. import org.eclipse.jgit.lib.FileMode;
  29. import org.eclipse.jgit.lib.MutableObjectId;
  30. import org.eclipse.jgit.lib.ObjectId;
  31. import org.eclipse.jgit.lib.ObjectReader;
  32. import org.eclipse.jgit.lib.Repository;
  33. import org.eclipse.jgit.lib.RepositoryBuilder;
  34. import org.eclipse.jgit.lib.RepositoryCache;
  35. import org.eclipse.jgit.pgm.Command;
  36. import org.eclipse.jgit.pgm.TextBuiltin;
  37. import org.eclipse.jgit.pgm.internal.CLIText;
  38. import org.eclipse.jgit.revwalk.RevCommit;
  39. import org.eclipse.jgit.revwalk.RevWalk;
  40. import org.eclipse.jgit.treewalk.TreeWalk;
  41. import org.eclipse.jgit.treewalk.filter.TreeFilter;
  42. import org.eclipse.jgit.util.FS;
  43. import org.kohsuke.args4j.Option;

  44. @Command(usage = "usage_DiffAlgorithms")
  45. class DiffAlgorithms extends TextBuiltin {

  46.     final Algorithm myers = new Algorithm() {
  47.         @Override
  48.         DiffAlgorithm create() {
  49.             return MyersDiff.INSTANCE;
  50.         }
  51.     };

  52.     final Algorithm histogram = new Algorithm() {
  53.         @Override
  54.         DiffAlgorithm create() {
  55.             HistogramDiff d = new HistogramDiff();
  56.             d.setFallbackAlgorithm(null);
  57.             return d;
  58.         }
  59.     };

  60.     final Algorithm histogram_myers = new Algorithm() {
  61.         @Override
  62.         DiffAlgorithm create() {
  63.             HistogramDiff d = new HistogramDiff();
  64.             d.setFallbackAlgorithm(MyersDiff.INSTANCE);
  65.             return d;
  66.         }
  67.     };

  68.     // -----------------------------------------------------------------------
  69.     //
  70.     // Implementation of the suite lives below this line.
  71.     //
  72.     //

  73.     @Option(name = "--algorithm", metaVar = "NAME", usage = "Enable algorithm(s)")
  74.     List<String> algorithms = new ArrayList<>();

  75.     @Option(name = "--text-limit", metaVar = "LIMIT", usage = "Maximum size in KiB to scan per file revision")
  76.     int textLimit = 15 * 1024; // 15 MiB as later we do * 1024.

  77.     @Option(name = "--repository", aliases = { "-r" }, metaVar = "GIT_DIR", usage = "Repository to scan")
  78.     List<File> gitDirs = new ArrayList<>();

  79.     @Option(name = "--count", metaVar = "LIMIT", usage = "Number of file revisions to be compared")
  80.     int count = 0; // unlimited

  81.     private final RawTextComparator cmp = RawTextComparator.DEFAULT;

  82.     private ThreadMXBean mxBean;

  83.     /** {@inheritDoc} */
  84.     @Override
  85.     protected boolean requiresRepository() {
  86.         return false;
  87.     }

  88.     /** {@inheritDoc} */
  89.     @Override
  90.     protected void run() throws Exception {
  91.         mxBean = ManagementFactory.getThreadMXBean();
  92.         if (!mxBean.isCurrentThreadCpuTimeSupported())
  93.             throw die("Current thread CPU time not supported on this JRE"); //$NON-NLS-1$

  94.         if (gitDirs.isEmpty()) {
  95.             RepositoryBuilder rb = new RepositoryBuilder() //
  96.                     .setGitDir(new File(gitdir)) //
  97.                     .readEnvironment() //
  98.                     .findGitDir();
  99.             if (rb.getGitDir() == null)
  100.                 throw die(CLIText.get().cantFindGitDirectory);
  101.             gitDirs.add(rb.getGitDir());
  102.         }

  103.         for (File dir : gitDirs) {
  104.             RepositoryBuilder rb = new RepositoryBuilder();
  105.             if (RepositoryCache.FileKey.isGitRepository(dir, FS.DETECTED))
  106.                 rb.setGitDir(dir);
  107.             else
  108.                 rb.findGitDir(dir);

  109.             try (Repository repo = rb.build()) {
  110.                 run(repo);
  111.             }
  112.         }
  113.     }

  114.     private void run(Repository repo) throws Exception {
  115.         List<Test> all = init();

  116.         long files = 0;
  117.         int commits = 0;
  118.         int minN = Integer.MAX_VALUE;
  119.         int maxN = 0;

  120.         AbbreviatedObjectId startId;
  121.         try (ObjectReader or = repo.newObjectReader();
  122.             RevWalk rw = new RevWalk(or)) {
  123.             final MutableObjectId id = new MutableObjectId();
  124.             TreeWalk tw = new TreeWalk(or);
  125.             tw.setFilter(TreeFilter.ANY_DIFF);
  126.             tw.setRecursive(true);

  127.             ObjectId start = repo.resolve(Constants.HEAD);
  128.             startId = or.abbreviate(start);
  129.             rw.markStart(rw.parseCommit(start));
  130.             for (;;) {
  131.                 final RevCommit c = rw.next();
  132.                 if (c == null)
  133.                     break;
  134.                 commits++;
  135.                 if (c.getParentCount() != 1)
  136.                     continue;

  137.                 RevCommit p = c.getParent(0);
  138.                 rw.parseHeaders(p);
  139.                 tw.reset(p.getTree(), c.getTree());
  140.                 while (tw.next()) {
  141.                     if (!isFile(tw, 0) || !isFile(tw, 1))
  142.                         continue;

  143.                     byte[] raw0;
  144.                     try {
  145.                         tw.getObjectId(id, 0);
  146.                         raw0 = or.open(id).getCachedBytes(textLimit * 1024);
  147.                     } catch (LargeObjectException tooBig) {
  148.                         continue;
  149.                     }
  150.                     if (RawText.isBinary(raw0, raw0.length, true))
  151.                         continue;

  152.                     byte[] raw1;
  153.                     try {
  154.                         tw.getObjectId(id, 1);
  155.                         raw1 = or.open(id).getCachedBytes(textLimit * 1024);
  156.                     } catch (LargeObjectException tooBig) {
  157.                         continue;
  158.                     }
  159.                     if (RawText.isBinary(raw1, raw1.length, true))
  160.                         continue;

  161.                     RawText txt0 = new RawText(raw0);
  162.                     RawText txt1 = new RawText(raw1);

  163.                     minN = Math.min(minN, txt0.size() + txt1.size());
  164.                     maxN = Math.max(maxN, txt0.size() + txt1.size());

  165.                     for (Test test : all)
  166.                         testOne(test, txt0, txt1);
  167.                     files++;
  168.                 }
  169.                 if (count > 0 && files > count)
  170.                     break;
  171.             }
  172.         }

  173.         Collections.sort(all, (Test a, Test b) -> {
  174.             int result = Long.signum(a.runningTimeNanos - b.runningTimeNanos);
  175.             if (result == 0) {
  176.                 result = a.algorithm.name.compareTo(b.algorithm.name);
  177.             }
  178.             return result;
  179.         });

  180.         File directory = repo.getDirectory();
  181.         if (directory != null) {
  182.             String name = directory.getName();
  183.             File parent = directory.getParentFile();
  184.             if (name.equals(Constants.DOT_GIT) && parent != null)
  185.                 name = parent.getName();
  186.             outw.println(name + ": start at " + startId.name()); //$NON-NLS-1$
  187.         }

  188.         outw.format("  %12d files,     %8d commits\n", valueOf(files), //$NON-NLS-1$
  189.                 valueOf(commits));
  190.         outw.format("  N=%10d min lines, %8d max lines\n", valueOf(minN), //$NON-NLS-1$
  191.                 valueOf(maxN));

  192.         outw.format("%-25s %12s ( %12s  %12s )\n", //$NON-NLS-1$
  193.                 "Algorithm", "Time(ns)", "Time(ns) on", "Time(ns) on"); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
  194.         outw.format("%-25s %12s ( %12s  %12s )\n", //$NON-NLS-1$
  195.                 "", "", "N=" + minN, "N=" + maxN); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$ //$NON-NLS-4$
  196.         outw.println("-----------------------------------------------------" //$NON-NLS-1$
  197.                 + "----------------"); //$NON-NLS-1$

  198.         for (Test test : all) {
  199.             outw.format("%-25s %12d ( %12d  %12d )", // //$NON-NLS-1$
  200.                     test.algorithm.name, //
  201.                     valueOf(test.runningTimeNanos), //
  202.                     valueOf(test.minN.runningTimeNanos), //
  203.                     valueOf(test.maxN.runningTimeNanos));
  204.             outw.println();
  205.         }
  206.         outw.println();
  207.         outw.flush();
  208.     }

  209.     private static boolean isFile(TreeWalk tw, int ithTree) {
  210.         FileMode fm = tw.getFileMode(ithTree);
  211.         return FileMode.REGULAR_FILE.equals(fm)
  212.                 || FileMode.EXECUTABLE_FILE.equals(fm);
  213.     }

  214.     private static final int minCPUTimerTicks = 10;

  215.     private void testOne(Test test, RawText a, RawText b) {
  216.         final DiffAlgorithm da = test.algorithm.create();
  217.         int cpuTimeChanges = 0;
  218.         int cnt = 0;

  219.         final long startTime = mxBean.getCurrentThreadCpuTime();
  220.         long lastTime = startTime;
  221.         while (cpuTimeChanges < minCPUTimerTicks) {
  222.             da.diff(cmp, a, b);
  223.             cnt++;

  224.             long interimTime = mxBean.getCurrentThreadCpuTime();
  225.             if (interimTime != lastTime) {
  226.                 cpuTimeChanges++;
  227.                 lastTime = interimTime;
  228.             }
  229.         }
  230.         final long stopTime = mxBean.getCurrentThreadCpuTime();
  231.         final long runTime = (stopTime - startTime) / cnt;

  232.         test.runningTimeNanos += runTime;

  233.         if (test.minN == null || a.size() + b.size() < test.minN.n) {
  234.             test.minN = new Run();
  235.             test.minN.n = a.size() + b.size();
  236.             test.minN.runningTimeNanos = runTime;
  237.         }

  238.         if (test.maxN == null || a.size() + b.size() > test.maxN.n) {
  239.             test.maxN = new Run();
  240.             test.maxN.n = a.size() + b.size();
  241.             test.maxN.runningTimeNanos = runTime;
  242.         }
  243.     }

  244.     private List<Test> init() {
  245.         List<Test> all = new ArrayList<>();

  246.         try {
  247.             for (Field f : DiffAlgorithms.class.getDeclaredFields()) {
  248.                 if (f.getType() == Algorithm.class) {
  249.                     f.setAccessible(true);
  250.                     Algorithm alg = (Algorithm) f.get(this);
  251.                     alg.name = f.getName();
  252.                     if (included(alg.name, algorithms)) {
  253.                         Test test = new Test();
  254.                         test.algorithm = alg;
  255.                         all.add(test);
  256.                     }
  257.                 }
  258.             }
  259.         } catch (IllegalArgumentException | IllegalAccessException e) {
  260.             throw die("Cannot determine names", e); //$NON-NLS-1$
  261.         }
  262.         return all;
  263.     }

  264.     private static boolean included(String name, List<String> want) {
  265.         if (want.isEmpty())
  266.             return true;
  267.         for (String s : want) {
  268.             if (s.equalsIgnoreCase(name))
  269.                 return true;
  270.         }
  271.         return false;
  272.     }

  273.     private abstract static class Algorithm {
  274.         String name;

  275.         abstract DiffAlgorithm create();
  276.     }

  277.     private static class Test {
  278.         Algorithm algorithm;

  279.         long runningTimeNanos;

  280.         Run minN;

  281.         Run maxN;
  282.     }

  283.     private static class Run {
  284.         int n;

  285.         long runningTimeNanos;
  286.     }
  287. }