Explain a performance difference

Question

Here's the Full Source and a direct link to the data

These tests have wildly varying timings but go through the same implementation. I'd like to understand why the timings are different.

private static final int ITERATIONS = 100;
private static final DataFactory RANDOM_DF = DataFactoryImpl.defaultInstance();


@Test // 6s
public void testGetMaxLength() throws Exception {
    for ( int i = 1; i < ITERATIONS; i++ ) {
        testGetMaxLength( i );
    }
}

private void testGetMaxLength( final int length ) {
    for ( int i = 0; i < ITERATIONS; i++ ) {
        String word = RANDOM_DF.word().getMaxLength( length );
        assertThat( word, not( isEmptyOrNullString() ) );
        assertThat( word.length(), allOf( greaterThanOrEqualTo( 1 ), lessThanOrEqualTo( length ) ) );
    }
}

@Test //  301ms
public void testGetLength() throws Exception {
    for ( int i = 1; i < ITERATIONS; i++ ) {
        testGetLength( i );
    }
}

private void testGetLength( final int length ) {
    for ( int i = 0; i < ITERATIONS; i++ ) {
        String word = RANDOM_DF.word().getLength( length );
        assertThat( word, not( isEmptyOrNullString() ) );
        assertThat( word.length(), equalTo( length ) );

This is the class DataFactoryUtil that most likely contains the code causing the massive difference.

final class DataFactoryUtil {
    private DataFactoryUtil() {
    }

    static <T> Optional<T> valueFromMap(
            final Map<Integer, List<T>> map,
            final IntUnaryOperator randomSupplier,
            final int minInclusive,
            final int maxInclusive
    ) {
        List<T> list = map.entrySet()
                .parallelStream() // line 26
                .filter( e -> e.getKey() >= minInclusive && e.getKey() <= maxInclusive )
                .map( Map.Entry::getValue )
                .flatMap( Collection::stream )
                .collect( Collectors.toList() );

        return valueFromList( list, randomSupplier );
    }

    static <T> Optional<T> valueFromList( final List<T> list, final IntUnaryOperator randomSupplier ) {
    int random = randomSupplier.applyAsInt( list.size() );
    return list.isEmpty() ? Optional.empty() : Optional.of( list.get( random ) );
    }

    static List<String> dict() {
        try {
            URL url = DataFactoryUtil.class.getClassLoader().getResource( "dictionary" );
            assert url != null;
            return Files.lines( Paths.get( url.toURI() ) ).collect( Collectors.toList() );
        }
        catch ( URISyntaxException | IOException e ) {
            throw new IllegalStateException( e );
        }
    }
}

Here's the different implementations

@FunctionalInterface
public interface RandomStringFactory {

    default String getMaxLength( final int maxInclusive ) {
        return this.getRange( 1, maxInclusive );
    }

    String getRange( final int minInclusive, final int maxInclusive );

    default String getLength( int length ) {
        return this.getRange( length, length );
    }
}

and the actual implementation of word

DataFactoryImpl( final IntBinaryOperator randomSource, final List<String> wordSource ) {
    this.random = randomSource;
    this.wordSource = wordSource.stream().collect( Collectors.groupingBy( String::length ) );
}

public static DataFactory defaultInstance() {
    return new DataFactoryImpl( RandomUtils::nextInt, dict() );
}

default RandomStringFactory word() {
    return ( min, max ) -> valueFromMap( getWordSource(), ( size ) -> getRandom().applyAsInt( 0, size ), min, max )
            .orElse( alphabetic().getRange( min, max ) );


}

Why is the measurement of these 2 methods so different when they share an implementation? is there any way I can improve the worst case for getMaxLength?

update

while I like the theory of Random being the source, and maybe it's true. changing my code to this caused a 13s run, which is longer than the run, which is more than twice the time of RandomUtils::nextInt.

public static DataFactory defaultInstance() {
    return new DataFactoryImpl( (a, b) -> a == b ? a :    ThreadLocalRandom.current().nextInt(a, b), dict() ); 
}

Answer 1

Why is the measurement of these 2 methods so different when they share an implementation?

Well, consider you have a "shared implementation" for counting pages in a set of books.

In the first case the set consists of a single book. You open the last page, look at its number and - that's it! A piece of cake.

In the second case the given set of books is the National Library... Does the analogy help?

---

The same is in your test. testGetLength chooses a random word with the given length, where all words are already grouped by their lengths.

filter( e -> e.getKey() >= minInclusive && e.getKey() <= maxInclusive ) retains at most one group of words, but more often, even zero (there are no words with length > 30).

testGetMaxLength chooses a random word shorter than the given length. The list of such words is never empty. Even worse, your flatMap + collect merges all by-length lists in one reeeeally large combined list, and this operation is reeeeally slow. Have you ever tried to use a profiler?

is there any way I can improve the worst case for getMaxLength?

Of course. But this would require complete redesign of the algorithms and the data structures used. For example, you could sort all your dictionary by the word lengths, and then build an array-backed index that maps a length to the last position in the result list of a word of this length. In such case you'll be able to get a range (1, maxLength) in a constant time.

Answer 2

The difference is actually in RandomUtils.nextInt() implementation which you are using to produce random numbers. In case if startInclusive and endInclusive parameters match (like in getLength()), it just returns the argument which is really fast. Otherwise it requests static instance of java.util.Random object to get the random number. The java.util.Random is thread-safe, but has very serious contention problems: you cannot just independently request random numbers from different threads: they will starve in CAS-loops. As you are using .parallelStream() in your valueFromMap, you hit these problems.

The simplest fix to apply here is to use ThreadLocalRandom instead:

new DataFactoryImpl( (a, b) -> ThreadLocalRandom.current().nextInt(a, b+1), dict() );

Note that ThreadLocalRandom.nextInt() has no fast-path like RandomUtils.nextInt(), so if you want to keep it, use:

new DataFactoryImpl( 
    (a, b) -> a == b ? a : ThreadLocalRandom.current().nextInt(a, b+1), dict() );

Be careful not to cache ThreadLocalRandom.current() instance somewhere outside (like in field or static variable): this call must be performed in the same thread where random number is actually requested.