Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Rust Performance Pitfalls

llogiq.github.io

Post reply on HN
Print view View original

71–80 of 112 posts

Re: Rust Performance Pitfalls

#71

Post by pcwalton »

smitherfield wrote: post #68
pcwalton wrote: post #60

Earlier quoted context omitted.

One problem with what you propose (as I understand it) is that it's not safe to have uninitialized data in the presence of panics. A panic can cause control flow to unwind and destructors to be invoked, and if you have partially uninitialized data you have a recipe for use after free. In C++ you just get use-after-free hazards everywhere (which is one of the many reasons why exception safety in C++ is extremely hard)…

Ah, I wasn't aware that Rust reorders structure members. Although I still feel it should be possible, whether the compiler just needs to change the tag or has to shift data around. What I was proposing was that common subsequences of enum fields be treated by the compiler as synonyms, but accesses to uninitialized data would still be illegal. One way this might be implemented is by, when necessary, creating additiona…

> What I was proposing was that common subsequences of enum fields be treated by the compiler as synonyms, but accesses to uninitialized data would still be illegal. One way this might be implemented is by, when necessary, creating additional tags behind the scenes, e.g. MyEnum::__AB__ meaning A was initialized but B is the active member, so only accesses to their common subsequence are legal, MyEnum::__BA__ meaning the reverse, and so forth. Or it could be restricted to fields that contain no members outside their common subsequence with nontrivial destructors. Or the compiler could null out any uninitialized references to such.

I feel like that's too much hidden behind-the-scenes magic for a systems language, and I suspect the majority of the Rust community would feel the same way, but feel free to file an RFC.

> Interesting. Link?

https://github.com/rust-lang/rfcs/issues/349

Re: Rust Performance Pitfalls

#72

Post by burntsushi »

zigzigzag wrote: post #65
kibwen wrote: post #51

Earlier quoted context omitted.

What seems like an unfortunate design decision? I'm unclear what concerns you're seeing that would suggest UTF-16 as preferable to UTF-8, either in terms of performance or memory safety.

To not only use UTF-8 as the internal string encoding but practically mandate it, if you want to remain safe. UTF-8 is a fine transport format, but for raw runtime performance it's obviously going to be an issue if you ever need to iterate over characters, do substring matches, things like that because you can't do constant time "next char" or indexing. UTF-16 doesn't let you do that either in the presence of combini…

I feel like your comment contains a lot of misunderstanding about UTF-8. For example, UTF-8 is self-synchronizing, which means you can indeed find the "next char" in constant time.

UTF-8 is certainly not a problem for runtime performance. Substring search, for example, is as straight-forward as you might imagine. You have a needle in UTF-8 and a haystack in UTF-8, and a straight-forward application of `memmem` will work just fine (for example). In fact, UTF-8 works out great for performance , because it's very simple to apply fast routines like `memchr`. e.g., If you `memchr` for `a`, then because of UTF-8's self-synchronizing property, any and all matches for `a` actually correspond to the codepoint U+0061.

Indexing works fine so long as your indices are byte offsets at valid UTF-8 boundaries. Byte offset indexing tends to be useful for mechanical transformations on a string. For example, if you know your `substring` starts as position `i` in `mystr`, then `&mystr[i + substring.len()..]` gives you the slice of `mystr` immediately following your substring in constant time. When all your APIs deal in byte offsets, this turns out to be a perfectly natural thing to do.

Generally speaking, indexing by Unicode codepoint isn't an operation you want to do, because it tends to betray the problem you're trying to solve. For example, if you wanted to display a trimmed string to an end user by "selecting the first 9 characters," then selecting the first 9 codepoints would result in bad things in some circumstances, and it's not just limited to the presence of combining characters. For example, UTF-16 encodes codepoints outside the basic multilingual plane using surrogate pairs, where a surrogate pair consists of two surrogate codepoints that combine to form a single Unicode scalar value (i.e., a non-surrogate codepoint). So if you do the "obvious" thing with UTF-16, you'll wind up with bad results in not-exactly-corner cases.

It's worth noting that Rust isn't alone in this. Go represents strings similarly and it also works remarkably well. (The only difference between Go and Rust is that Rust's string type is guaranteed to contain valid UTF-8 where as Go's string type is conventionally UTF-8.) Notably, you won't find "character indexing" anywhere in Go's standard library or various Unicode support libraries. :-)

