| 17:45 | <bakkot> | does anyone who actually knows how Sets are implement know if it is possible to use the internal data structure to efficiently implement something like "order this list, which is a subset of the elements in some Set, according to the order the values in the list would be emitted when iterating the Set" |
| 17:45 | <bakkot> | "efficiently" meaning something like "with time proportional to the size of the list, not the size of the Set" |
| 17:45 | <bakkot> | I am guessing no but I have no idea what the actual implementation looks like |
| 17:50 | <shu> | what is the subset? |
| 17:52 | <bakkot> | uh |
| 17:52 | <bakkot> | like it's some elements of a set |
| 17:52 | <bakkot> | you have 1) a Set x and 2) a list of some (but not necessarily all, and often much less than all) elements from x, which are not ordered according to the order in x |
| 17:53 | <bakkot> | and you want to sort the list according to the order of the elements in x |
| 17:54 | <bakkot> | the list is spec-internal, to be clear, so there's no side effects or anything happening during the process |
| 18:01 | <shu> | i do not understand the use case still, is there something concrete i can read? |
| 18:05 | <shu> | anyway maybe you can get some insight from https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables |
| 18:06 | <bakkot> | you don't understand the use case, or you don't understand the ask? |
| 18:06 | <shu> | i don't understand the use case |
| 18:06 | <shu> | is the sublist static, always same size? is it dynamic? |
| 18:06 | <shu> | what determines membership in the sublist? |
| 18:06 | <shu> | v8 continues to use roughly the same thing as described in jorendorff's wiki page there |
| 18:07 | <shu> | insertion order is simply the ascending order of the Entry array |
| 18:07 | <bakkot> | the use case is to get consistent order for Set.prototype.intersection - depending on which of this vs other is larger, you might be iterating this or other, and it would be nice if the order of the resulting set did not depend on which set was being iterated. |
| 18:07 | <shu> | i see |
| 18:07 | <bakkot> | and the obvious way to do that is to ensure the elements of the resulting set are ordered according to their order in this |
| 18:08 | <bakkot> | but if this is much larger than other, and performing said ordering takes time proportional to the size of this even when the intersection is small, that's bad |
| 18:08 | <shu> | you have two total orders, but how do you compose them into another total order? |
| 18:09 | <bakkot> | for intersection in particular, you don't need to |
| 18:09 | <shu> | ah it's intersection, right i see |
| 18:09 | <shu> | okay, i understand the use case now |
| 18:09 | <shu> | i have no idea how you do this efficiently in the current implementations of Set |
| 18:10 | <bakkot> | I haven't thought through all the other methods yet; it's possible this ordering wouldn't work for some of them. (others, like union, don't have this problem because the optimal algorithm does not produce a result whose order depends on the sizes of the input.) |
| 18:10 | <bakkot> | ok, alas. |
| 18:10 | <shu> | at the cost of either space or time everything is possible |
| 18:10 | <bakkot> | sure |
| 18:11 | <shu> | in this case, ISTM the shortest path would be to also store the index in the hash table Entry struct |
| 18:12 | <bakkot> | (Ashley Claymore has suggested in https://github.com/tc39/proposal-set-methods/issues/70#issuecomment-1179692731 another option which adds a constant factor number of additional calls (not observable when it's a native Set) to get a deterministic if kind of strange order, which is my current leading alternative) |
| 18:12 | <shu> | you can then straightforwardly sort the list of indices pointed to by the elements in the intersection, and the indices in either of the source Sets would work |
| 18:12 | <shu> | but that's an extra int in every entry |
| 18:12 | <shu> | and that seems bad |
| 18:12 | <bakkot> | yeah |
| 18:14 | <shu> | well, wait a second now |
| 18:14 | <shu> | one of the properties of that particular implementation strategy of an ordered hash table is that the Entrys are allocated contiguously in an Entry[] array |
| 18:15 | <shu> | if you build an auxiliary list of the found Entrys in the intersection, you can presumably do address comparison |
| 18:15 | <shu> | i hope that falls out from most implementation languages' array allocation guarantees |
| 18:15 | <bakkot> | ooh, love me some pointer comparisons |
| 18:16 | <shu> | mind you i am not excited to recommend that in a non-normative note |
| 18:16 | <shu> | i don't know how you'd get UB to bite you, but it will |
| 18:16 | <bakkot> | the spec currently doesn't suggest any implementation strategy at all |
| 18:16 | <shu> | right, i'm just saying it seems very particular |
| 18:16 | <bakkot> | actually it might, I forget |
| 18:17 | <shu> | and a touch too clever |
| 18:17 | <bakkot> | yeah |
| 18:17 | <shu> | there are footguns there i'm worried about like |
| 18:17 | <shu> | what if the table is rehashed in the middle of performing the intersection |
| 18:17 | <shu> | is that even possible, i hope not but maybe |
| 18:20 | <shu> | okay so pointer comparison is my final answer and i'm sticking to it |
| 18:20 | <shu> | probably fine |
| 18:20 | <bakkot> | I would expect rehashing not to affect the dataTable itself, just the chain pointers within it, so I'd expect that to be fine |
| 18:21 | <shu> | yes true, so the entry addresses would be stable |
| 18:36 | <bakkot> | I am pretty sure you can replace the Entry* pointers in this document with indices into dataTable (both the chain pointer and the elements of the hashTable array), which makes it more obvious that this works and would work even languages which don't expose pointers |
| 18:37 | <shu> | yes |
| 18:37 | <shu> | but you don't want 2 loads |
| 18:37 | <shu> | unless you are using an inferior "safe" language |
| 18:37 | <bakkot> | sure |
| 18:51 | <Ashley Claymore> | What do we expect the order to be if the receiver is modified during the method call? |
| 18:51 | <bakkot> | as a user I don't have an expectation of what the order would be in that case |
| 18:52 | <bakkot> | so I'm just going to write down the thing which is easiest to implement, namely, elements are ordered according to their position in the list of entries when the algorithm queries them |
| 18:58 | <bakkot> | doing this sorting does add a log(r) factor overhead to theoretical performance (where r is the size of the result) in the case that other is smaller than this, but I expect that to be much cheaper than the overhead of doing more user-observable calls in most cases, so I'm not bothered about it |
| 19:09 | <shu> | i feel like that's fine |
| 19:09 | <shu> | logs aren't real |
| 19:09 | <bakkot> | that is also my belief |
| 19:10 | <shu> | though my beliefs might be incoherent because i believe constant factors are very real |
| 19:14 | <littledan> | as a strict constructivist, I don't believe sets are real |
| 19:14 | <littledan> | so this whole conversation has been moot |
| 19:50 | <TabAtkins> | Sets obviously aren't real, but Maps are. |
| 19:50 | <jschoi> | I assert that Maps aren’t real either, because Maps are not the actual territory. |
| 19:51 | <TabAtkins> | damn |
| 20:47 | <shu> | how do folks feel about Temporal updates as part of plenary? |
| 20:48 | <shu> | no offense meant to ptomato who's doing the important work, but i mostly don't understand or am in a position to have opinions about the normative updates |
| 20:49 | <littledan> | We currently have a pattern that normative updates to Stage 3 proposals need consensus in committee; maybe the timebox should be shortened if people don't actually want to review them and just rubber-stamp? |
| 20:49 | <shu> | yes, that sounds good. if it is non-domain-specific, e.g. behaviors about options bags, then they should be presented |
| 20:50 | <shu> | but something like "we had to update this because the grammar upstream at ISO did this or that" is completely non-actionable for me |
| 20:50 | <littledan> | maybe this can just be during the presentation, that the presenter can ask, "do people want me to go into these details?" |
| 20:50 | <shu> | that might make scheduling harder |
| 20:50 | <littledan> | what would be unfortunate is if Temporal got held back because people said, "this doesn't have committee consensus yet; you can't ship this change" because we were trying to save time |
| 20:51 | <littledan> | Stage 3 makes getting this all nailed down high priority for committee |
| 20:51 | <shu> | i'd like to lean on the temporal champions' judgment on if it's something that runs the risk of that failure mode |
| 20:52 | <shu> | the pattern for the past few meetings doesn't seem like a productive use of time to me |
| 20:52 | <littledan> | i'd like to lean on the temporal champions' judgment on if it's something that runs the risk of that failure mode |
| 20:53 | <shu> | i don't follow |
| 20:53 | <shu> | it's not the pattern today that we skip normative updates for stage 3 proposals as you said |
| 20:53 | <littledan> | I mean, if you want to defer to their judgement on whether to present it to committee... they communicated their judgement by putting this on the agenda |
| 20:53 | <shu> | i'm saying let's change the pattern, and the new pattern would be to lean on the temporal champions' judgment on what normative updates are worth presenting instead of every one |
| 20:54 | <shu> | oh, i wasn't under the impression they were already saying these are the list of updates worth presenting |
| 20:54 | <shu> | if so then i retract |
| 20:54 | <littledan> | OK, sorry, I shouldn't speak for them; they can clarify |
| 20:54 | <shu> | and will just leave with the comment that i don't find them actionable and i zone out |
| 20:58 | <littledan> | I guess if we wanted to address this issue at a broader level we'd work on creating TGs that have the authority to make decisions on things. We could have a Temporal TG that can just decide fully on these changes without bothering plenary, and everyone who may have an opinion is expected to attend. I'd be in favor of this process change, but we haven't done it yet. |
| 20:59 | <shu> | i would also be in favor, and last time we brushed up against it there certainly were headwinds |
| 20:59 | <littledan> | or concretely we'd probably give TG2 (402) this authority and task them with reviewing Temporal even though it's not in 402 |
| 21:00 | <shu> | agreed on TG2 |
| 21:00 | <shu> | chip has raised concerns about other domains as well |
| 21:00 | <shu> | regexps was it? |
| 21:01 | <littledan> | so far we've said, those domains need to come back to plenary, their discussions are just advisory. Remember that I faced significant resistance when I just proposed that we meet in totally non-binding subgroups. |
| 21:01 | <shu> | yes, and similar resistance and concerns when incubator calls were proposed in their initial form |
| 21:02 | <littledan> | well, I think Temporal is doing the right thing for this meeting, and we should probably keep pushing with giving subgroups the power to make decisions |
| 21:02 | <littledan> | but, like, chartered subgroups, not random champion groups, IMO |
| 21:03 | <shu> | yes, agreed on chartered subgroups |
| 21:03 | <shu> | i mean i'd still like to reduce plenary time, but that's probably not a shared goal |
| 21:04 | <shu> | not reduce overall deliberation time over the set of all TC39 proposals mind you, but plenary time |
| 21:29 | <littledan> | Yeah I guess I'm neutral on that, or like it's not my top priority to reduce plenary time; top priority is to make good decisions inclusively, and plenary vs subgroups is more of a means to an end; all else being equal, good to use fewer person-hours, sure |
| 23:29 | <ptomato> | oh, i wasn't under the impression they were already saying these are the list of updates worth presenting |
| 23:30 | <ptomato> | (we haven't) |
| 23:31 | <shu> | ptomato: yeah, that was part of the question |
| 23:32 | <shu> | the other (to the broader committee) was do we feel comfortable leaning on the judgment of the Temporal champions to do the filtering, so only items of broad interest are presented, and we trust to rubber-stamp the rest |
| 23:32 | <ptomato> | well I asked this question previously and the answer was no |
| 23:32 | <shu> | since i don't know enough of the domain to, like, do anything other than rubberstamp |
| 23:33 | <shu> | oh too bad, i had forgotten |
| 23:33 | <ptomato> | yes, I'd love to skip the items that I know nobody cares about |
| 23:33 | <shu> | perhaps i can bring this up again to re-take the temperature |
| 23:33 | <shu> | what was the reasoning last time? |
| 23:35 | <ptomato> | I will look |
| 23:36 | <ptomato> | (FWIW, the status quo is better than the previous status quo, where the answer was "depends on who you ask") |
| 23:39 | <ptomato> | https://github.com/tc39/notes/blob/main/meetings/2022-01/jan-24.md#process-clarification - this is slightly different from what I remembered, good thing we have notes! I guess the "yes, we want this requirement" must have come from conversations before the plenary, the agenda item was only about making the unofficial requirement official |
| 23:58 | <shu> | yeah, i think there's a meaningful difference between "giving up plenary sign-off for normative changes" and "rubberstamp, trust domain experts to follow-up/review" |
| 23:58 | <shu> | the power still rests with plenary in the second case, and is more practical imo... |