patch, 3 partsdiff --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 <junkio@cox.net>
---

 * 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(-)

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

David Rientjes <rientjes@cs.washington.edu> writes:

I won't comment on this one.  See list archives ;-).

What's happening here in this particular case is:

	if the changes fits within the alloted width
		; /* we do not have to do anything */
	else if we are using non-linear scale {
               	scale it like this
	}
	else {
               	scale it like that
	}

so the code actually matches the flow of thought perfectly well.

I first tried to write it without "if () ;/*empty*/ else" chain like this:

	if given width is narrower than changes we have {
        	if we are doing non-linear scale {
                	scale it like this
                }
                else {
                	scale it like that
		}
	}

It made the indentation unnecessarily deep.

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

I'm very familiar with the list archives and your support of writing relationals like 0 < x. It's a matter of taste. And since the large majority of programmers in any language write x > 0 instead, I think it's preferrable to write code that is in the style and taste of the majority.

Large software projects require a conformity in the style in which the code is written. Granted the git developer community is small, there is still a need for this confomity so that developers don't have to put up with the subtleties in the style of which individuals decide to code.

When I read "x > 0", my mind parses that very easily. When I read "0 < x", it takes me a few cycles longer. I think the goal of any software project is to not only emit efficient and quality code, but also code that can be read and deciphered with ease unless it's impossible otherwise.

To change the code itself because of a hard 80-column limit or because you're tired of hitting the tab key is poor style. The idents are there for a purpose: it tells the reader that the code is inside a block. So when this conditional becomes a screen wide, I can understand it on the second screen and remember that I'm inside a conditional and not rely on the previous 'else' to jog my memory. C is not a whitespace-dependent language like Python, but since when did idents (which are there _solely_ for the purpose of helping the reader) become deprecated?

		David

David Rientjes <rientjes@cs.washington.edu> writes:

Well, the thing is, I end up being the guy who needs to stare at git code longer than you do ;-).

Before --stat-width was introduced there was code like this:

	if (max + len > 70)
		max = 70 - len;

Here "len" is the width of the filename part, and "max" is the number of changes we need to express. The code is saying "if we use one column for each changed line, does graph and name exceed 70 columns -- if so use the remainder of the line after we write name for the graph". Your "constant at right" rule makes this kosher.

If we make that to a variable, say line_width, we can still write:

	if (max + len > line_width)
        	...

I however tend to think "if line_width cannot fit (max + len) then we do this", which would be more naturally expressed with:

	if (line_width < max + len)
        	...

Now, at this point, it is really the matter of taste and there is no real reason to prefer one over the other. Textual ordering lets my eyes coast while reading the code without taxing the brain. I can see that the expression compares two quantities, "line_width" and "max + len", and the boolean holds true if line_width _comes_ _before_ "max + len" on the number line (having number line in your head helps visualizing what is compared with what). If you write the comparison the wrong way, it forces me to stop and think -- because on my number line smaller numbers appear left, and cannot help me reading the comparison written in "a > b" order.

I could try writing constants on the right hand side when constants are involved, but I do not think it makes much sense. It means that I would end up doing:

- if (max + len > 70) - max = 70 - len; + if (line_width < max + len) + max = line_width - len;

Consistency counts not only while reading the finished code, but also it helps reviewing the diff between the earlier version that used constant (hence forced to have it on the right hand side by your rule) and the version that made it into a variable.

Well, the program _firstly_ matches the logic flow better, and _in_ _addition_ if you write it another way it becomes unnecessarily too deeply indented. So while I agree with you as a general principle that indentation depth should not dictate how we code it does not apply to this particular example.

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

Really? This is the only community that hacks git? There _are_ people out there that make their own changes specifically tailored to their purposes or that of their organization.

First of all, it's not my "constant at right" rule, it's a preference that the _majority_ of computer programmers have used in virtually every language that you see source code for.

The grammar for C is

  relational-expression:
	shift-expression
	relational-expression < shift-expression

in this case. Now while this supports both your variations above, it _suggests_ that the higher degree of computation is associated on the left side because the less-than operator associates that way.

What happens here:
	a < b < c

it turns out that this is equivalent to:
	(a < b) < c

so if you want your entire code base to conform to a particular style, it's _preferable_ to place the constant on the right. And that's what the majority of programmers do. Your taste is in the minority and out of respect to the code base you should make your code conform to what is most popular in the surrounding code.

Your argument of saying to yourself "if line_width cannot fit max + len then we do this" has no relevance at all. I can say "if max + len is too big for line_width we do this" just the same.

If we're going by what sounds better in your head, then I expect _no_ argument when I write a function called conseguir_la_linea_longitud instead of get_line_length because Spanish is my first language.

Please respect what the majority of computer programmers write and unify the code base so that it's a similar style everywhere.

This is a ridiculous argument. The C code will emit the exact same assembly regardless of how you write it. You say that you wrote it that way to avoid idents which is an absolutely horrible way to dictate the code you use. There are tons of opportunities where you can write cryptic source code that functions great with the least number of tokens and least number of lines to get the job done in every large project. But, given that there are no assembler or performance tradeoffs, it should be written as clearly and nicely as possible for the reader. I assert again what I did previously: if that if clause runs the length of my screen the indents will help me later to remember we're still in a conditional. That's the SOLE purpose of indents: to make it easy for the reader to tell you're inside a block.

And in one of your patches you had:
	if (...)
		;
	else {
		...
	}

without any other if statements. If you're supporting that type of code, I'll simply consider this entire thread a lost cause.

		David

David Rientjes <rientjes@cs.washington.edu> writes:

Actually that is exactly my point. "Just the same". There is no reason to choose one way or the other from purely logical or mathematical point of view.

Comparisons written always in textual order, when one gets used to, takes less thinking to parse and understand, and that is what I'm used to. Have number line handy in your head and you will hopefully like it too ;-).

I guess probably I was unclear (I did not talk anything about code generation -- where did it come from?). I say I wrote it that way _firstly_ because the flow of the program matches exactly what I saw the code needed to do -- if A I do not have to do anything else if B I do this else I do that. In addition not having that "do nothing" made the code indent unnecessarily deep but that is "in addition" and not the primary cause. It was an added bonus.

Yes, indeed that was very funny looking.

It was refactored from the final one that had "else if" in the middle (else if was to add the non-linear scaling). I agree that any sane would not have done that if that was the real first version.

On Wed, 27 Sep 2006, Junio C Hamano wrote:

Nothing about this is "mathematical" at all and I never claimed it was. But there _is_ a reason to choose one way over the other and that is because the MAJORITY of programmers do it one way and YOU do it another way. Why is it so hard to write all the code in the same style so that there is as little variation in the code as possible?

Doing what you prefer and not what the majority of your developers do is the first step to a stagnant source tree.

The concept of code generation is the whole point. Both of our styles emits the same assembly code so by definition there is no difference since it achieves the exact same goal. But there's a reason git is written in C and not in assembly and that reason is not just for portability. A .c source file is the bridge between most programmers and assembly and since our coding styles differ but emit the same assembly, then it inherently comes with a freedom in how it's written. And on a collaborative project such as git, that freedom should be confined to resembling the surrounding source code.

		David

Hi,

On Wed, 27 Sep 2006, David Rientjes wrote:

Could you stop it already?

Git's source code is very clean and readable, even if there are inversions you might not be used to.

Besides, always doing it the same way is boring. _Boring_. Or do you make love to your girl-friend the same way over and over again?

Ciao, Dscho

Dear diary, on Wed, Sep 27, 2006 at 09:50:11AM CEST, I got a letter where Johannes Schindelin <Johannes.Schindelin@gmx.de> said that...

I think it's a good sign that _this_ is what we argue about. ;-)

Hi,

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

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:

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.

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

Ok, this is just _strange_.

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:

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 <tali@admingilde.org> writes:

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:

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.

Hi,

On Wed, 27 Sep 2006, Sean wrote:

In this case, though, "English" is utterly, totally irrelevant. The question is a mathematical one, and thus, the solution is a mathematical one.

So, in essence, if you do not understand a conditional with a constant on the left side, just because it happens to honour the mathematical view of "left is small, right is large", you do not stand a chance of understanding the formula, right?

Oh, come on! You cannot possibly spend even _seconds_ on this particular construct!

'nough said.

Ciao, Dscho

On Wed, 27 Sep 2006 10:35:16 +0200 (CEST) Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

Well, no.. At least for me, I "think" in english, not mathematics. And thus I have to understand each condition in my native language. And i'm being honest with you when I tell you that my parser hiccups every time I see such a construct.

It's not a matter of being able to understand, it's being able to digest at a glance, almost without a thought as opposed to consciously having to rearrange the arguments into something that "feels" right.

I'm telling you that it is disconcerting and annoying to have to rejig such a construct. Whereas when expressed in the opposite format it makes reading simple and natural. Making the code easier and more pleasurable to read.

And if you find it so easy to read either way, then why not bend for those of us who have trouble reading it your way instead of just telling us to get stuffed?

Sean