Quick Rust Improvement Ideas — Language & Std (Community Brainstorm)

41

I see hashmaps based on capture names and states. Both are external input when the regex to match on is external input. And the regex crate is designed to be safe for untrusted regexes: regex - Rust

Just like it isn't always better to avoid Arc, it isn't always better to avoid HashDOS resistent hashmaps when no untrusted data is used as keys. In many cases it is not worth the effort trying to determine if using a non-HashDOS resistent hashmap is actually safe. Also note that even ignoring untrusted data, using a non-HashDOS resistent hashmap can still cause accidental quadratic complexity on reasonable code: Exposure of HashMap iteration order allows for O(n²) blowup. · Issue #36481 · rust-lang/rust · GitHub

8 Likes
42

Saying as best (or as optimized) is kinda the problem.

You can't be best. I.e. you can only be best (or optimised) at something. There are too many axes for optimization. If you expend effort at getting better at speed chess, is the time you haven't spent practicing parkour or blindfighting on a horse.

Same with Rust. If you spend time ensuring safety by default, the trade-off is some loss of speed in benchmarks.

And honestly if you don't know enough about Rust to benchmark oranges to oranges comparison with another language, how can you be trusted to do benchmark correctly? What about memory randomisation, what about noisy environments, etc.

1 Like
43

My understanding was that it is used specifically to produce the state machine, then you are right on that one. But the rest are genuinely just processing internal states. A significant portion of real world code still follows the latter approach, and this becomes even more apparent the deeper one dives into the ecosystem

No one is suggesting avoiding HashDoS resistant hashmaps, I never said anything about changing the implementation. What I am saying is that the information should be communicated explicitly, namely through a proper warning, rather than implicitly relying on the heavier SipHash algorithm without any disclosure

44

You can still aim to be the best for the general use case, and if the implementation can detect special cases and automatically optimise for them, even better. If not, at the very least, communicate that trade off explicitly rather than silently defaulting to the heavier algorithm

So you are implying that I cannot benchmark correctly, even though I didn't post benchmark code. By all means, feel free to demonstrate that Rust's default hashmap outperforms those of C++, Go, and Zig, since you apparently have better insight into proper benchmarking methodology based on your own words

45

I just discovered something interesting ^^

The code :

Rust :

struct BigData {
    bytes: [u8; 1024 * 1024]
}

#[inline(never)]
fn return_array(val: u8) -> BigData {
    let mut data = BigData { bytes: [0u8; 1024 * 1024] };
    data.bytes.fill(val);
    data
}

#[unsafe(no_mangle)]
pub fn caller(val: u8) -> usize {
    let my_data = return_array(val);
    my_data.bytes[0] as usize
}

const BigData = struct {
    bytes: [1024 * 1024]u8,
};

noinline fn returnArray(val: u8) BigData {
    var data: BigData = undefined;
    @memset(&data.bytes, val);
    return data;
}

export fn caller(val: u8) usize {
    const my_data = returnArray(val);
    return my_data.bytes[0];
}

The Assembly :

Rust :

example[32c4274de85e6574]::return_array:
        mov     edx, 1048576
        jmp     qword ptr [rip + memset@GOTPCREL]

caller:
        mov     r11, rsp
        sub     r11, 1048576
.LBB1_1:
        sub     rsp, 4096
        mov     qword ptr [rsp], 0
        cmp     rsp, r11
        jne     .LBB1_1
        sub     rsp, 8
        mov     esi, edi
        lea     rdi, [rsp + 8]
        call    example[32c4274de85e6574]::return_array
        movzx   eax, byte ptr [rsp + 8]
        add     rsp, 1048584
        ret

Zig :

example.caller:
        push    rbp
        mov     rbp, rsp
        sub     rsp, 1048576
        mov     esi, edi
        lea     rdi, [rbp - 1048576]
        call    example.returnArray
        movzx   eax, byte ptr [rbp - 1048576]
        add     rsp, 1048576
        pop     rbp
        ret

example.returnArray:
        push    rbp
        mov     rbp, rsp
        mov     edx, 1048576
        pop     rbp
        jmp     memset@PLT

caller = example.caller

Rust does not optimise the return value, instead of performing the operation in a single pass like Zig does, Rust appears to loop through repeatedly. This would becomes increasingly slower as the data grows larger, since the loop also accumulates more iterations proportionally. It would be great if Rust could optimise this down to a single operation too if it is safe in that case, so it should be able to determine it. I have read some information suggesting that it is unsafe to do this exceeding 4KB, but is that correct?

46

What if you change it to this?

#[inline(never)]
fn return_array(val: u8) -> BigData {
    BigData { bytes: [val; 1024 * 1024] }
}

