Remove duplicate words & fix grammatical errors

[wimlib] / include / wimlib / lz_sarray.h

diff --git a/include/wimlib/lz_sarray.h b/include/wimlib/lz_sarray.h
index 0c7007b704b855bf7799aae044f6ce4fbf1b49e1..e609d0c2e79dbbcc93a668475ae0f4fa6a53d0dd 100644 (file)
--- a/include/wimlib/lz_sarray.h
+++ b/include/wimlib/lz_sarray.h
@@ -34,7 +34,8 @@
 #ifndef _WIMLIB_LZ_SARRAY_H
 #define _WIMLIB_LZ_SARRAY_H
 
-#include "wimlib/compiler.h" /* must define '_always_inline_attribute'  */
+#include "wimlib/compiler.h" /* must define '_always_inline_attribute',
+                               'likely()', and 'prefetch()'.  */
 #include "wimlib/lz.h"       /* must define 'struct raw_match' and LZ_ASSERT()  */
 #include "wimlib/types.h"    /* must define 'bool', 'u8', 'u16, and 'u32'  */
 
@@ -135,7 +136,7 @@ struct salink {
                struct {
                        /* Intially, the length, in bytes, of the longest common
                         * prefix (LCP) between the suffix having this rank and
-                        * the suffix with the the smallest larger rank that
+                        * the suffix with the smallest larger rank that
                         * starts earlier in the window than the suffix having
                         * this rank.  If no such suffix exists, this will be 0.
                         *
@@ -149,7 +150,7 @@ struct salink {
 
                        /* Initially, the length, in bytes, of the longest
                         * common prefix (LCP) between the suffix having this
-                        * rank and the suffix with the the largest smaller rank
+                        * rank and the suffix with the largest smaller rank
                         * that starts earlier in the window than the suffix
                         * having this rank.  If no such suffix exists, this
                         * will be 0.
@@ -169,7 +170,7 @@ struct salink {
                         * distance to the rank of a suffix that is
                         * lexicographically closer to the current suffix than
                         * the desired suffix, but appears *later* in the window
-                        * and hence cannot be used as the basis for a LZ77
+                        * and hence cannot be used as the basis for an LZ77
                         * match.  */
                        lz_sarray_delta_t dist_to_next;
 
@@ -180,7 +181,7 @@ struct salink {
                         * distance to the rank of a suffix that is
                         * lexicographically closer to the current suffix than
                         * the desired suffix, but appears *later* in the window
-                        * and hence cannot be used as the basis for a LZ77
+                        * and hence cannot be used as the basis for an LZ77
                         * match.  */
                        lz_sarray_delta_t dist_to_prev;
                };
@@ -285,6 +286,19 @@ lz_sarray_get_matches(struct lz_sarray *mf,
        /* Prepare for searching the current position.  */
        lz_sarray_update_salink(r, link);
 
+#if 1
+       /* Prefetch next position in SA and link.
+        *
+        * This can improve performance on large windows since the locations in
+        * SA and link at which each successive search begins are in general
+        * randomly distributed.  */
+       if (likely(i + 1 < mf->window_size)) {
+               const lz_sarray_pos_t next_r = ISA[i + 1];
+               prefetch(&SA[next_r]);
+               prefetch(&link[next_r]);
+       }
+#endif
+
        /* L = rank of next suffix to the left;
         * R = rank of next suffix to the right;
         * lenL = length of match between current position and the suffix with rank L;
@@ -409,10 +423,10 @@ extend_left:
                                }
                        }
 
-                       /* Here we have lenL < lenR.  Extend right, unless the
-                        * minimum match length would be underrun.  */
-                       if (lenR == 0)
-                               return nmatches;
+                       /* Here we have lenL < lenR.  Extend right.
+                        * (No check for whether the minimum match length has
+                        * been underrun is needed, provided that such lengths
+                        * are marked as 0.)  */
                        goto extend_right;
                }
        }