This is one advantage of Ada, where parameters are abstractly declared as "in" or "in out" or "out". The compiler can then decide how to best implement it for that specific size and architecture.
At the minimum, the compiler can look at the size of the type to decide whether copying or indirection makes more sense. The size is stable for a given parameter signature and architecture, so the ABI is stable.
But also, the ABI only matters between two pieces that are separately compiled. A static binary optimized at link-time doesn't have to care.
It can return multiple values, so this doesn’t matter much for value types, but it would be nice to be able to specify that a pointer arg is an out-param sometimes and enforce that it is not read from while handling allocation in the caller.
So far as I can tell, it's not quite the same thing since these still have pointer semantics (and thus have to deal with aliasing etc). The in/out approach is more generic, since "in" can map to a pointer where it makes sense, and to a copy where it does not.
Better yet when you prohibit such arguments from aliasing (or at least make no-alias the default) - now the compiler can also implement "in out" by copying the value back and forth, if it's faster than indirection.
Dlang can also qualify parameters as in, out, and inout; although I don't know to what degree the compiler is able to use that for optimization purposes (it is used for safety checks IIRC)
The difference between passing by reference vs. by value is observable when comparing pointers to the original vs. to the argument. This difference may be unobservable in Ada though (not sure), so Ada would have more freedom choosing between the two.
A question to the Rust experts, would lifetime annotations 'a in Rust have similar benefit as "in" or "in out" or "out" in Ada and other languages? With the additional benefit in Rust where the compiler can deduce those automatically for most cases?
As a sibling comment points out, "in" is effectively equivalent to "&T", and "inout" is effectively equivalent to "&mut T". Rust is missing purely "out" parameters, but that isn't a very common case, and I'm not sure how much value there is in saying "this reference can't be read" since references are always guaranteed to be valid in Rust.
Out params are needed to ensure zero-copy in-place initialization of large objects, i.e. what C++ does with placement new. You can sort of fake it with MaybeUninit<> https://doc.rust-lang.org/std/mem/union.MaybeUninit.html but it's quite fiddly, requires unsafe code, and has undesirable effects on the layout of containing objects.
My first thought was "now what is the calling convention for float parameters again? they are passed in registers right? the compiler can probably arrange so they don't have to actually be copied" and then I realized it will probably even inline it.
Anyway, assuming it's not inlined I would guess pass-by-copy, maybe with an occasional exception in code with heavy register pressure.
Edit: Actually since it's a structure, the calling convention is to memory allocate it and pass a pointer, doh. So it should actually compile the same.
> Edit: Actually since it's a structure, the calling convention is to memory allocate it and pass a pointer, doh. So it should actually compile the same.
Depending on calling convention, the structure may be spread out into registers.
> Edit: Actually since it's a structure, the calling convention is to memory allocate it and pass a pointer, doh. So it should actually compile the same.
FWIW the AMD64 SysV v1.0 psABI allows structures of up to 8 members to be passed via registers. Though older revisions limit that to 2 (and it's unclear whether MS's divergent ABI allows aggregates to be splat at all.
As sad as it's unsurprising, it does not look like LLVM (linux?) has followed up, on godbolt a 2-struct passes everything via registers but a 3-struct passes everything via the stack. Maybe there's a magic flag to use the 1.0 ABI, but a quick googling didn't reveal one. ICC doesn't seem to have followed up either.
How can an abi allow but not require passing them via registers? Isn't the point of a convention that everyone does it the same way? Other wise the caller could put it on the stack and the callee look for it in a register?
Actually reading the word abi made a little neuron light up. To what extent does rust even follow that abi?
Because rust is a compiled language and therefore it means you compile your code to a certain architecture. Who told you about syscalls ? There are systems not using syscalls
There are no syscalls or equivalent operating system calls in the code paths measured. The architecture is also independent of the operating system, with exceptions in some languages for the calling convention (not in rust, afaik, or at least rust makes no guarantees there.)
However, in practice Rust's calling convention does actually depend on the operating system. So on Linux Rust will make use of the stack red zone, while on Windows it doesn't. (Also some codegen in LLVM depends on the operating system)
The dependency is on the ABI, which can be OS-dependent. Also, it is a depressingly manual optimization to do: compilers don't know when it is safe to change a reference to a copy (for example) without an analysis of future code that they don't do.
C and C++ are also set up such that the compiler can do that optimization, they just don't. I'm pretty sure the Rust compiler is in the same boat - has the information, but doesn't do the optimization.
I'd be interested to know what the benchmarks of the two rust solutions are when inlining is disabled so we can get an idea of the different performance characteristics of each function call even if it's not a very realistic scenario.
The other question I have is which style should you use when writing a library? It's obviously not possible to benchmark all the software that will call your library but you still want to consider readability, performance as well as other factors such as common convention.
I would go with the version that gives the clean user interface (that is, by copy in this case). If it turns out that the other version is significantly more performant and this additional performance is critical for the end users consider adding the by-borrow option.
The clarity of the code using a particular library is such an big (but often under-appreciated) benefit that I would heavily lean in this direction when considering interface options. My 2c.
The assumption behind such arguments is when a performance problem does arise, a profiler will point to a single, easy to fix, smoking gun. Unfortunately this is not always the case. Performance problems can be hard to diagnose and hard to fix. A lot of damage has been done by unexamined / dogmatic "root of all evil" mantra.
In the vast majority of situations (1) you'll prematurely optimize in the wrong place and (2) yes the profiler will point to a single, easy-to-fix smoking gun.
Situations otherwise are the exception, rather than the rule, and it takes an expert to (1) recognize those situations and (2) know exactly how to write optimized code in that situation.
That's why "don't prematurely optimize" is a good rule of thumb - because it works the majority of the time, and it takes experience to know when not to apply it.
> In the vast majority of situations [..] yes the profiler will point to a single, easy-to-fix smoking gun.
[citation needed]
This claim depends hugely on the industry you're actually working in and the problem space. Things like UIs & games basically never have a single, easy-to-fix smoking gun. The entire app is more or less a hotspot - be it interactive performance, startup performance, RAM usage, or general responsiveness.
And once you're gone down the route of "build it first, optimize it later" you're pretty much fucked when you get to the "optimize" step because now your performance mistakes are basically unfixable without a rewrite - every layer of your architecture has issues that you can't fix without drastic overhauls. It would have been much easier to do some up-front measurements, get some guidelines in place (even if they aren't perfect), and then build the app.
This is ridiculous. If you had the knowledge, you'd apply it, and you can't acquire it without practice, which is going to involve heuristics (which you falsely call "dogma" in order to ad-hominem my argument) like this one, which exists precisely because you need something for when you don't have the specialized domain expertise.
> The true root of all evil is unexamined dogma.
This is so absurd that it doesn't deserve a reply.
I agree in general, but the side-effect of doing this is that no matter how fast your hardware gets, your software will always end up optimized to the new hardware. So over time your software gets slower and slower but performance stays consistent as hardware gets faster.
This advice hinges hugely on what "start simple" really means. There's a ton of counter-examples here where that just isn't true at all depending on what you're calling "simple". In particular JIT'd languages can be especially problematic here. An example would be using Java's Streams interfaces to do something that could be done without much difficulty with a regular boring ol' for loop. At the end of the day you're hoping the JIT will eventually convert the streams version into the same bytecode the for loop version would have started with. But it won't do that consistently, and you've still wasted time before it did so.
Trusting the compiler also means knowing what the compiler actually understands & handles vs. what's a library-provided abstraction that's maybe too bloated for its own good and that quickly becomes "not simple" depending on your language of choice.
I don’t feel like this gave a satisfactory answer the question. Since everything was inlined, the argument passing convention made no difference in the micro benchmarks. But what happens when it does not inline? Then you would actually be testing by-borrow be by-copy instead of how good rust is at optimizing.
I feel like they got excited by their C++ code being so much slower and curious about the "weird" C++ result and forgot to figure out the original question.
Rust - Windows - By-Copy: 14124, By-Borrow: 8150
C++ - Windows MS Compiler - By-Copy: 12160, By-Ref: 11423
C++ - Windows LLVM 15 - By-Copy: 4397, By-Ref: 4396 Delta: -0.0227428%
So it appears that C++ - Windows LLVM 15 beats Rust by large margin.
In Rust it's considered idiomatic to pass things by-value whenever you can. Usually this is also the most performant option, since it avoids dereferencing in the callee.
Of course, if your struct is truly enormous, you may want to break this rule to avoid large copies. But in that case you probably want to Box<T> the struct anyway.
Of course, if your struct contains something that can't be copied--like a Vec<T>--you'll have to decide whether to clone the whole struct (and thus the vector in it), pass the struct by-borrow, or find some other solution.
> Safely borrowing things by reference is one of Rust's headline features
Sure, but it's worth noting that references in Rust do not exist merely to avoid passing by-value. They also exist to make it easier to deal with Rust's ownership semantics: they let you pass things to a function without also requiring the function to "pass back" those things as returned values. In other words, references let you do `fn foo(x: &Bar)` rather than `fn foo(x: Bar) -> Bar`. This is a unique and interesting consequence of languages with by-default move semantics.
When the compiler can see both the callee and the caller (the most common case), why should it even matter? If you pass by value, but don't actually do anything that mutates the copy, and there are no aliasing concerns, surely the compiler can make it by-ref under the hood?
(The other direction is trickier, since by-ref implies the desire to observe aliasing, even though that's usually not expected in practice - but the compiler cannot tell.)
> Then you would actually be testing by-borrow be by-copy instead of how good rust is at optimizing.
I don’t think the question is actually: “what is faster in practice, a by-copy method call or a by-value method call”, I think the question is: “as an implementer, which semantics should I choose when I’m writing my function”.
For the second question: “Rust is usually pretty good at aggressively inlining, so… if you’re willing to trust Rust’s compiler, you’re often okay going with by-copy implementations, but you should keep an eye on it”. Whereas, as you note, for the first question it’s not an answer.
But, I do think if someone was going to put more work into it I’d be very curious what the answer to the first question is. If I’m choosing to implement with by-copy semantics and trusting the Rust compiler to hopefully inline things for me, I’d like to know the implications in the cases when it doesn’t.
Blog author here. This feels like the best summary in this comment section.
The root question is indeed “what semantics should I use”. And the answer I came up with was “the compiler does a lot of magic so by-copy seems pretty good”. I agree with the previous commenter this is not a satisfying conclusion!
My experience with Rust is that it requires a moderate amount of trust in the compiler. Iterator code is another example where the compiler should produce near optimal code. Emphasis on should!
When value size is small (whatever "small" means for particular architecture) I'd say "trust the compiler" suggestion is reasonable. When the size grows there should be no more "trust" unless compiler can decipher if it is safe to use ref instead of value basing on value size (we assume that the function does not mutate the value).
> When the size grows there should be no more "trust" unless compiler can decipher if it is safe to use ref instead of value basing on value size
I believe that the Rust compiler at least does exactly that. Large structs will be passed by reference under the hood even if it passed by value in the code. I suspect C++ compilers do the same, although I'm not sure about that.
>"Were the other benchmarks run in debug mode / with optimizations turned off or something like that?"
Why would I do something like that? Of course all builds are release mode, optimize for speed.
Rust - Windows - By-Copy: 14124, By-Borrow: 8150
C++ - Windows MS Compiler - By-Copy: 12160, By-Ref: 11423
C++ - Windows LLVM 15 - By-Copy: 4397, By-Ref: 4396
>"Why is performance so much better in this case?"
Not sure and not in a mood to investigate. I do know if cache locality and branch prediction stars line up properly the performance difference can be staggering. Maybe LLVM has accomplished something nice in this department.
No need to bother with LLVM16 and / or GCC. Enabling avx2 for Clang compiler produced following results that are more or less in line with what was expected.
Either is way faster than the result from the original post and no rust does non win this "competition". C++ is a bit faster (see also the results from other poster above) but not by much.
Such stark difference in performance is really fishy and needs a deeper analysis. I just checked it with different compilers (all based on LLVM) and here are the results:
Is this Windows or Linux? Also what CPU? Your results for rust on LLVM15 are pretty much close to mine but clang++ on LLVM15 is almost twice as slow. I really want to find reason.
Sorry for being dumb, I thought I've enabled it in ./cargo/config.toml for rust. Checked it again and it appears that I did not (the file name was wrong). -march=native for CLang also did better than just avx2
It may be the default fp mode for msvc is causing C++ to suffer here ( https://learn.microsoft.com/en-us/cpp/build/reference/fp-spe... ). It looks like the default behavior is quite conservative it what it allows to happen - like it won't even use FMAs with the default behavior?
> * Sprinkling & around everything in math expressions does make them ugly. Maybe rust needs an asBorrow or similar?
Do you mean AsRef, or do you mean magic which automatically borrows parameters and is specifically what rust does not do any more than e.g. C does?
Though you can probably get both if the by-ref version is faster (or more convenient internally): wrap the by-ref function with a by-value wrapper which is #[inline]-ed, this way the interface is by value but the actual parameter passing is byref (as the value-consuming wrapper will be inlined and essentially removed).
It's compiled, so, without any investigation at all, I would have been disappointed if there were any significant difference in the code emitted in these cases. I would expect the compiler to do the efficient thing based on usage rather than the particular syntax. I may have too much faith in the compiler.
I'd expect your claim to be true whenever the callee is inlined into the caller. In this case, the compiler has all the relevant information at the right point in time. As other commenters have pointed out, by enabling inlining the author has gone down a rabbit hole somewhat unrelated to the question, because any copies can be simply elided.
If there's no inlining at play, I'd expect vast differences to be possible. For example, imagine a chain of 3 functions - f calls g, g calls h, where one of the arguments is a 1kB struct and the options are passing by copy or by borrowing. In this case, each stack frame will be 1kB in size in the copy case and there will be a large performance overhead as opposed to the by-reference case. One would expect simply calling the function to be similar in overhead to an uncached memory load.
Within a single crate the inlining is possible, with multiple crates it's only possible with LTO enabled (and I'm not sure how _probable_ it is that the inlining would occur).
In either case, the difference between a 32 byte and 8 byte argument in terms of overhead is likely meaningless - the sort of thing to be optimized if profiling says it's a problem as opposed to ahead of time.
> Within a single crate (more specifically, codegen unit) the inlining is possible
Cross-crate inlining happens all the time. In order to be eligible for inlining, a function needs to have its IR included in the object's metadata. This happens automatically for every generic function (it's the only way monomorphization can work), and for non-generic functions can be enabled manually via the `#[inline]` attribute (which does not force inlining, it only makes it possible to inline at the backend's discretion).
However, as you, say, if you have LTO enabled then "cross-crate" inlining can happen regardless, since it's all just one giant compilation unit at that point.
At the VERY end of the article, the author points out "Oh, btw, I used MSVC for the C++ compilation, when I used clang things changed!"
So, what the author actually measured was the difference between llvm and msvc throughout the article. Particularly when they talked about rust being better at autovectorization than C++.
Incorrect. Clang C++ vs MSVC C++ is very comparable, and noticeably worse for f64 by-ref. Clang C++ is still slower than Rust by a large margin. Using Clang C++ throughout would not change any conclusion (or lack thereof).
This is not really surprising in such a case. The Rust compiler is pretty good at optimizing out uneeded copies. Here it does see that the copied value is not used after the function call, so it should simply not emit the copies in the final assembly.
For this code, the compiler inlined the call. So there should be no difference between pass by copy or pass by reference, which is what was measured. Where it could matter is when the code isn’t inlined. But with small structs it might not matter all that much.
It does sometimes matter though. One optimization I’ve seen in a few places is to box the error type, so that a result doesn’t copy the (usually empty) error by value on the stack. That actually makes a small performance difference, on the order of about 5-10%.
The general usability impact matters slightly less than it looks here, in part because the `do_math` with references in the article has two extra &s, and in part because methods autoreference when called like x.f().
Performance-wise, if you're likely to touch every element in a type anyway, err on the side of copies. They are going to have to end up in registers eventually anyway, so you might as well let the caller find out the best way to put them there.
Anyone know why seemingly knowledgeable people (like the person who wrote this article) don't use micro benchmarking frameworks when they run these tests?
Also, whenever you do one of these, please post the full source with it. There's no reason to leave your readers in the dark, wondering what could be going on, which is exactly what I'm doing now, because there's almost no excuse for c++ to be slower in a task than rust--it's just a matter of how much work you need to put in to make it get there.
I see now. I looked twice. I think most people stop after a section called "Conclusion" that ends with "Thanks for reading." It doesn't help that the formatting then leaves a large gap between sections that doesn't indicate there's more after that.
For C++ I guess you could make the claim that it's just too annoying to take a dependency on something like google-benchmark or whatever, since C++ dependency management is such a mess to deal with in general.
But yeah I have no idea why a benchmark framework wasn't used for Rust.
Note that this is from 2019, so it's probably worth re-benchmarking to see if anything has changed in the interim. Can we get the year added to the title?
The benchmarks lack the standard deviation, so the results may well be equivalent. Don't roll your own micro-benchmark runners.
References may get optimized to copies where possible and sound (i.e. blittable and const), a common heuristic involves the size of a cache line (64b on most modern ISAs, including x86_64).
Using a Vector4 would have pushed the structure size beyond the 64b heuristic. You would also need to disable inlining for the measured methods.
It was also (needlessly) using 2 different compilers, MSVC and LLVM. This is just a bad way to compare things all around.
And, for simple operations like this, you really should just look at the assembly output. If you are only generating 20ish instructions, then look at those 20 instructions rather than trying to heuristically guess what is happening.
There is no single answer to this question because it's going to depend completely on call patterns further up. Especially in regards to how much of the rest of the running program's data fits in L1 cache, and most especially in regards to what's going on in terms of concurrency.
The benchmark made here could completely fall apart once more threads are added.
Modern computer architectures are non-uniform in terms of any kind of memory accesses. The same logical operations can have extremely varied costs depending on how the whole program flow goes.
This is one of the problems I have with writing rust code. You have to think about so many mundane details that you barely have time left to think about more important and more interesting things.
Well, it is a systems programming language. Thinking about exactly how the language passes bits around is the whole point. Rust should specify a stable ABI already so that everyone can form a good mental model of what their code becomes once compiled.
True, I probably was using Rust for the wrong type of problem, i.e. was hoping to write a user-level application with a graphical UI at the time.
Rust is probably better used for writing fast low-level libraries that you call from higher level languages, possibly with a garbage collector, so you don't waste time thinking about memory management while you design/write your high-level application.
My (brief) experience with Rust was that, while I had to struggle to learn the borrow-checker, I didn't have lots of "mundane details" to worry about - if any, less than C(++).
Having written a lot of C, you spend basically all your time thinking about "mundane details", and worse, if you make a mistake, you often don't know you made a mistake until it's running on some customer's servers and you just got a ticket escalated 3 times up to you with vague information about crashes rarely happening. Good luck remembering which bit of code you wrote 6 months ago that may be causing the problem.
I'll take Rust shouting at me for missing "mundane details" any day of the week.
As a Rust beginner that likes to learn the hard way I think I have some insights why Rust seems cumbersome and/or hard for programmers trying it.
Rust uses syntax that feels familiar but means completely different things than in pretty much any other language.
For example '=' doesn't mean assign handle or copy. It by default means move.
'let' doesn't mean create a name for something. It means create physical space for something (of known size) that can be moved into or moved out of.
You don't deal with objects and values of primitive types. Instead everything in Rust is a value. When you move, you move the value. If you compare, you compare by value. If you pass something from variable into function, you move the value into the function.
And when the space where you keep the value goes out of scope value dies with it if it wasn't moved out to somewhere else.
Scope for variables (which are just named spaces for values) ends with the end of the block, but some values, created by functions and returned from them, if they are not moved into any named space, can die sooner, even in the middle of the line where they were acquired from function call.
Everything else stems from that fixed size moved value semantics. If you don't want to move the value into the function when you call it you need to pass something else instead, so you create and pass in the borrow. But you have to ensure that the value doesn't die or get moved anywhere (even inside the container you borrowed from) before borrows to it all die.
Because of this you are better off with borrows that are short lived and local. Often it's better to keep the index of an element of a Vec instead of the borrow of this element. If you must create types that contain borrows you must know that they become borrows themselves and you need to treat them exactly the same trying to limit their scope and life time.
It's hard when you come from any other language because borrows are superficialy similar to pointers or references to objects. So you try to use them as such. And crash into the compiler because they are not that. What's worse their syntax is very minimalistic which triggers intuition that they must be fast and optimal solution for many problems which they sure can be once you fully internalize their limitations but not a moment sooner.
Another thing is that values in Rust must have the fixed size. So even as simple thing as a string requires a bit of hackery. Basically in Rust the default strategy to have something of variable size is to allocate it on the heap and treat pointer to it (possibly with some other fixed sized data like length) as the fixed sized value you can move around clone and borrow.
So if you want to have semantics you know from other languages you can't just use basic Rust syntax.
You need constructs such as Box and Rc, Cell, RefCell. Make your things clonable and sometimes even copyable and avoid creating borrows whenever possible initially. When you do it Rust becomes as flexible as any other language and you can use it pretty much just as comfortably. Then the value semantics shines as you can very easily compare your data by value, order it, create operators for it, create has for it so you can keep it in HashMaps and HashSets. Then it's delightful.
My advice is when you create a long lived type just wrap it in Rc and treat this Rc as your 'object'. And avoid borrows in your types unless you have a very good performance (measured) reason to have them or you are creating something obviously dependant and usually short lived like an iterator.
If you further wrap Rc in an Option you can set crosslinks and backlinks to None when you are dropping your data to get rid of the problem of crosslinks or backlinks making reference-counting leak memory. Then you just need to be mindful to not loose handle to a cycle of your nodes before you break the cycle by setting some crosslinks to None.
You can fairly easily refactor your almost-tree code to adapt it to that additional Option wrap.
Of course you might instead opt to introduce some garbage collector crate into your project. They usually provide garbage collected Rc equivalent, which makes swapping it out very easy.
Rc's are really very useful first approach to making anything complex in Rust.
I usually have something like
struct NodeStruct {
my_data: i32,
link: Node
}
and
struct Node(Rc<NodeStruct>);
or
struct Node(Option<Rc<NodeStruct>>);
if I need cross-links.
Great thing is you can then add 'methods' to your type with
impl Node {}
Or define operators and other traits with:
impl Add<Node> for Node {}
Sometimes, when I need mutability I even wrap the NodeStruct in RefCell.
It seems like a lot of wrappers but thanks to them you can have very nice code that uses this type that has pretty much 'normal modren language' semantics + value semantics and is still blazing fast.
When you implement Ord, Eq, Hash they all go through all the wrappers and let you treat your final type Node as a comparable, sortable, hashable and cheaply clonable value. Dereferencing also goes through all or most of the wrappers automatically.
Sibling and parent pointers are almost universally a sign that an abstract data structure (and associated algorithm) has been mistaken for concrete. The exception that comes to mind first is Knuth's dancing links, and its obscurity is an indication of the rarity of actually needing these pointers. In any case, it's also a poster child for using indices rather than pointers.
Main objects in my program are expression trees. I manipulate them, cut them, merge them, compare them, splice one into the other. Rc's enable me to have full flexibility and share tremendous amount of data across objects in my program.
Rust is absolutely wonderful language for this problem thanks to Rc's, enums, value semantics, auto-deriving traits and ability to implement traits for existing types and of course speed.
I'm not implementing specific algorithms. I'm making them up as I go although I used some simple ones like topological sort or A* that eventually turned into just breadth search because I have no idea how far I am from the solution.
> I'm not implementing specific algorithms. I'm making them up as I go
It's mindboggling to me that people are using a systems programming language for mathematical research, especially if they don't know yet what the final algorithms will look like.
> For example '=' doesn't mean assign handle or copy. It by default means move.
Some complain about this, but the fact is there's no such thing as a zero-overhead "copy" for non-trivial types. C++ started out with = meaning clone the object which was an even bigger footgun, and support for move had to be added after the fact.
Yeah. Making = mean copy is a really bad idea. I very much like the solution in Rust where attempt to move out something that can't be moved out results in automatic copy if the type implements trait Copy.
It's very elegant solution for simple, small data types. But it further occludes how meaningfully Rust is different from everything else because thanks to that = sometimes does mean copy.
Rc, Cell & RefCell are suppose to be rare. For example I've got 2,000 line Rust program in front of me and I've used Arc 3 times and RWLock 1 time, that's all.
You need to structure your program as a Directed Acyclic Graph (DAG), with things interacting only with the things below them in the graph.
Then occasionally you might need to break the DAG structure by using Rc, Cell & RefCell, etc...
The thing is not everything can be expressed as a DAG.
And finding it towards the end of writing your program after hours of fighting with borrow checker is extremely unpleasant.
And I don't think I ever landed in the situation where I could fix the discrepancy by sprinkling in few Rc, RefCells and such.
So I prefer to write with RefCells from the start and when I got the thing working and I am ambitious enough then I look at which parts could be borrows instead and I swap them out.
> How do you express as a DAG a tree where nodes need to keep references to their children and parents?
Rewrite your program in a form where it does not contain a tree.
If you want an actual tree as a data structure, see the trees crate.
> Rust is not Forth. I can write whatever I want and there's nothing wrong with that.
And other people write Haskell code in Python :p. If your code style doesn't match the language you are using you are going to have a lot of unnecessary friction.
> Blech! Having to explicitly borrow temporary values is super gross.
I don’t think you ever have to write code like this. Implement your math traits in terms for both value and reference types like the standard library does.
Go down to Trait Implementations for scalar types, for instance i32 [1]
impl Add<&i32> for &i32
impl Add<&i32> for i32
impl Add<i32> for &i32
impl Add<i32> for i32
Once you do that your ergonomics should be exactly the same as with built in scalar types.
You are comparing two completely different compilers; I wouldn't worry all that much about the difference between rust and C++. If you do want to compare them directly, why not use LLVM for C++ as well? That will highlight any language-specific differences.
True, that does work for traits. But it's super annoying if you have to write multiple copies of the same thing. That can get out of control quick if you need to implement every combination.
And that doesn't help at all if you're writing a "free function" like 3D primitive intersection functions. I suppose you could change that simple function into a generic function that takes AsDeref? Bleh.
I always prefer by-borrow. That's because in the future this struct may become non-copy and that means some unnecessary refactoring.
My thinking is a bit like "don't take ownership if not needed" - the "not needed" part is the most important thing. Don't require things that are not needed.
Exactly why IMHO the rust stdlib is so easy to understand. Ownership only when required as a design principle tends to make the design of the overall system more consistent / easier to approach.
If a struct might lose Copy you shouldn't implement Copy at all, to preserve forward compatibility. You can still derive Clone in most cases; using .clone() does not per se add any overhead.
237 comments
[ 2.7 ms ] story [ 266 ms ] threadBut also, the ABI only matters between two pieces that are separately compiled. A static binary optimized at link-time doesn't have to care.
Also Fortran has "in", "inout" and "out".
It can return multiple values, so this doesn’t matter much for value types, but it would be nice to be able to specify that a pointer arg is an out-param sometimes and enforce that it is not read from while handling allocation in the caller.
Better yet when you prohibit such arguments from aliasing (or at least make no-alias the default) - now the compiler can also implement "in out" by copying the value back and forth, if it's faster than indirection.
Herb made a proposal for proper in/out parameters for C++ in 2020 https://youtu.be/6lurOCdaj0Y
in - regular function arguments
inout - mut function arguments
out - function return
Is there any additional information that a compiler can infer from Ada’s parameter syntax?
Anyway, assuming it's not inlined I would guess pass-by-copy, maybe with an occasional exception in code with heavy register pressure.
Edit: Actually since it's a structure, the calling convention is to memory allocate it and pass a pointer, doh. So it should actually compile the same.
Depending on calling convention, the structure may be spread out into registers.
FWIW the AMD64 SysV v1.0 psABI allows structures of up to 8 members to be passed via registers. Though older revisions limit that to 2 (and it's unclear whether MS's divergent ABI allows aggregates to be splat at all.
As sad as it's unsurprising, it does not look like LLVM (linux?) has followed up, on godbolt a 2-struct passes everything via registers but a 3-struct passes everything via the stack. Maybe there's a magic flag to use the 1.0 ABI, but a quick googling didn't reveal one. ICC doesn't seem to have followed up either.
Actually reading the word abi made a little neuron light up. To what extent does rust even follow that abi?
Though that should not apply to Rust at all, as it does not pledge to follow the C ABI internally (aka `extern "Rust"`).
The other question I have is which style should you use when writing a library? It's obviously not possible to benchmark all the software that will call your library but you still want to consider readability, performance as well as other factors such as common convention.
The clarity of the code using a particular library is such an big (but often under-appreciated) benefit that I would heavily lean in this direction when considering interface options. My 2c.
Situations otherwise are the exception, rather than the rule, and it takes an expert to (1) recognize those situations and (2) know exactly how to write optimized code in that situation.
That's why "don't prematurely optimize" is a good rule of thumb - because it works the majority of the time, and it takes experience to know when not to apply it.
[citation needed]
This claim depends hugely on the industry you're actually working in and the problem space. Things like UIs & games basically never have a single, easy-to-fix smoking gun. The entire app is more or less a hotspot - be it interactive performance, startup performance, RAM usage, or general responsiveness.
And once you're gone down the route of "build it first, optimize it later" you're pretty much fucked when you get to the "optimize" step because now your performance mistakes are basically unfixable without a rewrite - every layer of your architecture has issues that you can't fix without drastic overhauls. It would have been much easier to do some up-front measurements, get some guidelines in place (even if they aren't perfect), and then build the app.
> The true root of all evil is unexamined dogma.
This is so absurd that it doesn't deserve a reply.
There’s no hard and fast rule here. Even if there was, optimizers still occasionally surprise seasoned native devs in both positive and negative ways.
Glad the author’s first instinct was to pull out profiling tools.
Trusting the compiler also means knowing what the compiler actually understands & handles vs. what's a library-provided abstraction that's maybe too bloated for its own good and that quickly becomes "not simple" depending on your language of choice.
Not really. I'm just hoping that it will be "fast enough", which in the vast majority of cases it is.
Of course, if your struct is truly enormous, you may want to break this rule to avoid large copies. But in that case you probably want to Box<T> the struct anyway.
Of course, if your struct contains something that can't be copied--like a Vec<T>--you'll have to decide whether to clone the whole struct (and thus the vector in it), pass the struct by-borrow, or find some other solution.
Sure, but it's worth noting that references in Rust do not exist merely to avoid passing by-value. They also exist to make it easier to deal with Rust's ownership semantics: they let you pass things to a function without also requiring the function to "pass back" those things as returned values. In other words, references let you do `fn foo(x: &Bar)` rather than `fn foo(x: Bar) -> Bar`. This is a unique and interesting consequence of languages with by-default move semantics.
(The other direction is trickier, since by-ref implies the desire to observe aliasing, even though that's usually not expected in practice - but the compiler cannot tell.)
> Then you would actually be testing by-borrow be by-copy instead of how good rust is at optimizing.
I don’t think the question is actually: “what is faster in practice, a by-copy method call or a by-value method call”, I think the question is: “as an implementer, which semantics should I choose when I’m writing my function”.
For the second question: “Rust is usually pretty good at aggressively inlining, so… if you’re willing to trust Rust’s compiler, you’re often okay going with by-copy implementations, but you should keep an eye on it”. Whereas, as you note, for the first question it’s not an answer.
But, I do think if someone was going to put more work into it I’d be very curious what the answer to the first question is. If I’m choosing to implement with by-copy semantics and trusting the Rust compiler to hopefully inline things for me, I’d like to know the implications in the cases when it doesn’t.
The root question is indeed “what semantics should I use”. And the answer I came up with was “the compiler does a lot of magic so by-copy seems pretty good”. I agree with the previous commenter this is not a satisfying conclusion!
My experience with Rust is that it requires a moderate amount of trust in the compiler. Iterator code is another example where the compiler should produce near optimal code. Emphasis on should!
Your tests on my PC:
P.S. Just built it using LLVM under CLion IDE and the results are:I believe that the Rust compiler at least does exactly that. Large structs will be passed by reference under the hood even if it passed by value in the code. I suspect C++ compilers do the same, although I'm not sure about that.
Were the other benchmarks run in debug mode / with optimizations turned off or something like that? What compiler & flags are you using?
Why would I do something like that? Of course all builds are release mode, optimize for speed.
>"Why is performance so much better in this case?"Not sure and not in a mood to investigate. I do know if cache locality and branch prediction stars line up properly the performance difference can be staggering. Maybe LLVM has accomplished something nice in this department.
C++ MSVC: By-Copy: 12,077 By-Ref: 11,901
C++ Clang: By-Copy: 5,020 By-Ref: 5,029
Rust: By-Copy: 3,173 By-Borrow: 3,148
All on Windows, and on the same i7-8700k desktop I used for the original post in 2019.
Your Rust numbers are particularly curious. Maybe run `rustup update` and try again?
Happy New Year
Try this:
And: arch=native will also activate SSE, MMX, and all the other goodies that modern CPUs have to offer.* Sprinkling & around everything in math expressions does make them ugly. Maybe rust needs an asBorrow or similar?
* If you inline everything then the speed is the same.
* Link time optimizations are also an easy win.
https://github.com/mcallahan/lightray
Do you mean AsRef, or do you mean magic which automatically borrows parameters and is specifically what rust does not do any more than e.g. C does?
Though you can probably get both if the by-ref version is faster (or more convenient internally): wrap the by-ref function with a by-value wrapper which is #[inline]-ed, this way the interface is by value but the actual parameter passing is byref (as the value-consuming wrapper will be inlined and essentially removed).
FWIW, the `Borrow`, `AsRef`, and `Deref` traits all exist to support different variants of this.
If there's no inlining at play, I'd expect vast differences to be possible. For example, imagine a chain of 3 functions - f calls g, g calls h, where one of the arguments is a 1kB struct and the options are passing by copy or by borrowing. In this case, each stack frame will be 1kB in size in the copy case and there will be a large performance overhead as opposed to the by-reference case. One would expect simply calling the function to be similar in overhead to an uncached memory load.
Within a single crate the inlining is possible, with multiple crates it's only possible with LTO enabled (and I'm not sure how _probable_ it is that the inlining would occur).
In either case, the difference between a 32 byte and 8 byte argument in terms of overhead is likely meaningless - the sort of thing to be optimized if profiling says it's a problem as opposed to ahead of time.
Cross-crate inlining happens all the time. In order to be eligible for inlining, a function needs to have its IR included in the object's metadata. This happens automatically for every generic function (it's the only way monomorphization can work), and for non-generic functions can be enabled manually via the `#[inline]` attribute (which does not force inlining, it only makes it possible to inline at the backend's discretion).
However, as you, say, if you have LTO enabled then "cross-crate" inlining can happen regardless, since it's all just one giant compilation unit at that point.
So, what the author actually measured was the difference between llvm and msvc throughout the article. Particularly when they talked about rust being better at autovectorization than C++.
It does sometimes matter though. One optimization I’ve seen in a few places is to box the error type, so that a result doesn’t copy the (usually empty) error by value on the stack. That actually makes a small performance difference, on the order of about 5-10%.
Performance-wise, if you're likely to touch every element in a type anyway, err on the side of copies. They are going to have to end up in registers eventually anyway, so you might as well let the caller find out the best way to put them there.
Also, whenever you do one of these, please post the full source with it. There's no reason to leave your readers in the dark, wondering what could be going on, which is exactly what I'm doing now, because there's almost no excuse for c++ to be slower in a task than rust--it's just a matter of how much work you need to put in to make it get there.
There’s literally a section called Source Code…
But yeah I have no idea why a benchmark framework wasn't used for Rust.
https://github.com/sheredom/ubench.h
But nevertheless: I agree it would have been interesting to test with GCC as well.
References may get optimized to copies where possible and sound (i.e. blittable and const), a common heuristic involves the size of a cache line (64b on most modern ISAs, including x86_64).
Using a Vector4 would have pushed the structure size beyond the 64b heuristic. You would also need to disable inlining for the measured methods.
And, for simple operations like this, you really should just look at the assembly output. If you are only generating 20ish instructions, then look at those 20 instructions rather than trying to heuristically guess what is happening.
The benchmark made here could completely fall apart once more threads are added.
Modern computer architectures are non-uniform in terms of any kind of memory accesses. The same logical operations can have extremely varied costs depending on how the whole program flow goes.
Rust is probably better used for writing fast low-level libraries that you call from higher level languages, possibly with a garbage collector, so you don't waste time thinking about memory management while you design/write your high-level application.
What did you have in mind?
I'll take Rust shouting at me for missing "mundane details" any day of the week.
Rust uses syntax that feels familiar but means completely different things than in pretty much any other language.
For example '=' doesn't mean assign handle or copy. It by default means move.
'let' doesn't mean create a name for something. It means create physical space for something (of known size) that can be moved into or moved out of.
You don't deal with objects and values of primitive types. Instead everything in Rust is a value. When you move, you move the value. If you compare, you compare by value. If you pass something from variable into function, you move the value into the function.
And when the space where you keep the value goes out of scope value dies with it if it wasn't moved out to somewhere else.
Scope for variables (which are just named spaces for values) ends with the end of the block, but some values, created by functions and returned from them, if they are not moved into any named space, can die sooner, even in the middle of the line where they were acquired from function call.
Everything else stems from that fixed size moved value semantics. If you don't want to move the value into the function when you call it you need to pass something else instead, so you create and pass in the borrow. But you have to ensure that the value doesn't die or get moved anywhere (even inside the container you borrowed from) before borrows to it all die.
Because of this you are better off with borrows that are short lived and local. Often it's better to keep the index of an element of a Vec instead of the borrow of this element. If you must create types that contain borrows you must know that they become borrows themselves and you need to treat them exactly the same trying to limit their scope and life time.
It's hard when you come from any other language because borrows are superficialy similar to pointers or references to objects. So you try to use them as such. And crash into the compiler because they are not that. What's worse their syntax is very minimalistic which triggers intuition that they must be fast and optimal solution for many problems which they sure can be once you fully internalize their limitations but not a moment sooner.
Another thing is that values in Rust must have the fixed size. So even as simple thing as a string requires a bit of hackery. Basically in Rust the default strategy to have something of variable size is to allocate it on the heap and treat pointer to it (possibly with some other fixed sized data like length) as the fixed sized value you can move around clone and borrow.
So if you want to have semantics you know from other languages you can't just use basic Rust syntax.
You need constructs such as Box and Rc, Cell, RefCell. Make your things clonable and sometimes even copyable and avoid creating borrows whenever possible initially. When you do it Rust becomes as flexible as any other language and you can use it pretty much just as comfortably. Then the value semantics shines as you can very easily compare your data by value, order it, create operators for it, create has for it so you can keep it in HashMaps and HashSets. Then it's delightful.
My advice is when you create a long lived type just wrap it in Rc and treat this Rc as your 'object'. And avoid borrows in your types unless you have a very good performance (measured) reason to have them or you are creating something obviously dependant and usually short lived like an iterator.
One non-tree cross-link or back-link and you'll have to redesign your entire code.
You can fairly easily refactor your almost-tree code to adapt it to that additional Option wrap.
Of course you might instead opt to introduce some garbage collector crate into your project. They usually provide garbage collected Rc equivalent, which makes swapping it out very easy.
Rc's are really very useful first approach to making anything complex in Rust.
I usually have something like
and or if I need cross-links.Great thing is you can then add 'methods' to your type with
Or define operators and other traits with: Sometimes, when I need mutability I even wrap the NodeStruct in RefCell.It seems like a lot of wrappers but thanks to them you can have very nice code that uses this type that has pretty much 'normal modren language' semantics + value semantics and is still blazing fast.
When you implement Ord, Eq, Hash they all go through all the wrappers and let you treat your final type Node as a comparable, sortable, hashable and cheaply clonable value. Dereferencing also goes through all or most of the wrappers automatically.
Main objects in my program are expression trees. I manipulate them, cut them, merge them, compare them, splice one into the other. Rc's enable me to have full flexibility and share tremendous amount of data across objects in my program.
Rust is absolutely wonderful language for this problem thanks to Rc's, enums, value semantics, auto-deriving traits and ability to implement traits for existing types and of course speed.
I'm not implementing specific algorithms. I'm making them up as I go although I used some simple ones like topological sort or A* that eventually turned into just breadth search because I have no idea how far I am from the solution.
It's mindboggling to me that people are using a systems programming language for mathematical research, especially if they don't know yet what the final algorithms will look like.
But all the more power to you for trying.
Some complain about this, but the fact is there's no such thing as a zero-overhead "copy" for non-trivial types. C++ started out with = meaning clone the object which was an even bigger footgun, and support for move had to be added after the fact.
It's very elegant solution for simple, small data types. But it further occludes how meaningfully Rust is different from everything else because thanks to that = sometimes does mean copy.
You need to structure your program as a Directed Acyclic Graph (DAG), with things interacting only with the things below them in the graph.
Then occasionally you might need to break the DAG structure by using Rc, Cell & RefCell, etc...
And finding it towards the end of writing your program after hours of fighting with borrow checker is extremely unpleasant.
And I don't think I ever landed in the situation where I could fix the discrepancy by sprinkling in few Rc, RefCells and such.
So I prefer to write with RefCells from the start and when I got the thing working and I am ambitious enough then I look at which parts could be borrows instead and I swap them out.
The issue here is that you are writing C++ code rather than Rust code.
Two separate synced trees? Is it worth it?
> The issue here is that you are writing C++ code rather than Rust code.
How dare you! I'm writing TypeScript code! ;-)
Rust is not Forth. I can write whatever I want and there's nothing wrong with that.
Rewrite your program in a form where it does not contain a tree.
If you want an actual tree as a data structure, see the trees crate.
> Rust is not Forth. I can write whatever I want and there's nothing wrong with that.
And other people write Haskell code in Python :p. If your code style doesn't match the language you are using you are going to have a lot of unnecessary friction.
But you inspired me about something. I think I can rewrite the program that I am writing to use reverse Polish notation instead of a tree. Thanks!
I don’t think you ever have to write code like this. Implement your math traits in terms for both value and reference types like the standard library does.
Go down to Trait Implementations for scalar types, for instance i32 [1]
impl Add<&i32> for &i32
impl Add<&i32> for i32
impl Add<i32> for &i32
impl Add<i32> for i32
Once you do that your ergonomics should be exactly the same as with built in scalar types.
[1] https://doc.rust-lang.org/std/primitive.i32.html
Lots of criticism of my methodology in the comments here. That’s fine. That post was more of a self nerd snipe that went way deeper than I expected.
I hoped that my post would lead to a more definitive answer from some actual experts in the field. Unfortunately that never happened, afaik. Bummer.
And that doesn't help at all if you're writing a "free function" like 3D primitive intersection functions. I suppose you could change that simple function into a generic function that takes AsDeref? Bleh.
And I would bet 9 times out of 10 it won't be the bottleneck or even make a measurable difference.
That's my approach too as a Rust newbie. Borrow by default and take ownership only when needed, for the best ergononmics.
Rust - By-Copy: 14124, By-Borrow: 8150
C++ - By-Copy: 12160, By-Ref: 11423
P.S. Just built it using LLVM under CLion IDE and the results are:
Now comes big surprise: I just built it using LLVM under CLion IDE and the results are: