Changeset: 7bfcfcbae289 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=7bfcfcbae289
Modified Files:
monetdb5/extras/crackers/crackers.mx
monetdb5/extras/crackers/crackers_core_unordered.mx
monetdb5/extras/crackers/crackers_select_ops.mx
monetdb5/extras/crackers/crackers_selecthol_ops.mx
monetdb5/extras/crackers/crackers_selectholpl_ops.mx
monetdb5/extras/crackers/crackers_selectholst_ops.mx
monetdb5/extras/crackers/crackers_selectpl_ops.mx
monetdb5/extras/crackers/crackers_selectst_ops.mx
Branch: holindex
Log Message:
my take on (experimental) multi-threaded crack ("in two", only) implementation:
added crackers.(|theta)(|u)select() variants with extra "nthreads" argument:
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.
added multi-threaded implementations of "crack-in-two" (only) routines:
deviding the to-be-cracked piece into nthreads slices,
nthreads threads first count the smaller/larger than pivot values per slice,
then, nthreads threads "crack" the values into their final position in a
temporary array,
finally, the temporary array is copied back in place using memcpy.
All threads work in parallel without need for locking.
diffs (truncated from 903 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
@@ -181,6 +181,9 @@ comment "clear all debugging map ";
#
@= Select
+
+# original single-threaded versions
+
command select(b:bat[:oid,:@2],l:@2,h:@2):bat[:oid,:@2]
address CRKselect_@2
comment "Retrieve the subset using a cracker
@@ -221,6 +224,81 @@ address CRKthetaselect_@2
comment "Retrieve the subset using a cracker
index producing preferably a BATview.";
+# new multi-threaded versions
+
+command select(b:bat[:oid,:@2],l:@2,h:@2, nthreads:int):bat[:oid,:@2]
+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.";
+
+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.";
+
+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.";
+
+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.";
+
+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.";
+
+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.";
+
+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.";
+
+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.";
+
+#
command parallelselect(b:bat[:oid,:@2],l:@2,h:@2,li:bit,hi:bit):bat[:oid,:@2]
address CRKparallelselectBounds_@2
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
@@ -96,20 +96,20 @@ All Rights Reserved.
* @- Exported signatures
*/
@= CoreUnorderedFunctions_decl
-crackers_export str CRKcrackUnorderedZero_@1 (int *res, int *bid, @1 *mid);
+crackers_export str CRKcrackUnorderedZero_@1 (int *res, int *bid, @1 *mid, int
nthreads);
crackers_export str CRKcrackUnorderedThree_@1 (int *res, int *bid, @1 *low, @1
*hgh);
@
* @- Signatures shared within the crackers module/library
@= operations
-@:crackInTwoUnorderedPieces@4(@1,LE,LE,GT,@2,@3)@
-@:crackInTwoUnorderedPieces@4(@1,RE,LT,GE,@2,@3)@
+@:crackInTwoUnorderedPieces@4(@1,LE,LE,GT,@2,@3,<=,>)@
+@:crackInTwoUnorderedPieces@4(@1,RE,LT,GE,@2,@3,<,>=)@
@:crackInThreeUnorderedPieces@4(@1,LO,RE,LE,GT,LE,GT,@2,@3)@
@:crackInThreeUnorderedPieces@4(@1,LE,RE,LT,GE,LE,GT,@2,@3)@
@:crackInThreeUnorderedPieces@4(@1,LO,RO,LE,GT,LT,GE,@2,@3)@
@:crackInThreeUnorderedPieces@4(@1,LE,RO,LT,GE,LT,GE,@2,@3)@
@
@= crackInTwoUnorderedPieces_decl
-str CRKcrackUnorderedZero_@2_@1( BAT *b, @1 mval, oid first, oid last, oid
*pos);
+str CRKcrackUnorderedZero_@2_@1( BAT *b, @1 mval, oid first, oid last, oid
*pos, int nthreads);
@
@= crackInThreeUnorderedPieces_decl
str CRKcrackUnorderedThree_@2_@3_@1( BAT *b, @1 low, @1 hgh, oid first, oid
last, oid *posl, oid *posh);
@@ -154,6 +154,24 @@ str CRKcrackUnorderedThreeSideways_@3_@4
#include "monetdb_config.h"
#include "crackers.h"
+#define CRACK_MUTLI_THREAD_DEBUG
+
+/* argument struct for countThread & crackThread functions */
+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 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 */
+} c_Thread_t;
+
/* Functions shared within the crackers module/library */
@:TypeSwitch(operations,_impl)@
@:TypeSwitch_4(operationsSideways,_impl)@
@@ -166,7 +184,7 @@ str CRKcrackUnorderedThreeSideways_@3_@4
*/
@= CoreUnorderedFunctions_impl
str
-CRKcrackUnorderedZero_@1 (int *res, int *bid, @1 *mid){
+CRKcrackUnorderedZero_@1 (int *res, int *bid, @1 *mid, int nthreads){
BAT *b;
str msg;
oid pos;
@@ -178,7 +196,7 @@ CRKcrackUnorderedZero_@1 (int *res, int
/* if( sizeof(struct SCRATCH{ oid hdummy; @1 tdummy; } ) != BUNsize(b) )
throw(MAL, "crackers.crack_zeroUnordered", "Need more clever
mapping ");
*/
- msg = CRKcrackUnorderedZero_LE_@1( b, *mid,(BUN) 0, BATcount(b)-1,
&pos);
+ msg = CRKcrackUnorderedZero_LE_@1( b, *mid,(BUN) 0, BATcount(b)-1,
&pos, nthreads);
BBPkeepref(b->batCacheid);
*res = *bid;
@@ -209,13 +227,23 @@ CRKcrackUnorderedThree_@1 (int *res, int
@
* @- Functions shared within the crackers module/library
@= crackInTwoUnorderedPieces_impl
-str
-CRKcrackUnorderedZero_@2_@1( BAT *b, @1 mval, BUN first, BUN last, oid *pos){
+
+
+/* original single-threaded crack code */
+static str
+CRKcrackUnorderedZero_@2_@1_ST( BAT *b, @1 mval, BUN first, BUN last, oid
*pos){
@1 *ft, *lt, *t0;
oid *fh, *lh;
oid hdummy;
@1 tdummy;
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ lng t_0, t_1;
+ fprintf(stderr,
+ "CRKcrackUnorderedZero_@2_@1_ST ( %d, "LLFMT", "BUNFMT",
"BUNFMT" ) ...\n",
+ b->batCacheid, (lng) mval, first, last);
+ t_0 = GDKusec();
+ #endif
/* set bounds for the iterator */
t0 = (@1 *)Tloc(b, BUNfirst(b));
@@ -257,10 +285,383 @@ CRKcrackUnorderedZero_@2_@1( BAT *b, @1
else
*pos = (oid) BUNfirst(b);
}
+
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ t_1 = GDKusec();
+ fprintf(stderr,
+ "CRKcrackUnorderedZero_@2_@1_ST ( %d, "LLFMT", "BUNFMT",
"BUNFMT" ) -> "OIDFMT" : %.6f secs\n",
+ b->batCacheid, (lng) mval, first, last, *pos, (dbl) (t_1 - t_0)
/ 1000000.0);
+ #endif
return MAL_SUCCEED;
}
+
+/* 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 )
+{
+ BUN p = 0, q = last - first;
+ 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);
+ t_0 = GDKusec();
+ #endif
+
+ /* input (source) arrays */
+ src_h = (oid*) Hloc(b, BUNfirst(b) + first);
+ src_t = (@1 *) Tloc(b, BUNfirst(b) + first);
+
+ 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 */
+ q = last - first;
+ while (p <= q && src_t[p] @7 mval /*@5_@3(&src_t[p], &mval, @6@1)*/)
+ p++;
+ *pos = (oid) (first + p - 2);
+
+ #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);
+ #endif
+
+ return MAL_SUCCEED;
+}
+
+
+/* countThread for new multi-threaded crack code */
+static void*
+CRKcrackUnorderedZero_@2_@1_MT_countThread ( 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;
+ #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);
+ 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)*/]++;
+ }
+
+ #ifdef CRACK_MUTLI_THREAD_DEBUG
+ t_1 = GDKusec();
+ fprintf(stderr,
+ "CRKcrackUnorderedZero_@2_@1_MT_countThread ( %d, "LLFMT",
"BUNFMT" ) -> "BUNFMT", "BUNFMT" : %.6f s\n",
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
http://mail.monetdb.org/mailman/listinfo/checkin-list
