什么实现细节使这个代码很容易失败？

Question

这个问题不是关于众所周知和记录的事实,HashMap它不是线程安全的,而是关于它在HotSpot和JDK代码上的特定故障模式.我很惊讶这个代码在NPE中失败了:

public static void main(String[] args) {
    Map<Integer, Integer> m = new HashMap<>(0, 0.75f);
    IntStream.range(0, 5).parallel().peek(i -> m.put(i, i)).map(m::get).count();
}

NPE的来源并不神秘:.map(m::get)尝试拆箱时的步骤null.它在5次运行中大约有4次失败.

在我的机器上Runtime#availableProcessors()报告8,所以假设长度为5的范围被分成5个子任务,每个子任务只有一个成员.我还假设我的代码以解释模式运行.它可能正在调用JIT编译HashMap或Stream方法,但是顶层被解释,因此排除了将HashMap状态加载到线程本地存储器(寄存器/堆栈)中的任何变化,从而延迟了另一个线程对更新的观察.如果五个put操作中的某些操作在同一时间不在不同的核心上执行,我不认为它会破坏HashMap内部结构.鉴于工作量很小,个别任务的时间安排必须非常精确.

它是否真的是精确的时间(commonPool必须取消停放的线程),还是有其他途径导致Oracle/OpenJDK HotSpot失败？我目前的版本是

java version "1.8.0_72"
Java(TM) SE Runtime Environment (build 1.8.0_72-b15)
Java HotSpot(TM) 64-Bit Server VM (build 25.72-b15, mixed mode)

更新:我发现即使只进行两次插入也有类似的高故障率:

IntStream.range(0, 2).parallel().peek(i -> m.put(i, i)).map(m::get).count();

Answer 1

首先,它并没有可靠地失败.我设法进行了一些没有发生异常的运行.然而,这并不意味着得到的地图是正确的.每个线程也可能会成功放置自己的值,而生成的映射会错过几个映射.

但实际上,失败的NullPointerException情况经常发生.我创建了以下调试代码来说明它HashMap的工作原理:

static <K,V> void debugPut(HashMap<K,V> m, K k, V v) {
    if(m.isEmpty()) debug(m);
    m.put(k, v);
    debug(m);
}
private static <K, V> void debug(HashMap<K, V> m) {
    for(Field f: FIELDS) try {
        System.out.println(f.getName()+": "+f.get(m));
    } catch(ReflectiveOperationException ex) {
        throw new AssertionError(ex);
    }
    System.out.println();
}
static final Field[] FIELDS;
static {
    String[] name={ "table", "size", "threshold" };
    Field[] f=new Field[name.length];
    for (int ix = 0; ix < name.length; ix++) try {
        f[ix]=HashMap.class.getDeclaredField(name[ix]);
    }
    catch (NoSuchFieldException ex) {
        throw new ExceptionInInitializerError(ex);
    }
    AccessibleObject.setAccessible(f, true);
    FIELDS=f;
}

使用简单的顺序for(int i=0; i<5; i++) debugPut(m, i, i);打印:

table: null
size: 0
threshold: 1

table: [Ljava.util.HashMap$Node;@70dea4e
size: 1
threshold: 1

table: [Ljava.util.HashMap$Node;@5c647e05
size: 2
threshold: 3

table: [Ljava.util.HashMap$Node;@5c647e05
size: 3
threshold: 3

table: [Ljava.util.HashMap$Node;@33909752
size: 4
threshold: 6

table: [Ljava.util.HashMap$Node;@33909752
size: 5
threshold: 6

如您所见,由于初始容量0,即使在顺序操作期间也会创建三个不同的后备阵列.每次,容量增加,racy并发put错过数组更新并创建自己的数组的可能性更高.

这对于空映射的初始状态和几个尝试放置其第一个键的线程尤其相关,因为所有线程可能遇到null表的初始状态并创建它们自己的状态.此外,即使在读取完成的第一个状态时,也会put为第二个创建新阵列put.

但逐步调试显示出更多破坏机会:

在方法内部putVal,我们看到最后:

++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

换句话说,在成功插入新密钥后,如果新大小超过,则表格将调整大小threshold.所以,第一put,resize()在开始时调用,因为该表是null和你的,因为指定的初始容量0,即过低存储一个映射,新增产能将1和新threshold会1 * loadFactor == 1 * 0.75f == 0.75f,四舍五入到0.因此,在第一个结束时put,新threshold的超出并resize()触发另一个操作.因此,在初始容量为的情况下0,第一个put已经创建并填充两个数组,如果多个线程同时执行此操作,则会提供更高的中断机会,所有这些都会遇到初始状态.

还有一点.查看操作,我们看到了以下几resize()行:

 @SuppressWarnings({"rawtypes","unchecked"})
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 if (oldTab != null) {
     … (transfer old contents to new array)

换句话说,新数组引用在用旧条目填充之前存储到堆中,因此即使不重新排序读取和写入,另一个线程也有可能在不查看旧条目的情况下读取该引用,包括一个它以前写过的.实际上,减少堆访问的优化可能会降低线程在紧接着的查询中看不到自己的更新的可能性.

尽管如此,它还必须注意到,这里假设所有运行都是在这里解释的.由于HashMapJRE内部也在使用,因此即使在应用程序启动之前,使用时也有可能遇到已编译的代码HashMap.