5 ms·

> If only there was a clean fast bare-metal language to write all this in.. The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim

> If only there was a clean fast bare-metal language to write all this in.. The author includes a footnotes for "BUT RUST.." and "BUT ZIG..", but how about Nim? Looks like there is a native library implementation of `lowerBound` https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/algorithm.nim#L221 https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al... Yes, it's not a "bare-metal" language, but it compiles to one (or two), so it would be interesting to see what it compiles to here. Also, what's wrong with C?

matklad 3y ago
> BUT ZIG.. There’s no binary search implementation in Zig that I could find, rather it calls to C++. Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009c9662ba4c0ea77d4/lib/std/sort.zig#L400 https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009... At TigerBeetle, we have our own branchless implementation here: https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf71540747bd57fa2ffb1814ee3e2acff8/src/lsm/binary_search.zig#L53 https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...
- josephg 3y ago
  Rust's binary search is here. Also a pretty textbook version of the function: https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c4667b74fc7d784c1836/library/core/src/slice/mod.rs#L2769-L2809 https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c... How much faster is the branchless version in practice? I make heavy use of binary search in some code I maintain, and I wonder if it would make much of a difference to switch to a more efficient version of the function.
  - abhishekjha 3y ago
    I don't know much about Rust data types or Rust in general but does it not have any integer overflow? I see (left+right)/2. Is it like python with unbounded precision?
    - deleted 3y ago
      [deleted]
    - josephg 3y ago
      Integer overflows cause panics in debug mode. And its undefined behaviour in release mode. Where do you see that in the code? I can't see (left+right)/2 anywhere in the code I linked?
      - deleted 3y ago
        [deleted]
      - marcianx 3y ago
        I'm pretty sure it's not undefined behavior in rust in release mode if it does overflow. It's fully specified behavior, I believe.
      - cornstalks 3y ago
        > And its undefined behaviour in release mode. No, it uses 2’s complement and is well defined in release mode. From [1]: > When you’re compiling in release mode with the --release flag, Rust does not include checks for integer overflow that cause panics. Instead, if overflow occurs, Rust performs two’s complement wrapping. [1]: https://doc.rust-lang.org/book/ch03-02-data-types.html#integer-overflow https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...
    - Phemist 3y ago
      Left and right are both usizes, which are 64-bit pointers. You will need work on an array of 2^63 elements before you have to worry about integer overflow issues. This array would not fit in any kind of memory for the foreseeable future :)
      - creata 3y ago
        Not that it makes much of a difference, but Rust does compile to 32-bit platforms. https://doc.rust-lang.org/nightly/rustc/platform-support.html https://doc.rust-lang.org/nightly/rustc/platform-support.htm...
  - WinLychee 3y ago
    Rust's binary search used to be branchless but due to some issues down in LLVM land, the codegen doesn't issue a `cmov` where it should. https://github.com/rust-lang/rust/issues/53823 https://github.com/rust-lang/rust/issues/53823 old branchless version: https://github.com/rust-lang/rust/pull/45333/files https://github.com/rust-lang/rust/pull/45333/files
eru 3y ago
> Also, what's wrong with C? Oodles and oodles of undefined behaviour, for example. C ain't clean.
- User23 3y ago
  Nah, thanks to CompCert[1] C actually has one of the highest quality and most predictable compilers. [1] https://compcert.org/ https://compcert.org/
  - Ygg2 3y ago
    How much of available C libraries are CompCert compatible?
  - insanitybit 3y ago
    What is the practicality of actually using CompCert? And what does it actually defend against? All I know is that it tries to ensure that the behavior of the program is the same as the input, meaning that the compiler itself does not have bugs. But how does that actually interact with undefined behavior in the language? What happens to an array out of bounds? And what are the limitations imposed, since it only works on a subset of the C language? It seems unlikely that I could just switch compilers and suddenly have a safe program written in C.
    - LegionMammal978 3y ago
      It looks like CompCert explicitly does not attempt to prevent UB from resulting in unpredictable behavior; all it guarantees is that "the observable behavior of [the compiled code] C improves on one of the allowed observable behaviors of [the source program] S", where "improving on" allows for arbitrary behavior on UB [0]: > Third, the compiler is allowed to improve the behavior of the source program. Here, to improve means to convert a run-time error (such as crashing on an integer division by zero) into a more defined behavior. This can happen if the run-time error (e.g. division by zero) was optimized away (e.g. removed because the result of the division is unused). However, if the source program is known to be free of run-time errors, perhaps because it was verified using static analyzers or deductive program provers, improvement as described above never takes place, and the generated code behaves exactly as one of the allowed behaviors of the source program. So you still have to prove your program's correctness by some other means. [0] https://compcert.org/man/manual001.html#sec3 https://compcert.org/man/manual001.html#sec3
