5 ms·

For what it's worth, it appears a C++ version [0] of that binary search algorithm with Clang 13 requires 9.45 cycles [1]. The clang++-generated ASM is quite sim

For what it's worth, it appears a C++ version [0] of that binary search algorithm with Clang 13 requires 9.45 cycles [1]. The clang++-generated ASM is quite similar to the rustc-generated ASM in the article. Not sure what accounts for the difference from the C++ implementations the author was comparing against. Regardless, it's neat to see the two languages are so close in performance here. I wonder if down the line, the richer information about lifetimes, etc. that Rust provides will allow optimizations beyond those available to C++ -- or if this is already the case. [0] https://godbolt.org/z/Mj7PWevex https://godbolt.org/z/Mj7PWevex [1] https://bit.ly/3CawbUe https://bit.ly/3CawbUe

kibwen 5y ago
I'm not aware of any theoretical optimizations that lifetimes would enable. Aliasing information, absolutely, but the lifetimes themselves are purely used to reject a given program, and currently have no other impact. Maybe you could do something neat with reusing storage slots, though it seems like LLVM is already pretty good at that?
- dodobirdlord 5y ago
  Reusing storage slots definitely sounds plausible, another possible option is automatically allocating values with the same lifetime into memory arenas, so that you only have to do one alloc and one free for an arbitrary number of objects with the same or similar lifetimes.
  - Rusky 5y ago
    That doesn't really make much sense for Rust, unfortunately. That is, for stack objects, LLVM/etc already do this and lifetimes don't add any useful new information. A function will generally adjust the stack pointer once to allocate and free space for all its locals together. Beyond that, lifetimes are answering the wrong question. For one thing, the language goes to great lengths to squash and stretch lifetimes to accept more programs- so function signatures are typically as general as possible (IOW they capture as little lifetime information as possible). This even includes entirely "forgetting" information about how/where things are allocated. Actually using lifetimes or "regions" to control or track allocations probably makes more sense in a higher-level, perhaps more allocation-happy, language. You might be interested in looking at Vale, for example: https://vale.dev/ https://vale.dev/
- brundolf 5y ago
  There's an opportunity to avoid copying certain values due to move semantics, but last I checked it doesn't work yet because of LLVM. But it could one day: https://stackoverflow.com/questions/38571270/can-rust-optimise-away-the-bit-wise-copy-during-move-of-an-object-someday#38571602 https://stackoverflow.com/questions/38571270/can-rust-optimi... Edit: This answer is pretty old, so it may have changed by now, but I couldn't find anything more recent in a quick search
  - khuey 5y ago
    That specific optimization still does not happen.

kibwen 5y ago

I'm not aware of any theoretical optimizations that lifetimes would enable. Aliasing information, absolutely, but the lifetimes themselves are purely used to reject a given program, and currently have no other impact. Maybe you could do something neat with reusing storage slots, though it seems like LLVM is already pretty good at that?

dodobirdlord 5y ago
Reusing storage slots definitely sounds plausible, another possible option is automatically allocating values with the same lifetime into memory arenas, so that you only have to do one alloc and one free for an arbitrary number of objects with the same or similar lifetimes.
- Rusky 5y ago
  That doesn't really make much sense for Rust, unfortunately. That is, for stack objects, LLVM/etc already do this and lifetimes don't add any useful new information. A function will generally adjust the stack pointer once to allocate and free space for all its locals together. Beyond that, lifetimes are answering the wrong question. For one thing, the language goes to great lengths to squash and stretch lifetimes to accept more programs- so function signatures are typically as general as possible (IOW they capture as little lifetime information as possible). This even includes entirely "forgetting" information about how/where things are allocated. Actually using lifetimes or "regions" to control or track allocations probably makes more sense in a higher-level, perhaps more allocation-happy, language. You might be interested in looking at Vale, for example: https://vale.dev/ https://vale.dev/
brundolf 5y ago
There's an opportunity to avoid copying certain values due to move semantics, but last I checked it doesn't work yet because of LLVM. But it could one day: https://stackoverflow.com/questions/38571270/can-rust-optimise-away-the-bit-wise-copy-during-move-of-an-object-someday#38571602 https://stackoverflow.com/questions/38571270/can-rust-optimi... Edit: This answer is pretty old, so it may have changed by now, but I couldn't find anything more recent in a quick search
- khuey 5y ago
  That specific optimization still does not happen.