Re: [Monetdb-developers] [Monetdb-checkins] MonetDB5/src/modules/mal algebraExtensions.mx, , 1.32, 1.33
On Sat, Jul 18, 2009 at 10:21:00AM +0000, Lefteris Sidirourgos wrote:
Update of /cvsroot/monetdb/MonetDB5/src/modules/mal In directory 23jxhf1.ch3.sourceforge.com:/tmp/cvs-serv30235
Modified Files: algebraExtensions.mx Log Message: load and unload the bats in each round of bloom prejoin, assuming that both dont fit in memory at the same time
... results in (when comfigured with optimization enabled): ======== gcc -DHAVE_CONFIG_H -I. -I/ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal -I../../.. -I/ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal -I../atoms -I/ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/../atoms -I../kernel -I/ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/../kernel -I../../mal -I/ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/../../mal -I/ufs/manegold/_/scratch0/Monet/Testing/Current/prefix.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/include/MonetDB -I/ufs/manegold/_/scratch0/Monet/Testing/Current/prefix.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/include/MonetDB/mapilib -I/ufs/manegold/_/scratch0/Monet/Testing/Current/prefix.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/include/MonetDB -I/ufs/manegold/_/scratch0/Monet/Testing/Current/prefix.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/include/MonetDB/common -I/ufs/manegold/_/scratch0/Monet/Testing/Current/prefix.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/include/MonetDB/gdk -I/usr/include/libxml2 -std=c99 -DLIBALGEBRAEXTENSIONS -O2 -Wall -Wextra -O6 -fomit-frame-pointer -finline-functions -falign-loops=4 -falign-jumps=4 -falign-functions=4 -fexpensive-optimizations -funroll-loops -frerun-cse-after-loop -frerun-loop-opt -ftree-vectorize -Werror-implicit-function-declaration -Werror -Wpointer-arith -Wdeclaration-after-statement -Wundef -Wp,-D_FORTIFY_SOURCE=2 -D_REENTRANT -c algebraExtensions.c -fPIC -DPIC -o .libs/lib_algebraExtensions_la-algebraExtensions.o cc1: warnings being treated as errors /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx: In function ‘GDKbloomfilter_int_l’: /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:406: error: ‘blim’ may be used uninitialized in this function /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:660: note: ‘blim’ was declared here /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:410: error: ‘blog’ may be used uninitialized in this function /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:661: note: ‘blog’ was declared here /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:416: error: ‘bv’ may be used uninitialized in this function /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:658: note: ‘bv’ was declared here /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:423: error: ‘clim’ may be used uninitialized in this function /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:660: note: ‘clim’ was declared here /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:425: error: ‘cv’ may be used uninitialized in this function /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:658: note: ‘cv’ was declared here /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:443: error: ‘clog’ may be used uninitialized in this function /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:661: note: ‘clog’ was declared here /ufs/manegold/_/scratch0/Monet/Testing/Current/source/MonetDB5/src/modules/mal/algebraExtensions.mx:659: error: ‘b’ may be used uninitialized in this function make[8]: *** [lib_algebraExtensions_la-algebraExtensions.lo] Error 1 make[8]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src/modules/mal' make[7]: *** [all-recursive] Error 1 make[7]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src/modules/mal' make[6]: *** [all] Error 2 make[6]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src/modules/mal' make[5]: *** [all-recursive] Error 1 make[5]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src/modules' make[4]: *** [all] Error 2 make[4]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src/modules' make[3]: *** [all-recursive] Error 1 make[3]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src' make[2]: *** [all] Error 2 make[2]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5/src' make[1]: *** [all-recursive] Error 1 make[1]: Leaving directory `/net/rig.ins.cwi.nl/export/scratch0/manegold/Monet/Testing/Current/build.--enable-strict_--disable-debug_--enable-optimize_--disable-assert/MonetDB5' make: *** [all] Error 2 ======== Stefan
U algebraExtensions.mx Index: algebraExtensions.mx =================================================================== RCS file: /cvsroot/monetdb/MonetDB5/src/modules/mal/algebraExtensions.mx,v retrieving revision 1.32 retrieving revision 1.33 diff -u -d -r1.32 -r1.33 --- algebraExtensions.mx 18 Jul 2009 08:43:03 -0000 1.32 +++ algebraExtensions.mx 18 Jul 2009 10:20:58 -0000 1.33 @@ -110,7 +110,7 @@ is calculated for the heap(s) only. @c
-/* #define DEBUG_BLOOMFILTER*/ +#define DEBUG_BLOOMFILTER
static size_t GDKbatfootprint(BAT *b){ @@ -274,7 +274,7 @@ cp = BATslice(cr, cl, cl+blk); j = BATjoin(b,cp, BUN_NONE); #ifdef DEBUG_BLOOMFILTER - stream_printf(GDKout,"result " SZFMT " " SZFMT " " SZFMT "\n", bl, cl, BATcount(j)); + stream_printf(GDKout,"result " SZFMT " " SZFMT " " SZFMT "\n", blk, cl, BATcount(j)); #endif if (bn == 0) bn = BATnew( j->htype, j->ttype, BATcount(j)*blim/blk); @@ -375,6 +375,30 @@ }
#define bloomhash(x,y,z) ((unsigned int) ((x)*(y))%(z)) +#define bloomhash1(x,y,z) ((int) ((((x)*((double)y))-((int)((x)*(y))))*(z))) +/* #define bloomhash1(x,y,z) ((unsigned int) ((x)*(y))%(z)) */ + +/*static double primes[]= {19,29,31,41,43,53,59,61};*/ + +@= print_bbloom +#ifdef DEBUG_BLOOMFILTER +counter = 0; +for (i = 0; i < mb; i++) { + counter += bbloom[i]; +} +stream_printf(GDKout,"bbloom has %d 1's and %d 0's\n", counter, mb-counter); +counter = 0; +#endif + +@= print_cbloom +#ifdef DEBUG_BLOOMFILTER +counter = 0; +for (i = 0; i < mc; i++) { + counter += cbloom[i]; +} +stream_printf(GDKout,"cbloom has %d 1's and %d 0's\n", counter, mc-counter); +counter = 0; +#endif
@= body_smallsubset char *bbloom; @@ -474,42 +498,91 @@
@= body_outofmemory char * cbloom, *bbloom; - int bp[4]; - int cp[4]; + char bit; + /*int bp[4]; + int cp[4];*/ + double bp[4]; + double cp[4]; int counter = 0; + + b = BATdescriptor(*bid); + bv = (int*) Tloc(b, BUNfirst(b)); + blim = BATcount(b); + blog = (int) log(blim); + mb = blim*2; - mc = clim*2; + //mc = clim*2; bbloom = (char *) GDKmalloc(mb); - cbloom = (char *) GDKmalloc(mc); + //cbloom = (char *) GDKmalloc(mc); memset(bbloom, 0, mb); - memset(cbloom, 0, mc); + //memset(cbloom, 0, mc); for (i = 0; i < 4; i++) { bp[i] = (1 << (blog + i))+1; - cp[i] = (1 << (clog + i))+1; + //cp[i] = (1 << (clog + i))+1; + /* + bp[i] = primes[i]/((double) (sizeof(wrd)*8)); + cp[i] = primes[i+1]/((double) (sizeof(wrd)*8)); + */ }
- /* for (b) { built bloom } */ + /* for (b) { built bloom } */ for (i = 0; i < blim; i++) { setBit(bbloom, bloomhash(bp[0],bv[i],mb), 1); } + /*@:print_bbloom@*/ + BBPunfix(*bid); + + c = BATdescriptor(*cid); + cv = (int*) Tloc(c, BUNfirst(c)); + clim = BATcount(c); + clog = (int) log(clim); + mc = clim*2; + cbloom = (char *) GDKmalloc(mc); + memset(cbloom, 0, mc); + + for (i = 0; i < 4; i++) { + cp[i] = (1 << (clog + i))+1; + }
/* for (c) { test bbloom; built cbloom } */ for (i = 0; i < clim; i++) { - if (tstBit(bbloom, bloomhash(bp[0],cv[i],mb))) { + bit = tstBit(bbloom, bloomhash(bp[0],cv[i],mb)); + setBit(cbloom, bloomhash(cp[0],cv[i],mc), + bit | tstBit(cbloom, bloomhash(cp[0],cv[i],mc))); + setBit(cbloom, bloomhash(cp[1],cv[i],mc), + bit | tstBit(cbloom, bloomhash(cp[1],cv[i],mc))); + /*if (tstBit(bbloom, bloomhash(bp[0],cv[i],mb))) { setBit(cbloom, bloomhash(cp[0],cv[i],mc), 1); setBit(cbloom, bloomhash(cp[1],cv[i],mc), 1); counter++; - } + }*/ } + /*@:print_cbloom@*/ + BBPunfix(*cid);
#ifdef DEBUG_BLOOMFILTER stream_printf(GDKout, "1st round c %d\n", counter); counter = 0; #endif
+ b = BATdescriptor(*bid); + bv = (int*) Tloc(b, BUNfirst(b)); memset(bbloom, 0, mb); /* for (b) { test cbloom; rebuilt bbloom } */ for (i = 0; i < blim; i++) { + /* + bit = tstBit(cbloom, bloomhash(cp[0],bv[i],mc)) && + tstBit(cbloom, bloomhash(cp[1],bv[i],mc)); + + setBit(bbloom, bloomhash(bp[0],bv[i],mb), + bit | tstBit(bbloom, bloomhash(bp[0],bv[i],mb))); + setBit(bbloom, bloomhash(bp[1],bv[i],mb), + bit | tstBit(bbloom, bloomhash(bp[1],bv[i],mb))); + setBit(bbloom, bloomhash(bp[2],bv[i],mb), + bit | tstBit(bbloom, bloomhash(bp[2],bv[i],mb))); + setBit(bbloom, bloomhash(bp[3],bv[i],mb), + bit | tstBit(bbloom, bloomhash(bp[3],bv[i],mb))); + */ if ((tstBit(cbloom, bloomhash(cp[0],bv[i],mc)) && tstBit(cbloom, bloomhash(cp[1],bv[i],mc)))) { setBit(bbloom, bloomhash(bp[0],bv[i],mb), 1); @@ -519,13 +592,18 @@ counter++; } } + /*@:print_bbloom@*/ + BBPunfix(*bid);
#ifdef DEBUG_BLOOMFILTER stream_printf(GDKout, "1st round b %d\n", counter); counter = 0; #endif
+ /* for (c) { check bbloom } */ + c = BATdescriptor(*cid); + cv = (int*) Tloc(c, BUNfirst(c)); *cn = BATnew(TYPE_oid,TYPE_int, clim/4); memset(cbloom, 0, mc); for (i = 0; i < clim; i++) { @@ -542,12 +620,17 @@ counter++; } } + /*@:print_cbloom@*/ + BBPunfix(*cid); + GDKfree(bbloom);
#ifdef DEBUG_BLOOMFILTER stream_printf(GDKout, "2nd round c %d\n", counter); counter = 0; #endif
+ b = BATdescriptor(*bid); + bv = (int*) Tloc(b, BUNfirst(b)); *bn = BATnew(TYPE_oid,TYPE_int, blim/4); /* for (b) {check cbloom} */ for (i = 0; i < blim; i++) { @@ -560,28 +643,30 @@ counter++; } } + BBPunfix(*bid); + GDKfree(cbloom);
#ifdef DEBUG_BLOOMFILTER stream_printf(GDKout, "2nd round b %d\n", counter); counter = 0; #endif
- @c
void -GDKbloomfilter_int_l(BAT *b, BAT *c, BAT **bn, BAT **cn, int algo) { +GDKbloomfilter_int_l(bat *bid, bat *cid, BAT **bn, BAT **cn, int algo) { int *bv, *cv; + BAT *b, *c; BUN i, blim, clim; int clog, blog; BUN mb, mc; mb = mc = 0;
- /* b is the smaller one */ + /* b is the smaller one if ( BATcount(b) > BATcount(c) ) { GDKbloomfilter_int_l(c, b, cn, bn, algo); return; - } + } */
/* consider it an out-of-memory situation if ( b->ttype != TYPE_int || GDKbatfootprint(b) < 25 ){ @@ -592,12 +677,13 @@ return; }*/
+ /* bv = (int*) Tloc(b, BUNfirst(b)); cv = (int*) Tloc(c, BUNfirst(c)); blim= BATcount(b); clim= BATcount(c); clog = (int) log(clim); - blog = (int) log(blim); + blog = (int) log(blim); */
if (algo == 2) { /* only build one bloom filter on the smaller BAT, @@ -653,6 +739,7 @@ (void) cntxt; (void) mb;
+ if ((b = BATdescriptor(*bid)) == NULL) throw(MAL, "bbp.prejoin", INTERNAL_BAT_ACCESS); if ( (c = BATdescriptor(*cid)) == NULL) { @@ -667,7 +754,7 @@ case 2: /* lefteris 1st */ case 3: /* 2nd */ case 4: /* 3rd */ - GDKbloomfilter_int_l(b, c, &bn, &cn, algo); + GDKbloomfilter_int_l(bid, cid, &bn, &cn, algo); break; case 5: /* blocked join */ bn = GDKblockjoin(b,c);
------------------------------------------------------------------------------ Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ Monetdb-checkins mailing list Monetdb-checkins@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/monetdb-checkins
-- | Dr. Stefan Manegold | mailto:Stefan.Manegold@cwi.nl | | CWI, P.O.Box 94079 | http://www.cwi.nl/~manegold/ | | 1090 GB Amsterdam | Tel.: +31 (20) 592-4212 | | The Netherlands | Fax : +31 (20) 592-4312 |
participants (1)
-
Stefan Manegold