News for hackers. Stuff that matters.
Re:Rust 1.50 by k__ on Thursday February 11, 2021 @11:14AM (#26103241)
Do C/C++ use such optimizations or is their type system too brittle?
Re:Rust 1.50 by steveklabnik on Thursday February 11, 2021 @11:16AM (#26103282)
I am a non-expert in the exact semantics of C and C++ layout, but as far as I can recall off the top of my head, they do not, because the general semantics are "lay out the struct in the order as declared, add padding for alignment reasons, done."

Whereas the semantics in Rust are "we can do whatever we want unless you add an explicit #[repr] attribute, in which case you choose the semantics of layout and we don't mess with it."

It's not about the strength of the type system, it's about history.

Re:Rust 1.50 by MaulingMonkey on Thursday February 11, 2021 @11:51AM (#26103843)
Theoretically you could roll your own such optimizations manually in a C++ codebase by abusing partial specialization. That is, you could write:

    template < typename T >
    class optional< std::vector<T> > {
        // ...
    };
And write an implementation that (ab)uses knowledge of the exact layout of `std::vector<T>` to avoid an extra bool. This would of course be a breaking change to the ABI of optional<std::vector<T>> if implemented by std::optional, so compiler vendors tend to avoid such things.

There is one stdlib example of this, but sadly it's more infamous than inspirational: std::vector<bool>. The standard relaxes several guarantees of std::vector<T> in the case of T == bool, to allow it to bit-pack the booleans instead of using sizeof(bool) - e.g. an entire byte - per element.

Some of those relaxed guarantees make std::vector<T> unsuitable for interop with C style APIs taking pointers + lengths if T might be a bool. Worse still, many (most?) implementations don't even implement the space optimization those guarantees were relaxed for - a worst of both worlds situation. If you actually need such space optimizations, you'll reach for an alternative such as boost::dynamic_bitset which provides them consistently.

Re:Rust 1.50 by steveklabnik on Thursday February 11, 2021 @11:52AM (#26103868)
This is a good point; given that it's automatic in Rust, I assumed that they parent was talking about it happening automatically, but you are right that you absolutely can do this manually, and it's good to have that nuance. After all, this PR required manual intervention to get the automatic parts to kick in!
Re:Rust 1.50 by MereInterest on Thursday February 11, 2021 @11:35AM (#26103594)
Sort of. You're right on what the abstract C++ machine does, but C++ also has the "as if" rule. A compiler can make whatever changes it wants so long as all observable effects are as if it had generated exactly the program as requested. This is the rule that allows for compiler optimizations to be done. Values stored in memory are not considered to be observable effects, so the compiler is allowed to make whatever changes it wants on that end.

However, to the best of my understanding, most types are exposed to other compilation units, so it is hard to establish invariants about how they are used. Unless the compiler can verify that nowhere in the program ever takes the address of a boolean variable in a struct, it isn't allowed to rearrange the struct to avoid having that extra boolean. That might be possible at link-time for statically linked programs, but I'm not sure.

Also, my knowledge is mostly from programming in C++ and watching CppCon talks, so I may be out of date from the latest optimization techniques.

Re:Rust 1.50 by tjalfi on Thursday February 11, 2021 @04:06PM (#26107175)
That particular optimization is unlikely but there have been C compilers that optimized struct layout.

179.art, one of the SPEC2000 benchmarks, has some poorly laid out structs. Sun introduced targeted optimizations for this benchmark and several other vendors also did so. I have also read papers about profile-guided struct reordering but don't have a citation on hand.

GCC also had a pass[0] for this optimization but it may have been removed.

[0] https://www.research.ibm.com/haifa/dept/_svt/papers/golovane...

Re:Rust 1.50 by k__ on Thursday February 11, 2021 @11:22AM (#26103378)
I see, thanks.

Pretty cool to see that Rust can do more optimizations than other languages.

And it seems to play out well. I fondly remember Java being touted as being superior to C/C++ because it can do runtime optimizations, which will outperform C/C++. Somehow this never happened.

Re:Rust 1.50 by brundolf on Thursday February 11, 2021 @11:25AM (#26103430)
There are some cases, like the Option<&T>::None case, where C/C++ do roughly the same thing just without any type guards. So in this case: pointers in C/C++ can simply be null, which is not expressed at a type level but is lumped in as a special case of the pointer value itself instead of being a separate bit. i.e. the optimization in this case is only necessary for Rust because it normally represents the enum variant as a separate component of the value in addition to its contents. The optimization brings it back in line with C/C++ from a memory usage standpoint.

However, because there are no type guards for this stuff in C/C++ you're generally constrained by convention/intuitiveness, when picking these special values, in order to (hopefully) guard against accidental misuse. So in the NonZero case above, you probably wouldn't do that because it's pretty unusual, and you'd therefore use more memory.

And then, even when the "special values" are chosen "reasonably", they sometimes get misused anyway and we end up with bugs like last year's trivial sudo exploit: https://bit-sentinel.com/to-sudo-or-not-to-sudo-demystifying...

> Reading the manual for those functions we learn that -1 is a special value

> Supplying a value of -1 for either the real or effective user ID forces the system to leave that ID unchanged.

> If one of the arguments equals -1, the corresponding value is not changed.

> So, what happens when we send -1 as a parameter? Well, somewhere along the underlying code lines is a convention that -1 is represented as 4294967295, thus either values will get the wanted result.

Edit: In practice the above may be more common in C than modern C++

Re:Rust 1.50 by lpapez on Thursday February 11, 2021 @11:19AM (#26103344)
When it comes to std::optional, the answer is no. In fact, std::optional<T&> is explicitly forbidden (see here: https://www.fluentcpp.com/2018/10/05/pros-cons-optional-refe...)

It is used in some other places though. For instance, std::string implementations typically employ small-string optimization (SSO) which means that there might be a limit on string::size() since some of the bits inside that value are used for different purposes (example: https://akrzemi1.wordpress.com/2014/04/14/common-optimizatio...). The "niche" in this case is the realization that strings are unlikely to be exabytes in size, so there is no reason to always store zeros in high bits of _size.

Re:Rust 1.50 by steveklabnik on Thursday February 11, 2021 @11:21AM (#26103364)
Fun trivia fact: Rust's stdlib String type cannot, and therefore does not, support SSO.
Re:Rust 1.50 by pdimitar on Thursday February 11, 2021 @11:38AM (#26103645)
I recently wondered if a library like `smol_str` will be upstreamed one day. I feel people would rejoice if they can use stack-allocated strings (up to a certain size).

Do you think that's possible?

Re:Rust 1.50 by steveklabnik on Thursday February 11, 2021 @11:40AM (#26103658)
Anything is possible, but it's not clear to me what advantage being in the standard library would actually bring. It is a pretty niche use-case (and I work in embedded these days), and it is pretty trivial to use a package.

Only the libs team can really say, and I'm not on that team.

Re:Rust 1.50 by pdimitar on Thursday February 11, 2021 @03:44PM (#26106877)
I'm looking at it through the lens of "let Rust have the best possible newcomer experience", which of course isn't a sentiment that has to be shared by the creators.

I suppose I appreciate SmallString's ability to alias itself to Rust's String.

But I'd immediately agree that this adds hidden complexity and the potential for it to bite you in the worst possible moment.

Re:Rust 1.50 by brundolf on Thursday February 11, 2021 @04:03PM (#26107133)
Going along with the other replies, I disagree that this would improve the experience for newcomers. SmallString is a hyper-optimization for specialized use-cases which (I would assume) is rarely worthwhile. I would actively discourage people from using SmallString without first profiling to identify Strings as their bottleneck, especially newcomers. String will almost always be "fast enough".
Re:Rust 1.50 by pdimitar on Thursday February 11, 2021 @04:41PM (#26107697)
Agreed that it's a very likely unneeded optimization. As shared in another sibling comment, I got frustrated with Rust's strings and figured that maybe one more complexity on top wouldn't be that bad. But thinking of it now, yeah, it's definitely a bad idea.
Re:Rust 1.50 by pornel on Thursday February 11, 2021 @03:55PM (#26107018)
I like that Rust's String is not trying to be smart. It makes it predictable and easy to reason about.

Because Rust has &str as the lowest common denominator for all string types, "non-standard" strings aren't difficult to use.

Re:Rust 1.50 by pdimitar on Thursday February 11, 2021 @04:40PM (#26107687)
I agree that less smartness is a good thing, it's just that sometimes I get a bit frustrated even with basic usages of Rust's String and &str. It gets easier with time but the first few months were a big struggle.
Re:Rust 1.50 by steveklabnik on Thursday February 11, 2021 @03:52PM (#26106986)
Even with that perspective, you can disagree. Offering even more string types may be more confusing for users.
Re:Rust 1.50 by pdimitar on Thursday February 11, 2021 @04:04PM (#26107158)
Yep. I was kind of thinking out loud but was curious about your perspective. Thank you.
Re:Rust 1.50 by steveklabnik on Thursday February 11, 2021 @04:23PM (#26107453)
Totally! That's how progress is made, thinking out loud :) Thank you too!
Re:Rust 1.50 by drran on Thursday February 11, 2021 @11:36AM (#26103615)
If you need [no_std] version, use SmallString/SmallVec. Otherwise, use SmartString, SmolStr, etc.
Re:Rust 1.50 by colejohnson66 on Thursday February 11, 2021 @12:26PM (#26104394)
> The "niche" in this case is the realization that strings are unlikely to be exabytes in size,...

That’s what we say now, but a few dozen years down the line? Old Mac OS versions (pre X) would store extra bits of information in the MSBs of a pointer. “32 bit clean” Mac OS had to be created to allow usage on computers with more than a few dozen megabytes. That was an all too common problem when multiple gigabytes of RAM became commonplace.

Granted, I highly doubt we’ll see exabyte level string lengths, but you never know.

Fun fact: x86-64 mandates pointers be in “canonical” form where all unused bits of the address are the same as the MSB. So on a processor that has 48 address lines, the upper 16 must match the 48th bit. If you try to access memory with a “non canonical” pointer, the processor will throw an exception. This is because they don’t want people using them for flag bits and having a repeat of the “unclean” software problem.

TL;DR: I agree, but never say never

Re:Rust 1.50 by Dylan16807 on Thursday February 11, 2021 @03:47PM (#26106923)
There are two problems with using high pointer bits as flags.

The small problem is that your program will be limited in memory space. That's usually okay. If you want a vast expansion of memory space you probably need to start using different algorithms anyway.

The big problem is that your program depends on the CPU ignoring those bits, and now it can't run at all on updated hardware. As you noted, x86-64 solves this problem by forcing programs to clean up pointers before actually using them.

Re:Rust 1.50 by lpapez on Thursday February 11, 2021 @12:48PM (#26104733)
I think we have quite some before us until the need for these high bits becomes reality :)

Now that you mention pointers, Apple is using unused bits in their values for signing and authentication purposes https://googleprojectzero.blogspot.com/2019/02/examining-poi...

Pretty neat in my opinion

Re:Rust 1.50 by KMag on Thursday February 11, 2021 @12:40PM (#26104616)
And it's too bad that most kernels (including Linux and Windows) put userspace in the low half of the address space. In the upper half of a 48-bit address space (or even 51-bit), all valid pointers, if interpreted as IEEE-754 doubles, are NaN, so you get NaN boxing without performing any arithmetic. (Though, if you want NaN-boxed nullable pointers, you'll need to pick a special value for nullptr.)
Re:Rust 1.50 by colejohnson66 on Friday February 12, 2021 @09:48AM (#26114166)
Why are you treating pointers as floating point numbers?
Re:Rust 1.50 by KMag on Saturday February 13, 2021 @03:28AM (#26122236)
Pointers aren't being treated as doubles. There are 2**53-2 bit patterns for NaN values, and most FPUs (including x87 and the Aarch64 FPU) generate only 2 of those, leaving 2**25-4 values available as a variant on tagged pointers called NaN-boxing/nun-boxing.

NaN-boxing / nun-boxing is a common optimization, as seen in Firefox's SpiderMonkey, Safari's JSC, LuaJIT, etc. If all of your valid pointers are at the top of the address space, you can use 0x0 as the constant you either add/subtract or xor with your values to box/un-box. In other words, Nan-boxing/unboxing becomes a no-op.