为什么java vector API比scalar慢？

ccgok5k5 于 2023-03-28 发布在 Java

关注(0)|答案(2)|浏览(137)

我最近决定尝试一下Java新的孵化向量API，看看它能有多快。我实现了两个相当简单的方法，一个用于解析int，另一个用于查找字符串中字符的索引。在这两种情况下，我的向量化方法与标量方法相比都非常慢。
下面是我的代码：

public class SIMDParse {

private static IntVector mul = IntVector.fromArray(
        IntVector.SPECIES_512,
        new int[] {0, 0, 0, 0, 0, 0, 1000000000, 100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1},
        0
);
private static byte zeroChar = (byte) '0';
private static int width = IntVector.SPECIES_512.length();
private static byte[] filler;

static {
    filler = new byte[16];
    for (int i = 0; i < 16; i++) {
        filler[i] = zeroChar;
    }
}

public static int parseInt(String str) {
    boolean negative = str.charAt(0) == '-';
    byte[] bytes = str.getBytes(StandardCharsets.UTF_8);
    if (negative) {
        bytes[0] = zeroChar;
    }
    bytes = ensureSize(bytes, width);
    ByteVector vec = ByteVector.fromArray(ByteVector.SPECIES_128, bytes, 0);
    vec = vec.sub(zeroChar);
    IntVector ints = (IntVector) vec.castShape(IntVector.SPECIES_512, 0);
    ints = ints.mul(mul);
    return ints.reduceLanes(VectorOperators.ADD) * (negative ? -1 : 1);
}

public static byte[] ensureSize(byte[] arr, int per) {
    int mod = arr.length % per;
    if (mod == 0) {
        return arr;
    }
    int length = arr.length - (mod);
    length += per;
    byte[] newArr = new byte[length];
    System.arraycopy(arr, 0, newArr, per - mod, arr.length);
    System.arraycopy(filler, 0, newArr, 0, per - mod);
    return newArr;
}

public static byte[] ensureSize2(byte[] arr, int per) {
    int mod = arr.length % per;
    if (mod == 0) {
        return arr;
    }
    int length = arr.length - (mod);
    length += per;
    byte[] newArr = new byte[length];
    System.arraycopy(arr, 0, newArr, 0, arr.length);
    return newArr;
}

public static int indexOf(String s, char c) {
    byte[] b = s.getBytes(StandardCharsets.UTF_8);
    int width = ByteVector.SPECIES_MAX.length();
    byte bChar = (byte) c;
    b = ensureSize2(b, width);
    for (int i = 0; i < b.length; i += width) {
        ByteVector vec = ByteVector.fromArray(ByteVector.SPECIES_MAX, b, i);
        int pos = vec.compare(VectorOperators.EQ, bChar).firstTrue();
        if (pos != width) {
            return pos + i;
        }
    }
    return -1;
}

}

我完全期望我的int解析会更慢，因为它永远不会处理超过向量大小所能容纳的内容（int的长度永远不会超过10位）。
根据我的bechmarks，将123解析为int类型10 k次，Integer.parseInt花费了3081微秒，而我的实现花费了80601微秒;在一个很长的字符串（"____".repeat(4000) + "a" + "----".repeat(193)）中搜索'a'花费了7709微秒，而String#indexOf花费了7微秒。
为什么它会如此令人难以置信地慢呢？我认为SIMD的全部意义在于它比类似于这些任务的标量等效物更快。

Java

来源：https://stackoverflow.com/questions/68061254/why-is-the-java-vector-api-so-slow-compared-to-scalar

2条答案

按热度按时间

wz1wpwve1#

你选择了SIMD不擅长的东西（string-〉int），以及JVM非常擅长在循环外优化的东西。如果输入不是向量宽度的精确倍数，你就做了一堆额外的复制工作。
我假设你的时间是总数（每个重复10 k），而不是每个电话的平均值。
7我们是不可能的快。
"____".repeat(4000)在'a'之前有16 k个字符（32 k字节），我假设这就是你要搜索的。即使是一个良好调优/展开的wmemchr（又名indexOf），在4GHz的CPU上以每个时钟周期运行2x 32字节向量，也需要1250 us来执行10 k次重复（32000B / (64B/c) * 10000 reps / 4000 MHz），假设32 kB的字符串在32 KiB的L1 d缓存中保持热。
我希望JVM要么调用原生wmemchr，要么对String#indexOf这样的常用核心库函数使用同样高效的函数。例如，glibc's avx2 memchr在循环展开方面做了很好的调整。（Java字符串实际上是UTF-16，但Linux wchar_t上的C是4字节宽，这与Windows不同，因此JVM需要自己的实现。）

**内置String indexOf也是JIT“知道”的东西。**当它看到您重复使用相同的字符串作为输入时，它显然能够将其提升出循环。（但是它对剩下的7个我们做了什么呢？我猜做了一个不太好的memchr，然后在1/时钟可能需要大约7微秒，特别是如果你的CPU没有4GHz那么快。

参见Idiomatic way of performance evaluation?-如果将重复计数加倍到20 k并不能使时间加倍，则您的基准测试被破坏，并且没有测量您认为它所做的事情。

**但是你说每次迭代的时间是7 us？**这是不可能的慢，除非是非优化的第一遍。所以可能是错误的基准测试方法的标志，比如缺乏热身运行。

如果IndexOf一次检查一个字符，那么16k * 0.25 ns/char将需要4000纳秒，或者在4GHz CPU上需要4微秒。7 us在每个周期检查一个字符的范围内，这在现代x86上是非常慢的。我认为主流JVM在完成JIT优化后不太可能使用这样慢的实现。
您的手动SIMD indexOf不太可能在循环中得到优化。如果大小不是向量宽度的精确倍数，它每次都会复制整个数组！！（In ensureSize2）。通常的技术是对最后的size % width元素回退到标量，这对于大型数组显然要好得多。在数组的末尾（如果总大小〉= vectorwidth）执行一个非对齐加载，以避免与以前的工作重叠。
一个体面的memchr在现代x86（使用类似于您的indexOf的算法而不展开）应该在大约1个向量处进行（16/32/64字节），数据在L1 d缓存中处于热状态，没有循环展开或任何情况。（检查向量比较和指针边界作为可能的循环退出条件需要额外的asm指令，而不是简单的strlen。但请参阅一些假设对齐缓冲区的简单手写strlen的微基准测试的答案）。可能您的indexOf循环在像Skylake这样的CPU上的前端吞吐量瓶颈，其流水线宽度为4 uops/clock。
所以让我们猜猜你的实现需要1.5个周期每16字节向量，如果你在一个没有AVX 2的CPU上？
16 kB/16 B = 1000个矢量。每1.5个时钟周期1个矢量，即1500个周期。在3GHz机器上，1500个周期需要500 ns =每次调用0.5 us，或每10 k rep 5000 us。但由于16194字节不是16的倍数，因此每次调用都要复制整个内容，因此会花费更多时间。也能合理解释你7709美元的总时间。

SIMD有什么用

来完成这样的任务

**不，像ints.reduceLanes这样的“水平”东西通常是SIMD很慢的。**即使像How to implement atoi using SIMD?这样的东西使用x86 pmaddwd来水平地乘和加对，它仍然需要大量的工作。

请注意，要使元素足够宽，可以与位值相乘而不会溢出，必须进行解包，这需要进行一些重排。（元素）shuffle/add步骤，如果您从int的512位AVX-512向量开始，则这些shuffle中的前2个是跨车道的，3周期潜伏期（https://agner.org/optimize/）。（或者如果你的机器甚至没有AVX 2，那么一个512位的整数向量实际上是4 × 128位的向量。你必须单独做工作来解压缩每个部分。但至少减少的成本很低，只是垂直添加，直到你得到一个128位的向量。）

赞(0）回复(0）举报 2023-03-28

oaxa6hgo2#

这是我最初在2022年1月29日发布的关于这个主题的帖子的更新版本。我非常感谢@JimmyB和@rapaio指出其中的一些主要缺陷，并认为我现在已经解决了它们。此外，我可以比较Java 19和Java 20。*

我发现这篇文章是因为我觉得我在Vector性能上遇到了一些奇怪的东西，表面上它应该是两个双精度数组相乘的理想选择。更新后（在纠正错误后），主要例程是这样的（对于Vector的情况）：

static private void doVector(int iteration, double[] input1, double[] input2, double[] output) {
    long start = System.nanoTime();
    for (int i = 0; i < SPECIES.loopBound(ARRAY_LENGTH); i += SPECIES.length()) {
      DoubleVector va = DoubleVector.fromArray(SPECIES, input1, i);
      DoubleVector vb = DoubleVector.fromArray(SPECIES, input2, i);
      va.mul(vb).intoArray(output, i);
    }
    long finish = System.nanoTime();
    System.out.println("  vector (intoArray) duration (ns)\t" + iteration + "\t" + (finish - start));
  }

而这（对于标量的情况）：

static private void doScalar(int iteration, double[] input1, double[] input2, double[] output) {
    long start = System.nanoTime();
    for (int i = 0; i < ARRAY_LENGTH; ++i) {
      output[i] = input1[i] * input2[i];
    }
    long finish = System.nanoTime();
    System.out.println("  scalar duration (ns)\t" + iteration + "\t" + (finish - start));
  }

在测试中，我使用了一个长度为65536（随机数）的数组和1024次迭代。在我的机器上（CPU是2.8 GHz的Intel i7- 7700 HQ），物种长度为4。
时间需要一段时间才能稳定下来。首先，前2个标量和6个向量迭代比后面的迭代慢得多（大约10倍），其次，前180次左右的迭代在时间上非常不稳定。此后偶尔会出现尖峰（可能与机器/jvm上的其他事情有关）
如果我比较一下（使用中位数而不是平均值来避免离群值，并忽略前200次迭代以消除启动影响），在Java 19中，Vector方法比标量方法快大约8%，在Java 20中大约快9%。这意味着，我仍然没有看到“快四倍”。我想知道优化器是否正在分发标量计算……（或者这次我做错了什么：-））

赞(0）回复(0）举报 2023-03-28

我来回答

为什么java vector API比scalar慢？

2条答案

SIMD有什么用

相关问题

热门标签

最新问答