Const method should be thread safe
yosupo06 opened this issue · 2 comments
By #107 , we add const to some methods of lazysegtree.
But it seems that const method should be thread safe.
Sorry for my careless PR...
It seems that one of the easiest ways to resolve this issue while maintaining const 's might be introducing std::mutex to lazy_segtree. I tried writing the simple draft version of thread safe lazy_segtree using mutex for consideration (In this implementation, the mutexes are declared as global variables. Declaring them as member variables of lazy_segtree fails the test of ACL, since copy constructor for mutex is prohibited).
Unfortunately, it seems that the huge execution time degradation occurs when Clang is used because of the overhead of mutex...
| Problem | Used methods | Plain lazy_segtree | Using mutex |
|---|---|---|---|
| AtCoder practice2-K | prod(), apply() |
GCC, 796 ms / Clang, 865 ms | GCC, 750 ms / Clang, 1842 ms |
There might be a more effective way that I do not came up with to resolve this issue. At present, it seems that reverting this repo to the previous version is worth consideration (if possilble).
OK, we decide to revert the change of lazysegtree, so segtree has const but lazysegtree doesn't have const. Though it is a breaking change, I hope it doesn't occur any heavy problems (because it is not merged into production branch yet).
TBH, I think there is no nice solution for introduce const into lazysegtree, at least we cannot accept std::mutex... (>99.9% code of competitive programming is in single thread and std::mutex is a simply obstacle...)