如何“安全地发布"广告素材?惰性生成的有效不变数组 [英] How to "safely publish" lazily-generated effectively-immutable array

问题描述

Java当前的内存模型保证，如果对对象"George"的唯一引用存储在某个其他对象"Joe"的final字段中，并且任何其他线程都从未看到过George和Joe，所有线程将在存储之前执行的对George的操作视为在存储之前执行的操作.在有意义的情况下，将对对象的引用存储在此之后永远不会发生突变的情况下，这样做非常好.

Java's present memory model guarantees that if the only reference to an object "George" is stored into a final field of some other object "Joe", and neither George nor Joe have never been seen by any other thread, all operations upon George which were performed before the store will be seen by all threads as having been performed before the store. This works out very nicely in cases where it makes sense to store into a final field a reference to an object which will never be mutated after that.

在应该可变地创建可变类型的对象(在拥有对象的构造函数完成执行后的某个时间)的情况下，是否有任何有效的方法来实现这种语义?考虑一个相当简单的类ArrayThing，它封装了一个不可变的数组，但是它提供了一种方法(三个具有相同名义用途的版本)，用于返回指定元素之前的所有元素的总和.出于本示例的目的，假设将在不使用该方法的情况下构造许多实例，但是在使用该方法的实例上，它将被大量使用；因此，在构造每个ArrayThing实例时，不值得对总和进行预计算，但是将其缓存是值得的.

