EvaluationDomain::reindex_by_subdomain ergonomics and doc improvements

[ggutoski]

Here's the method signature:

algebra/poly/src/domain/mod.rs

Lines 284 to 287 in 273bf21

	/// Given an index which assumes the first elements of this domain are the
	/// elements of another (sub)domain,
	/// this returns the actual index into this domain.
	fn reindex_by_subdomain(&self, other: Self, index: usize) -> usize {

Wish list

• The caller must pass ownership of other. Thus, anyone who wants to use this method must clone other, which seems wasteful. Instead the type of other should be &Self. But this item is obsoleted by the next item...
• The only use of other in this implementation is to call other.size(), which merely returns a usize struct field. Thus, there is no need for an already-constructed EvaluationDomain for other here. Indeed, I suspect a common use of this method is where a caller knows the size of other but hasn't actually constructed a EvaluationDomain for it. In those use cases this method forces the caller to construct an EvaluationDomain just to call this method. I suggest changing the type of other from Self to usize. In that case it's name should be changed to something like other_domain_size.
• Code comments are hard for me to understand. Seems like the rustdoc for this method should read something like

/// Convert `index` from [an index into an element from `other`] into [an index of an element from `self`].
///
/// `other` must be a sub-domain of `self`.
/// etc.

• The following comment
  

  algebra/poly/src/domain/mod.rs

  Lines 289 to 292 in 273bf21

  	// Let this subgroup be G, and the subgroup we're re-indexing by be S.
  	// Since its a subgroup, the 0th element of S is at index 0 in G, the first
  	// element of S is at index |G|/|S|, the second at 2*|G|/|S|, etc.
  	// Thus for an index i that corresponds to S, the index in G is i*|G|/|S|

  
  can be replaced with something shorter:

// `other` is a subgroup of `self`. Thus, index `i` in `other` is index `i*|self|/|other|` in `self.

• I don't understand the following comment
  

  algebra/poly/src/domain/mod.rs

  Lines 297 to 304 in 273bf21

  	// Let i now be the index of this element in G \ S
  	// Let x be the number of elements in G \ S, for every element in S. Then x =
  	// (|G|/|S| - 1). At index i in G \ S, the number of elements in S
  	// that appear before the index in G to which i corresponds to, is
  	// floor(i / x) + 1. The +1 is because index 0 of G is S_0, so the
  	// position is offset by at least one. The floor(i / x) term is
  	// because after x elements in G \ S, there is one more element from S
  	// that will have appeared in G.

  
  It's not clear to me why this method should allow index >= other.size(). Shouldn't this be an out-of-bounds error?

[Pratyush]

Thanks @ggutoski! I think these changes make sense; if you'd like to make a PR with these changes, that would be great.

cc @ValarDragon also, since I think you implemented this change first?

[ggutoski]

It's not clear to me why this method should allow index >= other.size(). Shouldn't this be an out-of-bounds error?

I think I now understand the purpose for this case.

I suspect most use cases care only about where the indexth element of other occurs within self; this is the case index < other.size(). But some cases might wish to reorder all elements of self so that elements of other appear first. Such use cases can use reindex_by_subdomain to find where the indexth element of self occurs in this new ordering, including those index >= other.size().

Let's work through an example where self has size 16 and other has size 4.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
reindexed	0	4	8	12	1	2	3	5	6	7	9	10	11	13	14	15