rotate
highway
rotate | highway | |
---|---|---|
4 | 66 | |
143 | 3,656 | |
- | 2.1% | |
10.0 | 9.8 | |
over 1 year ago | 5 days ago | |
C | C++ | |
GNU General Public License v3.0 or later | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
rotate
-
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)
quadsort/fluxsort/crumsort author here.
For me there's a strong visual component, perhaps most obvious for my work on array rotation algorithms.
https://github.com/scandum/rotate
There's also the ability to notice strange/curious/discordant things, and either connect the dots through trying semi-random things, as well as sudden insights which seem to be partially subconscious.
One of my (many) theories is that I have the ability to use long-term memory in a quasi-similar manner to short-term memory for problem solving. My IQ is in the 120-130 range, I suffer from hypervigilance, so it's generally on the lower end due to lack of sleep.
I'd say there's a strong creative aspect. If I could redo life I might try my hand at music.
-
Is there a more efficient way to write this C program?
This is essentially just a rotation of a subrange of your original array. A variety of different algorithms for this operation can be found here.
-
Building the Perfect Memory Bandwidth Beast
Memory bandwidth is 1000x lower than CPU bandwidth, so as a rule of thumb any algorithm whose work scales linearly in the amount of data being processed will be memory bandwidth bound, and also any algorithm which can't be structured to do a lot of work on one memory region at once before moving onto the next one.
Examples (for large enough inputs that it's relevant) include shuffling, sorting, kmeans clustering, branch and bound sudoku solving, vector addition, dot products, and so on.
Moreover, writing a particular piece of code is often easier if you ignore memory bandwidth as a constraint. The classic example is matrix multiplication -- it can be structured such that even disk bandwidth isn't relevant compared to CPU bandwidth, but doing so is a little fiddly compared to the naive n^2 dot products approach, so writing it yourself usually results in a memory bandwidth bound solution for large matrices.
Similarly, writing two passes over your data rather than doing a mega-loop, the choice to use classic kmeans rather than one of its approximations (when it would be appropriate to do so), or not enforcing sortedness at some reasonable boundary and having to do additional passes over your data. It's easy to write code that hoovers up way more bandwidth than it needs to, and often faster algorithms that come out don't do anything different than access the right data at the right time to reduce that pressure, like a trinity rotation [0].
Caveat: Benchmark everything, especially as you're building intuition. Trying to fix what you think is a memory bandwidth issue can result in pipeline stalls and all sorts of fun things, especially when your server has more faster caches than your dev machine, when data in prod doesn't match your micro benchmark, ....
[0] https://github.com/scandum/rotate
- A collection of array rotation algorithms
highway
-
Llamafile 0.7 Brings AVX-512 Support: 10x Faster Prompt Eval Times for AMD Zen 4
The bf16 dot instruction replaces 6 instructions: https://github.com/google/highway/blob/master/hwy/ops/x86_12...
-
JPEG XL and the Pareto Front
[0] for those interested in Highway.
It's also mentioned in [1], which starts off
> Today we're sharing open source code that can sort arrays of numbers about ten times as fast as the C++ std::sort, and outperforms state of the art architecture-specific algorithms, while being portable across all modern CPU architectures. Below we discuss how we achieved this.
[0] https://github.com/google/highway
[1] https://opensource.googleblog.com/2022/06/Vectorized%20and%2..., which has an associated paper at https://arxiv.org/pdf/2205.05982.pdf.
-
Gemma.cpp: lightweight, standalone C++ inference engine for Gemma models
Thanks so much!
Everyone working on this self-selected into contributing, so I think of it less as my team than ... a team?
Specifically want to call out: Jan Wassenberg (author of https://github.com/google/highway) and I started gemma.cpp as a small project just a few months ago + Phil Culliton, Dan Zheng, and Paul Chang + of course the GDM Gemma team.
-
From slow to SIMD: A Go optimization story
C++ users can enjoy Highway [1].
[1] https://github.com/google/highway/
- GDlog: A GPU-Accelerated Deductive Engine
-
Designing a SIMD Algorithm from Scratch
At that point it is better to have some kind of DSL that should not be in the main language, because it would target a much lower level than a typical program. The best effort I've seen in this scene was Google's Highway [1] (not to be confused with HighwayHash) and I even once attempted to recreate it in Rust, but it is still distanced from my ideal.
[1] https://github.com/google/highway
-
SIMD Everywhere Optimization from ARM Neon to RISC-V Vector Extensions
Interesting, thanks for sharing :)
At the time we open-sourced Highway, the standardization process had already started and there were some discussions.
I'm curious why stdlib is the only path you see to default? Compare the activity level of https://github.com/VcDevel/std-simd vs https://github.com/google/highway. As to open-source usage, after years of std::experimental, I see <200 search hits [1], vs >400 for Highway [2], even after excluding several library users.
But that aside, I'm not convinced standardization is the best path for a SIMD library. We and external users extend Highway on a weekly basis as new use cases arise. What if we deferred those changes to 3-monthly meetings, or had to wait for one meeting per WD, CD, (FCD), DIS, (FDIS) stage before it's standardized? Standardization seems more useful for rarely-changing things.
1: https://sourcegraph.com/search?q=context:global+std::experim...
2: https://sourcegraph.com/search?q=context:global+HWY_NAMESPAC...
-
Permuting Bits with GF2P8AFFINEQB
Thanks for the link. We were previously using GFNI for bit reversal and 8-bit shifts, and I just extended that to our 8-bit BroadcastSignBit (https://github.com/google/highway/pull/1784).
-
Six times faster than C
You could study Google's Highway library [1].
[1] https://github.com/google/highway
-
AMD EPYC 97x4 “Bergamo” CPUs: 128 Zen 4c CPU Cores for Servers, Shipping Now
Runtime feature detection need not be rare nor hard, it's a few dozen lines of boilerplate. You can even write your code just once: see https://github.com/google/highway#examples.
What are some alternatives?
stb - stb single-file public domain libraries for C/C++
xsimd - C++ wrappers for SIMD intrinsics and parallelized, optimized mathematical functions (SSE, AVX, AVX512, NEON, SVE))
quadsort - Quadsort is a branchless stable adaptive mergesort faster than quicksort.
Vc - SIMD Vector Classes for C++
sort-research-rs - Test and benchmark suite for sort implementations.
swup - Versatile and extensible page transition library for server-rendered websites 🎉
mountain-sort - The best algorithm to sort mountains
DirectXMath - DirectXMath is an all inline SIMD C++ linear algebra library for use in games and graphics apps
buddy_alloc - A single header buddy memory allocator for C & C++
riscv-v-spec - Working draft of the proposed RISC-V V vector extension
microui - A tiny immediate-mode UI library
jpeg-xl