Niche optimization in HalfEdgeMesh

[ratmice]

Just looking through the HalfEdge implementation, it looks as though it should be possible to implement a niche optimization

lox/src/core/half_edge/mod.rs

Line 194 in 80c0e20

half_edges: DenseMap<HalfEdgeHandle, HalfEdge<C>>,

with HalfEdge defined as

lox/src/core/half_edge/mod.rs

Line 101 in 80c0e20

struct HalfEdgeHandle(hsize);

If that were switched from using DenseMap which uses a StableVec internally to a map using InlineStableVec which would use Option, then define HalfEdge using the NonZero variants then adding/subtracting on creation indexing.

It looks like trying it out would be a bit involved but overall doesn't really require any major refactors that would impact other parts of the code base, with the main thing being the alternative to DenseMap and NonZero Handle implementation. Was curious if you had tried that, or if feel like it's worth trying.

Edit:
What would be really nice here if there was a NonMax* as mentioned in rust-lang/rust#45842
That would allow for just checking when the handle is created rather than having to do arithmetic whenever it is used.
unfortunately afaik nothing in std which implements niches for _::MAX.
There is this crate though that emulates it https://crates.io/crates/nonmax but it is just a wrapper around NonZero*.

[LukasKalbertodt]

Hi!

You said "with HalfEdge defined as" and linked the definition of the HalfEdgeHandle. The actual definition (and whats relevant for the niche optimization inside InlineStableVec) is:

lox/src/core/half_edge/mod.rs

Lines 233 to 248 in 80c0e20

	struct HalfEdge<C: Config> {
	/// The adjacent face, if one exists.
	face: Opt<Checked<FaceHandle>>,
	/// The vertex this half edge points to.
	target: Checked<VertexHandle>,
	/// The next half edge around the face or hole this half edge is adjacent
	/// to (going counter clock wise).
	next: Checked<HalfEdgeHandle>,
	/// The previous half edge around the face or hole this half edge is
	/// adjacent to (counter clock wise). This is only stored when the
	/// configuration `C` says so.
	prev: <C::PrevEdge as OptionalField>::Storage<Checked<HalfEdgeHandle>>,
	}

But this just stores a bunch of handles, so the end result is the same: handles would need to use NonZero* for Option<HalfEdge> to get niche optimization. (Side note: as you can see there, I already use custom niche optimization by using max_value() as None sentinel. So I had this problem already and decided to solve it like that.)

And I did consider it back then, but it brings a few disadvantages. So either you have to subtract 1 before doing any index access or waste one element of space or something like that. -1 is apparently supported in the x86 built-in addressing modes, but I'm not sure if the encoded instruction is longer. And generally there could be other ways how a bunch of - 1 could reduce performance.

But I don't know because I haven't tried & measured it. So yes it could very well be worth a shot, but also yes: it would be a bit of work as this "start at 0" assumption is baked in lots of parts of the library.

A different approach would be to adjust stable-vec (e.g. add a new core) that allows setting custom sentinel values, so one could use something other than 0. I think this might be the most fruitful approach in this situation...

Is it worth trying? If it's for fun, then for sure. In terms of "product", I think my time would be way more valuable when spent on other things, like re-introducing the IO module. So I certainly won't work on this anytime soon. I don't want to stop you and I am certainly interested in the results, but I can't promise I would be merging this if I find the disadvantages overweight.

I hope this answers your questions :)

[ratmice]

Yeah, this does answer my questions, I didn't want to make too much effort if it turned out the reason it isn't here is because it was tried, measured and all the arithmetic makes it worse.

I had started working on an attempt based on the nonmax crate (which could in theory eventually allow avoiding the arithmetic if rust ever gained a similar NonMax type).
The main issue that I ran into was the hard coding of the hsize type into Handle. Which then makes it difficult to translate the sentinel value over to the Checked type that you mention.

I wouldn't expect you to merge it of course, Mostly this is just for getting a better understanding of the implementation by poking at the internals a little, so I guess that counts more as "for fun", than "product".

Anyhow if I do manage to get it working, I'll go ahead and make a PR.