The 4am Jamestown-Scotland ferry and other optimization strategies

Donald Raab
Jan 3, 2018 · 13 min read
Shortcuts sometimes aren’t.

Takeaways from this blog

A shortcut with a twist

“Two roads diverged in a wood…” — Robert Frost

“Premature optimization is the root of all evil” — Donald Knuth

Iteration Pattern Optimization Strategies

Eager vs. Lazy — Understanding how they work

@Test
public void eagerVsLazy()
{
long eagerSum = Lists.mutable.with(1, 2, 3, 4, 5)
.tap(i -> System.out.println("eager select: " + i))
.select(i -> i % 2 == 0)
.tap(i -> System.out.println("eager collect: " + i))
.collectInt(i -> i * 2)
.tap(i -> System.out.println("eager sum: " + i))
.sum();
System.out.println(eagerSum);

long lazySum = Lists.mutable.with(1, 2, 3, 4, 5)
.asLazy()
.tap(i -> System.out.println("lazy select: " + i))
.select(i -> i % 2 == 0)
.tap(i -> System.out.println("lazy collect: " + i))
.collectInt(i -> i * 2)
.tap(i -> System.out.println("lazy sum: " + i))
.sum();
System.out.println(lazySum);

Assert.assertEquals(eagerSum, lazySum);
}
eager select: 1
eager select: 2
eager select: 3
eager select: 4
eager select: 5
eager collect: 2
eager collect: 4
eager sum: 4
eager sum: 8
12
lazy select: 1
lazy select: 2
lazy collect: 2
lazy sum: 4
lazy select: 3
lazy select: 4
lazy collect: 4
lazy sum: 8
lazy select: 5
12
@Test
public void stream()
{
int streamSum = Lists.mutable.with(1, 2, 3, 4, 5)
.stream()
.peek(i -> System.out.println("stream filter: "+ i))
.filter(i -> i % 2 == 0)
.peek(i -> System.out.println("stream map: "+ i))
.mapToInt(i -> i * 2)
.peek(i -> System.out.println("stream sum: "+ i))
.sum();
System.out.println(streamSum);
}
stream filter: 1
stream filter: 2
stream map: 2
stream sum: 4
stream filter: 3
stream filter: 4
stream map: 4
stream sum: 8
stream filter: 5
12
@Test
public void parallel()
{
long parallelSum = Lists.mutable.with(1, 2, 3, 4, 5)
.asParallel(Executors.newWorkStealingPool(), 1)
.select(i -> {
System.out.println("parallel select: " + i);
return i % 2 == 0;
})
.collect(i -> {
System.out.println("parallel collect: " + i);
return i * 2;
})
.sumOfInt(i -> {
System.out.println("parallel sum: " + i);
return i;
});
System.out.println(parallelSum);
}
Run 1:
parallel select: 2
parallel select: 1
parallel select: 4
parallel collect: 4
parallel select: 3
sum: 8
parallel select: 5
parallel collect: 2
sum: 4
12
Run 2:
parallel select: 1
parallel select: 3
parallel select: 2
parallel select: 5
parallel select: 4
parallel collect: 2
parallel collect: 4
parallel sum: 4
parallel sum: 8
12
Run 3:
parallel select: 4
parallel select: 2
parallel collect: 2
parallel select: 5
parallel select: 3
parallel select: 1
parallel sum: 4
parallel collect: 4
parallel sum: 8
12
@Test
public void parallelStream()
{
int streamSum = Interval.oneTo(5).toList()
.parallelStream()
.peek(i -> System.out.println("stream filter: "+ i))
.filter(i -> i % 2 == 0)
.peek(i -> System.out.println("stream map: "+ i))
.mapToInt(i -> i * 2)
.peek(i -> System.out.println("stream sum: "+ i))
.sum();
System.out.println(streamSum);
}
Run 1:
stream filter: 4
stream filter: 1
stream map: 4
stream filter: 2
stream sum: 8
stream filter: 3
stream filter: 5
stream map: 2
stream sum: 4
12
Run 2:
stream filter: 5
stream filter: 1
stream filter: 3
stream filter: 2
stream filter: 4
stream map: 2
stream map: 4
stream sum: 4
stream sum: 8
12
Run 3:
stream filter: 2
stream filter: 4
stream map: 2
stream map: 4
stream sum: 8
stream filter: 1
stream filter: 3
stream filter: 5
stream sum: 4
12

Measure, Execute and Repeat.

Use Cases — Filter, Map, Reduce, and Filter/Map/Reduce

1. Filter even integers into a List
2. Multiply the integers by 2 and storing the result in a List
3. Sum all the integers into a long
4. Filter/Map/Reduce (Filter Evens, Multiply x 2, Sum into long)

The Data — 1,000,000 Integers

private List<Integer> jdkList;
private MutableList<Integer> ecList;
private IntList ecPrimitiveList;
private ExecutorService executorService;
@Setup
public void setup()
{
PrimitiveIterator.OfInt intGenerator =
new Random(1L).ints(-1000, 1000).iterator();
this.ecList =
FastList.newWithNValues(1_000_000, intGenerator::nextInt);
this.jdkList = new ArrayList<>(1_000_000);
this.jdkList.addAll(this.ecList);
this.ecPrimitiveList =
this.ecList.collectInt(i -> i, new IntArrayList(1_000_000));
this.executorService = Executors.newWorkStealingPool();
}

Hardware

Processor Name: 12-Core Intel Xeon E5
Processor Speed: 2.7 GHz
Number of Processors: 1
Total Number of Cores: 12
L2 Cache (per Core): 256 KB
L3 Cache: 30 MB
Memory: 64 GB

Software

Benchmarking

public static void main(String[] args) throws RunnerException
{
Options options = new OptionsBuilder()
.include(".*" + IntListJMHTest.class.getSimpleName() + ".*")
.forks(2)
.mode(Mode.Throughput)
.timeUnit(TimeUnit.SECONDS)
.warmupIterations(30)
.build();
new Runner(options).run();
}

Filter even integers

Filter even numbers from a List of 1,000,000 Integers
@Benchmark
public MutableList<Integer> filterECBoxedEager()
{
return this.ecList.select(i -> i % 2 == 0);
}
@Benchmark
public MutableList<Integer> filterECBoxedLazy()
{
return this.ecList
.asLazy()
.select(i -> i % 2 == 0)
.toList();
}
@Benchmark
public MutableList<Integer> filterECParallelEager()
{
return ParallelIterate.select(
this.ecList,
i -> i % 2 == 0,
new CompositeFastList<>(),
false);
}
@Benchmark
public MutableList<Integer> filterECParallelLazy()
{
return this.ecList
.asParallel(this.executorService, 50_000)
.select(i -> i % 2 == 0)
.toList();
}
@Benchmark
public IntList filterECPrimitiveEager()
{
return this.ecPrimitiveList.select(i -> i % 2 == 0);
}
@Benchmark
public IntList filterECPrimitiveLazy()
{
return this.ecPrimitiveList
.asLazy()
.select(i -> i % 2 == 0)
.toList();
}
@Benchmark
public List<Integer> filterJDKBoxedParallelStream()
{
return this.jdkList
.parallelStream()
.filter(i -> i % 2 == 0)
.collect(Collectors.toList());
}
@Benchmark
public List<Integer> filterJDKBoxedStream()
{
return this.jdkList
.stream()
.filter(i -> i % 2 == 0)
.collect(Collectors.toList());
}

Map each integer x 2

Multiply times two, each integer in a List of 1,000,000 Integers
@Benchmark
public MutableList<Integer> mapECBoxedEager()
{
return this.ecList.collect(i -> i * 2);
}
@Benchmark
public MutableList<Integer> mapECBoxedLazy()
{
return this.ecList
.asLazy()
.collect(i -> i * 2)
.toList();
}
@Benchmark
public MutableList<Integer> mapECParallelEager()
{
return ParallelIterate.collect(
this.ecList, i -> i * 2,
new CompositeFastList<>(),
false);
}
@Benchmark
public MutableList<Integer> mapECParallelLazy()
{
return this.ecList
.asParallel(this.executorService, 50_000)
.collect(i -> i * 2)
.toList();
}
@Benchmark
public IntList mapECPrimitiveEager()
{
return this.ecPrimitiveList
.collectInt(i -> i * 2, IntLists.mutable.empty());
}
@Benchmark
public IntList mapECPrimitiveLazy()
{
return this.ecPrimitiveList
.asLazy()
.collectInt(i -> i * 2)
.toList();
}
@Benchmark
public List<Integer> mapJDKBoxedParallelStream()
{
return this.jdkList
.parallelStream()
.mapToInt(i -> i * 2)
.boxed()
.collect(Collectors.toList());
}
@Benchmark
public List<Integer> mapJDKBoxedStream()
{
return this.jdkList
.stream()
.mapToInt(i -> i * 2)
.boxed()
.collect(Collectors.toList());
}

