解释性能差异

Question

这是全源和与数据的直接链接

这些测试有很大的不同时间，但经过相同的实现。我想知道为什么时间是不同的。

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 ) );

这是类DataFactoryUtil，很可能包含导致巨大差异的代码。

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 );
        }
    }
}

以下是不同的实现

@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 );
    }
}

以及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 ) );


}

为什么这两种方法的度量在共享实现时如此不同？我有没有办法改善getMaxLength最坏的情况？

更新

虽然我喜欢随机理论是来源，也许这是真的。将我的代码更改为这一点会导致13s运行，这比运行时间长，是RandomUtils::nextInt的两倍多。

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

Answer 1

区别实际上是在RandomUtils.nextInt()实现中，您正在使用它来生成随机数。如果startInclusive和endInclusive参数匹配(如getLength()中的参数)，则只返回非常快的参数。另外，它请求java.util.Random对象的静态实例获取随机数。java.util.Random是线程安全的，但是有非常严重的争用问题:您不能只从不同的线程独立地请求随机数:它们将在CAS循环中挨饿。当您在.parallelStream()中使用valueFromMap时，您遇到了以下问题。

这里应用的最简单的修复方法是使用ThreadLocalRandom，而不是：

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

请注意，ThreadLocalRandom.nextInt()没有像RandomUtils.nextInt()这样的快速路径，所以如果您想保留它，请使用：

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

小心不要在外部缓存ThreadLocalRandom.current()实例(比如字段或静态变量)：这个调用必须在实际请求随机数的线程中执行。

Answer 2

为什么这两种方法的度量在共享实现时如此不同？

那么，假设您有一个“共享实现”来计算一组书籍中的页面。

在第一种情况下，集合由一本书组成。你打开最后一页，看看它的号码-就是它！轻而易举。

在第二种情况下，给定的一套书是国家图书馆.这个类比有用吗？

在你的测试中也是如此。testGetLength选择一个具有给定长度的随机单词，其中所有单词都已按其长度分组。

filter( e -> e.getKey() >= minInclusive && e.getKey() <= maxInclusive )最多保留一组单词，但更多的情况是，甚至为零(没有长度超过30的单词)。

testGetMaxLength随机选择一个短于给定长度的单词。这些词的清单从来都不是空的。更糟糕的是，您的flatMap + collect将所有长度的列表合并到一个非常大的合并列表中，这个操作非常慢。你试过使用分析器吗？

我有没有办法改善getMaxLength最坏的情况呢？

当然了。但这需要对算法和所使用的数据结构进行彻底的重新设计。例如，您可以根据单词长度对所有字典进行排序，然后构建一个数组支持的索引，该索引将长度映射到此长度单词的结果列表中的最后一个位置。在这种情况下，您将能够在一个恒定的时间内得到一个范围(1，maxLength)。