To elaborate on that some more, safe Rust can guarantee that mutable aliasing never happens, without solving the halting program, because it forbids some programs that could've been considered legal. Here's an example of a function that's allowed:
fn foo() {
let mut x = 42;
let mut mutable_references = Vec::new();
let test: bool = rand::random();
if test {
mutable_references.push(&mut x);
} else {
mutable_references.push(&mut x);
}
}
Because only one if/else branch is ever allowed to execute, the compiler can see "lexically" that only one mutable reference to `x` is created, and `foo` compiles. But this other function that's "obviously" equivalent doesn't compile:
fn bar() {
let mut x = 42;
let mut mutable_references = Vec::new();
let test: bool = rand::random();
if test {
mutable_references.push(&mut x);
}
if !test {
mutable_references.push(&mut x); // error: cannot borrow `x` as mutable more than once at a time
}
}
The Rust compiler doesn't do the analysis necessary to see that only one of those branches can execute, so it conservatively assumes that both of them can, and it refuses to compile `bar`. To do things like `bar`, you have to either refactor them to look more like `foo`, or else you have to use `unsafe` code.
Isn't this a pretty trivial observation, though? All code everywhere relies on the absence of UB. The strength of Rust comes from the astronomically better tools to avoid UB, including Miri.
Miri is good, but it still has very significant large limitations. And the recommendation of using Miri is unlikely to apply to using similar tools for many other programming languages, given the state of UB in the Rust ecosystem, as recommended by
>If you use a crate in your Rust program, Miri will also panic if that crate has some UB. This sucks because there’s no way to configure it to skip over the crate, so you either have to fork and patch the UB yourself, or raise an issue with the authors of the crates and hopefully they fix it.
>This happened to me once on another project and I waited a day for it to get fixed, then when it was finally fixed I immediately ran into another source of UB from another crate and gave up.
Further, Miri is slow to run, discouraging people to use it even for the subset of cases that it can catch UB.
>The interpreter isn’t exactly fast, from what I’ve observed it’s more than 400x slower. Regular Rust can run the tests I wrote in less than a second, but Miri takes several minutes.
If Miri runs 50x slower than normal code, it can limit what code paths people will run it with.
So, while I can imagine that Miri could be best in class, that class itself has significant limitations.
> So, while I can imagine that Miri could be best in class, that class itself has significant limitations.
Sure -- but it's still better than writing similar code in C/C++/Zig where no comparable tool exists. (Well, for C there are some commercial tools that claim similar capabilities. I have not been able to evaluate them.)
It's funny that when OpenAI developed GPT-2, they've been warning it's going to be disruptive. But the warnings were largely dismissed, because GPT-2 was way too dumb to be taken as a threat.
You can't use this implementation to bootstrap Rust (in the sense of bootstrapping from non-Rust language or a compiler that isn't the rustc).
This GCC support here is only a backend in the existing Rust compiler written in Rust. The existing Rust compiler is using GCC as a language-agnostic assembler and optimizer, not as a Rust compiler. The GCC part doesn't even know what Rust code looks like.
There is a different project meant to reimplement Rust (front end) from scratch in C++ in GCC itself, but that implementation is far behind and can't compile non-toy programs yet.
Compression is limited by the pigeonhole principle. You can't get any compression for free.
There's every possible text in Pi, but on average it's going to cost the same or more to encode the location of the text than the text itself.
To get compression, you can only shift costs around, by making some things take fewer bits to represent, at the cost of making everything else take more bits to disambiguate (e.g. instead of all bytes taking 8 bits, you can make a specific byte take 1 bit, but all other bytes will need 9 bits).
To be able to reference words from an English dictionary, you will have to dedicate some sequences of bits to them in the compressed stream.
If you use your best and shortest sequences, you're wasting them on picking from an inflexible fixed dictionary, instead of representing data in some more sophisticated way that is more frequently useful (which decoders already do by building adaptive dictionaries on the fly and other dynamic techniques).
If you try to avoid hurting normal compression and assign less valuable longer sequences of bits to the dictionary words instead, these sequences will likely end up being longer than the words themselves.
The standard compressed formats don't literally contain a dictionary. The decompressed data becomes its own dictionary while its being decompressed. This makes the first occurrence of any pattern less efficiently compressed (but usually it's still compressed thanks to entropy coding), and then it becomes cheap to repeat.
Brotli has a default dictionary with bits of HTML and scripts. This is built in into the decompressor, and not sent with the files.
The decompression dictionaries aren't magic. They're basically a prefix for decompressed files, so that a first occurrence of some pattern can be referenced from the dictionary instead of built from scratch. This helps only with the first occurrences of data near the start of the file, and for all the later repetitions the dictionary becomes irrelevant.
The dictionary needs to be downloaded too, and you're not going to have dictionaries all the way down, so you pay the cost of decompressing the data without a dictionary whether it's a dictionary + dictionary-using-file, or just the full file itself.
Which is why the idea is to use a previous version of the same file, which you already have cached from a prior visit to the site. You pay the cost of decompressing without a dictionary, but only on the first visit. Basically it's a way to restore the benefits of caching for files that change often, but only a little bit each time.
Of course, the Brotli default (built-in) dictionary is infamous for containing such strings like "Holy Roman Emperor", "Confederate States", "Dominican Republic", etc., due to the way it was created. One can see the whole dictionary in https://gist.github.com/duskwuff/8a75e1b5e5a06d768336c8c7c37....
Having a dictionary created by actual content to be compressed will end up with a very different dictionary.
> The dictionary needs to be downloaded too, and you're not going to have dictionaries all the way down
We already have a way to manage this: Standardizing and versioning dictionaries for various media types (also with a checksum), and then just caching them locally forever, since they should be immutable by design.
To prevent an overgrowth of dictionaries with small differences, we could require each one to be an RFC.
Per-URL dictionaries (where a URL is its own dictionary) are great, because they allow updating to a new version of a resource incrementally, and an old version of the same resource is the best template, and there's no extra cost when you already have it.
However, I'm sceptical about usefulness of multi-page shared dictionaries (where you construct one for a site or group of pages). They're a gamble that can backfire.
The extra dictionary needs to be downloaded, so it starts as an extra overhead. It's not enough for it to just match something. It has to beat regular (per-page) compression to be better than nothing, and it must be useful enough to repay its own cost before it even starts being a net positive. This basically means everything in the dictionary must be useful to a user, and has to be used more than once, otherwise it's just an unnecessary upfront slowdown.
Standard (per-page) compression is already very good at removing simple repetitive patterns, and Brotli even comes with a default built-in dictionary of random HTML-like fragments. This further narrows down usefulness of the shared dictionaries, because generic page-like content is enough to be an advantage. They need to contain more specific content to beat standard compression, but the more specific the dictionary is, the lesser the chance of it fitting what the user browses.
The tool has a great potential, but I always found it too limited, fiddly, or imprecise when I needed to optimize some code.
It only supports consecutive instructions in the innermost loops. It can't include nor even ignore any setup/teardown cost. This means I can't feed any function as-is (even a tiny one). I need to manually cut out the loop body.
It doesn't support branches at all. I know it's a very hard problem, but that's the problem I have. Quite often I'd like to compare branchless vs branchy versions of an algorithm. I have to manually remove branches that I think are predictable and hope that doesn't alter the analysis.
It's not designed to compare between different versions of code, so I need to manually rescale the metrics to compare them (different versions of the loop can be unrolled different number of times, or process different amount of elements per iteration, etc.).
Overall that's laborious, and doesn't work well when I want to tweak the high-level C or Rust code to get the best-optimizing version.
In the safe subset of Rust it's guaranteed in all cases. Even across libraries. Even in multi-threaded code.