From 86fb67419bfb56e72fc7526a001093ad1fba62e3 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 13 Feb 2021 21:38:19 +0100 Subject: Update README.md --- README.md | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-) diff --git a/README.md b/README.md index 70c60e43..0193034e 100644 --- a/README.md +++ b/README.md @@ -32,23 +32,21 @@ Others: Performance ----------- -The chart uses average times from results of three compilers: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. -The black bars indicates performance variation between various platforms/compilers. - ![Benchmark](benchmarks/pics/benchmark.png) -This shows that the STC containers performs either equal or better than the c++ std counterparts. -**cmap** with default hash key is almost 3 times faster than *std::unordered_map* in this test, -on insert and erase, and has orders of magnitude faster iteration and destruction! Additionally, **csmap** is noticable -faster on lookup than *std::map*'s typical red-black tree implementation. *csmap* uses an AA-tree (Arne Andersson, 1993), -which tends to create a flatter structure (more balanced) than red-black trees. Be aware of though, both *csmap* and -*std::map* and are much slower than the unordered map implementations (`n` is half in the benchmarks). +STC containers performs either 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*! It is an order of magnitude faster on iteration and destruction. +**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. Notes: -- Iteration/summing is repeated 4 times. -- Find is not executed for *forward list*, *deque*, and *vector* because they have no native find. -- **deque** - *insert*: 1/3 push_front(), 1/3 push_back()+push_front(), 1/3 push_back(). -- **map and unordered map** - *insert*: 1/2 random numbers, 1/2 sequential numbers. *erase*: 1/2 keys are in the map, 1/2 keys are random. +- The barchart uses average times from results of three compilers: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. +- Container with value types uint64_t, and pairs of (uint64_t, uint64_t) for the maps. +- Black bars indicates performance variation between various platforms/compilers. +- Iteration is repeated 4 times. +- *find* is not executed for *forward list*, *deque*, and *vector* because they 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. Highlights ---------- @@ -204,12 +202,12 @@ The containers are memory efficent, i.e. they occupy as little memory as practic FAQ --- -**Q**: *How did you make **cmap** so fast?* +**Q**: *How can **cmap** be so fast?* **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**: *How come **cvec_str_emplace_back()** can take a `const char *` argument, when its value type `cstr` cannot be directly assigned from a `const char *`*? +**Q**: Why can **cvec_str_emplace_back()** take a `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++. All containers can take 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. +**A**: STC containers simulates automatic type convertion found in c++. Most containers can take 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. -It is also useful for map insertions, because values are only conditionally inserted - the **emplace()** method construct a cstr object from a rawvalue only when needed. **using_cvec_str()** declares `cvec_str` container type with predefined `cstr` value and `const char *` rawvalue, along with convertion methods. +Raw-value is also useful for map insertions, because values are only conditionally inserted - the **emplace()** method construct a cstr object from a rawvalue only when needed. **using_cvec_str()** declares the `cvec_str` container type with predefined `cstr` value and `const char *` rawvalue, along with convertion methods. -- cgit v1.2.3 From c7b1b2b16e31b2d041bc9fb9c29f60cce8db6e59 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 13 Feb 2021 21:49:23 +0100 Subject: Update README.md --- README.md | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) diff --git a/README.md b/README.md index 0193034e..d5b40c3e 100644 --- a/README.md +++ b/README.md @@ -34,17 +34,17 @@ Performance ----------- ![Benchmark](benchmarks/pics/benchmark.png) -STC containers performs either 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*! It is an order of magnitude faster on iteration and destruction. +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. Notes: -- The barchart uses average times from results of three compilers: Win-Clang++ v11, Mingw64 g++ 9.20, VC19. CPU: Ryzen 7 2700X CPU @4Ghz. -- Container with value types uint64_t, and pairs of (uint64_t, uint64_t) for the maps. +- 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. - Black bars indicates performance variation between various platforms/compilers. -- Iteration is repeated 4 times. -- *find* is not executed for *forward list*, *deque*, and *vector* because they have no native find. +- 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*. - **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. @@ -56,7 +56,7 @@ Highlights - **Fully type safe** - Avoids error-prone casting of container types and elements back and forth from the containers. - **Uniform API** - Methods to ***construct***, ***initialize***, ***iterate*** and ***destruct*** have a uniform and intuitive usage across the various containers. - **Small footprint** - Small source code and generated executables. The executable from the above example with six different containers is *26 kb in size* compiled with TinyC. -- **Dual mode compilation** - By default it is a simple header-only library with inline and static methods only, but you can easily switch to create a traditional library with shared symbols, without changing existing source files. See below how-to. +- **Dual mode compilation** - By default it is a simple header-only library with inline and static methods only, but you can easily switch to create a traditional library with shared symbols, without changing existing source files. See next how-to. Usage ----- -- cgit v1.2.3 From bac6c38262e3bf56fa1cb750aa210090b8e6e6c9 Mon Sep 17 00:00:00 2001 From: Tyge Løvset <60263450+tylov@users.noreply.github.com> Date: Sat, 13 Feb 2021 22:05:50 +0100 Subject: Update README.md --- README.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/README.md b/README.md index d5b40c3e..48d73f53 100644 --- a/README.md +++ b/README.md @@ -206,7 +206,7 @@ FAQ **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 a `const char *` argument, when its value type `cstr` cannot be directly assigned from a `const char *`*? +**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 "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. -- cgit v1.2.3