ref: 2ffda6b58c2e5fc7993066ca323898149e66495f
parent: 11398465c52e4fed4e62451f7ad31290726f6754
author: Ori Bernstein <ori@eigenstate.org>
date: Mon Jan 31 12:21:28 EST 2022
tree: implement optimized upsert The copying and small merges were expensive; this optimized version is better, though it still copies the blocks more than I want.
--- a/blk.c
+++ b/blk.c
@@ -103,8 +103,6 @@
switch(b->type){
default:
- if(flg&GBraw)
- break;
fprint(2, "invalid block @%llx\n", bp);
abort();
break;
@@ -674,9 +672,29 @@
return nil;
if((b = initblk(bp, t)) == nil)
return nil;
-
setmalloctag(b, getcallerpc(&t));
return b;
+}
+
+Blk*
+dupblk(Blk *b)
+{
+ Blk *r;
+
+ if((r = newblk(b->type)) == nil)
+ return nil;
+
+ setflag(r, Bdirty);
+ r->bp.hash = b->bp.hash;
+ r->nval = b->nval;
+ r->valsz = b->valsz;
+ r->nbuf = b->nbuf;
+ r->bufsz = b->bufsz;
+ r->logsz = b->logsz;
+ r->lognxt = b->lognxt;
+ memcpy(r->buf, b->buf, sizeof(r->buf));
+ setmalloctag(b, getcallerpc(&b));
+ return r;
}
void
--- a/dat.h
+++ b/dat.h
@@ -86,7 +86,6 @@
Ktref, /* tag[8] = snapid[] scratch snapshot label */
Ksnap, /* sid[8] => ref[8], tree[52]: snapshot root */
Ksuper, /* qid[8] => Kent: parent dir */
- Kdirty, /* [0] => [0]: mark dirty unmount */
};
enum {
@@ -392,6 +391,10 @@
int ht;
Bptr bp;
vlong gen;
+ Msg flush[16];
+ int nflush;
+ int flushsz;
+ char flushbuf[Bufspc/2];
Dlist dead[Ndead];
};
--- a/fns.h
+++ b/fns.h
@@ -12,6 +12,7 @@
extern char* forceuser;
Blk* newblk(int type);
+Blk* dupblk(Blk*);
Blk* getroot(Tree*, int*);
Blk* getblk(Bptr, int);
Blk* refblk(Blk*);
--- a/tree.c
+++ b/tree.c
@@ -194,8 +194,6 @@
hi = mid-1;
break;
case 0:
- if(same != nil)
- *same = 1;
ri = mid;
hi = mid-1;
break;
@@ -214,7 +212,7 @@
ri = lo-1;
else
*same = 1;
- if(ri >= 0)
+ if(m != nil && ri >= 0)
getmsg(b, ri, m);
return ri;
}
@@ -237,8 +235,6 @@
hi = mid-1;
break;
case 0:
- if(same != nil)
- *same = 1;
ri = mid;
hi = mid-1;
break;
@@ -1112,6 +1108,62 @@
}
}
+static char*
+fastupsert(Tree *t, Blk *b, Msg *msg, int nmsg)
+{
+ int i, c, o, ri, lo, hi, mid, nbuf;
+ Msg cmp;
+ char *p;
+ Blk *r;
+
+ if((r = dupblk(b)) == nil)
+ return Emem;
+
+ nbuf = r->nbuf;
+ for(i = 0; i < nmsg; i++)
+ setmsg(r, &msg[i]);
+
+ for(i = 0; i < nmsg; i++){
+ ri = -1;
+ lo = 0;
+ hi = nbuf+i-1;
+ while(lo <= hi){
+ mid = (hi + lo) / 2;
+ getmsg(r, mid, &cmp);
+ c = keycmp(&msg[i], &cmp);
+ switch(c){
+ case -1:
+ hi = mid-1;
+ break;
+ case 0:
+ ri = mid+1;
+ lo = mid+1;
+ break;
+ case 1:
+ lo = mid+1;
+ break;
+ }
+ }
+ if(ri == -1)
+ ri = hi+1;
+ p = r->data + Pivspc + 2*(nbuf+i);
+ o = GBIT16(p);
+ p = r->data + Pivspc + 2*ri;
+ memmove(p+2, p, 2*(nbuf+i-ri));
+ PBIT16(p, o);
+ }
+ lock(&t->lk);
+ t->bp = r->bp;
+ unlock(&t->lk);
+
+ freeblk(t, b);
+ enqueue(r);
+ putblk(b);
+ putblk(r);
+ return nil;
+}
+
+
char*
btupsert(Tree *t, Msg *msg, int nmsg)
{
@@ -1129,6 +1181,8 @@
Again:
if((b = getroot(t, &height)) == nil)
return Efs;
+ if(b->type == Tpivot && !filledbuf(b, nmsg, sz))
+ return fastupsert(t, b, msg, nmsg);
/*
* The tree can grow in height by 1 when we