make wt_int and wm_int thread safe

[ekg]

This is accomplished by moving m_path_off and m_path_rank_off to the local context of select (see #263).

Now, grep mutable include/sdsl/*hpp yields only wt_pc.hpp, bp_support_sada, and csa_sada, all of which have shared caches that will not be thread safe without changes to the API.

[tb-robot]

Can one of the admins verify this patch?

[ekg]

I think it might make sense to revert my last push. Trying to understand what I'm seeing here once I try to integrate the changes into another application: https://travis-ci.org/ekg/xg/builds/78046876#L5603-L5645. This wasn't an issue with int_vector<64>.

Here's the text of the error in case it vanishes into travis history:

In file included from sdsl-lite/build/include/sdsl/wavelet_trees.hpp:37:0,
                 from xg.hpp:12,
                 from xg.cpp:1:
sdsl-lite/build/include/sdsl/wt_int.hpp: In instantiation of ‘sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::size_type sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::select(sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::size_type, sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::value_type) const [with t_bitvector = sdsl::int_vector<1u>; t_rank = sdsl::rank_support_v<1u, 1u>; t_select = sdsl::select_support_mcl<1u, 1u>; t_select_zero = sdsl::select_support_mcl<0u, 1u>; sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::size_type = long unsigned int; sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::value_type = long unsigned int]’:
xg.cpp:355:64:   required from here
sdsl-lite/build/include/sdsl/wt_int.hpp:431:60: error: no matching function for call to ‘std::array<long unsigned int, 65ul>::array(unsigned int)’
             std::array<uint64_t, 65> m_path_off(max_level+1);
                                                            ^
sdsl-lite/build/include/sdsl/wt_int.hpp:431:60: note: candidates are:
In file included from /usr/include/c++/4.9/tuple:39:0,
                 from /usr/include/c++/4.9/bits/stl_map.h:63,
                 from /usr/include/c++/4.9/map:61,
                 from xg.hpp:6,
                 from xg.cpp:1:
/usr/include/c++/4.9/array:81:12: note: std::array<long unsigned int, 65ul>::array()
     struct array
            ^
/usr/include/c++/4.9/array:81:12: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(const std::array<long unsigned int, 65ul>&)
/usr/include/c++/4.9/array:81:12: note:   no known conversion for argument 1 from ‘unsigned int’ to ‘const std::array<long unsigned int, 65ul>&’
/usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(std::array<long unsigned int, 65ul>&&)
/usr/include/c++/4.9/array:81:12: note:   no known conversion for argument 1 from ‘unsigned int’ to ‘std::array<long unsigned int, 65ul>&&’
In file included from sdsl-lite/build/include/sdsl/wavelet_trees.hpp:37:0,
                 from xg.hpp:12,
                 from xg.cpp:1:
sdsl-lite/build/include/sdsl/wt_int.hpp:432:65: error: no matching function for call to ‘std::array<long unsigned int, 65ul>::array(unsigned int)’
             std::array<uint64_t, 65> m_path_rank_off(max_level+1);
                                                                 ^
sdsl-lite/build/include/sdsl/wt_int.hpp:432:65: note: candidates are:
In file included from /usr/include/c++/4.9/tuple:39:0,
                 from /usr/include/c++/4.9/bits/stl_map.h:63,
                 from /usr/include/c++/4.9/map:61,
                 from xg.hpp:6,
                 from xg.cpp:1:
/usr/include/c++/4.9/array:81:12: note: std::array<long unsigned int, 65ul>::array()
     struct array
            ^
/usr/include/c++/4.9/array:81:12: note:   candidate expects 0 arguments, 1 provided
/usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(const std::array<long unsigned int, 65ul>&)
/usr/include/c++/4.9/array:81:12: note:   no known conversion for argument 1 from ‘unsigned int’ to ‘const std::array<long unsigned int, 65ul>&’
/usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(std::array<long unsigned int, 65ul>&&)
/usr/include/c++/4.9/array:81:12: note:   no known conversion for argument 1 from ‘unsigned int’ to ‘std::array<long unsigned int, 65ul>&&’

[simongog]

why are you passing an argument to the constructor of std::array? The 65 as second template argument is enough I guess ;)

2015-08-31 16:22 GMT+02:00 Erik Garrison [email protected]:

I think it might make sense to revert my last push. Trying to understand what I'm seeing here once I try to integrate the changes into another application: https://travis-ci.org/ekg/xg/builds/78046876#L5603-L5645. This wasn't an issue with int_vector<64>.

Here's the text of the error in case it vanishes into travis history:

In file included from sdsl-lite/build/include/sdsl/wavelet_trees.hpp:37:0, from xg.hpp:12, from xg.cpp:1: sdsl-lite/build/include/sdsl/wt_int.hpp: In instantiation of ‘sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::size_type sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::select(sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::size_type, sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::value_type) const [with t_bitvector = sdsl::int_vector<1u>; t_rank = sdsl::rank_support_v<1u, 1u>; t_select = sdsl::select_support_mcl<1u, 1u>; t_select_zero = sdsl::select_support_mcl<0u, 1u>; sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::size_type = long unsigned int; sdsl::wt_int<t_bitvector, t_rank, t_select, t_select_zero>::value_type = long unsigned int]’: xg.cpp:355:64: required from here sdsl-lite/build/include/sdsl/wt_int.hpp:431:60: error: no matching function for call to ‘std::array<long unsigned int, 65ul>::array(unsigned int)’ std::array<uint64_t, 65> m_path_off(max_level+1); ^ sdsl-lite/build/include/sdsl/wt_int.hpp:431:60: note: candidates are: In file included from /usr/include/c++/4.9/tuple:39:0, from /usr/include/c++/4.9/bits/stl_map.h:63, from /usr/include/c++/4.9/map:61, from xg.hpp:6, from xg.cpp:1: /usr/include/c++/4.9/array:81:12: note: std::array<long unsigned int, 65ul>::array() struct array ^ /usr/include/c++/4.9/array:81:12: note: candidate expects 0 arguments, 1 provided /usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(const std::array<long unsigned int, 65ul>&) /usr/include/c++/4.9/array:81:12: note: no known conversion for argument 1 from ‘unsigned int’ to ‘const std::array<long unsigned int, 65ul>&’ /usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(std::array<long unsigned int, 65ul>&&) /usr/include/c++/4.9/array:81:12: note: no known conversion for argument 1 from ‘unsigned int’ to ‘std::array<long unsigned int, 65ul>&&’ In file included from sdsl-lite/build/include/sdsl/wavelet_trees.hpp:37:0, from xg.hpp:12, from xg.cpp:1: sdsl-lite/build/include/sdsl/wt_int.hpp:432:65: error: no matching function for call to ‘std::array<long unsigned int, 65ul>::array(unsigned int)’ std::array<uint64_t, 65> m_path_rank_off(max_level+1); ^ sdsl-lite/build/include/sdsl/wt_int.hpp:432:65: note: candidates are: In file included from /usr/include/c++/4.9/tuple:39:0, from /usr/include/c++/4.9/bits/stl_map.h:63, from /usr/include/c++/4.9/map:61, from xg.hpp:6, from xg.cpp:1: /usr/include/c++/4.9/array:81:12: note: std::array<long unsigned int, 65ul>::array() struct array ^ /usr/include/c++/4.9/array:81:12: note: candidate expects 0 arguments, 1 provided /usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(const std::array<long unsigned int, 65ul>&) /usr/include/c++/4.9/array:81:12: note: no known conversion for argument 1 from ‘unsigned int’ to ‘const std::array<long unsigned int, 65ul>&’ /usr/include/c++/4.9/array:81:12: note: constexpr std::array<long unsigned int, 65ul>::array(std::array<long unsigned int, 65ul>&&) /usr/include/c++/4.9/array:81:12: note: no known conversion for argument 1 from ‘unsigned int’ to ‘std::array<long unsigned int, 65ul>&&’

— Reply to this email directly or view it on GitHub https://github.com/simongog/sdsl-lite/pull/264#issuecomment-136385034.

[ekg]

I'd like to pick this back up as it's continuing to cause issues for me.

Relative to the patch that I proposed, what changes would you require to make this acceptable?

I'm also interested in doing something similar for csa_sada.

[mpetri]

just making the buffer in csa_sada local would probably cause lots of allocations which will degrade performance? Have not benchmarked this though.

[ekg]

It seems it might hurt performance. That said, mutex locking isn't a great solution.

What might be sensible is to pass a thread-local buffer into the select.

[simongog]

Yes, a third argument which is a pointer to a thread-local buffer seems to be the good solution, since it is backward-compatible. If a nullptr is passed we could then just use the old mutable array to still get the same performance for single-threaded program ;)

[mpetri]

the buffer is also used in rank_bwt which is called from the suffix_array_helper classes which are called from count() and extract() etc. so it will be quite difficult to adjust all of these and remain backward-compatible.

[simongog]

Yes, it is used in those places, but since it is only called with the two arguments it will still work as expected in the single-threaded case. You are certainly right that more adjustments have to be made to make some methods of the CSA (like rank_bwt,count, and extract) work in a multithreaded environment, but I think this is not the point of Erik's request.

[mpetri]

well csa_sada::select_bwt() doesn't use the buffer at all so not sure what the problem is here?

[mpetri]

also, there is a assert(cc != 255); in there which probably has to removed as we now deal with integer alphabets.

[ekg]

How much does the caching help? Could I simply add an option to turn it off to all of the classes that use this kind of non-threadsafe feature?