Stream: t-compiler/wg-rls-2.0

Topic: Salsa q


osa1 (May 02 2020 at 09:50, on Zulip):

I'm studying salsa -- in this line https://github.com/salsa-rs/salsa/blob/master/src/interned.rs#L272 how do we guarantee that values.len() won't be 0 ? It's initialized as an empty vector, so it seems to me that it's possible to get a 0 there, but that would break InternId (which can't be 0), so I'm wondering what I'm missing.

matklad (May 02 2020 at 09:52, on Zulip):

we don't we +1 instead: https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L64

osa1 (May 02 2020 at 09:53, on Zulip):

Hmm but tables.values.len() is a usize, not u32, right?

matklad (May 02 2020 at 09:53, on Zulip):

which goes via this impl: https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L112-L117

osa1 (May 02 2020 at 09:53, on Zulip):

I was expecting that we'd call this line https://github.com/salsa-rs/salsa/blob/fecec6bab2ea218b1fad45aa910cddb85284fc29/src/intern_id.rs#L115

matklad (May 02 2020 at 09:54, on Zulip):

Yes, we do, and new_uncecked does +1

osa1 (May 02 2020 at 09:54, on Zulip):

Ahh, I see. Thanks!

osa1 (May 02 2020 at 10:08, on Zulip):

Another related question, why is the max value of InterId defined as 0xFFFF_FF00 instead of std::u32::MAX ?

matklad (May 02 2020 at 10:14, on Zulip):

For future compatability

matklad (May 02 2020 at 10:14, on Zulip):

Ideally, we want to use not the NonZero, but "highest two bits are zero"

matklad (May 02 2020 at 10:14, on Zulip):

This is what rustc is using, and it is measurably faster

matklad (May 02 2020 at 10:15, on Zulip):

but to do that, you need unstable API to specify valid patterns precisely

osa1 (May 02 2020 at 10:17, on Zulip):

Do you mean least significant bits? Why does that matter for performance?

matklad (May 02 2020 at 10:18, on Zulip):

no, I mean highest

matklad (May 02 2020 at 10:19, on Zulip):

with no-zero, you need to do - 1 for every index access, which is not free

matklad (May 02 2020 at 10:19, on Zulip):

with "highlest two bits are always zero", you don't need to do anything special for indexing, but you still have space for niche-filling

osa1 (May 02 2020 at 10:20, on Zulip):

Why does highest bits matter for - 1 performance? What do you mean by "special"?

matklad (May 02 2020 at 10:22, on Zulip):

two cases:

Case 1:

idx is a NonZeroU32 index. To access vector element, we need to do xs[idx as usize - 1] (we need -1, b/c we added one when creating the index)

Case 2:

idx is TwoHighestBitsAreZero index. To access vector element, we need to do xs[idx as usize]

osa1 (May 02 2020 at 10:26, on Zulip):

Ahh, so same optimizations are applied to TwoHighestBitsAreZero (e.g. Option<TwoHighestBitsAreZero> has the same size as TwoHighestBitsAreZero) ?

matklad (May 02 2020 at 10:27, on Zulip):

yup

osa1 (May 02 2020 at 10:31, on Zulip):

OK, but I still can't relate that to the max value chosen for InterId. Max value for TwoHighestBitsAreZero would be 0x3FFFFFFF, I think

matklad (May 02 2020 at 10:34, on Zulip):

riiight, I think this actually might be a bug?

matklad (May 02 2020 at 10:34, on Zulip):

Or it might also be me not understanding things...

osa1 (May 02 2020 at 10:45, on Zulip):

OK, thanks for the answers. This has been educational to me. Another question: why does InternId implement From<u32> and From<usize>? That means users of salsa can invent InternIds out of thin air, which shouldn't be possible, I think. I'd expect to obtain InternIds only by interning.

Last update: May 29 2020 at 17:55UTC