WordPress.org

Make WordPress Core

Changeset 43775


Ignore:
Timestamp:
10/20/2018 08:35:41 AM (8 months ago)
Author:
pento
Message:

Revisions: Improve performance of WP_Text_Diff_Renderer_Table.

WP_Text_Diff_Renderer_Table is used to generate the diff view in revisions, but there were some cases that could cause it to take excessive amounts of time to run.

Some noteable cases include:

  • When a large number of new lines were inserted in the middle of the post from one revision to the next.
  • When both revisions contain >100 lines.
  • When either revision contains a lot of long lines.

In one extreme test case, the diff view took over a minute to generate. With this change, it now takes less than a second.

See #35667.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/5.0/src/wp-includes/class-wp-text-diff-renderer-table.php

    r41162 r43775  
    5555
    5656    protected $compat_fields = array( '_show_split_view', 'inline_diff_renderer', '_diff_threshold' );
     57
     58    /**
     59     * Caches the output of count_chars() in compute_string_distance()
     60     *
     61     * @var array
     62     * @since 5.0.0
     63     */
     64    protected $count_cache = array();
     65
     66    /**
     67     * Caches the difference calculation in compute_string_distance()
     68     *
     69     * @var array
     70     * @since 5.0.0
     71     */
     72    protected $difference_cache = array();
    5773
    5874    /**
     
    392408                array_splice( $final_rows, $orig_pos, 0, -1 );
    393409            } elseif ( $final_pos < $orig_pos ) { // This orig's match is up a ways. Pad final with blank rows.
    394                 $diff_pos = $final_pos - $orig_pos;
    395                 while ( $diff_pos < 0 )
    396                     array_splice( $final_rows, $orig_pos, 0, $diff_pos++ );
     410                $diff_array = range( -1, $final_pos - $orig_pos );
     411                array_splice( $final_rows, $orig_pos, 0, $diff_array );
    397412            } elseif ( $final_pos > $orig_pos ) { // This orig's match is down a ways. Pad orig with blank rows.
    398                 $diff_pos = $orig_pos - $final_pos;
    399                 while ( $diff_pos < 0 )
    400                     array_splice( $orig_rows, $orig_pos, 0, $diff_pos++ );
     413                $diff_array = range( -1, $orig_pos - $final_pos );
     414                array_splice( $orig_rows, $orig_pos, 0, $diff_array );
    401415            }
    402416        }
     
    426440     */
    427441    public function compute_string_distance( $string1, $string2 ) {
    428         // Vectors containing character frequency for all chars in each string
    429         $chars1 = count_chars($string1);
    430         $chars2 = count_chars($string2);
    431 
    432         // L1-norm of difference vector.
    433         $difference = array_sum( array_map( array($this, 'difference'), $chars1, $chars2 ) );
     442        // Use an md5 hash of the strings for a count cache, as it's fast to generate, and collisions aren't a concern.
     443        $count_key1 = md5( $string1 );
     444        $count_key2 = md5( $string2 );
     445
     446        // Cache vectors containing character frequency for all chars in each string.
     447        if ( ! isset( $this->count_cache[ $count_key1 ] ) ) {
     448            $this->count_cache[ $count_key1 ] = count_chars( $string1 );
     449        }
     450        if ( ! isset( $this->count_cache[ $count_key2 ] ) ) {
     451            $this->count_cache[ $count_key2 ] = count_chars( $string2 );
     452        }
     453
     454        $chars1 = $this->count_cache[ $count_key1 ];
     455        $chars2 = $this->count_cache[ $count_key2 ];
     456
     457        $difference_key = md5( implode( ',', $chars1 ) . ':' . implode( ',', $chars2 ) );
     458        if ( ! isset( $this->difference_cache[ $difference_key ] ) ) {
     459            // L1-norm of difference vector.
     460            $this->difference_cache[ $difference_key ] = array_sum( array_map( array( $this, 'difference' ), $chars1, $chars2 ) );
     461        }
     462
     463        $difference = $this->difference_cache[ $difference_key ];
    434464
    435465        // $string1 has zero length? Odd. Give huge penalty by not dividing.
Note: See TracChangeset for help on using the changeset viewer.