I wrote a grep clone recently. It does a recursive search of a string query through all files of a specified directory. The core of program is the function shown below.
/** Do recursive search of query string in files under the given directory. */
void Search::searchFiles()
{
std::vector<std::future<void>> futures;
auto files = fs::recursive_directory_iterator(_directory);
for (auto& file : files) {
if (!fs::is_directory(file)) {
futures.emplace_back(std::async(&Search::searchFile, this, file));
}
}
for (auto & ftr : futures) ftr.wait();
}
I create many futures, but I could have used std::thread. For instance, in the code snippet below searchFiles uses std::thread instead.
void Search::searchFiles()
{
std::vector<std::thread> threads;
auto files = fs::recursive_directory_iterator(_directory);
for (auto& file : files) {
if (!fs::is_directory(file)) {
threads.emplace_back(&Search::searchFile, this, file);
}
}
for (auto & th : threads) th.join();
}
Is one or the other implementation better? Performance is one aspect of my question. I am interesting to learn about trade-offs between task-based and thread-based parallelism.
Additionally, how might one implement searchFiles with iterators? The idea being a fixed number of threads would be created, and each searchFile instance would increment the file iterator if there were more files to get. Below is sketch of an idea I had.
void Search::searchFile(FileIterator it)
{
while(true) {
// get next file from iterator
std::unique_lock<std::mutex> ulock(_mutex);
if (it == it.end()) break;
auto file = *it;
++it;
ulock.unlock();
// open file and loop through lines.
std::ifstream filestream(file);
...
}
void Search::searchFiles()
{
std::vector<std::thread> threads;
auto fileIterator = fs::recursive_directory_iterator(_directory);
// create only 10 threads
for (int idx = 0; idx < 10; idx++) {
if (!fs::is_directory(file)) {
threads.emplace_back(&Search::searchFile, this, fileIterator);
}
}
for (auto & th : threads) th.join();
}
KPI
Is one or the other implementation better?
You didn’t tell us your key performance indicator, your metric for “better”,
leaving both of them equally good absent comparison criteria.
Suppose that on a 16-core machine we take “elapsed time” as such a criterion.
Then this submission would be about performance,
yet it includes no performance measurements.
The OP can record such timings on his target host of interest; we cannot.
stragglers
Some files are short, while some are long.
This information is available up front via the POSIX stat() call.
Longer files will tend to imply longer elapsed times during a benchmark.
The OP code schedules files in arbitrary order,
with a decent chance of a long file appearing near the end.
We call such a matching task a “straggler”,
as it will keep a core busy after many other cores have gone idle.
On an N-core machine this code should immediately schedule N-1 tasks,
then identify all the input file sizes and sort on that.
Then execute the remaining tasks in descending size order.
That guarantees that toward the end of a run we will be assigning
short duration tasks, so all cores will tend to go idle at around the same time.
1
Use a thread pool and a thread-safe queue
As J_H already mentioned, you should start by creating a thread pool with around N-1 new threads on a machine with N cores. The main thread can then scan the directories, and add files to a thread-safe queue. The other threads can pick items from the queue to work on.
Adding iterators to the queue might be unsafe, unless you can guarantee that the iterators will remain valid until all files have been processed. Instead you could consider storing filenames in the queue.
No need to explicitly wait for futures
The destructor of a std::future will already call wait() for you, so you don’t have to do this explicitly at the end of searchFiles().
Note that if you would use std::jthread instead of std::thread, you also don’t need to explicitly join() anymore.