SIMD instructions

https://opensourceweekly.org/issues/7

by _3lin • 6 years ago

129 121 6 years ago

opensourceweekly.org

nickysielicki5• 6 years ago

Plus many many more if they use the right compiler flags and use aligned types.

I wrote this a couple days ago: https://sielicki.github.io/posts/playing-around-with-autovec...

mynegation• 6 years ago

Exactly this! I am glad this list exists but even more interesting question is what are the reasons for the list like that to exist? Ideally it is up to the compiler to user target architecture to its maximum potential.

Every item on this list is a library, compiler optimization, or an idiomatic abstraction waiting to happen.

saagarjha9• 6 years ago

Most compilers will by default generate portable code.

Twinklebear2• 6 years ago

SIMD is used a ton in rendering applications and starting to see more use in games too (through ISPC for example).

I'd add to the list:

- Embree: https://www.embree.org/ Open source high-performance ray tracing kernels for CPUs using SIMD.

- OpenVKL: https://www.openvkl.org/ Similar to Embree (high-performance ray tracing kernels), but for volume traversal and sampling.

- ISPC: https://ispc.github.io/ an open source compiler for a SPMD language which compiles it to efficient SIMD code

- OSPRay: http://www.ospray.org/ A large project using SIMD throughout (via ISPC) for real time ray tracing for scientific visualization and physically based rendering.

- Open Image Denoise: https://openimagedenoise.github.io/ An open-source image denoiser using SIMD (via ISPC) for some image processing and denoising.

- (my own project) ChameleonRT: https://github.com/Twinklebear/ChameleonRT has an Embree + ISPC backend, using Embree for SIMD ray traversal and ISPC for vectorizing the rest of the path tracer (shading, texture sampling).

z0mbie429• 6 years ago

Hi, thank you for the pointers!

I try not to include C or C++ projects other than for educational purpose (like the Mandelbrot set) because one of my life's goal is to help the world to transition to a C & C++ free world (other than for kernels...).

I believe that my role is to promote projects which are "building the new world" and thus we need to abandon and port all form insecure core.

sk0g• 6 years ago

So in an article about high/extreme performance systems, you're ignoring the vast majority of them because you don't agree with the tool used to achieve said performance? What..?

fermentation• 6 years ago

Despise of C and an interest in high-performance, a unique mix.

hedora• 6 years ago

Some of the most secure software is written in C.

The language matters less than you’d think once you get past a certain correctness baseline.

adev_5• 6 years ago

By the sake of god, please stop to put C and C++ in the same basket when talking about security.

It just show you do not know what you are talking about.

Most security problems affecting C program DO NOT affect C++ programs.

Stack smash, vla abuse, string null termination problems, goto error control, double free corruption do NOT affect C++, they are C specific.

bityard2• 6 years ago

I mean, have you even _seen_ the trail of CVEs that Java has left in its wake over the past few decades?

z3phyr• 6 years ago

In my opinion, we should instead focus on hardware and experiment more with different kinds of cpus, memory, co-processors etc. The key to newer software systems are newer kinds of hardware, for which you can write newer experimental systems in the language of your own designs.

The sky is the limit, and there is so much to do! Transactional memory, massively multicore computers, hardware built on predicate logic, neuromorphic computers, and whatnot.

We are still mostly stuck with the cpu and memory designs of old.

misnome• 6 years ago

ISPC: https://ispc.github.io/ an open source compiler for a SPMD language which compiles it to efficient SIMD code

I've been learning ispc lately and it does seem like a wonderful solution, you avoid having to build separate implementations for every instruction set and/or worrying about per-compiler massaging to get it to recognise the vectorisation opportunities. The arguments for having a domain-specific language variant and why it was written (https://pharr.org/matt/blog/2018/04/30/ispc-all.html is a good read) seem like persuasive arguments.

However, outside of the projects in the above list - it doesn't seem to have very wide usage. There are still commits coming in/responding to some issues so it doesn't seem dead, but there are many issues untouched or just untriaged. There isn't much discussion about using it, or people asking for advice. The mailing list has about a message a month.

Is it merely just an extremely highly specialised domain? Is it just that CUDA/OpenCL is a more efficient solution for most cases where one would otherwise consider it? Are there too many ASM/intrinsic experts out there to bother learning?

