3 ms·

It's a shame the parallel recursive file size sum example reads all of the file and directory names into memory first, and then iterates over them in parallel a

It's a shame the parallel recursive file size sum example reads all of the file and directory names into memory first, and then iterates over them in parallel after. A clean concise version of the same example, in a stream-like but still parallelized way, is not obvious to me at first glance (although I don't touch C++ often, perhaps someone here knows of a good way?)

saagarjha 8y ago
That’s because the directory iterator isn’t random access, and I don’t see a way to get the functionality you want in any language, not just C++.
- stochastic_monk 8y ago
  To do that, you’d have to buffer records from the file and dispatch threads to perform your task. Lazily loading can be preferable for large workloads, but it requires fine-grained threading. (And probably dedicated reading/writing threads and/or locks.) That’s a lot more work than this, though.
burntsushi 8y ago
Indeed, I've actually written such a thing (although in Rust, not C++), I'm still looking for a clean concise version. :-) Here's the public API of mine[1], which is pretty blah, because it takes a closure (per-thread initialization) that must return a closure (executed on each entry in the tree). The most interesting part of the implementation is here[2], along with a suspicious termination argument. Outside of that, ucg (written in C++) also has a recursive directory iterator.[3] I also know of two written in Go, one in sift[4] and another in the platinum searcher[5]. The ones in Go seem considerably simpler as they fall back to goroutines. I haven't carefully benchmarked all of these, but if memory serves, they're all faster than the single threaded variants. In my experience, the hardest part about implementing this is coming up with a solid termination argument because your consumers are also your producers. (I documented this a bit in `get_work` in my Rust code.) [1] - https://docs.rs/ignore/0.4.2/ignore/struct.WalkParallel.html https://docs.rs/ignore/0.4.2/ignore/struct.WalkParallel.html [2] - https://github.com/BurntSushi/ripgrep/blob/b38b101c77003fb94aaaa8084fcb93b6862586eb/ignore/src/walk.rs#L940-L1378 https://github.com/BurntSushi/ripgrep/blob/b38b101c77003fb94... [3] - https://github.com/gvansickle/ucg/blob/master/src/libext/DirTree.cpp https://github.com/gvansickle/ucg/blob/master/src/libext/Dir... [4] - https://github.com/svent/sift/blob/2ca94717ef0bbf43068f217c8a0dfb216df52225/sift.go#L159-L376 https://github.com/svent/sift/blob/2ca94717ef0bbf43068f217c8... [5] - https://github.com/monochromegane/the_platinum_searcher/blob/master/walk.go https://github.com/monochromegane/the_platinum_searcher/blob...
- jjnoakes 8y ago
  Yeah, I've written such a thing many times as well, in languages like Go which make it easy and languages like C which make it not-as-easy and a few in between. I was more curious if there was a cleaner C++ way of doing it with all of the recent or pending languages changes.
jstimpfle 8y ago
Anyway, why would anybody standardize this at all? Too many ways to do it and each one sucks because of race conditions. Any program that needs such a feature should just write the 10-20 lines version that it deems best. There will hardly be any project that needs to know the "recursive file size" that is also too small to be able to afford this extra work. Ok, but maybe I'm missing something here: Why parallel? Is there any benefit?
AtlasBarfed 8y ago
Yeah, it's kind of annoying that most parallel libs only show single-depth/degree examples. I get that's good for a "five minute intro", but usually parallel processing involves dynamic task production (descending the filesystem tree nodes) in addition to the parallel processing of the tasks themselves. ... in addition to the tasks behaving like streams.

saagarjha 8y ago

That’s because the directory iterator isn’t random access, and I don’t see a way to get the functionality you want in any language, not just C++.

stochastic_monk 8y ago
To do that, you’d have to buffer records from the file and dispatch threads to perform your task. Lazily loading can be preferable for large workloads, but it requires fine-grained threading. (And probably dedicated reading/writing threads and/or locks.) That’s a lot more work than this, though.

burntsushi 8y ago

Indeed, I've actually written such a thing (although in Rust, not C++), I'm still looking for a clean concise version. :-) Here's the public API of mine[1], which is pretty blah, because it takes a closure (per-thread initialization) that must return a closure (executed on each entry in the tree). The most interesting part of the implementation is here[2], along with a suspicious termination argument. Outside of that, ucg (written in C++) also has a recursive directory iterator.[3] I also know of two written in Go, one in sift[4] and another in the platinum searcher[5]. The ones in Go seem considerably simpler as they fall back to goroutines. I haven't carefully benchmarked all of these, but if memory serves, they're all faster than the single threaded variants. In my experience, the hardest part about implementing this is coming up with a solid termination argument because your consumers are also your producers. (I documented this a bit in `get_work` in my Rust code.) [1] - https://docs.rs/ignore/0.4.2/ignore/struct.WalkParallel.html https://docs.rs/ignore/0.4.2/ignore/struct.WalkParallel.html [2] - https://github.com/BurntSushi/ripgrep/blob/b38b101c77003fb94aaaa8084fcb93b6862586eb/ignore/src/walk.rs#L940-L1378 https://github.com/BurntSushi/ripgrep/blob/b38b101c77003fb94... [3] - https://github.com/gvansickle/ucg/blob/master/src/libext/DirTree.cpp https://github.com/gvansickle/ucg/blob/master/src/libext/Dir... [4] - https://github.com/svent/sift/blob/2ca94717ef0bbf43068f217c8a0dfb216df52225/sift.go#L159-L376 https://github.com/svent/sift/blob/2ca94717ef0bbf43068f217c8... [5] - https://github.com/monochromegane/the_platinum_searcher/blob/master/walk.go https://github.com/monochromegane/the_platinum_searcher/blob...

jjnoakes 8y ago
Yeah, I've written such a thing many times as well, in languages like Go which make it easy and languages like C which make it not-as-easy and a few in between. I was more curious if there was a cleaner C++ way of doing it with all of the recent or pending languages changes.

jstimpfle 8y ago

Anyway, why would anybody standardize this at all? Too many ways to do it and each one sucks because of race conditions. Any program that needs such a feature should just write the 10-20 lines version that it deems best. There will hardly be any project that needs to know the "recursive file size" that is also too small to be able to afford this extra work. Ok, but maybe I'm missing something here: Why parallel? Is there any benefit?

AtlasBarfed 8y ago

Yeah, it's kind of annoying that most parallel libs only show single-depth/degree examples. I get that's good for a "five minute intro", but usually parallel processing involves dynamic task production (descending the filesystem tree nodes) in addition to the parallel processing of the tasks themselves. ... in addition to the tasks behaving like streams.