141–150 of 198 posts
The setup code to reduce the length to a 2-power can be avoided. I'm curious how well the following code performs in comparison: for (size_t length = end - begin; length != 0; length = (length + 1) / 2) { size_t step = length / 2; if (compare(begin[step], value)) begin += step; } return begin; For odd lengths like 5, this splits the array in an even part of length 2, and an odd part of length 3, and then searches eit…
The setup code to reduce the length to a 2-power can be avoided. I'm curious how well the following code performs in comparison: for (size_t length = end - begin; length != 0; length = (length + 1) / 2) { size_t step = length / 2; if (compare(begin[step], value)) begin += step; } return begin; For odd lengths like 5, this splits the array in an even part of length 2, and an odd part of length 3, and then searches eit…
Doesn't this run forever? Once length reaches 1 it will never go to 0.
for (size_t length = end - begin; length != 1; length = (length + 1) / 2)
{
size_t step = length / 2;
if (compare(begin[step], value))
begin += step;
}
return begin + compare(*begin, value);
Earlier quoted context omitted.
I’m always surprised by rust’s performance for this reason. The compiler outputs huge binaries, chock full of bounds checks and the like. But performance doesn’t seem to suffer at all from it. On the contrary - I ported some well optimized C to rust and it ran faster. I can only assume the compiler is marking all the bounds checks as unlikely to fail, and correctly predicted branches must be more or less free in mode…
I believe that in release mode Rust will remove bounds checks.
You can see this pretty easily in compiler explorer. This is a simple array lookup compiled in release mode:
Earlier quoted context omitted.
True. But if binary size is anything to go by, an awful lot of bounds checks still end up in the code.
Doesn't a rust binary also include a whole lot of standard library? C compilers assume that libc is available, a rust compiler is hardly going to assume that rust's libstd is installed on a random user's machine.
And the “compile in the standard library” pattern will probably never be changed in rust due to monomorphization. Lots of types in the standard library need to be specialised based on the types of your structs. Even if rust had an ABI for dynamic linking (it doesn’t), structs and functions which take generic type parameters will probably never be able to be loaded from a shared library. Same as C++.