Re: Feature request: Improve diff algorithm

[Stefan Beller <sbeller@google.com>]

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.