I would very strongly urge you to read my link in my previous comment to you. I think it would help clarify a lot of misconceptions.

Re: Rust Performance Pitfalls

#73

Post by stcredzero »

dom0 wrote: post #37
stcredzero wrote: post #15

Earlier quoted context omitted.

but that's only a comfort for the programmer's ability to reason about the code A way to mark functions as pure for this purpose would be great! Especially if it's not as fraught as const in C++.

const does not imply pure. If applied to a member function, it makes this const; if applied to types it makes types const. Purity is a different concept. The closest match would probably be constexpr.

const does not imply pure. If applied to a member function, it makes this const; if applied to types it makes types const.

You just demonstrated what I mean when I comment that const is fraught.

Purity is a different concept.

Purity more easily maps more closely to an abstract concept and is easier to for people reason about.

Re: Rust Performance Pitfalls

#74

Post by kibwen »

topspin wrote: post #39
kbenson wrote: post #38

Earlier quoted context omitted.

No, I don't believe it does. There are perfectly safe operations that must be done in unsafe, because the compiler is not smart enough to determine they are safe. Thus when describing a potential operation, saying it "requires unsafe" does not imply it can blow up in your face, just that the compiler is not smart enough to determine that at this time. This is exactly why warnings should strive to be as clear as possi…

"saying it "requires unsafe" does not imply it can blow up in your face" Good argument. If you advise someone to use unsafe the responsible thing to do is explain precisely what the consequences are besides "it's faster."

For any API that requires the `unsafe` keyword to use, improper usage of that API risks memory unsafety.

Re: Rust Performance Pitfalls

#75

Post by dbaupp »

kbenson wrote: post #67
kibwen wrote: post #64

Earlier quoted context omitted.

We must be talking past each other, because I'm still not certain what you're trying to say. If you're trying to say "there exists Rust code that contains `unsafe` blocks that is memory-safe", then this is obviously (hopefully!) correct, because 100% of the time we hope that our `unsafe` blocks are correctly implemented. In the same sense that "valid" C code does not contain undefined behavior, "valid" Rust code does…

> If you're trying to say "there exists Rust code that contains `unsafe` blocks that is memory-safe", then this is obviously (hopefully!) correct, because 100% of the time we hope that our `unsafe` blocks are correctly implemented. Yes, and additionally there are some algorithms that are safe, but to implement require unsafe blocks. I think it's obvious that there are patterns of memory access that are safe, possibly…

> Yes, and additionally there are some algorithms that are safe, but to implement require unsafe blocks.

I believe kibwen's point is that every algorithm is safe (when implemented correctly), since any memory safety violations inside `unsafe` blocks are incorrect. The keyword indicates the compiler can't guarantee that there isn't any, not that memory unsafety is okay. Maybe an example of the sort of thing you're thinking of would clarify the distinction you're drawing.

> I think it's obvious that there are patterns of memory access that are safe, possibly provably so, but not by the compiler at this time.

This is true of "everything": given any task X, a sufficiently smart language/compiler could allow expressing it without the risk of memory unsafety (i.e. no use of `unsafe`).

Re: Rust Performance Pitfalls

#76

Post by gamegoblin »

Lerc wrote: post #59

I have been doing some exploration of how well Rust optimizes Iterators and have been quite impressed. Writing a iterator to provide the individual bits supplied by an iterator of bytes means you can count them with fn count_bits >(it : I) -> i32{ let mut a=0; for i in it { if i {a+=1}; } return a; } Counting bits in an array of bytes would need something like this let p:[u8;6] = [1,2,54,2,3,6]; let result = count_bi…

How much of this is the Rust compiler and how much is generic LLVM optimization passes?

Re: Rust Performance Pitfalls

#77

Post by pcwalton »

gamegoblin wrote: post #76
Lerc wrote: post #59

I have been doing some exploration of how well Rust optimizes Iterators and have been quite impressed. Writing a iterator to provide the individual bits supplied by an iterator of bytes means you can count them with fn count_bits >(it : I) -> i32{ let mut a=0; for i in it { if i {a+=1}; } return a; } Counting bits in an array of bytes would need something like this let p:[u8;6] = [1,2,54,2,3,6]; let result = count_bi…

How much of this is the Rust compiler and how much is generic LLVM optimization passes?

It's the combination of LLVM, the Rust compiler providing enough information to LLVM, and very optimized library code. As well as plenty of testing to make sure this kind of stuff doesn't regress :)