Though I guess zig has a similar syntax for that. Is your point that zig allows uninitialized without unsafe?

47

The actually equivalent Rust is something like this

#[inline(never)]
fn return_array(val: u8) -> BigData {
    unsafe {
        let mut bytes: [MaybeUninit<u8>; 1024 * 1024]> = MaybeUninit::uninit().assume_init();
        bytes.fill(val);
        BigData { bytes }
    }
}
48

That is not what I meant, in the Zig version, I was already calling memset manually. In Rust, memset happens implicitly for every array. The one I want to mention here is actually the return value mechanism. Rust performs the write in a loop every 4KB, whereas Zig writes the entire 1MB in a single pass. In theory, the single 1MB write should be faster, however, I have since found the answer, unfortunately, the OS does not permit this, as it requires the write to touch each guard page, which is typically placed at every 4KB boundary. That is likely why Rust loops at every 4KB interval. I then ran the Zig version with recursion and it crashed, then someone gives good blog posts explaining that such a stack violation does not necessarily cause an immediate crash, it may only manifest much later down the line, which I was able to reproduce and trigger through recursion

49

That's stack probing and it's a safety measure. When allocating large amount of data in one stack frame, you can have UB and security vulnerabilities as you don't hit the guard page at the end of the stack. This ensures a segfault on a stack overflow. Not all platforms support it, but on those that do Rust does it by default. Zig appears to not.

3 Likes
50

Yes, I have already noted that in my finding. Initially, my goal was to test whether Rust eliminates unnecessary memcpy calls by replacing them with direct writes into the caller's stack frame, as I had benchmarked memcpy to be roughly 2x slower than direct allocation. However, I did not find the evidence of that unoptimized memcpy, and instead stumbled upon this :rofl:

51

So you discovered that Rust protects the program from the stack smashing into the heap. Zig does not, which means that stack overflows in Zig risk arbitrary memory corruption. What's the "improvement idea" here? Remove the protection and cause memory corruption in Rust? That's not going to happen. Such huge stack frames are rare, and it's not worth making them slightly faster at the expense of everyone's safety.

6 Likes
52

I was wondering whether there was a faster way of doing the stack probe, but except for truly large stack allocations, I suspect there isn't. On at least some platforms, you can ask the OS how much stack is currently allocated and then do the calculation yourself (rather than probing); but that would involve a system call, which is probably more expensive than just touching every page in the range (especially if you're initializing every page in the range anyway).

53

Conceivably, when there's a large array being allocated on the stack and we know we're going to fill all of it immediately (to first order, any time that array's type doesn't involve MaybeUninitialized), the stack probe could be combined with the fill. This would require a memset-alike primitive that's guaranteed to touch memory in the direction of stack growth, which seems like something reasonable to ask to be added to libgcc / compiler-rt.

