Efficient representation of sparse sets with MaybeUninit

I made a proof-of-concept implementation of the Efficient reprentation of sparse sets paper from 1993, that uses memory that's maybe uninitialized.

It seems to work well in practice but unfortunately it doesn't pass the miri test in the method that checks whether a value is contained or not in the set. And I'd like to understand whether it means this can't ever be made in Rust, and why, or whether we can ignore miri in this case, since the logic seems sound otherwise.

1 Like

Unfortunately, this seems to make the assumption that an uninitialized byte is just a byte with some random value. It isn't. See this article for more info.

You could implement this if Rust had a freeze operation, but it doesn't currently.

2 Likes

The logic is fine from we code for the hardware POV. It's totally incompatible with Rust definition, though.

And that's fine: you couldn't make Rust compiler write arbitrary code (Rust compiler just completely refuses to use certain instructions), why do you think any arbitrary data processing approach should be representable in Rust? If you want to write any arbitrary code assembler is your tool of choice (and even then you may need to use .4byte directive directly to emit certain tricky code).

Now, of course for systems level language, that's the omission that couldn't be allowed… and yes, there's a way to do that: just use assembler! Rust compiler, by definition, doesn't know what happens in the asm! block, which, then, may do various tricks, including tricks described in that article.

That may not feel like a satisfactory answer, but… why not? Every single time people start talking about freeze operation they bring that particular article… there may be others, but, ultimately, the question that arises: is the complexity that such operations bring to the language are justified by the ability to implement these few algorithms (there are probably more than that single one, but judging by the fact that I haven't seen anything besides that one there couldn't that many of them)?

The answer, so far, sounds like “no, while writing high-level algorithm in assembler in XXI century sounds a bit silly, if it's only that particular one algorithm… it's easier to write it in assembler than to change the language definition”.

1 Like

That's a wonderful article thank you. It's very clear now.

So are you saying it could be possible to implement the structure in Rust if the key methods are made using inline assembly? Or rather than everything has to be done in assembly, including the allocation...

The methods that access “MaybeUninit” elements and return not “MaybeUninit” values have to be implemented in assembler. At least that's how I understand things.

Unfortunately Miri explicitly doesn't support assembler thus you couldn't use it to verify that everything works and that part of the language is not fully-defined.

I think that creating accessors which would read uninitialized memory should be enough: if you look on the definition of assembler block you would see that nomem and readonly restrictions are opt-in, not opt-out, by default compiler have to assume that assembler block writes into any memory at may legally access (which means that if you pass address of MaybeUnunit buffer to assembler block then compiler have to assume that it would be fully initialized after return, which would implement poor-man's-freeze AFAICS).

But I think it would be better to ask on IRLO because you are playing near the very edge of what's allowed there.

The question is: would en empty assembler block which receives address of buffer work as “freeze” operation or not, if yes then is it possible to support that in Miri, if no, then how can one use MaybeUnunit with assembler in principle?

1 Like

You still get most of the benefit of the data structure if you initialize the values.

The benefit is in being able to clear the structure in constant time.

1 Like

At least on linux you can use an zeroed vec for sparse data e.g. vec![0u8; 1024*1024*1024]. It gets the zero-page optimization which means it doesn't need explicit initialization and doesn't occupy any physical memory until a page is written to.

If the sparse allocation is much larger than physical ram you may have to disable overcommit heuristics (vm.overcommit_memory = 1) or use mmap(..., MAP_NORESERVE)

3 Likes