odenas / indexed_ms Goto Github PK

One easy optimization that we could is to not test for repmaximality when we do parent operation from already repmaximal node, since the new node is certainly repmaximal.

As of March 31, fd_ms runs much slower due to the removal of operations on the bwt (like the backward step). This was motivated by the equivalence of (v.i, v.j) with the interval of the word of locus v.

Revert the code to use the intervals and bsteps.

Is there a way to make the lazy_wl completely transparent, in the sense that you don't need to call the followup explicitly.

Why is the lazy mode not supported, while it is advertised as a parameter?

Running matching_stats_parallel.x -lazy_wl 1 results in the error message

ERROR from buiold_runs: lazy mode not supported

Try with mut_xxx strings where the mutation period is potentially larger than the block

I also think we could report the time taken by normal parent operation vs. lazy parent when it comes after a Weiner link (the latter should be slower)

fixed size chunks defined over the bit-vector

https://github.com/bingmann/malloc_count
used in papers which use parallelism:
https://users.dcc.uchile.cl/~jfuentess/thesis/files/sea2015.pdf
https://arxiv.org/pdf/1702.07578.pdf

Split the text into d equal-length pieces, do the matching statistics on each piece independently. Then, we can compute the missing matching statistics which are the ones that cross the boundaries between pieces.

Restructure the snakefile so that it runs max operations,

Benchmark max operations

rle_partial_max_vector constructor signature rle_partial_max_vector(const string&) and rle_partial_max_vector(const string&, counter_t&)

rle_partial_max_vector.noindex(int from, int to, algo) which calls either trivial or djamal

Current rank tests are very superficial and not unified.

Create two types of tests:

• sandbox: run each function a number of times and measure the exec time
• full: run the full algorithm on different input types and measure time

The double_rank comes in a vanilla flavor and an extra trick which fails early on the WT search for the symbol.

Perform sandbox tests on nodes that

• span small or big intervals
• have a WL for only some characters of the alphabet. Call the rank procedure on all characters

Perform the full test on all inputs available (you can run this in parallel).

csa.double_rank() was not calling wt.double_rank, I made the change, but the code is failing. inspect!

add tests with large blocks

for a n-threaded run, n ms vectors are allocated. See if you can reduce this space requirement

What kind of restriction do you have for the input text and the pattern? For arbitrary files, I get the following error:

bin/matching_stats_parallel.x -s_path makefile -t_path readme.md                                                                                                            [master] ?? [ 134 ]
building RUNS ... 
 * loadding index string  from makefile 
 * building the CST of length 10 DONE (0 seconds, 11 leaves)
 ** filling 1 slices with : 1 threads ...
 *** [0 .. 1149)
matching_stats_parallel.x: src/fd_ms/p_runs_vector.hpp:354: fdms::p_runs_vector<cst_t>::p_runs_state fdms::p_runs_vector<cst_t>::fill_slice(fdms::InputSpec, const cst_t&, fdms::p_runs_vector<cst_t>::size_type) [with cst_t = fdms::StreeOhleb<>; fdms::p_runs_vector<cst_t>::size_type = long unsigned int]: Assertion `!st.is_root(u)' failed.

Having users setup a virtual env for the software is onerous. Remove

scan as you do in the trivial method
same for other scans in this method

Fixes

• try lazy vs non-lazy experiments with an even bigger tree
• often the context requires a speedup in terms of the whole algorithm vs just the operation, might be better to report both

It takes too long to compute the maxrep vector.

• Allow for the script to load a previously computed one (just as with the -load_cst flag)
• Create a script that dumps a maxrep vector.

why not just if ((ms_idx + 1) % block_size == 0) ?

avoid division and write as a for loop

ridx is not needed and should be de-allocated after rmq construction
int_from should be a const

The code can now leverage a maxrep bitvector indicating the nodes that correspond to maximal repeats.

This information can be used to speedup the WL operations.

Experiment in sandbox to test the effect of the fail mechanism, double rank and the maxrep vector.

Update range_query_profile.cpp

The current optimization is trivial, can we do it at the rank data structure level?

implement a correct method (e.g, using python/numpy) and integrate into own folder with smake

rename the existing test folder for sum

this key is not consistent

matchin_stats_parallel.cpp should be used instead (with nthreads=1)

construct_im() will write input to a file and call construct() to build the data structure. However, you have already loaded the input (you just passed it to construct_im), which means it is being loaded twice.