Revisit intersection algorithm based on JSC's Set implementation

[rkirsling]

Just making a note here, based on our Matrix conversation:

We need to discuss in next plenary whether we'd like to update the spec for intersection, having identified that JSC cannot "[determine] the relative order of two elements ... without needing to iterate the entire [receiver set]" under its existing Set implementation. (A Set in JSC is a hashmap with a linked list of buckets for iteration.)

[bakkot]

We'll discuss this at the March meeting. If anyone has ideas for possible paths forward, please suggest them - right now all I've got are

• change the algorithm so the order of the result changes depending on the relative sizes of the sets
• change the algorithm (e.g.) so the order is stable with respect to relative sizes but depends on other unexpected details
  • maybe there's a different algorithm which would have less surprising order?
• keep the current ordering requirement but don't place any normative requirements on performance

[bakkot]

In plenary resolved to just drop the sort step, and live with the order depending on the relative sizes of the sets. I'll update the spec soon and close this issue at that point.

[bakkot]

We'll discuss this at the March meeting. If anyone has ideas for possible paths forward, please suggest them - right now all I've got are

• change the algorithm so the order of the result changes depending on the relative sizes of the sets
• change the algorithm (e.g.) so the order is stable with respect to relative sizes but depends on other unexpected details
  • maybe there's a different algorithm which would have less surprising order?
• keep the current ordering requirement but don't place any normative requirements on performance

[bakkot]

In plenary resolved to just drop the sort step, and live with the order depending on the relative sizes of the sets. I'll update the spec soon and close this issue at that point.