Changeset: 5fe9877fb653 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=5fe9877fb653
Modified Files:
monetdb5/extras/crackers/crackers_core_unordered.mx
Branch: holindex
Log Message:
revised ad fixed multi-threaded cracking implementation
the best choices of some local code alternatives
(see "#if [01] /* option [12] */")
still need to be assessed experimentally
diffs (truncated from 598 to 300 lines):
diff --git a/monetdb5/extras/crackers/crackers_core_unordered.mx
b/monetdb5/extras/crackers/crackers_core_unordered.mx
--- a/monetdb5/extras/crackers/crackers_core_unordered.mx
+++ b/monetdb5/extras/crackers/crackers_core_unordered.mx
@@ -154,7 +154,7 @@ str CRKcrackUnorderedThreeSideways_@3_@4
#include "monetdb_config.h"
#include "crackers.h"
-/*#define CRACK_MUTLI_THREAD_DEBUG*/
+//#define CRACK_MUTLI_THREAD_DEBUG
/* argument struct for countThread & crackThread functions */
typedef struct {
@@ -165,7 +165,7 @@ typedef struct {
const void *mval; /* pivot value */
BUN first; /* offset of first value in slice */
BUN last; /* offset of last value in slice */
- BUN pos; /* offset of pivot value */
+ BUN pos_r; /* first(!) pos of right(!) piece */
const char *msg; /* error message */
BUN m; /* size of half slice */
} c_Thread_t;
@@ -297,15 +297,210 @@ CRKcrackUnorderedZero_@2_@1_ST( BAT *b,
/* revised single-threaded crack code */
static str
+CRKcrackUnorderedZero_@2_@1_STxx ( const BAT *b, const @1 mval, const BUN
first, const BUN last, const BUN m, BUN *pos_r
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ , const char *secs
+ #endif
+ )
+{
+ BUN p = first, q = last, pp = p + m - 1, qq = q + 1 - m;
+ oid *src_h;
+ @1 *src_t;
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ lng t_0, t_1;
+
+ fprintf(stderr,
+ "CRKcrackUnorderedZero_@2_@1_STxx ( %d, "LLFMT", "BUNFMT",
"BUNFMT", "BUNFMT", "BUNFMT", "BUNFMT" ) ...\n",
+ b->batCacheid, (lng) mval, first, pp, qq, last, m);
+ t_0 = GDKusec();
+ #endif
+
+ assert(b);
+ assert(pos_r);
+
+ /* input (source) arrays */
+ src_h = (oid*) Hloc(b, BUNfirst(b));
+ src_t = (@1 *) Tloc(b, BUNfirst(b));
+
+ if (m && pp + 1 < qq) {
+ /* crack disjoint left- & right-half of piece / slice */
+ while (p <= pp && q >= qq) {
+#if 1 /* option 1 */
+ /* skip over smaller values from beginning */
+ while (p <= pp && src_t[p] @7 mval)
+ p++;
+ if (p > pp) {
+ /* exhausted left half, skip to right one */
+ p = qq;
+ break; /* not really required */
+ }
+#endif
+#if 0 /* option 2 */
+ /* skip over smaller value from beginning */
+ if (src_t[p] @7 mval) {
+ p++;
+ if (p > pp) {
+ /* exhausted left half, skip to right
one */
+ p = qq;
+ break; /* not really required */
+ }
+ }
+#endif
+ else {
+ /* skip over larger values from end */
+ while (q >= qq && src_t[q] @8 mval)
+ q--;
+ if (q < qq) {
+ /* exhausted right half, skip to left
one */
+ q = pp;
+ break; /* not really required */
+ } else {
+ /* swap values */
+#if 1 /* option 1 */
+ const oid h = src_h[p];
+ const @1 t = src_t[p];
+ src_h[p] = src_h[q];
+ src_t[p] = src_t[q];
+ src_h[q] = h;
+ src_t[q] = t;
+#endif
+#if 0 /* option 2 */
+ oid h;
+ @1 t;
+ h = src_h[p];
+ src_h[p] = src_h[q];
+ src_h[q] = h;
+ t = src_t[p];
+ src_t[p] = src_t[q];
+ src_t[q] = t;
+#endif
+ p++;
+ q--;
+ if (p > pp) {
+ /* exhausted left half, skip to
right one */
+ p = qq;
+ }
+ if (q < qq) {
+ /* exhausted left half, skip to
right one */
+ q = pp;
+ }
+ if (p > pp || q < qq) {
+ break; /* not really required */
+ }
+ }
+ }
+ }
+ }
+
+ /* crack (remaining) consequtive piece / slice */
+ if (!(m && pp + 1 < qq) || p >= qq || q <= pp) {
+ while (p < q) {
+#if 1 /* option 1 */
+ /* skip over smaller values from beginning */
+ while (p < q && src_t[p] @7 mval) {
+ p++;
+ }
+#endif
+#if 0 /* option 2 */
+ /* skip over smaller value from beginning */
+ if (src_t[p] @7 mval) {
+ p++;
+ } else
+#endif
+ {
+ /* skip over larger values from end */
+ while (p < q && src_t[q] @8 mval) {
+ q--;
+ }
+ if (p < q)
+ {
+ /* swap values */
+#if 1 /* option 1 */
+ const oid h = src_h[p];
+ const @1 t = src_t[p];
+ src_h[p] = src_h[q];
+ src_t[p] = src_t[q];
+ src_h[q] = h;
+ src_t[q] = t;
+#endif
+#if 0 /* option 2 */
+ oid h;
+ @1 t;
+ h = src_h[p];
+ src_h[p] = src_h[q];
+ src_h[q] = h;
+ t = src_t[p];
+ src_t[p] = src_t[q];
+ src_t[q] = t;
+#endif
+ p++;
+ q--;
+ }
+ }
+ }
+ }
+
+ /* return pivot position, i.e., first(!) pos in right(!) piece */
+ assert(p >= first && p <= last);
+ if (m && pp + 1 < qq) {
+ if (p <= pp + 1) {
+ assert(p == first || src_t[p-1] @7 mval);
+ while (p <= pp && src_t[p] @7 mval)
+ p++;
+ if (p == pp + 1)
+ p = qq;
+ }
+ if (p >= qq) {
+ assert((p == qq && src_t[pp] @7 mval) || (p > qq &&
src_t[p-1] @7 mval));
+ while (p <= last && src_t[p] @7 mval)
+ p++;
+ }
+ } else {
+ assert(p == first || src_t[p-1] @7 mval);
+ while (p <= last && src_t[p] @7 mval)
+ p++;
+ }
+
+ assert(p >= first && p <= last + 1);
+ assert(p == first || (m && pp + 1 < qq && p == qq && src_t[pp] @7 mval)
|| (!(m && pp + 1 < qq && p == qq) && src_t[p-1] @7 mval));
+ assert(p == last + 1 || src_t[p] @8 mval);
+#ifndef NDEBUG
+ for (q = first; q < p; q++) {
+ if (m && pp + 1 < qq && q == pp + 1)
+ q = qq;
+ if (!(src_t[q] @7 mval))
+ fprintf(stderr,"a "BUNFMT": %d !@7
%d\n",q,(int)src_t[q],(int)mval);
+ }
+ for (q = p; q <= last; q++) {
+ if (m && pp + 1 < qq && q == pp + 1)
+ q = qq;
+ if (!(src_t[q] @8 mval))
+ fprintf(stderr,"b "BUNFMT": %d !@8
%d\n",q,(int)src_t[q],(int)mval);
+ }
+#endif
+ *pos_r = p;
+
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ t_1 = GDKusec();
+ fprintf(stderr,
+ "CRKcrackUnorderedZero_@2_@1_STxx ( %d, "LLFMT", "BUNFMT",
"BUNFMT", "BUNFMT", "BUNFMT", "BUNFMT" ) -> "BUNFMT" : %.6f %s\n",
+ b->batCacheid, (lng) mval, first, pp, qq, last, m, *pos_r,
(dbl) (t_1 - t_0) / 1000000.0, secs);
+ #endif
+
+ return MAL_SUCCEED;
+}
+
+
+static str
CRKcrackUnorderedZero_@2_@1_STx ( const BAT *b, const @1 mval, const BUN
first, const BUN last, const BUN m, oid *pos
#ifdef CRACK_MUTLI_THREAD_DEBUG
, const char *secs
#endif
)
{
- BUN p = first, q = last, pp = p + m - 1, qq = q - m + 1;
- oid *src_h;
- @1 *src_t;
+ str msg;
+ BUN pos_r;
+
#ifdef CRACK_MUTLI_THREAD_DEBUG
lng t_0, t_1;
@@ -315,66 +510,16 @@ CRKcrackUnorderedZero_@2_@1_STx ( const
t_0 = GDKusec();
#endif
- /* input (source) arrays */
- src_h = (oid*) Hloc(b, BUNfirst(b));
- src_t = (@1 *) Tloc(b, BUNfirst(b));
+ assert(b);
+ assert(pos);
+ assert(m == 0 || first + m - 1 + 1 == last + 1 - m);
- if (m && pp < qq - 1) {
- /* crack disjoint left- & right-half of piece / slice */
- while (p <= pp && q >= qq) {
- /* skip over smaller values from beginning */
- while (p <= pp && src_t[p] @7 mval /*@5_@3(&src_t[p],
&mval, @6@1)*/)
- p++;
- /* skip over larger values from end */
- while (q >= qq && src_t[q] @8 mval /*@5_@4(&src_t[q],
&mval, @6@1)*/)
- q--;
- if (p <= pp && q >= qq) {
- /* swap values */
- const oid h = src_h[p];
- const @1 t = src_t[p];
- src_h[p] = src_h[q];
- src_t[p] = src_t[q];
- src_h[q] = h;
- src_t[q] = t;
- p++;
- q--;
- }
- }
- if (p > pp) {
- /* exhausted left half, skip to right one */
- p = qq;
- }
- if (q < qq) {
- /* exhausted right half, skip to left one */
- q = pp;
- }
- }
-
- /* crack (remaining) consequtive piece / slice */
- while (p < q) {
- /* skip over smaller values from beginning */
- while (p < q && src_t[p] @7 mval /*@5_@3(&src_t[p], &mval,
@6@1)*/)
- p++;
- /* skip over larger values from end */
- while (p < q && src_t[q] @8 mval /*@5_@4(&src_t[q], &mval,
@6@1)*/)
- q--;
- if (p < q) {
- /* swap values */
- const oid h = src_h[p];
- const @1 t = src_t[p];
- src_h[p] = src_h[q];
- src_t[p] = src_t[q];
- src_h[q] = h;
- src_t[q] = t;
- p++;
- q--;
- }
- }
-
- /* return pivot position */
- while (p <= last && src_t[p] @7 mval /*@5_@3(&src_t[p], &mval, @6@1)*/)
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
