Feature request: Improve diff algorithm

Feature request: Improve diff algorithm

[KES]

Hi.

I have some question about how diff works then give proposal:

it will be very useful for each "symbol" store additional meta info as source line length. So in this case when git counter two equal sequence of commands it will do further comparison: Adds 23 chars deletes none VS adds 75 chars deletes 46

Actually I got this:

@@ -129,8 +132,9 @@ sub _preprocess_message {
 sub _process_message {
     my ($self, $message) = @_;

-    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
+    my $time =  [ gettimeofday ];

+    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
     return $self->send_error(ERROR_REQUEST_INVALID)
         unless defined($method);

Instead of expected:
@@ -129,6 +132,8 @@ sub _preprocess_message {
 sub _process_message {
     my ($self, $message) = @_;

+    my $time =  [ gettimeofday ];
+
     my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
-     
     return $self->send_error(ERROR_REQUEST_INVALID)


Details: http://stackoverflow.com/questions/40550751/unexpected-result-in-git-diff/40552165?noredirect=1#comment68648377_40552165

Re: Feature request: Improve diff algorithm

[Jacob Keller]

On Mon, Nov 21, 2016 at 12:11 AM, KES <kes-kes@yandex.ru> wrote:
> Hi.
>

Hi,

> I have some question about how diff works then give proposal:
>
> it will be very useful for each "symbol" store additional meta info as source line length. So in this case when git counter two equal sequence of commands it will do further comparison: Adds 23 chars deletes none VS adds 75 chars deletes 46
>
> Actually I got this:
>
> @@ -129,8 +132,9 @@ sub _preprocess_message {
>  sub _process_message {
>      my ($self, $message) = @_;
>
> -    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
> +    my $time =  [ gettimeofday ];
>
> +    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>      return $self->send_error(ERROR_REQUEST_INVALID)
>          unless defined($method);
>
> Instead of expected:
> @@ -129,6 +132,8 @@ sub _preprocess_message {
>  sub _process_message {
>      my ($self, $message) = @_;
>
> +    my $time =  [ gettimeofday ];
> +
>      my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
> -
>      return $self->send_error(ERROR_REQUEST_INVALID)
>

Have you tried the various options for git to search for smaller
diffs? Or using the other diff algorithms such as histogram instead of
patience?

Thanks,
Jake

Re: Feature request: Improve diff algorithm

[Stefan Beller]

On Mon, Nov 21, 2016 at 8:56 AM, Jacob Keller <jacob.keller@gmail.com> wrote:
> On Mon, Nov 21, 2016 at 12:11 AM, KES <kes-kes@yandex.ru> wrote:
>> Hi.
>>
>
> Hi,
>
>> I have some question about how diff works then give proposal:
>>
>> it will be very useful for each "symbol" store additional meta info as source line length. So in this case when git counter two equal sequence of commands it will do further comparison: Adds 23 chars deletes none VS adds 75 chars deletes 46
>>
>> Actually I got this:
>>
>> @@ -129,8 +132,9 @@ sub _preprocess_message {
>>  sub _process_message {
>>      my ($self, $message) = @_;
>>
>> -    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>> +    my $time =  [ gettimeofday ];
>>
>> +    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>      return $self->send_error(ERROR_REQUEST_INVALID)
>>          unless defined($method);
>>
>> Instead of expected:
>> @@ -129,6 +132,8 @@ sub _preprocess_message {
>>  sub _process_message {
>>      my ($self, $message) = @_;
>>
>> +    my $time =  [ gettimeofday ];
>> +
>>      my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>> -
>>      return $self->send_error(ERROR_REQUEST_INVALID)
>>
>
> Have you tried the various options for git to search for smaller
> diffs? Or using the other diff algorithms such as histogram instead of
> patience?
>

The newest version of Git comes with a flag to move around the diff
better, based on the work at https://github.com/mhagger/diff-slider-tools

Re: Feature request: Improve diff algorithm

[Jacob Keller]

On Mon, Nov 21, 2016 at 10:17 AM, Stefan Beller <sbeller@google.com> wrote:
> On Mon, Nov 21, 2016 at 8:56 AM, Jacob Keller <jacob.keller@gmail.com> wrote:
>> On Mon, Nov 21, 2016 at 12:11 AM, KES <kes-kes@yandex.ru> wrote:
>>> Hi.
>>>
>>
>> Hi,
>>
>>> I have some question about how diff works then give proposal:
>>>
>>> it will be very useful for each "symbol" store additional meta info as source line length. So in this case when git counter two equal sequence of commands it will do further comparison: Adds 23 chars deletes none VS adds 75 chars deletes 46
>>>
>>> Actually I got this:
>>>
>>> @@ -129,8 +132,9 @@ sub _preprocess_message {
>>>  sub _process_message {
>>>      my ($self, $message) = @_;
>>>
>>> -    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>> +    my $time =  [ gettimeofday ];
>>>
>>> +    my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>>      return $self->send_error(ERROR_REQUEST_INVALID)
>>>          unless defined($method);
>>>
>>> Instead of expected:
>>> @@ -129,6 +132,8 @@ sub _preprocess_message {
>>>  sub _process_message {
>>>      my ($self, $message) = @_;
>>>
>>> +    my $time =  [ gettimeofday ];
>>> +
>>>      my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>> -
>>>      return $self->send_error(ERROR_REQUEST_INVALID)
>>>
>>
>> Have you tried the various options for git to search for smaller
>> diffs? Or using the other diff algorithms such as histogram instead of
>> patience?
>>
>
> The newest version of Git comes with a flag to move around the diff
> better, based on the work at https://github.com/mhagger/diff-slider-tools

Unfortunately in this case, I'm not convinced that it will improve the
diff. It's worth a try as well though.

Thanks,
Jake

Re: Feature request: Improve diff algorithm

[KES]

Here is another place where diff can be improved:
@@ -141,8 +140,9 @@ My_runops(pTHX)
 		// Do not trace variables in DB:: module
 		if( SvOK( inDB ) ) continue;
 
-		sv_inc_nomg( inDB );
 
+		// save_item( inDB );
+		sv_inc_nomg( inDB );
 		dSP; SINFO; SAVETMPS;
 
 		// printf( "SWITCH\n" );


This would be better it the patch looks like:
( this patch is manually created just to light the idea. It may contain errors)
@@ -140,6 +140,7 @@ My_runops(pTHX)
         // Do not trace variables in DB:: module
         if( SvOK( inDB ) ) continue;

+ 
+        // save_item( inDB );
         sv_inc_nomg( inDB );
- 
         dSP; SINFO; SAVETMPS;

As we can see, here the `sv_inc_nomg( inDB );` line is unchanged and `// save_item( inDB );` is added.
Here we just add/remove empty lines and patch looks more better.

I think (and this is my assumption), the the diff algorithm should take into account the string length.
This is more better to add/remove more short lines

21.11.2016, 20:55, "Jacob Keller" <jacob.keller@gmail.com>:
> On Mon, Nov 21, 2016 at 10:17 AM, Stefan Beller <sbeller@google.com> wrote:
>>  On Mon, Nov 21, 2016 at 8:56 AM, Jacob Keller <jacob.keller@gmail.com> wrote:
>>>  On Mon, Nov 21, 2016 at 12:11 AM, KES <kes-kes@yandex.ru> wrote:
>>>>  Hi.
>>>
>>>  Hi,
>>>
>>>>  I have some question about how diff works then give proposal:
>>>>
>>>>  it will be very useful for each "symbol" store additional meta info as source line length. So in this case when git counter two equal sequence of commands it will do further comparison: Adds 23 chars deletes none VS adds 75 chars deletes 46
>>>>
>>>>  Actually I got this:
>>>>
>>>>  @@ -129,8 +132,9 @@ sub _preprocess_message {
>>>>   sub _process_message {
>>>>       my ($self, $message) = @_;
>>>>
>>>>  - my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>>>  + my $time = [ gettimeofday ];
>>>>
>>>>  + my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>>>       return $self->send_error(ERROR_REQUEST_INVALID)
>>>>           unless defined($method);
>>>>
>>>>  Instead of expected:
>>>>  @@ -129,6 +132,8 @@ sub _preprocess_message {
>>>>   sub _process_message {
>>>>       my ($self, $message) = @_;
>>>>
>>>>  + my $time = [ gettimeofday ];
>>>>  +
>>>>       my $method = ref($message) eq 'HASH' ? $message->{method} : undef;
>>>>  -
>>>>       return $self->send_error(ERROR_REQUEST_INVALID)
>>>
>>>  Have you tried the various options for git to search for smaller
>>>  diffs? Or using the other diff algorithms such as histogram instead of
>>>  patience?
>>
>>  The newest version of Git comes with a flag to move around the diff
>>  better, based on the work at https://github.com/mhagger/diff-slider-tools
>
> Unfortunately in this case, I'm not convinced that it will improve the
> diff. It's worth a try as well though.
>
> Thanks,
> Jake

Re: Feature request: Improve diff algorithm

[Jacob Keller]

On Wed, Jan 24, 2018 at 8:43 AM, KES <kes-kes@yandex.ru> wrote:
> Here is another place where diff can be improved:
> @@ -141,8 +140,9 @@ My_runops(pTHX)
>                 // Do not trace variables in DB:: module
>                 if( SvOK( inDB ) ) continue;
>
> -               sv_inc_nomg( inDB );
>
> +               // save_item( inDB );
> +               sv_inc_nomg( inDB );
>                 dSP; SINFO; SAVETMPS;
>
>                 // printf( "SWITCH\n" );
>
>
> This would be better it the patch looks like:
> ( this patch is manually created just to light the idea. It may contain errors)
> @@ -140,6 +140,7 @@ My_runops(pTHX)
>          // Do not trace variables in DB:: module
>          if( SvOK( inDB ) ) continue;
>
> +
> +        // save_item( inDB );
>          sv_inc_nomg( inDB );
> -
>          dSP; SINFO; SAVETMPS;
>
> As we can see, here the `sv_inc_nomg( inDB );` line is unchanged and `// save_item( inDB );` is added.
> Here we just add/remove empty lines and patch looks more better.
>
> I think (and this is my assumption), the the diff algorithm should take into account the string length.
> This is more better to add/remove more short lines
>

Hi,

Can you check if this is already handled by --indent-heuristic option
of diff? I think it might help this one already.

Thanks,
Jake

Re: Feature request: Improve diff algorithm

[KES]

One yet more:

@@ -141,5 +86,9 @@
 	// }
 
 
-	OP* o;
+	SV *tvs =  newSVpvs( "ScalarHistory" );
+	SV *tva =  newSVpvs( "ArrayHistory"  );
+	SV *tvh =  newSVpvs( "HashHistory"   );
+
+	OP *o;
 	while( PL_op ) {

Re: Feature request: Improve diff algorithm

[SZEDER Gábor]

> One yet more:
> 
> @@ -141,5 +86,9 @@
>  	// }
>  
>  
> -	OP* o;
> +	SV *tvs =  newSVpvs( "ScalarHistory" );
> +	SV *tva =  newSVpvs( "ArrayHistory"  );
> +	SV *tvh =  newSVpvs( "HashHistory"   );
> +
> +	OP *o;
>  	while( PL_op ) {

What version of Git are you using?

The current version gives me this:

diff --git a/f b/f
index 30a292bbd..fa1e98292 100644
--- a/f
+++ b/f
@@ -1,5 +1,9 @@
 	// }
 
 
+	SV *tvs =  newSVpvs( "ScalarHistory" );
+	SV *tva =  newSVpvs( "ArrayHistory"  );
+	SV *tvh =  newSVpvs( "HashHistory"   );
+
 	OP* o;
 	while( PL_op ) {

Re: Feature request: Improve diff algorithm

[SZEDER Gábor]

On Thu, Jan 25, 2018 at 9:12 PM, SZEDER Gábor <szeder.dev@gmail.com> wrote:
>> One yet more:
>>
>> @@ -141,5 +86,9 @@
>>       // }
>>
>>
>> -     OP* o;

Oops, when trying to reproduce I overlooked that here the * is stuck
after OP ...

>> +     SV *tvs =  newSVpvs( "ScalarHistory" );
>> +     SV *tva =  newSVpvs( "ArrayHistory"  );
>> +     SV *tvh =  newSVpvs( "HashHistory"   );
>> +
>> +     OP *o;

... but here it's stuck to o.

With that adjusted I do get the same diff as you, and I think that's the
right output in this case.

Re: Feature request: Improve diff algorithm

[Junio C Hamano]

KES <kes-kes@yandex.ru> writes:

> One yet more:
>
> @@ -141,5 +86,9 @@
>  	// }
>  
>  
> -	OP* o;
> +	SV *tvs =  newSVpvs( "ScalarHistory" );
> +	SV *tva =  newSVpvs( "ArrayHistory"  );
> +	SV *tvh =  newSVpvs( "HashHistory"   );
> +
> +	OP *o;
>  	while( PL_op ) {

Huh?

If the asterisk between type OP and var o did not change, then
inserting the three new lines before o's definition may make sense,
but otherwise...

Re: Feature request: Improve diff algorithm

[KES]

One yet more:

@@ -43,22 +44,25 @@ sub tariff_title {
 1;
 
 __DATA__
-@@ control/tariff.css
-* {
-    margin: 0;
-    padding: 0;
-    border: 0;
-    -webkit-box-sizing: border-box;
-    box-sizing: border-box; }
-html {
-    background-color: #121212;
-    color: white;
-    font-family: 'Roboto', 'Arial',  sans-serif;
-    font-size: 16px; }
-a {
-    cursor: pointer; }
 
 
+@@ control/tariff_about_old.html.ep
+<div class="option__about">
+  <div class="option__info">
+    <div class="option__icon"><img src="<%= $icon %>"></div>
+    <h3 class="option__name"><%= $title %></h3>
+  </div>
+  <div class="option__duration">
+    <p><%== $option1 %><%= stash->{ comment1 }? "<span> (" .stash->{ comment1 }.")</span>": '' %></
+    <div class="switch option__switch">
+      <input class="switch__toggle" type="checkbox" checked id="<%= $id %>">
+      <label for="<%= $id %>"></label>
+    </div>
+    <p><%== $option2 %><%= stash->{ comment2 }? "<span> (" .stash->{ comment2 }.")</span>": '' %></
+  </div>
+</div>
+
+@@ control/tariff.css
 /*  BASE BUTTON FOR TARIFF CARD  */
 .button {
   display: -webkit-box;

But it would be better if `@@ control/tariff.css` were untouched:

@@ -43,22 +44,25 @@ sub tariff_title {
 1;
 
 __DATA__
+
+
+@@ control/tariff_about_old.html.ep
+<div class="option__about">
+  <div class="option__info">
+    <div class="option__icon"><img src="<%= $icon %>"></div>
+    <h3 class="option__name"><%= $title %></h3>
+  </div>
+  <div class="option__duration">
+    <p><%== $option1 %><%= stash->{ comment1 }? "<span> (" .stash->{ comment1 }.")</span>": '' %></
+    <div class="switch option__switch">
+      <input class="switch__toggle" type="checkbox" checked id="<%= $id %>">
+      <label for="<%= $id %>"></label>
+    </div>
+    <p><%== $option2 %><%= stash->{ comment2 }? "<span> (" .stash->{ comment2 }.")</span>": '' %></
+  </div>
+</div>
+
 @@ control/tariff.css
-* {
-    margin: 0;
-    padding: 0;
-    border: 0;
-    -webkit-box-sizing: border-box;
-    box-sizing: border-box; }
-html {
-    background-color: #121212;
-    color: white;
-    font-family: 'Roboto', 'Arial',  sans-serif;
-    font-size: 16px; }
-a {
-    cursor: pointer; }
-
-
 /*  BASE BUTTON FOR TARIFF CARD  */
 .button {
   display: -webkit-box;

Re: Feature request: Improve diff algorithm

[Stefan Beller]

On Sat, Jan 27, 2018 at 5:08 AM, KES <kes-kes@yandex.ru> wrote:
> One yet more:
>
> @@ -43,22 +44,25 @@ sub tariff_title {
>  1;
>
>  __DATA__
> -@@ control/tariff.css
> -* {
> -    margin: 0;
> -    padding: 0;
> -    border: 0;
> -    -webkit-box-sizing: border-box;
> -    box-sizing: border-box; }
> -html {
> -    background-color: #121212;
> -    color: white;
> -    font-family: 'Roboto', 'Arial',  sans-serif;
> -    font-size: 16px; }
> -a {
> -    cursor: pointer; }
>
>
> +@@ control/tariff_about_old.html.ep
> +<div class="option__about">
> +  <div class="option__info">
> +    <div class="option__icon"><img src="<%= $icon %>"></div>
> +    <h3 class="option__name"><%= $title %></h3>
> +  </div>
> +  <div class="option__duration">
> +    <p><%== $option1 %><%= stash->{ comment1 }? "<span> (" .stash->{ comment1 }.")</span>": '' %></
> +    <div class="switch option__switch">
> +      <input class="switch__toggle" type="checkbox" checked id="<%= $id %>">
> +      <label for="<%= $id %>"></label>
> +    </div>
> +    <p><%== $option2 %><%= stash->{ comment2 }? "<span> (" .stash->{ comment2 }.")</span>": '' %></
> +  </div>
> +</div>
> +
> +@@ control/tariff.css
>  /*  BASE BUTTON FOR TARIFF CARD  */
>  .button {
>    display: -webkit-box;
>
> But it would be better if `@@ control/tariff.css` were untouched:
>
> @@ -43,22 +44,25 @@ sub tariff_title {
>  1;
>
>  __DATA__
> +
> +
> +@@ control/tariff_about_old.html.ep
> +<div class="option__about">
> +  <div class="option__info">
> +    <div class="option__icon"><img src="<%= $icon %>"></div>
> +    <h3 class="option__name"><%= $title %></h3>
> +  </div>
> +  <div class="option__duration">
> +    <p><%== $option1 %><%= stash->{ comment1 }? "<span> (" .stash->{ comment1 }.")</span>": '' %></
> +    <div class="switch option__switch">
> +      <input class="switch__toggle" type="checkbox" checked id="<%= $id %>">
> +      <label for="<%= $id %>"></label>
> +    </div>
> +    <p><%== $option2 %><%= stash->{ comment2 }? "<span> (" .stash->{ comment2 }.")</span>": '' %></
> +  </div>
> +</div>
> +
>  @@ control/tariff.css
> -* {
> -    margin: 0;
> -    padding: 0;
> -    border: 0;
> -    -webkit-box-sizing: border-box;
> -    box-sizing: border-box; }
> -html {
> -    background-color: #121212;
> -    color: white;
> -    font-family: 'Roboto', 'Arial',  sans-serif;
> -    font-size: 16px; }
> -a {
> -    cursor: pointer; }
> -
> -
>  /*  BASE BUTTON FOR TARIFF CARD  */
>  .button {
>    display: -webkit-box;
>

Try the new option that Jonathan Tan implemented:

  git diff --anchor="@@ control/tariff.css"

to produce the second diff.

I wonder if we want to have a permanent store for these
lines in given diffs, such that you only have to figure it out once.
(And eventually the community will have a corpus of data to
figure out how to improve the diff for real)

Re: Feature request: Improve diff algorithm

[Stefan Beller]

On Wed, Jan 24, 2018 at 8:43 AM, KES <kes-kes@yandex.ru> wrote:
> Here is another place where diff can be improved:
> @@ -141,8 +140,9 @@ My_runops(pTHX)
>                 // Do not trace variables in DB:: module
>                 if( SvOK( inDB ) ) continue;
>
> -               sv_inc_nomg( inDB );
>
> +               // save_item( inDB );
> +               sv_inc_nomg( inDB );
>                 dSP; SINFO; SAVETMPS;
>
>                 // printf( "SWITCH\n" );
>
>

(Manually reconstructing), the before:

                 // Do not trace variables in DB:: module
                 if( SvOK( inDB ) ) continue;

                 sv_inc_nomg( inDB );

                 dSP; SINFO; SAVETMPS;

                 // printf( "SWITCH\n" );

and after:

                 // Do not trace variables in DB:: module
                 if( SvOK( inDB ) ) continue;


                  // save_item( inDB );
                  sv_inc_nomg( inDB );
                 dSP; SINFO; SAVETMPS;

                 // printf( "SWITCH\n" );



> This would be better it the patch looks like:
> ( this patch is manually created just to light the idea. It may contain errors)
> @@ -140,6 +140,7 @@ My_runops(pTHX)
>          // Do not trace variables in DB:: module
>          if( SvOK( inDB ) ) continue;
>
> +
> +        // save_item( inDB );
>          sv_inc_nomg( inDB );
> -
>          dSP; SINFO; SAVETMPS;

Before:

          // Do not trace variables in DB:: module
          if( SvOK( inDB ) ) continue;

          sv_inc_nomg( inDB );

          dSP; SINFO; SAVETMPS;

after:

          if( SvOK( inDB ) ) continue;


          // save_item( inDB );
          sv_inc_nomg( inDB );
          dSP; SINFO; SAVETMPS;

Seems like the diff is the same.
I agree that we'd rather want to remove/add empty lines
instead of moving full lines. Maybe we can add a penalty for that
in the diff code. Currently each line costs the same, as diff algorithm
optimizes for number of lines to be minimal, which both these diffs
satisfy.


>
> As we can see, here the `sv_inc_nomg( inDB );` line is unchanged and `// save_item( inDB );` is added.
> Here we just add/remove empty lines and patch looks more better.
>
> I think (and this is my assumption), the the diff algorithm should take into account the string length.
> This is more better to add/remove more short lines

Yup. Thanks for giving an example.