Zippering of two sets can fail even when they are the same length

[dlongnecke-cray]

Currently the zippering of two sets can fail even if they are the same length. The number of full slots yielded by each follower currently depends on the distribution of slots in the hashtable used to implement the set. If the followers for two different hashtables yield a different number of full slots, iteration will fail with a runtime error.

Code from @cassella

use Set;

var s1, s2: set(int);

for i in 1..10 { s1.add(i); s2.add(i+10); }

forall (i,j) in zip(s1, s2) do writeln(i, " ", j);

writeln("all done");

---

Here is a potential solution proposed by @cassella in #15772:

https://github.com/chapel-lang/chapel/pull/15772/files#discussion_r434996280

The leader/follower don't seem right to me. They'll work with each other, but won't play well with other leaders/followers, IIUC.

Given say a set mySet with _htb.tableSize 53 and _htb.tableNumFilledSlots 25 (say) and one task, the leader will yield 0..52, and the follower will follow 0..52 and yield 25 things.

But if paired with a zip(0..52, mySet), the range leader will yield 0..52 (ok), but the range follower will yield 0..52 whereas the set follower will yield only 25 elements. Or zip(0..24, mySet), the range leader will yield 0..24, and the range follower will yield 0..24, but the set follower will yield however many elements are set in the first 25 slots of the hash table.

If you turn the zip() around, things work out poorly the other way around too.

I'd think the leader has to yield 0..#htb.numFilledSlots, and the follower following (a..#c) unfortunately has to count a filled slots in and then yield the next c.

(I'd also think this iteration is something the hash table should implement.)

Though maybe I'm missing something. I can't figure out how the current DefaultAssociativeDom (using the same hashtable module) can be zipped with anything other than not only a DefaultAssociativeDom, but a domain with a hash table that has precisely the same slots filled. (And indeed, forall (i,j) in zip(D,r) (and vice versa) where D is a domain(int) fails to compile (and fails to compile differently). So maybe sets don't need to be zippable with anything other than sets?

[bradcray]

Is this bug with respect to the way set was implemented prior to #15772, or after, or both?

Historically, I thought that the leader-follower iterators for associative were hardcoded to only work if all the things being zippered involved the same domain (and printed an error otherwise). If that's not the case anymore, I'm not sure whether we removed that check incorrectly or whether I'm completely misremembering / getting mixed up with sparse or something else.

[dlongnecke-cray]

I'm not sure if it was prior or not, @cassella suggested in an edit that this bug seemed to occur prior as well (? correct if wrong). It's easy enough to go test in a bit.

[dlongnecke-cray]

(As for why I have no frame-of-reference, I guess the test for set didn't have a zip-forall...)
🤦

[cassella]

@bradcray Yes, you're right -- prior to #15772, the set leader / follower just dispatched to the associative domain _dom's leader and follower, and had the behavior you recall. (Though the restriction isn't literally "the same domain", but "the domains have identical sets of indices".) After that change, a set no longer has an underlying _dom, and instead has its own leader / follower.

So I guess it's not new that sets with different members can't be zippered. Though I guess it is new that a set can't be zippered with an associative domain whose indices are exactly the set's elements. (I haven't tested that.)

[bradcray]

I'm giving this a bump in priority because it came up in a user gitter issue today.

[bradcray]

Here's another case a user submitted on gitter that didn't work as expected:

use Set;

var LocalSet= new set(int,parSafe = true);
LocalSet.add(1);
LocalSet.add(2);
LocalSet.add(3);
LocalSet.add(4);
LocalSet.add(5);

var A : [0..4] int;
writeln(A.size, LocalSet.size);
forall (a,b) in zip(A,LocalSet) {
    a=b;
    writeln(b);
}

And a less-complete pattern:

var LocalSet= new set(int,parSafe = true);
forall (a,b) in zip (A,LocalSet) {
  a=b;
}
// In the above, the value of b is not the element of LocalSet
// When I change the set to an array, it works
forall (a,b) in zip (A,LocalSet.toArray()) {
  a=b;
}