Re: Rust Performance Pitfalls

#78

Post by mindleyhilner »

pcwalton wrote: post #43
blinkingled wrote: post #40

> for i in 0..(xs.len()) { let x = xs[i]; // do something with x } > should really be this: > for x in &xs { // do something with x } I am curious why the compiler can't rewrite the former to the latter?

Because in the former case, the optimizer has to prove that the length of the array cannot change during the body of the loop, while in the latter case, that's guaranteed by the language semantics.

Doesn't `let x = xs[i]` immutably borrow from xs? So for the duration of x's lifetime (which is the entire for-body block), xs cannot be changed and therefore its length must remain the same.

Though this might be information that rustc knows about but not LLVM.

Re: Rust Performance Pitfalls

#79

Post by kibwen »

kbenson wrote: post #67
kibwen wrote: post #64

Earlier quoted context omitted.

We must be talking past each other, because I'm still not certain what you're trying to say. If you're trying to say "there exists Rust code that contains `unsafe` blocks that is memory-safe", then this is obviously (hopefully!) correct, because 100% of the time we hope that our `unsafe` blocks are correctly implemented. In the same sense that "valid" C code does not contain undefined behavior, "valid" Rust code does…

> If you're trying to say "there exists Rust code that contains `unsafe` blocks that is memory-safe", then this is obviously (hopefully!) correct, because 100% of the time we hope that our `unsafe` blocks are correctly implemented. Yes, and additionally there are some algorithms that are safe, but to implement require unsafe blocks. I think it's obvious that there are patterns of memory access that are safe, possibly…

Even if someone that you trust is telling you to use a specific unsafe API and that "it's no less safe than when we do the same in C/C++", proper responsible usage of that API always requires reading the documentation to determine which invariants must be upheld, if only because you ought to be documenting those exact same invariants (and describing the measures that you take to uphold them) in your own code. Don't trust anyone; Rust caters to the paranoid. :P

Re: Rust Performance Pitfalls

#80

Post by shepmaster »

Lerc wrote: post #59

I have been doing some exploration of how well Rust optimizes Iterators and have been quite impressed. Writing a iterator to provide the individual bits supplied by an iterator of bytes means you can count them with fn count_bits >(it : I) -> i32{ let mut a=0; for i in it { if i {a+=1}; } return a; } Counting bits in an array of bytes would need something like this let p:[u8;6] = [1,2,54,2,3,6]; let result = count_bi…

> If this produces simiarly nice code (I haven't checked yet) I'll be very happy

You didn't specify what the type of `buffer` was, so I picked a `u8`. This code[1]:

    pub struct Thing {
        buffer: Vec,
    }
    
    impl Thing {
        pub fn copy(&mut self, data: &[u8]) {
            for (dest, &source) in self.buffer.iter_mut().zip(data) {
                *dest = source;
            }
        }
    }
Produces this assembly:

    _ZN10playground5Thing4copy17hf523bcb10e2298f3E:
    	.cfi_startproc
    	pushq	%rax
    .Ltmp0:
    	.cfi_def_cfa_offset 16
    	movq	16(%rdi), %rax
    	cmpq	%rdx, %rax
    	cmovbeq	%rax, %rdx
    	testq	%rdx, %rdx
    	je	.LBB0_2
    	movq	(%rdi), %rdi
    	callq	memcpy@PLT
    .LBB0_2:
    	popq	%rax
    	retq
The call to `memcpy` is what makes me happy.

----

Your `count_bits` already exists as a combination of iterator adapters (`filter`[2] and `count`[3]):

    a_bit_iterator.filter(|bit| bit).count()
Although if you have a numeric value, I'd suggest using `count_ones`[4], which can use the `popcnt` intrinsic.

If you wanted to count all the bits in an array, I'd suggest `map`[5] and `sum`[6]

    let p = [1u8, 2, 54, 2, 3, 6];
    let result: u32 = p.iter().map(|b| b.count_ones()).sum();
If you wanted to keep the bit iterator, you could also use `flat_map`[7].

[1]: https://play.integer32.com/?gist=03f8ffbe3ade6ced4d315c8e020...

[2]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

[3]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

[4]: https://doc.rust-lang.org/std/primitive.u8.html#method.count...

[5]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

[6]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

[7]: https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

Post reply on HN