[PATCH 3/3] diff --stat: sometimes use non-linear scaling.

When some files have big changes and others are touched only
slightly, diffstat graph did not show differences among smaller
changes that well.  This changes the graph scaling to non-linear
algorithm in such a case.

Without this, "git show --stat fd88d9c" gives:

 .gitignore                       |    1
 Documentation/git-tar-tree.txt   |    3 +
 Documentation/git-upload-tar.txt |   39 -----------
 Documentation/git.txt            |    4 -
 Makefile                         |    1
 builtin-tar-tree.c               |  130 +++++++++++++++-----------------------
 builtin-upload-tar.c             |   74 ----------------------
 git.c                            |    1
 8 files changed, 53 insertions(+), 200 deletions(-)

while with this, it shows:

 .gitignore                       |    1
 Documentation/git-tar-tree.txt   |    3 +++++++++
 Documentation/git-upload-tar.txt |   39 -----------------------------
 Documentation/git.txt            |    4 -----------
 Makefile                         |    1
 builtin-tar-tree.c               |  130 +++++++++++++++-----------------------
 builtin-upload-tar.c             |   74 ----------------------------------
 git.c                            |    1
 8 files changed, 53 insertions(+), 200 deletions(-)

Signed-off-by: Junio C Hamano <redacted>
---

 * Jan Engelhardt wondered about doing non-linear scaling on the
   kernel list and this is an experimental patch to do so.  I do
   not seriously consider this for inclusion but it is more of a
   "see if people like it" patch.

 Makefile |    2 +-
 diff.c   |   29 +++++++++++++++++++++++++++--
 2 files changed, 28 insertions(+), 3 deletions(-)

diff --git a/Makefile b/Makefile
index 28091d6..0fc59c4 100644
--- a/Makefile
+++ b/Makefile

@@ -304,7 +304,7 @@ BUILTIN_OBJS = \
 	builtin-write-tree.o
 
 GITLIBS = $(LIB_FILE) $(XDIFF_LIB)
-LIBS = $(GITLIBS) -lz
+LIBS = $(GITLIBS) -lz -lm
 
 #
 # Platform specific tweaks

diff --git a/diff.c b/diff.c
index 13aac2d..163ef48 100644
--- a/diff.c
+++ b/diff.c

@@ -4,6 +4,7 @@
 #include <sys/types.h>
 #include <sys/wait.h>
 #include <signal.h>
+#include <math.h>
 #include "cache.h"
 #include "quote.h"
 #include "diff.h"

@@ -555,6 +556,16 @@ static int scale_linear(int it, int widt
 	return (it * width * 2 + max_change) / (max_change * 2);
 }
 
