Skip to content
This repository has been archived by the owner on Jul 8, 2024. It is now read-only.

Revisit intersection algorithm based on JSC's Set implementation #91

Closed
rkirsling opened this issue Feb 2, 2023 · 2 comments · Fixed by #94
Closed

Revisit intersection algorithm based on JSC's Set implementation #91

rkirsling opened this issue Feb 2, 2023 · 2 comments · Fixed by #94

Comments

@rkirsling
Copy link
Member

rkirsling commented Feb 2, 2023

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
Copy link
Collaborator

bakkot commented Feb 11, 2023

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
Copy link
Collaborator

bakkot commented Mar 21, 2023

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.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants