4 ms·

How to Optimize Rust for Slowness: Inspired by New Turing Machine Results

55 points by carlkcarlk 1y ago

Surac 1y ago
If you can’t make it useful. It always can be used to write horrible examples hihi
- deleted 1y ago
  [deleted]
capitol_ 1y ago
[flagged]
- deleted 1y ago
  [deleted]
carlkcarlk 1y ago
Python version: https://towardsdatascience.com/how-to-optimize-your-python-program-for-slowness/ https://towardsdatascience.com/how-to-optimize-your-python-p...
LoganDark 1y ago
If our only goal is to run forever, the solution is immediate: ```rs fn main() { loop {} } ``` I think this can even cause Undefined Behavior :) https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728
- the8472 1y ago
  This was fixed, llvm added the `mustprogress` attribute to get C++ semantics and Rust doesn't set it.
- 9rx 1y ago
  Not to mention that it will halt on signal, contrary to the goal. I guess that's the problem with "vibe coding": What immediately looks like the solution isn't apt to be.
  - LoganDark 1y ago
    > Not to mention that it will halt on signal, contrary to the goal. Well, it's difficult not to halt on, say, SIGKILL, that's for sure. There are ways to do it, but they are cursed and I hate them (e.g. zombie processes). Though you can still usually get rid of zombie processes by killing the parent, or just rebooting the system.
    - 9rx 1y ago
      Halting normally implies that the program has finished executing. Maybe, as your tricks suggest, SIGKILL is a little grey area, but I think it is fair to say that its intent is ultimately to kill the program even if it hasn't finished executing, thus in a typical scenario it wouldn't see the program halt. Rebooting or otherwise terminating execution of a program at the hardware level before a program has finished is even clearer that the program hasn't halted, at least as the term is typically understood. But something like SIGINT is at the discretion of the program. If it chooses to accept the signal and halt it is entirely because the program decided it was finished.
  - creatonez 1y ago
    A real solution would be able to disobey the power switch on the back of your computer
- tialaramex 1y ago
  There has been a nasty habit of the LLVM people treating their IR as "Yeah, but we all know it's basically C++ right?" as if there weren't any other consumers except Clang. The semantics claimed for that loop IR said it can go infinite, the reality was that it has the (at the time) no infinite loops C++ semantics instead. The doubly funny thing is that some C++ people don't want those either, and so the ISO document will be updated to say actually C++ does have infinite loops because programmers want that. It just won't have an elegant way to express it like Rust.
timeon 1y ago
Sorry for commenting on the form but that picture is bit too much for me. (Not because how it was produced.)
QuadmasterXLII 1y ago
tricky tricky- I think this stops well before 10^^15 due to the limits of 64 bit addressing
- carlkcarlk 1y ago
  Yes, the article figures that with a limit of 64GB of memory, with simple nested loops, you could only loop about 10^(165 billion) steps. To get 10^^15 steps, the article assumes "any amount of zero-initialized memory". (It calls that assumption "unrealistic but interesting".)
  - kryptiskt 1y ago
    You can hook it up to a cloud service, say an S3 bucket, and allocate storage space as needed. Then it fulfills the condition of unbounded memory, at the small price of unbounded cost. But it will not be a problem during your lifetime. If you are cloud-averse, you could do the same with networked storage on your local LAN and just connect more disks when it's running out.
carlkcarlk 1y ago
Here is the [final function in Python](https://towardsdatascience.com/how-to-optimize-your-python-program-for-slowness/ https://towardsdatascience.com/how-to-optimize-your-python-p...): (Regular Python `int` is arbitrary precision, but immutable, so I use `gmpy2.xmpz` instead.) def tetrate(a, tetrate_acc): assert is_valid_other(a), "not a valid other" assert is_valid_accumulator(tetrate_acc), "not a valid accumulator" assert a > 0, "we don't define 0↑↑b" exponentiate_acc = xmpz(1) for _ in count_down(tetrate_acc): multiply_acc = xmpz(1) for _ in count_down(exponentiate_acc): add_acc = xmpz(0) for _ in count_down(multiply_acc): for _ in range(a): add_acc += 1 multiply_acc = add_acc exponentiate_acc = multiply_acc return exponentiate_acc And here is the final function in Rust: (I used `&mut` instead of returned values because I don't think Rust guarantees that returned owned values aren't copied.) fn tetrate(a: u32, acc: &mut BigUint) { assert!(a > 0, "we don’t define 0↑↑b"); let mut exp = BigUint::from(1u32); for () in acc.count_down() { let mut mul = BigUint::from(1u32); for () in exp.count_down() { let mut add = BigUint::ZERO; for () in mul.count_down() { for _ in 0..a { add += 1u32; } } mul = add; } exp = mul; } *acc = exp; }

55 points by carlkcarlk 1y ago

Surac 1y ago

If you can’t make it useful. It always can be used to write horrible examples hihi

deleted 1y ago
[deleted]

capitol_ 1y ago

[flagged]

deleted 1y ago
[deleted]

carlkcarlk 1y ago

Python version: https://towardsdatascience.com/how-to-optimize-your-python-program-for-slowness/ https://towardsdatascience.com/how-to-optimize-your-python-p...

LoganDark 1y ago

If our only goal is to run forever, the solution is immediate: ```rs fn main() { loop {} } ``` I think this can even cause Undefined Behavior :) https://github.com/rust-lang/rust/issues/28728 https://github.com/rust-lang/rust/issues/28728

the8472 1y ago
This was fixed, llvm added the `mustprogress` attribute to get C++ semantics and Rust doesn't set it.
9rx 1y ago
Not to mention that it will halt on signal, contrary to the goal. I guess that's the problem with "vibe coding": What immediately looks like the solution isn't apt to be.
- LoganDark 1y ago
  > Not to mention that it will halt on signal, contrary to the goal. Well, it's difficult not to halt on, say, SIGKILL, that's for sure. There are ways to do it, but they are cursed and I hate them (e.g. zombie processes). Though you can still usually get rid of zombie processes by killing the parent, or just rebooting the system.
  - 9rx 1y ago
    Halting normally implies that the program has finished executing. Maybe, as your tricks suggest, SIGKILL is a little grey area, but I think it is fair to say that its intent is ultimately to kill the program even if it hasn't finished executing, thus in a typical scenario it wouldn't see the program halt. Rebooting or otherwise terminating execution of a program at the hardware level before a program has finished is even clearer that the program hasn't halted, at least as the term is typically understood. But something like SIGINT is at the discretion of the program. If it chooses to accept the signal and halt it is entirely because the program decided it was finished.
- creatonez 1y ago
  A real solution would be able to disobey the power switch on the back of your computer
tialaramex 1y ago
There has been a nasty habit of the LLVM people treating their IR as "Yeah, but we all know it's basically C++ right?" as if there weren't any other consumers except Clang. The semantics claimed for that loop IR said it can go infinite, the reality was that it has the (at the time) no infinite loops C++ semantics instead. The doubly funny thing is that some C++ people don't want those either, and so the ISO document will be updated to say actually C++ does have infinite loops because programmers want that. It just won't have an elegant way to express it like Rust.

timeon 1y ago

Sorry for commenting on the form but that picture is bit too much for me. (Not because how it was produced.)

QuadmasterXLII 1y ago

tricky tricky- I think this stops well before 10^^15 due to the limits of 64 bit addressing

carlkcarlk 1y ago
Yes, the article figures that with a limit of 64GB of memory, with simple nested loops, you could only loop about 10^(165 billion) steps. To get 10^^15 steps, the article assumes "any amount of zero-initialized memory". (It calls that assumption "unrealistic but interesting".)
- kryptiskt 1y ago
  You can hook it up to a cloud service, say an S3 bucket, and allocate storage space as needed. Then it fulfills the condition of unbounded memory, at the small price of unbounded cost. But it will not be a problem during your lifetime. If you are cloud-averse, you could do the same with networked storage on your local LAN and just connect more disks when it's running out.

carlkcarlk 1y ago

Here is the [final function in Python](https://towardsdatascience.com/how-to-optimize-your-python-program-for-slowness/ https://towardsdatascience.com/how-to-optimize-your-python-p...): (Regular Python `int` is arbitrary precision, but immutable, so I use `gmpy2.xmpz` instead.) def tetrate(a, tetrate_acc): assert is_valid_other(a), "not a valid other" assert is_valid_accumulator(tetrate_acc), "not a valid accumulator" assert a > 0, "we don't define 0↑↑b" exponentiate_acc = xmpz(1) for _ in count_down(tetrate_acc): multiply_acc = xmpz(1) for _ in count_down(exponentiate_acc): add_acc = xmpz(0) for _ in count_down(multiply_acc): for _ in range(a): add_acc += 1 multiply_acc = add_acc exponentiate_acc = multiply_acc return exponentiate_acc And here is the final function in Rust: (I used `&mut` instead of returned values because I don't think Rust guarantees that returned owned values aren't copied.) fn tetrate(a: u32, acc: &mut BigUint) { assert!(a > 0, "we don’t define 0↑↑b"); let mut exp = BigUint::from(1u32); for () in acc.count_down() { let mut mul = BigUint::from(1u32); for () in exp.count_down() { let mut add = BigUint::ZERO; for () in mul.count_down() { for _ in 0..a { add += 1u32; } } mul = add; } exp = mul; } *acc = exp; }