adev_5• 6 years ago

However, outside of the projects in the above list - it doesn't seem to have very wide usage.

ISPC is pretty popular in the HPC world.

Twinklebear2• 6 years ago

ISPC is really awesome, but you're right it is much less known than CUDA/OpenCL. Part of that might just be lack of marketing effort and focus (you don't hear much about it compared to e.g. CUDA) and the team working on it is far smaller than that on CUDA. There has been some wider adoption, like Unreal Engine 4 using it now: https://devmesh.intel.com/projects/intel-ispc-in-unreal-engi... which is super cool, so hopefully we'll see more of that.

As far as support from other languages I did write this wrapper for using ISPC from Rust https://github.com/Twinklebear/ispc-rs (but that's just me again), and there has been work on a WebASM+SIMD backend which is really exciting. Intel does also have an ISPC based texture compressor (https://github.com/GameTechDev/ISPCTextureCompressor) which I think does have some popularity.

However, the domain is pretty specialized, and I think the fraction of people who really care about CPU performance and are willing to port or write part of their code in another language is smaller still. It's also possible that a lot of those who would do so have their own hand written intrinsics wrappers already. Migrating to ISPC would reduce a lot of maintenance effort on such projects, but when they already have momentum in the other direction it can be harder to switch. I think that on the CPU ISPC is easier and better than OpenCL for performance and tight integration with the "host" language, since you can directly share pointers and even call back and forth between the "host" and "kernel".

KMag• 6 years ago

