Faster: Fast numerical calculations in Rust | Hacker News Reader

Faster: Fast numerical calculations in Rust

github.com

163 pointsblacksmythe52 comments

When I read "absurdly fast", I expected to see some benchmarks against an equivalent SIMD implementation in C or at least a similar library in another language.

Please consider adding such benchmarks so that we can assess how fast this library really is when compared to other more established libraries.

At a quick glance, the "absurdly fast" seems to be talking about programmer time, not cpu time.

It shows four lines of code, and compares it to ~30 lines with the comment "Even with all of that boilerplate, this still only supports x86-64 machines with SSE or AVX ... "

The closing section: "Here are some extremely unscientific benchmarks which, at least, prove that this isn’t any worse than scalar iterators." suggests the final executed code probably runs at around the same speed, but the short version is _way_ easier to write and _way_ more portable.

Compared to 4 lines in Eigen it is not impressive anymore. And that thing cab also statically optimize equations. Call back when Rust grows an equivalent.

I second this. When I do some quick stuff at home or at work, a small ditch in performance is okay, if I spend less time coding. But I know a few people (researchers) with access to >1 PetaFlop/s clusters. Being hit with performance degradation is possibly an issue there: More power consumption; other people need the system, too; as an individual, you might have limited cluster time available. Of course this depends if 1% is to be expected, or 20%...

it seems like the main problem this solves is around the ergonomics of getting Rust to compile your code down to SIMD instructions.

having run into this while working on Rust code a while ago, I really appreciate this library! I would expect Rust users to come to this library when they find themselves working with numeric arrays on Intel CPUs, much like I did.

I think it would be quite useful to me right now, whether or not it turns out to be fast enough to make users doing array computations come to Rust. (I'd guess probably not, although it could get there!)

I'll add benchmarks soon; I'm trying to make it usable first ;).

Right now, it's within 5% of ugly-style explicit SIMD code in the absolute worst case (the example in the README is more like 1%). The hot bit (the body of the map) compiles down to 100% simd instructions in the order LLVM thinks will be the fastest, and the load/store bit has an extra branch per load/store. This is because faster is mainly a bunch of 1-line wrappers around SIMD intrinsics, and a bunch of polyfills which only get used on machines which don't support those intrinsics.

The main reasons you'd experience a perf hit compared to explicit SIMD when using this library would be using runtime feature detection (minimal, and not implemented yet - would add around 2 branches per simd_iter call), getting lazy with gathers/scatters rather than ugly bit-level hacks, and accidentally using operations which aren't vectorizable on your machine (scatters on non-avx512, reductive operations on non-sse4.2, etc) and not realizing it (explicit simd will throw a SIGILL; faster will use a scalar polyfill).

You do you.. but why wait on the benchmarks? its the only thing I care about when I look at this.. I'm willing to forgo semantics if its absurdly fast

If you don't care as much about usability and care only about speed, there's already stdsimd which allows you to invoke SIMD intrinsics directly.

This crate explicitly focuses on usability, and given the limited author time, prioritizes that.

The people behind stdsimd haven't started this thread praising their work as being absurdly fast. Extraordinary claims require extraordinary evidence. A baseless claim accompanied by excuses such as "no time for proofs, working on aesthetics" to avoid presenting evidence that would support those claims doesn't build any confidence on the original claim.

For the record, the author of `faster` did not post to HN. Secondly, since this is just a pleasant wrapper around stdsimd, I wouldn't expect performance to degrade severely. Finally, this is still a maturing project, and no where on their project page does the author claim that their work done.

lay off the unnecessary aggressiveness.

>The people behind stdsimd haven't started this thread praising their work as being absurdly fast.

Neither did the programmer of this lib.

>Extraordinary claims require extraordinary evidence.

Only if one's goal is to convince people who can't be bothered to do the check for themselves. Otherwise one can just make the claim, and let others (if they are interested) sort out whether it's true.

Can't you test for the capabilities of the processor once and use the right SIMD code from then on? Maybe it makes sense to introduce a block around the SIMD code, which gets compiled into different blocks of SIMD instructions. Then you only pay for choosing the right block once. That's what I would do in Haskell at least.

It is the typical approach taken by libraries in C and C++ too (though you can usually hardwire to avoid paying the initial cost). Say, Eigen, OpenCL, fftw, ATLAS to name a few.

