Java多线程：想要的AtomicInteger的快速替代品

Question

我有一个（约250.000）三态单元，其状态为UNKNOWN，TRUE或FALSE。

所有单元格均以“未知”开头。然后一组大约60个线程（在AMD ThreadRipper 64核心CPU上）进行计算，并将这些变量从UNKNOWN设置为TRUE或FALSE。

一旦为单元格分配了值，它就永远不会改变。

如果两个线程独立地通过不同的策略计算出单元格的值，则可能将相同的值分配给单元格两次。线程以后是否“看到”某个单元的更改并不重要。如果另一个线程决定为值为UNKNOWN的单元格分配TRUE，则它永远不会看到FALSE的中间值。反之亦然。

线程越早看到单元格的变化，就越好。在这种情况下，我也不关心写重新排序。

我目前正在使用AtomicInteger实现单元。剖析显示我在这堂课上花费了大约30％的计算时间。

我该如何改善这种情况？

PS。我这样做是为了创建Nonogram解算器。

Answer 1

正如我们在德国所说的“ Einen Tod muss mann sterben”，所以无法进行某种锁定或同步。

volatile无法满足您的要求。

考虑这种情况：

• 您的单元格处于未知状态
• 2个线程尝试同时更改状态
• 一个想要将状态更改为TRUE，另一个要更改为FALSE
• 两者都可以检索（在读取时，正确的）未知的易失值
• 读取该值后，两个线程都被中断并稍后恢复
• 然后他们都更新了它
• 也许他们俩都不会赢，但都认为他们赢了！

该方案有些人为设计，但很有可能，而且您正在做的数字运算非常有可能。那就是墨菲定律。

多个线程无法从volatile中读取正确的值是不够的，它们需要确保更新的持续时间的状态不变，这就是为什么没有办法进行某种锁定的原因。

还请注意，广泛使用的double-checked lock算法（至少在Java中）是错误识别的anti-pattern。它会失败。您可以在Wikipedia上阅读。

尝试下面的概念验证程序。它使用同步来解决您的要求，并且坚如磐石。性能：90秒钟内有10亿次访问，多线程。

import java.security.SecureRandom;
import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

public class TriState {

    private static final byte TRI_STATE_UNKNOWN =  0;
    private static final byte TRI_STATE_TRUE    =  1;
    private static final byte TRI_STATE_FALSE   =  2;

    private              byte value = TRI_STATE_UNKNOWN;

    public  synchronized boolean isUnknown() {
        return value == TRI_STATE_UNKNOWN;
    }

    public  synchronized boolean isTrue() {
        return value == TRI_STATE_TRUE;
    }

    public  synchronized boolean isFalse() {
        return value == TRI_STATE_FALSE;
    }

    public  synchronized boolean doIfKnown(final Runnable runnable) {

        if (value != TRI_STATE_UNKNOWN) {
            runnable.run();

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean doIfUnknown(final Runnable runnable) {

        if (value == TRI_STATE_UNKNOWN) {
            runnable.run();

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean doIfNotTrue(final Runnable runnable) {

        if (value != TRI_STATE_TRUE) {
            runnable.run();

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean doIfTrue(final Runnable runnable) {

        if (value == TRI_STATE_TRUE) {
            runnable.run();

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean doIfNotFalse(final Runnable runnable) {

        if (value != TRI_STATE_FALSE) {
            runnable.run();

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean doIfFalse(final Runnable runnable) {

        if (value == TRI_STATE_FALSE) {
            runnable.run();

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean setTrue() {
        /*
         * ok to set True if its Unknown or already True...
         */
        if (value != TRI_STATE_FALSE) {
            value =  TRI_STATE_TRUE;

            return   true;
        } else {
            return   false;
        }
    }

    public  synchronized boolean setFalse() {
        /*
         * ok to set False if its Unknown or already False ...
         */
        if (value != TRI_STATE_TRUE) {
            value =  TRI_STATE_FALSE;

            return   true;
        } else {
            return   false;
        }
    }

    private static final int        SIZE      = 250_000;
    private static final TriState[] TRI_STATE = IntStream.range(0, SIZE).mapToObj(move -> new TriState()).toArray(TriState[]::new);

    public static void main(final String[] args) throws Exception {

        final ExecutorService pool     = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        final SecureRandom    rng      = new SecureRandom();

        final Duration        duration = Duration.ofSeconds(90);
        final Instant         end      = Instant.now().plus(duration);
        /*
         * Following accessed TRI_STATE 1,061,946,535 times in 90 seconds on a midrange Office PC...
         */
        pool.submit(() -> {
            while (Instant.now().isBefore(end)) {
                Arrays.stream(TRI_STATE).forEach(triState -> {
                    if (rng.nextBoolean()) {
                        triState.setTrue();
                    } else {
                        triState.setFalse();
                    }
                });
            }
        });
        pool.shutdown();
        pool.awaitTermination(duration.getSeconds(), TimeUnit.SECONDS);
    }
}

这里是一个示例，以突出说明为什么volatile会失败：

public  boolean setTrue() {
    /*
     * Read out Status & if already set, we lost...
     */
    if (status != UNKNOWN) {
        return false;
    }
    /*
     * Status is Unknown here & just BEFORE doing the following, another Thread reads out Status.
     */
    /**/       status     =  TRUE;  // Update volatile Status
    /*
     * Now we can detect if that Thread modifies Status between these 2 lines of code...
     */
    return     status     == TRUE;  // Is volatile Status still True?
    /*
     * Just AFTER doing the above, that Thread updates Status to False, thinking its Unknown.
     * 
     * So now both Threads think they won & you are up a certain creek without a paddle!
     */
}