diff options
Diffstat (limited to 'src/engine')
| -rw-r--r-- | src/engine/e_snapshot.c | 78 |
1 files changed, 67 insertions, 11 deletions
diff --git a/src/engine/e_snapshot.c b/src/engine/e_snapshot.c index 112f8fed..d2379217 100644 --- a/src/engine/e_snapshot.c +++ b/src/engine/e_snapshot.c @@ -1,4 +1,5 @@ /* copyright (c) 2007 magnus auvinen, see licence.txt for more info */ +#include <stdlib.h> #include "e_snapshot.h" #include "e_compression.h" #include "e_interface.h" @@ -33,8 +34,47 @@ int snapshot_get_item_index(SNAPSHOT *snap, int key) } return -1; } +typedef struct +{ + int num; + int keys[64]; + int index[64]; +} ITEMLIST; +static ITEMLIST sorted[256]; +static int snapshot_generate_hash(SNAPSHOT *snap) +{ + int i, key, hashid; + for(i = 0; i < 256; i++) + sorted[i].num = 0; + + for(i = 0; i < snap->num_items; i++) + { + key = snapitem_key(snapshot_get_item(snap, i)); + hashid = ((key>>8)&0xf0) | (key&0xf); + if(sorted[hashid].num != 64) + { + sorted[hashid].index[sorted[hashid].num] = i; + sorted[hashid].keys[sorted[hashid].num] = key; + sorted[hashid].num++; + } + } + return 0; +} + +int snapshot_get_item_index_hashed(SNAPSHOT *snap, int key) +{ + int hashid = ((key>>8)&0xf0) | (key&0xf); + int i; + for(i = 0; i < sorted[hashid].num; i++) + { + if(sorted[hashid].keys[i] == key) + return sorted[hashid].index[i]; + } + + return -1; +} typedef struct { @@ -141,6 +181,7 @@ static void undiff_item(int *past, int *diff, int *out, int size) /* TODO: OPT: this should be made much faster */ int snapshot_create_delta(SNAPSHOT *from, SNAPSHOT *to, void *dstdata) { + static PERFORMACE_INFO hash_scope = {"hash", 0}; SNAPSHOT_DELTA *delta = (SNAPSHOT_DELTA *)dstdata; int *data = (int *)delta->data; int i, itemsize, pastindex; @@ -153,6 +194,10 @@ int snapshot_create_delta(SNAPSHOT *from, SNAPSHOT *to, void *dstdata) delta->num_deleted_items = 0; delta->num_update_items = 0; delta->num_temp_items = 0; + + perf_start(&hash_scope); + snapshot_generate_hash(to); + perf_end(); /* pack deleted stuff */ { @@ -162,7 +207,7 @@ int snapshot_create_delta(SNAPSHOT *from, SNAPSHOT *to, void *dstdata) for(i = 0; i < from->num_items; i++) { fromitem = snapshot_get_item(from, i); - if(snapshot_get_item_index(to, (snapitem_key(fromitem))) == -1) + if(snapshot_get_item_index_hashed(to, (snapitem_key(fromitem))) == -1) { /* deleted */ delta->num_deleted_items++; @@ -174,22 +219,35 @@ int snapshot_create_delta(SNAPSHOT *from, SNAPSHOT *to, void *dstdata) perf_end(); } + perf_start(&hash_scope); + snapshot_generate_hash(from); + perf_end(); + /* pack updated stuff */ { static PERFORMACE_INFO scope = {"update", 0}; + int pastindecies[1024]; perf_start(&scope); + + /* fetch previous indices */ + /* we do this as a separate pass because it helps the cache */ + { + static PERFORMACE_INFO scope = {"find", 0}; + perf_start(&scope); + for(i = 0; i < to->num_items; i++) + { + curitem = snapshot_get_item(to, i); /* O(1) .. O(n) */ + pastindecies[i] = snapshot_get_item_index_hashed(from, snapitem_key(curitem)); /* O(n) .. O(n^n)*/ + } + perf_end(); + } for(i = 0; i < to->num_items; i++) { /* do delta */ - { - static PERFORMACE_INFO scope = {"find", 0}; - perf_start(&scope); - itemsize = snapshot_get_item_datasize(to, i); - curitem = snapshot_get_item(to, i); - pastindex = snapshot_get_item_index(from, snapitem_key(curitem)); - perf_end(); - } + itemsize = snapshot_get_item_datasize(to, i); /* O(1) .. O(n) */ + curitem = snapshot_get_item(to, i); /* O(1) .. O(n) */ + pastindex = pastindecies[i]; if(pastindex != -1) { @@ -202,7 +260,6 @@ int snapshot_create_delta(SNAPSHOT *from, SNAPSHOT *to, void *dstdata) *data++ = itemsize; *data++ = snapitem_type(curitem); *data++ = snapitem_id(curitem); - /*data++ = curitem->key();*/ data += itemsize/4; delta->num_update_items++; } @@ -216,7 +273,6 @@ int snapshot_create_delta(SNAPSHOT *from, SNAPSHOT *to, void *dstdata) *data++ = itemsize; *data++ = snapitem_type(curitem); *data++ = snapitem_id(curitem); - /*data++ = curitem->key();*/ mem_copy(data, snapitem_data(curitem), itemsize); size_count += itemsize; |