This has to be done at a granularity coarse enough that the function call overhead doesn't kill the performance. It has to be entire loops, for example, not just some primitive operation like a dot product (which has at least 3 different implementations on x86).

On my C code, I have a build script that rebuilds a shared library 3-4 times for different CPUs (e.g. with and without -mavx2) and then uses dlopen() to choose the right one at runtime. The actual SIMD code has a bunch of #ifdefs to choose the appropriate implementation for primitive operations.

GCC has function multiversioning [0][1] (__attribute__((target("sse4.2")))) to enable choosing a function implementation based on CPU capabilities at runtime, but that is not suitable for the use case I describe. I want my "high level" code to be the same, but using the right implementation for "primitive" ops like dot product. Using multiversioning would completely kill the optimizer and cause excessive register spilling and other unwanted artifacts.

[0] https://gcc.gnu.org/wiki/FunctionMultiVersioning [1] https://gcc.gnu.org/onlinedocs/gcc-6.2.0/gcc/Function-Multiv...

> This has to be done at a granularity coarse enough that the function call overhead doesn't kill the performance. It has to be entire loops, for example, not just some primitive operation like a dot product.

Yes, You are right! I understood, that they wanted to add the branch to _every_ SIMD instruction. I concur with branching outside of loops.

Re Rust: I expect that one could use a macro around the function (or annotate it, if the macro system is good enough) that generates these different functions and branches to the right one.

I wonder if one could do a Rust version of https://github.com/ekmett/rts ? It's a SPMD-on-SIMD exploratory hack, with SOA and masked branching, built on C++ templates.

Core is https://github.com/ekmett/rts/blob/master/src/rts/varying.hp... and https://github.com/ekmett/rts/blob/master/src/rts/vec.hpp .

So something like rayon + faster?

Yes, plus integrated branched control flow using simd masks.[1]

[1] eg, random ggl link: https://gain-performance.com/2017/05/14/umesimd-tutorial-8-c...

https://github.com/AdamNiederer/faster https://github.com/rayon-rs/rayon

For better or worse I have a very big soft spot for things in programming that go fast, even moreso for things that go really fast.

I look forward to learning more Rust so I can get an excuse to use this.

Back in the day we had to add extra STOP statements at the end of our Fortran programs if the machine was really fast because it would crash through the first one or two.

Really?

That's actually awesome! CPU's and GPU's are capable of breakneck speeds, so I love to see things that really make the most out of the capacity available.

Nope. This is what used to pass for a programmer joke.

      STOP
  C Add a couple more stop statements in case someone runs this on a Cray and it is going so fast it breaks though the first one:
      STOP
      STOP

Well, there is this: http://elixir.free-electrons.com/linux/latest/source/arch/x8...

Yes, Linux does the equivalent of

    while(true)
    {
      halt
    }

I don’t think that code will loop, but why take the risk?

There is/was a detailed description of what it takes to stop an OS that included multiple ways to stop the CPUs, executed in order in the hope/expectation that one of them would work that in the end hit a similar loop, but I can’t find it anymore.

There used to be a Turbo button on most PCs in the 90s which would be on by default but could be disabled to support games made for slower CPUs.

hehe, yes!

When I was young I never understood why someone would turn turbo mode off.

Author of Faster here. Thanks so much for posting this; I was wondering where the flood of stars was coming from!

How do these numbers stack up to equivalent algorithms in C and Fortran?

Are we going to see a RustBLAS soon? Something open-source that could go up against MKL for performance would be really amazing.

It would be cool to have some equivalent of a complete BLAS implementation in pure Rust, but I am not sure how sensible/economically viable that would be. But there do exist Rust creates built on top of existing BLAS libraries, e.g. https://github.com/mikkyang/rust-blas Rather, I'd like to have something like Python's Numpy for Rust, not sure there is something equivalent to that, but this faster crate certainly is a step in that direction, conceptually at least.

What's the point of reimplementing BLAS in Rust? Those libraries have been polished for literally decades. They're not even security critical.

No point of doing it in Rust specifically, as opposed to any other language.

But the point would be no longer having to trade software freedom (or at least open source) for performance -- try benchmarking Numpy built on MKL vs OpenBLAS and you'll see what I mean.

