416 lines
11 KiB
C
416 lines
11 KiB
C
#include <time.h>
|
|
#include <stdio.h>
|
|
#include <stdint.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include <vessel/hmap.h>
|
|
|
|
#ifndef KEY_COUNT
|
|
# define KEY_COUNT ((1 << 20) + 1)
|
|
/* # define KEY_COUNT 1024 */
|
|
#endif
|
|
|
|
#ifndef KEY_SIZE
|
|
# define KEY_SIZE (1 << 8)
|
|
/* # define KEY_SIZE 16 */
|
|
#endif
|
|
|
|
#ifndef REHASH_PASSES
|
|
# define REHASH_PASSES 8 /* ~1.6 gb of RAM */
|
|
/* # define REHASH_PASSES 2 */
|
|
#endif
|
|
|
|
/* #define PRINTABLE */
|
|
|
|
static unsigned char charset[255] = { 0 };
|
|
|
|
static void grand(char *key, const uint64_t length) {
|
|
for (uint64_t idx = 0; idx < length - 1; ++idx)
|
|
key[idx] = (char)charset[(unsigned)rand() % (sizeof(charset) - 1)];
|
|
|
|
key[length - 1] = '\0';
|
|
}
|
|
|
|
typedef struct {
|
|
char key[KEY_SIZE];
|
|
char value[KEY_SIZE];
|
|
vs_HMapID hid;
|
|
} Kv;
|
|
|
|
int main(void) {
|
|
Kv *kv = calloc(KEY_COUNT, sizeof(*kv));
|
|
|
|
const uint64_t kv_size = sizeof(*kv) * KEY_COUNT;
|
|
const double kv_size_gb = (double)kv_size / (double)(1024 * 1024 * 1024);
|
|
|
|
if (kv) {
|
|
printf("Allocated %zu bytes (%lf GB)\n", kv_size, kv_size_gb);
|
|
} else {
|
|
fprintf(stderr, "Failed to allocate %zu bytes (%lf GB)\n", kv_size, kv_size_gb);
|
|
return 1;
|
|
}
|
|
|
|
puts("Initializing charset ...");
|
|
|
|
for (uint8_t idx = 0; idx < sizeof(charset); ++idx) {
|
|
#ifdef PRINTABLE
|
|
charset[idx] = (unsigned char)((idx % 95) + 32);
|
|
#else
|
|
charset[idx] = (unsigned char)(idx + 1);
|
|
#endif
|
|
printf("%02x ", charset[idx]);
|
|
}
|
|
|
|
putchar('\n');
|
|
|
|
puts("Testing...");
|
|
|
|
vs_HMap hmap = { 0 };
|
|
|
|
if (!vs_HMap_init(&hmap)) {
|
|
fputs("Failed to initialize the HMap\n", stderr);
|
|
free(kv);
|
|
return 1;
|
|
}
|
|
|
|
/* Insert + duplication */
|
|
for (uint8_t v = 1; v <= 2; ++v) {
|
|
printf("Testing insert (%u/2)...\n", v);
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
if (v == 1) {
|
|
/* Only generate keys on first run */
|
|
grand(kv[idx].key, KEY_SIZE);
|
|
}
|
|
grand(kv[idx].value, KEY_SIZE);
|
|
|
|
kv[idx].hid = vs_HMap_insert(&hmap, kv[idx].key, kv[idx].value);
|
|
vs_HMapEntry *b = vs_HMap_find(&hmap, kv[idx].key);
|
|
|
|
if (!vs_HMapID_is_valid(kv[idx].hid) || !b || strcmp(b->value, kv[idx].value) != 0) {
|
|
fprintf(
|
|
stderr, "Failed to insert (%u/2): %s => %s\n", v, kv[idx].key, kv[idx].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
/* Find key */
|
|
|
|
b = vs_HMap_find(&hmap, kv[idx].key);
|
|
|
|
if (!b || strcmp(b->value, kv[idx].value) != 0) {
|
|
fprintf(stderr,
|
|
"Failed to find insert (%u/2): %s => %s\n",
|
|
v,
|
|
kv[idx].key,
|
|
kv[idx].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
/* Find key (id) */
|
|
|
|
b = vs_HMap_find_id(&hmap, kv[idx].hid);
|
|
|
|
if (!b || strcmp(b->value, kv[idx].value) != 0) {
|
|
fprintf(stderr,
|
|
"Failed to find insert by ID (%u/2): %s => %s\n",
|
|
v,
|
|
kv[idx].key,
|
|
kv[idx].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
#if 0
|
|
vs_HMap_print_as_str(&hmap);
|
|
#endif
|
|
|
|
puts("Testing find...");
|
|
|
|
vs_HMapEntry *fv = vs_HMap_find_val(&hmap, kv[0].value, NULL);
|
|
|
|
if (!fv || strcmp(fv->value, kv[0].value) != 0) {
|
|
fprintf(stderr, "Failed to check value mapping %s => %s\n", kv[0].key, kv[0].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
vs_HMapEntry *b = vs_HMap_find(&hmap, kv[idx].key);
|
|
|
|
if (!b || strcmp(b->value, kv[idx].value) != 0) {
|
|
fprintf(stderr, "Failed to check (find) %s => %s\n", kv[idx].key, kv[idx].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
b = vs_HMap_findn(&hmap, kv[idx].key, KEY_SIZE - 1);
|
|
|
|
if (!b || strcmp(b->value, kv[idx].value) != 0) {
|
|
fprintf(stderr, "Failed to check (findn) %s => %s\n", kv[idx].key, kv[idx].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
b = vs_HMap_find_id(&hmap, kv[idx].hid);
|
|
|
|
if (!b || strcmp(b->value, kv[idx].value) != 0) {
|
|
fprintf(stderr, "Failed to check (find_id) %s => %s\n", kv[idx].key, kv[idx].value);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
puts("Testing delete...");
|
|
|
|
printf("Size (pre-delete): "
|
|
"%zu"
|
|
", Capacity: "
|
|
"%zu"
|
|
"\n",
|
|
hmap.size,
|
|
hmap._cap);
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
if (!vs_HMap_delete(&hmap, kv[idx].key)) {
|
|
fprintf(stderr, "Failed to delete %s\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
if (vs_HMap_find(&hmap, kv[idx].key) != NULL) {
|
|
fprintf(stderr, "Failed to delete %s (found)\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
if (vs_HMap_find_id(&hmap, kv[idx].hid) != NULL) {
|
|
fprintf(stderr, "Failed to delete %s (found id)\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
if (vs_HMap_find(&hmap, kv[idx].key)) {
|
|
fprintf(stderr, "Failed to check deletion of %s\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
if (vs_HMap_find_id(&hmap, kv[idx].hid)) {
|
|
fprintf(stderr, "Failed to check ID deletion of %s\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
puts("Testing delete by ID...");
|
|
|
|
puts("Reinserting all elements...");
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
kv[idx].hid = vs_HMap_insert(&hmap, kv[idx].key, kv[idx].value);
|
|
|
|
if (!vs_HMapID_is_valid(kv[idx].hid)) {
|
|
fprintf(stderr, "Failed to insert %s => %s\n", kv[idx].key, kv[idx].value);
|
|
}
|
|
}
|
|
|
|
printf("Size (pre-delete by id): "
|
|
"%zu"
|
|
", Capacity: "
|
|
"%zu"
|
|
"\n",
|
|
hmap.size,
|
|
hmap._cap);
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
if (!vs_HMap_delete_id(&hmap, kv[idx].hid)) {
|
|
fprintf(stderr, "Failed to delete by ID %s\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
if (vs_HMap_find(&hmap, kv[idx].key) != NULL) {
|
|
fprintf(stderr, "Failed to delete %s (found)\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
if (vs_HMap_find_id(&hmap, kv[idx].hid) != NULL) {
|
|
fprintf(stderr, "Failed to delete %s (found id)\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
if (vs_HMap_find(&hmap, kv[idx].key)) {
|
|
fprintf(stderr, "Failed to check deletion of %s\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
if (vs_HMap_find_id(&hmap, kv[idx].hid)) {
|
|
fprintf(stderr, "Failed to check ID deletion of %s\n", kv[idx].key);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
}
|
|
|
|
printf("Size (pre-rehash): "
|
|
"%zu"
|
|
", Capacity: "
|
|
"%zu"
|
|
"\n",
|
|
hmap.size,
|
|
hmap._cap);
|
|
|
|
uint64_t cap = hmap._cap;
|
|
|
|
puts("Testing rehash...");
|
|
|
|
if (!vs_HMap_rehash(&hmap, 1)) {
|
|
fputs("Failed to rehash\n", stderr);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
printf("Size: "
|
|
"%zu"
|
|
", Capacity: "
|
|
"%zu"
|
|
"\n",
|
|
hmap.size,
|
|
hmap._cap);
|
|
|
|
if (hmap.size != 0 || hmap._cap <= cap) {
|
|
fputs("Rehash failed to modify the HMap\n", stderr);
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
return 1;
|
|
}
|
|
|
|
puts("Functions OK");
|
|
|
|
printf("Benchmarking (%d passes)...\n", KEY_COUNT);
|
|
|
|
clock_t start, end;
|
|
double cpu_time_used;
|
|
|
|
/* Insert */
|
|
|
|
start = clock();
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx)
|
|
vs_HMap_insert(&hmap, kv[idx].key, kv[idx].value);
|
|
|
|
end = clock();
|
|
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
|
|
|
|
printf("Insertion time: ~%f s (~%f s/insertion)\n", cpu_time_used, cpu_time_used / KEY_COUNT);
|
|
|
|
/* Rehash */
|
|
|
|
start = clock();
|
|
|
|
for (uint8_t idx = 0; idx < REHASH_PASSES; ++idx)
|
|
vs_HMap_rehash(&hmap, true);
|
|
|
|
end = clock();
|
|
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
|
|
|
|
printf("Rehashing time (%u passes): ~%f s (~%f s/rehash) [%f GB]\n",
|
|
REHASH_PASSES,
|
|
cpu_time_used,
|
|
cpu_time_used / REHASH_PASSES,
|
|
(double)(sizeof(vs_HMap) + (hmap._cap * sizeof(vs_HMapEntry)) +
|
|
(hmap.size * sizeof(size_t)) + (KEY_SIZE * 2 * KEY_COUNT)) /
|
|
(double)(1024 * 1024 * 1024));
|
|
|
|
/* Find */
|
|
|
|
start = clock();
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx)
|
|
vs_HMap_find(&hmap, kv[idx].key);
|
|
|
|
end = clock();
|
|
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
|
|
|
|
printf("Find time: ~%f s (~%f s/query)\n", cpu_time_used, cpu_time_used / KEY_COUNT);
|
|
|
|
/* Find by ID */
|
|
|
|
start = clock();
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx)
|
|
vs_HMap_find_id(&hmap, kv[idx].hid);
|
|
|
|
end = clock();
|
|
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
|
|
|
|
printf("Find by ID time: ~%f s (~%f s/query)\n", cpu_time_used, cpu_time_used / KEY_COUNT);
|
|
|
|
/* Delete */
|
|
|
|
start = clock();
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx)
|
|
vs_HMap_delete(&hmap, kv[idx].key);
|
|
|
|
end = clock();
|
|
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
|
|
|
|
printf("Deletion time: ~%f s (~%f s/deletion)\n", cpu_time_used, cpu_time_used / KEY_COUNT);
|
|
|
|
/* Delete by ID */
|
|
|
|
puts("Reinserting all elements...");
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx) {
|
|
kv[idx].hid = vs_HMap_insert(&hmap, kv[idx].key, kv[idx].value);
|
|
|
|
if (!vs_HMapID_is_valid(kv[idx].hid)) {
|
|
fprintf(stderr, "Failed to insert %s => %s\n", kv[idx].key, kv[idx].value);
|
|
}
|
|
}
|
|
|
|
start = clock();
|
|
|
|
for (uint64_t idx = 0; idx < KEY_COUNT; ++idx)
|
|
vs_HMap_delete_id(&hmap, kv[idx].hid);
|
|
|
|
end = clock();
|
|
cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
|
|
|
|
printf(
|
|
"Deletion by ID time: ~%f s (~%f s/deletion)\n", cpu_time_used, cpu_time_used / KEY_COUNT);
|
|
|
|
puts("All tests passed :D");
|
|
|
|
free(kv);
|
|
vs_HMap_destroy(&hmap);
|
|
|
|
return 0;
|
|
}
|