Hacker News Reader

Comment by forrestthewoods | Hacker News Reader

I'm not familiar with some of these operations. I don't know what a Rust "slice" is. Or what "Zip" does.

Could someone show me the most straight forward equivalent in vanilla C? I assume there is no direct equivalent as temporary storage will be needed. But that's fine and would further serve the purpose of explaining why Rust is cool.

Thanks.

View on HN

A slice is a pointer + a length. Zip takes two iterators and gives an iterator that returns pairs of elements from each of them.

For an imperative translation see https://www.reddit.com/r/programming/comments/5fpghn/zerocos...

Doing an exact translation to C is hard. The C that does the same thing, or C that demonstrates these abstractions that are boiling away?

The thing with C is also that it's hard to do metaprogramming. Example, I have some finite element code that ideally, I would like to run for an arbitrary dimension. In C, this is practically impossible to code efficiently, while in C++ (and I suppose in Rust) I belive this can be done with templates (though I have not too much experience with this).

Uh, the C equivalent might be something like

    uint32_t *buffer = ...;
    uint64_t coefficients[12] = {...};
    uint16_t qlp_shift = ...;

    uint32_t *bufp = &buffer[...];
    uint64_t sum;
    for (size_t i = 0; i < 12; i++)
        sum += coefficients[i] * bufp[i-12];
    uint64_t prediction = sum >> qlp_shift;
    *bufp += (uint32_t)prediction;

Edit: this is incorrect

Which -in my opinion- is a lot clearer than the Rust code in the article.

That's totally fair, but that may have something to do with how well you know Rust. I obviously don't know your familiarity level, but once your mental models "snap" out of thinking about moving data around, and start thinking about operations upon the data, it gets really intuitive.

I've seen Rust written in imperative style, and it was clear to me in most of the cases. I think it's more the difference between imperative and functional styles that's throwing people for a loop.

Yeah this is clearly someone who's into FP. If you rewrite this code to replace the map/sum with a for loop it's basically identical in length, while being completely idiomatic.

It took me some tome to embrace this style in Rust, but now o love it. It cuts down on boiler plate code.

> I think it's more the difference between imperative and functional styles that's throwing people for a loop.

Pun intended? If so, nicely done.

I am familiar enough with functional programming patterns. I could probably understand this if I had some more experience with Rust. But I think I would be able to understand the snippet in most imperative and functional languages.

My point is not that the snippet is bad, just that Rust feels, looks, and probably is, quite complex. As opposed to, for example, Haskell, which also introduced a bunch of nice, new, ideas.

  > Rust feels, looks, and probably is, quite complex. As opposed to, for example, Haskell

Do you really think that Haskell is less complex than Rust, or am I just reading your comment wrong?

> I am familiar enough with functional programming patterns.

Really? I've never used rust but the code was pretty clear to me except for the >> shift part.

> But I think I would be able to understand the snippet in most imperative and functional languages.

In Python (ignoring the shift thingy) I'd write

  prediction = sum(map(lambda c, s: c*s, zip(coefficients, buffer[i-12: i])))

To me, both are equally clear

On the other hand, the Rust code is guaranteed at compile time to be free from buffer overruns, off-by-one errors, and a whole host of other nasties.

I know, I know, the C code you write never has buffer overruns, just like the C code I write never does, well, except that one time, but then I caught it in the debugger during testing and it was easy to fix. Oh, and then that other time, but I caught that one too, and then.....

You forgot about the time you forgot to zero the memory before using it, and it took a week to track down the random junk appearing in you data.

> you forgot to zero the memory before using it

Nah, I did that on purpose because I remember the time I accidentally swapped the 'value' and 'size' parameters of memset, trashing the stack, and so now I go the 'safer' option to just leave things uninitialised. Not to mention the performance increase I get from avoiding a memset that isn't necessary, so long as I'm really, really careful and never make a mistake, which I almost never do.

I love how a type safe memset that distinguished between size types and value types would have fixed your problem (with no run time overhead), but you take this a reason to do even more unsafe stuff that has dubious costs for dubious advantages.

And I cannot tell if you are serious, trolling or sarcastic, because I know people who think this way, think this way is a joke and think this way is the bane of their professional lives.

Not being serious, but joking based on real life things have have bitten me at one point or another, and the mindset of some developers dismissing the benefits of safety and caring about mostly non-existent speed benefits.

> On the other hand, the Rust code is guaranteed at compile time to be free from buffer overruns

No it's not. In this line:

    .zip(&buffer[i - 12..i])

you can just put any indices and it will compile.

