How to search for a string in a large text file, using buffers and multithreading

Question

I want to find a string in a very large text file (containing tens of gigabytes of text). I need to use buffers and multithreading, and this is what I thought to do:

1. Create a loop reading chunk of the text using buffer at each iteration.
2. Split the chunk into the given number of threads.
3. Each thread will search the string in the part of the text it received.
4. If the string was found print its location, else read another chunk of the text file.

This is what I tried to do:

string[] lines = System.IO.File.ReadAllLines(@textfile);
int counter = lines.Length / nThreads;
int start = 0;
int end = counter;
(int,int)[] results = new (int, int)[nThreads];

results.ToList().ForEach(i => Console.WriteLine(i.ToString()));
for (int i = 0; i < nThreads; i++)
{
    Thread thread1 = new Thread(() => { results[i] = ThreadSearch
        .SubarraySearch(StringToSearch, Delta, lines, start, end); });
    // ThreadSearch - function that search the string in the array
    thread1.Start();
    thread1.Join();
}
// At the end I will go through the results array see if any
// of the threads found something

Now I have two problems at implementing this algorithm:

1. I don't now how to run all the threads at the same time and stop when result is found.
2. I only know how to read line by line using buffer and not a chunk from the text.

Constraints and invariants of the input data:

1. I don't know the exact size of the text file, only that it's too large to read at once, but I do know that the maximum buffer size of thread is 10k.
2. The size of string I'm searching is unknown - probably a word from the text file, it will contain only letters and digits, no spaces or new lines.

I'm new at C#, so any help will be great.

Answer 1

1. First you want to benchmark the file reading and the buffer processing in order to know if you're IO bound, memory bound or CPU bound. If you're IO bound, the multithread approach is useless. You can use the c# stopwatch, you can use Intel's Advisor and Vtune profilers (it works on any assembly), you can use the c# profilers (alt+F2 in visual studio).

2. When you split your file in n memory chunks / buffers, you take also the risk to split the keyword too, therefore you want to take that aspect into account in the multithread approach, and into the engineering + maintenance cost.

3. You want to open several filestreams and each stream to be associated to one thread.

4. In c# you want to use the more modern than threads approach which is tasks; when you found the keyword fully, you need to have a thread safe update (use lock); a semi-pseudocode:

   private object _mtx = new();
   private List<long> _foundPositions = new();
   
   public void StartMultireader()
   {
       int ncores = 16; // add manually/from config file/from CPU detection
       for (int i = 0; i < ncores; i++)
           Task.Run(() => FindKeyword(i));
   }
   
   private void FindKeyword(int fileChunk)
   {
       OpenFileStream(fileChunk);
       SearchAndUpdateResult();
   }
   
   private void SearchAndUpdateResult()
   {
       long position = 0;
       //search;
       {
           //if found
           {
               lock (_mtx)
               {
                   _foundPositions.Add(position);
               }
           }
       }
   }
   
   private void OpenFileStream(int fileChunk)
   {
   }
   

Answer 2

Here is a PLINQ approach. By using the PLINQ library you can avoid explicit thread management. The library manages the threads for you, using ThreadPool threads. The AsParallel operator signifies that the subsequent operators will be executed in parallel.

string filePath = @"C:\YourFile.txt";
string searchedText = "TheTextToFind";

bool fileContainsText = File
    .ReadLines(filePath)
    .AsParallel()
    .WithDegreeOfParallelism(Environment.ProcessorCount)
    .Any(line => line.Contains(searchedText, StringComparison.Ordinal));

This solution uses the File.ReadLines method, so it works under the assumption that the searchedText does not contain CR or LF characters. Otherwise the string will not be detected.

The above solution is unlikely to be faster than a normal LINQ query, because of the synchronization overhead associated with passing each individual line to a different thread. A more sophisticated approach would be to process the lines in chunks of, say, 1000 lines per chunk:

bool fileContainsText = Partitioner
    .Create(File.ReadLines(filePath).Chunk(1000),
        EnumerablePartitionerOptions.NoBuffering)
    .AsParallel()
    .WithDegreeOfParallelism(Environment.ProcessorCount)
    .Any(array =>
    {
        return Array.FindIndex(array, line =>
            line.Contains(searchedText, StringComparison.Ordinal)) >= 0;
    });

The Chunk LINQ operator was introduced in .NET 6. For older .NET platforms see the 1st revision of this answer.

The EnumerablePartitionerOptions.NoBuffering configuration optimizes the memory usage, by instructing the PLINQ to avoid buffering the elements of the input enumerable. This is important when working with batches, because each batch can be quite large memory-wise, and reclaiming this memory ASAP is more important than minimizing the synchronization overhead (this is the intention of buffering the input of the query, PLINQ's default behavior, known as chunk partitioning).