Use `slice-dst` until custom DSTs land

[MattesWhite]

I started reading about DSTs and stumbled upon the slice-dst crate. With it it should be possible to implement Iri (and IriRef) as DSTs right now. The caveat is that we can't use a Vec for the Buf types but I wrote an example that demonstrates how a mutable buffer can be implemented with slice-dst (cf. CAD97/pointer-utils#70). Actually, most changes would be to re-write the replace function.

[timothee-haudebourg]

Sounds nice, I'll look into it.

[timothee-haudebourg]

It is actually a good theoretical idea, but I don't think it would be a good idea in our case. The header is not stored in the fat pointer but in the slice/array itself. This means that functions such as Iri::from_str or even Iri::new are impossible to implement since they borrow the user input slice, over which we have no control (so we cannot insert our header into it).

[MattesWhite]

Okay, then I had a misunderstanding. I thought your goal was to implement Iri and IriRef as slice-like types like str and [u8] which both have no constructors. In fact, there is only a static constructor for &'static str namely the string literals. And a similar iri! macro already exists.

I think the question is where to put ParsedIriRef. The benefit I see storing it inline like in my example for slice-dst is that Iri (and IriRef) would really work like str. The life time of Iri could be removed and traits like AsRef<Iri>, Borrow<Iri>, ToOwned<Owned = IriBuf> and so on could easily be implemented.
Storing ParsedIriRef on stack and point to the 'data slice' is the current implementation. As can be seen, there are some difficulties with lifetimes, borrowing Iri from IriBuf without cloning ParsedIriRef and inconsistency with standard traits, e.g. Borrow and ToOwned.
Another idea that comes to my mind would be to use references for ParsedIriRef and the 'data slice' which doesn't solve the problems of the current implementation as far as I can see. Maybe I'm wrong.
The last (and worst) would be to make Iri only a wrapper around str that ensures that the underlying data is a valid Iri. This way methods like Iri::from_str could still work but on each operation you'd have to parse the str again.

[timothee-haudebourg]

I thought your goal was to implement Iri and IriRef as slice-like types like str and [u8] which both have no constructors

I'm not sure what you mean by "slice-like types". My idea is to implement Iri and IriRef as DSTs, where a reference &Iri is represented as a fat pointer (ParsedIriRef, *const u8). Indeed this is much like the str DST for which &str is stored as a fat pointer (usize, *const u8). This implementation would allow a low cost conversion between &Iri and &str where we only would have to replace the metadata of the fat pointer, without touching to the actual data.

I think the question is where to put ParsedIriRef

Exactly, and there are only two solution: either we store it in the metadata (ideal) or in the data (not ideal). With slice-dst, the metadata is still usize and the header (in our case ParsedIriRef) has to be stored in the data, which means that a conversion between &Iri and &str is not possible anymore. So until custom DSTs are shipped, the only solution I see is the current one: wrapping &'a str inside a Iri<'a> that also contains our header (extending the metadata).

I agree that this is not an ideal solution (for the reasons you mentioned), but I think it is the best we can do for now.

[MattesWhite]

Exactly, and there are only two solution: either we store it in the metadata (ideal) or in the data (not ideal).

Okay I had to read up on DSTs again to get that. So the idea is to store ParsedIriRef as part of the fat pointer that points to an Iri. Well, given that ParsedIriRef takes 12 words of space (96 bytes on a 64bit machine) I don't think that's a good idea. Given that references are Copy that would mean to always copy 104 bytes (including the data pointer) when we pass around a &Iri. I don't feel that that follows Rust's principle of making expensive operations explicit. In contrast, storing ParsedIriRef inline with the data on the heap would prevent copying the metadata.

With slice-dst, the metadata is still usize and the header (in our case ParsedIriRef) has to be stored in the data, which means that a conversion between &Iri and &str is not possible anymore.

I think this is only half true. You can still return an &str by pointing to the 'data' slice stored on the heap (cf. from_utf8(). However, the other way around wouldn't work. You can't just write 96 bytes in front of the memory of a &str. Especially, as &'static str are normally stored in the read-only memory section of a binary.

[timothee-haudebourg]

Well, given that ParsedIriRef takes 12 words of space (96 bytes on a 64bit machine) I don't think that's a good idea.

That's already what is happening with Iri and IriRef though. Both types are Copy. But there are ways to optimize this. For instance we could use usize instead of Option<usize> in ParsedIriRef with a special value for None, that would reduce the size of the metadata to 64 bytes. We can even use u32 or even u16 instead of usize (this may even be a parameter of Iri) since Iris are generally small. That would go down to 22 bytes total. If you know that the Iri will not be larger than 254 bytes, you can specify u8 and go down to 15 bytes total. I really don't think it is that bad. And if you really don't want to copy this much data, you can use &&Iri instead.

I was more or less waiting for custom DSTs before introducing those optimizations, but I could do that now.

However, the other way around wouldn't work

And in my experience this way is the most important: you generally create IRIs by borrowing a string or byte slice and rarely go the other way unless you want to display them.

[timothee-haudebourg]

Note that I may have been a bit optimistic about alignment considerations here. In the last case, we will most probably end up with 16 bytes and not 15, with a 1 byte padding after ParsedIriRef so that it is correctly aligned.

[timothee-haudebourg]

I should add that If you don't care about the &str -> &Iri conversion, then I'm not sure using DSTs are really useful at all. You can directly use IriBuf since the conversion &IriBuf -> &str already exists. It is already a "store the header in the data" solution (and bonus, it is mutable) 😄

Now that I think of it, what could be interesting is an equivalent of IriBuf stored on the stack instead of the heap maybe backed with smallvec or constvec. The actual storage type could be a parameter of IriBuf with a default to Vec.

[MattesWhite]

Okay, alright I hadn't the memory optimization in mind. On that regard:

But there are ways to optimize this. For instance we could use usize instead of Option<usize> ... with a special value for None, ...

Instead of doing such an implicit contract, I recommend leveraging Rust's type system with non-zero integers. They are built for exact this use case where:

use std::mem::size_of;
assert_eq!(size_of::<Option<core::num::NonZeroU16>>(), size_of::<u16>());

[timothee-haudebourg]

I'm closing this now, but we can continue the discussion on the metadata optimization in #10.