It would need to be carefully benchmarked, though. I could easily imagine hardware-level sequential memory access optimizations only being tuned for low-to-high addresses, which is the opposite of the stack growth direction on effectively all supported CPUs, and so the current code would be faster.. (Does LLVM even have an HPPA backend? that's the only vaguely recent "stack grows up" architecture I can think of, and "vaguely" is doing a lot of work there.)

54

That finding was something I discovered after I had already published the post, as you can see above. So it does invalidate the original post. However, Rust still crashes with the same code, and I have an updated possible new cause that it is not due to stack probing. Firstly, here is the crash

[dev@localhost src]# cargo run --release
    Finished `release` profile [optimized] target(s) in 0.12s
     Running `/dev/rust/target/release/rust`
=== Test 1: Basic call ===
caller(42) = 42
=== Test 2: Recursive (depth=200) ===
depth: 200
depth: 199
depth: 198
depth: 197
depth: 196
depth: 195
                                                      thread 'main' (11387) has overflowed its stack
fatal runtime error: stack overflow, aborting
Aborted                    cargo run --release
[dev@localhost src]#

Based on the print pattern, the crash occurs right before the 8th print, meaning it happens inside the 8th iteration of the resursive. The data size is 1 MB, and 8 × 1 = 8 MB, which looks like the usual Linux stack limit violation that occurs in any language

But there is one difference, Rust consistently crashes even in release mode. Edit : Zig also crash in release mode be it ReleaseSafe or ReleaseFast. The reason it didn't crash earlier is dead code elimination or flattening the recursive I'm not sure yet but the recursive is removed due to the value not being used and there is no side effect. After fixed it, it consistently crash segmentation fault

55

At least on Intel x86-64, if the code is performing an exact loop in the machine code (in the sense that the same sequence of machine code lines is run repeatedly), and the memory it accesses shifts by a constant offset each time, the processor will notice the pattern and optimize memory accesses under the assumption that the pattern will continue. This optimization would work just fine for predicting a backwards fill loop, for pretty much any reasonable way of writing it.

I think it's very likely that other comparable processors contain similar optimizations. so I'd expect backwards fill loops to optimize well on most desktop/laptop processors. The pattern might not hold for embedded processors, though.

56

You are confusing "consistency" with "guarantee".

57

I'm not entirely sure of the correct terminology here, but essentially I'd like to update the findings to reflect that both approaches guarantee that behavior. The Zig version uses memset, which sequentially touches all bytes, thereby triggering the guard page

58

Is there already a roadmap for eager drop in Rust? I'd like to share a proof of concept put together with the help of LLM, to demonstrate that it's feasible and can be implemented without breaking changes. All it needs is fine grained application. Here's where the demo lives GitHub - fuji-184/Rust-ASAP-Drop · GitHub

With this demonstration code :

use asap_macro::asap;

#[derive(Clone)]
struct Tracked {
    name: &'static str,
}

impl Tracked {
    fn new(name: &'static str) -> Self {
        println!("CREATE {name}");
        Tracked { name }
    }

    fn use_it(&self) {
        println!("USE    {}", self.name);
    }
}

impl Drop for Tracked {
    fn drop(&mut self) {
        println!("DROP   {}", self.name);
    }
}

fn borrow(a: &Tracked) {
    println!("BORROW early 2 is borrowed by other function, the new 2nd");
    
}

fn moved(a: Tracked) {
    println!("MOVE early 2 is moved to other function, the new 2nd");
    
}

fn main() {
    let normal = Tracked::new("variable that uses scope based drop");
    let early  = asap!(Tracked::new("variable that uses asap drop"));

    normal.use_it();
    early.use_it();

    drop(normal);

    let early  = asap!(Tracked::new("variable that uses asap drop, the new 2nd"));
    
    let cloned = early.clone();
    borrow(&cloned);
    
    borrow(&early);
    moved(early);

    let early  = asap!(Tracked::new("variable that uses asap drop, branching"));

    if 1 == 12 {
        borrow(&early);     
    } else {
        moved(early);
    }

    println!("after branching");

}

Here is the result of eager drop :

CREATE variable that uses scope based drop
CREATE variable that uses asap drop
USE    variable that uses scope based drop
USE    variable that uses asap drop
DROP   variable that uses asap drop
DROP   variable that uses scope based drop
CREATE variable that uses asap drop, the new 2nd
BORROW early 2 is borrowed by other function, the new 2nd
DROP   variable that uses asap drop, the new 2nd
BORROW early 2 is borrowed by other function, the new 2nd
MOVE early 2 is moved to other function, the new 2nd
DROP   variable that uses asap drop, the new 2nd
CREATE variable that uses asap drop, branching
MOVE early 2 is moved to other function, the new 2nd
DROP   variable that uses asap drop, branching
after branching

To see the difference, here is the output if it is scope based mode :

CREATE variable that uses scope based drop
CREATE variable that uses asap drop
USE    variable that uses scope based drop
USE    variable that uses asap drop
DROP   variable that uses scope based drop
CREATE variable that uses asap drop, the new 2nd
BORROW early 2 is borrowed by other function, the new 2nd
BORROW early 2 is borrowed by other function, the new 2nd
MOVE early 2 is moved to other function, the new 2nd
DROP   variable that uses asap drop, the new 2nd
CREATE variable that uses asap drop, branching
MOVE early 2 is moved to other function, the new 2nd
DROP   variable that uses asap drop, branching
after branching
DROP   variable that uses asap drop, the new 2nd
DROP   variable that uses asap drop

As shown, there are no stale variables. Everything is cleaned up immediately after it is no longer needed, rather than waiting until the end of the scope for execution to complete. This therefore resolves the temporary memory leak problem, as there is no memory sitting idle

59

General use case depends on the general audience. I would hazard a guess, that Rust's general audience would appreciate more safety over the fast hash.

On the plus side this could be a Clippy lint for benchmark.

I'm not implying because I wasn't aware you did any benchmarking.

As for benchmarking itself, it's extremely hard to get it right, and it most of the time it measures what people benchmarking did know about computers and languages they work on.

60

The problem could start if guard page was to be touched last.

Say, you have two threads: one wishes to delete a file from fs, and the second memsets the array and so overlaps the filename buffer... and it will be a few more milliseconds before the segfault. Is it predictable which file will be deleted? The same applies to pointer overwrite, etc.

Rust has a few places where it's technically too late to save anything (Arc::clone overflowing isize::MAX), but not as easily accessible as a stack overflow.