Re: Feature request: Improve diff algorithm

From: Stefan Beller <sbeller@google.com>
Date: Jan 26, 2018, 18:29 UTC
Message-ID: <CAGZ79kZX3NOb4ttXvjV0=vrLrMTj7z7N=+=DUtd0+3gYWJ6wng@mail.gmail.com>
In-Reply-To: <12531516812201@web36o.yandex.ru>

On Wed, Jan 24, 2018 at 8:43 AM, KES <kes-kes@yandex.ru> wrote:

Show 14 quoted lines

> 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" );

Show 11 quoted lines

> 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.

Show 6 quoted lines

>
> 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.