Capstone: a parallel word count
The concurrency part ends with the program every parallel framework demonstrates: count the words of several documents at once and check the totals against one thread. It uses the executor of lesson 116, the futures of lesson 117, the concurrent map of lesson 120 and the counting of lesson 073, and it is small enough that the numbers can be checked by hand.
The task
A count of words is a map from a word to how often it appears, and the work splits by document: each document can be counted on its own, and the maps are added together at the end. That is the whole design, and it is called map and reduce after the two steps.
The four documents are in the source so the program runs alone. Their word counts are the numbers on the page: 9, 7, 4 and 2 words, 22 in all, and the word the appears five times.
The sequential count
One loop over the documents and one merge per word, into a TreeMap so the output is sorted. This is the reference the parallel version must match:
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class WordCount {
static final List<String> DOCUMENTS = List.of(
"the quick brown fox jumps over the lazy dog",
"the dog barks and the fox runs",
"a quick brown dog",
"the end");
public static void main(String[] args) throws InterruptedException, ExecutionException {
Map<String, Integer> sequential = countSequential();
Map<String, Integer> parallel = countParallel(4);
System.out.println("words: " + sequential.values().stream().mapToInt(Integer::intValue).sum());
System.out.println("distinct: " + sequential.size());
System.out.println("the: " + sequential.get("the"));
System.out.println("fox: " + sequential.get("fox"));
System.out.println("same result: " + sequential.equals(new TreeMap<>(parallel)));
System.out.println("first five: " + sequential.entrySet().stream().limit(5).toList());
}
static Map<String, Integer> countSequential() {
Map<String, Integer> counts = new TreeMap<>();
for (String document : DOCUMENTS) {
for (String word : document.split(" ")) {
counts.merge(word, 1, Integer::sum);
}
}
return counts;
}
static Map<String, Integer> countParallel(int threads) throws InterruptedException, ExecutionException {
ExecutorService pool = Executors.newFixedThreadPool(threads);
List<Future<Map<String, Integer>>> futures = new ArrayList<>();
for (String document : DOCUMENTS) {
futures.add(pool.submit(() -> {
Map<String, Integer> local = new TreeMap<>();
for (String word : document.split(" ")) {
local.merge(word, 1, Integer::sum);
}
return local;
}));
}
Map<String, Integer> merged = new ConcurrentHashMap<>();
for (Future<Map<String, Integer>> future : futures) {
future.get().forEach((word, count) -> merged.merge(word, count, Integer::sum));
}
pool.shutdown();
return merged;
}
}
javac -Xlint:all WordCount.java
java WordCount
words: 22
distinct: 13
the: 5
fox: 2
same result: true
first five: [a=1, and=1, barks=1, brown=2, dog=3]
The parallel count
Each document is a task that returns its own map, so the tasks share nothing while they run. The merge happens on the main thread after the get of each future, which is why the ConcurrentHashMap is not strictly needed here: one thread merges, and the map could be a plain one.
The concurrent map becomes necessary the moment the merge moves into the tasks, which is the next step of the design: a task that merges into the shared map as soon as it finishes, so the main thread does less. Then the merge of the map is the atomic operation of lesson 120, and the counts stay exact. The version on the page is the simpler one on purpose, because it makes the split and the join visible.
The result checked
The comparison is the interesting line: sequential.equals(new TreeMap<>(parallel)) copies the concurrent map into a sorted one so the two are the same type, and the answer is true. A test that compares the two maps is the check a parallel implementation needs, because a lost update shows up as a difference in one count.
The totals are computed from the map rather than stored, so the sum of the values, 22, and the size, 13, are the two facts a reader checks first. The five lines of the last output are the first five words in alphabetical order: a, and, barks, brown and dog, with the counts of the table of lesson 079.
Reading the numbers
Check the table against the text. the appears twice in the first document, twice in the second and once in the fourth, which is five. dog is in the first, the second and the third, which is three and the fourth line of the table. fox is in the first and the second, which is two, and brown in the first and the third, which is two.
The words of the four documents are 9 + 7 + 4 + 2 = 22, and the distinct ones are the thirteen of the table. A parallel count that printed 21 or a the of four would be wrong, and the program's own comparison would say so.
Exercises
- Add a fifth document and update the expected numbers by hand before you run it.
- Move the merge into the tasks, into the shared ConcurrentHashMap, and print the same totals.
- Replace the executor with a virtual-thread executor and compare the code.
- Print the ten most frequent words, sorted by count and then by word.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What are the two steps of map and reduce?
Answer
Counting each document on its own, then adding the counts together
The map is the per-document count and the reduce is the merge of the maps.
-
Why does each task return its own map?
Answer
The tasks then share no mutable state while they run
A local map is thread-confined, so the counting needs no lock.
-
Why is the result compared with the sequential one?
Answer
A lost update in the parallel version shows as a difference in a count
Two independent computations that agree are the strongest check the program can make.
-
What does this program print?
import java.util.concurrent.ConcurrentHashMap; public class Q1 { public static void main(String[] args) { ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>(); for (String word : new String[] {"a", "b", "a"}) { map.merge(word, 1, Integer::sum); } System.out.println(map.get("a")); System.out.println(map.values().stream().mapToInt(Integer::intValue).sum()); } }Answer
2 / 3
The word a is counted twice, and the three words are the sum of the values.
-
When does the shared map need to be concurrent?
Answer
When the tasks merge into it while they run
The version where the main thread merges after the joins could use a plain map.
-
What does the sum of the map values give?
Answer
The total number of words counted
Each value is the count of one word, so the sum is the number of words.
-
Why does the check copy the concurrent map into a TreeMap?
Answer
So both sides of equals are the same kind of map
Map equality compares the entries, and a sorted copy also gives a stable order for the test.
-
What does this program print?
import java.util.Map; import java.util.TreeMap; public class Q2 { public static void main(String[] args) { Map<String, Integer> counts = new TreeMap<>(); for (String word : "b a b".split(" ")) { counts.merge(word, 1, Integer::sum); } System.out.println(counts); System.out.println(counts.values().stream().mapToInt(Integer::intValue).sum()); } }Answer
{a=1, b=2} / 3
The sorted map orders the keys and the two b words are counted together.
-
What would a lost update look like in this program?
Answer
A count lower than the sequential one, caught by the comparison
A lost merge drops one from a count, and the two maps then differ.
-
What is the main thread doing while the tasks count?
Answer
Waiting in get for the first future, then the next
The gets are in the order of the list, so the merge starts as soon as the first task is done.
The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.
Article author: Arthur Isaev