AdamNiederer / AdamNiederer/faster
Redesign with a better design
- Ngôn ngữ chính
- Rust
- Star
- 1.6k
- Fork
- 52
- Chỉ số merge pull request
- Không có pull request nào được merge trong 30 ngày
Mô tả
The current design of "faster" has several big flaws that should be addressed, including:
1. It makes no effort to use aligned loads and no effort to support aligned Vec, which is detrimental to performance on several architectures
2. It abuses the Iterator interface, since the next() method only iterates the element in the first part that is a multiple of the SIMD width, and then you are supposed to call end() for the final part. This is a wrong use of Iterator since next() is supposed to return all items
3. Zip is very limited since it only supports vectors of the same length, and also cannot zip e.g. u8x16 and u32x4 in a way that results in 4 u8s and 4 u32s at once
4. A "default" element is required just to create SIMD iterators, which is probably not the best design
5. The SIMDIterator interface has a bunch of methods like "vector_pos()", "vector_len()", "scalar_len()", etc. that are inappropriate for a SIMD version of Iterator, since the position/length is not a concept valid for general iterators (only for slice iterators)
6. It has no support for multiple vector sizes
7. The SIMDZipped* traits are redundant, and can be removed by just implementing Packed and Packable for tuples and using the normal SIMD* traits
Here is a better design:
1. Introduce a Partial\ type that represent a partially filled SIMD vector, containing a vector and the number of elements that are valid (and that supports iteration, map(), and_then()
2. Implementing Packed and Packable for tuples and remove the SIMDZipped* traits in favor of just using the normal traits with tuple types
3. Implement Iterator with Item = Partial\ for SIMD iterators, so that the next() interface returns all items properly
4. Implement slice iterators so they return a partial vector to align the iterator, then return full vectors until the final partial vector, and so that aligned loads are used
5. Remove the current SIMDIterator and add a new SIMDIterator that provides a next_n(n: usize) -> Partial\ method that returns a partial SIMD vector filled with exactly n elements or less if the end of the iterator is reached, and a size_hint() in terms of scalars
6. Remove the SIMDArray and UnsafeIterator traits
7. Add helpers that can reduce the SIMD size of an iterator, and that can realign the iterator
8. Add a SIMDExactSizeIterator that specifies that an exact size in terms of scalar is valid for the iterator
9. Use specialization to implement SIMDIterator and SIMDExactSizeIterator for any Iterator>, while still allowing to override the implementation for things like slice operator
10. Provide a SIMDVec that is like Vec but guarantees sufficient alignment for allocations (alternatively, change Vec to always align to SIMD alignment, although this might be undesirable)
11. Support all vector sizes including smaller ones when a bigger size is supported
12. Add a version of simd_iter() that allows to specify the vector size, and add a macro that allows to instantiate a code block for each possible SIMD instruction set for the platform using it and that uses runtime feature detection to dispatch (this would be an alternative to the preferred approach of compiling the binary for each SIMD instruction set, which is better overall but that some people may dislike due to code size issues).
With this design:
1. map(), etc. from Iterator can be used directly on SIMD iterators.
2. zip() can be implemented by first automatically reducing the vector size to the smallest width, and then calling next() on the first iterator (or next_n() when implementing next_n()), and then calling next_n() on the other iterators with the number of elements the first one returned
3. A more sophisticated version of zip() could be provided that finds the most frequent alignment among all iterators, aligns all the other with next_n() and then continues zipping with next_n(WIDTH) on all iterators. It's not clear whether this is much more useful than the simpler version that just follows the first iterator though.
Hướng dẫn đóng góp
Chưa lập chỉ mục được hướng dẫn đóng góp cho kho mã nguồn này
Đánh giá
Issue này chưa được đánh giá.