WaveletTree CPU usage #55
Description
WaveletTree.rangeQuery regularly uses excessive CPU time (10+ cores used when calling with -threads 1), I believe due to JVM overhead in handling the recursion. Is it possible to rewrite this iteratively?
Metadata
Metadata
Assignees
Type
Projects
Milestone
Relationships
Development
No branches or pull requests
Participants
Activity
mvaudel commentedon Jan 18, 2022
Hi and thanks for narrowing down the issue this specifically.
We are currently refactoring another section of the code and will look into this issue as soon as we get some bandwidth. I will get back to you as soon as I have looked into it. In the meantime, PRs are most welcome :-)
heckendorfc commentedon Jan 19, 2022
I tried rewriting rangeQueryOneValue as an iterative algorithm as a proof of concept since it was already tail call, but it doesn't seem to make much difference on the CPU usage. Maybe the problem is more involved and we just have to live with it.