roaring bitmap performance test

bitmap.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/sha.h>
#include <roaring/roaring.h>
#include <time.h>

#define EVENT_ID_SIZE 32
#define KEY_SIZE 8
#define SALT_SIZE 16
#define BATCH_SIZE 10

// Function to hash event_id + salt and get the first 8 bytes of SHA256
void generate_key(unsigned char *salt, unsigned char *event_id, unsigned char *key) {
    unsigned char hash[SHA256_DIGEST_LENGTH];
    SHA256_CTX sha256_ctx;

    // Prepare data for SHA256: salt + event_id
    unsigned char data[SALT_SIZE + EVENT_ID_SIZE];
    memcpy(data, salt, SALT_SIZE);
    memcpy(data + SALT_SIZE, event_id, EVENT_ID_SIZE);

    // SHA256
    SHA256_Init(&sha256_ctx);
    SHA256_Update(&sha256_ctx, data, sizeof(data));
    SHA256_Final(hash, &sha256_ctx);

    // Take the first 8 bytes
    memcpy(key, hash, KEY_SIZE);
}

// Function to generate a random 32-byte event ID using OpenSSL
void generate_event_id(unsigned char *event_id) {
    if (RAND_bytes(event_id, EVENT_ID_SIZE) != 1) {
        fprintf(stderr, "Error generating random bytes\n");
        exit(1);  // Handle error appropriately
    }
}

void test_membership(roaring_bitmap_t *bitmap, unsigned char **stored_keys, int stored_key_count) {
    clock_t start_time = clock();
    int total_tests = 0;

    // Take 1 valid and 1 invalid key from the stored keys for testing
    unsigned char test_key[KEY_SIZE];
    for (int i = 0; i < stored_key_count; i++) {
        // Test the valid key (stored key)
        uint64_t valid_key_int = *((uint64_t *)stored_keys[i]);
        roaring_bitmap_contains(bitmap, valid_key_int); // Valid key test

        // Test the invalid key (generate a random event ID)
        unsigned char test_event_id[EVENT_ID_SIZE];
        generate_event_id(test_event_id); // Generate a new invalid event ID
        generate_key(test_event_id, stored_keys[i], test_key); // Generate key for invalid event
        uint64_t invalid_key_int = *((uint64_t *)test_key);
        roaring_bitmap_contains(bitmap, invalid_key_int); // Invalid key test

        total_tests += 2; // We are testing 2 keys for every stored key (valid and invalid)
    }

    clock_t end_time = clock();
    double total_time = (double)(end_time - start_time) / CLOCKS_PER_SEC;

    // Calculate average tests per second
    double tests_per_second = total_tests / total_time;
    printf("Average Membership tests per second: %.2f\n", tests_per_second);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Usage: %s <number_of_event_ids>\n", argv[0]);
        return 1;
    }

    // Number of event IDs to process
    int total_event_ids = atoi(argv[1]);

    // Initialize salt and bitmap
    unsigned char salt[SALT_SIZE];
    for (int i = 0; i < SALT_SIZE; i++) {
        salt[i] = rand() % 256;
    }

    roaring_bitmap_t *bitmap = roaring_bitmap_create();

    // Array to store generated keys
    unsigned char **stored_keys = malloc(total_event_ids * sizeof(unsigned char *));
    int stored_key_count = 0;

    // Insert the event IDs into the bitmap
    for (int i = 0; i < total_event_ids; i++) {
        unsigned char event_id[EVENT_ID_SIZE];
        generate_event_id(event_id);

        unsigned char key[KEY_SIZE];
        generate_key(salt, event_id, key);

        uint64_t key_int = *((uint64_t *)key);
        roaring_bitmap_add(bitmap, key_int);

        // Store the key for future membership testing
        stored_keys[stored_key_count] = malloc(KEY_SIZE);
        memcpy(stored_keys[stored_key_count], key, KEY_SIZE);
        stored_key_count++;

        // Every 10 event IDs, test 1 valid and 1 invalid key
        if (i % BATCH_SIZE == 0 && i > 0) {
            // Remove any membership testing during insertions
        }
    }

    // Test membership after all event IDs have been added
    printf("Testing membership after all event IDs are inserted...\n");
    test_membership(bitmap, stored_keys, stored_key_count);

    // Get the size of the bitmap in KB
    size_t bitmap_size_bytes = roaring_bitmap_size_in_bytes(bitmap);
    double bitmap_size_kb = bitmap_size_bytes / 1024.0;
    printf("Bitmap size: %.2f KB\n", bitmap_size_kb);

    // Free memory
    for (int i = 0; i < stored_key_count; i++) {
        free(stored_keys[i]);
    }
    free(stored_keys);
    roaring_bitmap_free(bitmap);

    return 0;
}