Changeset 44129

Timestamp:

12/14/2018 01:03:51 AM (7 years 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.

Merges [43775] from the 5.0 branch to trunk.

Fixes #35667.

Location:

trunk

Files:

• . (modified) (1 prop)
• src/wp-includes/class-wp-text-diff-renderer-table.php (modified) (3 diffs)

trunk/src/wp-includes/class-wp-text-diff-renderer-table.php

@@ -55 +55 @@
 
     protected $compat_fields = array( '_show_split_view', 'inline_diff_renderer', '_diff_threshold' );
+
+    /**
+     * Caches the output of count_chars() in compute_string_distance()
+     *
+     * @var array
+     * @since 5.0.0
+     */
+    protected $count_cache = array();
+
+    /**
+     * Caches the difference calculation in compute_string_distance()
+     *
+     * @var array
+     * @since 5.0.0
+     */
+    protected $difference_cache = array();
 
     /**
@@ -397 +413 @@
                 array_splice( $final_rows, $orig_pos, 0, -1 );
             } elseif ( $final_pos < $orig_pos ) { // This orig's match is up a ways. Pad final with blank rows.
-                $diff_pos = $final_pos - $orig_pos;
-                while ( $diff_pos < 0 ) {
-                    array_splice( $final_rows, $orig_pos, 0, $diff_pos++ );
-                }
+                $diff_array = range( -1, $final_pos - $orig_pos );
+                array_splice( $final_rows, $orig_pos, 0, $diff_array );
             } elseif ( $final_pos > $orig_pos ) { // This orig's match is down a ways. Pad orig with blank rows.
-                $diff_pos = $orig_pos - $final_pos;
-                while ( $diff_pos < 0 ) {
-                    array_splice( $orig_rows, $orig_pos, 0, $diff_pos++ );
-                }
+                $diff_array = range( -1, $orig_pos - $final_pos );
+                array_splice( $orig_rows, $orig_pos, 0, $diff_array );
             }
         }
@@ -435 +447 @@
      */
     public function compute_string_distance( $string1, $string2 ) {
-        // Vectors containing character frequency for all chars in each string
-        $chars1 = count_chars( $string1 );
-        $chars2 = count_chars( $string2 );
-
-        // L1-norm of difference vector.
-        $difference = array_sum( array_map( array( $this, 'difference' ), $chars1, $chars2 ) );
+        // Use an md5 hash of the strings for a count cache, as it's fast to generate, and collisions aren't a concern.
+        $count_key1 = md5( $string1 );
+        $count_key2 = md5( $string2 );
+
+        // Cache vectors containing character frequency for all chars in each string.
+        if ( ! isset( $this->count_cache[ $count_key1 ] ) ) {
+            $this->count_cache[ $count_key1 ] = count_chars( $string1 );
+        }
+        if ( ! isset( $this->count_cache[ $count_key2 ] ) ) {
+            $this->count_cache[ $count_key2 ] = count_chars( $string2 );
+        }
+
+        $chars1 = $this->count_cache[ $count_key1 ];
+        $chars2 = $this->count_cache[ $count_key2 ];
+
+        $difference_key = md5( implode( ',', $chars1 ) . ':' . implode( ',', $chars2 ) );
+        if ( ! isset( $this->difference_cache[ $difference_key ] ) ) {
+            // L1-norm of difference vector.
+            $this->difference_cache[ $difference_key ] = array_sum( array_map( array( $this, 'difference' ), $chars1, $chars2 ) );
+        }
+
+        $difference = $this->difference_cache[ $difference_key ];
 
         // $string1 has zero length? Odd. Give huge penalty by not dividing.