Changeset: 88bd32babd47 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=88bd32babd47
Modified Files:
monetdb5/mal/mal_recycle.c
Branch: default
Log Message:
Another round over the recycling policy
Based on experiences against tpch, the recycler policy is simplified
by taking note of the amount of free memory to keep intermediates
and LRU in all other cases.
Stability is not yet guaranteed.
diffs (truncated from 596 to 300 lines):
diff --git a/monetdb5/mal/mal_recycle.c b/monetdb5/mal/mal_recycle.c
--- a/monetdb5/mal/mal_recycle.c
+++ b/monetdb5/mal/mal_recycle.c
@@ -87,6 +87,7 @@ static lng recyclerSavings = 0;
static lng recycled=0;
static lng statements =0;
static lng recycleSearchTime =0; /* cache search time in ms*/
+static lng recycleSearchCalls =0;
/*
* The profiler record is re-used to store recycler information.
@@ -127,7 +128,6 @@ static lng recycleSearchTime =0; /* cach
static str bindRef = 0, bind_idxRef = 0, sqlRef = 0;
static str subselectRef = 0, thetasubselectRef = 0, likesubselectRef = 0;
-static void RECYCLEexitImpl(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
InstrPtr p, RuntimeProfile prof);
static void RECYCLEdumpInternal(stream *s);
/*
@@ -203,87 +203,77 @@ RECYCLEgarbagecollect(MalBlkPtr mb, Inst
}
/* leaves : array of indices of leaf instructions */
-/* choose victum based on the predicted benefit from keeping it around */
+/* choose victims based on what's required */
static
-int chooseVictims(Client cntxt, int *leaves, int ltop, lng wr)
+int chooseVictims(Client cntxt, int *leaves, int ltop)
{
- dbl *wben, ben = 0, maxwb, tmp, ci_ben, tot_ben;
- int l, newtop, mpos, tmpl, ci = 0;
- lng sz, totmem = 0, targmem, smem;
+ int i,j,l;
+ lng freed, sz;
+ lng target = (lng) MT_getrss() - (lng) (MEMORY_THRESHOLD *
monet_memory);
- (void) cntxt;
+#ifdef _DEBUG_CACHE_
+ mnstr_printf(cntxt->fdout,"#chooseVictims %d mem "LLFMT, ltop, (lng)
(MEMORY_THRESHOLD * monet_memory));
+ mnstr_printf(cntxt->fdout," RSS "LLFMT, (lng) MT_getrss());
+ mnstr_printf(cntxt->fdout," " LLFMT" srch %5.2f\n",
+ target, ((double)recycleSearchTime)/recycleSearchCalls);
+#endif
- wben = (dbl *)GDKzalloc(sizeof(dbl)*ltop);
- for (l = 0; l < ltop; l++){
- sz = recycleBlk->profiler[leaves[l]].wbytes;
- ben = recycleProfit2(leaves[l]);
- wben[l] = sz? ben / sz : -1;
-#ifdef _DEBUG_CACHE_
- mnstr_printf(cntxt->fdout,"#leaf[%d], wr "LLFMT" size "LLFMT"
benefit %6.2f (%6.2f) wben %6.2f\n" ,l, wr, sz, (float)ben, recycleProfit2(l),
(float)wben[l]);
-#endif
- totmem += sz;
- }
- if (totmem <= wr) { /* all leaves need to be dropped */
- GDKfree(wben);
-#ifdef _DEBUG_CACHE_
- mnstr_printf(cntxt->fdout,"#drop all leaves\n");
-#endif
- return ltop;
- }
-
- /* reorder instructions on increasing weighted credit */
- /* knapsack: find a set with biggest wben fitting in totmem-wr.
- They are most benefitial and can be saved from dropping */
-
- targmem = totmem - wr; /*sack volume */
- smem = 0;
- tot_ben = 0;
- for(newtop = ltop; newtop>0; newtop--){
- maxwb = 0; mpos = newtop-1; /* find most benefitial
item (weighted ben.)*/
- for(l = 0; l<newtop; l++){
- if ((lng) recycleBlk->profiler[leaves[l]].wbytes >
targmem - smem)
- wben[l] = -1;
- if (maxwb < wben[l]){
- maxwb = wben[l];
- mpos = l;
+ if ( target > 0 ){
+ /* reduce the memory footprint */
+ for( i=0; i < ltop; i++)
+ for( j= i+1; j<ltop; j++)
+ if ( recycleBlk->profiler[leaves[j]].wbytes >
recycleBlk->profiler[leaves[i]].wbytes){
+ l = leaves[i];
+ leaves[i] = leaves[j];
+ leaves[j] = l;
+ }
+ } else {
+ /* free up some entries using LRU on leaves */
+ for( i=0; i < ltop; i++){
+ for( j= i+1; j<ltop; j++){
+ if (recycleBlk->profiler[leaves[j]].clk <
recycleBlk->profiler[leaves[i]].clk){
+ l = leaves[i];
+ leaves[i] = leaves[j];
+ leaves[j] = l;
+ }
}
}
- if ( maxwb ){ /* add it to the sack
(newtop - ltop)*/
- smem += recycleBlk->profiler[leaves[mpos]].wbytes;
- tmpl = leaves[mpos];
- leaves[mpos] = leaves[newtop-1];
- leaves[newtop-1] = tmpl;
- tmp = wben[mpos];
- wben[mpos] = wben[newtop-1];
- wben[newtop-1] = tmp;
- tot_ben += recycleProfit2(tmpl);
- }
- else break;
}
- /* compare benefits of knap-sack content and the critical item */
- ci_ben = 0; /* find the critical item */
- for (l = 0; l < ltop; l++) {
- ben = recycleProfit2(leaves[l]);
- if (recycleBlk->profiler[leaves[l]].wbytes <= targmem &&
- ben > ci_ben){
- ci = l;
- ci_ben = ben;
+ /* throw out all instructions until you fit */
+ freed =0;
+ if ( target > 0) {
+ for(i=0; i< ltop; i++)
+ if( ( sz = recycleBlk->profiler[leaves[i]].wbytes)){
+ freed += sz;
+#ifdef _DEBUG_CACHE_
+ mnstr_printf(cntxt->fdout,"#leaf[%d], size
"LLFMT" benefit %6.2f\n" ,leaves[i], sz, recycleProfit2(leaves[i]));
+#endif
+ if ( freed > target){
+ i++;
+ break;
+ }
+ } else break;
+ } else
+ i=1; /* at least one instruction removed */
+#ifdef _DEBUG_CACHE_
+ mnstr_printf(cntxt->fdout,"#TO be evicted based on space %d\n"
,i);
+#endif
+
+ /* throw out all cheap instructions as well */
+ for(l = i ; l< ltop; l++){
+ if ( recycleBlk->profiler[leaves[l]].ticks <
recycleSearchTime/recycleSearchCalls){
+ leaves[i++] = leaves[l];
+#ifdef _DEBUG_CACHE_
+ mnstr_printf(cntxt->fdout,"#leaf[%d], cheap benefit
%6.2f\n" ,leaves[l], recycleProfit2(leaves[l]));
+#endif
}
}
-
- if ( ci_ben > tot_ben ) { /* save the critical item instead */
- newtop = ltop - 1;
- tmpl = leaves[ci];
- leaves[ci] = leaves[newtop];
- leaves[newtop] = tmpl;
#ifdef _DEBUG_CACHE_
- mnstr_printf(cntxt->fdout,"#Don't drop critical item :
instruction %d, credit %f\n" ,tmpl,ci_ben);
+ mnstr_printf(cntxt->fdout,"#TO be evicted based on space +cheap
%d\n" ,i);
#endif
- }
- GDKfree(wben);
- return newtop;
-
+
+ return i;
}
@@ -292,20 +282,17 @@ static void RECYCLEcleanCache(Client cnt
InstrPtr p;
InstrPtr *old, *newstmt;
bit *lmask, *dmask;
- int k, *leaves, *vm;
- int limit, idx;
- size_t mem;
- lng wr = recyclerMemoryUsed - (lng) (MEMORY_THRESHOLD * monet_memory);
- dbl minben, ben;
+ int k, *leaves;
+ int limit;
bte *used;
#ifdef _DEBUG_RESET_
//mnstr_printf(cntxt->fdout,"#CACHE BEFORE CLEANUP
%d\n",recycleCacheLimit);
//RECYCLEdumpInternal(cntxt->fdout);
#endif
-newpass:
if ( recycleBlk == 0 || recycleBlk->stop == 0)
return;
+newpass:
if ( recycleBlk->stop < recycleCacheLimit)
return;
@@ -324,25 +311,32 @@ newpass:
for (i = 0; i < recycleBlk->stop; i++){
p = recycleBlk->stmt[i];
for( j = 0; j < p->retc ; j++)
- if (used[getArg(p,j)]) goto skip;
- lmask[i] = 1;
- ltop++;
- skip:;
+ if (used[getArg(p,j)]) break;
+ if ( j == p->retc ){
+ lmask[i] = 1;
+ ltop++;
+ }
}
if (ltop == 0 ){
+#ifdef _DEBUG_RESET_
+ mnstr_printf(cntxt->fdout,"#CACHE NOTHING TO CLEANUP
%d\n",recycleCacheLimit);
+ RECYCLEdumpInternal(cntxt->fdout);
+ assert(0);
+#endif
GDKfree(lmask);
+ GDKfree(used);
return;
}
leaves = (int *)GDKzalloc(sizeof(int)*ltop);
l = 0;
- for (i = 0; i < recycleBlk->stop; i++){
- if (lmask[i]) leaves[l++] = i;
- }
+ for (i = 0; i < recycleBlk->stop; i++)
+ if (lmask[i])
+ leaves[l++] = i;
GDKfree(lmask);
#ifdef _DEBUG_CACHE_
- //mnstr_printf(cntxt->fdout,"#RECYCLEcleanCache: usedmem="LLFMT"\n",
recyclerMemoryUsed);
+ mnstr_printf(cntxt->fdout,"#RECYCLEcleanCache: usedmem="LLFMT"\n",
recyclerMemoryUsed);
//mnstr_printf(cntxt->fdout,"#Candidates for
eviction\n#LRU\tclk\t\tticks\t\twbytes\tCalls\tProfit\n");
//for (l = 0; l < ltop; l++)
//mnstr_printf(cntxt->fdout,"#%3d\t"LLFMT"\t"LLFMT"\t\t
"LLFMT"\t%3d\t%5.1f\n",
@@ -355,55 +349,20 @@ newpass:
#endif
/* find entries to evict */
- mem = recyclerMemoryUsed > (lng) (MEMORY_THRESHOLD * monet_memory) ;
- vm = (int *)GDKzalloc(sizeof(int)*ltop);
- vtop = 0;
-
- if (!mem){ /* evict 1 entry */
- minben = recycleProfit2(leaves[0]);
- idx = 0;
- for (l = 1; l < ltop; l++){
- ben = recycleProfit2(leaves[l]);
- if( ben < minben) {
- minben = ben;
- idx = l;
- }
- }
- vm[vtop++] = leaves[idx];
- } else { /* evict several to get enough memory */
- wr = recyclerMemoryUsed - (lng) (MEMORY_THRESHOLD *
monet_memory);
- k = 0;
- for (l = 0; l < ltop; l++) {
- // also discard leaves that are more expensive to find
then compute
- if( recycleBlk->profiler[leaves[l]].ticks <
recycleSearchTime)
- continue;
- if ( recycleBlk->profiler[leaves[l]].wbytes > 0 )
- leaves[k++] = leaves[l];
- }
- if ( k > 0 )
- ltop = k;
- vtop = chooseVictims(cntxt,leaves, ltop, wr);
- wr=0;
- for (v = 0; v < vtop; v++){
- vm[v] = leaves[v];
- wr += recycleBlk->profiler[leaves[v]].wbytes;
- }
- }
+ vtop = chooseVictims(cntxt,leaves, ltop);
#ifdef _DEBUG_CACHE_
mnstr_printf(cntxt->fdout,"#Evicted %d instruction(s) \n",vtop);
for(v=0; v<vtop;v++){
- mnstr_printf(cntxt->fdout,"#%d\t " LLFMT"
",vm[v],recycleBlk->profiler[vm[v]].ticks);
-
printInstruction(cntxt->fdout,recycleBlk,0,recycleBlk->stmt[vm[v]],
LIST_MAL_ALL);
+ mnstr_printf(cntxt->fdout,"#%d\t " LLFMT"
",leaves[v],recycleBlk->profiler[leaves[v]].ticks);
+
printInstruction(cntxt->fdout,recycleBlk,0,recycleBlk->stmt[leaves[v]],
LIST_MAL_ALL);
}
#endif
- GDKfree(leaves);
/* drop victims in one pass */
dmask = (bit *)GDKzalloc(recycleBlk->stop);
for (v = 0; v < vtop; v++)
- dmask[vm[v]] = 1;
- GDKfree(vm);
+ dmask[leaves[v]] = 1;
(void) newstmt;
old = recycleBlk->stmt;
@@ -412,6 +371,9 @@ newpass:
newstmt = (InstrPtr *) GDKzalloc(sizeof(InstrPtr) * recycleBlk->ssize);
if (newstmt == NULL){
GDKerror("newMalBlk:"MAL_MALLOC_FAIL);
+ GDKfree(leaves);
+ GDKfree(used);
+ GDKfree(dmask);
return;
}
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
http://mail.monetdb.org/mailman/listinfo/checkin-list
