X-Git-Url: https://wimlib.net/git/?a=blobdiff_plain;f=include%2Fwimlib%2Flz_sarray.h;h=30dc2b30a480ea64d943ab73e6baedf71bfa86f6;hb=dec3bbfa2c3e9fc8e4b1adbaa0323337a75aaadb;hp=0c7007b704b855bf7799aae044f6ce4fbf1b49e1;hpb=5c0846b71891c0c088de4f9ef4cc6ab545f5b64e;p=wimlib

diff --git a/include/wimlib/lz_sarray.h b/include/wimlib/lz_sarray.h
index 0c7007b7..30dc2b30 100644
--- 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'  */
 
@@ -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;
 		}
 	}