Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
From b0cf91cf7bc32fc20f73f4abc463d952c86983a3 Mon Sep 17 00:00:00 2001
From: Bart Wiegmans <bartwiegmans@gmail.com>
Date: Fri, 17 May 2019 12:45:13 +0200
Subject: [PATCH] [Vector] Implement MVM_VECTOR_CONTAINS with memmem
This should be more flexible (arbitrary sized items) and hopefully
faster because memmem is fairly optimized. And allows the use as an
expression.
---
build/Makefile.in | 1 +
src/core/vector.h | 18 ++++++------------
src/platform/memmem.c | 23 +++++++++++++++++++++++
src/platform/memmem.h | 24 +-----------------------
src/spesh/pea.c | 5 ++---
src/strings/ops.c | 2 +-
6 files changed, 34 insertions(+), 39 deletions(-)
create mode 100644 src/platform/memmem.c
diff --git a/build/Makefile.in b/build/Makefile.in
index e0223083a..6782add8c 100644
--- a/build/Makefile.in
+++ b/build/Makefile.in
@@ -236,6 +236,7 @@ OBJECTS2 = src/6model/reprs/MVMDLLSym@obj@ \
src/instrument/line_coverage@obj@ \
src/platform/sys@obj@ \
src/platform/random@obj@ \
+ src/platform/memmem@obj@ \
src/platform/memmem32@obj@ \
src/moar@obj@ \
@platform@ \
diff --git a/src/core/vector.h b/src/core/vector.h
index d46615b42..8fb19f131 100644
--- a/src/core/vector.h
+++ b/src/core/vector.h
@@ -22,8 +22,9 @@
x ## _alloc = 0; \
} while (0)
-#define MVM_VECTOR_SIZE(x) \
- (sizeof(*x) * (x ## _alloc))
+
+#define MVM_VECTOR_ELEM_SIZE(x) (sizeof(*x))
+#define MVM_VECTOR_SIZE(x) (MVM_VECTOR_ELEM_SIZE(x) * (x ## _alloc))
#define MVM_VECTOR_TOP(x) \
((x) + (x ## _num))
@@ -62,7 +63,6 @@
#define MVM_VECTOR_POP(x) \
(x)[--(x ## _num)]
-
#define MVM_VECTOR_APPEND(x, ar, len) do { \
size_t _l = (len); \
MVM_VECTOR_ENSURE_SPACE(x, _l); \
@@ -84,12 +84,6 @@
a ## _num = b ## _num; \
} while (0)
-#define MVM_VECTOR_CONTAINS(x, elem, result) do { \
- MVMint32 i; \
- result = 0; \
- for (i = 0; i < x ## _num; i++) \
- if (x[i] == elem) { \
- result = 1; \
- break; \
- } \
- } while (0)
+#define MVM_VECTOR_SEARCH(h, n) (MVM_memmem(h, MVM_VECTOR_SIZE(h), n, MVM_VECTOR_ELEM_SIZE(h)))
+
+#define MVM_VECTOR_CONTAINS(h, n) (MVM_VECTOR_SEARCH(h, n) != NULL)
diff --git a/src/platform/memmem.c b/src/platform/memmem.c
new file mode 100644
index 000000000..b03e24606
--- /dev/null
+++ b/src/platform/memmem.c
@@ -0,0 +1,23 @@
+/* On Linux we use glibc's memmem which uses the Knuth-Morris-Pratt algorithm.
+ * We use FreeBSD's libc memmem on Windows and MacOS, which uses
+ * Crochemore-Perrin two-way string matching.
+ * Reasoning:
+ * Windows, does not include any native memmem
+ * MacOS has a memmem but is slower and originates from FreeBSD dated to 2005
+ * Solaris doesn't seem to have memmem */
+
+#if defined(_WIN32) || defined(__APPLE__) || defined(__Darwin__) || defined(__sun)
+#include "../3rdparty/freebsd/memmem.c"
+#else
+/* On systems that use glibc, you must define _GNU_SOURCE before including string.h
+ * to get access to memmem. */
+#define _GNU_SOURCE
+#include <string.h>
+#endif
+
+void * MVM_memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen) {
+ return memmem(haystack, haystacklen, needle, needlelen);
+}
+
+/* Extended info:
+ * In glibc, the Knuth-Morris-Pratt algorithm was added as of git tag glibc-2.8-44-g0caca71ac9 */
diff --git a/src/platform/memmem.h b/src/platform/memmem.h
index b03e24606..8c40f6724 100644
--- a/src/platform/memmem.h
+++ b/src/platform/memmem.h
@@ -1,23 +1 @@
-/* On Linux we use glibc's memmem which uses the Knuth-Morris-Pratt algorithm.
- * We use FreeBSD's libc memmem on Windows and MacOS, which uses
- * Crochemore-Perrin two-way string matching.
- * Reasoning:
- * Windows, does not include any native memmem
- * MacOS has a memmem but is slower and originates from FreeBSD dated to 2005
- * Solaris doesn't seem to have memmem */
-
-#if defined(_WIN32) || defined(__APPLE__) || defined(__Darwin__) || defined(__sun)
-#include "../3rdparty/freebsd/memmem.c"
-#else
-/* On systems that use glibc, you must define _GNU_SOURCE before including string.h
- * to get access to memmem. */
-#define _GNU_SOURCE
-#include <string.h>
-#endif
-
-void * MVM_memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen) {
- return memmem(haystack, haystacklen, needle, needlelen);
-}
-
-/* Extended info:
- * In glibc, the Knuth-Morris-Pratt algorithm was added as of git tag glibc-2.8-44-g0caca71ac9 */
+void * MVM_memmem(const void *haystack, size_t haystacklen, const void *needle, size_t needlelen);
diff --git a/src/spesh/pea.c b/src/spesh/pea.c
index 2e0557eff..b1dc313cb 100644
--- a/src/spesh/pea.c
+++ b/src/spesh/pea.c
@@ -1,4 +1,5 @@
#include "moar.h"
+#include "platform/memmem.h"
/* Debug logging of EA. */
#define PEA_LOG 0
@@ -1197,9 +1198,7 @@ static void setup_bb_state(MVMThreadContext *tc, GraphState *gs, MVMSpeshBB *new
num_materialized++;
for (k = 0; k < MVM_VECTOR_ELEMS(a_state->materializations); k++) {
Transformation *t = a_state->materializations[k];
- MVMint32 already_seen;
- MVM_VECTOR_CONTAINS(distinct_materializations, t, already_seen);
- if (!already_seen)
+ if (!MVM_VECTOR_CONTAINS(distinct_materializations, t))
MVM_VECTOR_PUSH(distinct_materializations, t);
}
}
diff --git a/src/strings/ops.c b/src/strings/ops.c
index 14caf69a4..20c63d3e9 100644
--- a/src/strings/ops.c
+++ b/src/strings/ops.c
@@ -1,6 +1,6 @@
+#include "moar.h"
#include "platform/memmem.h"
#include "platform/memmem32.h"
-#include "moar.h"
#define MVM_DEBUG_STRANDS 0
#define MVM_string_KMP_max_pattern_length 8192
/* Max value possible for MVMuint32 MVMStringBody.num_graphs */
--
2.20.1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment