I have an idea for a parallel Dict implementation without using those llvm-mutex-lock-stuff. I believe, reading from a Dict can be done in parallel without locking. Only write operations need locks.
The idea is to use additional FIFOs. The Dict is splitted into n subdicts. There are n dict-write-threads handling one subdict per thread. Each subdict handles its own key range. Reading the Dict means, at first
subdict_list[hash(key)%n]. And second reading the selected subdict. There is nothing new here. The write operations need locking the dict, because they can happen on the same dict with a known probability.
The new idea is to add one FIFO system per thread. Writing to Dict does only write to the individual FIFO system. The n worker threads look at the m FIFO systems. If the appropriate key is there, the worker thread take the key-value-pair and transfers its own subdict.
One FIFO system consists of n FIFOs. So there are n-by-m FIFOs. Each worker thread has one corresponding FIFO per program thread.
There is exactly one thread writing to one FIFO or one subdict. No locking is needed. Yes, reading the Dict may give an old value, if it is not already transferedfrom the FIFO to the subdict, but parallel writing should be fast.
I don’t know if what you’re thinking would work, but will +1 this as something I personally would find useful. Any thread safe implementation that could afford some concurrence to dict reads/writes would help a lot with some of my work. I’ve looked for something like this in the past and found academic papers on this topic (although I don’t remember much). Seems probably like a well trodden topic if you search around, since there are lots of hash table heavy algorithms that would benefit from this kind of thing (noSQL databases for instance). If you make a numba-ready implementation do share.
Now, we need to find out, if there are remaining problems, maybe FiFo overflow, that needs blocking write. We also need the read operation, which is trivial and native interfacing, that we can use it like a normal numba dict.
There is an important issue: Some items are missing in the target dicts. This maybe due to rescheduling the of the operations in parallel context, but I don’t know exactly.
Now, I made an object based version. The parallel dictionary object is represented by a state tuple. You can access it by the 4 par_dict_() member function defined here:
