Changeset: 6a7f7c065a0c for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=6a7f7c065a0c Added Files: monetdb5/modules/mal/mosaic_frame.c monetdb5/modules/mal/mosaic_frame.h Branch: mosaic Log Message:
Replace variance with frame-based delta diffs (truncated from 1030 to 300 lines): diff --git a/monetdb5/modules/mal/mosaic_frame.c b/monetdb5/modules/mal/mosaic_frame.c new file mode 100644 --- /dev/null +++ b/monetdb5/modules/mal/mosaic_frame.c @@ -0,0 +1,977 @@ +/* + * The contents of this file are subject to the MonetDB Public License + * Version 1.1 (the "License"); you may not use this file except in + * compliance with the License. You may obtain a copy of the License at + * http://www.monetdb.org/Legal/MonetDBLicense + * + * Software distributed under the License is distributed on an "AS IS" + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the + * License for the specific language governing rights and limitations + * under the License. + * + * The Original Code is the MonetDB Database System. + * + * The Initial Developer of the Original Code is CWI. + * Portions created by CWI are Copyright (C) 1997-July 2008 CWI. + * * Copyright August 2008-2014 MonetDB B.V. + * All Rights Reserved. + */ + +/* + * (c)2014 author Martin Kersten + * Use the dictionary space to administer deltas wrt frame of reference value + */ + +#include "monetdb_config.h" +#include "mosaic.h" +#include "mosaic_frame.h" + +void +MOSadvance_frame(Client cntxt, MOStask task) +{ + int *dst = (int*) (((char*) task->blk) + MosaicBlkSize); + long cnt = MOSgetCnt(task->blk); + long bytes; + (void) cntxt; + + assert(cnt > 0); + task->start += (oid) cnt; + task->stop = task->elm; + bytes = (cnt * task->hdr->framebits)/8 + (((cnt * task->hdr->framebits) %8) != 0) + sizeof(unsigned long); + task->blk = (MosaicBlk) (((char*) dst) + wordaligned(bytes, lng)); +} + +/* Beware, the dump routines use the compressed part of the task */ +void +MOSdump_frame(Client cntxt, MOStask task) +{ + MosaicHdr hdr= task->hdr; + int i; + void *val = (void*)hdr->frame; + + mnstr_printf(cntxt->fdout,"# framebits %d",hdr->framebits); + switch(ATOMstorage(task->type)){ + case TYPE_sht: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"sht [%d] %hd ",i, ((sht*) val)[i]); break; + case TYPE_int: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"int [%d] %d ",i, ((int*) val)[i]); break; + case TYPE_oid: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"oid [%d] "OIDFMT, i, ((oid*) val)[i]); break; + case TYPE_lng: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"lng [%d] "LLFMT, i, ((lng*) val)[i]); break; +#ifdef HAVE_HGE + case TYPE_hge: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"hge [%d] %.40g ", i, (dbl) ((hge*) val)[i]); break; +#endif + case TYPE_wrd: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"wrd [%d] "SZFMT, i, ((wrd*) val)[i]); break; + case TYPE_flt: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"flt [%d] %f ",i, ((flt*) val)[i]); break; + case TYPE_dbl: + for(i=0; i< hdr->framesize; i++) + mnstr_printf(cntxt->fdout,"dbl [%d] %g ",i, ((dbl*) val)[i]); break; + } + mnstr_printf(cntxt->fdout,"\n"); +} + +void +MOSskip_frame(Client cntxt, MOStask task) +{ + MOSadvance_frame(cntxt, task); + if ( MOSgetTag(task->blk) == MOSAIC_EOL) + task->blk = 0; // ENDOFLIST +} + +#define MOSfind(X,VAL,F,L)\ +{ int m,f= F, l=L; \ + while( l-f > 0 ) { \ + m = f + (l-f)/2;\ + if ( VAL < dict[m] ) l=m-1; else f= m;\ + if ( VAL > dict[m] ) f=m+1; else l= m;\ + }\ + X= f;\ +} + +#define estimateFrame(TPE)\ +{ TPE *val = ((TPE*)task->src) + task->start, frame = *val, delta;\ + TPE *dict= (TPE*)hdr->frame;\ + for(i =task->start; i<task->stop; i++, val++){\ + delta = *val - frame;\ + MOSfind(j,delta,0,hdr->framesize);\ + if( j == hdr->framesize || dict[j] != delta )\ + break;\ + }\ + i -= task->start;\ + if ( i > MOSlimit() ) i = MOSlimit();\ + if(i) factor = (flt) ((int)i * sizeof(int)) / wordaligned( MosaicBlkSize + i,TPE);\ +} + +// store it in the compressed heap header directly +// filter out the most frequent ones +#define makeFrame(TPE)\ +{ TPE *val = ((TPE*)task->src) + task->start, frame = *val, delta;\ + TPE *dict = (TPE*)hdr->frame,v;\ + for(i =task->start; i< task->stop; i++, val++){\ + delta = *val - frame;\ + for(j= 0; j< hdr->framesize; j++)\ + if( dict[j] == delta) break;\ + if ( j == hdr->framesize){\ + if ( hdr->framesize == 256){\ + int min = 0;\ + for(j=1;j<256;j++)\ + if( cnt[min] <cnt[j]) min = j;\ + j=min;\ + cnt[j]=0;\ + break;\ + }\ + dict[j] = delta;\ + cnt[j]++;\ + hdr->framesize++;\ + } else\ + cnt[j]++;\ + }\ + for(i=0; i< (BUN) hdr->framesize; i++)\ + for(j=i+1; j< hdr->framesize; j++)\ + if(dict[i] >dict[j]){\ + v= dict[i];\ + dict[i] = dict[j];\ + dict[j] = v;\ + }\ + hdr->framebits = 1;\ + hdr->mask =1;\ + for( i=1 ; i < (BUN) hdr->framesize-1; i *=2){\ + hdr->framebits++;\ + hdr->mask = (hdr->mask <<1) | 1;\ + }\ +} + + +void +MOScreateframe(Client cntxt, MOStask task) +{ BUN i; + int j; + MosaicHdr hdr = task->hdr; + lng cnt[256]; + + (void) cntxt; + for(j=0;j<256;j++) + cnt[j]=0; + hdr->framesize = 0; + switch(ATOMstorage(task->type)){ + case TYPE_sht: makeFrame(sht); break; + case TYPE_lng: makeFrame(lng); break; + case TYPE_oid: makeFrame(oid); break; + case TYPE_wrd: makeFrame(wrd); break; + case TYPE_flt: makeFrame(flt); break; + case TYPE_dbl: makeFrame(dbl); break; +#ifdef HAVE_HGE + case TYPE_hge: makeFrame(hge); break; +#endif + case TYPE_int: + { int *val = ((int*)task->src) + task->start, frame = *val, delta; + int *dict = (int*)hdr->frame,v; + + for(i =task->start; i< task->stop; i++, val++){ + delta = *val - frame; + for(j= 0; j< hdr->framesize; j++) + if( dict[j] == delta) break; + if ( j == hdr->framesize){ + if ( hdr->framesize == 256){ + int min = 0; + // select low frequent candidate + for(j=1;j<256;j++) + if( cnt[min] <cnt[j]) min = j; + j=min; + cnt[j]=0; + break; + } + dict[j] = delta; + cnt[j]++; + hdr->framesize++; + } else + cnt[j]++; + } + // sort it + for(i=0; i< (BUN) hdr->framesize; i++) + for(j=i+1; j< hdr->framesize; j++) + if(dict[i] >dict[j]){ + v= dict[i]; + dict[i] = dict[j]; + dict[j] = v; + } + hdr->framebits = 1; + hdr->mask =1; + for( i=1 ; i < (BUN) hdr->framesize-1; i *=2){ + hdr->framebits++; + hdr->mask = (hdr->mask <<1) | 1; + } + } + } +#ifdef _DEBUG_MOSAIC_ + MOSdump_frame(cntxt, task); +#endif +} + +// calculate the expected reduction using dictionary in terms of elements compressed +flt +MOSestimate_frame(Client cntxt, MOStask task) +{ BUN i = -1; + int j; + flt factor= 1.0; + MosaicHdr hdr = task->hdr; + (void) cntxt; + + switch(ATOMstorage(task->type)){ + //case TYPE_bte: CASE_bit: no compression achievable + case TYPE_sht: estimateFrame(sht); break; + case TYPE_lng: estimateFrame(lng); break; + case TYPE_oid: estimateFrame(oid); break; + case TYPE_wrd: estimateFrame(wrd); break; + case TYPE_flt: estimateFrame(flt); break; + case TYPE_dbl: estimateFrame(dbl); break; +#ifdef HAVE_HGE + case TYPE_hge: estimateFrame(hge); break; +#endif + case TYPE_int: + { int *val = ((int*)task->src) + task->start, frame = *val, delta; + int *dict = (int*)hdr->frame; + for(i =task->start; i<task->stop; i++, val++){ + delta= *val - frame; + MOSfind(j,delta,0,hdr->framesize); + if( j == hdr->framesize || dict[j] != delta) + break; + } + i -= task->start; + if ( i > MOSlimit() ) i = MOSlimit(); + if(i) factor = (flt) ((int)i * sizeof(int)) / wordaligned( MosaicBlkSize + i,lng); + } + } +#ifdef _DEBUG_MOSAIC_ + mnstr_printf(cntxt->fdout,"#estimate dict "BUNFMT" elm %4.2f factor\n", i, factor); +#endif + return factor; +} + +// insert a series of values into the compressor block using frame +#define framecompress(Vector,I,Bits,Value)\ +{int cid,lshift,rshift;\ + cid = (I * Bits)/64;\ + lshift= 63 -((I * Bits) % 64) ;\ + if ( lshift >= Bits){\ + Vector[cid]= Vector[cid] | (((unsigned long) Value) << (lshift- Bits));\ + }else{ \ + rshift= 63 - ((I+1) * Bits) % 64;\ + Vector[cid]= Vector[cid] | (((unsigned long) Value) >> (Bits-lshift));\ + Vector[cid+1]= 0 | (((unsigned long) Value) << rshift);\ +}} + +#define FRAMEcompress(TPE)\ +{ TPE *val = ((TPE*)task->src) + task->start, frame = *val, delta;\ + TPE *dict = (TPE*)hdr->frame;\ + BUN limit = task->stop - task->start > MOSlimit()? task->start + MOSlimit(): task->stop;\ + task->dst = ((char*) task->blk)+ MosaicBlkSize;\ + *(TPE*) task->dst = frame;\ + base = (unsigned long*) (((char*) task->blk) + 2 * MosaicBlkSize);\ + base[0]=0;\ + for(i =task->start; i<limit; i++, val++){\ + delta = *val - frame;\ + MOSfind(j,delta,0,hdr->framesize);\ + if(j == hdr->framesize || dict[j] != delta) \ + break;\ + else {\ + MOSincCnt(blk,1);\ + framecompress(base,(i- task->start),hdr->framebits,j);\ + }\ + }\ + assert(i);\ +} + _______________________________________________ checkin-list mailing list [email protected] https://www.monetdb.org/mailman/listinfo/checkin-list
