Proof of Concept : Concurrent exacthash

[chris-ha458]

I built a proof of concept concurrent exact hash using shared_memory and Manager() from multiprocessing

Discussion

• It is not faster. I think it will only be relevant when the datasets do not fit in memory, but considering how mmaped huggingface datasets work, that threshold might be much larger. Also, the core computation IS linear. Even in the ideal case, the membership change conceptually and practically becomes serial. The primitives merely manage that without (or while minimizing) races. No amount of concurrent algorithms can change that fundamental fact.
• There seems to be a race condition. Most of the time, the results are the same as the serial version, but sometimes there are false negatives (a duplicate is not removed). I think it is a race since It's hard to replicate and changes from run to run. I cannot see where it is, but it seems that atleast within each shard processing there seems to be a case where a race in the duplicate checking causes a false negative. My assumption is that the dict used as a replacement for a set is not updated properly during between the processes even though it is backed by a shared buffer. This also changes according the batch sizes so I would have to assume. The lower the batch size the less likely that the final result diverges from the serial version which leads me to believe it is related to races within a batch.
• I hope there is some footgun I'm missing that would be easy to fix, otherwise, this might be hard to address with the primitives and language limitation Python represents.
• I think it is premature to formulate as a PR as this point, but i would also love feedback especially relating to other attempts at concurrency so I am documenting it here.

[ChenghaoMou]

if h in hash_dict:
    flags[idx] = True
else:
    hash_dict[h] = True

The shared object hash_dict is being written/updated while it is being read in another process. This should explain the inconsistency you saw.

For example, if doc_a and doc_b are the same, and hash_dict does not contain this specific fingerprint before this batch, they could end up updating hash_dict twice and no flag being set (they both enter the else branch simultaneously);

It might need a lock when accessing hash_dict.

[chris-ha458]

I assumed that the shared_memory and Manager() class would internally provide lock or atomic mechanisms.
Upon careful rereading of the references
https://docs.python.org/3/library/multiprocessing.html#multiprocessing.managers.SyncManager
https://docs.python.org/3/library/multiprocessing.shared_memory.html

I think they might not. If the do provide locking methods, they are not documented.
Unfortunately however, it could be that these objects merely allow to "share" the objects and do not provide any threadsafe read/write mechanisms AT ALL.
This would be the worse case (and also the likely one) and I'd have to re-evaluate all object choices and locking mechanisms.

Considering how python is with concurrency this is non trivial.
For example, where to put the lock can be a very difficult consideration with numerous performance impacts.

# lock here?
if h in hash_dict:
    # lock here?
    flags[idx] = True
    # release here or not?
else:
    # lock here?
    hash_dict[h] = True
    # release here or not?
#release here?

I implemented this when I stumbled upon how np.ndarray can be initialized from a shared_memory buffer, but it does not seem to be the magic bullet I was looking for, if it exists at all.

[ChenghaoMou]

I think the SyncManager object itself is thread-safe. But the if-else code is not (both entering the else branch but still updating the hash_dict sequentially. Does that make sense?