Explanation about "stateless"

[jorenretel]

I am looking to switch from ncls to ruranges. I believe when you say it is fast. But I am a little bit confused about the "Stateless: plain functions, no classes." aspect. When I use NCLS, some work is done at the moment I create the NCLS object, like building an index. When I repeatedly search against that same index, that work supposedly does not have to be done again.

It seems like ruranges is starting from scratch every time though. Could you maybe explain how this works? I think a comment on this would help a lot of people that have to search against the same set of intervals very many times.

[endrebak]

ruranges merely sorts the data with a linear time algorithm which takes no time at all and then iterates through the intervals to find overlaps.

I should benchmark how much time it takes to sort.

One way to work around this if you are worried about the speed is to have one collection of intervals which is sorted and then be allowed to pass a sorted=True argument to ruranges which does not resort the left collection of intervals.

[endrebak]

Benchmark:

import pyranges as pr
from ncls import NCLS
from time import time


num_intervals = int(1e7)
chr1_size = 249 * int(10e6)
gr = pr.random(num_intervals, chromsizes={1: chr1_size})
gr2 = pr.random(num_intervals, chromsizes={1: chr1_size})

gr.overlap(gr2)

start = time()
n = NCLS(gr.Start.to_numpy(), gr.End.to_numpy(), gr.index.to_numpy())
print("Took ", time() - start, "building the NCLS")

start = time()
res = n.all_overlaps_both(gr2.Start.to_numpy(), gr2.End.to_numpy(), gr2.index.to_numpy())
print("Took ", time() - start, "to find the overlaps")

Results in:

Time to sort: 638.18ms
Time to find overlaps: 288.80ms
Took  1.426201581954956 building the NCLS
Took  3.094311237335205 to find the overlaps

The first two print statements are from within rust ruranges. So using ruranges takes less than a second while using NCLS takes 4.5. Even if you do not have to build the NCLS it will still take more time (3 seconds vs 1).

And ruranges has other advantages like being able to take a list of chromosomes while with NCLS you need to build a different datastructure for each one which adds additional overhead in Python.

[endrebak]

@marco-mariotti Perhaps the benchmarks are of interest :) You might be asked this question. It is true that ruranges relies on no datastructure so we resort the data each time but it still is very fast.

[marco-mariotti]

Indeed, it seems that some users may benefit from some ruranges methods having a sorted=True keyword. It may also benefit some PyRanges native methods: we would need to re-read all the code to see if any duplicate sorting is performed. It may further push performance.

I think this is in a way related to this issue pyranges/pyranges1#104

Let's see and plan our next 'batch' of development soon (Endre, let's talk by email), which may include these two items, and a couple more open issue in pyranges

[jorenretel]

Hi, thanks for looking into this and running those benchmarks. Now I understand what is going on. And yes, I think my use case would benefit from not having to do that sort every time. In my case "gr" would be large (and "static"), but gr2 would be very small. I would do that query of gr2 against gr very many times though. So, my benchmark looks more like this:

num_intervals = int(1e7)
num_intervals_query = 32
chr1_size = 249 * int(10e6)
gr = pr.random(num_intervals, chromsizes={1: chr1_size})
gr2 = pr.random(num_intervals_query, chromsizes={1: chr1_size})

gr.overlap(gr2)

index = np.arange(num_intervals)
query_index = np.arange(num_intervals_query)

start = time()
n = NCLS(gr.Start.to_numpy(), gr.End.to_numpy(), index)
print("Took ", time() - start, "building the NCLS (only once)")

start = time()
res = n.all_overlaps_both(gr2.Start.to_numpy(), gr2.End.to_numpy(), query_index)
print("Took ", time() - start, "to find the overlaps (very many times)")

result:

Took  1.1577999591827393 building the NCLS (only once)
Took  0.0007500648498535156 to find the overlaps (very many times)

I understand that I could just gather very many gr2's up front in a batch and then run them all at once, but since ncls allowed me to this "on the fly" with just a bit of overhead (and fast compared to everything that comes after I find the overlaps), this is how I was using it. So this sorted=True keyword would help me to replace ncls with ruranges without changing too much code.

[endrebak]

Thanks for the feedback. This will be trivial to fix for the case where you only have one chromosome in the data but might require some thinking for the case where you have multiple chromosomes in one dataset.

[endrebak]

I see this as high priority but it needs some mulling over so that I find a good forever solution:)

[jorenretel]

Sounds good. And thanks again. Good luck mulling...

[endrebak]

It is the chromosome handling that is going to take a bit of thinking. ruranges avoids using pandas and string handling in numpy (ruranges only dependency) is slow. So I would need to implement some string handling functions in rust myself.

[endrebak]

I've come to realize that the optimizations and algorithms that make ruranges perfect for pyranges make them hard to rewrite to support this use-case.

In the short term I think the best thing to do would be to rewrite the documentation to reflect that the NCLS is superior for the use-case above.

Long term I think that rewriting the NCLS in Rust would be good for this. I suppose the popularity of NCLS is partly due to it supporting the above use case. We can tell people to cite the new pyranges paper if they use the Rust version.

[jorenretel]

Thanks for the feedback. This will be trivial to fix for the case where you only have one chromosome in the data but might require some thinking for the case where you have multiple chromosomes in one dataset.

If this is still true though, I think including that would already help. For me it would be enough. I basically use a position system that spans the entire genome instead of individual chromosomes. Therefore, what you proposed would still work for me.

[endrebak]

The problem is that the algorithm I implemented requires merging the two datasets and resorting the resulting collection.

I think implementing the NCLS in Rust might be preferable. It might be that it is less cumbersome than it sounds. Perhaps I would just need to oversee the translation of the code from C to Rust. I have not been impressed with AI for novel or semi-difficult problems but who knows.

[endrebak]

Example use here: #19

The API is not stable. I'm trying to build and upload to PyPI: https://github.com/pyranges/ruranges/actions/runs/20307300842/job/58328199434

[jorenretel]

That was fast. The AI did actually help?

Edit: I understand now after looking at your other branch mentioned here (#19). That's the version that assumes sorted input, not a reimplementation of NCLS, right?

[endrebak]

AI is always of help in actually writing and getting the types right but it needs lots of overseeing when it comes to novel and difficult algorithms.

The thing we wrote there is an extremely straightforward algorithm. It is 15% faster than my current algorithm even if I have to sort the data first and it is simpler so I might make it the default.

Note that it should be just as fast with multiple chromosomes. You just need to ensure that each collection is sorted with the groups in the same order for it to work correctly.