The Java implementation used as a reference, both for correctness and “how long would this take to do in Java”, is a lightly modified version of this implementation, taken from the git repo of the original article.
Implementation
This section is going to be considerably larger than previous parts as it’s less abstracted, and not as large as one might expect as most of the logic will be skipped and only the interesting bits will be noted.
Overview
The basic logic is the same, the primary structural difference is that it’s a mutable operation centered on a huge while loop. This is getting a bit on the long side for a Java method, though still within what I dealt with back when worked primarily in Java.
public class JavaStdLib implements FileReader {
private JavaStdLib() {
}
@Override
public String description() {
return "Java StdLib";
}
@Override
public Result consume(Path path) {
Pattern columnDelimiters = Pattern.compile("\\s*\\|\\s*");
Pattern nameDelimiter = Pattern.compile(", ");
try (BufferedReader reader = Files.newBufferedReader(path)) {
String readLine;
int lines = 0;
Set<Integer> indexes = new HashSet<>();
indexes.add(1);
indexes.add(433);
indexes.add(43244);
Map<Integer, String> specialNames = new HashMap<>();
Map<DateBucket, Integer> donationsPerYearMonth = new HashMap<>();
Map<String, Integer> firstNameOccurrences = new HashMap<>();
while ((readLine = reader.readLine()) != null) {
lines++;
String columns[] = columnDelimiters.split(readLine, 9);
String name = columns[7];
if (indexes.contains(lines)) {
specialNames.put(lines - 1, name);
}
String nameParts[] = nameDelimiter.split(name, 3);
if (nameParts.length > 1) {
String firstAndMiddle = nameParts[1].trim();
if (!firstAndMiddle.isEmpty()) {
String firstNameParts[] = firstAndMiddle.split(" ");
firstNameOccurrences.merge(firstNameParts[0].trim(), 1, (a, b) -> a + b);
}
}
String rawDate = columns[4];
Integer month = Integer.parseInt(rawDate.substring(4, 6));
Integer year = Integer.parseInt(rawDate.substring(0, 4));
donationsPerYearMonth.merge(DateBucket.apply(year, month), 1, (a, b) -> a + b);
}
Map.Entry<String, Integer> mostCommonFirstName = Collections.max(
firstNameOccurrences.entrySet(),
Map.Entry.comparingByValue());
return Result.fromJava(
lines,
specialNames,
donationsPerYearMonth,
mostCommonFirstName.getKey(),
mostCommonFirstName.getValue()
);
} catch (IOException e) {
throw new RuntimeException(e);
}
}
public static JavaStdLib implementation = new JavaStdLib();
}
Result.fromJava
It turns out that the Java compiler doesn’t handle some Scala features gracefully, so there needed to be a method on the Scala side to handle the conversions. The length of the collections at play is so small that it shouldn’t affect the outcome of the timing.
Ergonomics 😕
These bits made me really wish this method was defined on Scala’s Map. Well done, Java:
donationsPerYearMonth.merge(DateBucket.apply(year, month), 1, (a, b) -> a + b);
Otherwise, it wasn’t great. Particularly bad is that the logic handling the record layout is scattered through the body of the method, so changing it would be error-prone.
Safety 😞
Other than “don’t use an int when you mean a String”, there wasn’t much. The whole thing is completely mutable and isn’t clean to reason about.
Performance
I really expected this to be even with (or possibly beat) the Scala Standard Library. Functional programming and immutable data tend to have a performance cost, which is generally more than justified by other factors. The Java implementation is mutable and extremely simple, so both the longer average runtime and the greater variability between measurements were a huge surprise.
This was such a surprise that I pulled the git repo for the original challenge and ran the pure Java version a couple of times manually as a sanity check. The results were in the 88 seconds range, so the automatically gathered results seem reliable.
Still, it seemed like such an outliner that I ran it by one of our newer Livongoans, Polina Spivak, whose Java chops were considerably less rusty than mine.
We were able to improve on the implementation somewhat, knocking about 2 minutes off the average runtime through various optimizations. We got the biggest lift by switching from using the split provided by the String class to the split provided by the Pattern class to cache the regex compilation.
The current implementation probably has other optimizations which could hopefully bring it closer to the times we saw in the Scala standard library.
| library | env | wall clock (mm:ss ± %) | % of best in env | % of best | % of reference | % change from local |
|---|---|---|---|---|---|---|
| Scala StdLib | local | 00:36.643 ± 1.91 % | 100.00 % | 100.00 % | 20.34 % | 0.00 % |
| Java StdLib | local | 01:17.751 ± 4.42 % | 212.18 % | 212.18 % | 43.16 % | 0.00 % |
| Scala StdLib | EC2 | 02:02.973 ± 8.83 % | 100.00 % | 335.59 % | 68.26 % | 235.59 % |
| Java StdLib | EC2 | 03:00.161 ± 23.98 % | 146.50 % | 491.66 % | 100.00 % | 131.71 % |
Memory Usage
The Java version ruled the memory usage metric, beating the next most frugal library by half. This isn’t surprising, because of the extra allocations involved in using immutable data. What’s surprising is that the GC was able to handle the extra allocations incurred by the Scala implementations without the more frequent GC cycles providing a noticeable edge to the Java implementation.
| library | env | peak memory used (mb ± %) | % of best in env | % of best | % of reference |
|---|---|---|---|---|---|
| Java StdLib | local | 321.51 ± 7.93 % | 100.00 % | 100.00 % | 97.75 % |
| Java StdLib | EC2 | 328.89 ± 9.71 % | 100.00 % | 102.30 % | 100.00 % |
| Scala StdLib | EC2 | 365.64 ± 0.06 % | 111.17 % | 113.73 % | 111.17 % |
| Scala StdLib | local | 916.20 ± 7.59 % | 284.97 % | 284.97 % | 278.57 % |
Conclusion
If memory is extremely constrained, it might be worth looking at as a last recourse.
Up next: TL;DR