Sum all integers

Sum 1,000,000 Integers
@Benchmark
public long sumECBoxedEager()
{
return this.ecList.sumOfInt(Integer::intValue);
}
@Benchmark
public long sumECBoxedLazy()
{
return this.ecList
.asLazy()
.sumOfInt(Integer::intValue);
}
@Benchmark
public long sumECParallelEager()
{
return ParallelIterate.sumByInt(
this.ecList,
i -> Integer.valueOf(0),
Integer::intValue).get(0);
}
@Benchmark
public long sumECParallelLazy()
{
return this.ecList
.asParallel(this.executorService, 50_000)
.sumOfInt(Integer::intValue);
}
@Benchmark
public long sumECPrimitiveEager()
{
return this.ecPrimitiveList.sum();
}
@Benchmark
public long sumECPrimitiveLazy()
{
return this.ecPrimitiveList
.asLazy()
.sum();
}
@Benchmark
public long sumJDKBoxedParallelStream()
{
return this.jdkList
.parallelStream()
.mapToLong(Integer::longValue)
.sum();
}
@Benchmark
public long sumJDKBoxedStream()
{
return this.jdkList
.stream()
.mapToLong(Integer::longValue)
.sum();
}

Filter, Map, Sum

Filter even integers, multiply remaining x 2 and return their sum
@Benchmark
public long filterMapSumECBoxedEager()
{
return this.ecList
.select(i -> i % 2 == 0)
.sumOfInt(i -> i * 2);
}
@Benchmark
public long filterMapSumECBoxedLazy()
{
return this.ecList
.asLazy()
.select(i -> i % 2 == 0)
.sumOfInt(i -> i * 2);
}
@Benchmark
public long filterMapSumECOptimizedParallelEager()
{
return ParallelIterate.sumByInt(
this.ecList,
i -> i % 2,
i -> i * 2).get(0);
}
@Benchmark
public long filterMapSumECOptimizedParallelLazy()
{
return this.ecList
.asParallel(this.executorService, 50_000)
.sumOfInt(i -> i % 2 == 0 ? i * 2 : 0);
}
@Benchmark
public long filterMapSumECParallelLazy()
{
return this.ecList
.asParallel(this.executorService, 50_000)
.select(i -> i % 2 == 0)
.sumOfInt(i -> i * 2);
}
@Benchmark
public long filterMapSumECPrimitiveEager()
{
return this.ecPrimitiveList
.select(i -> i % 2 == 0)
.collectInt(i -> i * 2, IntLists.mutable.empty())
.sum();
}
@Benchmark
public long filterMapSumECPrimitiveLazy()
{
return this.ecPrimitiveList
.asLazy()
.select(i -> i % 2 == 0)
.collectInt(i -> i * 2)
.sum();
}
@Benchmark
public long filterMapSumJDKBoxedParallelStream()
{
return this.jdkList
.parallelStream()
.filter(i -> i % 2 == 0)
.mapToLong(i -> (long) (i * 2))
.sum();
}
@Benchmark
public long filterMapSumJDKBoxedStream()
{
return this.jdkList
.stream()
.filter(i -> i % 2 == 0)
.mapToLong(i -> (long) (i * 2))
.sum();
}

Congratulations!

Recommendations

Donald Raab

Written by

Java Champion. Creator of the Eclipse Collections OSS Java library (http://www.eclipse.org/collections/). Inspired by Smalltalk. Opinions are my own.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade