为什么Arrays.fill()不再用于HashMap.clear()了？

Question

我注意到在执行中有些奇怪HashMap.clear().这就是它在OpenJDK 7u40中的表现:

public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}

这就是OpenJDK 8u40的外观:

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

我知道现在table为空地图可以为null,因此需要在局部变量中进​​行额外的检查和缓存.但为什么被Arrays.fill()for-loop取代？

似乎在此提交中引入了更改.不幸的是,我没有找到解释为什么普通for循环可能比更好Arrays.fill().它更快吗？还是更安全？

Answer 1

我将尝试总结三个在评论中提出的更合理的版本.

@Holger 说:

我想这是为了避免类java.util.Arrays加载作为此方法的副作用.对于应用程序代码,这通常不是问题.

这是最容易测试的事情.让我们编译这样的程序:

public class HashMapTest {
    public static void main(String[] args) {
        new java.util.HashMap();
    }
}

运行它java -verbose:class HashMapTest.这将在发生时打印类加载事件.使用JDK 1.8.0_60,我看到加载了400多个类:

... 155 lines skipped ...
[Loaded java.util.Set from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.AbstractSet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptySet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableCollection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableRandomAccessList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.Reflection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.HashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.HashMap$Node from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$3 from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$ReflectionData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$Atomic from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.AbstractRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.GenericDeclRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.ClassRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$AnnotationData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.annotation.AnnotationType from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.WeakHashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.ClassValue$ClassValueMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.Modifier from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.LangReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.ReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.Arrays from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
...

正如您所看到的,HashMap在应用程序代码之前加载很久并且Arrays之后只加载了14个类HashMap.由于具有静态字段,因此初始化HashMap会触发负载.该负载可能被触发,实际上有负载的方法.该负载由触发延伸.该存在于每个实例.所以对我来说似乎没有类,JDK根本无法初始化.另外,静态初始化是很短的,它只是初始化断言机制.此机制用于许多其他类(例如,包括sun.reflect.ReflectionHashMapArraysWeakHashMapArrays.fillclear()WeakHashMapjava.lang.ClassValue$ClassValueMapWeakHashMapClassValueMapjava.lang.ClassArraysArraysjava.lang.Throwable哪个很早就加载了).没有执行其他静态初始化步骤java.util.Arrays.因此@Holger版本似乎对我不正确.

在这里我们也发现了非常有趣的事情 在WeakHashMap.clear()仍然使用Arrays.fill.当它出现在那里时很有意思,但不幸的是,这发生在史前时代(它已经存在于第一个公共OpenJDK存储库中).

接下来,@ MarcoTopolnik 说:

肯定不会更安全,但是当内联呼叫很短时,它可能会更快.在HotSpot上,循环和显式调用都将导致快速编译器内在(在快乐的情形中).filltabfill

对我来说实际上Arrays.fill并不是直接内在化(参见@apangin生成的内部列表).似乎JVM可以识别和矢量化这样的循环,而无需明确的内部处理.因此,在特定情况下(例如,如果达到限制),可以不内联额外调用.另一方面,它是非常罕见的情况,它只是一个单独的调用,它不是内部循环调用,而是静态的,而不是虚拟/接口调用,因此性能改进可能只是边际而且仅在某些特定情况下.不是JVM开发人员通常关心的事情.MaxInlineLevel

还应该注意的是,即使C1'客户端'编译器(层1-3)也能够内联Arrays.fill调用,例如,WeakHashMap.clear()内联log(-XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintInlining)说:

36       3  java.util.WeakHashMap::clear (50 bytes)
     !m        @ 4   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 28   java.util.Arrays::fill (21 bytes)
     !m        @ 40   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 1   java.util.AbstractMap::<init> (5 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
               @ 9   java.lang.ref.ReferenceQueue::<init> (27 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
                 @ 10   java.lang.ref.ReferenceQueue$Lock::<init> (5 bytes)   unloaded signature classes
               @ 62   java.lang.Float::isNaN (12 bytes)   inline (hot)
               @ 112   java.util.WeakHashMap::newTable (8 bytes)   inline (hot)

当然,它也可以通过智能且功能强大的C2'服务器'编译器轻松实现.因此,我认为这里没有问题.似乎@Marco版本也不正确.

最后,我们收到了@StuartMarks 的一些评论(他是JDK开发人员,因此是一些官方声音):

有趣.我的预感是这是一个错误.此变更审查线程是在这里,它引用了早前的线程是在这里继续.早期线程中的初始消息指向Doug Lea的CVS存储库中的HashMap.java原型.我不知道这是从哪里来的.它似乎与OpenJDK历史中的任何内容都不匹配.

......无论如何,它可能是一些旧的快照; for循环多年来一直在clear()方法中.Arrays.fill()调用是由此变更集引入的,因此它只在树中存在了几个月.另请注意,此变更集引入的基于Integer.highestOneBit()的二次幂计算也同时消失,尽管这已被注意到但在审核期间被驳回.嗯.

确实HashMap.clear()包含了多年的循环,在2013年4月10日被取代并且Arrays.fill在讨论的提交被引入之前,直到9月4日才停留少于半年.讨论的提交实际上是HashMap修复JDK-8023463问题的内部重大改写.这是一个很长的故事,关于HashMap使用重复哈希码的密钥中毒的可能性,将HashMap搜索速度降低到线性,使其容易受到DoS攻击.解决此问题的尝试在JDK-7中执行,包括String hashCode的一些随机化.所以似乎是HashMap 实现是从早期的提交中分离出来的,独立开发,然后合并到主分支中,覆盖介于其间的几个更改.

我们可能会支持这种假设表现出差异.就拿版本,其中Arrays.fill移除(2013年9月4日),并将其与比较以前的版本(2013年7月30日).该diff -U0输出具有4341线.现在让我们对添加之前的版本进行区分Arrays.fill(2013-04-01).现在diff -U0只包含2680行.因此,较新的版本实际上更像是旧版本而不是直接版本.

结论

总而言之,我同意斯图尔特马克斯的意见.没有具体的理由要删除Arrays.fill,这只是因为错误地覆盖了中间的更改.Arrays.fill在JDK代码和用户应用程序中使用都非常好,例如,在用户中使用WeakHashMap.在Arrays类加载反正在JDK初始化过程中很早就已经很简单的静态初始化函数和Arrays.fill方法可以很容易地通过,即使客户端编译器内联,所以没有性能缺陷应引起注意.