From 40cd61ca7d5f9d32931b3a2313aef65e13c950b6 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Thu, 7 Apr 2022 16:38:47 +0200 Subject: More refactoring of cbits.h + minor changes in examples/benchmark. --- benchmarks/misc/sso_bench2.cpp | 35 ++++++++++++++++++------ examples/mapmap.c | 20 ++++++-------- include/stc/cbits.h | 62 ++++++++++++++++++++++-------------------- 3 files changed, 68 insertions(+), 49 deletions(-) diff --git a/benchmarks/misc/sso_bench2.cpp b/benchmarks/misc/sso_bench2.cpp index 91ffe6ca..7d3bf5ca 100644 --- a/benchmarks/misc/sso_bench2.cpp +++ b/benchmarks/misc/sso_bench2.cpp @@ -2,7 +2,7 @@ #include #include #include -#include +//#define STC_USE_SSO 1 #define i_val_str #include @@ -29,8 +29,7 @@ static void sromutrio(uint64_t seed) { } -static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+"; -static const int ARRAY_SIZE = sizeof(CHARS) - 1; +static const char CHARS[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz=+-"; static const int BENCHMARK_SIZE = 10000000; static const int MAX_STRING_LENGTH = 20; @@ -39,7 +38,7 @@ using time_point = std::chrono::high_resolution_clock::time_point; void addRandomString_STD(std::vector& vec, const int length) { std::string s(length, 0); - char* p = s.data(); + char* p = &s[0]; for (int i = 0; i < length; ++i) { p[i] = CHARS[romutrio() & 63]; } @@ -60,10 +59,13 @@ void addRandomString_STC(cstack_str& vec, const int length) { template void benchmark(L& vec, const int length, R addRandomString) { time_point t1 = std::chrono::high_resolution_clock::now(); - - for (int i = 0; i < BENCHMARK_SIZE; i++) { - addRandomString(vec, length); - } + + if (length == 0) + for (int i = 0; i < BENCHMARK_SIZE; i++) + addRandomString(vec, (i*13 & 31) + 1); + else + for (int i = 0; i < BENCHMARK_SIZE; i++) + addRandomString(vec, length); time_point t2 = std::chrono::high_resolution_clock::now(); const auto duration = std::chrono::duration_cast(t2 - t1).count(); @@ -72,6 +74,23 @@ void benchmark(L& vec, const int length, R addRandomString) { int main() { + sromutrio(1234); + std::cerr << "length\ttime\tstd::string\n"; + for (int k = 0; k < 4; k++) { + std::vector vec; vec.reserve(BENCHMARK_SIZE); + benchmark(vec, 0, addRandomString_STD); + std::cout << '\t' << vec[0] << '\n'; + } + + sromutrio(1234); + std::cerr << "\nlength\ttime\tSTC string\n"; + for (int k = 0; k < 4; k++) { + cstack_str vec = cstack_str_with_capacity(BENCHMARK_SIZE); + benchmark(vec, 0, addRandomString_STC); + std::cout << '\t' << cstr_str(&vec.data[0]) << '\n'; + cstack_str_drop(&vec); + } + sromutrio(1234); std::cerr << "length\ttime\tstd::string\n"; for (int length = 1; length <= MAX_STRING_LENGTH; length++) { diff --git a/examples/mapmap.c b/examples/mapmap.c index b3360d1e..2d681d23 100644 --- a/examples/mapmap.c +++ b/examples/mapmap.c @@ -24,15 +24,13 @@ void add(Departments* deps, const char* name, const char* email, const char* dep People_emplace_or_assign(people, name, email); } -Stack contains(Departments* map, const char* name) +int contains(Departments* map, const char* name) { - Stack stk = Stack_init(); - const People_value* v; + int count = 0; c_foreach (i, Departments, *map) - if ((v = People_get(&i.ref->second, name))) { - Stack_push(&stk, People_value_clone(*v)); - } - return stk; + if (People_contains(&i.ref->second, name)) + ++count; + return count; } int main(void) @@ -58,10 +56,10 @@ int main(void) printf("%s: %s - %s\n", i.ref->first.str, _.name.str, _.email.str); puts(""); - c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Nick Denton"))); - c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Patrick Dust"))); - c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Dennis Kay"))); - c_auto (Stack, s) printf("found: %" PRIuMAX "\n", Stack_size(s = contains(&map, "Serena Bath"))); + printf("found: %d\n", contains(&map, "Nick Denton")); + printf("found: %d\n", contains(&map, "Patrick Dust")); + printf("found: %d\n", contains(&map, "Dennis Kay")); + printf("found: %d\n", contains(&map, "Serena Bath")); puts("Done"); } } diff --git a/include/stc/cbits.h b/include/stc/cbits.h index 347261d8..8d030e25 100644 --- a/include/stc/cbits.h +++ b/include/stc/cbits.h @@ -78,6 +78,8 @@ STC_INLINE void cbits_drop(cbits* self) { c_free(self->data64); } STC_INLINE size_t cbits_size(cbits set) { return set.size; } #define _cbits_bit(i) ((uint64_t)1 << ((i) & 63)) +#define _cbits_words(n) (((n) + 63) >> 6) +#define _cbits_bytes(n) (_cbits_words(n) * sizeof(uint64_t)) #define cbits_new(literal) \ cbits_from_n(literal, c_strlen_lit(literal)) @@ -92,60 +94,60 @@ STC_INLINE cbits cbits_move(cbits* self) { return tmp; } -STC_INLINE bool cbits_test(cbits set, size_t i) { +STC_INLINE bool cbits_test(cbits set, const size_t i) { return (set.data64[i >> 6] & _cbits_bit(i)) != 0; } -STC_INLINE bool cbits_at(cbits set, size_t i) { +STC_INLINE bool cbits_at(cbits set, const size_t i) { return (set.data64[i >> 6] & _cbits_bit(i)) != 0; } -STC_INLINE void cbits_set(cbits *self, size_t i) { +STC_INLINE void cbits_set(cbits *self, const size_t i) { self->data64[i >> 6] |= _cbits_bit(i); } -STC_INLINE void cbits_reset(cbits *self, size_t i) { +STC_INLINE void cbits_reset(cbits *self, const size_t i) { self->data64[i >> 6] &= ~_cbits_bit(i); } -STC_INLINE void cbits_set_value(cbits *self, size_t i, bool value) { +STC_INLINE void cbits_set_value(cbits *self, const size_t i, const bool value) { self->data64[i >> 6] ^= ((uint64_t)-(int)value ^ self->data64[i >> 6]) & _cbits_bit(i); } -STC_INLINE void cbits_flip(cbits *self, size_t i) { +STC_INLINE void cbits_flip(cbits *self, const size_t i) { self->data64[i >> 6] ^= _cbits_bit(i); } -STC_INLINE void cbits_set_all(cbits *self, bool value) { - memset(self->data64, -(int)value, ((self->size + 63) >> 6) * 8); +STC_INLINE void cbits_set_all(cbits *self, const bool value) { + memset(self->data64, -(int)value, _cbits_bytes(self->size)); } -STC_INLINE void cbits_set_values(cbits *self, uint64_t pattern) { - size_t n = (self->size + 63) >> 6; +STC_INLINE void cbits_set_values(cbits *self, const uint64_t pattern) { + size_t n = _cbits_words(self->size); for (size_t i=0; idata64[i] = pattern; } STC_INLINE void cbits_flip_all(cbits *self) { - size_t n = (self->size + 63) >> 6; + size_t n = _cbits_words(self->size); for (size_t i=0; idata64[i] ^= ~(uint64_t)0; } /* Intersection */ STC_INLINE void cbits_intersect(cbits *self, cbits other) { assert(self->size == other.size); - size_t n = (self->size + 63) >> 6; + size_t n = _cbits_words(self->size); for (size_t i=0; idata64[i] &= other.data64[i]; } /* Union */ STC_INLINE void cbits_union(cbits *self, cbits other) { assert(self->size == other.size); - size_t n = (self->size + 63) >> 6; + size_t n = _cbits_words(self->size); for (size_t i=0; idata64[i] |= other.data64[i]; } /* Exclusive disjunction */ STC_INLINE void cbits_xor(cbits *self, cbits other) { assert(self->size == other.size); - size_t n = (self->size + 63) >> 6; + size_t n = _cbits_words(self->size); for (size_t i=0; idata64[i] ^= other.data64[i]; } @@ -168,12 +170,12 @@ STC_INLINE void cbits_xor(cbits *self, cbits other) { STC_DEF cbits* cbits_copy(cbits* self, cbits other) { if (self->data64 == other.data64) return self; if (self->size != other.size) return cbits_take(self, cbits_clone(other)); - memcpy(self->data64, other.data64, ((other.size + 63) >> 6) * 8); + memcpy(self->data64, other.data64, _cbits_bytes(other.size)); return self; } -STC_DEF void cbits_resize(cbits* self, size_t size, bool value) { - size_t new_n = (size + 63) >> 6, osize = self->size, old_n = (osize + 63) >> 6; +STC_DEF void cbits_resize(cbits* self, const size_t size, const bool value) { + const size_t new_n = _cbits_words(size), osize = self->size, old_n = _cbits_words(osize); self->data64 = (uint64_t *) c_realloc(self->data64, new_n * 8); self->size = size; if (new_n >= old_n) { @@ -185,17 +187,17 @@ STC_DEF void cbits_resize(cbits* self, size_t size, bool value) { } } -STC_DEF cbits cbits_with_size(size_t size, bool value) { - cbits set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size}; +STC_DEF cbits cbits_with_size(const size_t size, const bool value) { + cbits set = {(uint64_t *) c_malloc(_cbits_bytes(size)), size}; cbits_set_all(&set, value); return set; } -STC_DEF cbits cbits_with_values(size_t size, uint64_t pattern) { - cbits set = {(uint64_t *) c_malloc(((size + 63) >> 6) * 8), size}; +STC_DEF cbits cbits_with_values(const size_t size, const uint64_t pattern) { + cbits set = {(uint64_t *) c_malloc(_cbits_bytes(size)), size}; cbits_set_values(&set, pattern); return set; } -STC_DEF cbits cbits_from_n(const char* str, size_t n) { +STC_DEF cbits cbits_from_n(const char* str, const size_t n) { cbits set = cbits_with_size(n, false); for (size_t i=0; i> 6) * 8; + const size_t bytes = _cbits_bytes(other.size); cbits set = {(uint64_t *) memcpy(c_malloc(bytes), other.data64, bytes), other.size}; return set; } @@ -221,18 +223,18 @@ STC_DEF size_t cbits_count(cbits s) { return count; } -#define _cbits_SETOP(OPR, x) \ +#define _cbits_OPR(OPR, VAL) \ assert(s.size == other.size); \ - size_t n = s.size >> 6; \ + const size_t n = s.size >> 6; \ for (size_t i = 0; i < n; ++i) \ - if ((s.data64[i] OPR other.data64[i]) != x) \ + if ((s.data64[i] OPR other.data64[i]) != VAL) \ return false; \ if (!(s.size & 63)) return true; \ - uint64_t i = n, m = _cbits_bit(s.size) - 1; \ - return ((s.data64[i] OPR other.data64[i]) & m) == (x & m) + const uint64_t i = n, m = _cbits_bit(s.size) - 1; \ + return ((s.data64[i] OPR other.data64[i]) & m) == (VAL & m) -STC_DEF bool cbits_subset_of(cbits s, cbits other) { _cbits_SETOP(|, s.data64[i]); } -STC_DEF bool cbits_disjoint(cbits s, cbits other) { _cbits_SETOP(&, 0); } +STC_DEF bool cbits_subset_of(cbits s, cbits other) { _cbits_OPR(|, s.data64[i]); } +STC_DEF bool cbits_disjoint(cbits s, cbits other) { _cbits_OPR(&, 0); } #endif #endif -- cgit v1.2.3