Java多线程: Fast alternative to AtomicInteger wanted

Question

我有一个(大约 250.000)个三态单元，其状态为 UNKNOWN、TRUE 或 FALSE。

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

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

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

线程越早看到单元格的更改就越好。在这些条件下，我也不关心写入重新排序。

我目前正在使用 AtomicInteger 来实现单元。分析显示，我在这门课上花费了大约 30% 的计算时间。

我可以做些什么来改善这种情况？

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

Answer 1

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

volatile 不能满足您的要求。

考虑这种情况:

• 您的单元格状态未知
• 2 个线程尝试同时更改状态
• 一个想要将状态更改为 TRUE，另一个想要将状态更改为 FALSE
• 两者都可以检索(在阅读时，正确的)未知的 volatile 值
• 读取值后，两个线程都会被中断并稍后恢复
  
• 然后他们都更新它
• 也许他们都不会赢，但他们都认为自己赢了!
  

这种情况有些人为，但有可能，并且按照您正在进行的数字运算，很有可能。这就是墨菲定律。

多个线程可以从 volatile 中读取正确的值是不够的，它们需要确保状态在更新期间保持不变，这就是为什么没有办法绕过某种锁定。

另请注意，广泛传播的双重检查锁定算法(至少在 Java 中)是一种被误解的反模式。它会失败。您可以在维基百科中阅读相关内容。

尝试下面的概念验证程序。
它使用同步来解决您的需求并且坚如磐石。
性能: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!
     */
}