search

iu-parfunc / adaptive-data

0 stars 0 forks source link

For later on: either better concurrent bag or get rid of Pure/Scalable distinction. #5

Open rrnewton opened 9 years ago

rrnewton commented 9 years ago

Here's the thing, if we had a best-in-class concurrent bag, then the pure version and the scalable version would be very very different in terms of heap representation.

But right now, our relatively simple "scalable" bag is just P copies of the pure bag! As long as that is the case it is not really necessary to have a separate Pure/Scalable copy. (This strategy would be more compelling in the Data.Map vs concurrent skiplist case... if we can fix up our concurrent-skiplist.)

With our simplified bag we could avoid going all the way back to the Pure representation and instead just use the first slot of the array as the only list. (Or we could use the other slots only as needed based on contention. I'm sure there's an algorithm for this somewhere in the literature. The other slots serve as an elimination structure for the first slot.)

There's a large design space here. Also, I think there are some opportunities to use simple ring-buffer queues in the concurrent bag setting (which, with a single producer thread and single consumer, don't need an atomic operation per add/remove at all).

DreamLinuxer commented 9 years ago

Yes, I really think we should get a better ScalableBag. One heuristic I can think of is that we can decide whether to increase or reduce the number of copies by the size of the bag.

And regarding the map, I think maybe we can start from hashtable?

rrnewton commented 9 years ago

Yeah, definitely for the sequential one we should use the HAMT in hashmap package. For concurrent hash table... well we could do a lock-striped version of the gregory collins hash table package... or try to fix our concurrent skiplist.