sdsl-lite
sdsl-lite copied to clipboard
simongog
thread safety
I'm learning through trial and error that not all classes in sdsl-lite are thread safe (for instance). Is there documentation about what features of sdsl-lite are thread safe? I have an application that relies on read-only thread-safe succinct data structures.
csa_sada is (as far as I remember) the only class which is not thread-safe in the read-only scenario, since it stores some decoded integers in a cache. We will definitely change this in the very near future.
For a quick fix, you would have to replace the buffer m_psi_buf by a local variable in the rank_bwt function: https://github.com/simongog/sdsl-lite/blob/master/include/sdsl/csa_sada.hpp#L330
I'm having thread-safety problems that superficially (in gdb) appear to be related to a wt_int<>. If I run a select operation on the wavelet tree in multiple threads I get:
sdsl-lite/install/include/sdsl/select_support_mcl.hpp:355: sdsl::select_support::size_type sdsl::select_support_mcl<t_bit_pattern, t_pattern_len>::select(sdsl::select_support::size_type) const [with unsigned char t_b = 0u; unsigned char t_pat_len = 1u; sdsl::select_support::size_type = long unsigned int]: Assertion `i > 0 and i <= m_arg_cnt' failed.
It doesn't seem like this could this be related to csa_sada, so I'm confused. It could be something in my application, but I haven't yet found anything and wanted to confirm it's not a limitation of sdsl-lite.
I can avoid this error by placing a mutex lock on the code that calls select on the wt.
Sorry, you are right; select on wt_int and wm_int are also not thread safe (a grep mutable include/sdsl/*.hpp ensured that).
Here the two variables m_path_off and m_path_rank_off should be made local to the select procedure. Thanks for pointing this out!
Am I right in assuming that putting things local to the select procedure would be a problem for larger alphabets? I'm wondering if it's worth working around this by establishing a select support per thread.
No, the size of the vector is log(alphabet size). So it should be not a problem ;) A really efficient solution is to implement a version of select which gets this additional memory from the thread.
I've run back into thread safety problems, presumably related to caching in select. Is there a way to configure sdsl-lite to not use caching?
Hi Erik,
could you please open a pull request with your changes to wm_int and wt_int? Thanks!
Simon
ps: We have a thread-safe redesign of the other non-thread safe part (csa_sada) in another branch, which will be merged in a few weeks. @mpetri : @ekg is referring to the select on pointerless wavelet trees
@simongog have you pulled in the thread safe branch of csa_sada?
I'm re-making the appropriate changes for wm_int and wt_int.
The referenced pull request includes roughly the same change that I had made before. Are there other aspects of the library which are still not thread safe?
@ekg, thanks for the pull request. The branch which makes csa_sada thread safe is not yet merged. We did a major redesign of csa_sada and will it merge in the next weeks. (The redesigned version lives in the hyb_sd_vector_slow branch)
Do you need csa_sada in your project?
@simongog thanks for merging the pull request so quickly!
This fix lets me remove the lock on the one non-threadsafe part of the API that I'm targeting.
I don't need csa_sada, but I totally support making sdsl-lite thread safe for non-destructive operations on its data structures.
Can you guys provide an update on the status of csa_sada's thread safety? I've been playing with it lately and the data structure seems to be locked when multiple threads are accessing it.
Did more investigation and turns out something else was the source of problem. My bad. Please delete this if necessary. Thanks.