From 5219b7883fc719ae5ba5918a32ccf9010ce5c9ca Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 16 Feb 2021 21:32:45 +0100 Subject: More docs updates. --- README.md | 54 ++++++++++++++++++++++++++++-------------------------- 1 file changed, 28 insertions(+), 26 deletions(-) diff --git a/README.md b/README.md index cf6671ba..b8b4ec95 100644 --- a/README.md +++ b/README.md @@ -34,17 +34,17 @@ Performance ----------- ![Benchmark](benchmarks/pics/benchmark.png) -STC containers performs either about equal or better than the c++ std counterparts. **cmap** *insert* is almost 4x times faster -than *std::unordered_map* in this benchmark, and 2x times faster *erase*! Iteration and destruction is an order of magnitude +STC containers performs either about equal or better than the c++ std counterparts. **cmap** *insert* is almost ***4x*** times faster +than *std::unordered_map* in this benchmark, and ***2x*** times faster than *erase*! Iteration and destruction is an order of magnitude faster. **csmap** has noticable faster lookup than *std::map*'s typical red-black tree implementation. It uses an AA-tree -(Arne Andersson, 1993), which tends to create a flatter structure (more balanced) than red-black trees. +(Arne Andersson, 1993), which tends to create a flatter structure (more balanced) than red-black trees. **cvec** is only slighly slower than *std::vector*. Notes: -- The barchart shows average times from results from three platforms: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. -- Containers uses value types uint64_t and pairs of (uint64_t, uint64_t) for the maps. +- The barchart shows average test times from three platforms: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. +- Containers uses value types `uint64_t` and pairs of `uint64_t`for the maps. - Black bars indicates performance variation between various platforms/compilers. -- Iteration is repeated 4 times over n elements. -- *find* is not executed for *forward_list*, *deque*, and *vector* because c++ std have no native *find*. +- Iterations are repeated 4 times over n elements. +- *find* is not executed for *forward_list*, *deque*, and *vector* because the c++ containers have no native *find*. - **deque** - *insert*: n/3 push_front(), n/3 push_back()+push_front(), n/3 push_back(). - **map and unordered map** - *insert*: n/2 random numbers, n/2 sequential numbers. *erase*: n/2 keys are in the map, n/2 keys are random. @@ -203,24 +203,26 @@ The containers are memory efficent, i.e. they occupy as little memory as practic - **carray**: carray1, carray2 and carray3. Type size: One pointer plus one, two, or three size_t variables to store dimensions. Arrays are allocated as one contiguous block of heap memory. - **csptr**: a shared-pointer uses two pointers, one for the data and one for the reference counter. -FAQ ---- -**Q**: *How come **cmap** is so fast?* +Important notes +--------------- -**A**: It uses open addressing which holds all buckets in one block of memory. It has a separate array for precomputed -hashes/used buckets - one byte per bucket. Further if avoids modulus operations and erases elements without leaving -tombstones. Modern architechtures favors simple code and cached memory access, so linear probing is actually as fast -or faster than the more advanced Robin Hood and Hopscotch hashing schemes, which also requires tombstones. **cmap** -does not rely on wasteful power-of-two array sizes, it actually expands only by 1.5x when required. - -**Q**: Why can **cvec_str_emplace_back()** take `const char *` argument when its value type `cstr` cannot be directly -assigned from a `const char *`? - -**A**: STC containers simulates automatic type convertion found in c++. Most containers can take an optional +For STC containers with dynamic allocated elements e.g. **cstr**, elements are moved into containers, e.g: +```c +cvec_str_push_back(&vec, cstr_from("Hello")); +cvec_str_push_back(&vec, cstr_clone(mycstr)); +cmap_str_insert_or_assign(&vec, cstr_from("Hello"), cstr_clone(mycstr)); +``` +Most templated STC container can simulate automatic type convertion like in c++. You may specify an optional "rawvalue" type as template parameter in the **using_**-declaration, along with back and forth convertion methods -to the container value type. By default, rawvalue is equal to value. Various **emplace()**, **cmap_put()** and -lookup methods accepts the rawvalue type, which is convenient e.g. for strings. - -The use of rawvalues are also useful for map insertions, because values are conditionally inserted - the **emplace()** -method constructs a cstr object from a rawvalue when needed only. The shorthand **using_cvec_str()** declares `cvec_str` -container type with `cstr` value and `const char *` rawvalue, along with convertion methods. +to the container value type. By default, rawvalue is equal to value. Methods like **emplace_back()**, +**emplace_front()**, **emplace()**, **cmap_put()** takes a rawvalue type instead of value. This makes adding +literal strings to containers with **cstr**-elements easy: +```c +cvec_str_emplace_back(&vec, "Hello"); +``` +Rawvalues are also beneficial for map insertions, because key and mapped values are only conditionally inserted. +The **emplace()** and **put()** methods constructs cstr-objects from the rawvalues only when it is needed: +```c +cmap_str_emplace(&map, "Hello", "world"); // no cstr constructed if "Hello" is in the map. +cmap_str_put(&map, "Hello", "world"); // similar, but cstr "world" is always constructed. +``` -- cgit v1.2.3