Is there any efficient way of achieving such semantics in cases where an object of mutable type is supposed to be lazily created (sometime after the owning object's constructor has finished execution)? Consider the fairly simple class ArrayThing which encapsulates an immutable array, but it offers a method (three versions with the same nominal purpose) to return the sum of all elements prior to a specified one. For purposes of this example, assume that many instances will be constructed without ever using that method, but on instances where that method is used, it will be used a lot; consequently, it's not worthwhile to precompute the sums when every instance of ArrayThing is constructed, but it is worthwhile to cache them.

class ArrayThing {
    final int[] mainArray;

    ArrayThing(int[] initialContents) {
        mainArray = (int[])initialContents.clone();
    }
    public int getElementAt(int index) {
        return mainArray[index];
    }

    int[] makeNewSumsArray() {
        int[] temp = new int[mainArray.length+1];
        int sum=0;
        for (int i=0; i<mainArray.length; i++) {
            temp[i] = sum;
            sum += mainArray[i];
        }
        temp[i] = sum;
        return temp;
    }

    // Unsafe version (a thread could be seen as setting sumOfPrevElements1
    // before it's seen as populating array).

    int[] sumOfPrevElements1;
    public int getSumOfElementsBefore_v1(int index) {
        int[] localElements = sumOfPrevElements1;
        if (localElements == null) {
            localElements = makeNewSumsArray();
            sumOfPrevElements1 = localElements;
        }
        return localElements[index];
    }
    static class Holder {
        public final int[] it;
        public Holder(int[] dat) { it = dat; }
    }

    // Safe version, but slower to read (adds another level of indirection
    // but no thread can possibly see a write to sumOfPreviousElements2
    // before the final field and the underlying array have been written.

    Holder sumOfPrevElements2;
    public int getSumOfElementsBefore_v2(int index) {
        Holder localElements = sumOfPrevElements2;
        if (localElements == null) {
            localElements = new Holder(makeNewSumsArray());
            sumOfPrevElements2 = localElements;
        }
        return localElements.it[index];
    }

    // Safe version, I think; but no penalty on reading speed.
    // Before storing the reference to the new array, however, it
    // creates a temporary object which is almost immediately
    // discarded; that seems rather hokey.

    int[] sumOfPrevElements3;
    public int getSumOfElementsBefore_v3(int index) {
        int[] localElements = sumOfPrevElements3;
        if (localElements == null) {
            localElements = (new Holder(makeNewSumsArray())).it;
            sumOfPrevElements3 = localElements;
        }
        return localElements[index];
    }
}

与String#hashCode()方法一样，两个或更多线程可能会看到尚未执行计算，决定执行计算并存储结果.由于所有线程最终都会产生相同的结果，所以这不是问题.但是，对于getSumOfElementsBefore_v1()，存在一个不同的问题:Java可以对程序执行进行重新排序，以便在写入数组的所有元素之前将数组引用写入sumOfPrevElements1.那时另一个名为getSumOfElementsBefore()的线程可以看到该数组不是null，然后继续读取一个尚未写入的数组元素.糟糕！

As with the String#hashCode() method, it is possible that two or more threads might see that a computation hasn't been performed, decide to perform it, and store the result. Since all threads would end up producing identical results, that wouldn't be an issue. With getSumOfElementsBefore_v1(), however, there is a different problem: Java could re-order program execution so the array reference gets written to sumOfPrevElements1 before all the elements of the array have been written. Another thread which called getSumOfElementsBefore() at that moment could see that the array wasn't null, and then proceed to read an array element which hadn't yet been written. Oops.

据我了解，getSumOfElementsBefore_v2()解决了该问题，因为将对数组的引用存储在最终字段Holder#it中会建立与数组元素写入有关的后发生"关系.不幸的是，该版本的代码将需要创建和维护一个额外的堆对象，并且要求每次访问sum-of-elements数组的尝试都要经过一个额外的间接级别.

From what I understand, getSumOfElementsBefore_v2() fixes that problem, since storing a reference to the array in final field Holder#it would establish a "happens-after" relationship with regard to the array element writes. Unfortunately, that version of the code would need to create and maintain an extra heap object, and would require that every attempt to access the sum-of-elements array go through an extra level of indirection.

我认为getSumOfElementsBefore_v3()会便宜一些，但仍然安全. JVM保证在将任何引用存储到final字段之前对新对象执行的所有操作对所有线程可见，直到任何线程可以看到该引用为止.因此，即使其他线程不直接使用Holder#it，但它们正在使用从该字段复制的参考 的事实也将证明，他们在执行完所有操作之后才能看到该参考.是在商店实际发生之前完成的.

I think getSumOfElementsBefore_v3() would be cheaper but still safe. The JVM guarantees that all actions which were done to a new object before a reference is stored into a final field will be visible to all threads by the time any thread can see that reference. Thus, even if other threads don't use Holder#it directly, the fact that they are using a reference which was copied from that field would establish that they can't see the reference until after everything that was done before the store has actually happened.

尽管后一种方法将开销(相对于不安全方法)限制为创建新数组的时间(而不是为每次读取增加开销)，但纯粹出于此目的创建新对象似乎仍然很丑陋写和读回最后一个领域.将数组字段设置为volatile可以实现合法的语义，但是每次读取该字段时都会增加内存系统的开销(volatile限定符将要求代码通知该字段是否是在另一个线程中编写的，但这太过分了对于此应用程序，仅需要确实看到该字段已被写入的任何线程还可以看到该数组发生的所有写操作，从而在存储引用之前识别出该数组). 是否有任何方法可以实现相似的语义，而不必创建和放弃多余的临时对象，或者每次读取字段时都增加额外的开销??

Even though the latter method limits the overhead (versus the unsafe method) to the times when the new array is created (rather than adding overhead to every read), it still seems rather ugly to create a new object purely for the purpose of writing and reading back a final field. Making the array field volatile would achieve legitimate semantics, but would add memory-system overhead every time the field is read (a volatile qualifier would require that the code notice if the field has been written in another thread, but that's overkill for this application; what's necessary is merely that any thread which does see that the field has been written also see all writes which occurred to the array identify thereby before the reference was stored). Is there any way to achieve similar semantics without having to either create and abandon a superfluous temporary object, or add additional overhead every time the field is read??

推荐答案

我认为您的第二个和第三个示例确实起作用(就像您说的那样，引用本身可能不会被另一个线程注意到，这可能会重新分配数组.这是很多额外的工作！).

I think your second and third examples do work (sort of, as you say the reference itself might not be noticed by another thread, which might re-assign the array. That's a lot of extra work!).

但是这些示例基于错误的前提:volatile字段要求读者注意"更改并非正确.实际上，volatile和final字段执行完全相同的操作. volatile或final的读操作在大多数CPU体系结构上都没有开销.我相信写volatile会产生很少的额外开销.

But those examples are based on a faulty premise: it is not true that a volatile field requires the reader to "notice" the change. In fact, volatile and final fields perform exactly the same operation. The read operation of a volatile or a final has no overhead on most CPU architectures. I believe on a write volatile has a tiny amount of extra overhead.

因此，我只在这里使用volatile，而不用担心您所谓的优化".速度上的差异(如果有的话)将非常微小，而且我所说的像是用总线锁写入的额外4字节(如果有的话).而且您的优化"代码让人难以理解.

So I would just use volatile here, and not worry about your supposed "optimizations". The difference in speed, if any, is going to be extremely slight, and I'm talking like an extra 4 bytes written with a bus-lock, if that. And your "optimized" code is pretty god-awful to read.

作为次要项，final字段要求您仅具有对对象的引用以使其不可变并具有线程安全性是不正确的.该规范仅要求您防止更改对象.当然，仅引用对象是一种防止更改的方法.但是已经不可变的对象(例如java.lang.String)可以毫无问题地共享.

As a minor pendant, it is not true that final fields require you to have the sole reference to an object to make it immutable and thread safe. The spec only requires you to prevent changes to the object. Having the sole reference to an object is one way to prevent changes, sure. But objects that are already immutable (like java.lang.String for example) can be shared without problems.

摘要:过早的优化是万恶之源..消除棘手的废话，只需编写一个简单的数组更新，并将其分配给volatile.

In summary: Premature Optimization is the Root of All Evil.. Loose the tricky nonsense and just write a simple array update with assignment to a volatile.

volatile int[] sumOfPrevElements;
public int getSumOfElementsBefore(int index) {
    if( sumOfPrevElements != null ) return sumOfPrevElements[index];
    sumOfPrevElements = makeNewSumsArray();
    return sumOfPrevElements[index];
}

这篇关于如何“安全地发布"广告素材?惰性生成的有效不变数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！