Changeset: f35911b4722e for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=f35911b4722e
Modified Files:
monetdb5/modules/mal/Tests/xidlist.stable.out
monetdb5/modules/mal/Tests/xidlist.stable.out.oid32
monetdb5/modules/mal/xid.c
Branch: xid
Log Message:
improved encoding schema to exploit all available bits
diffs (truncated from 482 to 300 lines):
diff --git a/monetdb5/modules/mal/Tests/xidlist.stable.out
b/monetdb5/modules/mal/Tests/xidlist.stable.out
--- a/monetdb5/modules/mal/Tests/xidlist.stable.out
+++ b/monetdb5/modules/mal/Tests/xidlist.stable.out
@@ -314,60 +314,52 @@ r+:0 3
p:5
p:7
p:70
-p:188
s+:[188] 012
p:9999
r-:50 49
-r=:50 2
+r=:50 1
p:48
r-:1003 1000
p:95
p:99
p:96
p:98
-p:97
s-:[97] 0104
p:93
p:91
p:92
-p:1140
s-:[1140] 010004002001000
-p:1250
s+:[1250] 010004002001000
b:9223372036854775807
-r=:0 20
+r=:0 19
b:9
-r=:0 30
+r=:0 29
b:0
r+:0 3
p:5
p:7
p:70
-p:188
s+:[188] 012
p:9999
r-:50 49
-r=:50 2
+r=:50 1
p:48
r-:1003 1000
p:95
p:99
p:96
p:98
-p:97
s-:[97] 0104
p:93
p:91
p:92
-p:1140
s-:[1140] 010004002001000
-p:1250
s+:[1250] 010004002001000
b:9223372036854775807
-r=:0 20
+r=:0 19
b:9
-r=:0 30
-#xid, pc 102 var 139, tail decompress, 74, 180, clk 0 sec 2 usec
+r=:0 29
+#xid, pc 102 var 139, tail decompress, 74, 180, clk 0 sec 1 usec
#---------------------------------#
# h t # name
# void oid # type
diff --git a/monetdb5/modules/mal/Tests/xidlist.stable.out.oid32
b/monetdb5/modules/mal/Tests/xidlist.stable.out.oid32
--- a/monetdb5/modules/mal/Tests/xidlist.stable.out.oid32
+++ b/monetdb5/modules/mal/Tests/xidlist.stable.out.oid32
@@ -308,74 +308,62 @@ end main;
[ 177@0, 9@0 ]
[ 178@0, 9@0 ]
[ 179@0, 9@0 ]
-#xid, 139, tail compress, 180,81, 45.00 % clk 0 sec 4 usec
-column first 82, size 180,
+#xid, 139, tail compress, 180,77, 42.78 % clk 0 sec 9 usec
+column first 78, size 180,
r+:0 3
p:5
p:7
p:70
-p:188
s+:[188] 012
p:9999
r-:50 49
-r=:50 2
+r=:50 1
p:48
r-:1003 1000
p:95
p:99
p:96
p:98
-p:97
s-:[97] 0104
p:93
p:91
p:92
-p:1140
-s-:[1140] 02001000
-p:1110
+s-:[1140] 04002001000
p:1100
-p:1250
-s+:[1250] 02001000
-p:1280
+s+:[1250] 04002001000
p:1290
b:2147483647
-r=:0 20
+r=:0 19
b:9
-r=:0 30
+r=:0 29
b:0
r+:0 3
p:5
p:7
p:70
-p:188
s+:[188] 012
p:9999
r-:50 49
-r=:50 2
+r=:50 1
p:48
r-:1003 1000
p:95
p:99
p:96
p:98
-p:97
s-:[97] 0104
p:93
p:91
p:92
-p:1140
-s-:[1140] 02001000
-p:1110
+s-:[1140] 04002001000
p:1100
-p:1250
-s+:[1250] 02001000
-p:1280
+s+:[1250] 04002001000
p:1290
b:2147483647
-r=:0 20
+r=:0 19
b:9
-r=:0 30
-#xid, pc 102 var 139, tail decompress, 82, 180, clk 0 sec 2 usec
+r=:0 29
+#xid, pc 102 var 139, tail decompress, 78, 180, clk 0 sec 5 usec
#-------------------------#
# h t # name
# void oid # type
diff --git a/monetdb5/modules/mal/xid.c b/monetdb5/modules/mal/xid.c
--- a/monetdb5/modules/mal/xid.c
+++ b/monetdb5/modules/mal/xid.c
@@ -46,11 +46,12 @@
typedef oid xid;
#define SIZEOF_XID SIZEOF_OID
#define XIDFMT OIDFMT
+#define XID_CNT_BITS (8 * SIZEOF_XID)
+#define XID_CNT_MAX (~((xid)0))
#define XID_TAG_BITS 3
#define XID_TAG_MAX ((((xid)1) << XID_TAG_BITS) - 1)
-#define XID_VAL_BITS ((8 * SIZEOF_XID) - XID_TAG_BITS)
+#define XID_VAL_BITS (XID_CNT_BITS - XID_TAG_BITS)
#define XID_VAL_MAX ((((xid)1) << XID_VAL_BITS) - 1)
-#define XID_CNT_MAX (~((xid)0))
typedef union XIDCOLUMN{
struct {
@@ -68,8 +69,9 @@ typedef union XIDCOLUMN{
static str
XIDencode(BUN *rtrn, XIDcolumn col, oid *p, oid *q, oid min, BUN org_size)
{
+ bte active_tag = 0;
oid o;
- xid v, prev = 0, vmin = XID_VAL_MAX, vmax = 0;
+ xid v, prev = 0, vmin = XID_CNT_MAX, vmax = 0;
BUN i=XID_IDX_BASE, scnt=0, max_size = MAX_COMPRESSED_SIZE +
XID_IDX_BASE;
//xid point=0, range=0,set=0;
@@ -84,14 +86,14 @@ XIDencode(BUN *rtrn, XIDcolumn col, oid
assert(o <= XID_VAL_MAX);
v = (xid) o;
col[i].x.val = v;
- col[i].x.tag = XIDPOINT;
+ col[i].x.tag = active_tag = XIDPOINT;
//mnstr_printf(GDKout,"xidpoint " BUNFMT " " XIDFMT "\n",i,v);
for ( ; p<q ; p++) {
o = *(oid*) p;
assert(o <= XID_CNT_MAX);
if (o < min || o - min >= XID_VAL_MAX) {
- switch( col[i].x.tag){
+ switch ( active_tag ) {
case XIDRANGEEQ:
case XIDRANGEINC:
case XIDRANGEDEC:
@@ -100,6 +102,7 @@ XIDencode(BUN *rtrn, XIDcolumn col, oid
case XIDSETINC:
case XIDSETDEC:
if (scnt == 1) { /* simplify decoding */
+ col[i-1].x.tag = XIDPOINT;
col[i].x.tag = XIDPOINT;
col[i].x.val = prev;
scnt =0;
@@ -115,30 +118,31 @@ XIDencode(BUN *rtrn, XIDcolumn col, oid
assert(o <= XID_VAL_MAX);
v = (xid) o;
col[i].x.val = v;
- col[i].x.tag = XIDPOINT;
+ col[i].x.tag = active_tag = XIDPOINT;
continue;
}
o -= min;
assert(o <= XID_VAL_MAX);
v = (xid) o;
- switch ( col[i].x.tag ) {
+ switch ( active_tag ) {
case XIDSETINC:
/* works only for strictly increasing sets (sequences);
* otherwise, we loose order information
*/
if ( v > prev && v <= vmax ) {
- col[i].x.val |= (((xid)1) << ((v -
col[i-1].x.val) - 1));
+ col[i].count |= (((xid)1) << ((v -
col[i-1].x.val) - 1));
scnt++;
prev= v;
//mnstr_printf(GDKout,"xidset " BUNFMT " "
XIDFMT "\n",i,(xid) (v - col[i-1].x.val));
} else {
if (scnt == 1) { /* simplify decoding */
+ col[i-1].x.tag = XIDPOINT;
col[i].x.tag = XIDPOINT;
col[i].x.val = prev;
scnt =0;
}
i++;
- col[i].x.tag = XIDPOINT;
+ col[i].x.tag = active_tag = XIDPOINT;
col[i].x.val = v;
//mnstr_printf(GDKout,"xidpoint " BUNFMT " "
XIDFMT "\n",i,v);
//point++;
@@ -149,31 +153,32 @@ XIDencode(BUN *rtrn, XIDcolumn col, oid
* otherwise, we loose order information
*/
if ( v < prev && v >= vmin ) {
- col[i].x.val |= (((xid)1) << ((col[i-1].x.val -
v) - 1));
+ col[i].count |= (((xid)1) << ((col[i-1].x.val -
v) - 1));
scnt++;
prev= v;
//mnstr_printf(GDKout,"xidset " BUNFMT " "
XIDFMT "\n",i,(xid) (v - col[i-1].x.val));
} else {
if (scnt == 1) { /* simplify decoding */
+ col[i-1].x.tag = XIDPOINT;
col[i].x.tag = XIDPOINT;
col[i].x.val = prev;
scnt =0;
}
i++;
- col[i].x.tag = XIDPOINT;
+ col[i].x.tag = active_tag = XIDPOINT;
col[i].x.val = v;
//mnstr_printf(GDKout,"xidpoint " BUNFMT " "
XIDFMT "\n",i,v);
//point++;
}
break;
case XIDRANGEEQ:
- if ( (xid) col[i-1].x.val == v && col[i].x.val <
XID_VAL_MAX){
- col[i].x.val++;
+ if ( (xid) col[i-1].x.val == v && col[i].count <
XID_CNT_MAX){
+ col[i].count++;
//mnstr_printf(GDKout,"xidrange " BUNFMT " "
XIDFMT " " XIDFMT "\n",i, (xid) col[i-1].x.val, v);
} else {
/* fall back to point if spread to large */
i++;
- col[i].x.tag = XIDPOINT;
+ col[i].x.tag = active_tag = XIDPOINT;
col[i].x.val = v;
//mnstr_printf(GDKout,"xidpoint " BUNFMT " "
XIDFMT "\n",i,v);
//point++;
@@ -186,7 +191,7 @@ XIDencode(BUN *rtrn, XIDcolumn col, oid
} else {
/* fall back to point if spread to large */
i++;
- col[i].x.tag = XIDPOINT;
+ col[i].x.tag = active_tag = XIDPOINT;
col[i].x.val = v;
//mnstr_printf(GDKout,"xidpoint " BUNFMT " "
XIDFMT "\n",i,v);
//point++;
@@ -199,67 +204,67 @@ XIDencode(BUN *rtrn, XIDcolumn col, oid
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
