3

A classical problem: read the words from a text file and list the occurence of each unique word in the file.

I solved the problem using a hash map, but how could the performance be improved? I tried reading multiple lines of that file using threads, but even that would be like a bottle neck and there are chances of race condition in a hashmap. Using concurrent HashMap would cause a bottleneck. What would be an ideal multithreaded approach?

  • 5
    Sounds like a trick question to me. Parallelisation is useful if you are CPU limited and have a parallelisable problem; async IO is useful to avoid IO latency; but if you are limited by IO throughput, then multithreading is not going to help. The only way around that would be to split the file between multiple physical drives, then use a map-reduce approach to get the partial count for each fragment (doesn't need any synchronization), then merge the partial results into the final result (involves much less data than the raw file). – amon Jan 16 '17 at 15:18
  • @amon : So much closer like the fork-join approach? – Nilesh Jan 16 '17 at 15:25
  • 1
    To really scale this out, think multiple nodes, not multiple threads or multiple processes. – Erik Eidt Jan 16 '17 at 15:36
  • @amon I take it you are assuming platters and not SSD? – JimmyJames Jan 16 '17 at 15:44
  • @JimmyJames I thought even SSDs would be too slow, but after playing with a couple of benchmarks, it seems that word counting is in fact CPU-limited, not IO-limited. My single-threaded test programs got around 6–11 MB/s throughput, which is around two orders of magnitude slower than either HDD or SSD. – amon Jan 16 '17 at 17:20
3

Supposing you can efficiently split your files into blocks (for instance, groups of lines), you can try to associate some blocks to each thread, and to build an hashmap for each of your threads. As soon as two threads have finished, you can merge their hashmaps into a single new hashmap (The hashmap is nothing but a monad), and proceed until you obtain a single final hashmap counting the words for the entire file.

You have to tune some parameters in order to find the most interesting tradeoff between fine granularity and efficiency: number of threads, number of blocks, etc.

A probably suboptimal but straightforward implementation would be to wait until all your hashmaps are built before merging all of them at the same time. An unchecked attempt in Java 8:

Function<String, Map<String, Long>> countWords = (block) -> {
   Map<String, Long> ret = new HashMap<String, Long>();
   for(String word : block.split(" ")){
      ret.merge(word, 1, (a,b) -> a+b);
   }

   return ret;
};

BinaryOperator<Map<String, Long>> combine = (m1, m2) -> {
   Map<String, Long> m3 = new HashMap<>(m1);
   m2.forEach((k, v) -> m3.merge(k, v, (a,b) -> a+b);

   return m3;
};

Stream<String> blocks = file.getLineBlocks().parallelStream();
Stream<Map<String, Long>> counts = blocks.map(block -> countWords(blocks));
Map<String, Long> count = counts.reduce(new HashMap<String, Long>(), combine);    
3

Many implementations of hash tables are not thread safe. Other implementations may be thread safe, but slow. Other implementations may be thread safe, slow if actually accessed by multiple threads at the same time, and fast if accessed by multiple threads, but not at the same time. Since finding words takes very little effort, any multithreading implementation is likely to hammer the hash table, so most thread safe implementations would be slow.

You could implement a hash table that is fast under multithreading as long as there are no writes (because in that case multi-threading is no problem). Then create your word list multi-threaded, and you can check whether entries are already present in the hash table multithreaded, and if you have a certain amount of new words, you add them single threaded all together. Let's say you have 10 million words but only 100,000 distinct ones, then 9,900,000 times you will find "word is already present" with your multithreaded code.

Of course in this situation having 4 threads which each read 2,500,000 words and each fill their own hash table with 90,000 entries, and then merging the hash tables, would be a lot easier.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.