Changeset: a90871b89c0d for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=a90871b89c0d
Modified Files:
monetdb5/extras/crackers/crackers.mx
monetdb5/extras/crackers/crackers_core_unordered.mx
Branch: holindex
Log Message:
revised (experimental) multi-threaded crack ("in two", only) implementation:
replaced previous three-phase "count-crack-restore" by two-phase
- first crack individual slices (one per thread) concurrently,
- then "meta"-crack slices to create final result.
implemented 2 alternatives:
1) ("inferior"):
- each thread cracks one consecutive slice
2) ("superior"):
- nthreads-1 threads crack two disjoint half-slices
(from either end of the input piece), each
- last thread cracks center consecutive slice
adjusted semantics of crackers.(|theta)(|u)select(...,nthreads) calls:
- nthreads == 0 -> revised single-threaded implementation,
- nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
- nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.
diffs (truncated from 722 to 300 lines):
diff --git a/monetdb5/extras/crackers/crackers.mx
b/monetdb5/extras/crackers/crackers.mx
--- a/monetdb5/extras/crackers/crackers.mx
+++ b/monetdb5/extras/crackers/crackers.mx
@@ -231,72 +231,72 @@ address CRKselect_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command select(b:bat[:oid,:@2],l:@2, nthreads:int):bat[:oid,:@2]
address CRKselectValue_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command select(b:bat[:oid,:@2],l:@2,h:@2,li:bit,hi:bit,
nthreads:int):bat[:oid,:@2]
address CRKselectBounds_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command uselect(b:bat[:any_1,:@2],l:@2,h:@2, nthreads:int):bat[:any_1,:void]
address CRKuselect_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command uselect(b:bat[:any_1,:@2],l:@2, nthreads:int):bat[:any_1,:void]
address CRKuselectValue_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command uselect(b:bat[:any_1,:@2],l:@2,h:@2,li:bit,hi:bit,
nthreads:int):bat[:any_1,:void]
address CRKuselectBounds_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command thetauselect(b:bat[:any_1,:@2],v:@2,op:str,
nthreads:int):bat[:any_1,:void]
address CRKthetauselect_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
command thetaselect(b:bat[:any_1,:@2],v:@2,op:str,
nthreads:int):bat[:any_1,:@2]
address CRKthetaselect_@2_MT
comment "Retrieve the subset using a cracker
index producing preferably a BATview;
nthreads == nil -> original single-threaded implementation,
- nthreads == -1 -> revised single-threaded implementation,
- nthreads == 0 -> new multi-threaded implementation with
gdk_nr_threads threads,
- nthreads > 0 -> new multi-threaded implementation with nthreads
threads.";
+ nthreads == 0 -> revised single-threaded implementation,
+ nthreads < 0 -> 1st (inferior) version of new multi-threaded
implementation,
+ nthreads > 0 -> 2nd (superior) version of new multi-threaded
implementation.";
#
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
@@ -161,15 +161,13 @@ typedef struct {
#ifdef CRACK_MUTLI_THREAD_DEBUG
int id; /* thread id */
#endif
- BUN n; /* # tuples / values per piece / thread */
- BUN *cnt_off; /* counts/offsets pair:
- [0] = first piece / smaller values
- [1] = second piece / larger values */
+ const BAT *b; /* BAT to be cracked */
const void *mval; /* pivot value */
- const void *src_t; /* input / source tail */
- const oid *src_h; /* input / source head */
- void *dst_t; /* output / destination tail */
- oid *dst_h; /* output / destination head */
+ BUN first; /* offset of first value in slice */
+ BUN last; /* offset of last value in slice */
+ BUN pos; /* offset of pivot value */
+ const char *msg; /* error message */
+ BUN m; /* size of half slice */
} c_Thread_t;
/* Functions shared within the crackers module/library */
@@ -299,24 +297,60 @@ CRKcrackUnorderedZero_@2_@1_ST( BAT *b,
/* revised single-threaded crack code */
static str
-CRKcrackUnorderedZero_@2_@1_STx ( const BAT *b, const @1 mval, const BUN
first, const BUN last, oid *pos )
+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 = 0, q = last - first;
+ BUN p = first, q = last, pp = p + m - 1, qq = q - m + 1;
oid *src_h;
@1 *src_t;
#ifdef CRACK_MUTLI_THREAD_DEBUG
lng t_0, t_1;
fprintf(stderr,
- "CRKcrackUnorderedZero_@2_@1_STx ( %d, "LLFMT", "BUNFMT",
"BUNFMT" ) ...\n",
- b->batCacheid, (lng) mval, first, last);
+ "CRKcrackUnorderedZero_@2_@1_STx ( %d, "LLFMT", "BUNFMT",
"BUNFMT", "BUNFMT" ) ...\n",
+ b->batCacheid, (lng) mval, first, last, m);
t_0 = GDKusec();
#endif
/* input (source) arrays */
- src_h = (oid*) Hloc(b, BUNfirst(b) + first);
- src_t = (@1 *) Tloc(b, BUNfirst(b) + first);
+ src_h = (oid*) Hloc(b, BUNfirst(b));
+ src_t = (@1 *) Tloc(b, BUNfirst(b));
+ 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)*/)
@@ -338,58 +372,50 @@ CRKcrackUnorderedZero_@2_@1_STx ( const
}
/* return pivot position */
- q = last - first;
- while (p <= q && src_t[p] @7 mval /*@5_@3(&src_t[p], &mval, @6@1)*/)
+ while (p <= last && src_t[p] @7 mval /*@5_@3(&src_t[p], &mval, @6@1)*/)
p++;
- *pos = (oid) (first + p - 1);
+ *pos = (oid) (p - 1);
#ifdef CRACK_MUTLI_THREAD_DEBUG
t_1 = GDKusec();
fprintf(stderr,
- "CRKcrackUnorderedZero_@2_@1_STx ( %d, "LLFMT", "BUNFMT",
"BUNFMT" ) -> "OIDFMT" : %.6f secs\n",
- b->batCacheid, (lng) mval, first, last, *pos, (dbl) (t_1 - t_0)
/ 1000000.0);
+ "CRKcrackUnorderedZero_@2_@1_STx ( %d, "LLFMT", "BUNFMT",
"BUNFMT", "BUNFMT" ) -> "OIDFMT" : %.6f %s\n",
+ b->batCacheid, (lng) mval, first, last, m, *pos, (dbl) (t_1 -
t_0) / 1000000.0, secs);
#endif
return MAL_SUCCEED;
}
-/* countThread for new multi-threaded crack code */
+/* crackThread for new multi-threaded crack code */
static void*
-CRKcrackUnorderedZero_@2_@1_MT_countThread ( void *arg_p )
+CRKcrackUnorderedZero_@2_@1_MT_crackThread ( void *arg_p )
{
c_Thread_t *arg = (c_Thread_t*) arg_p;
- #ifdef CRACK_MUTLI_THREAD_DEBUG
- const int id = arg->id; /* thread id */
- #endif
- const BUN n = arg->n; /* # tuples / values per
piece / thread */
- BUN *cnt = arg->cnt_off; /* counts/offsets pair:
- [0] = first piece /
smaller values
- [1] = second piece /
larger values */
- const @1 mval = * (@1*) arg->mval; /* pivot value */
- const @1 *src_t = (const @1*) arg->src_t; /* input / source tail */
- BUN i;
+ @1 mval = * (@1*) arg->mval;
+ oid pos;
#ifdef CRACK_MUTLI_THREAD_DEBUG
lng t_0, t_1;
fprintf(stderr,
- "CRKcrackUnorderedZero_@2_@1_MT_countThread ( %d, "LLFMT",
"BUNFMT" ) ...\n",
- id, (lng) mval, n);
+ "CRKcrackUnorderedZero_@2_@1_MT_crackThread ( %d, "LLFMT",
"BUNFMT", "BUNFMT", "BUNFMT" ) ...\n",
+ arg->id, (lng) mval, arg->first, arg->last, arg->m);
t_0 = GDKusec();
#endif
- /* count smaller / larger values */
- for (i = 0; i < n; i++) {
- /* [0] = first piece / smaller values */
- /* [1] = second piece / larger values */
- cnt[src_t[i] @8 mval /*@5_@4(&src_t[i], &mval, @6@1)*/]++;
- }
+ /* call actual cracking routine for this slice */
+ arg->msg = CRKcrackUnorderedZero_@2_@1_STx ( arg->b, mval, arg->first,
arg->last, arg->m, &pos
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ , "se"
+ #endif
+ );
+ arg->pos = (BUN) pos;
#ifdef CRACK_MUTLI_THREAD_DEBUG
t_1 = GDKusec();
fprintf(stderr,
- "CRKcrackUnorderedZero_@2_@1_MT_countThread ( %d, "LLFMT",
"BUNFMT" ) -> "BUNFMT", "BUNFMT" : %.6f s\n",
- id, (lng) mval, n, cnt[0], cnt[1], (dbl) (t_1 - t_0) /
1000000.0);
+ "CRKcrackUnorderedZero_@2_@1_MT_crackThread ( %d, "LLFMT",
"BUNFMT", "BUNFMT", "BUNFMT" ) -> "OIDFMT" : %.6f s\n",
+ arg->id, (lng) mval, arg->first, arg->last, arg->m, pos, (dbl)
(t_1 - t_0) / 1000000.0);
#endif
pthread_exit(NULL);
@@ -397,74 +423,25 @@ CRKcrackUnorderedZero_@2_@1_MT_countThre
}
-/* crackThread for new multi-threaded crack code */
-static void*
-CRKcrackUnorderedZero_@2_@1_MT_crackThread ( void *arg_p )
+/* new multi-threaded crack code; Alternative 2 */
+static str
+CRKcrackUnorderedZero_@2_@1_MT ( const BAT *b, const @1 mval, const BUN first,
const BUN last, oid *pos, int nthreads, int alt )
{
- c_Thread_t *arg = (c_Thread_t*) arg_p;
- #ifdef CRACK_MUTLI_THREAD_DEBUG
- const int id = arg->id; /* thread id */
- #endif
- const BUN n = arg->n; /* # tuples / values per piece /
thread */
- BUN *off = arg->cnt_off; /* counts/offsets pair:
- [0] = first piece / smaller
values
- [1] = second piece / larger
values */
- const @1 mval = * (@1*) arg->mval; /* pivot value */
- const @1 *src_t = (@1*) arg->src_t; /* input / source tail */
- const oid *src_h = arg->src_h; /* input / source head */
- @1 *dst_t = (@1*) arg->dst_t; /* output / destination tail */
- oid *dst_h = arg->dst_h; /* output / destination head */
- BUN i;
- #ifdef CRACK_MUTLI_THREAD_DEBUG
- lng t_0, t_1;
-
- fprintf(stderr,
- "CRKcrackUnorderedZero_@2_@1_MT_crackThread ( %d, "LLFMT",
"BUNFMT", "BUNFMT", "BUNFMT" ) ...\n",
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
