diff options
Diffstat (limited to 'doc/Bonus/tuple_vector_readme.md')
| -rw-r--r-- | doc/Bonus/tuple_vector_readme.md | 416 |
1 files changed, 0 insertions, 416 deletions
diff --git a/doc/Bonus/tuple_vector_readme.md b/doc/Bonus/tuple_vector_readme.md deleted file mode 100644 index f406ac5..0000000 --- a/doc/Bonus/tuple_vector_readme.md +++ /dev/null @@ -1,416 +0,0 @@ -## Introduction to tuple_vector - -`tuple_vector` is a data container that is designed to abstract and simplify -the handling of a "structure of arrays" layout of data in memory. In -particular, it mimics the interface of `vector`, including functionality to do -inserts, erases, push_backs, and random-access. It also provides a -`RandomAccessIterator` and corresponding functionality, making it compatible -with most STL (and STL-esque) algorithms such as ranged-for loops, `find_if`, -`remove_if`, or `sort`. - -When used or applied properly, this container can improve performance of -some algorithms through cache-coherent data accesses or allowing for -sensible SIMD programming, while keeping the structure of a single -container, to permit a developer to continue to use existing algorithms in -STL and the like. - -## Review of "Structure of arrays" data layouts - -When trying to improve the performance of some code, it can sometimes be -desirable to transform how some data is stored in memory to be laid out not as -an "array of structures", but as a "structure of arrays". That is, instead of -storing a series of objects as a single contiguous chunk of memory, one or -more data members are instead stored as separate chunks of memory that are -handled and accessed in parallel to each other. - -This can be beneficial in two primary respects: - -1) To improve the cache coherency of the data accesses, e.g. by utilizing more -data that is loaded per cache line loaded from memory, and thereby reducing -the amount of time waiting on memory accesses from off-CPU memory. -This presentation from Mike Acton touches on this, among other things: -https://www.youtube.com/watch?v=rX0ItVEVjHc - -2) To allow the data to be more easily loaded and utilized by SIMD kernels, -by being able to load memory directly into a SIMD register. -This is touched on in this presentation from Andreas Fredriksson for writing -code with SIMD intrinsics: -http://www.gdcvault.com/play/1022249/SIMD-at-Insomniac-Games-How -...and as well in this guide for writing performant ISPC kernels: -https://ispc.github.io/perfguide.html - -## How TupleVecImpl works - -`tuple_vector` inherits from `TupleVecImpl`, which -provides the bulk of the functionality for those data containers. It manages -the memory allocated, marshals data members to each array of memory, generates -the necessary iterators, and so on. - -When a `tuple_vector` is declared, it is alongside a list of types, or "tuple -elements", indicating what data to store in the container, similar to how `tuple` -operates. `TupleVecImpl` uses this list of tuple elements to then inherit from a series of -`TupleVecLeaf` structures, which each have their own pointer to an array of their -corresponding type in memory. When dereferencing the container, either to fetch a -tuple of references or just fetching pointers to the memory, it is these pointers -that are utilized or fetched. - -While each `TupleVecLeaf` contains a pointer to its own block of memory, they -are not individual memory allocations. When `TupleVecImpl` needs to grow its -capacity, it calculates the total size needed for a single allocation, taking -into account the number of objects for the container, the size of each tuple -element's type, and the alignment requirements for each type. Pointers into the -allocation for each tuple element are also determined at the same time, which -are passed to each `TupleVecLeaf`. From there, many of the interactions with -`TupleVecImpl`, to modify or access members of the container, then reference -each `TupleVecLeaf`'s data pointer in series, using parameter packs to repeat -each operation for each parent `TupleVecLeaf`. - -## How tuple_vector's iterator works - -`TupleVecImpl` provides a definition to an iterator type, `TupleVecIter`. -As mentioned above, `TupleVecIter` provides all of the functionality to operate -as a `RandomAccessIterator`. When it is dereferenced, it provides a tuple of -references, similar to `at()` or `operator[]` on `TupleVecImpl`, as opposed to -a reference of some other type. As well, a customization of `move_iterator` for -`TupleVecIter` is provided, which will return a tuple of rvalue-references. - -The way that `TupleVecIter` operates internally is to track an index into the -container, as well as a copy of all of the `TupleVecImpl`'s `TupleVecLeaf` -pointers at the time of the iterator's construction. As a result, modifying the -iterator involves just changing the index, and dereferencing the iterator into -the tuple of references involves dereferencing each pointer with an offset -specified by that index. - -Of the various ways of handling the multitude of references, this tended to -provide the best code-generation. For example, having a tuple of pointers that -are collectively modified with each iterator modification resulted in the compiler -not being able to accurately determine which pointers were relevant to the final -output of some function, creating many redundant operations. Similarly, having -the iterator refer to the source `TupleVecImpl` for the series of pointers -often resulted in extra, unnecessary, data hops to the `TupleVecImpl` to repeatedly -fetch data that was not practically mutable, but theoretically mutable. While this -solution is the heaviest in terms of storage, the resulted assembly tends to be -competitive with traditional structure-of-arrays setups. - -## How to work with tuple_vector, and where to use it - -Put simply, `tuple_vector` can be used as a replacement for `vector`. For example, -instead of declaring a structure and vector as: - -``` -struct Entity -{ - bool active; - float lifetime; - Vec3 position; -} -vector<Entity> entityVec; -``` - -...the `tuple_vector` equivalent of this can be defined as: - -``` -tuple_vector<bool, float, Vec3> entityVec; -``` - -In terms of how `tuple_vector` is modified and accessed, it has a similar -featureset as `vector`, except where `vector` would accept or return a single -value, it instead accepts or returns a tuple of values or unstructured series -of equivalent arguments. - -For example, the following functions can be used to access the data, either by -fetching a tuple of references to a series of specific values, or the data -pointers to the tuple elements: - -``` -tuple<bool&, float&, Vec3&> operator[](size_type) -tuple<bool&, float&, Vec3&> at(size_type) -tuple<bool&, float&, Vec3&> iterator::operator*() -tuple<bool&&, float&&, Vec3&&> move_iterator::operator*() -tuple<bool*, float*, Vec3*> data() - -// extract the Ith tuple element pointer from the tuple_vector -template<size_type I> -T* get<I>() -// e.g. bool* get<0>(), float* get<1>(), and Vec3* get<2>() - -// extract the tuple element pointer of type T from the tuple_vector -// note that this function can only be used if there is one instance -// of type T in the tuple_vector's elements -template<typename T> -T* get<T>() -// e.g. bool* get<bool>(), float* get<float>(), and Vec3* get<Vec3>() -``` - -And `push_back(...)` has the following overloads, accepting either values or tuples as needed. - -``` -tuple<bool&, float&, Vec3&> push_back() -push_back(const bool&, const float&, const Vec3&) -push_back(tuple<const bool&, const float&,const Vec3&>) -push_back(bool&&, float&&, Vec3&&) -push_back(tuple<bool&&, float&&, Vec3&&>) -``` -...and so on, and so forth, for others like the constructor, `insert(...)`, -`emplace(...)`, `emplace_back(...)`, `assign(...)`, and `resize(...)`. - -As well, note that the tuple types that are accepted or returned for -`tuple_vector<Ts...>` have typedefs available in the case of not wanting to use -automatic type deduction: -``` -typedef eastl::tuple<Ts...> value_tuple; -typedef eastl::tuple<Ts&...> reference_tuple; -typedef eastl::tuple<const Ts&...> const_reference_tuple; -typedef eastl::tuple<Ts*...> ptr_tuple; -typedef eastl::tuple<const Ts*...> const_ptr_tuple; -typedef eastl::tuple<Ts&&...> rvalue_tuple; -``` -With this, and the fact that the iterator type satisfies -the `RandomAccessIterator` requirements, it is possible to use `tuple_vector` in -most ways and manners that `vector` was previously used, with few structural -differences. - -However, even if not using it strictly as a replacement for `vector`, it is -still useful as a tool for simplifying management of a traditional structure of -arrays. That is, it is possible to use `tuple_vector` to just perform a single -large memory allocation instead of a series of smaller memory allocations, -by sizing the `tuple_vector` as needed, fetching the necessary pointers with -`data()` or `get<...>()`, and carrying on normally. - -One example where this can be utilized is with ISPC integration. Given the -following ISPC function definition: - - export void simple(uniform float vin[], uniform float vfactors[], uniform float vout[], uniform int size); - -...which generates the following function prototype for C/C++ usage: - - extern void simple(float* vin, float* vfactors, float* vout, int32_t size); - -...this can be utilized with some raw float arrays: -``` -float* vin = new float[NumElements]; -float* vfactors = new float[NumElements]; -float* vout = new float[NumElements]; - -// Initialize input buffer -for (int i = 0; i < NumElements; ++i) -{ - vin[i] = (float)i; - vfactors[i] = (float)i / 2.0f; -} - -// Call simple() function from simple.ispc file -simple(vin, vfactors, vout, NumElements); - -delete vin; -delete vfactors; -delete vout; -``` -or, with `tuple_vector`: - -``` -tuple_vector<float, float, float> simpleData(NumElements); -float* vin = simpleData.get<0>(); -float* vfactors = simpleData.get<1>(); -float* vout = simpleData.get<2>(); - -// Initialize input buffer -for (int i = 0; i < NumElements; ++i) -{ - vin[i] = (float)i; - vfactors[i] = (float)i / 2.0f; -} - -// Call simple() function from simple.ispc file -simple(vin, vfactors, vout, NumElements); -``` - -`simpleData` here only has a single memory allocation during its construction, -instead of the three in the first example, and also automatically releases the -memory when it falls out of scope. - -It is possible to also skip a memory allocation entirely, in some circumstances. -EASTL provides "fixed" counterparts of many data containers which allows for a -data container to have an inlined buffer of memory. For example, -`eastl::vector<typename T>` has the following counterpart: - - eastl::fixed_vector<typename T, size_type nodeCount, bool enableOverflow = true> - -This buffer allows for enough space to hold a `nodeCount` number of `T` objects, -skipping any memory allocation at all, until the requested size becomes -greater than `nodeCount` - assuming `enableOverflow` is True. - -There is a similar counterpart to `eastl::tuple_vector<typename... Ts>` available as well: - - eastl::fixed_tuple_vector<size_type nodeCount, bool enableOverflow, typename... Ts> - -This does the similar legwork in creating an inlined buffer, and all of the -functionality of `tuple_vector` otherwise is supported. Note the slight -difference in declaration, though: `nodeCount` and `enableOverflow` are defined -first, and `enableOverflow` is not a default parameter. This change arises out -of restrictions surrounding variadic templates, in that they must be declared -last, and cannot be mixed with default template parameters. - -Lastly, `eastl::vector` and other EASTL data containers support custom Memory Allocator -types, through their template parameters. For example, `eastl::vector`'s full declaration -is actually: - - eastl::vector<typename T, typename AllocatorType = EASTLAllocatorType> - -However, because such a default template parameter cannot be used with -variadic templates, a separate type for `tuple_vector` is required for such a -definition: - - eastl::tuple_vector_alloc<typename AllocatorType, typename... Ts> - -Note that `tuple_vector` uses EASTLAllocatorType as the allocator. - -## Performance comparisons/discussion - -A small benchmark suite for `tuple_vector` is included when running the -EASTLBenchmarks project. It provides the following output on a Core i7 3770k -(Skylake) at 3.5GHz, with DDR3-1600 memory. - -The `tuple_vector` benchmark cases compare total execution time of similar -algorithms run against `eastl::tuple_vector` and `std::vector`, such as -erasing or inserting elements, iterating through the array to find a specific -element, sum all of the elements together via operator[] access, or just -running `eastl::sort` on the data containers. More information about the -EASTLBenchmarks suite can be found in EASTL/doc/EASTL Benchmarks.html - -Benchmark | STD execution time | EASTL execution time | Ratio ---------- | -------- | ---------- | ----- -`tuple_vector<AutoRefCount>/erase ` | 1.7 ms | 1.7 ms | 1.00 -`tuple_vector<MovableType>/erase ` | 104.6 ms | 106.3 ms | 0.98 -`tuple_vector<MovableType>/reallocate ` | 1.3 ms | 1.7 ms | 0.77 - - | | | -`tuple_vector<uint64>/erase ` | 3.4 ms | 3.5 ms | 0.98 -`tuple_vector<uint64>/insert ` | 3.4 ms | 3.4 ms | 0.99 -`tuple_vector<uint64>/iteration ` | 56.3 us | 81.4 us | 0.69 - -`tuple_vector<uint64>/operator[] ` | 67.4 us | 61.8 us | 1.09 -`tuple_vector<uint64>/push_back ` | 1.3 ms | 818.3 us | 1.53 + -`tuple_vector<uint64>/sort ` | 5.8 ms | 7.3 ms | 0.80 - | | | -`tuple_vector<uint64,Padding>/erase ` | 34.7 ms | 32.9 ms | 1.05 -`tuple_vector<uint64,Padding>/insert ` | 41.0 ms | 32.6 ms | 1.26 -`tuple_vector<uint64,Padding>/iteration ` | 247.1 us | 80.5 us | 3.07 + -`tuple_vector<uint64,Padding>/operator[]` | 695.7 us | 81.1 us | 8.58 + -`tuple_vector<uint64,Padding>/push_back ` | 10.0 ms | 6.0 ms | 1.67 + -`tuple_vector<uint64,Padding>/sort ` | 8.2 ms | 10.1 ms | 0.81 - | | | -`vector<AutoRefCount>/erase ` | 1.3 ms | 1.2 ms | 1.05 -`vector<MovableType>/erase ` | 104.4 ms | 109.4 ms | 0.95 -`vector<MovableType>/reallocate ` | 1.5 ms | 1.5 ms | 0.95 - | | | -`vector<uint64>/erase ` | 4.3 ms | 3.6 ms | 1.20 -`vector<uint64>/insert ` | 4.8 ms | 4.8 ms | 1.01 -`vector<uint64>/iteration ` | 71.5 us | 77.3 us | 0.92 -`vector<uint64>/operator[] ` | 90.7 us | 87.2 us | 1.04 -`vector<uint64>/push_back ` | 1.6 ms | 1.2 ms | 1.38 + -`vector<uint64>/sort ` | 7.7 ms | 8.2 ms | 0.93 - -First off, `tuple_vector<uint64>`'s performance versus `std::vector<uint64>` is -comparable, as expected, as the `tuple_vector`'s management for one type -becomes very similar to just a regular vector. The major notable exception is -the iteration case, which runs `eastl::find_if`. This -performance differences is a consequence of the iterator design, and how -it works with indices, not a direct pointer, so the code generation suffers slightly -in this compute-bound scenario. This is worth noting as a demonstration of a -case where falling back to pointer-based iteration by fetching the `begin` and -`end` pointers of that tuple element may be preferable, instead of using the -iterator constructs. - -The set of `tuple_vector<uint64,Padding>` tests are more interesting. -This is a comparison between a single `std::vector` with a -structure containing a `uint64` and 56 bytes of padding, and a `tuple_vector` with -two elements: one for `uint64` and one for 56 bytes of padding. The erase, -insert, push_back, and sort cases all perform at a similar relative rate as -they did in the `tuple_vector<uint64>` tests - demonstrating that operations -that have to touch all of elements do not have a significant change in -performance. - -However, iteration and operator[] are very different, because -those only access the `uint64` member of both `vector` and `tuple_vector` to run -some operation. The iteration test now runs 3x faster whereas before it ran -0.7x as fast, and operator[] runs 8.5x faster, instead of 1.1x. This -demonstrates some of the utility of `tuple_vector`, in that these algorithms end -up being limited by the CPU's compute capabilities, as opposed to being -limited by how fast they can load memory in from DRAM. - -In a series of other tests, generally speaking, `tuple_vector` tends to perform -on par with manual management of multiple arrays in many algorithms and -operations, often even generating the same code. It should be noted that -significant degrees of inlining and optimization are required to get the most out -of `tuple_vector`. Compared to accessing a series of arrays or vectors, -`tuple_vector` does perform a multitude of extra trivial function calls internally -in order to manage the various elements, or interact with `eastl::tuple` through -its interface, so running in debug configurations can run significantly slower -in some cases, e.g. sometimes running at 0.2x the speed compared to vector. - -## The problem of referencing tuple elements - -This will be experienced shortly after using `tuple_vector` in most capacities, -but it should be noted that the most significant drawback is that there is no -way to **symbolically** reference each tuple element of the `tuple_vector` - much -in the same way as `tuple`. For example, if translating a struct such as... - -``` -struct Entity -{ - float x, y, z; - float lifetime; -}; -``` -...to `tuple_vector`, it will exist as: - -``` -tuple_vector<float, float, float, float> entityVec; -``` - -...and can only be accessed in a manner like `entityVec.get<3>()` to refer to -the `lifetime` member. With existing tools, the only good alternatives are to -encapsulate each float as a separate struct to give it unique typenames... - -``` -struct entityX { float val; }; -struct entityY { float val; }; -struct entityZ { float val; }; -struct entityLifetime { float val; }; - -tuple_vector<entityX, entityY, entityZ, entityLifetime> entityVec; -``` -...and then access each tuple element by typename like -`entityVec.get<entityLifetime>()`; or, creating an enumerated value to replace -the indices... - -``` -enum EntityTypeEnum -{ - entityX = 0, - entityY = 1, - entityZ = 2, - entityLifetime = 3 -}; - -tuple_vector<float, float, float, float> entityVec; -``` - -...and then access each tuple element by the enumerated value: -`entityVec.get<entityLifetime>()`. - -Either way, there is a fairly significant maintenance and readability issue -around this. This is arguably more severe than with `tuple` on its own -because that is generally not intended for structures with long lifetime. - -Ideally, if the language could be mutated to accommodate such a thing, it would -be good to have some combination of typenames and symbolic names in the -declaration, e.g. something like - -``` -tuple_vector<float x, float y, float z, float lifetime> entityVec; -``` -and be able to reference the tuple elements not just by typename or index, but -through their corresponding symbol, like `entityVec.get<lifetime>()`. Or, it may -be interesting if the necessary `get` functions could be even automatically -generated through a reflection system, e.g. `entityVec.get_lifetime()`. -All of this remains a pipe dream for now. |