search

radareorg / sdb

Simple and fast string based key-value database with support for arrays and json
https://www.radare.org/
MIT License
217 stars 62 forks source link

other sdbht improvements #169

Closed ret2libc closed 6 years ago

ret2libc commented 6 years ago

SdbHt with master:

insert time: 0.009232 seconds
find time: 0.070190 seconds, sum = 4738954741
insert time (2 time): 3.497370 seconds
find time (2 time): 24.897873 seconds, sum = 5000114468030

SdbHt with this PR:

insert time: 0.006166 seconds
find time: 0.051466 seconds, sum = 4738954741
insert time (2 time): 0.812717 seconds
find time (2 time): 6.450335 seconds, sum = 5000114468030

dict on master (it wasn't changed in this PR):

insert time: 0.001178 seconds
find time: 0.071153 seconds, sum = 4738954741
insert time (2 time): 1.449738 seconds
find time (2 time): 14.697669 seconds, sum = 5000114468030

As you can see this PR considerably improves the performance compared to previous SdbHt implementation and it makes it faster than dict too (apart from the insert time on small numbers, which of course is faster in dict because it doesn't have growing... but we are talking about 5ms more, with a gain of 0.6 seconds in insert time [0.8 vs 1.4] when the numbers grow and 8 seconds of difference in finding[6.4 vs 14.6])

These tests were done with these two programs:

define SEED 0xdeadbeef

define INSERT_SZ 10000

define FIND_SZ 1000000

define INSERT_SZ2 10000000

define FIND_SZ2 100000000

define MOD_VAL 100000

int main(int argc, char *argv) { SdbHt ht = ht_new_size (1024, NULL, NULL, NULL); ht->cmp = NULL; ht->hashfn = NULL; ht->dupkey = NULL; ht->calcsizeK = NULL; int i;

clock_t start, end;
double cpu_time_used, time_taken;

// few elements
srand(SEED);
start = clock();
for (i = 0; i < INSERT_SZ; ++i) {
    int val = rand() % MOD_VAL;
    ht_insert (ht, (void *)val, (void *)(ut64)val);
}
end = clock();
time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
printf("insert time: %f seconds\n", time_taken);

long long sum = 0;
start = clock();
for (i = 0; i < FIND_SZ; ++i) {
    int val = rand() % MOD_VAL;
    int res = (int)(ut64)ht_find (ht, (void *)val, NULL);
    sum += res;
}
end = clock();
time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
printf("find time: %f seconds, sum = %lld\n", time_taken, sum);
ht_free (ht);

// many elements
ht = ht_new_size (1024, NULL, NULL, NULL);
ht->cmp = NULL;
ht->hashfn = NULL;
ht->dupkey = NULL;
ht->calcsizeK = NULL;
srand(SEED);
start = clock();
for (i = 0; i < INSERT_SZ2; ++i) {
    int val = rand() % MOD_VAL;
    ht_insert (ht, (void *)val, (void *)(ut64)val);
}
end = clock();
time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
printf("insert time (2 time): %f seconds\n", time_taken);

sum = 0;
start = clock();
for (i = 0; i < FIND_SZ2; ++i) {
    int val = rand() % MOD_VAL;
    int res = (int)(ut64)ht_find (ht, (void *)val, NULL);
    sum += res;
}
end = clock();
time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
printf("find time (2 time): %f seconds, sum = %lld\n", time_taken, sum);

ht_free (ht);
return 0;

}

- for dict
```C
#include "minunit.h"
#include <stdlib.h>
#include <sdb.h>
#include <time.h>

#define SEED 0xdeadbeef
#define INSERT_SZ   10000
#define FIND_SZ     1000000

#define INSERT_SZ2  10000000
#define FIND_SZ2    100000000

#define MOD_VAL    100000

int main(int argc, char **argv) {
    dict *ht = dict_new (1024, NULL);
    int i;

    clock_t start, end;
    double cpu_time_used, time_taken;

    // few elements
    srand(SEED);
    start = clock();
    for (i = 0; i < INSERT_SZ; ++i) {
        int val = rand() % MOD_VAL;
        dict_set (ht, val, val, NULL);
    }
    end = clock();
    time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
    printf("insert time: %f seconds\n", time_taken);

    long long sum = 0;
    start = clock();
    for (i = 0; i < FIND_SZ; ++i) {
        int val = rand() % MOD_VAL;
        int res = (int)(ut64)dict_get (ht, val);
        sum += res;
    }
    end = clock();
    time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
    printf("find time: %f seconds, sum = %lld\n", time_taken, sum);
    dict_free (ht);

    // many elements
    ht = dict_new (1024, NULL);
    srand(SEED);
    start = clock();
    for (i = 0; i < INSERT_SZ2; ++i) {
        int val = rand() % MOD_VAL;
        dict_set (ht, val, val, NULL);
    }
    end = clock();
    time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
    printf("insert time (2 time): %f seconds\n", time_taken);

    sum = 0;
    start = clock();
    for (i = 0; i < FIND_SZ2; ++i) {
        int val = rand() % MOD_VAL;
        int res = (int)(ut64)dict_get (ht, val);
        sum += res;
    }
    end = clock();
    time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds 
    printf("find time (2 time): %f seconds, sum = %lld\n", time_taken, sum);

    dict_free (ht);
    return 0;
}
radare commented 6 years ago

Why 3 elements at the beginning?

yeah good performance improvement :) good work

On 18 Oct 2018, at 10:32, Riccardo Schirone notifications@github.com wrote:

SdbHt with master:

insert time: 0.009232 seconds find time: 0.070190 seconds, sum = 4738954741 insert time (2 time): 3.497370 seconds find time (2 time): 24.897873 seconds, sum = 5000114468030 SdbHt with this PR:

insert time: 0.006166 seconds find time: 0.051466 seconds, sum = 4738954741 insert time (2 time): 0.812717 seconds find time (2 time): 6.450335 seconds, sum = 5000114468030 dict on master (it wasn't changed in this PR):

insert time: 0.001178 seconds find time: 0.071153 seconds, sum = 4738954741 insert time (2 time): 1.449738 seconds find time (2 time): 14.697669 seconds, sum = 5000114468030 As you can see this PR considerably improves the performance compared to previous SdbHt implementation and it makes it faster than dict too (apart from the insert time on small numbers, which of course is faster in dict because it doesn't have growing... but we are talking about 5ms more, with a gain of 0.6 seconds in insert time [0.8 vs 1.4] when the numbers grow and 8 seconds of difference in finding[6.4 vs 14.6])

These tests were done with these two programs:

for SdbHt

include "minunit.h"

include

include

include

define SEED 0xdeadbeef

define INSERT_SZ 10000

define FIND_SZ 1000000

define INSERT_SZ2 10000000

define FIND_SZ2 100000000

define MOD_VAL 100000

int main(int argc, char *argv) { // on master this defaults to allocating 1024 elements // on my PR it starts with 3 elements SdbHt ht = ht_new_size (1024, NULL, NULL, NULL); ht->cmp = NULL; ht->hashfn = NULL; ht->dupkey = NULL; ht->calcsizeK = NULL; int i;

clock_t start, end; double cpu_time_used, time_taken;

// few elements srand(SEED); start = clock(); for (i = 0; i < INSERT_SZ; ++i) { int val = rand() % MOD_VAL; ht_insert (ht, (void )val, (void )(ut64)val); } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("insert time: %f seconds\n", time_taken);

long long sum = 0; start = clock(); for (i = 0; i < FIND_SZ; ++i) { int val = rand() % MOD_VAL; int res = (int)(ut64)ht_find (ht, (void *)val, NULL); sum += res; } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("find time: %f seconds, sum = %lld\n", time_taken, sum); ht_free (ht);

// many elements ht = ht_new_size (1024, NULL, NULL, NULL); ht->cmp = NULL; ht->hashfn = NULL; ht->dupkey = NULL; ht->calcsizeK = NULL; srand(SEED); start = clock(); for (i = 0; i < INSERT_SZ2; ++i) { int val = rand() % MOD_VAL; ht_insert (ht, (void )val, (void )(ut64)val); } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("insert time (2 time): %f seconds\n", time_taken);

sum = 0; start = clock(); for (i = 0; i < FIND_SZ2; ++i) { int val = rand() % MOD_VAL; int res = (int)(ut64)ht_find (ht, (void *)val, NULL); sum += res; } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("find time (2 time): %f seconds, sum = %lld\n", time_taken, sum);

ht_free (ht); return 0; } for dict

include "minunit.h"

include

include

include

define SEED 0xdeadbeef

define INSERT_SZ 10000

define FIND_SZ 1000000

define INSERT_SZ2 10000000

define FIND_SZ2 100000000

define MOD_VAL 100000

int main(int argc, char *argv) { // on master this defaults to allocating 1024 elements // on my PR it starts with 3 elements dict ht = dict_new (1024, NULL); int i;

clock_t start, end; double cpu_time_used, time_taken;

// few elements srand(SEED); start = clock(); for (i = 0; i < INSERT_SZ; ++i) { int val = rand() % MOD_VAL; dict_set (ht, val, val, NULL); } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("insert time: %f seconds\n", time_taken);

long long sum = 0; start = clock(); for (i = 0; i < FIND_SZ; ++i) { int val = rand() % MOD_VAL; int res = (int)(ut64)dict_get (ht, val); sum += res; } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("find time: %f seconds, sum = %lld\n", time_taken, sum); dict_free (ht);

// many elements ht = dict_new (1024, NULL); srand(SEED); start = clock(); for (i = 0; i < INSERT_SZ2; ++i) { int val = rand() % MOD_VAL; dict_set (ht, val, val, NULL); } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("insert time (2 time): %f seconds\n", time_taken);

sum = 0; start = clock(); for (i = 0; i < FIND_SZ2; ++i) { int val = rand() % MOD_VAL; int res = (int)(ut64)dict_get (ht, val); sum += res; } end = clock(); time_taken = ((double)end - start)/CLOCKS_PER_SEC; // in seconds printf("find time (2 time): %f seconds, sum = %lld\n", time_taken, sum);

dict_free (ht); return 0; } — You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/radare/sdb/pull/169#issuecomment-430922801, or mute the thread https://github.com/notifications/unsubscribe-auth/AA3-lgZO43JwN7KLG9PcpdvBUOqUhdg0ks5umDyegaJpZM4Xs5co.

ret2libc commented 6 years ago

Why 3 elements at the beginning?

sorry, that's old comment I took from my previous tests, but it's not true anymore... I started all hashtables/dicts with 1024 elements.

ret2libc commented 6 years ago

Ok I've addressed the comments. I've also tested the PR with radare2 master and all tests pass except one related to pf., which is just about sorting and I'll fix it in radare2 when we'll merge this.

radare commented 6 years ago

Looks good to merge

On 26 Oct 2018, at 10:32, Riccardo Schirone notifications@github.com wrote:

Ok I've addressed the comments. I've also tested the PR with radare2 master and all tests pass except one related to pf., which is just about sorting and I'll fix it in radare2 when we'll merge this.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.