If someone gets inspired by a new language to try and write a free or open-source MKL competitor, because that language has such-and-such features that make it more feasible than in Fortran or C, then that'd be fantastic. All I was suggesting is that it'd be cool if Rust was that language.

Superlatives are problematic because for instance "fast" is relative to something and that something might change over time.

Superlatives are usually challenged and you will require proof. The proof itself can also be challenged. Suddenly you are spending a lot of time.

I would rather say: "SIMD math library" rather than "Fast library".

"Faster" is technically a comparative, not a superlative. Otherwise, sound advice.

Right, superlative is not the right term. "Fastest" would be the superlative, and is not in use.

I am just generally against referring to software in absolute terms like: simple, fast, friendly, lightweight, etc. since it can be misleading.

I consider a good practice to separate facts and opinions to achieve clear communication. Passing opinions as facts is dogmatism.

Is there a simpler way than building to find out whether a crate requires nightly, as this one does?

You could try clicking on the "build|passing" badge and see what it's being built against.

Check src/{main, lib}.rs for any !#[feature] flags.

Utterly superficial thought, but how about the name "fastr" for this crate?

Making it harder to look up / talk to people about seems worse ;)

Using a common adjective for your project name already makes it difficult to search for. Misspelling it works in your favor.

Except for autocomplete...

Are you referring to “fastr” or “faster”, though? I’d imagine the former is much, much, much easier to google for and remember than “faster rust library”, which could return basically any piece of rust code ever.

fastr is a loaded term already anyway, plenty of google hits for it (graalvm’s r implementation). Crates.io search works just fine though

or "simder"

Won't the compiler be autovectorising that kind of code already?

Sadly, even something like [1.0f32].map(|s| s.sqrt().abs().recip()).collect() doesn't get vectorized 99% of the time; you can check the disassembly and you'll see sqrtss et al.

There are some llvm flags you can pass to see what got autovectorized in the rustic output. And some that make it autovec more stuff. It is really sensitive to container size. Just throwing a few flags when compiling n-body speeds it up quite a bit over the one up on the benchmark game. I got it to beat the c implementation which had explicit SIMD with portable rust code. Still didn't beat FORTRAN with ifort but faster than gfortran. Also, when rust brings in an llvm with newgvn the autovec should get better.

I thought modern languages optimized code into SIMD instructions where it could automatically...

I know Java does this.

They do. It's called auto-vectorization and the Rust compiler does it (mostly by virtue of LLVM). But there are thousands[1] of SIMD instructions just for x86_64 alone and auto-vectorization doesn't come close to covering all of them. Even if auto-vectorization does cover the instructions you want to use, you might be justifiably uncomfortable with relying on it for performance in every case (or perhaps you simply can't rely on it), and would instead prefer to explicitly write out the transformations.

[1] - https://software.intel.com/sites/landingpage/IntrinsicsGuide...

LLVM and rustc are pretty fickle with what they'll autovectorize. The idea of faster is to make things which are impossible to autovectorize easy to write as SIMD.

A few examples I'm targeting for the next point release are matrix determinants, cross products, byte-aligned encoding (like https://github.com/AdamNiederer/base100/blob/master/src/lib....), and reductive operations like strcmp. AFAIK none of that can be autovectorized at all.

Did you also know that a sufficiently smart compiler can deduce the whole programming logic from English prose?

It's just pretty hard to create one. Same applies to automatic optimizations in the general case: what do you exactly know about what Java does beyond that it is capable of using SIMD instructions? Have you perhaps evaluated how and where it does so, or how the end result compares to more explicit manual use of stream operations?

edit: and for the record, the problem is not as easy as you seem to think it is, given how you described your astonishment.

> I thought modern languages optimized code into SIMD instructions where it could automatically...

Kinda-sorta yes, but not really. Auto-vectorization is a very brittle optimization that only works at the best of times and the slightest change in your code can cause it to fall out of the hot path. You have to be extra careful with aliasing and use the "restrict" keyword a lot.

If you really do care about performance, you still have to write your hot loops with explicit SIMD code.

I don't see absurdly fast anything in this post. Are there any benchmarks that would support the statement "absurdly fast numerical calculations"?

Reply on news.ycombinator.com