Reasons for speedup? [LWN.net]

Reasons for speedup?

Posted Feb 12, 2025 18:00 UTC (Wed) by jreiser (subscriber, #11027)
Parent article: Rewriting essential Linux packages in Rust

> sorting a text file containing all of Shakespeare's works ...
> the Rust version performing the test six times faster than GNU's implementation.

Why? (Algorithm strategy? Parallelism of CPU? Of I/O?) In what environment? (The same GNU code works in 16-, 32-, and 64-bit environments. 32-bit MS Windows offers only a cramped 2GiB of user address space, while the input and data structures fit easily in a minimal 64-bit machine with 4 GiB of RAM.)

to post comments

Reasons for speedup?

Posted Feb 12, 2025 19:29 UTC (Wed) by NYKevin (subscriber, #129325) [Link] (2 responses)

I have not looked at the code at all. But there's one straightforward answer that applies to nearly any rewrite-it-in-Rust project: Rust is really, really good at emitting noalias to the IR layer, whereas C is only mediocre at it (unless you liberally sprinkle the restrict keyword all over your codebase, and I suspect that a lot of C programmers have not bothered to do that). This is the same reason that FORTRAN has a reputation for outperforming C.

6x is a pretty large improvement, so I expect that they also made some substantive changes to how it works, which is probably easier in Rust-with-dependencies than it would be in C-without-dependencies. For example, Rayon provides a parallelized sorting implementation for data that fits in memory[1], whereas that would probably take tens or even hundreds of lines of C to write from scratch. Sorting a full file probably also benefits from Rayon's high-level API (par_iter() is much easier to use than pthread_create()). I don't know if they actually used Rayon, or for that matter if the GNU people did parallel sorting in their sort(1), but it's just one example of the kind of thing that is much easier in Rust-with-dependencies than in C-without-dependencies.

[1]: https://docs.rs/rayon/latest/rayon/slice/trait.ParallelSl...

Reasons for speedup?

Posted Feb 12, 2025 20:53 UTC (Wed) by roc (subscriber, #30627) [Link]

Sprinkling 'restrict' through in your C code is not even an option; it would be a disaster. Sooner or later you're going to accidentally violate the restrict constraint, the code will start misbehaving in weird ways (but only with certain optimization levels and compilers), and since no sanitizers address this feature, you'll have a nightmarish time trying to figure out the bug.

For this reason and others, the performance ceiling for single-threaded Rust code is potentially quite a bit higher than for similar C or C++ code. A lot more compiler work is needed though.

Reasons for speedup?

Posted Feb 25, 2025 20:10 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link]

> But there's one straightforward answer that applies to nearly any rewrite-it-in-Rust project: Rust is really, really good at emitting noalias to the IR layer, whereas C is only mediocre at it

Case in point: https://trifectatech.org/blog/zlib-rs-is-faster-than-c/ - zlib port into Rust is outperforming C.

Reasons for speedup?

Posted Feb 12, 2025 19:49 UTC (Wed) by excors (subscriber, #95769) [Link] (2 responses)

In my crude testing, uutils is the same speed as GNU coreutils with LANG=C, but coreutils with LANG=C.UTF-8 (the default in my environment) is several times slower.

With LANG=C.UTF-8, coreutils spends most of its time in strcoll_l, and it sorts by what I presume is some Unicode collation algorithm.

As far as I can see, uutils has no locale support. It aborts if the input is not valid UTF-8 ("sort: invalid utf-8 sequence of 1 bytes from index 0"). It simply sorts by byte values (equivalent to sorting by codepoint), regardless of LANG.

So in this case it's only faster because it doesn't implement Unicode collation.

Reasons for speedup?

Posted Feb 12, 2025 20:08 UTC (Wed) by excors (subscriber, #95769) [Link] (1 responses)

(I should probably add, in practice I never want `sort` to do Unicode collation. On systems which default to e.g. LANG=en_US.UTF-8 I find it actively annoying: it ignores capitalisation and leading whitespace, and I definitely don't want that, so I have to remember to add LANG=C to every invocation. If I wanted to do proper Unicode-aware text processing, I'd do it in a real programming language where I can configure it fully, I wouldn't do it in locale-dependent shell scripts; so I don't mind that uutils is missing that feature. On the other hand, I do sometimes want to run `sort | uniq -c | sort -n` over non-UTF-8 files (e.g. looking for common patterns in binary data), so I do mind that that isn't supported.)

Reasons for speedup?

Posted Feb 18, 2025 3:10 UTC (Tue) by ehiggs (guest, #90713) [Link]

> (I should probably add, in practice I never want `sort` to do Unicode collation. On systems which default to e.g. LANG=en_US.UTF-8 I find it actively annoying

Regardless it should do Unicode canonicalization or it will miss sort depending on how different runes are composed. This is fine for diacritic free languages like English but as soon as you get some diacritics then LANG=C's naïve handling of text breaks in my experience.