At work, I had a project involving a DSL for Monte Carlo simulations. The DSL was an internal DSL in Scala, our interpreter was in Scala, and we transpiled to ISPC (for servers/VMs that didn't expose a GPU) and OpenCL.

I generally liked ISPC, but I really didn't like that it tried to look as close as possible to C but departed from C in unnecessary ways. With Monte Carlo simulations, we deal with a lot of probabilities represented as doubles in the range [0.0, 1.0]. The biggest pain is that operations between a double and any integral type cast the double to the integral type, whereas in C, the integral type gets implicitly cast to a double. I understand the implicit casting rules were changed to give the fastest speed rather than minimize worst-case rounding error. I could understand getting rid of implicit casts, or maybe I could understand changing rules to improve accuracy and know that the user could easily use a profiler to discover any performance problems this caused. However, in our case, uint32_t * double = (uint32_t) 0, which then would get implicitly cast back to a double if being assigned to a variable. My interne was beating his head against the wall for the better part of an afternoon before I gave him a bit of debugging help. All of his probabilities were coming out 0% and 100% for his component.

I actually emailed the authors with a bug report when I found the implicit casting rules differed so radically from C and were in the direction away from accuracy. (Note there's no rounding error when converting uint32_t to a 64-bit IEEE-754 double.) They were very nice, and pointed us to where this behavior was documented.

If you're going out of your way to make your language look like C and interoperate seamlessly with C, you should have really strong justifications for the places where you radically depart from C's semantics.

apjana7• 6 years ago

Adding nnn: https://github.com/jarun/nnn A terminal file manager.

It takes advantage of SIMD at -O3 level of optimization in it's custom string copy function: https://github.com/jarun/nnn/blob/bc7a81921ed974a408d4de2cbf...

The function is used extensively in the program.

saagarjha9• 6 years ago

I don’t see why you’d write one of these yourself when the one in the standard library is probably vectorized too, and better…

bityard2• 6 years ago

starting to see more use in games

Starting to see? Back in Ye Olde 586 Days of the late 1990s, MMX was added to the Pentium architecture pretty much exclusively for 3D games and real-time audio/video decoding. (This was back when the act of playing an MP3 was no small chore for the average consumer CPU.) Intel made quite a big deal over MMX including millions of dollars in TV ads aimed at the general population, despite the fact that software had to be built specifically to use MMX and that only certain kinds of software could benefit from it.

djmips• 6 years ago

Indeed it's been a workhorse since forever. All the consoles from PS2 forward have included some form of SIMD and it is used extensively.

Here's a GDC 2015 article about SIMD at Insomniac Games. https://deplinenoise.files.wordpress.com/2015/03/gdc2015_afr...

rasz• 6 years ago

MMX had nothing to do with games! It was a part of Intel _marketing scam_. https://news.ycombinator.com/item?id=19468837 :

"MMX was useless for games. MMX is Integer math only, good for DSP, things like audio filters, or making a softmodem out of your sound card. Unsuitable for accelerating 3D games. Whats worse MMX has no dedicated registers, and instead reuses/shares FPU ones, this means you cant use MMX and FPU (all 3D code pre Direct3D 7 Hardware T&L) at the same time. ... Funnily enough AMDs 1998 3DNow! did actually add floating point support to MMX and was useful for 3D acceleration until hardware T&L came along 2 years later.

Intel Paid few dev houses to release make believe MMX enhancements, like POD (1997)

https://www.mobygames.com/images/covers/l/51358-pod-windows-...

1/6 of box covered with Intel MMX advertising while game used it only for some sound effects. Intel repeated this trick in 99 while introducing Pentium 3 with SSE. Intel commissioned Rage Software to build a demo piece showcasing P3 during Comdex Fall. It worked .. by cheating with graphic details ;-) Quoting hardware.fr "But looking closely at the demo, we notice - as you can see on the screenshots - that the SSE version is less detailed than the non-SSE version (see the ground). Intel would you try to roll the journalists in the flour?". Of course Anandtech used this never released publicly cheating demo pretending to be a game in all of their Pentium 3 tests for over a year.

https://www.vogons.org/viewtopic.php?f=46&t=65247&start=20#p... "

MMX was one of Intel's many Native Signal Processing (NSP) initiatives. They had plenty of ideas for making PCs dependent on Intel hardware, something Nvidia is really good at these days (physx, cuda, hairworks, gameworks). Thankfully Microsoft was quick to kill their other fancy plans https://www.theregister.co.uk/1998/11/11/microsoft_said_drop... Microsoft did the same thing to Creative with Vista killing DirectAudio, out of fear that one company was gripping positional audio monopoly on their platform.

capableweb• 6 years ago

Looks like a blog post, so shouldn't really be a Show HN. Take a look at the guidelines: https://news.ycombinator.com/showhn.html

This week has been particularly bad regarding security

Seems like a weird way to phrase it, when talking about security fixes. If it was about security vulnerabilities, I would understand you say it's bad, but in this case it's about fixing vulnerabilities, that's good right?

z0mbie429• 6 years ago

Oops, Fixed!

I prefixed with "Show HN" because I started this newsletter 7 weeks ago and wanted to 'show it' to HN.

You are right regarding the phrasing (I'm not a native English speaker, so any feedback is welcome). Fixed :)

reikonomusha• 6 years ago

A Common Lisp project that uses SIMD (specifically AVX2) is the Quantum Virtual Machine [1]. It’s a quantum computer simulator. Here [2] is part of the source that has the SIMD instructions.

It’s cool that with using SBCL, an implementation of Common Lisp, you can write compartmentalized assembly very easily in an otherwise extremely high-level language.

[1] https://github.com/rigetti/qvm

[2] https://github.com/rigetti/qvm/blob/master/src/impl/sbcl-avx...

haolez• 6 years ago

I found this curious regarding QuestDB[1]:

Java 8 64-bit. We recommend Oracle Java 8, but OpenJDK8 will also work (although a little slower).

Anyone have an idea why?

[1]https://github.com/questdb/questdb

bluestreak• 6 years ago

This is because OracleJDK has more intrinsics than OpenJDK.

dmos62• 6 years ago

To someone just hearing about SIMD, anyone care to give an experience infused introduction? Is it worth the hassle only in rare cases?

tombert• 6 years ago

If you are just hearing about it, there's a good chance that you're not doing any kind of elaborate matrix math, so it's tough to say if it's useful.

It's incredible useful if you're doing a lot of stuff involving matrices (graphics, image/video processing, neural-net stuff, stuff like that). If you have any interest in that topic, it's absolutely worth learning how to use SIMD (or at least learning a library that takes advantage of SIMD in your language of choice).

augustt• 6 years ago

Compilers are really smart, so in many cases they will vectorize without even asking - no hassle involved. Some examples here: https://llvm.org/docs/Vectorizers.html

TazeTSchnitzel2• 6 years ago

GCC and Clang will try their best to vectorise simple code, but if you try to write more complex algorithms, they will have a more difficult time and you may end up trying to massage your code to be more vectoriser-friendly. Auto-vectorisation is no substitute for a predictable SIMD programming model.

nickysielicki5• 6 years ago

Is it worth the hassle only in rare cases?

Vectorization is not always faster. It's important to understand that modern processors can perform work on >100 instructions in a given cycle, and not all instructions take equal amounts of time. So reducing a dozen instructions to a single instruction doesn't necessarily mean that the single instruction is going to be faster.

atq2119• 6 years ago

This is misleading, at least if you're looking at a single core.

A single core can have >100 instructions in flight, but most of them will be waiting for their operands to arrive. The theoretical maximum throughput is gated by the instruction decoders and execution units, and is an order of magnitude lower.

vardump4• 6 years ago

So reducing a dozen instructions to a single instruction doesn't necessarily mean that the single instruction is going to be faster.

Are you saying dozen scalar instructions can be faster than one vector instruction? That's wrong 100% of time on modern CPUs.

dahart• 6 years ago

GPUs are SIMD machines, does that color whether it seems rare? Coming from a graphics background and working on GPUs, I am super biased, but I say it's very worth the hassle.

The easiest intro IMO is check out & play around in ShaderToy. You don't have to know much about SIMD to write shaders, but once you start paying attention to how the machine works, you can make it go really fast.

In general, using something like CUDA is similar to C++ you just have to make sure all your threads do as close to the same thing as possible in order to see good perf.

xioxox• 6 years ago

It's certainly useful for quite a lot of mathematical science code. In my experience compilers are not very good at autovectorizing anything but the most simple loops and writing SIMD intrinsics is necessary to obtain the maximum output of the processor.

calaphos2• 6 years ago

The cpu just takes a bunch of numbers and applies the same operation on them in one instruction instead of a bunch single ones. E.g. if you are writing some simulations/game code where you deal with 3d vectors a lot the use case is there a lot. Is it worth writing the custom instruction intrinsics yourself? Most likely no as the compiler often (!) does a good job at auto vectorizing or the underlying library already uses them (I think c# vector types does).

truth_seeker• 6 years ago

JVM generates SIMD to certain extent, i wish other runtimes like V8 (Browser/NodeJS), Go, BEAM (Elixir/Erlang) etc did the same.

gameswithgo3• 6 years ago

JVM does it to an extremely limited extent. Anything jitted, doesn't have a lot of time to do autovectorization. Even GCC/llvm are pretty limited at this, as it is just a hard problem, and doing it with floating point is problematic as it usually changes the result.

pjmlp12• 6 years ago

To a limited extent that also takes advantage of AVX thanks to Intel contributions.

All modern JVMs take advantage of code caches and possibly PGO (depending on the configuration) between runs.

ART also does the same for NEON.

poorman• 6 years ago

Surprised Apache Arrow isn't on this list.

https://arrow.apache.org/ > Apache Arrow™ enables execution engines to take advantage of the latest SIMD (Single instruction, multiple data) operations included in modern processors, for native vectorized optimization of analytical data processing.

andrea_s• 6 years ago

Yandex ClickHouse also should be on the list!

tarr11• 6 years ago

Apache Lucene has recently started using SIMD to decode postings lists (Java)

https://issues.apache.org/jira/browse/LUCENE-9027

singhrac• 6 years ago

Pretty much every neural network framework is aggressively SIMD-optimized (after all, that's kind of the point besides autodiff), not sure why Tencent's framework is picked..

If you know about it, I want to hear about more fast SIMD-based CLI tools that can replace my existing workflow (e.g. burntsushi's ripgrep or xsv).

z0mbie429• 6 years ago

Thank you for the feedback.

I picked Chinese technology because they are rarely promoted but really great.

Regarding the CLI tools it's a great question and I have opened a ticket for a future issue: https://gitlab.com/bloom42/open_source_weekly/-/issues/14

vmchale• 6 years ago

gcc can do SIMD on its own quite surprisingly (to me)

https://github.com/vmchale/ats-codecount/blob/master/DATS/wc...

FZ1• 6 years ago

Adding the obvious numpy vectorization - I presume that counts as an 'open source project'?

Or maybe this is limited to little personal projects, and not major libraries ?

burntsushi3• 6 years ago

ripgrep does, and it's a big reason why it edges out GNU grep in a lot of common cases, especially for case insensitive searches. The most significant use of SIMD is the Teddy algorithm, which I copied from the Hyperscan project. I wrote up how it works here: https://github.com/BurntSushi/aho-corasick/blob/66f581583b69...

z0mbie429• 6 years ago

I wasn't aware! Added it.

Thank you very much for all your work. Your CLI tools are really making a positive impact on the world of development.

mastax• 6 years ago

The intended connotation of ripgrep wasn't "RIP Grep" but that it rips through searches, i.e. it is fast. I can't find the comment where he said this but burntsushi can confirm.

burntsushi3• 6 years ago

Thanks, I appreciate it.

But could you take out the part that says it "aims to kill grep"? That definitely wasn't my intention. grep still has a place. See https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#int... and https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md#can...

TazeTSchnitzel2• 6 years ago

SIMD […] is a good alternative to multithreading

They are not alternatives to eachother, they are orthogonal things, unless you're using a GPU.

z0mbie429• 6 years ago

They can, but as explained in one of the article (by Cloudflare, "On the dangers of Intel's frequency scaling") SIMD in a multithreaded environment can cause performance problems due to CPU throttling.

So generally SIMD are used for single thread algorithms.

gameswithgo3• 6 years ago

I'm not sure it is fair to say "Generally". Sometimes, you maybe don't want to multithread it. When I've used it, multithreading was still useful, despite downclocks, by huge margins.

And on AMD cpus, the downclock issue doesn't exist near as badly.

opportune2• 6 years ago

If you're doing a scientific workload where you need to process all your vectors before moving on to the next part of the simulation, you're still better off multithreading your vectorized operations even with the throttling.

gameswithgo3• 6 years ago

I have a couple of videos introducing intel SIMD intrinsics and how to use them well.

For Rust/C/C++: https://www.youtube.com/watch?v=4Gs_CA_vm3o

For C#: https://www.youtube.com/watch?v=8RcjQPbvvRU

corysama3• 6 years ago

The megahertz-scaling "Free Lunch" was declared dead 15 years ago [http://www.gotw.ca/publications/concurrency-ddj.htm] and it's been only getting deader. People are finally, grudgingly accepting that they must go parallel unless we want to see software performance stagnate permanently. For most people here, the issue has been obvious since before they learned to program. But, still they are putting off learning how to deal with it. The first, obvious answer to that is threading. But, in my experience, SIMD is a bigger bang for the buck for two reasons: 1) No synchronization problems. 2) Better cache utilization. It's not just that SIMD forces you to work in large, contiguous blocks. Fun fact: When you aren't using SIMD you are only using a fraction of your L1 cache bandwidth!

A big challenge is that SIMD intrinsic-function APIs are weird. They have inscrutable function names and sometimes difficult semantics. What helped me greatly was going through the effort of writing #define wrappers for myself that just gave each function in SSE1-3 names that made sense to me. I don't expect many people to put in that effort. And, unfortunately, I don't have go-to recommendations for pre-existing libraries. Best I can do is:

https://github.com/VcDevel/Vc is working on being standardized into C++. It's great for processing medium-to-large arrays.

https://ispc.github.io/ is great for writing large, complicated SIMD features.

https://github.com/microsoft/DirectXMath is not actually tied to DirectX. It's has a huge library of small-vector linear algebra (3D graphics math) function. It used to be pretty tied to MS's compiler. But, I believe they've been cleaning it up to be cross compiler lately.

CyberDildonics• 6 years ago

Can you say more about non SIMD instructions not making full use of the L1 bandwidth? Is it just that even keeping all the integer units busy still doesn't equate to using all the bandwidth? I suppose that makes sense when adding up the numbers for clock cycles and bytes. I'm guessing this not common to point out since being limited to L1 cache bandwidth is so unlikely to be a program's main bottleneck.

corysama3• 6 years ago

Intel's scalar pipelining does do an amazing job of keeping pipes busy. And, well-pipelined code can approximate SIMD performance. But, in practice to solidly get that kind of pipelining you need to pretty much write your scalar code as if you were emulating SIMD.

But, the point is that a 4-byte load instruction leaves 12 bytes of bandwidth on the table for many architectures -even with a perfect L1 cache hit.

I point it out because I usually get rebuttals that everything is memory bound (true) and that using the cache well is more important (true, but it turns out...).

jzelinskie• 6 years ago

Reminder that nothing is a panacea: I've heard from game engine authors and cryptographers that on Intel chips _over-using_ SIMD can actually heat up the chips too much such that it'll cause the system to then adjust the clockrate lower to cool down and you can degrade performance beyond not using SIMD at all. Before hearing that, I had never considered thermal properties of particular instructions.

saagarjha9• 6 years ago

That’s probably AVX-512.

corysama3• 6 years ago

It's not a problem for SSE and AVX1. But, with AVX2/AVX-512, the deal is that you should not just dip your toe with an occasional call to a small SIMD task using such heavy-hitting features. Either do enough SIMD work to overcome the down-clock, or use a lower-end SIMD functionality for smaller tasks.

And, even within AVX2/512 there are huge sets of added functionality that are really "AVX1-enhanced" without going wider. Those are fine to use to without worrying about downclocking.

calaphos2• 6 years ago

The AVX ALUs also go into power saving when not used and take a couple of cycles to switch back on, delaying the first AVX instruction. There is afaik even a paper on a side channel attack that uses this.

robocat• 6 years ago

“Intel cores can run in one of three modes: license 0 (L0) is the fastest (and is associated with the turbo frequencies written on the box), license 1 (L1) is slower and license 2 (L2) is the slowest. To get into license 2, you need sustained use of heavy 512-bit instructions, where sustained means approximately one such instruction every cycle. Similarly, if you are using 256-bit heavy instructions in a sustained manner, you will move to L1. The processor does not immediately move to a higher license when encountering heavy instructions: it will first execute these instructions with reduced performance (say 4x slower) and only when there are many of them will the processor change its frequency. Otherwise, any other 512-bit instructions will move the core to L1: the processor stops and changes its frequency as soon as an instruction is encountered.”

Great info from here: https://lemire.me/blog/2018/09/07/avx-512-when-and-how-to-us...

Be careful to benchmark real loads as there are perverse interactions e.g. “Downclocking, when it happens, is per core and for a short time after you have used particular instructions (e.g., ~2ms).“ so a function using AVX512 can affect the speed of unrelated code (similar to thermal throttling).

The_rationalist• 6 years ago

The easiest way to benefit from SIMD is to use OpenMP SIMD directive on for loops.

GordonS• 6 years ago

As a point of interest, you can even use SIMD (and other hardware intrinsics) in dotnet core, since 3.0, e.g. https://medium.com/@alexyakunin/geting-4x-speedup-with-net-c...

dang• 6 years ago

This is a list of articles—probably a good one, but HN is itself a list of articles, so this is too much indirection.

Lists don't make good HN submissions, because the only thing to discuss about them is the lowest common denominator of the items on the list [1], leading to generic discussion, which isn't as interesting as specific discussion [2].

It's better to pick the most interesting item from the list and submit that. You can always do it more than once, if there is more than one interesting item—but it's best to wait a while between such submissions, to let the hivemind caches clear.

[1] https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

[2] https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

veselin• 6 years ago

I was wondering generally, is SIMD a good idea for general purpose CPUs. Imagine if the current high end CPUs had double the number of cores, no SIMD, but possibly higher frequency and the algorithms that benefit from SIMD were all run on integrated accelerators instead.

At least as a side observer it looks like a huge number of very large registers take large portions of a core, for sure consuming a lot of power as well, just to sit idle while the core is running JavaScript. Can somebody with CPU architecture experience say what is the real tradeoff here.

zamadatix• 6 years ago

Adding SIMD takes less space than adding cores and the use case where you need double the cores on a many core chip but aren't doing the same thing many times is pretty rare.

SIMD units don't need to consume power or limit the frequency of the rest of the chip while not being used Same as when JavaScript is running on one boosted core and the other 63 powersave. While being used SIMD units are more efficient than running 2x or 4x entire cores just to get the additional operation per clock.

SIMD instructions

Related Stories