8 ms·
Designing a SIMD Algorithm from Scratch
- gbin 3y agoThis is a pretty good trial for Rust Simd! What were the most surprising quirks of it when you inspected the generated code?
- celeritascelery 3y agoNot OP, but one thing that surprised me was if you are doing rust Simd in a library, and part of the code is marked #[inline] but others are not you might see catastrophic performance regressions. We saw an issue where the SIMD version was over 10x slower because we missed marking one function as inline. Essentially rustc converted it from an intrinsic to a regular function call. https://github.com/rust-lang/rust/issues/107617#issuecomment-1422000166 https://github.com/rust-lang/rust/issues/107617#issuecomment...
- uo21tp5hoyg 3y agoWow I really like that little mini-map on the right...
- joennlae 3y ago+1. Does someone know how to do that?
- progbits 3y agoFirefox only: https://news.ycombinator.com/item?id=36757542 https://news.ycombinator.com/item?id=36757542
- m1el 3y agoThe minimap contains a copy of the content, but with `transform: scale`. The rest is handling `window.onscroll` and mouse events on the overlay.
- Klaster_1 3y agoFound a canvas-based library for this: https://larsjung.de/pagemap/ https://larsjung.de/pagemap/. Definitely not what OP uses, where the minimap is a shrunk copy of the content markup, with all the drawbacks, such as page search finding the same item twice.
- orlp 3y agoThe author should really add at least aria-hidden="true" to the minimap element.
- orf 3y agoInteresting article! Right at the start, the first example of a non-vectorized popcnt implementation is said to produce “comically bad code, frankly”, but in release mode with the native target CPU, it does appear to be vectorising the function fairly ok? https://godbolt.org/z/WE1Eq65jY https://godbolt.org/z/WE1Eq65jY
- saagarjha 3y agoI mean ideally you’d probably want this to be lowered to a popcnt instruction.
- celrod 3y agoYes, just because you see SIMD instructions doesn't mean the code is fast. You need the correct instructions. Not relevant to this example, which is `popcount`ing only a single number, but AVX512 did also introduce SIMD popcount instructions for getting many inputs at a time. Also true for other useful bit-funs like leading or trailing zeros. So if you're using zmm registers, you can do way better than that godbolt example.
- eesmith 3y agoThe following should produce equivalent output: pub fn popcnt(mut x: u32) -> u32 { x.count_ones() } which gets compiled to: example::popcnt: popcnt eax, edi ret For large bit vectors, an AVX2 implementation can outperform POPCNT. See "Faster Population Counts Using AVX2 Instructions" at https://academic.oup.com/comjnl/article/61/1/111/3852071 https://academic.oup.com/comjnl/article/61/1/111/3852071 32 bits is not large enough, and the code Rust produces is indeed comically bad.
- dist1ll 3y agoGreat article, and it’s pretty interesting to see portable simd in use. I tried reproducing the benchmarks on a Zen 3 system, and I’m getting identical speedups. On my M1 mbp, the perf gains start around 1.4x, gradually increasing to 2x @ 110 bytes of input length. A bit less gains than on x86_64, but I’d say it fulfils its goal. Although looking at the code, this article confirms my experience that Rust has rather poor ergonomics for simd and pointer-related work (and performance engineering in general).
- pcwalton 3y agoI disagree with the ergonomics being poor. C++ SSE intrinsics are significantly worse, with ugly underscores and names that are hard to remember.
- dist1ll 3y agoBeing more ergonomic than C++ is a low bar anyways, we should hold ourselves to a higher standard. For starters, field offset syntax is painful (see Gankra's post on this topic) and pointer manipulation lacks syntactic sugar. I also believe unsigned integer promotion and UFCS would improve ergonomics with high-perf code (although I'm aware this is not going to be included in Rust).
- lifthrasiir 3y agoAt 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 a bit far from my ideal. [1] https://github.com/google/highway https://github.com/google/highway
- janwas 3y agoThanks :) We're always curious to hear how it could be improved?
- dzaima 3y agoSmall note - while the compiler wasn't able to optimize that specific popcount implementation to a single instruction, it can for some other implementations, though it's of course very picky: https://godbolt.org/z/T69KxWWW8 https://godbolt.org/z/T69KxWWW8
- deleted 3y ago[deleted]
- Const-me 3y ago> _mm256_cvtps_epu32 that represent a low-level operation in a specific instruction set (this is a float to int cast from AVX2) That instruction is from AVX-512. There’s no AVX2 float to int cast. There’s in AVX1, the int is signed and the instruction is _mm256_cvtps_epi32.
- mattsan 3y agoIn Lua we have indexes off by one and in SIMD we have keyboard letters off by one
- bhumihang 3y ago[flagged]
- alex_suzuki 3y agoAwesome writeup. Leaves me with the distinct impression that „I‘ll never be this smart“.
- hnisoss 3y agoAh, it's just not your field of work. Just like average person is not soft.engineer or physicist or... you get the point. Few months of dedicated study and you would be able to do similar for sure.
- VitruviusBen 3y agoDunning Kruger effect?
- cmrdporcupine 3y agoIf you ever had occasion to have an employer and/or project where this was called for, you could probably "be this smart"; it just comes down to interest and necessity. I dip in and out of these waters (performance optimization, more systems bare metal engineering), but basically on personal projects. I wish I had jobs where it was more called for, but it's not what most industry work needs.
- anonzzzies 3y agoTry doing AoC '23 in APL/j/k, BQN or Python/numpy (meaning, not idiomatic python, but everything with numpy) or cuda etc. It's fun and it will teach you these types of smarts; a lot of the post is very natural on how you think about solving things in those languages. After while you start seeing problems in that form.
- corysama 3y agohttps://fgiesen.wordpress.com/2016/02/05/smart/ https://fgiesen.wordpress.com/2016/02/05/smart/
- anonymoushn 3y agoHow does this compare to fastbase64[0]? Great article, I'm happy to see this sort of thing online. I wish I could share the author's optimism about portable SIMD libraries. [0]: https://github.com/lemire/fastbase64 https://github.com/lemire/fastbase64
- leohacker 3y ago[flagged]
- whalesalad 3y agothe minimap on this page is so cool
- Aardwolf 3y agoIt is crazy sometimes how you try to program something the best you ever could with classical C++, and then someone comes along and makes a version using SIMD that is over 10x faster (but less portable code). I really wish compilers were better at auto vectorization. And some support added for annotations in the language to locally allow reordering some operations, ...
- deleted 3y ago[deleted]
- janwas 3y agoThis happens regularly in my experience :) Also, when using a SIMD wrapper library, it can actually be quite portable in practice.
- kolbe 3y agoThere are unfortunately a lot of serial guarantees that are unavoidable even if compilers could optimize perfectly. For example: 'for(double v: vec) sum+=v' Floating point addition is not associative, so summing each value in order is not the same as summing every 8th element, then summing the remainder, which is how SIMD handles it. So even though this is an obvious optimization for compilers, they will prioritize the serial guarantee over the optimization unless you tell it to relax that particular guarantee. It's a mess and I agree with janwas: use a library (and in particular: use Google Highway) or something like Intel's ISPC when your hot path needs this.
- Aardwolf 3y agoHence my suggestion for language support. Add some language syntax where you can say: "add these doubles, order doesn't matter", which allows the compiler to use SIMD
- kolbe 3y ago-ffast-math if you want to push the onus on the compiler. Problem is you need to enforce that requirement on all user compilations, and I don't know what for MSVC. In-language would be nice.
- intalentive 3y agoSIMD is pretty intuitive if you’ve used deep learning libraries, NumPy, array based or even functional languages
- westurner 3y agoNumPy roadmap: https://numpy.org/neps/roadmap.html https://numpy.org/neps/roadmap.html : > Improvements to NumPy’s performance are important to many users. We have focused this effort on Universal SIMD (see NEP 38 — Using SIMD optimization instructions for performance) intrinsics which provide nice improvements across various hardware platforms via an abstraction layer. The infrastructure is in place, and we welcome follow-on PRs to add SIMD support across all relevant NumPy functions "NEP 38 — Using SIMD optimization instructions for performance" (2019) https://numpy.org/neps/nep-0038-SIMD-optimizations.html#nep38 https://numpy.org/neps/nep-0038-SIMD-optimizations.html#nep3... NumPy docs > CPU/SIMD Optimizations: https://numpy.org/doc/stable/reference/simd/index.html https://numpy.org/doc/stable/reference/simd/index.html std::simd: https://doc.rust-lang.org/std/simd/index.html https://doc.rust-lang.org/std/simd/index.html "Show HN: SimSIMD vs SciPy: How AVX-512 and SVE make SIMD nicer and ML 10x faster" (2023-10) https://news.ycombinator.com/item?id=37808036 https://news.ycombinator.com/item?id=37808036 "Standard library support for SIMD" (2023-10) https://discuss.python.org/t/standard-library-support-for-simd/35138 https://discuss.python.org/t/standard-library-support-for-si...
- westurner 3y agoAutomatic vectorization > Techniques: https://en.wikipedia.org/wiki/Automatic_vectorization#Techniques https://en.wikipedia.org/wiki/Automatic_vectorization#Techni... SIMD: Single instruction, multiple data: https://en.wikipedia.org/wiki/Single_instruction,_multiple_data https://en.wikipedia.org/wiki/Single_instruction,_multiple_d... Category:SIMD computing: https://en.wikipedia.org/wiki/Category:SIMD_computing https://en.wikipedia.org/wiki/Category:SIMD_computing Vectorization: Introduction: https://news.ycombinator.com/item?id=36159017 https://news.ycombinator.com/item?id=36159017 : > GPGPU > Vectorization, Stream Processing > Compute kernels: https://en.wikipedia.org/wiki/General-purpose_computing_on_graphics_processing_units#Vectorization https://en.wikipedia.org/wiki/General-purpose_computing_on_g...
- kookamamie 3y agoISPC is just better, compared to bolting SIMD on C++ or Rust. Also, it supports dynamic dispatching, a feature that is painful to implement yourself.
- anonymoushn 3y agoIs it easy to call into ISPC from C++ and rust for small subroutines like the ones in TFA?
- kookamamie 3y agoYes, extremely easy. ISPC emits objects and header files, which can be directly linked/included from C++. Dynamic dispatching happens automatically and the widest version of the called function gets selected according to the runtime architecture.
- janwas 3y agohm, any tool that enables people to write more SIMD is probably a good thing, but personally I find it preferable to have the SIMD integrated into the same toolchain. This allows us to (inlined!) call back into C++, use templates/classes in the SIMD code, and also inline together multiple SIMD code regions. I agree implementing dynamic dispatch is difficult, but Highway has taken care of that :)
- kookamamie 3y agoHighway is a step to the right direction, but more difficult to use compared to ISPC - e.g. handling remainders is mostly manual and somewhat error-prone.
- janwas 3y agoJust saw your comment. I agree that remainders are tricky. We do have some ready-made algorithms in hwy/contrib/algo and hwy/contrib/unroller which avoid remainder handling. Any thoughts on how this can be improved?
- hansvm 3y ago> This seems like a trick question… just an add right? This sort of thing is part of why you'd often like to target an intermediate vector representation and let the compiler figure out the details. E.g., on Haswell chips you had multiple floating point execution units per core, and the CPU could definitely execute more than one pipelined FP operation simultaneously, but only one of those could be an `add` instruction. If you had a bunch of additions to do which didn't rely on the previously computed results (avoiding stalls), you could double your addition throughput by also dispatching a fused-multiply-add instruction where the multiplicand was just one. That _could_ execute at the same time as a normal vector FP addition.
- deleted 3y ago[deleted]
- fulafel 3y agoWould be interesting to see a comparison vs languages that compile per lane logic to SIMD such as ISPC or (CPU side) OpenCL or others.