小编典典

为什么在HashMap.clear()中不再使用Arrays.fill()?

java

我注意到在实施时有些奇怪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循环代替?

似乎此提交中引入了更改。不幸的是,我找不到任何解释说明为什么普通的for循环会比更好Arrays.fill()。它更快吗?或更安全?


阅读 317

收藏
2020-12-03

共1个答案

小编典典

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

@霍尔格说:

我猜想这是为了避免类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负载由触发sun.reflect.Reflection初始化,因为它有HashMap静态字段。该Arrays负载可能被触发WeakHashMap,实际上有负载Arrays.fillclear()方法。该WeakHashMap负载由触发java.lang.ClassValue$ClassValueMap延伸WeakHashMap。该ClassValueMap存在于每个java.lang.Class实例。在我看来,没有Arrays类,JDK根本无法初始化。另外,Arrays初始化很短一成不变的,它只是初始化断言机制。许多其他类也使用了这种机制(例如,java.lang.Throwable这是很早加载的)。不会执行其他静态初始化步骤java.util.Arrays。因此,@
Holger版本对我来说似乎不正确。

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

接下来,@ MarcoTopolnik

当然不是更安全,但是当呼叫未内联且很短时,它 可能
会更快。在HotSpot上,循环和显式调用都将导致快速的编译器内部函数(在欢乐时光中)。fill``tab``fill

令我惊讶的是,Arrays.fill它没有被直接内化。似乎这种循环可以被JVM识别和向量化,而无需显式的内部处理。因此,在非常特殊的情况下(例如,如果达到限制),不能内联额外的呼叫,这是事实。另一方面,这是非常罕见的情况,它仅是单个调用,不是循环内调用,而是静态(而不是虚拟/接口)调用,因此,性能改善可能仅是微不足道的,并且仅在某些特定情况下才有效。JVM开发人员通常不在乎的事情。MaxInlineLevel

还应注意,即使C1“客户端”编译器(1-3层)也能够内联Arrays.fill调用,例如in
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()方法中使用了很多年。这个changeset引入了Arrays.fill()调用,因此它只在树中呆了几个月。还要注意,此变更集引入的基于Integer.highestOneBit()的二次幂计算也同时消失了,尽管已注意到但在本次审查中被忽略了。嗯

事实上,HashMap.clear()包含循环多年被替换Arrays.fill在2013年4月10日,住少一个半个,直到今年9月4日,当讨论提交了介绍。讨论的提交实际上是对HashMap内部组件的重大重写,以解决JDK-8023463问题。长期以来,关于HashMap散列码重复的键可能会毒害密钥,从而将HashMap搜索速度降低为线性,使其容易受到DoS攻击。解决该问题的尝试是在JDK-7中进行的,包括对String
hashCode的一些随机化。如此看来HashMap
实现是从较早的提交派生的,是独立开发的,然后合并到master分支中,以覆盖介于两者之间的一些更改。

我们可能会支持这种假设进行比较。就拿版本,其中Arrays.fill移除(2013年9月4日),并将其与比较以前的版本(二○一三年七月三十○日)。该diff -U0输出具有4341线。现在,让我们与添加时(2013-04-01)之前的版本进行比较Arrays.fill。现在diff -U0仅包含2680行。因此,新版本实际上比旧版本更像直接父版本。

结论

因此,总而言之,我同意Stuart
Marks的观点。没有具体的理由要删除Arrays.fill,只是因为中间的更改被错误覆盖。Arrays.fill在JDK代码和用户应用程序中使用都非常好,例如,在中使用过WeakHashMapArrays无论如何,该类都是在JDK初始化期间很早就加载的,它具有非常简单的静态初始化器,并且Arrays.fill即使由客户端编译器也可以轻松地内联方法,因此,不应注意到性能上的缺点。

2020-12-03