1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.pgm.debug;
12
13 import static java.lang.Integer.valueOf;
14 import static java.lang.Long.valueOf;
15
16 import java.io.File;
17 import java.lang.management.ManagementFactory;
18 import java.lang.management.ThreadMXBean;
19 import java.lang.reflect.Field;
20 import java.util.ArrayList;
21 import java.util.Collections;
22 import java.util.List;
23
24 import org.eclipse.jgit.diff.DiffAlgorithm;
25 import org.eclipse.jgit.diff.HistogramDiff;
26 import org.eclipse.jgit.diff.MyersDiff;
27 import org.eclipse.jgit.diff.RawText;
28 import org.eclipse.jgit.diff.RawTextComparator;
29 import org.eclipse.jgit.errors.LargeObjectException;
30 import org.eclipse.jgit.lib.AbbreviatedObjectId;
31 import org.eclipse.jgit.lib.Constants;
32 import org.eclipse.jgit.lib.FileMode;
33 import org.eclipse.jgit.lib.MutableObjectId;
34 import org.eclipse.jgit.lib.ObjectId;
35 import org.eclipse.jgit.lib.ObjectReader;
36 import org.eclipse.jgit.lib.Repository;
37 import org.eclipse.jgit.lib.RepositoryBuilder;
38 import org.eclipse.jgit.lib.RepositoryCache;
39 import org.eclipse.jgit.pgm.Command;
40 import org.eclipse.jgit.pgm.TextBuiltin;
41 import org.eclipse.jgit.pgm.internal.CLIText;
42 import org.eclipse.jgit.revwalk.RevCommit;
43 import org.eclipse.jgit.revwalk.RevWalk;
44 import org.eclipse.jgit.treewalk.TreeWalk;
45 import org.eclipse.jgit.treewalk.filter.TreeFilter;
46 import org.eclipse.jgit.util.FS;
47 import org.kohsuke.args4j.Option;
48
49 @Command(usage = "usage_DiffAlgorithms")
50 class DiffAlgorithms extends TextBuiltin {
51
52 final Algorithm myers = new Algorithm() {
53 @Override
54 DiffAlgorithm create() {
55 return MyersDiff.INSTANCE;
56 }
57 };
58
59 final Algorithm histogram = new Algorithm() {
60 @Override
61 DiffAlgorithm create() {
62 HistogramDiff d = new HistogramDiff();
63 d.setFallbackAlgorithm(null);
64 return d;
65 }
66 };
67
68 final Algorithm histogram_myers = new Algorithm() {
69 @Override
70 DiffAlgorithm create() {
71 HistogramDiff d = new HistogramDiff();
72 d.setFallbackAlgorithm(MyersDiff.INSTANCE);
73 return d;
74 }
75 };
76
77
78
79
80
81
82
83 @Option(name = "--algorithm", metaVar = "NAME", usage = "Enable algorithm(s)")
84 List<String> algorithms = new ArrayList<>();
85
86 @Option(name = "--text-limit", metaVar = "LIMIT", usage = "Maximum size in KiB to scan per file revision")
87 int textLimit = 15 * 1024;
88
89 @Option(name = "--repository", aliases = { "-r" }, metaVar = "GIT_DIR", usage = "Repository to scan")
90 List<File> gitDirs = new ArrayList<>();
91
92 @Option(name = "--count", metaVar = "LIMIT", usage = "Number of file revisions to be compared")
93 int count = 0;
94
95 private final RawTextComparator cmp = RawTextComparator.DEFAULT;
96
97 private ThreadMXBean mxBean;
98
99
100 @Override
101 protected boolean requiresRepository() {
102 return false;
103 }
104
105
106 @Override
107 protected void run() throws Exception {
108 mxBean = ManagementFactory.getThreadMXBean();
109 if (!mxBean.isCurrentThreadCpuTimeSupported())
110 throw die("Current thread CPU time not supported on this JRE");
111
112 if (gitDirs.isEmpty()) {
113 RepositoryBuilder rb = new RepositoryBuilder()
114 .setGitDir(new File(gitdir))
115 .readEnvironment()
116 .findGitDir();
117 if (rb.getGitDir() == null)
118 throw die(CLIText.get().cantFindGitDirectory);
119 gitDirs.add(rb.getGitDir());
120 }
121
122 for (File dir : gitDirs) {
123 RepositoryBuilder rb = new RepositoryBuilder();
124 if (RepositoryCache.FileKey.isGitRepository(dir, FS.DETECTED))
125 rb.setGitDir(dir);
126 else
127 rb.findGitDir(dir);
128
129 try (Repository repo = rb.build()) {
130 run(repo);
131 }
132 }
133 }
134
135 private void run(Repository repo) throws Exception {
136 List<Test> all = init();
137
138 long files = 0;
139 int commits = 0;
140 int minN = Integer.MAX_VALUE;
141 int maxN = 0;
142
143 AbbreviatedObjectId startId;
144 try (ObjectReader or = repo.newObjectReader();
145 RevWalk rw = new RevWalk(or)) {
146 final MutableObjectId id = new MutableObjectId();
147 TreeWalk tw = new TreeWalk(or);
148 tw.setFilter(TreeFilter.ANY_DIFF);
149 tw.setRecursive(true);
150
151 ObjectId start = repo.resolve(Constants.HEAD);
152 startId = or.abbreviate(start);
153 rw.markStart(rw.parseCommit(start));
154 for (;;) {
155 final RevCommit c = rw.next();
156 if (c == null)
157 break;
158 commits++;
159 if (c.getParentCount() != 1)
160 continue;
161
162 RevCommit p = c.getParent(0);
163 rw.parseHeaders(p);
164 tw.reset(p.getTree(), c.getTree());
165 while (tw.next()) {
166 if (!isFile(tw, 0) || !isFile(tw, 1))
167 continue;
168
169 byte[] raw0;
170 try {
171 tw.getObjectId(id, 0);
172 raw0 = or.open(id).getCachedBytes(textLimit * 1024);
173 } catch (LargeObjectException tooBig) {
174 continue;
175 }
176 if (RawText.isBinary(raw0, raw0.length, true))
177 continue;
178
179 byte[] raw1;
180 try {
181 tw.getObjectId(id, 1);
182 raw1 = or.open(id).getCachedBytes(textLimit * 1024);
183 } catch (LargeObjectException tooBig) {
184 continue;
185 }
186 if (RawText.isBinary(raw1, raw1.length, true))
187 continue;
188
189 RawText txt0 = new RawText(raw0);
190 RawText txt1 = new RawText(raw1);
191
192 minN = Math.min(minN, txt0.size() + txt1.size());
193 maxN = Math.max(maxN, txt0.size() + txt1.size());
194
195 for (Test test : all)
196 testOne(test, txt0, txt1);
197 files++;
198 }
199 if (count > 0 && files > count)
200 break;
201 }
202 }
203
204 Collections.sort(all, (Test a, Test b) -> {
205 int result = Long.signum(a.runningTimeNanos - b.runningTimeNanos);
206 if (result == 0) {
207 result = a.algorithm.name.compareTo(b.algorithm.name);
208 }
209 return result;
210 });
211
212 File directory = repo.getDirectory();
213 if (directory != null) {
214 String name = directory.getName();
215 File parent = directory.getParentFile();
216 if (name.equals(Constants.DOT_GIT) && parent != null)
217 name = parent.getName();
218 outw.println(name + ": start at " + startId.name());
219 }
220
221 outw.format(" %12d files, %8d commits\n", valueOf(files),
222 valueOf(commits));
223 outw.format(" N=%10d min lines, %8d max lines\n", valueOf(minN),
224 valueOf(maxN));
225
226 outw.format("%-25s %12s ( %12s %12s )\n",
227 "Algorithm", "Time(ns)", "Time(ns) on", "Time(ns) on");
228 outw.format("%-25s %12s ( %12s %12s )\n",
229 "", "", "N=" + minN, "N=" + maxN);
230 outw.println("-----------------------------------------------------"
231 + "----------------");
232
233 for (Test test : all) {
234 outw.format("%-25s %12d ( %12d %12d )",
235 test.algorithm.name,
236 valueOf(test.runningTimeNanos),
237 valueOf(test.minN.runningTimeNanos),
238 valueOf(test.maxN.runningTimeNanos));
239 outw.println();
240 }
241 outw.println();
242 outw.flush();
243 }
244
245 private static boolean isFile(TreeWalk tw, int ithTree) {
246 FileMode fm = tw.getFileMode(ithTree);
247 return FileMode.REGULAR_FILE.equals(fm)
248 || FileMode.EXECUTABLE_FILE.equals(fm);
249 }
250
251 private static final int minCPUTimerTicks = 10;
252
253 private void testOne(Test test, RawText a, RawText b) {
254 final DiffAlgorithm da = test.algorithm.create();
255 int cpuTimeChanges = 0;
256 int cnt = 0;
257
258 final long startTime = mxBean.getCurrentThreadCpuTime();
259 long lastTime = startTime;
260 while (cpuTimeChanges < minCPUTimerTicks) {
261 da.diff(cmp, a, b);
262 cnt++;
263
264 long interimTime = mxBean.getCurrentThreadCpuTime();
265 if (interimTime != lastTime) {
266 cpuTimeChanges++;
267 lastTime = interimTime;
268 }
269 }
270 final long stopTime = mxBean.getCurrentThreadCpuTime();
271 final long runTime = (stopTime - startTime) / cnt;
272
273 test.runningTimeNanos += runTime;
274
275 if (test.minN == null || a.size() + b.size() < test.minN.n) {
276 test.minN = new Run();
277 test.minN.n = a.size() + b.size();
278 test.minN.runningTimeNanos = runTime;
279 }
280
281 if (test.maxN == null || a.size() + b.size() > test.maxN.n) {
282 test.maxN = new Run();
283 test.maxN.n = a.size() + b.size();
284 test.maxN.runningTimeNanos = runTime;
285 }
286 }
287
288 private List<Test> init() {
289 List<Test> all = new ArrayList<>();
290
291 try {
292 for (Field f : DiffAlgorithms.class.getDeclaredFields()) {
293 if (f.getType() == Algorithm.class) {
294 f.setAccessible(true);
295 Algorithm alg = (Algorithm) f.get(this);
296 alg.name = f.getName();
297 if (included(alg.name, algorithms)) {
298 Test test = new Test();
299 test.algorithm = alg;
300 all.add(test);
301 }
302 }
303 }
304 } catch (IllegalArgumentException | IllegalAccessException e) {
305 throw die("Cannot determine names", e);
306 }
307 return all;
308 }
309
310 private static boolean included(String name, List<String> want) {
311 if (want.isEmpty())
312 return true;
313 for (String s : want) {
314 if (s.equalsIgnoreCase(name))
315 return true;
316 }
317 return false;
318 }
319
320 private abstract static class Algorithm {
321 String name;
322
323 abstract DiffAlgorithm create();
324 }
325
326 private static class Test {
327 Algorithm algorithm;
328
329 long runningTimeNanos;
330
331 Run minN;
332
333 Run maxN;
334 }
335
336 private static class Run {
337 int n;
338
339 long runningTimeNanos;
340 }
341 }