草庐IT

Java 2D 数组填充 - 无辜的优化导致严重的减速

coder 2023-05-17 原文

我尝试通过计算两个元素的每个总和一次来优化二维 Java 数组的填充，每个元素的索引总和与主对角线相反。但是，我的代码并没有提高速度，或者至少没有可比的性能，而是 23(!) 倍。

我的代码:

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(ArrayFill.N * ArrayFill.N)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class ArrayFill {
    public static final int N = 8189;
    public int[][] g;

    @Setup
    public void setup() { g = new int[N][N]; }

    @GenerateMicroBenchmark
    public int simple(ArrayFill state) {
        int[][] g = state.g;
        for(int i = 0; i < g.length; i++) {
            for(int j = 0; j < g[i].length; j++) {
                g[i][j] = i + j;
            }
        }
        return g[g.length - 1][g[g.length - 1].length - 1];
    }

    @GenerateMicroBenchmark
    public int optimized(ArrayFill state) {
        int[][] g = state.g;
        for(int i = 0; i < g.length; i++) {
            for(int j = 0; j <= i; j++) {
                g[j][i] = g[i][j] = i + j;
            }
        }
        return g[g.length - 1][g[g.length - 1].length - 1];
    }
}

基准测试结果:

Benchmark               Mode     Mean   Mean error    Units
ArrayFill.simple        avgt    0.907        0.008    ns/op
ArrayFill.optimized     avgt   21.188        0.049    ns/op


问题:
如何解释如此巨大的性能下降？

P. S. Java 版本为 1.8.0-ea-b124，64 位 3.2 GHz AMD 处理器，基准测试在单线程中执行。

最佳答案

附注:您的“优化”版本可能根本不会更快，即使我们将所有可能的问题放在一边。现代 CPU 中有多种资源，饱和其中之一可能会阻止您进行任何改进。我的意思是:速度可能受内存限制，并且尝试在一次迭代中以两倍的速度写入可能根本不会改变任何事情。

我可以看到三个可能的原因:

  • 您的访问模式可能会强制执行绑定(bind)检查。在“简单”循环中，它们显然可以被消除，在“优化”中，只有当数组是正方形时。确实如此，但此信息仅在方法之外可用(此外，另一段代码可能会更改它!)。

  • “优化”循环中的内存位置很糟糕。它访问本质上是随机内存位置，因为在 Java 中没有像二维数组那样的东西(只有一个数组数组，new int[N][N] 是一个快捷方式)。 当逐列迭代时，您只使用每个加载的缓存行中的一个 int，即 64 个字节中的 4 个字节。

  • 内存预取器 可能与您的访问模式有问题。具有 8189 * 8189 * 4 字节的数组太大而无法放入任何缓存中。现代 CPU 有一个预取器，允许在发现常规访问模式时提前加载缓存行。预取器的功能差异很大。这在这里可能无关紧要，因为您只是在写，但我不确定是否可以写入尚未获取的缓存行。

我猜内存位置是罪魁祸首:

我添加了一个“反向”方法，它的工作原理很简单，但使用

g[j][i] = i + j;

而不是

g[i][j] = i + j;

这种“无害”的变化是一场性能灾难:

Benchmark                                Mode   Samples         Mean   Mean error    Units
o.o.j.s.ArrayFillBenchmark.optimized     avgt        20       10.484        0.048    ns/op
o.o.j.s.ArrayFillBenchmark.reversed      avgt        20       20.989        0.294    ns/op
o.o.j.s.ArrayFillBenchmark.simple        avgt        20        0.693        0.003    ns/op

关于Java 2D 数组填充 - 无辜的优化导致严重的减速，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21639405/

减速严重strongcodelengthjavaarraysperformancemultidimensional-arraybenchmarking

有关Java 2D 数组填充 - 无辜的优化导致严重的减速的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  3. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  4. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  5. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  6. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  7. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  8. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  9. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

  10. ruby - 匹配大写字母并用后续字母填充，直到一定的字符串长度 - 2

    我有一个驼峰式字符串，例如:JustAString。我想按照以下规则形成长度为4的字符串:抓取所有大写字母；如果超过4个大写字母，只保留前4个；如果少于4个大写字母，则将最后大写字母后的字母大写并添加字母，直到长度变为4。以下是可能发生的3种情况:ThisIsMyString将产生TIMS(大写字母)；ThisIsOneVeryLongString将产生TIOV(前4个大写字母)；MyString将生成MSTR(大写字母+tr大写)。我设法用这个片段解决了前两种情况:str.scan(/[A-Z]/).first(4).join但是，我不太确定如何最好地修改上面的代码片段以处理最后一种

随机推荐