2

Problem

There is a huge file (10GB), one have to read the file and print out the number of words repeat exactly k times in the file

My Solution

  1. Use ifstream to read the file word by word;
  2. Insert the word into a map std::map<std::string, long> mp; mp[word] += 1;
  3. Once file is read, find all the words in the map to get the words occuring k times

Question

  1. How can multi-thread is used to read the file effectively [read by chunk]? OR Any method to improve the read speed.
  2. Is there any better data structure other than map can be employed to find the output effectively?

File info

  1. each line can be maximum of 500 words length
  2. each word can be maximum of 100 char length
Praveen
  • 8,945
  • 4
  • 31
  • 49

2 Answers2

9

How can multi-thread is used to read the file effectively [read by chunk]? OR Any method to improve the read speed.

I've been trying out the actual results and it's a good thing to multithread, unlike my previous advice here. The un-threaded variant runs in 1m44,711s, the 4-thread one (on 4 cores) runs in 0m31,559s and the 8-thread one (on 4 cores + HT) runs in 0m23,435s. Major improvement then - almost a factor of 5 in speedup.

So, how do you split up the workload? Split it into N chunks (n == thread count) and have each thread except for the first seek to the first non-word character first. This is the start of their logical chunk. Their logical chunk ends at their end boundary, rounded up to the first non-word character after that point.

Process these blocks in parallel, sync them all to one thread, and then make that thread do the merge of results.

Best next thing you can do to improve speed of reading is to ensure you don't copy data when possible. Read through a memory-mapped file and find strings by keeping pointers or indices to the start and end, instead of accumulating bytes.

Is there any better data structure other than map can be employed to find the output effectively?

Well, because I don't think you'll be using the order, unordered_map is a better choice. I would also make it an unordered_map<std::string_view, size_t> - string_view copies it even less than string would.

On profiling I find that 53% of time is spent in finding the exact bucket that holds a given word.

dascandy
  • 7,184
  • 1
  • 29
  • 50
1

If you have a 64-bit system then you can memory-map the file, and use e.g. this solution to read from memory.

Combine with the answer from dascandy regarding std::unordered_map and std::string_view (if you have it), and you should be as fast as you can get in a single thread. You could use std::unordered_multiset instead of std::unordered_map, which one is "faster" I don't know.

Using threads is simple, just do what you do know, but each thread handles only part of the file. Merge the maps after all threads are done. But when you split the file into chunks for each thread, then you risk splitting words in the middle. Handling this is not trivial.

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
  • .. Right. There are systems that don't have 10 GB of address space. `unordered_multiset` won't be faster as it has to keep track of more data. If you do want to do multithreaded, split it into N chunks (n == thread count) and have each thread but the first seek to the first non-word character first. Then make all handle words including those starting at their end (except for the last block). Then when they all finish, merge and sync them. Note that processing 10GB will take order of size 1 second (assuming it's loaded) and threading will add about 2 seconds of overhead. – dascandy Jun 20 '17 at 06:53