+static int scale_non_linear(int it, int width, int max_change)
+{
+	/*
+	 * round(width * log(it)/log(max_change))
+	 */
+	if (!it || !max_change)
+		return 0;
+	return (int)(0.5 + width * log(it) / log(max_change));
+}
+
 static void show_name(const char *prefix, const char *name, int len,
 		      const char *reset, const char *set)
 {

@@ -574,10 +585,11 @@ static void show_graph(char ch, int cnt,
 static void show_stats(struct diffstat_t* data, struct diff_options *options)
 {
 	int i, len, add, del, total, adds = 0, dels = 0;
-	int max_change = 0, max_len = 0;
+	int max_change = 0, max_len = 0, min_change = 0;
 	int total_files = data->nr;
 	int width, name_width;
 	const char *reset, *set, *add_c, *del_c;
+	int non_linear_scale = 0;
 
 	if (data->nr == 0)
 		return;

@@ -595,12 +607,12 @@ static void show_stats(struct diffstat_t
 			width = name_width + 15;
 	}
 
-	/* Find the longest filename and max number of changes */
 	reset = diff_get_color(options->color_diff, DIFF_RESET);
 	set = diff_get_color(options->color_diff, DIFF_PLAIN);
 	add_c = diff_get_color(options->color_diff, DIFF_FILE_NEW);
 	del_c = diff_get_color(options->color_diff, DIFF_FILE_OLD);
 
+	/* Find the longest filename and max/min number of changes */
 	for (i = 0; i < data->nr; i++) {
 		struct diffstat_file *file = data->files[i];
 		int change = file->added + file->deleted;

@@ -620,6 +632,8 @@ static void show_stats(struct diffstat_t
 			continue;
 		if (max_change < change)
 			max_change = change;
+		if (0 < change && (!min_change || change < min_change))
+			min_change = change;
 	}
 
 	/* Compute the width of the graph part;

@@ -635,6 +649,12 @@ static void show_stats(struct diffstat_t
 	else
 		width = max_change;
 
+	/* See if the minimum change is shown with the normal scale
+	 * and if not switch to non-linear scale
+	 */
+	if (min_change && !scale_linear(min_change, width, max_change))
+		non_linear_scale = 1;
+
 	for (i = 0; i < data->nr; i++) {
 		const char *prefix = "";
 		char *name = data->files[i]->name;

@@ -684,6 +704,11 @@ static void show_stats(struct diffstat_t
 
 		if (max_change < width)
 			;
+		else if (non_linear_scale) {
+			total = scale_non_linear(total, width, max_change);
+			add = scale_linear(add, total, add + del);
+			del = total - add;
+		}
 		else {
 			total = scale_linear(total, width, max_change);
 			add = scale_linear(add, width, max_change);

-- 
1.4.2.1.gf80a

On Tue, 26 Sep 2006, Junio C Hamano wrote:

Again with the constant placement in a comparison expression.

if (...)
	;
else if {
	...
}

is _never_ necessary.

		David

Hi,

On Tue, 26 Sep 2006, Junio C Hamano wrote:

When some files have big changes and others are touched only
slightly, diffstat graph did not show differences among smaller
changes that well.  This changes the graph scaling to non-linear
algorithm in such a case.

I want to say something about the purpose of the patch, not some totally 
unimportant superficialities.

In your example, a three line change has more than three plusses, and I 
find that wrong.

But I would actually find another change very useful: still linear, but 
such that if lines were added, at least one plus should be shown, and 
likewise with minus. (Often I ask myself, was this file removed, or just 
dramatically reduced, when I only see minusses).

Ciao,
Dscho

hoi :)

On Tue, Sep 26, 2006 at 07:40:53PM -0700, Junio C Hamano wrote:

 .gitignore                       |    1
 Documentation/git-tar-tree.txt   |    3 +++++++++
 Documentation/git-upload-tar.txt |   39 -----------------------------
 Documentation/git.txt            |    4 -----------
 Makefile                         |    1
 builtin-tar-tree.c               |  130 +++++++++++++++-----------------------
 builtin-upload-tar.c             |   74 ----------------------------------
 git.c                            |    1
 8 files changed, 53 insertions(+), 200 deletions(-)

hmm, the small changes (1 line) are still not shown :-(.
I like the idea of non-linear display, but we have to fine-tune the
algorithm a little bit more.

-- 
Martin Waitz

On Tue, 26 Sep 2006, Junio C Hamano wrote:

When some files have big changes and others are touched only
slightly, diffstat graph did not show differences among smaller
changes that well.  This changes the graph scaling to non-linear
algorithm in such a case.

Ok, this is just _strange_.

while with this, it shows:

 .gitignore                       |    1
 Documentation/git-tar-tree.txt   |    3 +++++++++

No _way_ is it correct to show more than three characters if there were 
three lines of changes.

I think "nonlinear" is fine, but this is something that is "superlinear" 
in small changes, and then sublinear in bigger ones (and then apparently 
totally wrong for one-line changes).

It should at least never be superlinear, I believe.

		Linus

hoi :)

On Wed, Sep 27, 2006 at 08:12:49AM -0700, Linus Torvalds wrote:

No _way_ is it correct to show more than three characters if there were 
three lines of changes.

I think "nonlinear" is fine, but this is something that is "superlinear" 
in small changes, and then sublinear in bigger ones (and then apparently 
totally wrong for one-line changes).

It should at least never be superlinear, I believe.

So if we want to keep the logarithmic scale we can do some maths:

Assume we use a formula ala

	length = a log(change + b) + c

with three invariants a, b, and c.

We want to scale linearly at first, but want to reach width at
max_change:

	0 = a log(b) + c
	1 = a log(b + 1) + c
	width = a log(max_change + b) + c

But only I have not succeeded in solving these equations, I always stop
at the last invariant :-(

-- 
Martin Waitz

Martin Waitz [off-list ref] writes:

quoted

It should at least never be superlinear, I believe.

So if we want to keep the logarithmic scale we can do some maths:
...
But only I have not succeeded in solving these equations, I always stop
at the last invariant :-(

There is another constraint you did not mention.  Here is the
output from my another failed experiment:

 .gitignore                       |    1 -
 Documentation/git-tar-tree.txt   |    3 +++
 Documentation/git-upload-tar.txt |   39 -----------------------------
 Documentation/git.txt            |    4 ----
 Makefile                         |    1 -
 builtin-tar-tree.c               |  130 +++++++++++++++-----------------------
 builtin-upload-tar.c             |   74 ----------------------------------
 git.c                            |    1 -
 8 files changed, 53 insertions(+), 200 deletions(-)

The deletion from Documentation/git-upload-tar.txt looks much
larger than addition to builtin-tar-tree.c in the above, but
there are 50 lines added to builtin-tar-tree.c (which is why
this experiment is a failure).

Because we are dealing with non-linear scaling, the total of
scaled adds and scaled deletes does not equal to scaled total.
We can deal with this in two ways.  Scale the total and
distribute it, or scale adds and deletes individually and make
sure the sum of scaled adds and deletes never exceed the width.
Obviously the former is easier to implement but it was _wrong_.

The fitting algorithm in the posted patch scales the total to
fit the alloted width and then distributes the result to adds
and deletes.

Junio C Hamano wrote:

Martin Waitz [off-list ref] writes:

quoted

quoted

It should at least never be superlinear, I believe.

So if we want to keep the logarithmic scale we can do some maths:
...
But only I have not succeeded in solving these equations, I always stop
at the last invariant :-(

There is another constraint you did not mention.  Here is the
output from my another failed experiment:

 .gitignore                       |    1 -
 Documentation/git-tar-tree.txt   |    3 +++
 Documentation/git-upload-tar.txt |   39 -----------------------------
 Documentation/git.txt            |    4 ----
 Makefile                         |    1 -
 builtin-tar-tree.c               |  130 +++++++++++++++-----------------------
 builtin-upload-tar.c             |   74 ----------------------------------
 git.c                            |    1 -
 8 files changed, 53 insertions(+), 200 deletions(-)

The deletion from Documentation/git-upload-tar.txt looks much
larger than addition to builtin-tar-tree.c in the above, but
there are 50 lines added to builtin-tar-tree.c (which is why
this experiment is a failure).

Because we are dealing with non-linear scaling, the total of
scaled adds and scaled deletes does not equal to scaled total.
We can deal with this in two ways.  Scale the total and
distribute it, or scale adds and deletes individually and make
sure the sum of scaled adds and deletes never exceed the width.
Obviously the former is easier to implement but it was _wrong_.

The fitting algorithm in the posted patch scales the total to
fit the alloted width and then distributes the result to adds
and deletes.

Why not just take the stupid and simple solution and make it:

file1   | +31,-19    +++
file2   | +19,-106   ---
file3   | +10,-10    ###

That is, show the number of lines that actually changed, and print a 
fixed number of plusses or minuses after the numbers to make it easy to, 
at a glance, check if more lines were added than deleted or vice versa.

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231