But it will not read outside of the buffer. It will panic at runtime instead. That's not a buffer overrun.

It's still an error discovered at runtime. It's one that smacks you in the face instead of silently doing the wrong thing, but it's still found at runtime. I really prefer my errors to be found at compile time, but that's often harder to do...

This is incorrect. The C code is more like

    for (size_t i = 0; i < 12; i++) {
        sum = 0;
        for (size_t j = 0; j < 12; j++)
            sum += coefficients[j] * bufp[i + j];
        buffer[i + 12] += sum >> qlp_shift;
    }

Whoops! You're totally right. I missed the outer loop. Thanks for the correction.

I think this is still a little off. Maybe you used bufp[i + j] where you meant buffer[i + j]? I may have something wrong too, but I probably would go with:

    for (size_t i = 0; i < 12; i++) {
        int64_t sum = 0;
        int32_t *bufp = buffer + i;
        for (size_t j = 0; j < 12; j++)
            sum += coefficients[j] * bufp[j];
        *bufp += (int32_t)(sum >> qlp_shift);
    }

I think this will put it in a form where the compiler should vectorize it[1], probably making the loop about twice as fast as the version shown: 3 vector loads, 3 vector multiplications, 3 vector additions and a horizontal sum versus 16 scalar loads[2], 12 scalar multiplications and 12 scalar additions.

[1] I presume the "various reasons the above snippet is not as obvious to vectorise as it might seem at first sight" is because the coefficients[] are 64-bit and buffer[] is 32-bit. But a smart compiler should be able to use PMOVSXDQ (packed move sign extend double-word to quad-word) here. Unless there is some other issue, I think the author may be underestimating the benefit of vectorizing here.

[2] While the author is right that most of coefficients stay in registers, there isn't actually room for all 12, so 4 of them are loaded from the stack every iteration. Since only 3 128-bit vector registers are required, they should remain there. I'm not sure if the excess loads are actually a bottleneck, though.

This whole thread: C is fine. We're fine. Everything's fine here now. How are you?

Why the insult?

Memory safety without a hit in performance seems like a great thing, and this is a fine example that it's becoming possible. The point is not that C is always fine. In this case, I think the actual conclusion is something like: C and Rust perform equally here, both have about 50% of the theoretical assembly performance on modern processors, thus better vectorization would help both of them. But if all else is equal, choose the safe one.

> I think this will put it in a form where the compiler should vectorize it

I played around with you snippet using the compiler explorer https://godbolt.org/ . I tried a couple versions of clang, gcc, and icc and none of those were able to auto-vectorize it. Not sure why. Kind of a shame, since there would definitely be a speedup.

Thanks for testing it. You inspired me to try as well, and I've found that Intel ICC 16 and 17 will vectorize it if you put "#pragma vector always" before the inner loop. Without it, it thinks that the write to buffer[i] might interfere with the reads of buffer[i + j]. I think this is because it's trying to "jam" the inner and outer loop.

In addition, I discovered a couple other issues. I was embarrassed to see that I'd messed up the loop bounds in my example. But the bigger one is that AVX2 and earlier do not have a 64-bit x 64-bit -> 64-bit vector multiplication instruction. VPMULLQ was only added with AVX512, possibly because it requires a 512-bit intermediate.

This means that with 64-bit coefficients, the vector approach has to do the multiplications twice, and shift, and add. This is likely going to be slower than the scalar approach. But if you were able to switch to 32-bit (or floating point) coefficients, I think the vectorized solution looks pretty good. ICC estimates a 1.4x speedup, but I think that gets better with longer buffers.

I put the version with int32_t coefficients up here: https://godbolt.org/g/GXNVe2

Actually, the coefficients are only 16 bit, they are just widened before the loop. AVX2 and later are not widely supported, but there is pmuldq in SSE4.1 which is appropriate here. It takes 32 bit operands and and produces a 64 bit result. Because its result is 64 bit (as it should be by the way, because truncating to 32 bit will overflow on real-world FLAC files) it can only do two elements per operation. A few adds can be vectorised too then, but you still need a horizontal add to get the final value. I think it is possible to get a small speedup, but definitely not the 4× or 8× that you might hope for with SSE/AVX. But at this point I would say that this is a pretty advanced optimisation, not your average "vectorise all operations in the loop, increment the counter by 4/8 at a time" transformation that a compiler can do easily. I am impressed that the Intel compiler can actually vectorise things here.

zip is a function/method (depending on the language used) that transforms lists of values into A LIST of (n-)tuples of values ending IIRC when the shortest list ends.

For example: https://is.gd/hrUf7q

Reply on news.ycombinator.com