[PATCH 1/3] erofs-utils: optimize dedupe matching

From: Gao Xiang <hsiangkao@linux.alibaba.com>
To: linux-erofs@lists.ozlabs.org
Cc: Gao Xiang <hsiangkao@linux.alibaba.com>
Subject: [PATCH 1/3] erofs-utils: optimize dedupe matching
Date: Thu,  9 Mar 2023 19:26:28 +0800	[thread overview]
Message-ID: <20230309112630.74230-1-hsiangkao@linux.alibaba.com> (raw)

Match in words instead of byte granularity.

Signed-off-by: Gao Xiang <hsiangkao@linux.alibaba.com>
---
 lib/dedupe.c | 48 ++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 42 insertions(+), 6 deletions(-)

diff --git a/lib/dedupe.c b/lib/dedupe.c
index 7f6e56f..84c323b 100644
--- a/lib/dedupe.c
+++ b/lib/dedupe.c
@@ -8,6 +8,45 @@
 #include "rolling_hash.h"
 #include "sha256.h"
 
+inline unsigned long erofs_memcmp2(const u8 *s1, const u8 *s2,
+				   unsigned long sz)
+{
+	unsigned int n = sz;
+
+	if (sz >= sizeof(long) && ((long)s1 & (sizeof(long) - 1)) ==
+			((long)s2 & (sizeof(long) - 1))) {
+		const unsigned long *a1, *a2;
+
+		while ((long)s1 & (sizeof(long) - 1)) {
+			if (*s1 != *s2)
+				break;
+			++s1;
+			++s2;
+			--sz;
+		}
+
+		a1 = (const unsigned long *)s1;
+		a2 = (const unsigned long *)s2;
+		while (sz >= sizeof(long)) {
+			if (*a1 != *a2)
+				break;
+			++a1;
+			++a2;
+			sz -= sizeof(long);
+		}
+		s1 = (const u8 *)a1;
+		s2 = (const u8 *)a2;
+	}
+	while (sz) {
+		if (*s1 != *s2)
+			break;
+		++s1;
+		++s2;
+		--sz;
+	}
+	return n - sz;
+}
+
 static unsigned int window_size, rollinghash_rm;
 static struct rb_tree *dedupe_tree, *dedupe_subtree;
 
@@ -72,12 +111,9 @@ int z_erofs_dedupe_match(struct z_erofs_dedupe_ctx *ctx)
 		if (memcmp(sha256, e->prefix_sha256, sizeof(sha256)))
 			continue;
 
-		extra = 0;
-		while (cur + window_size + extra < ctx->end &&
-		       window_size + extra < e->original_length &&
-		       e->extra_data[extra] == cur[window_size + extra])
-			++extra;
-
+		extra = min_t(unsigned int, ctx->end - cur - window_size,
+			      e->original_length - window_size);
+		extra = erofs_memcmp2(cur + window_size, e->extra_data, extra);
 		if (window_size + extra <= ctx->cur - cur)
 			continue;
 		ctx->cur = cur;
-- 
2.24.4

