-
Notifications
You must be signed in to change notification settings - Fork 496
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
How to process very big file in parallel and write results in correct order? (I want FuturesOrdered!) #1070
Comments
It seems I know how to solve this with rayon. I will possibly open pull request today or tomorrow |
I think it would be much easier if you used positioned I/O, i.e. just iterate over |
(Actually, if the file is really large, you might even consider using |
Okay, so I wrote my solution here #1071 and I will publish it to crates.io in some point of future. I'm closing this issue |
Here is my tasks:
(My OS is Linux.)
(In fact my actual problem is this: borgbackup/borg#7674 (comment) . See there sequential Rust solution.)
It seems rayon doesn't support these cases directly. This is how I managed to do the first (big-to-small) task:
Unfortunately, I see multiple problems here:
par_bridge
will not store too many items in memory. @cuviper gave me such guarantee here: Does rayon have guarantee that .par_bridge().map().collect() will not store too many "Item"s in mem? #1068 (comment) , but it is limited to current version, so I have to make sure to never upgrade rayon, unless I checked that guarantee still holds. This is ugly. (Okay, it seems that current decision is to stick to this guarantee, this is good.)par_bridge().map(...).collect()
doesn't preserve order. (This is my interpretation of phrase "The resulting iterator is not guaranteed to keep the order of the original iterator" in https://docs.rs/rayon/1.7.0/rayon/iter/trait.ParallelBridge.html .) So I have to do that
sort_by_key
trick. The code seems error-prone. What if I forget to callsort_by_key
?Okay, so I decided to stick with this solution. If you know better, please, let me know.
Now to small-to-big task. I spend a lot of time reading rayon documentation and still it seems that this is not possible to solve this problem using rayon! But it seems the problem can be solved using tokio and
futures::stream::FuturesOrdered
( https://docs.rs/futures/0.3.28/futures/stream/struct.FuturesOrdered.html ). FuturesOrdered by itself runs everything in single thread, so it seems I should also usetokio::task::spawn_blocking
( https://docs.rs/tokio/1.29.1/tokio/task/fn.spawn_blocking.html ). I think the code should look like so (not tested):But my problem is CPU-bounded, not I/O bounded! And everyone says that we should use threads and rayon for CPU-bounded tasks and async for I/O-bounded tasks. So, it seems everyone lies. It seems I should use async, despite my problem is CPU-bounded.
How we got here? How it is became possible that rayon, which designed for CPU-bounded problems, perform on them worse than async programming, which has whole book on how bad it is ( https://rust-lang.github.io/wg-async/vision/submitted_stories/status_quo.html )?
It seems that FuturesOrdered will go for big-to-small task, too.
Another possible solution for small-to-big task is so: mmap output file to memory, then write to it using rayon and my own
collect_into_vec
-like function ( https://docs.rs/rayon/1.7.0/rayon/iter/trait.IndexedParallelIterator.html#method.collect_into_vec ). (I cannot usecollect_into_vec
directly, because I want to collect parallel iterator ofVec<u8>
into single&mut [u8]
, i. e. I don't need merelycollect_into_vec
, I needflatten_and_collect_into_vec
, or, more precisely,flatten_and_collect_into_mut_slice
.)Such solution will be idiomatic rayon code. Unfortunately, it will move all hard work to OS. It will generate too much pressure for page cache. And I know that this is bad, and that for performance we should not put too much information to page cache (see borgbackup/borg#7674 (comment) ). So I think FuturesOrdered solution will be better.
Conclusions/questions:
The text was updated successfully, but these errors were encountered: