300 lines
9.6 KiB
C++
300 lines
9.6 KiB
C++
#include "../api/noose.hpp"
|
|
#include "../api/rope.hpp"
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
#include <cstdlib>
|
|
#include <cstring>
|
|
#include <fstream>
|
|
#include <iostream>
|
|
#include <string>
|
|
|
|
char *load_file(const char *path, size_t *out_len) {
|
|
FILE *f = fopen(path, "rb");
|
|
if (!f) {
|
|
perror("fopen");
|
|
return nullptr;
|
|
}
|
|
fseek(f, 0, SEEK_END);
|
|
size_t len = ftell(f);
|
|
rewind(f);
|
|
|
|
char *buf = (char *)malloc(len);
|
|
if (!buf) {
|
|
perror("malloc");
|
|
fclose(f);
|
|
return nullptr;
|
|
}
|
|
|
|
fread(buf, 1, len, f);
|
|
fclose(f);
|
|
|
|
*out_len = len;
|
|
return buf;
|
|
}
|
|
|
|
int main() {
|
|
|
|
printf("My rope implementation benchmark\n");
|
|
|
|
{
|
|
size_t len;
|
|
printf("Loading file into rope...\n");
|
|
char *buf = load_file("./random.bin", &len);
|
|
auto start = std::chrono::high_resolution_clock::now();
|
|
Knot *root = load(buf, len, optimal_chunk_size(len));
|
|
auto end = std::chrono::high_resolution_clock::now();
|
|
printf("Load time: %.3f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
free(buf);
|
|
|
|
// READ TEST
|
|
printf("Testing read...\n");
|
|
start = std::chrono::high_resolution_clock::now();
|
|
char *content = read(root, len / 2, 1024);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
free(content);
|
|
printf("Read 1 KB from middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// INSERT TEST
|
|
printf("Testing insert...\n");
|
|
char insert_data[1024];
|
|
memset(insert_data, 'X', 1024);
|
|
start = std::chrono::high_resolution_clock::now();
|
|
root = insert(root, len / 2, insert_data, 1024);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("Insert 1 KB in middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// ERASE TEST (Delete the same 1 KB we just inserted)
|
|
printf("Testing erase...\n");
|
|
start = std::chrono::high_resolution_clock::now();
|
|
root = erase(root, len / 2, 1024);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("Erase 1 KB in middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// SPLIT TEST
|
|
printf("Testing split...\n");
|
|
Knot *left = nullptr, *right = nullptr;
|
|
start = std::chrono::high_resolution_clock::now();
|
|
split(root, len / 2, &left, &right);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("Split at middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// CONCAT TEST
|
|
printf("Testing concat...\n");
|
|
start = std::chrono::high_resolution_clock::now();
|
|
root = concat(left, right);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("Concat: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// ---------------------------------------------------------
|
|
// LINE OPERATIONS TESTS
|
|
// ---------------------------------------------------------
|
|
printf("Testing line operations...\n");
|
|
|
|
// KNOWN CONSTANTS based on: yes "The quick brown fox jumps over the lazy
|
|
// dog." String length: 44 + 1 newline = 45 bytes per line.
|
|
const uint32_t BYTES_PER_LINE = 45;
|
|
const uint32_t TEST_LINE_INDEX = 1000; // A line deep in the file
|
|
|
|
// 1. Test byte_to_line
|
|
// We pick a byte in the middle of TEST_LINE_INDEX.
|
|
// Offset = (100000 * 45) + 10.
|
|
uint32_t test_offset = (TEST_LINE_INDEX * BYTES_PER_LINE) + 10;
|
|
|
|
start = std::chrono::high_resolution_clock::now();
|
|
uint16_t calculated_line = byte_to_line(root, test_offset);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
|
|
printf("byte_to_line (%u -> %u): %.6f s ", test_offset, calculated_line,
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
if (calculated_line == TEST_LINE_INDEX) {
|
|
printf("[PASS]\n");
|
|
} else {
|
|
printf("[FAIL] Expected %u, got %u\n", TEST_LINE_INDEX, calculated_line);
|
|
}
|
|
|
|
// 2. Test line_to_byte
|
|
// We ask for the start of TEST_LINE_INDEX. Should be exactly
|
|
// TEST_LINE_INDEX * 45.
|
|
uint32_t out_len = 0;
|
|
uint32_t expected_start = TEST_LINE_INDEX * BYTES_PER_LINE;
|
|
|
|
start = std::chrono::high_resolution_clock::now();
|
|
uint32_t calculated_start = line_to_byte(root, TEST_LINE_INDEX, &out_len);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
|
|
printf("line_to_byte (Line %u -> Offset %u): %.6f s ", TEST_LINE_INDEX,
|
|
calculated_start,
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
if (calculated_start == expected_start && out_len == BYTES_PER_LINE) {
|
|
printf("[PASS]\n");
|
|
} else {
|
|
printf("[FAIL] Expected offset %u (len %u), got %u (len %u)\n",
|
|
expected_start, BYTES_PER_LINE, calculated_start, out_len);
|
|
}
|
|
|
|
// ---------------------------------------------------------
|
|
// ITERATOR SPEED TEST
|
|
// ---------------------------------------------------------
|
|
printf("Testing iterator speed...\n");
|
|
|
|
const uint32_t LINES_TO_ITERATE = 10000; // Iterate 10,000 lines
|
|
|
|
// 1. Initialize the iterator at a deep line index
|
|
uint32_t start_line = TEST_LINE_INDEX + 10;
|
|
|
|
LeafIterator *it = begin_k_iter(root);
|
|
if (!it) {
|
|
printf("Iterator Test: [FAIL] begin_iterator returned NULL.\n");
|
|
} else {
|
|
char *line = NULL;
|
|
uint32_t lines_read = 0;
|
|
|
|
start = std::chrono::high_resolution_clock::now();
|
|
|
|
// 2. Iterate and time the process
|
|
// We use the clean C idiom: get the line, check for NULL, then
|
|
// process.
|
|
while (lines_read < LINES_TO_ITERATE && (line = next_leaf(it)) != NULL) {
|
|
// Note: We deliberately skip printing to focus on the Rope operation
|
|
// time.
|
|
lines_read++;
|
|
}
|
|
|
|
end = std::chrono::high_resolution_clock::now();
|
|
|
|
double elapsed_time = std::chrono::duration<double>(end - start).count();
|
|
|
|
printf("Iterator speed (f:: %u): %.6f s (%.2f lines/s)\n", lines_read,
|
|
elapsed_time, (double)lines_read / elapsed_time);
|
|
|
|
if (lines_read == LINES_TO_ITERATE) {
|
|
printf("Iterator Test: [PASS] Successfully iterated %u lines.\n",
|
|
LINES_TO_ITERATE);
|
|
} else {
|
|
printf("Iterator Test: [FAIL] Expected %u lines, read %u.\n",
|
|
LINES_TO_ITERATE, lines_read);
|
|
}
|
|
|
|
// 3. Clean up the iterator
|
|
free(it);
|
|
}
|
|
|
|
// search test
|
|
|
|
start = std::chrono::high_resolution_clock::now();
|
|
std::vector<std::pair<size_t, size_t>> matches =
|
|
search_rope(root, "[A-Z][a-z]+");
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("Search Time: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
printf("Found %lu matches\n", matches.size());
|
|
|
|
// char *c = read(root, 0, 1000);
|
|
// printf("%s\n", c);
|
|
// free(c);
|
|
|
|
// ByteIterator *it1 = begin_b_iter(root);
|
|
// char ch;
|
|
// while ((ch = next_byte(it1)) != '\0') {
|
|
// printf("%c:", ch);
|
|
// }
|
|
|
|
ByteIterator *it2 = begin_b_iter(root);
|
|
uint32_t saved[40];
|
|
for (int i = 0; i < 40; i++)
|
|
saved[i] = 0;
|
|
std::string pattern = "[A-Z][a-z]+";
|
|
Inst *program = compile_regex(pattern);
|
|
print_program(program);
|
|
bool result;
|
|
int prolen = proglen(program);
|
|
ThreadList *clist = (ThreadList *)malloc(sizeof(ThreadList));
|
|
clist->t = (Thread *)malloc(+sizeof(Thread) * prolen);
|
|
clist->n = 0;
|
|
ThreadList *nlist = (ThreadList *)malloc(sizeof(ThreadList));
|
|
nlist->t = (Thread *)malloc(+sizeof(Thread) * prolen);
|
|
nlist->n = 0;
|
|
int count = 0;
|
|
start = std::chrono::high_resolution_clock::now();
|
|
while ((result = next_match(program, it2, saved, clist, nlist))) {
|
|
count++;
|
|
}
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("Search Time: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
printf("Found2 %d matches\n", count);
|
|
|
|
free_program(program);
|
|
free(it2->it);
|
|
free(it2);
|
|
free(clist->t);
|
|
free(nlist->t);
|
|
free(clist);
|
|
free(nlist);
|
|
|
|
free_rope(root);
|
|
}
|
|
|
|
printf("Testing std::string...\n");
|
|
|
|
{
|
|
std::ifstream file("random.bin", std::ios::binary | std::ios::ate);
|
|
if (!file) {
|
|
perror("ifstream");
|
|
return 1;
|
|
}
|
|
size_t len = file.tellg();
|
|
file.seekg(0);
|
|
std::string data(len, '\0');
|
|
file.read(data.data(), len);
|
|
|
|
std::string s = data;
|
|
|
|
auto start = std::chrono::high_resolution_clock::now();
|
|
// READ: middle 1 KB
|
|
std::string read_chunk = s.substr(len / 2, 1024);
|
|
auto end = std::chrono::high_resolution_clock::now();
|
|
printf("std::string read 1 KB from middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// INSERT: middle 1 KB
|
|
std::string insert_data(1024, 'X');
|
|
start = std::chrono::high_resolution_clock::now();
|
|
s.insert(len / 2, insert_data);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("std::string insert 1 KB in middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// ERASE: middle 1 KB
|
|
start = std::chrono::high_resolution_clock::now();
|
|
s.erase(len / 2, 1024);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("std::string erase 1 KB in middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// SPLIT: middle
|
|
start = std::chrono::high_resolution_clock::now();
|
|
std::string left = s.substr(0, len / 2);
|
|
std::string right = s.substr(len / 2);
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("std::string split at middle: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
|
|
// CONCAT
|
|
start = std::chrono::high_resolution_clock::now();
|
|
s = left + right;
|
|
end = std::chrono::high_resolution_clock::now();
|
|
printf("std::string concat: %.6f s\n",
|
|
std::chrono::duration<double>(end - start).count());
|
|
}
|
|
}
|