Collections 2.0: Collections & Distributed Data Structures Overhaul

[LouisJenkinsCS]

This is a TODO list I'm planning to get around to relatively soon to overhaul both the Collections API as well as the data structures implemented under it (DistributedBag and DistributedDeque). While they pass the simple tests I have for ensuring data structure correctness, they definitely trigger some nasty compiler/runtime issues that I need to either formerly file bug reports for or to avoid/work around. As well some design changes are planned as well...

[Work in Progress] Bug Fixes

• [ ] Remove Reference Counting in favor of manual control of allocation/deallocation.
• [ ] Report or Fix issues with record forwarding triggering compiler bugs
  • [ ] Issue #8449
• [ ] Fine-tune and improve work stealing algorithm for DistributedBag
• [ ] Add configuration settings for DistributedBag
• [ ] Add random-access indexing support for DistributedDeque
• [ ] Add a variant for DistributedDeque that does not rely on network atomics
• [ ] Implement data-structure specific addBulk functions
• [ ] Add a unidirectional and bidirectional map
• [ ] Make use of exception handling instead of halting
• [ ] Add a way to sort the data structures
• [ ] Add a way to have a pseudo-contiguous view of the data structures

[mppf]

I'd add:

• [ ] Provide "Collections" APIs in a way that makes sense for users to use when their use case is not distributed. That might mean creating implementations that choose distributed / not distributed, making a separate single-locale one, or possibly just renaming the modules.

[nimitbhardwaj]

One more thing to add, as told by @LouisJenkinsCS adding the priority queue class, which may sometimes be handy

[LouisJenkinsCS]

@nimitbhardwaj

Can you describe what precisely you would want from the priority queue? The one personal constraint I have is that the data structure has to be parallel-safe (and optionally distributed). Hence it may take a while, but I want to know what kind of operations do you want supported?

As the data structure is sorted via some partial order operation, likely we'd need some function compare(eltType, eltType) : eltType. The fundamental add would insert it in an ordered/sorted way, and remove would take the largest item. What about iteration? Any other features you'd want?

[LouisJenkinsCS]

Speaking of which, I was thinking of a way to implement these data structures easier... QSBR PR #8182 would help immensely and I can see about implementing some STM to smooth this process along (man I sure can't wait until that gets accepted)

[nimitbhardwaj]

I thought of simple priority queue first, like a simple C++ implementation of priority queue, then multithreading could be added

[LouisJenkinsCS]

Sure I can hack one out for you in Chapel if you want, although I don't think it'd be accepted in a PR unless it was parallel-safe and scalable as a minimum. Then again maybe not since Chapel doesn't have any other data structure besides a List.

[LouisJenkinsCS]

Okay, I think I have an idea to satisfy both criteria. I'll let you know once I finish it.

[LouisJenkinsCS]

Okay got a bit side-tracked but here is a demo for the Priority Queue that implements CollectionImpl and makes use of the cool nifty utility methods it provides for free. You can run it here and see the syntax-highlighted source code here. Currently it only makes use of add and remove and the utility features addBulk and removeBulk, but other things like iteration or other specific methods can be added at will. I have other things I have to focus on now but I'll come back once I can find a way to make it parallel-safe.

Note:

A method like makePriorityQueue can be implemented using the 'Sort' module's heapSort algorithm to handle sorting it and setting it as the current array.

[e-kayrakli]

After #15081, .getSize() should probably be deprecated and turned into .size