Speed of Rust vs. C(kornel.ski) |
Speed of Rust vs. C(kornel.ski) |
A more useful comparison would be to modern C++.
Given that RCU is a complex wait-free data structure (though I don't fully understand it), I suspect it may not necessarily be possible to implement it without unsafe blocks, purely in terms of the standard library concurrency types (atomics and Arc can be used without unsafe, but themselves contain unsafe blocks). The general goal is to create an abstraction which encapsulates unsafe blocks such that it's impossible for outside users calling safe functions to violate memory safety. Of course, libraries sometimes have bugs that need to be fixed.
Even more surprising it got to front page
Do people really have low standard of quality on hacker news too?
Billions of cars with multi-billion ECUs, practically every device running an OS, and several NASA rovers disagree.
"Rust enforces thread-safety of all code and data, even in 3rd party libraries, even if authors of that code didn't pay attention to thread safety. Everything either upholds specific thread-safety guarantees, or won't be allowed to be used across threads."
If you write a library, and use e.g. thread-unsafe `Rc` or not-sure-if-safe raw pointers anywhere in your structs, the compiler will stop me from using your library in my threaded code.
This is based on a real experience. I've written a single threaded batch-processing code, and then tried to make it parallel. The compiler told me that I used a GitHub client, which used an HTTP client, which used an I/O runtime, which in this configuration stored shared state in an object without a Mutex. Rust pointed out exactly the field in 3rd party code that would cause a data race. At compile time.
It's not marketing speak.
This is as same as some one tell you that you will never loose any money by investing a certain asset.
The fact that C is used in so many places speaks for itself about it usefulness. And this is done by writing software by majority of C programmers instead of jumping on every forum to attack other languages, writing extended blog posts just to convince people that they "should" switch to the language they like.
Also if you believe bounds check is the most difficult thing in software development, it just mean that you haven't dealt with a sufficient system yet or you just pretends to be.
The similar thing also applied to that if you think naively putting pthread_mutex_lock and unlock around the data structure is hard, it just means you haven't touched the scenarios that C programmers resorts to non-trivial locking mechanisms for.
As the article mentions, C is 50 years old. The fact that it's still used is evidence of its usefulness, sure. It has outlasted almost all of its peers.
Rust has been stable for under 6 years. In that time, it's been adopted by a slew of major companies, and people have used their free time to write some extremely good software in it. So by that metric, Rust's usefulness speaks for itself, too.
- Regardless it is true or not, this seldom works in long term. I just simply point this observation out.
In fact language as tool is never about more features, it is about minimum features for maximize utilities, and Rust is already on the domain of "feature-rich" language.
I didn't read it, because it might present outdated knowledge.
No, it does not. If Rust programmers don't have discipline in C, other people have.
And don't drag out some random CVE numbers again. These are about a fraction of existing C projects, many of them were started 1980-2000.
It is an entirely different story if a project is started with sanitizers, Valgrind and best practices.
I'm not against Rust, except that they managed to take OCaml syntax and make it significantly worse. It's just ugly and looks like design by committee.
But the evangelism is exhausting. I also wonder why corporations are pushing Rust. Is it another method to take over C projects that they haven't assimilated yet?
All benchmarks should be delivered in the form of a graph and histogram, I had to close a PR recently where the "optimization" was 1% of a standard deviation away from the mean without even running either implementation!
I don't think it's ugly because it's design-by-committee, I think they intentionally made it ugly so that it's familiar to C++ people.
> I also wonder why corporations are pushing Rust.
You said it yourself: undisciplined people can't write C without introducing memory-related bugs, and it's much easier to hire undisciplined people than disciplined people.
> It is an entirely different story if a project is started with sanitizers, Valgrind and best practices.
Do you have an example of a project that is (a) built in such a way, (b) large, and (c) has a good track record on memory safety?
Some people are hard learners.
My best guess is that people who are "stuck" working in C or C++ wish they could use Rust at their Jobs.
Or that others would make the leap and get over the learning curve.
For anything else managed languages are a much more productive option, other than writing kernel and drivers.
And TBH I rarely see other popular language did the similar things either, including very popular ones like python, Java or Go.
And you even observe there is thing called "C evangelism" actually exists?
I want to be able to write code without having to be "disciplined" about how I access memory. Means I can be more "disciplined" about business logic.
What are the agreed upon tools and best practices in the C community as of right now?
Recruiting.
They don't call it C-lioning for nothing :^)
For rust this is certainly the case, demonstrated by this thread and almost any other thread about rust, it is . TBH it is a pattern to see title "fastest xxx written in rust".
C programmers do not have the tradition to ASK other people to write something in C, they WRITE something in C. That's the real difference here.
What you cannot easily do in Rust is dynamically switch thread safety on or off.
Like, do you have a specific objection to the way Rust accomplishes this?
There are also a lot of people who do not use C or C++, but use a bit of rust because it's so much easier to write fast little tools with it. I'm in this category. I even use threads sometimes, and it's reasonably easy. A crop of new unixy tools in rust seems to indicate other people also think alike.
Liking a programing language doesn't make me blind to what use cases it actually makes sense to use it, I don't see nails everywhere.
I think you'll find that most rational advocates for any language agree that their favorite language is only strong in its subdomain.
Any compiled language is more painful than a quick scripting one for quick projects where the project complexity is low and the language overhead doesn't matter.
Rust is substantially more painful to get compiling (due to the borrow checker) and harder to debug (due to tool maturity) than C# or C++. It's much harder to use than Python. Every language has its place.
But when you are investing the time to make an efficient, high performance program... or you have limited requirements like you said -- Rust becomes a great choice.
Every langauge has its place. I'm just dreadfully excited that we have a new choice now to trade a bit more time interacting with compiler errors for high performance and stability -- when that makes sense.
Command-line tools are also ideal for Rust because startup performance matters a lot there.
What was done in C, C++ and Tcl, I nowadays use Java and .NET languages.
If we really need something low level that either Java or .NET cannot offer, a native library for a specific component will do, no need to throw the whole thing away and do one of those rewrite blog posts.
Idiomatic Rust avoids the situations which require JVM tuning experts. You can write a Rust service, put it into production and tail latency is very likely not going to be a problem at all.
Now you may decide that needing the occasional services of a JVM tuning expert is better overall than ownership concerns being pervasive throughout a codebase, depending on the specifics. But do accept that the trade-off exists.
You are the one focusing in Java, and in your answer proved exactly my point of knowing stacks superficially.
Object pools aren't the only way to reduce memory footprint in Java.
A bit of FFI into host OS syscalls and it is done, or a tiny high performance native library for a custom data structures and ready for the races.
No need to throw away 25 years of tooling and libraries.
Then we can move into languages that offer exactly the same features as C++, like D, Nim, Swift, Eiffel, Ada.
Yes. Today, I integrated two parts of a 3D graphics program. One refreshes the screen and lets you move the viewpoint around. The other loads new objects into the scene. Until today, all the objects were loaded, then the graphics window went live. Today, I made those operations run in parallel, so the window comes up with just the sky and ground, and over the next few seconds, the scene loads, visibly, without reducing the frame rate.
This took about 10 lines of code changes in Rust. It worked the first time it compiled.
How did you do that in Rust? Doesnt one of those have to own the scene at a time? Or is there a way to make that exclusive ownership more granular?
I'm using Rend3, which is a 3D graphics library for Rust that uses Vulkan underneath. Rend3 takes care of memory allocation in the GPU, which Vulkan leaves to the caller, and it handles all the GPU communication. The Rend3 user has to create all the vertex buffers, normal buffers, texture maps, etc., and send them to Rend3 to be sent to the GPU. It's a light, safe abstraction over Vulkan.
This is where Rust's move semantics ownership transfer helps. The thread that's creating object to be displayed makes up the big vertex buffers, etc., and then asks Rend3 to turn them into a "mesh object", "texture object", or "material object". That involves some locking in Rend3, mostly around GPU memory allocation. Then, the loader puts them together into an "object", and tells Rend3 to add it to the display list. This puts it on a work queue. At the beginning of the next frame, the render loop reads the work queue, adds and deletes items from the display list, and resumes drawing the scene.
Locking is brief, just the microseconds needed for adding things to lists. The big objects are handed off across threads, not recopied. Adding objects does not slow down the frame rate. That's the trouble with the existing system. Redraw and new object processing were done in the same thread, and incoming updates stole time from the redraw cycle.
If this was in C++, I'd be spending half my time in the debugger. In Rust, I haven't needed a debugger. My own code is 100% safe Rust.
The Arc is an async reference counter that allows multiple ownership. And the nested Mutex enforces only one mutable borrow at a time.
Rust "works badly with memory mapped files" doesn't mean, "Rust can't use memory mapped files." It means, "it is difficult to reconcile Rust's safety story with memory maps." ripgrep for example uses memory maps because they are faster sometimes, and its safety contract[3] is a bit strained. But it works.
[1] - https://github.com/BurntSushi/fst/
[2] - https://github.com/BurntSushi/imdb-rename
[3] - https://docs.rs/grep-searcher/0.1.7/grep_searcher/struct.Mma...
You can mmap files in Rust just fine, but it’s generally as dangerous as it is in C.
These issues about multiple processes and distributed systems are framework and OS level concerns. Rust helps you build fast concurrent solutions to those problems, but you’re correct that it can not solve problems exterior to the application runtime. How is that a deficiency with Rust?
The most important design decision while writing a parallel algorithm is to decide for what amount of data is not worth it.
I don't get the obsession of parallel code in low level languages by the way. If you have an architecture where you can afford real parallelism you can afford higher level languages anyway.
In embedded applications you don't usually have the possibility to have parallel code, and even in low level software (for example the classical UNIX utilities), for simplicity and solidity using a single thread is really fine.
Threads also are not really as portable as they seem, different operating systems have different way to manage threads, or even don't supports thread at all.
This isn't an "obsession." It's engineering.
[1] - I make this claim loosely. Absence of evidence isn't evidence of absence and all that. But if I saw ripgrep implemented in, say, Python and it matched speed in the majority of cases, I would learn something.
Depends on which of the classic utilities you are talking about.
Many of them are typically IO bound. You might not get much out of throwing more CPU at them.
The primary reason c libraries do this is not for safety, but to maintain ABI compatibility. Rust eschews dynamic linking, which is why it doesn't bother. Common lisp, for instance, does the same thing as c, for similar reasons: the layout of structures may change, and existing code in the image has to be able to deal with it.
> Rust by default can inline functions from the standard library, dependencies, and other compilation units. In C I'm sometimes reluctant to split files or use libraries, because it affects inlining
This is again because c is conventionally dynamically linked, and rust statically linked. If you use LTO, cross-module inlining will happen.
This made me laugh
Heartbleed wasn't caused by reusing buffers; it was caused by not properly sanitizing the length of the buffer from entrusted input, and reading over it's allocated size, thus allowing the attacker to read into memory that wasn't meant for him.
... In rust I'd just declare an enum for this. Enums in Rust can store data. In this way they are like a safe union.
The issue with this is that 'clever' compilers can optimise out any memset calls you do.
I did a deep dive into this topic lately when exploring whether to add a language feature to zig for this purpose. I found that, although finnicky, LLVM is able to generate the desired machine code if you give it a simple enough while loop continue expression[1]. So I think it's reasonable to not have a computed goto language feature.
More details here, with lots of fun godbolt links: https://github.com/ziglang/zig/issues/8220
This reminds me of when I use to write supercomputing codes. Lots of programming language nerds would wonder why we didn’t use functional models to simplify concurrency and parallelism. Our code was typically old school C++ (FORTRAN was already falling out of use). The truth was that 1) the software architecture was explicitly single-threaded — some of the first modern thread-per-core designs — to maximize performance, obviating any concerns about mutability and concurrency and 2) the primary performance bottlenecks tended to be memory bandwidth, of which functional programming paradigms tend to be relatively wasteful compared to something like C++. Consequently, C++ was actually simpler and higher performance for massively parallel computation, counterintuitively.
Looks like you're compiling C code with -O2. Does Rust build set -O3 on clang? Did you try -O3 with C? I know it's not guaranteed to be faster, just curious.
https://doc.rust-lang.org/cargo/reference/profiles.html#rele...
>"Clever" memory use is frowned upon in Rust. In C, anything goes. For example, in C I'd be tempted to reuse a buffer allocated for one purpose for another purpose later (a technique known as HEARTBLEED).
Ha!
>It's convenient to have fixed-size buffers for variable-size data (e.g. PATH_MAX) to avoid (re)allocation of growing buffers. Idiomatic Rust still gives a lot control over memory allocation, and can do basics like memory pools, combining multiple allocations into one, preallocating space, etc., but in general it steers users towards "boring" use or memory.
Since I write a lot of memory-constrained embedded code this actually annoyed me a bit with Rust, but then I discovered the smallvec crate: https://docs.rs/smallvec/1.5.0/smallvec/
Basically with it you can give your vectors a static (not on the heap) size, and it will automatically reallocate on the heap if it grows beyond that bound. It's the best of both world in my opinion: it lets you remove a whole lot of small useless allocs but you still have all the convenience and API of a normal Vec. It might also help slightly with performance by removing useless indirections.
Unfortunately this doesn't help with Strings since they're a distinct type. There is a smallstring crate which uses the same optimization technique but it hasn't been updated in 4 years so I haven't dared use it.
The good thing about having a decent type system is that I expect that transitioning to smartstrings should be painless! Thank you for that.
There is this habit in both academia and industry where people say "as fast as C" and justify this by comparing to a tremendously slow C program, but don't even know they are doing it. It's the blind leading the blind.
The question you should be asking yourself is, "If all these claims I keep seeing about X being as fast as Y are true, then why does software keep getting slower over time?"
(If you don't get what I am saying here, it might help to know that performance programmers consider malloc to be tremendously slow and don't use it except at startup or in cases when it is amortized by a factor of 1000 or more).
Compared to all the religious texts I've read about Rust, this is a huge breath of fresh air.
Thanks for sharing! Bookmarking this.
No, it's not, especially if you have multiple binaries. There are hacks, like using a multi-call single binary, (forget about file-based privilege separation), or using an unmaintained fork of cargo to build a rust toolchain capable of dynamic linking libstd. See: https://users.rust-lang.org/t/link-the-rust-standard-library... and https://github.com/johnthagen/min-sized-rust
I'd be interested in any up-to-date trick to do better than this.
https://github.com/antoyo/rustc_codegen_gcc https://github.com/Rust-GCC/gccrs https://github.com/sapir/gcc-rust/
I remember making an argument on a mailing list against using alloca on the grounds that there's usually a stack-blowing bug hiding behind it. As I revisited the few examples I remembered of it being used correctly, I strengthened my argument by finding more stack-blowing bugs hiding behind uses of alloca.
When I ran my simple fuzz test in rust it seg faulted, crashing in 'safe' code. I thought for a moment there might be something wrong with the compiler (hahaha no). Sure enough, there was a bug in one of my far-too-clever unsafe blocks that was corrupting memory. Then that was in turn causing a crash later in the program's execution.
That was one of my first big "aha" moments for rust - in rust because segfaults (should be) impossible in safe code, I only needed to study the code in my ~30 lines of unsafe code to find the bug. (Compared to 150+ lines of regular code). I had some similar bugs when I wrote the C version earlier, and they took all day to track down because in C memory corruption can come from anywhere.
I don't tend to think of Rust as "portable assembly", and this is indeed one of the points where I think it differs the most from C. I think of "portable assembly" as being applicable to C, because it is some version of a "minimal" level of abstraction for a high-level language. Rust is very much a tool for abstraction, and one of the USPs of rust is that the compiler abstracts away the low-level details of memory management in a way which is not as costly as other automatic memory management strategies.
Maybe it's due to lack of experience, but with C code it's fairly easy to look at a block of code and imagine approximately which assembly would be generated. With highly abstract Rust code, like with template-heavy C++ code, I don't feel like that at all.
Rust does not abstract away memory management. For example, it never heap allocates anything implicitly. It inserts destructors, but does so predictably at end of scopes, in a specified order.
Rust heavily uses iterators with closures, but these get aggressively inlined, and you can rely on them optimizing down to a basic loop. For code generation they're not too different from a fancy C macro.
And if in doubt, there's https://rust.godbolt.org/ (don't forget to add -O to flags)
The fact that Rust specialises its generic code according to the type it's used with it not some inherent disadvantage of generics. That's what they're supposed to do. By choosing to not specialise, you're actively making the decision to make your code slower. Rust has mechanisms for avoiding generic specialisation. They're called trait objects and they work brilliantly.
When you use void* in your data structures in C, you're not winning anything when compared to Rust. You're just producing slower code that mimics the behaviour of Rust's trait objects, but more dangerously.
Code 'bloat' (otherwise known as 'specialising your code correctly to make it run faster') is not a reason to not use Rust in 2021, so please stop pretending that it is.
> Rust has mechanisms for avoiding generic specialisation. They're called trait objects and they work brilliantly.
As someone who uses a lot of rust, they are sort of the red-headed stepchild. As a minimum to make the properly usable, we need a way of passing one object with multiple different traits.
What do you mean?
fn foo<T: TraitA + TraitB>(x: T) { T.something(); }Supertraits?
You can do that in Java (with byte arrays) or in Common Lisp, so what is the point here? It is not practice in Java, Lisp nor in C and C++.
> It's convenient to have fixed-size buffers for variable-size data (e.g. PATH_MAX) to avoid (re)allocation of growing buffers
This is because OS/Kernel/filesystem guarantee path max size.
> Idiomatic Rust still gives a lot control over memory allocation, and can do basics like memory pools, ... but in general it steers users towards "boring" use or memory.
The same is done by sane C libraries (e.g. glib).
> Every operating system ships some built-in standard C library that is ~30MB of code that C executables get for "free", e.g. a "Hello World" C executable can't actually print anything, it only calls the printf shipped with the OS.
printf is not shipped with the OS, but with libc runtime. It doesn't have to be runtime (author needs to learn why this libc runtime is shared library and not the usually statically linked library) and you can use minimal implementations (musl) if you want static binaries with minimal size.
So you are saying Rust doesn't call (g)libc at all and directly invoke kernel interrupts? Sure, you can avoid this print "overhead" in C with 3-4 lines of inline assembly, but, why?
> Rust by default can inline functions from the standard library, dependencies, and other compilation units.
So do C compiler.
> In C I'm sometimes reluctant to split files or use libraries, because it affects inlining and requires micromanagement of headers and symbol visibility.
Functions doesn't have to be in headers to be inlined.
> C libraries typically return opaque pointers to their data structures, to hide implementation details and ensure there's only one copy of each instance of the struct. This costs heap allocations and pointer indirections. Rust's built-in privacy, unique ownership rules, and coding conventions let libraries expose their objects by value, so that library users decide whether to put them on the heap or on the stack. Objects on the stack can can be optimized very aggressively, and even optimized out entirely.
WTF? Stopped reading after this.
I find this post a random nonsense and I'd urge author to read some serious C book.
Non-checked malloc returns - ouch, I count 12 (out of 56) without a check. Thanks for pointing this out.
Which is why so many people are creating formal verification languages and spending years in research to fix those ... That just isn't true. It's a very complex problem that is an issue in both hardware (cache-coherency protocols) to OS (atomics locks) to higher level construct (commit-rollback in databases).
Consequently
> But the biggest potential is in ability to fearlessly parallelize majority of Rust code, even when the equivalent C code would be too risky to parallelize. In this aspect Rust is a much more mature language than C.
This couldn't be more wrong either. Rust doesn't help you write synchronization primitives safely because it doesn't handle synchronization like locks, condition variables or atomics. You need formal verification to be fearless.
Memory safety is just a small part and is a much easier problem than ensuring the absence of race conditions.
If it was that simple, Tokio wouldn't need to formally verify their implementation with an external tool and it wouldn't have found dozens of well hidden bugs.
C programming patterns have more-or-less equivalents in Rust. OTOH non-trivial C++ OOP or template usage is alien and hard to adapt to Rust.
Rust has 1 (one) way to initialize an object. No constructors, initializer lists, or rules-of-<insert number>. Move semantics are built-in, without move/copy constructors/NRVO/moved-out-of state. No inheritance. No object truncation. Methods are regular function pointers. No SFINAE (generics are equivalent to concepts, and dumber, e.g. no variadic). Iterators require only implementing a single method. Operator overloading is all done in the style of the spaceship operator.
It's not the same kind of complexity.
For fuck's sake.
Maximum speeds are already explored. I wanted to discuss an aspect that's not typically covered by pure benchmarks: what can you expect from normal day-to-day use of these languages. Not fine-tuned hot loops, but a "median" you can expect when you just need to get shit done.
If I tried to write a benchmark code to represent average, practical, idiomatic, but less-than-maximally optimized code, I don't think anyone would believe me that's a fair comparison. So I describe problems and patterns instead, and leave it to readers to judge how much applies to their problems and programming style.
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
Also sub-maximum speeds — start at the bottom of the measurements and work up from the 5.37s g++ program to the 0.72s g++ program :-)
https://benchmarksgame-team.pages.debian.net/benchmarksgame/...
My experience using Rust vs C aligns with yours as well.
Pahaha
am I a minority having this opinion?
The people implementing the libraries you use (e.g. Rayon) may have to use TSAN, of course.
Rust provides ABI compatibility against its C ABI, and if you want you can dynamically link against that. What Rust eschews is the insane fragile ABI compatibility of C++, which is a huge pain to deal with as a user:
https://community.kde.org/Policies/Binary_Compatibility_Issu...
I don't think we'll ever see as comprehensive an ABI out of Rust as we get out of C++, because exposing that much incidental complexity is a bad idea. Maybe we'll get some incremental improvements over time. Or maybe C ABIs are the sweet spot.
However, as the parent comment you responded to you can enable LTO when compiling C. As rust is mostly always statically linked it basically always got LTO optimizations.
If you have an API that allows the caller to instantiate a structure on the stack and pass a reference to it to your function, then the caller must now be recompiled when the size of that structure changes. If that API now resides in a separate dynamic library, then changing the size of the structure is an ABI-breaking change, regardless of the language.
If instead you’re referring to the fact that all the fields of a struct aren’t explicitly obvious when you have such a value, well I don’t really agree that it’s always what you want. A great thing about pattern matching with exhaustiveness checks is that it forces you to acknowledge that you don’t care about new record fields (though the Common Lisp way of dealing with this probably involves CLOS instead).
[1] some implementations may use NaN-boxing to get around this
Heap allocations, yes; pointer indirections no.
A structure is referenced by pointer no matter what. Remember that the stack is accessed via a stack pointer.
The performance cost is that there are no inline functions for a truly opaque type; everything goes through a function call. Indirect access through functions is the cost, which is worse than a mere pointer indirection.
An API has to be well-designed this regard; it has to anticipate the likely use cases that are going to be performance critical and avoid perpetrating a design in which the application has to make millions of API calls in an inner loop. Opaqueness is more abstract and so it puts designers on their toes to create good abstractions instead of "oh, the user has all the access to everything, so they have all the rope they need".
Opaque structures don't have to cost heap allocations either. An API can provide a way to ask "what is the size of this opaque type" and the client can then provide the memory, e.g. by using alloca on the stack. This is still future-proof against changes in the size, compared to a compile-time size taken from a "sizeof struct" in some header file. Another alternative is to have some worst-case size represented as a type. An example of this is the POSIX struct sockaddr_storage in the sockets API. Though the individual sockaddrs are not opaque, the concept of providing a non-opaque worst-case storage type for an opaque object would work fine.
There can be half-opaque types: part of the structure can be declared (e.g. via some struct type that is documened as "do not use in application code"). Inline functions use that for direct access to some common fields.
Sure, there are libraries which have `init(&struct, sizeof(struct))`. This adds extra ABI fragility, and doesn't hide fields unless the lib maintains two versions of a struct. Some libraries that started with such ABI end up adding extra fields behind internal indirection instead of breaking the ABI. This is of course all solvable, and there's no hard limit for C there. But different concerns nudge users towards different solutions. Rust doesn't have a stable ABI, so the laziest good way is to return by value and hope the constructor gets inlined. In C the solution that is both accepted as a decent practice and also the laziest is to return malloced opaque struct.
I'd like to point out that this is not always the case. Some libraries, especially those with embedded systems in mind, allow you to provide your own memory buffer (which might live on the stack), where the object should be constructed. Others allow you to pass your own allocator.
> C++, D, and Go have throw/catch exceptions, so foo() might throw an exception, and prevent bar() from being called. (Of course, even in Zig foo() could deadlock and prevent bar() from being called, but that can happen in any Turing-complete language.)
Well, you could bite the bullet and carefully make Zig non-Turing complete. (Or at least put Turing-completeness behind an escape hatch marked 'unsafe'.)
That's how Idris and Agda etc do it.
Languages like Idris and Agda are different because sometimes code isn’t executed at all. A proof may depend on knowing that some code will terminate without running it.
As you said though, this is finicky, and if you need this optimization for performance then you don’t want to rely on compiler heuristics.
However, in this specific instance at least, this isn't as optimal as it could be. What this is basically doing is creating a jump table to find out which branch it should go down. But, because all the functions have the same signature, and each branch does the same thing, what it could have done instead is create a jump table for the function to call. At that point, all it would need to do is use the Inst's discriminant to index into the jump table.
I'm not sure what it would look like in Zig, but it's not that hard to get that from Rust[1]. The drawback of doing it this way is that it now comes with the maintenance overhead of ensuring the order and length of the jump table exactly matches the enum, otherwise you get the wrong function being called, or an out-of-bounds panic. You also need to explicitly handle the End variant anyway because the called function can't return for its parent.
I don't know Zig, but from what I understand it has some pretty nice code generation, so maybe that could help with keeping the array and enum in step here?
My experience with process-based parallelism is that yes on Linux it's basically isomorphic to thread-based parallelism. It's just so much more code to do the same thing.
In Rust adding a new special-purpose background thread with some standard-library channels is 30 lines of code and I can probably even access the same logging system from the other thread.
If I wanted to do that with processes I need to:
- Coordinate a shared memory file over command line arguments or make sure everything is fork-safe
- Find a library for shared-memory queues
- Deal with making sure that if either process crashes the other process goes down with it in a reasonable way.
- Make sure all my monitoring/logging is also hooked up to the other process.
If I want to use a shared memory data-structure with atomics I need to either not use pointers or live dangerously and try and memory-map it at the exact same offsets in each process and ensure I use a special allocator for things in the shared file.
Yes you can do all the same things with both approaches, I just find threads take way less code. It's not too bad if all your processes are doing the same thing, and you also need to scale to many servers anyhow. It's more annoying if you want to have a bunch of different types of special background processes.
I think what's nice about rust is that, because it makes it difficult to write thread-unsafe code, it's naturally easier to add threading at some point in the future without too much pain. As a result, more applications can benefit from having access to multiple CPU cores. I don't think that's quite the same thing as pure performance per watt, though. That really comes down to how the code was written, and how well the compiler can optimize it. Rust may have some advantages there over C, since it constrains what you can do so much that the compiler has a smaller state space to optimize over. Someone who knows what they're doing in C, though, could likely write very efficient code that effectively uses parallelism, and may gain an edge over rust simply by cleverly leveraging the relative lack of training wheels. For high performance compute, rust vs. C may be a wash. For consumer facing applications, though, the more programs that can use multiple cores to run faster (even if less efficiently), the better.
Do you happen to have a link to code that does this? This sounds similar to a problem I have right now and I’d love to see what solution you’ve arrived at.
Not my experience at all. One big problem is that most languages in 2021 have very, very poor support for thread-based parallelism. It’s crazy how many languages make it hard to do basic data parallel tasks. That steers people toward writing single threaded code and/or trying to rely on process-based parallelism which is basically strictly worse.
I’ve been writing parallel code at the largest scales most of my career. The state-of-the-art architectures are all, effectively, single-threaded with latency-hiding. This model has a lot of mechanical sympathy with real silicon which is why it is used. It is also pleasantly simple in practice.
Unfortunately, that is only a certain subsection of problems and usually you want to be able to use parallel computations on the function call level. There the support for parallel computations of Rust or Go shines. When at each point in the program flow you can decide to go parallel.
Why is that worse?
I very seldomly use threads for concurrency, it creates monolithic binaries that are hard to maintain, configure, and understand.
I much prefer a process based architecture with mmap'd shared memories for interprocess communications.
Heavily multi threaded code is difficult to write correctly. Do it wrong, you wind up with race conditions, data corruption, dead locks because a thread pool or other resource is exhausted, thread leaks because you didn't shut something down correctly. The problems go on and on.
For example I consider glyph drawing as "performance optimized". It requires massive parallelism just to be able to display text smoothly in a high definition screen.
But most people will never see it, because they use a library that they call that does all the work for them and do not need to care about that.
The difference is tremendous. We are talking 100x more efficiency just using GPUs alone. You can get 1000x, 10.000x with hardware(electronic chip design) acceleration parallelism(increasing the cost and rigidity, and times to market too).
It is so big that it is a different level. It is not performance alone. It is that some things are so inefficient that are just not practical(like expending a million dollars in your energy bill in order to solve a problem).
Same happens with of course 3D, audio or video recognition. Sensor I/O. Artificial intelligence.
Rust lets you just prototype lots of code in a parallel way in the CPU, even for things that will run in a FPGA or ASIC in the future. It let's you transition smaller steps: CPU->GPU->FPGA->ASIC
Why?
Edit: Thanks for all the replies. It seems this applies to data-parallel workloads only. I'd use a GPU for this. An RTX 3090 has around ~10000 CUDA cores (10000 simultaneous operations) v/s just ~10 for CPUs.
This creates a new problem: how do you balance load across cores? What if the workload is not evenly distributed across the data held by each core? Real workloads are like this! Fortunately, over the last decade, architectures and techniques for dynamic cross-core load shedding have become smooth and efficient while introducing negligible additional inter-core coordination. At this point, it is a mature way of designing extremely high throughput software.
Functional programming (especially, say, actor systems) is better for organizing mental models of concurrency when your concurrency is coupled with communication between the components. For hpc, you're typically optimizing for gustafson scaling (versus amdhal scaling) where you are running multiple copies of the same, computationally costly linearly organized code with no coupling between instances except statistical aggregation of results, so there is no particular benefit to functional-style concurrency.
(And some FPLs,like Julia, are perfectly good at hpc anyways)
The codes I worked on were complex graph analysis, spatiotemporal behavioral analysis, a bit of geospatial environmental modeling, and in prehistoric times thermal and mass transport modeling. These codes (pretty much anything involving reality) are intrinsically tightly coupled across compute nodes. Low-latency interconnects eventually gave way to latency-hiding software architectures but at no point did we use map-reduce as that would have been insanely inefficient given the sparsity and unpredictability of the interactions between nodes.
These were the prototype software architectures for later high-performance databases. Every core is handling thousands or millions of independent shards of the larger computational model, which makes latency-hiding particularly efficient.
It is about how easily a programmer, who deals with a certain subtask in a system, can utilize more cores for the this task. Not talking about supercomputing, but looking at a smarktphone or a typical PC. There you usually have most cores just idle unused, but if the user triggers an action, you want to be able to use as many cores as it speeds up computation. Language support for parallelism makes a huge difference there. In Go I can write a function to do a certain computation and quite often it is trivial to spread several calls across goroutines.
It's one of the secrets exploited by the M1 chip, seen in how many more cache lines the CPU's LFB can fill concurrently compared to Intel chips and that these are now 128 byte cache lines instead of 64 byte cache lines.
I do not accept this premise. Things are increasingly multithreaded.
I wouldn't call that a first approximation. Take ripgrep as an example. In a checkout of the Linux kernel with everything in my page cache:
$ time rg zqzqzqzq -j1
real 0.609
user 0.315
sys 0.286
maxmem 7 MB
faults 0
$ time rg zqzqzqzq -j8
real 0.116
user 0.381
sys 0.464
maxmem 9 MB
faults 0
Using Rust made it a lot easier to parallelize ripgrep.
> C allows you to do bulk memory operations, Rust does not (unless you turn off the things about Rust that everyone says are good). Thus C is tremendously faster.
Talk about nonsense. I do bulk memory operations in Rust all the time. Amortizing allocation is exceptionally common in Rust. And it doesn't turn off anything. It's used in ripgrep in several places.
> There is this habit in both academia and industry where people say "as fast as C" and justify this by comparing to a tremendously slow C program, but don't even know they are doing it. It's the blind leading the blind.
I've never heard anyone refer to GNU grep as a "tremendously slow C program."
> The question you should be asking yourself is, "If all these claims I keep seeing about X being as fast as Y are true, then why does software keep getting slower over time?"
There are many possible answers to this. The question itself is so general that I don't know how to glean much, if anything, useful from it.
You chose an embarrassingly parallel problem, which most programs are not. So you cannot generalize this example across most software. When you try to parallelize a structurally complicated algorithm, the biggest issue is contention. I was leaving this out because it really is a 2nd order problem -- most software today would get faster if you just cleaned up its memory usage, than if you just tried to parallelize it. (Of course it'd get even faster if you did both, but memory is the E1).
> There are many possible answers to this.
How come so few people are concerned with the answers to that question and which are true, but so many people are concerned with making performance claims?
As I've pointed out in the article, Rust does give you precise control over memory layout. Heap allocations are explicit and optional. In safe code. You don't even need to avoid any nice features (e.g. closures and iterators can be entirely on stack, no allocations needed).
Move semantics enables `memcpy`ing objects anywhere, so they don't have a permanent address, and don't need to be allocated individually.
In this regard Rust is different from e.g. Swift and Go, which claim to have C-like speed, but will autobox objects for you.
Rust is now getting support for custom local allocators ala C++, including in default core types like Box<>, Vec<> and HashMap<>. It's an unstable feature, hence not yet part of stable Rust but it's absolutely being worked on.
> > For example, in C I'd be tempted to reuse a buffer allocated for one purpose for another purpose later (a technique known as HEARTBLEED).
> You can do that in Java (with byte arrays) or in Common Lisp, so what is the point here? It is not practice in Java, Lisp nor in C and C++.
C is a really old language with ancient libraries that are still widely used even though they are simply bad by modern standards. For that reason, I roll my eyes when people say something is not practice in C or talk about "sane" C libraries. A big part of working with C is dealing with ancient insanity.
You can make much stronger statements about what is idiomatic in Rust (and to some extent Java) simply because it's newer and more cohesive.
> > It's convenient to have fixed-size buffers for variable-size data (e.g. PATH_MAX) to avoid (re)allocation of growing buffers
> This is because OS/Kernel/filesystem guarantee path max size.
I think you've got that backwards. There's an advertised max path size because people wanted to stick paths in fixed-size buffers rather than deal with dynamic allocation. PATH_MAX is fairly arbitrary considering that there are certainly ways of creating and opening files which have paths exceeding that limit. I found this doc talking about this: https://eklitzke.org/path-max-is-tricky
> printf is not shipped with the OS, but with libc runtime.
"The OS" doesn't mean "the kernel". Read...anything...even the lackluster wikipedia article about operating systems...and you'll see stuff like GUIs described as part of the OS. They (generally) don't mean those are in the kernel. You can also see this for example in the GNU GPL; they call out "system libraries", which certainly includes libc.
> So you are saying Rust doesn't call (g)libc at all and directly invoke kernel interrupts? Sure, you can avoid this print "overhead" in C with 3-4 lines of inline assembly, but, why?
Rust's own standard library uses libc's system call wrappers but not stdio. It has its own libraries for buffer management and formatting which provide the safety one would expect of Rust, know how to integrate with Rust's Display trait for formatting arbitrary Rust data structures, etc. You could call libc::printf yourself if you wanted to, but that's not idiomatic. I wrote some Rust code calling libc::vsnprintf just the other day, because I got a format string + va_list from C in a log callback.
"Expert C Programming" [1]. Not up to date, but written from a C compiler writer standpoint. A lot of references to why C (and libs) are the way they are.
[1] https://www.amazon.com/Expert-Programming-Peter-van-Linden/d...
To make static analysis robust in C you need to start reliably tracking ownership and forbid type-erasing constructs. This typically means adding smart pointers, some kind of borrow checking or garbage collection, generics to replace void*, maybe tagged unions, and a new standard library that embraces these features.
It's going to bring most of Rust's complexity and require major code changes anyway, but you won't even get benefits of a newer language.
C++, OTOH, you could probably port most of Rust's concepts into (with some extra language changes for various reasons I don't want to get into). However, since almost no existing C++ code would typecheck in the "safe" subset without modifications, it would effectively be a different language anyway. And to be clear, this isn't necessarily because people are routinely doing dangerous stuff in C++ -- the whole Rust ecosystem has grown up around the borrow checker, which means some very basic things people use in most other languages aren't done. Here are some examples of things typical Rust code does differently from typical C++ code due to it making it much harder to perform safety checks, beyond the obvious aspect of lifetime annotations and genuinely unsafe patterns like accessing globals (sorry, it just is):
* far less use of accessors, especially mutable ones (because Rust can't track split field ownership)
* Rust tends to split up big "shared context" structures depending on function use, rather than logical relationships, for much the same reason (Rust conservatively assumes that all fields are used when a context object gets passed to a function as long as any pointer to the structure remains, even if the fields you use aren't being accessed).
* Rust almost never uses internal or cyclic pointers. It's safe to do it with boxed data or data that doesn't move, and there are safe type mechanisms around that, but it's cumbersome since it has to be visible to the typechecker, so people usually don't bother.
* single-threaded mutation through multiple pointers into the same data structure, which may even be aliased. Again, often safe (though not always), and in the safe cases there are generally safe types to enable it in Rust, but since it's not the default and requires pre-planning for all but the simplest cases, people usually don't bother.
* Rust types are always annotated with thread safety information. This is usually done by default, but if it weren't it would be a huge amount of boilerplate. The reason this works is that in the cases where people are doing unsafe stuff, the type system automatically opts out and requires them to opt in. Libraries have been built around this assumption. Even if we were to port such a mechanism over to C++, the lack of these explicit annotations would mean that in practice it just wouldn't work that well--you would have to do a very detailed thread safety analysis of basically any existing library to try to assign types.
Often, complying with these kinds of rules is what people coming to Rust struggle with--not so much local lifetime issues which the compiler can usually figure out, but how to structure the entire program to make life easy for the borrow checker. However, complying comes with a big benefit--it allows safety analysis to proceed purely locally in almost all cases. The reason that static analyzers don't just "do what Rust does" is that they're dealing with programs that aren't structured that way and need to perform far more global analysis to catch most of the interesting memory safety bugs that pop up in mature C++ codebases, especially the ones that evade code review.
So--do I think it would be great to port this stuff over to C++ (or C, hypothetically?). Absolutely--I still prefer Rust as a language, but at the end of the day memory safety you could layer on top of existing C code would be a huge win for everyone. But I don't see it happening because of the fact that Rust's solution requires serious code restructuring. if people are going to have to rewrite their old programs anyway to work with a tractable static analysis, and not be able to use almost any existing libraries, it's not clear how much more benefit they'd have from using this subset than from just switching to Rust.
And most pertinently, this critique was written by someone who genuinely loves programming in Rust. Shows you that Rust users aren't blinded to the faults of the language. You shouldn't think that Rust users are fanboys just because you see push back to low effort, low knowledge critiques.
That's too much assuming, btw I read in this thread a comment from a well-known Nim dev working in multithreading (with much knowledge on the subject) and it was downvoted to oblivion.
That is putting the bar impossible high. I would expect most of the criticism to come from people who hate to program in Rust, which it is fine as long as the criticism is well argued.
I have a number of specific critiques of Rust, chief being that APIs and implementations are bound too tightly. &[String] and &[&str] are logically similar but changing from one to the other in your implementation might mean a breaking API change.
fn func (slice: &[impl AsRef<str>]) {
// ...
}In other words, mmaped files are hard, and Rust points this out. C just provides you with the footgun.
C has this issue as well, but Rust's compiler/borrow checker is particularly strong at this kind of analysis, so it's potentially bitten even harder.
It's still a very nice lib though, and a smart optimization, but it doesn't cover all of my use cases for small string buffers.
Yes. They are rather different in other respects as well. Though you can produce executable code from Idris and Agda, of course.
> With respect to deadlocks, there’s little practical difference between an infinite loop and a loop that holds the lock for a very long time.
Yes, that's true. Though as a practical matter, I have heard that it's much harder to produce the latter by accident, even though only the former is forbidden.
For perhaps a more practical example, have a look at https://dhall-lang.org/ which also terminates, but doesn't have nearly as much involved proving.
And in C, you have to design your data structures to be mmap friendly anyway. Same deal in Rust.
But this is moving the goal posts. This thread started with "you can't do this." But you can. And I have. Multiple times. And I showed you how.
So your code operates directly on a block of raw bytes? I can see how that can work with mmap without much problems.
My argument was more about structured data (created using the type system), which is a level higher than raw bytes.
$ ls -lh $(which grep) $(which rg)
-rwxr-xr-x 1 root root 199K Nov 10 06:37 /usr/bin/grep
-rwxr-xr-x 1 root root 4.2M Jan 19 09:31 /usr/bin/rg
My very unscientific measurement of the startup time of grep vs ripgrep is 10ms when the cache is cold (ie, never run before) and 3ms when the cache is hot (ie, was run seconds prior). For grep even in the cold case libc will already be in memory, of course. The point I'm trying to make is even the worst case, 10ms, is irrelevant to a human using the thing.
However, speaking as a Debian Developer, it makes a huge difference to maintaining the two systems that use the two programs. If a security bug is found in libc, all Debian has to do is make the fixed version of libc as a security update. If a bug is found in the rust stdlib create Debian has to track down every ripgrep like program that statically includes it, recompile it. There are current 21,000 packages that link to libc6 right in Debian right now. If it was statically linked, Debian would have to rebuilt and distribute _all_ of them. (As a side note, Debian has a lot hardware resources donated to it but if libc wasn't dynamlic I wonder if it could get security updates to a series of bugs in libc6 out in a timely fashion.)
I don't know rust well, but I thought it could dynamically link. The Debian rust packagers don't, for some reason. (As opposed 21,000 dependencies, libstd-rust has 1.) I guess there must be some kink in the rust tool chain that makes it easier not to. I imagine that would have to change if rust replaces C.
Also to be pedantic, C doesn't spec anything about linkage. Shared objects and how linkers use them to compose programs is a system detail more than a language one.
This being said, Rust has no problem using dynamic libraries.
Why else come up with this - https://docs.microsoft.com/en-us/windows/win32/procthread/th...?
I don't understand your comment about mmap. It is often used to share memory between related processes.
This is similar in typed languages with polymorphism like Haskell or ocaml where a function like concat (taking a list of lists to a single list) needs to work when the elements are floats (morally 8 bytes each) or bools (morally 1 bit each). The solution is to write the code once and have everything be in one word, either a fixnum or a pointer.
Scheduling Parallel Programs by Work Stealing with Private Deques https://hal.inria.fr/file/index/docid/863028/filename/full.p...
Without a requirement of utility it's easy to come up with counterexamples from math, eg "does the Collatz starting from Graham's number reach one?" Once you've exhausted cores that can be used for the actual arithmetic, you are still gated by the decision-making at each step so cores cannot work too far "ahead" of each other. There may well be much smarter things we can do than brute force, but that's not "just coding work" at that point.
Theoretically, it doesn't hold - at some point you have split apart everything that can be split, and you are left with some essential chains of data dependency that cannot be further parallelized.
I don't disagree that Rust probably would not go this way, but I think that's less "this is spooky reflection" and more "Rust likes static linking and cares less about stable ABIs, plus the general attitude of 'if you're going to make an indirect call the language should make you work for it'".
It's not the same kind of runtime reflection people talk about when they (for example) use reflection in Java. It's hidden from the library-using programmer, but the calling needs to "communicate" with the library to figure out data layouts and such, and that sounds a lot like reflection to me.
I'm making a game in Rust and Godot (engine) and since it's a factory game the simulation performance is important. Rust means I worry far less about stability and performance.
I bet if you wrote a good blog entry with screenshots and explanation of how your code loads and renders I imagine it would do well on HN.
Rust is good for this sort of thing. It's overkill for most web back end stuff. That's where Go is more useful. Go has all those well-used libraries for web back end tasks. Parallelism in web back ends tends to be about waiting for network events, not juggling heavy compute loads of coordinated disparate tasks. Hence all the interest in "async" for web servers. As I've said before, use the right tool for the job.
You have an authoritive world simulation server, as usual.
You then have several servers whose chief job is to keep clients in sync with the authoritive server.
Most network games combine these two roles, but there is a lot of processing and network traffic required to keep clients in sync. For massive multiplayer there is a benefit to scale the "client-interaction" servers.
There's a reason why Epic is able to charge a percentage of sales for their engine, and companies still opt for it. That's because it's hard to do reliably and with good performance and visuals.
Personally, I'd prefer to have a single binary that I start with some arguments, then need to also have a launch script, probably in a different language, which needs to coordinate all the starting, stopping, shared state etc.
But, most of my work has been at the workstation level. Maybe it's different once you start needing clusters? The issue is that workstations have grown extremely powerful over the last few years with 50+ cores, 1000s of GPU 'cores', and hundreds of GB of memory. Clusters now bring the same headaches, in hardware, of multiprocess design.
That's true indeed, but I find it more manageable that way.
To me, managing independent processes instead of threads is especially powerful when the lifecycle of the concurrent work can vary.
A typical example that happens quite often is when you have some kind of producer/consumer application. Say, you need to receive some data from a socket, and then process it.
If implemented with threads, it becomes quite messy very fast. You end up with a big blob binary that spawns whatever the hell it wants and need to engineer some complex configuration file to tell it how many workers you want, etc. You also need some notification to this process to tell him to increase or decrease its amount of workers, etc.
With independent process, it can be much more manageable. You can have a "collector" process that reads the socket and places messages in a shared memory, and if you want more/less workers, you just spawn worker processes to read from the shared memory.
If implemented with processes it becomes quite messy very fast. You end up with a bunch of processes that do whatever the hell they want, and need some complex orchestrator script to tell it how many processes you want, and need some notifications to the orchestrator to increase or decrease the number of workers
With threads, you can have a main thread that reads the socket and places messages in a shared queue, and if you want more/less workers you just spawn worker threads to read from the queue.
There is a lot of untapped parallelism readily available waiting for the right code.
That said, I think the original comment was rightly pointing out how easy it was to make the change and test it, which in this case did turn out to be noticeably faster.
That's the real issue here! Most language have poor abstractions for parallelism and concurrency. (Many languages don't even differentiate between the two.)
Encapsulating and abstracting is how we make things usable.
Eg letting people roll hash tables by themselves every time they want to use one, would lead to people shooting themselves in the foot more often than not. Compared to that, Python's dicts are dead simple to use. Exactly because they move all the fiddly bits out of the reach of meddling hands.
I think the example case in this subthread was about making some long app operations asynchronous and overlapping, which is a more forgiving use case than trying to make a piece of code faster by utilizing multiple cores.
Correct. It's a finite state machine. The docs of the crate give links to papers if you want to drill down.
> My argument was more about structured data (created using the type system), which is a level higher than raw bytes.
Yes. You should be able to do in Rust whatever you would do in C. You can tag your types with `repr(C)` to get a consistent memory layout equivalent to whatever C does. But when you memory map stuff like this, you need to take at least all the same precautions as you would in C. That is, you need to build your data structures to be mmap friendly. The most obvious thing that is problematic for mmap structures like this that is otherwise easy to do is pointer indirection.
With that said, this technique is not common in Rust because it requires `unsafe` to do it. And when you use `unsafe`, you want to be sure that it's justified.
This is all really besides the point. You'd have the same problems if you read a file into heap memory. The main problem in Rust land with memory maps is that they don't fit into Rust's safety story in an obvious way. But this in and of itself doesn't make them inaccessible to you. It just makes it harder to reason about safety.
This is of course a kernel feature when the lower level primitives are used that ask for blocks of memory from the kernel, which zeroes them if they had belonged to another process prior, and does not when they had not, and thus strongly favors giving back own memory. — allocators, such as the standard library's one or any custom ones, are built on top of these primitives.
My point is precisely that's its not trivial to do that.
You now need some signal mechanism to tell your main process to spawn or kill workers. That's an additional layer of complexity.
Things get even worse if you want to add new types of workers that were unplanned.
Say I want a new type of worker that is just a forwarder, or a new type of worker that stores the queue on disk for replaying it.
With a monolithic thread based design, you now need to stop your whole main and worker threads and start a newly built process that support these workers.
With a process based design, you just spawn a new worker process and point it to the existing shared memory without any interruption.
But sure, there is a reason why the M1 has so stellar performance, it has one of the fastest single-thread performances and many applications do not manage to load more than 4 cores for common tasks - which partially is also a consequence of doing that is difficult in many programming languages, but easy in some, which are only slowly gaining traction.
Not in the user application model you were describing. Those threads would need to coordinate and communicate (for example, back to the user interface), and that implies context switches.
Unless you're thinking of a strictly isolated thread-per-core design (https://mechanical-sympathy.blogspot.com/2011/09/single-writ...), which means we are then in agreement.
> And if you are memory-bound, why have more CPUs?
Yes, exactly, and that's why parallelism can often make things worse: https://brooker.co.za/blog/2014/12/06/random.html
However, for independent processes, each additional CPU adds memory bandwidth (according to the NUMA model) because there's a concurrency limit to each CPU's LFB that puts an upper bound of 6 GB/s on filling cache lines for cache misses (even if the bandwidth of your memory system is actually much higher): https://www.eidos.ic.i.u-tokyo.ac.jp/~tau/lecture/parallel_d...
[1] - I'm assuming commodity SSD in the range of a few hundred MB/s read speed. This will likely become less true as the prevalence of faster SSDs increases (low single digit GB/s).
I would guess it contains more c than rust code...
But what I love about this article is its lack of hype. It makes clear arguments both ways and all of them I can get behind
Hype doesn't help
Edit: To all my downvoters; I anticipated you :) With love and best wishes
Off the top of my head, the only C code in ripgrep is optional integration with PCRE2. In addition to whatever libc is being used on POSIX platforms. Everything else is pure Rust.
I would guess D could do it.
I don't know enough about Nim or Swift.
I would learn something if Common Lisp did it. I'd also learn something if Haskell or Go did it.
At the point of realizing the above no ceiling bit, the argument devolves to more one about (fairly subjective) high/low levelness of the code itself/the effort applied to optimizing, not about the language the code is written in. So, it's not very informative and tends to go nowhere (EDIT: especially when the focus is on a single, highly optimized tool like `rg` as opposed to "broad demographic traits" of pools of developers, and "levelness" is often somewhat subjective, too).
That's basically by knowing enough about GHC to carefully trigger all the relevant optimizations.
From the reference:
> Trait objects are written as the optional keyword dyn followed by a set of trait bounds, but with the following restrictions on the trait bounds. All traits except the first trait must be auto traits, there may not be more than one lifetime, and opt-out bounds (e.g. ?Sized) are not allowed.
The only one of those restrictions that is acceptable to have is the single lifetime one. All the others are seriously restricting. The devs seem to agree, but work on this aspect of rust is very slow, and people are arguing on how to implement it. (I, for one, feel very strongly that dyn TraitA + TraitB should have a size of 3 pointers. That is, no magic combining vtables, just every added trait adds a new pointer to vtable.)
Here's that example working: https://play.rust-lang.org/?version=stable&mode=debug&editio...
I am not entirely sure that it answers your point though; what you want is trait A or trait B, not both, right?
I don't know what you're trying to imply that Rust does, but I'll reiterate that Rust lifetimes don't exist at code generation time. They're not a runtime construct, they have zero influence over what code does at run time (e.g. mrustc compiler doesn't implement lifetimes, but bootstraps the whole Rust compiler just fine).
If you create `Vec<Object>` in Rust, then all objects will be allocated and laid out together as one contiguous chunk of memory, same as `malloc(sizeof(struct object) * n)` in C. You can also use `[Object; N]` or ArrayVec that's is identical to `struct object arr[N]`. It's also possible to use memory pools/arenas.
And where possible, LLVM will autovectorize operations on these too. Even if you use an iterator that in source code looks like it's operating on individual elements.
Knowing your other work I guess you mean SoA vs AoS? Rust doesn't have built-in syntax for these, but neither does C that we're talking about here.
This kind of reasoning seems like it makes sense, but actually it is false. ("Modern C++" people make the same arguments when arguing that you should use "zero-cost abstractions" all over the place). Abstractions determine how people write code, and the way they write the code determines the performance of the code.
When you conceptualize a bunch of stuff as different objects with different lifetimes, you are going to write code treating stuff as different objects with different lifetimes. That is slow.
> If you create `Vec<Object>` in Rust, then all objects will be allocated and laid out together as one contiguous chunk of memory
Sure, and that covers a small percentage of the use cases I am talking about, but not most of them.
This is not how lifetimes work at all. In fact this sounds like the sort of thing someone who has never read or written anything using lifetimes would say: even the most basic applications of lifetimes go beyond this.
Fundamentally, any particular lifetime variable (the 'a syntax) erases the distinctions between individual objects. Rust doesn't even have syntax for the lifetime of any individual object. Research in this area tends to use the term "region" rather than "lifetime" for this reason.
Lifetimes actually fit in quite nicely with the sorts of things programs do to optimize memory locality and allocations.
> Sure, and that covers a small percentage of the use cases I am talking about, but not most of them.
Fortunately the other stuff you are talking about works just fine in Rust as well.
Maybe you'd be interested to hear that Rust's borrow checker is very friendly to the ECS pattern, and works with ECS much better than with the classic OOP "Player extends Entity" approach.
The claim was that Rust made making something parallel easy/easier, and the illustrative example given was someone trying to parallelize something in a game engine. Whether Rust is good for game development or not is irrelevant to the point that was being made.
Even if everyone accepted that Rust was horrible for game development on most metrics, the example given would still carry the exact same weight, because it's really about "parallelizing this would be very hard in C++, but it was very easy because of Rust."
* I was thinking return values.
* Also you can't use that style in an enum definition if you want to return a custom enum.
You can use impl Trait in returns, this is actually one of the reasons why that feature exists.
And yes, you can use generics in an enum.
Ownership, mutability, and thread-safety are not easy to abstract over and hide as implementation details in Rust.
It's a side effect of the fact that Rust actually cares about these and checks them strictly, but for users coming from eg Java that's a bit of a shock.
I write them quite often in Rust, because Rayon makes it super easy, there is almost no risk because the compiler checks the relevant thread-safety invariants, and I'm working on different problems where data parallelism is much more useful.
Maybe it's not so hard if you're in a domain like HPC where the libraries you use are designed specifically to be used with data parallelism. But when you're pulling together code from different sources that may or may not have been used in an aggressively parallel application before...
Jonathan Blow makes good games, but chooses not to make particularly CPU intensive ones. That's fine, but that's also his choice.
#pragma omp parallel for
Point B: a criticism by someone who loves the language was presented, to show that claim was false.
Point B does not contradict point A at all. That is like saying that is false I cannot accept criticism because , hey, look at the weak points I have and I gladly mention("I am too perfectionist","I work too hard", "I put the wellness of the company ahead of myself")
I've read a lot of criticism of Rust and most of it is from people who tried it for a weekend, couldn't understand the borrow checker and wrote some low quality criticism of it. If someone points out problems in that post, they are accused of zealotry and fanboyism.
Read the post I linked. It covers all the issues and makes the strongest possible case against the language. Then tell me if you've ever seen one that is as negative, accurate and succinct as that one.
But that was OP's point.If your best example of Rust lovers accepting criticism of the language is the existence of a critical article written by a Rust lover, that does no say anything. The bar is naively high if the best example you got of tolerance to criticism was a critical article made by a member of the "tribe". The implicit point is that those kind of articles will be the ones playing "soft ball" with the language,so any perceived tolerance to criticism is almost meaningless.
It works pretty well for ordinary heavy crunch code too. I originally designed code like this on supercomputers. You do need a practical mechanism for efficiently decomposing loads at a fine granularity but you rarely see applications that don’t have this property that are also compute bound.
I've (badly) written code like you describe -- usually by abusing fork to do my initial data structure setup, then using C pipes to pass jobs around. I suspect there are much better ways of doing it, but that parallelised well enough for the stuff I was doing. I'd be interested to know if there are good libraries (or best practices) for doing this kind of parallelism.
Latency hiding is a technique where 1) most workloads are trivially decomposed into independent components that can be executed separately and 2) you can infer or directly determine when any particular operation will stall. There are many ways to execute these high latency operations in an asynchronous and non-blocking way such that you can immediate work on some other part of the workload. The “latency-hiding” part is that the CPU is rarely stalled, always switching to a part of the workload that is immediately runnable if possible so that the CPU is never stalled and always doing real, constructive work. Latency-hiding optimizes for throughput, maximizing utilization of the CPU, but potentially increasing the latency of specific sub-operations by virtue of reordering the execution schedule to “hide” the latency of operations that would stall the processor. For many workloads, the latency of the sub-operations doesn’t matter, only the throughput of the total operation. The real advantage of latency-hiding architectures is that you can approach the theoretical IPC of the silicon in real software.
There are exotic CPU architectures explicitly designed for latency hiding, mostly used in supercomputing. Cray/Tera MTA architecture is probably the canonical example as well as the original Xeon Phi. As a class, latency-hiding CPU architectures are sometimes referred to as “barrel processors”. In the case of Cray MTA, the CPU can track 128 separate threads of execution in hardware and automatically switch to a thread that is immediately runnable at each clock cycle. Thread coordination is effectively “free”. In software, switching between logical threads of execution is much more by inference but often sees huge gains in throughput. The only caveat is that you can’t ignore tail latencies in the design — a theoretically optimal latency-hiding architecture may defer execution of an operation indefinitely.
I don’t know much about supercomputers, but what you described is precisely how all modern GPUs deal with VRAM latency. Each core runs multiple threads, the count is bound by resources used: the more registers and group shared memory a shader uses, the less threads of the shader can be scheduled on the same core. The GPU then switches threads instead of waiting for that latency.
That’s how GPUs can saturate their RAM bandwidth, which exceeds 500 GB/second in modern high-end GPUs.
"Threads" are nothing but kernel-mode coroutines with purpose-built schedulers in the kernel.
Redoing the same machinery except in usermode is not the way to get performance.
The problem is that scripting languages don't let you access the kernel API's cleanly due to various braindead design decisions - global locks in the garbage collector, etc.
But the solution isn't to rewrite the kernel in every scripting language, the solution is to learn to make scripting languages that aren't braindead.
unsafe impl GlobalAlloc {
pub unsafe fn alloc(&self, layout: Layout) -> *mut u8;
pub unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
}
Now, there's a good argument to be had about safe and unsafe, how much you need, in what proportion, and in what kinds of programs... but when you say things like "C allows you to do bulk memory operations, Rust does not" and ask about the borrow checker when talking about allocators, to someone who is familiar with Rust's details, it seems like you are misinformed somehow, which makes it really hard to engage constructively with what you're saying.
Yes languages like Erlang and runtimes like Coyote and Orleans.
I’ve not worked with Coyote, but if it is the system for .net, it describes itself as a framework, “Coyote provides developers a programming framework for confidently building reliable asynchronous software on the .NET platform”.
Orleans similarly describes itself as a framework, “Orleans is a cross-platform software framework for building scalable and robust distributed interactive applications based on the .NET Framework.”
Rust is a language, similar frameworks are being built with it, the point your making does not appear to be about the language.
You say, that the Erlang concurrency model has higher overhead than Rust. In Rust there are probably multiple projects going on right now (one of them is Bastion, but I guess there are probably others), which try to provide Erlang like concurrency. What do you mean by overhead of a concurrency model (that of Erlang) being higher than the overhead a programming language (Rust)? As far as I know Erlang's lightweight processes are about as lightweight as you can get. Is there a Rust framework for Erlang like concurrency, which reduces the footprint of lightweight processes even more?
I don’t have time right now to research the full details, but the Wikipedia article gives a clue:
> Theo de Raadt, founder and leader of the OpenBSD and OpenSSH projects, has criticized the OpenSSL developers for writing their own memory management routines and thereby, he claims, circumventing OpenBSD C standard library exploit countermeasures, saying "OpenSSL is not developed by a responsible team." Following Heartbleed's disclosure, members of the OpenBSD project forked OpenSSL into LibreSSL.
Well, I mean, you chose an embarrassingly general statement to make? Play stupid games, win stupid prizes.
> which most programs are not
Programs? Or problems? Who says? It's not at all obvious to me that it's true. And even if it were true, "embarrassingly parallel" problems are nowhere close to uncommon.
> When you try to parallelize a structurally complicated algorithm, the biggest issue is contention.
With respect to performance, I agree.
> How come so few people are concerned with the answers to that question and which are true, but so many people are concerned with making performance claims?
The question is itself flawed. Technology isn't fixed. We "advance" and try to do more stuff. This is not me saying, "this explains everything." Or even that "more stuff" is a good thing. This is me saying, "there's more to it than your over-simplifications."
Burntsushi began with "here, parallelization is beating out memory locality and optimization in its impact," but explicitly declined to generalize this the way you generalized your claim about memory.
He further pointed out that ripgrep is fast not just because of parallelization, but also because of how it handles memory.
Then you come back with "you can't always parallelize this well" (which burntsushi agreed with from the beginning) and "you also need to deal with memory" (which ripgrep does)? How is this burntsushi's problem with understanding "embarrassingly parallel" and not your problem with understanding Rust?
Makes me all the more sad that you're consistently unable to work through the consequences of Rust's axioms.
You don't even need to hide those out of reach. You just need to make it dead simple to use and pretty much nobody will want to touch the fiddly bits.
And those who do know they had it coming.
You seldom have to protect against malicious attempts. (But when you do, it's a much harder task.)
It has a very specific meaning in Rust: the user can cause memory unsafety if they make a mistake.
> I think a better word is “error-prone.”
The issue with the connotation there is that it's not about the rate of problems, it's about them going from "impossible" to "possible."
“A commission attributed the primary cause to general poor software design and development practices rather than single-out specific coding errors. In particular, the software was designed so that it was realistically impossible to test it in a clean automated way.“
Ergo, concurrency doesn’t kill people, people do.
most rust folks who use mmap don't mark the region as Celled, which means they risk UB in the form of incorrect behavior because the compiler assumes that the memory region is untouchable outside the single Rust program, and that's not true
(it's also not true generally b/c /dev/mem and /proc/pid/mem exist, but it's beyond Rust's scope that the OS allows intrusion like that)
Dangerous means dangerous. It's not up for interpretation.
Languages have multiple, very different words, for exactly this reason.
Rust has plenty of situations where you do unsafe things but wrap that in safe APIs. If you’re returning regions of that mmapped file, for example, a lifetime can be associated to those references to ensure that those are valid for the duration of the file being mmapped in the program.
It can be used to ensure that if you need to write back to that mmapped file (inside the same program) that there are no existing references to it, because those would be invalid after an update to the file. You need to do the same in C, but there are no guardrails you can build in C to make that same assurance.
I've never heard of this trick. And my first reaction is "That would be a nightmare of memory unsafety if I did it in C++"
What's it used for? IPC?
I know some very skilled C++ and Rust developers who can pull it off. If you're at that skill level, Rust is not going to get in your way because you're just going to use unsafe and throw some sanitizers and fuzzers at it. I wouldn't trust myself to implement it.
I've tried optimizing Haskell code myself before. It did not go well. It was an implementation of the Viterbi algorithm actually. We ported it to Standard ML and C and measured performance. mlton did quite well at least.
We published a paper about the process of writing Viterbi in Haskell in ICFP a few years back: https://dl.acm.org/doi/pdf/10.1145/2364527.2364560?casa_toke...
Unfortunately, the performance aspect of it was only a small part, and we didn't talk about the C or mlton ports in the paper.
I suspect you could make a very Haskell-like language that's also really fast, but you'd have to base it on linear types from the ground up, and make everything total by default. (Hide non-total parts behind some type 'tag' like we do with IO in current Haskell (and have something like unsafePerformPartial when you know your code is total, but can't convince the compiler).)
That way the compiler can be much more aggressive about making things strict.
The “process” model of Erlang is about as lightweight as you can get, agreed.
In terms of capabilities of beam across systems, point taken. Though we start stretching some of the understanding of where languages end and runtimes begin... Rust and C make those boundaries a little more clear.
I anticipated I could well be wrong. I ALSO anticipated it would be a hard statement for people to take
I think it was a reasonable statement -- I can't research everything I say, and I had read re2 and regexes in rust to be the same
Interesting to read about redgrep and derivatives approach. Currently I'm programming a language that adds turing completeness to PEG expressions -- as in functions, but extended so the lhs is like a PEG -- just as function body can call sub functions, so too can the lhs
I'm hoping this will give a simple unified language
--
Philosophically:
We make mistakes. If we can't handle that, then either we don't speak or program; or we deny it, program in c, then have flamewars and real wars
Or thirdly, we accept it, program in rust, and let others correct us
We can say you are my rustc compiler. So in effect I used a rust philosophy..... While programming in c
Rust also has "Copy" types which by definition can be trivially created and can't have destructors. Collections take advantage of that (e.g. dropping an array doesn't run any code).
So I don't really get what you mean. Rust's RAII can be compiled to plain C code (in fact, mrustc does exactly that). It's just `struct Foo foo = {}` followed by optional user-defined `bye_bye(&foo)` after its last use (note: it's not free/delete, memory allocator doesn't have to be involved at all).
I suspect you're talking about some wider programming patterns and best practices, but I don't see how that relates to C. If you don't need per-object init()/deinit(), then for the same you wouldn't use RAII in Rust either. RAII is an opt-in pattern.
But, I am familiar with the kind of thing you're complaining about here, and frankly the mere existence of RAII is not its cause. Working with a large dataset, managing allocation/layout/traversal in a holistic way, you just... don't write destructors for every tiny piece. It works fine, I do it all the time (in both Rust and C++).
> If you have an architecture where you can afford real parallelism you can afford higher level languages anyway.
My response is, "no you can't, and here's an example."
> but any language mature enough to have an impl/way to not have arbitrary performance ceilings needs access to inline assembly/SIMD
If you ported ripgrep to Python and the vast majority of it was in C or Assembly, then I would say, "that's consistent with my claim: your port isn't in Python."
My claim is likely more subtle than you might imagine. ripgrep has many performance sensitive areas. It isn't enough to, say, implement the regex engine in C and write some glue code around that. It won't be good enough. (Or at least, that's my claim. If I'm proven wrong, then as I said, I'd learn something.)
> At the point of realizing the above no ceiling bit, the argument devolves to more one about (fairly subjective) high/low levelness of the code itself/the effort applied to optimizing, not about the language the code is written in. So, it's not very informative and tends to go nowhere.
I agree that it's pretty subjective and wishy washy. But when someone goes around talking nonsense like "if parallelism is a benefit then you're fine with a higher level language," you kind of have to work with what you got. A good counter example to that nonsense is to show a program that is written is a "lower" level language that simultaneously benefits from parallelism and wouldn't be appropriate to do in a higher level language. I happen to have one of those in my back-pocket. :-) (xsv is another example. Compare it with csvkit, even though csvkit's CSV parser is written in C, it's still dog slow, because the code around the CSV parser matters.)
FWIW, as per your subtle claim, it all seems pretty hot spot optimizable to me, at least if you include the memchr/utf8-regex engine in "hot spot". I do think the entire framing has much measurement vagueness ("hot", "vast majority", "levelness", and others) & is unlikely to be helpful, as explained. In terms of "evidence", I do not know of a competitor who has put the care into such a tool to even try to measure, though. { And I love rg. Many thanks and no offense at all was intended! }
> I do not know of a competitor who has put the care into such a tool to even try to measure, though.
Right. Like for example, I am certain enough about my claim that I would never even attempt to do it in the first place. I would guess that others think the same. With that said, people have written grep's in Python and the like, and last time I checked, they were very slow. But yeah, the "development effort" angle of this likely makes such tools inappropriate for a serious comparison to support my claim. But then again, if I'm right, the development effort required to make a Python grep be as fast as ripgrep is insurmountable.
> it all seems pretty hot spot optimizable to me
As long as we're okay with being hand wavy, then I would say that it's unlikely. Many of the optimizations in ripgrep have to do with amortizing allocation, and that kind of optimization is just nearly completely absent in a language like Python unless you drop down into C. This amortization principle is pervasive and applies as deep as regex internals to the code the simply prints ripgrep's output (which is in and of itself a complex beast and quite performance sensitive in workloads with lots of matches), and oodles of stuff inbetween.
> { And I love rg. Many thanks and no offense at all was intended! }
:-) No offense taken. This is by far the best convo I'm having in this HN post. Lol.
Note that I've made similar claims before. In the last one, there is a lot more data: https://news.ycombinator.com/item?id=17943509
As an aside, I'm the author of ack, and I would ask that folks not use the word "competitor" to describe different projects in the same space. Speaking for me/ack and burntsushi/ripgrep, there is absolutely no competition between us. We have different projects that do similar things, and neither of us is trying to best the other. We are each trying to make the best project we can for the needs we are looking to fill. ripgrep won't replace ack, ack won't replace ripgrep, and neither one will replace plain ol' grep. Each has its place.
I believe this so strongly that I created a [feature comparison chart](https://beyondgrep.com/feature-comparison/) comparing various greplike tools, and a related blog post I wrote on this: [The best open source project for someone might not be yours, and that's OK](https://blog.petdance.com/2018/01/02/the-best-open-source-pr...)
But anyways, cheers and good luck with your programming language!
In the HPC world, software is usually doing one thing at a time. Most of the time it's either single-threaded, or there are multiple threads doing the same thing for independent chunks of data. There may be shared immutable data and private mutable data but very little shared mutable data. You avoid situations where the behavior of a thread depends on what the other threads are doing. Ideally, there is a single critical section doing simple things in a single place, which should make thread-safety immediately obvious.
You try to avoid being clever. You avoid complex control flows. You avoid the weird middle ground where things are not obviously thread-safe and not obviously unsafe. If you are unsure about an external library, you spend more time familiarizing yourself with it or you only use it in single-threaded contexts. Or you throw it away and reinvent the wheel.
Don't you sort of have to do that if you're writing your own garbage collector, though? I guess for a simple collector you could maintain lists of allocated objects separately, but precisely controlling where the memory is allocated is important for any kind of performant implementation.
Type-specific free lists (just a few examples; there are more):
* https://github.com/python/cpython/blob/master/Objects/floato...
* https://github.com/python/cpython/blob/master/Objects/tupleo...
And also just wrapping malloc in general. There's no refcounting reason for this, they just assume system malloc is slow (which might be true, for glibc) and wrap it in the default build configuration:
https://github.com/python/cpython/blob/master/Objects/obmall...
So many layers of wrapping malloc, just because system allocators were slow in 2000. Defeats free() poisoning and ASAN. obmalloc can be disabled by turning off PYMALLOC, but that doesn't disable the per-type freelists IIRC. And PYMALLOC is enabled by default.
Regular languages are closed under those operations after all.
Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk
ripgrep's regex syntax is the same as Rust's regex crate: https://docs.rs/regex/1.4.4/regex/#syntax (Which is in turn similar to RE2, although it supports a bit more niceties.)
Oh, I didn't say anything about easy! I am on and off working on a Haskell re-implementation (but with GADTs and in Oleg's tagless final interpreter style etc, so it's more about exploring the type system).
> In practice, they explode the size of the underlying FSM.
You may be right, but that's still better than the gymnastics you'd have to do by hand to get the same features out of a 'normal' regex.
> Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining.
Alas, that only works, if your intersection or complement happen at the top level. You can't do something like
(A & not B) followed by (C & D)
that way.
> Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk
I have, and I agree!
Perhaps I'll try and implement a basic version of redgrep in Rust as an exercise. (I just want something that supports basically all the operations regular languages are closed, but don't care too much about speed, as long as the runtime complexity is linear.)
Great work btw. Ripgrep is the best
... I will have to restrict my comment to just LLVM being a larger, c++, dependency
... Just angling for more downvotes ;) Thanks for the reply
I played with making a regex library in rust. Which, as per RE2 design involves constructing graphs and glueing them together as the regex is traversed
This requires a cycle catching gc, or, just a preallocated arena... It was my first foray into rust and felt I would need to be hitting into unsafe, which I wasn't ready for. Array indexing might decompose into an arena, but syntactically just a bit messier (imho)
Would be interesting to see how the RE2 does it in rust (didn't know that)
I like how the article shows both sides of the fence, it makes me realize:
I get a lot of optimizations from ptr stuffing in c. But sometimes we should lay down the good, for the better
But Python runs a generational GC in addition to refcounting to catch cycles (https://docs.python.org/3/library/gc.html): isn't fine control over allocation necessary for that? E.g. to efficiently clear the nursery?
While allocation is pretty pervasive, I'm skeptical that everywhere or even most places you do it is an important perf bottleneck. Without a count of these 20 times it matters and these 40 it doesn't, it's just kind guesswork from an all too often frail human memory/attention that "ignores the noise" by its very nature. You might be right. Just trying to add some color. :-)
Another way to think of this is to imagine your own codebase "in reverse". "If I drop this optim, would I see it on that profile?" Or look at the biggest piles of code in your repo and ask "Is this in the critical path/really perf necessary?" and the like. Under the assumption that higher level things would be a lot shorter that kind of thought experiment can inform. Maybe an approach toward more objectivity, anyway. Little strewn about tidbits in every module don't really count { to me :-) } - that speaks more to abstraction problems.
But I don't think there is a lot of value in all the above gendankenizing. While I realize some bad "just throw money at it" kicked this off, one of my big objections to the entire framing is that I think people and their APIs really "alter the level" of a language. Indeed their experience with the language has big impact there. Every one reading this knows C's `printf(fmt, arg1, arg2,..)`. Yet, I'd bet under 1% have heard of/thought to do an allocating (or preallocated) string builder variant like `str(sub1, sub2, ..., NULL)` or using/acquiring something like glibc's `asprintf`. People will say "C is low level - It has no string concatenation!". Yet, inside of an hour or two most medium-skill devs could write my above variadic string builder or learn about vasprintf. Or learn about Boehm-Wiser for garbage collected C or 100 other things like that CTL I mentioned elsewhere in this thread.
So what "level" is C, the language? Beats me. Does it have concatenation? Well, not spelled "a+b" but maybe spelled not much worse "str(a,b,NULL)". Level all just depends so much on how you use it. Performance is similar. Much C++ (and Rust for that matter) is terribly inefficient because of reputations for being "fast languages" leading to less care (or maybe just being done by junior devs..). These "depends" carry over to almost anything..not just Rust or C, but sometimes even English. I am usually told I write in much too detailed a way and a trimmer way might have higher persuasion/communication performance! { How's that for "meta"? ;-) }
> This is by far the best convo I'm having in this HN post. Lol.
Cool, cool. There can be a lot of "Rust Rage" out there (in both directions, probably). :)
Anyway, I don't think we'll resolve anything objective here, but don't take a lack of response as indicating anything other than that. You aren't making any strong objective claims to really rebut and I'm glad that you personally undertook the challenge to do ripgrep in any language. I do think many might have done..maybe Ada, too, and probably many more, but maybe all at the same "realized levelness". You just did not know them/feel confident about getting peformance in them. Which is fine. A.Ok, even! I guess your other biggy is Go and that might actually not have worked of all the alternatives bandied about by pjmlp and myself so far.
In general I agree. But I'm saying what I'm saying because of all the times I've had to change my code to amortize allocation rather than not do it. It's just pervasive because there are all sorts of little buffers everywhere in different parts of the code. And those were put there because of experimenting that said the program benefited from them.
The key here is that the loops inside of ripgrep can grow quite large pretty quickly. There's the obvious "loop over all files," and then there's "loop over all lines" and then "loop over all matches." ripgrep has to do work in each of those loops and sometimes the work requires allocation. Even allocations at the outermost loop (looping over all files) can cause noticeable degradations in speed for some workloads.
This is why I'm so certain.
The numpy example is a good one where a substantial amount of code has been written to cater to one very specific domain. And in that domain, it's true, you can write programs that are very fast.
> So what "level" is C, the language?
Oh I see, I don't think I realized you wanted to go in this direction. I think I would just say that I absolutely agree that describing languages as "levels" is problematic. There's lots of good counter examples and what not. For example, one could say that Rust is both high level and low level and still be correct.
But like, for example, I would say that "Python is high level" is correct and "Python is low level" is probably not. But they are exceptionally general statements and I'm sure counter-examples exist. They are, after all, inherently relativistic statements, so your baseline matters.
That's kind of why I've stayed in "hand wavy" territory here. If we wanted to come down to Earth, we could, for example, replace "high level languages" in the poster's original statement with something more precise but also more verbose that this discussion still largely fits.
> I am usually told I write in much too detailed a way and a trimmer way might have higher persuasion/communication performance! { How's that for "meta"? ;-) }
Yeah, it's hard to be both pithy and precise. So usually when one is pithy, it's good to take the charitable interpretation of it. But we are technical folks, and chiming in with clarifications is to be expected.
> I don't think we'll resolve anything objective here
Most definitely. At the end of the day, I have a prior about what's possible in certain languages, and if that prior is proven wrong, then invariably, my mental model gets updated. Some priors are stronger than others. :-)
> You aren't making any strong objective claims to really rebut
Right. Or rather, my claims are rooted in my own experience. If we were going to test this, we'd probably want to build a smaller model of ripgrep in Rust, then try implementing that in various languages and see how far we can get. The problem with that is that the model has to be complex enough to model some reasonable real world usage. As you remove features from ripgrep, so to do you remove the need for different kinds of optimizations. For example, if ripgrep didn't have replacements or didn't do anything other than memory map files, then that's two sources of alloc amortization that aren't needed. So ultimately, doing this test would be expensive. And that's ignoring the quibbling folks will ultimately have about whether or not it's fair.
> I guess your other biggy is Go and that might actually not have worked of all the alternatives bandied about by pjmlp and myself so far.
I would guess Go would have a much better shot than Python. But even Go might be tricky. Someone tried to write a source code line counter in Go, put quite a bit of effort into it, and couldn't get over the GC hurdle: https://boyter.org/posts/sloc-cloc-code/ (subsequent blog posts on the topic discuss GC as well).
My first reply was questioning "what counts" as "Python". Cython is its own language, not just "C", nor just "Python", but can do "low level things" such as using C's alloca. Maybe the only prior update here is on the diversity of "Python" impls. There are a lot. This is another reason why language levelness is hard to pin down which was always my main point, upon which we do not disagree. Maybe this is what you meant by "exceptionally general", but I kinda feel like "there isn't just one 'Python'" got lost. { There used to be a joke.."Linux isn't" related to the variety of distros/default configs/etc. :-) }
Advice-wise, I would say that your claim can be closer to easily true if you adjust it to say "ripgrep needs 'low level tricks' to be fast and a language that allows them, such as Rust". That phrasing side-steps worrying about levelnesses in the large of programming languages, re-assigns it to techniques which is more concrete and begs the question of technique enumeration. That is the right question to beg, though, if not in this conversation then in others. You might learn how each and every technique has representation in various other programming languages. It's late for me, though. So, good night!
People in this thread keep talking about "arena allocators" as if they are special things that you would use a few times (Grep Guy said this above, for example), or, here you imply they would be used internally to data structures, in a way that doesn't reach out to user-level.
That makes them not nearly as useful as they can be!
The game we are working on is currently 100k lines (150k lines if you count comments etc), and almost all allocations in the entire program are of this bulk type, in one way or another. Like if I want to copy a string to modify it a little bit to then look up a bitmap or make a filename, those are temporary allocations at user level and are not wrapped by anything. The string type is not some weird heavyweight C++ std::string kind of thing that wraps a bunch of functionality, it is just a length and a data pointer.
So the proposal to use unsafe in this kind of context doesn't make sense, since then you are putting unsafe everywhere in the program, which, then, why pretend you are checking things?
You can say, "well you as the end-user shouldn't be doing this stuff, everything should be wrapped in structures that were written by someone smarter than you I guess," but that is just not the model of programming that I am doing.
I understand how you can think the statement "Rust does not (allow you to do bulk memory operations)" is false, but when I say this, part of what I am including in "bulk memory operations" is the ability (as the end user) to pretend like you are in a garbage-collected language and not worry about the lifetime of your data, without having to take the performance penalty of using a garbage-collected language. So if you add back in worrying about lifetimes, it's not the same thing.
If you think "bulk memory allocation" is like, I have this big data structure that manages some API and it has some linked lists, and instead of allocating those nodes on the heap I get them from an arena or pool managed by the bigger structure ... that's fine, it is better than not doing it, but it doesn't help the end user write simpler code, and in practical terms it means that most of the allocations in the program are going to be non-bulk, because there's just too much friction on doing them broadly.
If it helps, I can revise my statement to "Rust enables you to do certain kinds of internal bulk memory allocation, but using bulk allocation broadly and freely across your program goes against the core spirit of the language" ... that sounds pretty uncontroversial? Then to bring it back to the original post, I would say, "This kind of broad use of bulk allocation is important for high performance and simplicity of the resulting code."
One last note, I am pretty tired of the "you don't understand Rust, therefore you are beneath us" line that everyone in the Rust community seems to deploy with even the slightest provocation -- not just when responding to me, but to anyone who doesn't just love Rust from top to bottom. Really it makes me feel that the only useful thing to do is just ignore Rust folks and go do useful things instead. I know I am not the only person who feels this way.
I didn't say anything about arena allocators. What I said was that amortizing allocation was routine and commonplace in ripgrep's code. I definitely wouldn't say that amortizing allocation is "special" or something I use a "few" times. As one example of amortizing allocs, it's very common to ask the caller for some memory instead of allocating memory yourself.
> I am pretty tired of the "you don't understand Rust, therefore you are beneath us" line that everyone in the Rust community seems to deploy with even the slightest provocation
Kind of like opening a comment with "This entire article is nonsense." Right? Snubbing your nose and then getting miffed by the perception of others snubbing their nose at you is a bunch of shenanigans. And then you snub your nose at pretty much everyone: "It's the blind leading the blind." I mean, c'mon dude.
The problem with your comments is that they lack specifics. Even after this comment where you've tried to explain, it's pretty hard for me to understand what you're getting at. I suspect part of the problem is your use of this term "bulk allocation." Is it jargon that refers to the specific pattern you have in mind? Because if it is, I can't find it documented anywhere after a quick search. If it's not jargon, then "bulk allocation" could mean a lot of things, but you clearly have a very specific variant of it in mind.
It's clear to me that your argument is a very subtle one that requires nuance and probably lots of code examples to get the point across. Going about this at the other end---with lots of generalities and presumptions---just seems like a fool's errand.
If every throwaway string in your program comes from an arena that you clear later, great! Rust won't stop you, or even force you to use unsafe every time you build one. The unsafe code goes in a "give me a fresh chunk of temporary memory" function, and that function is safe to call all over the place: unsafe-in-a-safe-function is a common pattern for extending the set of analyzable programs.
(It's also worth pointing out that Rust's primitive string type is "just a length and a data pointer," so once you've allocated one out of an arena like this, you can do all the nice built-in string-y things with it, with no std::string-like interference.)
The Rust compiler itself uses this sort of bulk memory all the time. It's not limited to the internals of data structures there- it's spread across larger phases and queries of its operation, with all kinds of stuff allocated the same way.
Now, to be fair, this is not the default- e.g. Rust's standard library of collections don't participate. But this is why everyone keeps mentioning custom allocators to you- there is ongoing work to extend these collections with the ability to control how they perform their allocation!
> One last note, I am pretty tired of the "you don't understand Rust, therefore you are beneath us" line that everyone in the Rust community seems to deploy with even the slightest provocation -- not just when responding to me, but to anyone who doesn't just love Rust from top to bottom.
You would get this kind of reaction a lot less often if you didn't make vague or nonsense claims about it so often.
Then when you guys say I am making nonsense claims because of course you can have your cake and also eat it as long as you use the Rust programming language, well, it's just pretty weird at that point.
Ah! I think I am understanding you a bit better. The thing is, ultimately, Rust is as flexible as you want it to be, and so there are a variety of options. This can make it tricky, when folks are talking about slightly different things, in slightly different contexts.
When you say "doesn't reach out to user level," what I mean by what I said was that users don't generally call alloc and dealloc directly. Here, let's move to an actual concrete example so that it's more clear. Code is better than words, often:
use bumpalo::{Bump, boxed::Box};
struct Point {
x: i32,
y: i32,
}
fn main() {
let bump = Bump::with_capacity(256);
let c = Box::new_in(Point { x: 5, y: 6 }, &bump);
}
But notably, I am not using any unsafe here. Yes, I am saying "give me an allocation of this total size", and yes I am saying "please allocate stuff into it and give me pointers to it," but generally, I as a user don't need to mess with unsafe unless I'm the person implementing bumpalo. And sometimes you are! Personally, I work in embedded, with no global heap at all. I end up using more unsafe than most. But there's no unsafe code in what I've written above, but it's still gonna give you something like what you said you're doing in your current game. Of course, you probably want something more like an arena, than a pure bump allocator. Those exist too. You write 'em up like you would anything else. Rust will still make sure that c doesn't outlive bump, but it'll do that entirely at compile time, no runtime checks here.
Oh, and this is sorta random but I didn't know where to put it: Rust's &str type is a "pointer + length" as well. Using this kind of thing is extremely common in Rust, we call them "slices" and they're not just for strings.
> You can say, "well you as the end-user shouldn't be doing this stuff, everything should be wrapped in structures that were written by someone smarter than you I guess," but that is just not the model of programming that I am doing.
While that's convenient, and in this case, I am showing that, the point is that it's about encapsulation. I don't have to use this existing allocator if I wanted to write something different. But because I can encapsulate the unsafe bit, no matter who is writing it, I need to pay attention in a smaller part of my program. Maybe I am that person, maybe someone else is, but the benefit is roughly the same either way.
> So if you add back in worrying about lifetimes, it's not the same thing.
To be super clear about it, Rust has raw pointers, that are the same as C. No lifetimes. If you want to use them, you can. The vast, vast, vast majority of the time, you do not need the flexibility, and so it's worth giving it up for the compile time checks.
> If you think "bulk memory allocation" is like...
It's not clear to me above if the API I'm talking about above is what you mean here, or something else. It's not clear to me how you'd get simpler than "please give me a handle to this part of the heap," but I haven't seen your latest Jai streams. I am excited to give it a try once I am able to.
> but using bulk allocation broadly and freely across your program goes against the core spirit of the language
I don't know why you'd think these techniques are against the core spirit of the language. Rust's primitive array type is literally "give me N of these bits of data laid out next to each other in memory." We had a keynote at Rustconf about how useful generational arenas are as a technique in Rust. As a systems language, Rust needs to give you the freedom to do literally anything and everything possible.
> One last note, I am pretty tired of the "you don't understand Rust, therefore you are beneath us"
To be clear, I don't think that you or anyone else is "beneath us," here. What I want is informed criticism, rather than sweeping, incorrect statements that lead people to believe things that aren't true. Rust is not perfect. There are tons of things we could do better. But that doesn't mean that it's not right to point out when facts are different than the things that are said. You of all people seem to appreciate a forward communication style.
I agree, and if I say things that are incorrect, then I definitely want to fix them, because I value being correct.
But what I am meeting in this thread is people wanting to do some language-lawyer version of trying to prove I am incorrect, without addressing the substance of what I am actually saying. I think your replies have been the only exception to this (and only just).
I realize my original posting was pretty brusque, but, the article was very bad and I am very concerned with the ongoing deterioration of software quality, and the hivemind responses to articles like this on HN, I think, are part of the problem.
I know that Rust people are also concerned with software quality, and that's good. I just think most of Rust's theories about what will help, and most of the ways these are implemented semantically, are just wrong.
So if something I am saying doesn't seem to make sense, or seems "incorrect", well, maybe it's that I am just coming from a very different place in terms of what good programming looks like. The code that I write just looks way different from the code you guys write, the things I think about are way different, etc. So that probably makes communication much harder than it otherwise would be, and makes it much easier to misunderstand things.
On the technical topic being discussed here...
Using a bump allocator in the way you just did, on the stack for local code that uses the bump allocator right there, is semantically correct, but not a very useful usage pattern. In a long-running interactive application, that is being programmed according to a bulk allocation paradigm that maybe is "data oriented" or whatever the kids call it these days, there are pretty much 4 memory usage patterns that you ever care about:
(1) Data baked into the program, or that is initialized so early at startup that you don't have to worry about it. [This is 'static in Rust].
(2) Data that probably lives a long time, but not the whole lifetime of the program, and that will be deallocated capriciously at some point. (For example, an entry in a global state table).
(3) Data that lasts long enough that local code doesn't have to care about its lifetime, but that does not need to survive long-term. For example, a per-frame temporary arena, or a per-job arena that lasts the lifetime of an asynchronous task.
(4) Data that lives on the stack, thus that can't ever be used upward on the stack.
Now, the thing is that category (3) was not really acknowledged in a public way for a long time, and a lot of people still don't really think of it as its own thing. (I certainly didn't learn to think about this possibility in CS school, for example). But in cases of dynamic allocation, category (3) is strictly superior to (4) -- because it's approximately as fast, and you don't have to worry about your alloca trying to survive too long. You can whip up a temporary string and just return it from your function and nobody owns it and it's fine. So having your program really lean on (3) in a big way is very useful. This is what I was saying before about pretending to have a garbage collector, but you don't pay for it.
So if you are doing a fast data-oriented program (I don't really use the term "data-oriented" but I will use it here just for shorthand), dynamic allocations are going to be categories 1-3, and (4) is just for like your plain vanilla local variables on the stack, but these are so simple you just don't need to think about them much.
Insofar as I can tell, all this lifetime analysis stuff in Rust is geared toward (4). Rust wants you to be a good RAII citizen and have "resources" owned by authoritative things that drop at very specific times. (The weird thing about "resources" is that in reality this almost always means memory, and dealing with memory is very very different from dealing with something like a file descriptor, but this is genericized into "resources", which I think is generally a big mistake that many modern programming language people make).
With (1), you don't need any lifetime checking, because there is no problem. With (2), well, you can leak and whatever, but this is sort of just your problem to make sure it doesn't happen, because it is not amenable to static analysis. With (3), you could formalize a lifetime for it, but it is just one quasi-global lifetime that you are using for lots of different data, so this by definition cannot do very much work for you. You could use it to avoid setting a global to something in category (3), and that's useful to a degree, but in reality this problem is not hard to catch without that, and it doesn't seem worth it to me in terms of the amount of friction required to address this problem. Then there is (4), which, if you are not programming in RAII style, you don't really need checking very much??, because everything there is simple, and anyway, the vast majority of common stack violations are statically detectable even in C (the fact that C compilers did not historically do this is really dumb, and has been a source of much woe, but like, it is very easy to detect if you return a pointer to a local from a function, for example. Yes, this is not thorough in the way Rust's lifetime checking is, and this class of analysis will not catch everything Rust does, but honestly it will catch most of it, at no cost to the programmer).
So when I said "Rust does not allow you to do bulk memory allocation" what I am saying is, the way the language is intended to be used, you have most of your resources being of type (4), and it prevents you from assigning them incorrectly to other resources of type (4) but that have shorter lifetimes, or to (2) or (1).
But if almost everything in (4) is so simple you don't take pointers to it and whatnot, and if most of your resources are (3), they have the same lifetime as each other, all over the place, so there is no use checking them against each other. So now the only benefit you are getting is ensuring that you don't assign (3) to (2) or (1). But the nature of (3) is such that it is reset from a centralized place, so that it is easy, for example, to wipe the memory each frame with a known pattern to generate a crash if something is wrong, or, if you want something more like an analytical framework, to do a Boehm-style garbage collector thing on your heap (in Debug/checked builds only!) to ensure that nothing points into this space, which is a well-defined and easy thing to do because there is a specific place and time during which that space is supposed to be empty.
So to me "programming in Rust" involves living in (4) and heavily using constructors and destructors, whereas I tend to live in (3) and don't use constructors or destructors. (I do use initializers, which are the simple version of constructors where things can be assigned to constant values that do not require code execution and do not involve "resources" -- basically, could you memcpy the initial value of this struct from somewhere fixed in memory). Now the thing that is weird is that maybe "programming in Rust" has changed since last time I argued with Rust people. It seems that it used to be the sentiment that one should minimize use of unsafe, that it should just be for stuff like lockfree data structure implementation or using weird SIMD intrinsics or whatever, but people in this thread are saying, no man, you just use unsafe all over the place, you just totally go for it. And with regard to that, I can just say again what I said above, that if your main way of using memory is some unsafe stuff wrapped in a pretend safe function, then the program does not really have the memory safety that it is claiming it does, so why then be pretending to use Rust's checking facilities? And if not really using those, why use the language?
So that's what I don't get here. Rust is supposed to be all about memory safety ... isn't it? So the "spirit of Rust" is something about knowing your program is safe because the borrow checker checked it. If I am intentionally programming in a style that prevents the borrow checker from doing its job, is this not against the spirit of the language?
I'll just close this by saying that one of the main reasons to live in (3) and not do RAII is that code is a lot faster, and a lot simpler. The reason is because RAII encourages you conceptualize things as separately managed when they do not need to be. This seems to have been misunderstood in many of the replies above, as people thinking I am talking about particular features of Rust lifetimes or something. No, it is RAII at the conceptual level that is slow.
> We had a keynote at Rustconf about how useful generational arenas are as a technique in Rust.
If that's the one I am thinking of, I replied to it at length on YouTube back in 2018.
If you get something working, I'd love to look at it though! Especially if you're building in a tagless final interpreter style. I find that approach extremely elegant.
I tried to build a system that not only recognizes regular languages, but also serves as a parser for them (a la Parsec).
The latter approach pushes you to support something like fmap, but the whole derivatives-based approach needs more 'introspection' so support general mapping via fmap (ie a->b) is out, and you can only support things that you have more control over than functions.
(And in general, I am doing bifunctors, because I want the complement of the complement be the original thing.)
Sorry, if that's a bit confused.. If I was a better theoretician, I could probably work it out.
I haven't touched the code in a while. But recently I have thought about the theory some more. The Brzozowski derivative introduced the concept of multiplicative inverse of a string. I am working out the ramifications of extending that to the multiplicative inverse of arbitrary regular expressions. (The results might already be in the literature. I haven't looked much.)
I don't expect anything groundbreaking to come out of that, but I hope my understanding will improve.
> And these particular features just don't really pull their weight IMO. They are performance footguns, and IMO, are also tricky to reason about inside of regex syntax.
Well, in theory I could 'just' write a preprocessor that takes my regex with intersection and complement and translates it to a more traditional one. I wouldn't care too much if that's not very efficient.
I'm interested in those features because of the beauty of the theory, but it would also help make production regular expressions more modular.
Eg if you have a regular expression to decide on what's a valid username for someone to sign up to your system. You decide to use email addresses as your usernames, so the main qualification is that users can receive an email on it. But because they will be visible to other users, you have some additional requirements:
'.{0,100} & [^@]@[^@] & not (.(root|admin|<some offensive term>).@.) & not (.<sql injection>.*)'
That's a silly example. I think in production, I would be more likely to see something as complicated as this in eg some ad-hoc log parsing.
> The issue is that building a production grade regex engine---even when it's restricted to regular languages---requires a lot more engineering than theory.
Amen to that!
We don't have to tumble down that rabbit hole though. If someone wrote a ripgrep in Cython and matched performance, then I would definitely learn something.
> "ripgrep needs 'low level tricks' to be fast and a language that allows them, such as Rust"
I might use that, sure. I think my point above was that I had to riff off of someone else's language. But I think we covered that. :-) In any case, yes, that phrasing sounds better.
Anyway, good chatting with you, good night!
Rust does case (3) with arenas. In your frame loop you'd create or reset an arena and then borrow it. That would limit lifetime of its items to a single loop iteration. The cost would be only in a noisy syntax with `'arena` in several places, but other than that it compiles to plain pointers with no magic. Lifetimes are merely compile-time assertions for a static analyzer. Note that in Rust borrowing is unrelated to RAII and theoretically separate from single ownership.
Rust's `async fn` is one case where a task can hold all of the memory it will need, as one tagged union.
As for unsafe, the point is in encapsulating it in safe abstractions.
Imagine you're implementing a high level sandbox language. Your language is meant to be bulletproof safe, but your compiler for that language may is in C. The fact that the compiler might do unsafe things doesn't make the safe language pointless.
Rust does that, but the safe language vs unsafe compiler barrier is shifted a but, so that users can add "compiler internals" themselves for the safe language side.
eg. `String` implementation is full of unsafe code, but once that one implementation has been verified manually to be sound, and hidden behind a safe API, nobody else using it can screw it up when eg concatenating strings.
I know it seems pointless if you can access unsafe at all, so why bother? But in practice it really helps, for reasons that are mostly social.
* There are clear universal rules about what is a safe API. That helps review the code, because the API contract can't be arbitrary or "just be careful not to…". It either is or isn't, and you mark it as such. Not everything can be expressed in terms of safe APIs, but enough things can.
* Unsafe parts can be left to be written by more experienced devs, or flagged for more thorough review, or fuzzed, etc. Rust's unsafe requires as much diligence as equivalent C code. The difference is that thanks to encapsulation you don't need to write the whole program with maximum care, and you know where to focus your efforts to ensure safety. You focus on designing safe abstraction once, and then can rely on the compiler upholding it everywhere else.
I do think this is probably true, and I know you do care about this! The thing is...
> The code that I write just looks way different from the code you guys write, the things I think about are way different, etc.
This is also probably true! The issue comes when you start describing how Rust code must be or work. There's nothing bad about having different ways of doing things! It's just that when you say things like "since then you are putting unsafe everywhere in the program," when that's empirically not what happens in Rust code.
> Using a bump allocator in the way you just did, on the stack for local code that uses the bump allocator right there, is semantically correct, but not a very useful usage pattern.
Yes. I thought going to the simplest possible thing would be best to illustrate the concept, but you're absolutely right that there is a rich wealth of options here.
Rust handles all four of these cases, in fairly straightforward ways. I also agree that 3 isn't often talked about as much as it should be in the broader programming world. I also have had this hunch that 3 and 4 are connected, given that the stack sometimes feels like an arena for just the function and its children in the call graph, and that it has some connection to the young generation in garbage collectors as well, but this is pretty offtopic so I'll leave it at that :)
Rust doesn't care just about 4 though! Lifetimes handle 3 as well; they ensure that the pointers don't last longer than the arena lives. That's it.
I don't have time to dig into this more, but I do appreciate you elaborating a bit here. It is very helpful to get closer to understanding what it is you're talking about, exactly. I think I see this differently than you, but I don't have a good quick handle on explaining exactly why. Some food for thought though. Thanks.
(Oh, and it is the one you're thinking of; I forgot that you had commented on that. My point was not to argue that the specifics were good, or that your response was good or bad, just that different strategies for handling memory isn't unusual in Rust world.)
Sure, but my point is, when most things have lifetimes tied to the same arena, this becomes a almost a no-op. Both in the sense of, you are not really checking much (as Ayn Rand said, 'a is 'a), and you're paying a lot in terms of typing stuff into the program, and waiting around for the compiler to be not usefully checking all these things that are the same. Refactoring a program so that most things' lifetimes are the same does not feel to me like it's in the spirit of Rust, because then why have all these complicated systems, but maybe you feel that it is.
There is a bit of a different story when you are heavily using threads, because you want those threads to have allocators that are totally decoupled from each other (because otherwise waiting on the allocator becomes a huge source of inefficiency). So then there are more lifetimes. But here I am not convinced about the Rust story either, because here too I think there are simpler things to do that give you 95% of the benefit and are much lower-friction.
What Rust does is reduce the amount of code that's memory unsafe, that needs to be triply reviewed and audited. Reduction of the scope of high-scrutiny code is the single most leveraged thing that can be done to improve code quality in a large, long-running project. Why? Because it lets you do careful, time-consuming analysis on a small part of your codebase (the bits that are marked unsafe), then scale the analysis up to the rest of your code.
> These stories are mutually inconsistent. Either you have memory safety or you don't.
This is... what can I say. This is simply incorrect. It pains me to say this as a fan of your games but you really don't seem to have any idea what you're talking about.
No, that's not how this works. You write the unsafe code in one place and make sure it's correct (just like you'd do in C or Jai), and then you wrap it in a function signature that lets the compiler apply its memory safety checks to all the places that call it (this is what Rust gives you over C).
This is still a meaningful improvement to memory safety over C. The compiler checks the majority of your program; if you still see memory bugs now you only have a small subset to think about when debugging them.
This is also not very different from a hypothetical language with your "actual" memory safety- in that case, you still have to consider the correctness of the compiler checks themselves. Rust just takes a more balanced and flexible approach here and moves some of that stuff out of the compiler. (In fact this simplifies the compiler, which increases confidence in its correctness...)
Rust has been very clear about all this from the beginning. If you are still reading people's claims about Rust memory safety a different way, that's on you.
> Why wouldn't I use a lower-friction language with a faster compiler?
That's totally up to you! I don't have a problem with people using other languages for these kinds of reasons. My goal here is not to convert you, but to cover more accurately what Rust is and isn't capable of. (At the root of this thread, that's things like "writing fast software with effective memory management styles.")
My point is that those memory safety checks are now meaningless.
> This is still a meaningful improvement to memory safety over C.
No, it really isn't. What you are describing is almost exactly what you get in C.
Please take some time and think about this a bit more. Please think about how code review processes work, how audits work, how human attention spans work. Please think about how people endlessly nitpick small PRs but accept large ones with few comments. What unsafe does is make it easy to spot the small bits of critical code to nitpick while not having to worry about safety for the rest.
You're better than this, Jon.
This may or may not be something you care about, but it is certainly a meaningful tool that is quite useful to me, including when I use your type (3) style described in the sibling thread.
For reference, I am also the author of the regex crate. The only unsafe it uses specific to finite automata is to do explicit elimination of bounds checks in the core hybrid NFA/DFA loop.
As an old C programmer, the difference between an array index and a pointer caught me by surprise. In C a pointer is just an unchecked offset into memory. A real array index is just a unchecked offset into ... maybe a smaller chunk of raw memory.
But in rust, an array index is something that comes with additional bounds checking overheads with every use. And the memory it points to is also constrained - the entire array has to be initialised, so if the index passes the bounds check you are guaranteed rusts memory consistency invariants are preserved. Indexes also allow you to escape the borrow checker. If you own the slice, there is no need to prove you can access an element of the slice.
So yeah, you can use indexes instead of pointers, but for rust that's like saying you can use recursion instead of iteration. Indexing and pointers are two very different things in rust.
If bounds checks prove to be a problem, you can explicitly elide them. Indeed, Rust's regex does just that. :-)
You could instead go with a derivatives approach.
About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you?
One way to handle them that works well when the characters in your classes are mostly next to each other unicode, is to express your state transition function as an 'interval map'
What I mean is that eg a hash table or an array lets you build representations of mathematical functions that map points to values.
You want something that can model a step function.
You can either roll your own, or write something around a sorted-map data structure.
Eg in C++ you'd base the whole thing around https://en.cppreference.com/w/cpp/container/map/upper_bound (or https://hackage.haskell.org/package/containers-0.4.0.0/docs/... in Haskell.)
The keys in your sorted map are the 'edges' of your characters classes (eg where they start and end).
Does that make sense? Or am I misunderstanding the problem?
> I personally always get stuck at how to handle things like captures [...]
Let me think about that one for a while. Some Googling suggests https://github.com/elfsternberg/barre but they don't seem to support intersection, complement or stripping prefixes.
What do you want your capture groups to do? Do you eg just want to return pointers to where you captured them (if any)?
I have an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm might work.
https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture groups.
I think a common sentiment among Rust programmers would instead phrase this as, "the complicated system we designed to find bugs keeps yelling at us when we have lots of crazy lifetimes flying around, so presumably designs that avoid them might be better."
In this sense, even for someone who doesn't feel the borrow checker is worth it in their compiler, this can just be taken as a general justification for designs in any language that have simpler lifetime patterns. If they're easier to prove correct with static analysis, maybe they're easier to keep correct by hand.
I mean specifically in the context of derivatives. IIRC, the formulation used in Turon's paper wasn't amenable to large classes.
Yes, interval sets work great: https://github.com/rust-lang/regex/blob/master/regex-syntax/...
This is why I asked if a production grade regex engine based on derivatives exists. Because I want to see how the engineering is actually done.
> What do you want your capture groups to do? Do you eg just want to return pointers to where you captured them (if any)?
Look at any production grade regex engine. It will implement captures. It should do what they do.
> I have an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm might work.
Nothing about Viterbi is fast, in my experience implementing it in the past. :-)
> https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture groups.
It looks like it does, and in particular see: https://github.com/google/redgrep/blob/6b9d5b02753c4ece17e2f...
But that's only for parsing the regex itself. I don't see any match APIs that utilize them. I wouldn't expect to either, because you can't implement capturing inside a DFA. (You need a tagged DFA, which is a strictly more powerful thing. But in that case, the DFA size explodes. See the re2c project and their associated papers.)
If I'm remembering correctly, I think the problem with derivatives is that they jump straight to a DFA. You can't do that in a production regex engine because a DFA's worst case size is exponential in the size of the regex.
Oh, that's interesting! Because I actually worked on some approaches that don't jump directly to the DFA.
The problem is the notion of (extended) NFA you need is quite a bit more complicated when you support intersection and complement.
The seem similar to closed languages with a disjunct and conjunct
Though I don't think I will, I was considering adding zdd or bdd to a PEG, to provide that conjunct
ofc, sat solver can represent a regex with conjuncts, but is this a good way of going about it, particularly with unbounded strings??
Would love to hear your thoughts on that