TillE 3y ago
An equivalent generic sort function in C would, at best, require a bunch of additional distracting cruft. This is exactly what C++ templates are for.

matklad 3y ago

> BUT ZIG.. There’s no binary search implementation in Zig that I could find, rather it calls to C++. Zig’s binary search is here, it’s an unoptimized textbook version: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009c9662ba4c0ea77d4/lib/std/sort.zig#L400 https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009... At TigerBeetle, we have our own branchless implementation here: https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf71540747bd57fa2ffb1814ee3e2acff8/src/lsm/binary_search.zig#L53 https://github.com/tigerbeetle/tigerbeetle/blob/e996abcf7154...

josephg 3y ago
Rust's binary search is here. Also a pretty textbook version of the function: https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c4667b74fc7d784c1836/library/core/src/slice/mod.rs#L2769-L2809 https://github.com/rust-lang/rust/blob/4d7a80d48697171ed151c... How much faster is the branchless version in practice? I make heavy use of binary search in some code I maintain, and I wonder if it would make much of a difference to switch to a more efficient version of the function.
- abhishekjha 3y ago
  I don't know much about Rust data types or Rust in general but does it not have any integer overflow? I see (left+right)/2. Is it like python with unbounded precision?
  - deleted 3y ago
    [deleted]
  - josephg 3y ago
    Integer overflows cause panics in debug mode. And its undefined behaviour in release mode. Where do you see that in the code? I can't see (left+right)/2 anywhere in the code I linked?
    - deleted 3y ago
      [deleted]
    - marcianx 3y ago
      I'm pretty sure it's not undefined behavior in rust in release mode if it does overflow. It's fully specified behavior, I believe.
    - cornstalks 3y ago
      > And its undefined behaviour in release mode. No, it uses 2’s complement and is well defined in release mode. From [1]: > When you’re compiling in release mode with the --release flag, Rust does not include checks for integer overflow that cause panics. Instead, if overflow occurs, Rust performs two’s complement wrapping. [1]: https://doc.rust-lang.org/book/ch03-02-data-types.html#integer-overflow https://doc.rust-lang.org/book/ch03-02-data-types.html#integ...
  - Phemist 3y ago
    Left and right are both usizes, which are 64-bit pointers. You will need work on an array of 2^63 elements before you have to worry about integer overflow issues. This array would not fit in any kind of memory for the foreseeable future :)
    - creata 3y ago
      Not that it makes much of a difference, but Rust does compile to 32-bit platforms. https://doc.rust-lang.org/nightly/rustc/platform-support.html https://doc.rust-lang.org/nightly/rustc/platform-support.htm...
- WinLychee 3y ago
  Rust's binary search used to be branchless but due to some issues down in LLVM land, the codegen doesn't issue a `cmov` where it should. https://github.com/rust-lang/rust/issues/53823 https://github.com/rust-lang/rust/issues/53823 old branchless version: https://github.com/rust-lang/rust/pull/45333/files https://github.com/rust-lang/rust/pull/45333/files

eru 3y ago

> Also, what's wrong with C? Oodles and oodles of undefined behaviour, for example. C ain't clean.

User23 3y ago
Nah, thanks to CompCert[1] C actually has one of the highest quality and most predictable compilers. [1] https://compcert.org/ https://compcert.org/
- Ygg2 3y ago
  How much of available C libraries are CompCert compatible?
- insanitybit 3y ago
  What is the practicality of actually using CompCert? And what does it actually defend against? All I know is that it tries to ensure that the behavior of the program is the same as the input, meaning that the compiler itself does not have bugs. But how does that actually interact with undefined behavior in the language? What happens to an array out of bounds? And what are the limitations imposed, since it only works on a subset of the C language? It seems unlikely that I could just switch compilers and suddenly have a safe program written in C.
  - LegionMammal978 3y ago
    It looks like CompCert explicitly does not attempt to prevent UB from resulting in unpredictable behavior; all it guarantees is that "the observable behavior of [the compiled code] C improves on one of the allowed observable behaviors of [the source program] S", where "improving on" allows for arbitrary behavior on UB [0]: > Third, the compiler is allowed to improve the behavior of the source program. Here, to improve means to convert a run-time error (such as crashing on an integer division by zero) into a more defined behavior. This can happen if the run-time error (e.g. division by zero) was optimized away (e.g. removed because the result of the division is unused). However, if the source program is known to be free of run-time errors, perhaps because it was verified using static analyzers or deductive program provers, improvement as described above never takes place, and the generated code behaves exactly as one of the allowed behaviors of the source program. So you still have to prove your program's correctness by some other means. [0] https://compcert.org/man/manual001.html#sec3 https://compcert.org/man/manual001.html#sec3

TillE 3y ago

An equivalent generic sort function in C would, at best, require a bunch of additional distracting cruft. This is exactly what C++ templates are for.