从Java字符串中剥离所有不可打印字符的最快方法

Question

从Java字符串中剥离所有不可打印字符的最快方法

javastringperformanceoptimizationmicro-optimization

85

什么是在Java中从字符串中剥离所有不可打印字符的最快方法？

到目前为止，我已经尝试并测量了一个138字节、131个字符的字符串：

replaceAll() 方法是 String 类中最慢的方法
- 每秒517009个结果
预编译 Pattern，然后使用 Matcher 的 replaceAll() 方法
- 每秒637836个结果
使用 StringBuffer，逐一获取代码点并附加到 StringBuffer 中，使用 codepointAt() 方法
- 每秒711946个结果
使用 StringBuffer，逐一获取字符并附加到 StringBuffer 中，使用 charAt() 方法
- 每秒1052964个结果
预分配一个 char[] 缓冲区，逐一获取字符并填充该缓冲区，然后将其转换回 String
- 每秒2022653个结果
预分配 2 个 char[] 缓冲区 - 旧的和新的，一次性使用 getChars() 方法获取现有字符串的所有字符，逐一迭代旧缓冲区并填充新缓冲区，然后将新缓冲区转换为 String - 我自己的最快版本
- 每秒2502502个结果
使用 2 个 byte[] 缓冲区进行相同的操作，但使用 getBytes() 方法，并将编码指定为 "utf-8"
- 每秒857485个结果
使用 2 个 byte[] 缓冲区进行相同的操作，但将编码指定为常量 Charset.forName("utf-8")
- 每秒791076个结果
使用 2 个 byte[] 缓冲区进行相同的操作，但将编码指定为 1 字节本地编码（几乎是不明智的做法）
- 每秒370164个结果

我最好的尝试如下：

    char[] oldChars = new char[s.length()];
    s.getChars(0, s.length(), oldChars, 0);
    char[] newChars = new char[s.length()];
    int newLen = 0;
    for (int j = 0; j < s.length(); j++) {
        char ch = oldChars[j];
        if (ch >= ' ') {
            newChars[newLen] = ch;
            newLen++;
        }
    }
    s = new String(newChars, 0, newLen);

有没有想法如何使它更快？

额外加分回答一个非常奇怪的问题：为什么直接使用“utf-8”字符集名称比使用预分配的静态常量Charset.forName("utf-8")性能更好？

更新

ratchet freak的建议取得了令人印象深刻的3105590个结果/秒的性能，提高了24%！
Ed Staub的建议又带来了进一步的改进——3471017个结果/秒，比之前最佳的结果提高了12%。

更新2

我尽力收集了所有提出的解决方案及其交叉变异，并将其发布为在github上提供的小型基准测试框架。目前它拥有17种算法。其中有一个是“特殊”的——Voo1算法（由SO用户Voo提供）采用复杂的反射技巧，从而实现了卓越的速度，但会破坏JVM字符串的状态，因此单独进行基准测试。

欢迎您查看并在您的计算机上运行它以确定结果。这是我在我的机器上得到的结果摘要。它的规格：

Debian sid
Linux 2.6.39-2-amd64 (x86_64)
已从软件包sun-java6-jdk-6.24-1安装Java，JVM标识为
- Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
- Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode)

不同的算法在给定不同的输入数据集时最终会产生不同的结果。我以三种模式运行了基准测试：

相同的单个字符串

此模式适用于由StringSource类提供的同一单个字符串作为常量。决斗是：

每秒操作数 │ 算法
──────────┼──────────────────────────────
6,535,947 │ Voo1
──────────┼──────────────────────────────
5,350,454 │ RatchetFreak2EdStaub1GreyCat1
5,249,343 │ EdStaub1
5,002,501 │ EdStaub1GreyCat1
4,859,086 │ ArrayOfCharFromStringCharAt
4,295,532 │ RatchetFreak1
4,045,307 │ ArrayOfCharFromArrayOfChar
2,790,178 │ RatchetFreak2EdStaub1GreyCat2
2,583,311 │ RatchetFreak2
1,274,859 │ StringBuilderChar
1,138,174 │ StringBuilderCodePoint
  994,727 │ ArrayOfByteUTF8String
  918,611 │ ArrayOfByteUTF8Const
  756,086 │ MatcherReplace
  598,945 │ StringReplaceAll
  460,045 │ ArrayOfByteWindows1251

以图表形式呈现:
_{(来源: greycat.ru)}

多个字符串，100%的字符串包含控制字符

源字符串提供程序使用(0..127)字符集预先生成了大量随机字符串，因此几乎所有字符串都包含至少一个控制字符。算法以轮流方式从这个预生成的数组中接收字符串。

 每秒操作数 │ 算法
──────────┼──────────────────────────────
2 123 142 │ Voo1
──────────┼──────────────────────────────
1 782 214 │ EdStaub1
1 776 199 │ EdStaub1GreyCat1
1 694 628 │ ArrayOfCharFromStringCharAt
1 481 481 │ ArrayOfCharFromArrayOfChar
1 460 067 │ RatchetFreak2EdStaub1GreyCat1
1 438 435 │ RatchetFreak2EdStaub1GreyCat2
1 366 494 │ RatchetFreak2
1 349 710 │ RatchetFreak1
  893 176 │ ArrayOfByteUTF8String
  817 127 │ ArrayOfByteUTF8Const
  778 089 │ StringBuilderChar
  734 754 │ StringBuilderCodePoint
  377 829 │ ArrayOfByteWindows1251
  224 140 │ MatcherReplace
  211 104 │ StringReplaceAll

以图表形式呈现:
_{(来源: greycat.ru)}

多个字符串，1%的字符串包含控制字符

与之前相同，但只有1％的字符串是使用控制字符生成的 - 其他99％是使用[32..127]字符集生成的，因此它们根本不包含控制字符。这种合成负载最接近我所在地区此算法的真实应用。

按图表形式呈现：

_{（来源：greycat.ru）}

对于我来说很难决定谁提供了最好的答案，但考虑到实际应用场景，Ed Staub提供/启发的解决方案是最好的，我想标记他的答案是公平的。感谢所有参与其中的人，你们的意见非常有帮助和宝贵。请随意在您的计算机上运行测试套件并提出更好的解决方案（任何工作JNI解决方案？）。

参考资料

GitHub存储库带有基准测试套件

- GreyCat

23

这个问题表明了研究的努力。嗯...好吧，过了。+1 - Gustav Barkefors

7

因为StringBuilder是非同步的，所以它比StringBuffer略快。我提到这一点是因为你标记了这个为“微优化”。 - user177800

2

@Jarrod Roberson：好的，那么让我们把所有只读字段都设为final，并且也将s.length()从for循环中提取出来 :-) - home

3

空格以下的一些字符是可打印的，例如\t和\n。你字符集中127以上的许多字符是不可打印的。 - Peter Lawrey

1

你是否使用s.length()作为字符串缓冲区的容量进行初始化？ - ratchet freak

显示剩余8条评论

8个回答

11

如果将这个方法嵌入到不跨线程共享的类中是合理的，那么您可以重用缓冲区：

char [] oldChars = new char[5];

String stripControlChars(String s)
{
    final int inputLen = s.length();
    if ( oldChars.length < inputLen )
    {
        oldChars = new char[inputLen];
    }
    s.getChars(0, inputLen, oldChars, 0);

这是一次大的胜利——大约20%左右，就我现在了解到的最佳情况而言。

如果要用于可能很大的字符串，并且内存“泄漏”是一个问题，可以使用弱引用。

- Ed Staub

太棒了！到目前为止，它将计数提高到每秒3471017个字符串 - 即比之前最好的版本提高了12％。 - GreyCat

11

根据我的测量结果，我已经比当前最佳方法（freak 的预分配数组解决方案）提高了约30％。怎么做到的？出卖灵魂。

我相信每个跟进这个讨论的人都知道这违反了基本的编程原则，但是没关系。无论如何，以下内容仅在使用的字符串的字符数组不在其他字符串之间共享时才有效 - 如果共享了字符数组，那么调试此问题的人将有权决定杀死您（如果没有调用substring()并且在文字字符串上使用它，这应该可以正常工作，因为我不认为JVM会联合来自外部源的唯一字符串）。虽然不要忘记确保基准代码不会这样做 - 这极有可能会帮助反射解决方案。

总之，我们开始吧：

    // Has to be done only once - so cache those! Prohibitively expensive otherwise
    private Field value;
    private Field offset;
    private Field count;
    private Field hash;
    {
        try {
            value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            offset = String.class.getDeclaredField("offset");
            offset.setAccessible(true);
            count = String.class.getDeclaredField("count");
            count.setAccessible(true);
            hash = String.class.getDeclaredField("hash");
            hash.setAccessible(true);               
        }
        catch (NoSuchFieldException e) {
            throw new RuntimeException();
        }

    }

    @Override
    public String strip(final String old) {
        final int length = old.length();
        char[] chars = null;
        int off = 0;
        try {
            chars = (char[]) value.get(old);
            off = offset.getInt(old);
        }
        catch(IllegalArgumentException e) {
            throw new RuntimeException(e);
        }
        catch(IllegalAccessException e) {
            throw new RuntimeException(e);
        }
        int newLen = off;
        for(int j = off; j < off + length; j++) {
            final char ch = chars[j];
            if (ch >= ' ') {
                chars[newLen] = ch;
                newLen++;
            }
        }
        if (newLen - off != length) {
            // We changed the internal state of the string, so at least
            // be friendly enough to correct it.
            try {
                count.setInt(old, newLen - off);
                // Have to recompute hash later on
                hash.setInt(old, 0);
            }
            catch(IllegalArgumentException e) {
                e.printStackTrace();
            }
            catch(IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        // Well we have to return something
        return old;
    }

我进行了测试，结果显示新版本的运行速度为3477148.18ops/s，而旧版本的运行速度为2616120.89ops/s。我相信唯一能够超越这个速度的方式可能是使用C语言编写（虽然可能不是），或者采用目前没有人想到的全新方法。但我并不确定在不同平台上的计时是否稳定——至少在我的电脑上（Java7，Win7 x64）可以产生可靠的结果。

- Voo

感谢您提供的解决方案，请查看问题更新 - 我已经发布了我的测试框架，并添加了17个算法的3个测试运行结果。您的算法始终位于顶部，但它更改了Java字符串的内部状态，从而破坏了“不可变字符串”的约定=>在实际应用中使用它将非常困难。就测试而言，是最佳结果，但我想我会将其作为单独的提名公布 :) - GreyCat

3

@GreyCat 是的，它肯定有一些大的限制条件，老实说我几乎只是写了它，因为我相信目前没有明显的方法可以进一步改进你目前的最佳解决方案。在某些情况下，我确信它会很好地工作（在剥离之前没有子字符串或intern调用），但这是因为我了解当前Hotspot版本的知识（即据我所知，它不会将从IO读取的字符串intern - 不会特别有用）。如果确实需要那些额外的x％，它可能会有用，但否则更多是一个基线，以查看您仍然可以改进多少;) - Voo

1

虽然我想尝试JNI版本，如果我有时间的话——到目前为止从未使用过，所以这会很有趣。但我相当确定它会更慢，因为额外的调用开销（字符串太小了）和JIT不应该在优化函数方面遇到太大问题。只是在你的字符串没有改变的情况下不要使用new String()，但我认为你已经知道了。 - Voo

我已经尝试过在纯C中做完全相同的事情，但实际上它并没有比基于反射的版本表现得更好。C版本运行速度大约快了5到10％，并不是很出色 - 我以为至少会像1.5x-1.7x那样快... - GreyCat

2

您可以根据处理器的数量将任务拆分为几个并行子任务。

- umbr

是的，我也考虑过，但在我的情况下它不会带来任何性能提升——这个剥离算法已经在一个大规模并行的系统中被调用。 - GreyCat

2

而且，我猜想为每个50-100字节的字符串分叉出几个线程进行处理可能会是一个巨大的过度设计。 - GreyCat

是的，为每个小字符串分叉线程不是一个好主意。但负载均衡器可以提高性能。顺便说一下，您是否使用StringBuilder进行了性能测试？它比StringBuffer具有更好的性能，因为它是非同步的。 - umbr

我的生产环境会启动多个独立的进程，并尽可能利用并行CPU和核心，因此我可以自由地在任何地方使用StringBuilder而不会出现任何问题。 - GreyCat

2

我很空闲，写了一个有关不同算法的小型基准测试。这并不完美，但我对给定算法进行1000次运行的最小值进行了10000次重复，使用随机字符串（默认情况下大约有32/200％的非打印字符）。这应该能够处理GC，初始化等问题-没有太多开销，任何算法都应该至少有一次无阻碍的运行。

文档不是特别完善，但没关系。在此处（点击链接）中，我包含了ratchet freak的两个算法和基本版本。目前，我随机初始化一个长度为200个字符的字符串，并在范围[0,200)内均匀分布的字符中选择。

- Voo

+1 鼓励你的努力，但是你应该问问我，我已经有一个类似的基准测试套件了，那里是我测试算法的地方 ;) - GreyCat

@GreyCat 嗯，我本来可以的，但是把它（无论如何都是现有代码）拼凑在一起可能更快一些 ;) - Voo

1

它可以变得更快。更快^*。如何实现？通过利用System.arraycopy这个本地方法。所以，总结一下：

Return the same String if it's "clean".
Avoid allocating a new char[] on every iteration

Use System.arraycopy for moving the elements x positions back

  public class SteliosAdamantidis implements StripAlgorithm {

      private char[] copy = new char[128];

      @Override
      public String strip(String s) throws Exception {
          int length = s.length();
          if (length > copy.length) {
              int newLength = copy.length * 2;
              while (length > newLength) newLength *= 2;
              copy = new char[newLength];
          }

          s.getChars(0, length, copy, 0);

          int start = 0;  //where to start copying from
          int offset = 0; //number of non printable characters or how far
                          //behind the characters should be copied to

          int index = 0;
          //fast forward to the first non printable character
          for (; index < length; ++index) {
              if (copy[index] < ' ') {
                  start = index;
                  break;
              }
          }

          //string is already clean
          if (index == length) return s;

          for (; index < length; ++index) {
              if (copy[index] < ' ') {
                  if (start != index) {
                      System.arraycopy(copy, start, copy, start - offset, index - start);
                  }
                  ++offset;
                  start = index + 1; //handling subsequent non printable characters
              }
          }

          if (length != start) {
              //copy the residue -if any
              System.arraycopy(copy, start, copy, start - offset, length - start);
          }
          return new String(copy, 0, length - offset);
      }
  }

这个类不是线程安全的，但我猜如果有人想在单独的线程上处理大量的字符串，那么他们可以在ThreadLocal<>中使用4-8个StripAlgorithm实现的实例。

趣闻

I used as reference the RatchetFreak2EdStaub1GreyCat2 solution. I was surprised that this wasn't performing any good on my machine. Then I wrongfully thought that the "bailout" mechanism didn't work and I moved it at the end. It skyrocketed performance. Then I though "wait a minute" and I realized that the condition works always it's just better at the end. I don't know why.
```
 ...
 6. RatchetFreak2EdStaub1GreyCatEarlyBail   3508771.93   3.54x   +3.9%
 ...
 2. RatchetFreak2EdStaub1GreyCatLateBail    6060606.06   6.12x   +13.9%
```
The test is not 100% accurate. At first I was an egoist and I've put my test second on the array of algorithms. It had some lousy results on the first run and then I moved it at the end (let the others warm up the JVM for me :) ) and then it came first.

结果

当然，还有结果。在一台相对较旧的机器上使用Windows 7和jdk1.8.0_111，因此在新硬件和/或操作系统上可能会得到不同的结果。

    Rankings: (1.000.000 strings)
    17. StringReplaceAll                        990099.01   1.00x   +0.0%
    16. ArrayOfByteWindows1251                  1642036.12  1.66x   +65.8%
    15. StringBuilderCodePoint                  1724137.93  1.74x   +5.0%
    14. ArrayOfByteUTF8Const                    2487562.19  2.51x   +44.3%
    13. StringBuilderChar                       2531645.57  2.56x   +1.8%
    12. ArrayOfByteUTF8String                   2551020.41  2.58x   +0.8%
    11. ArrayOfCharFromArrayOfChar              2824858.76  2.85x   +10.7%
    10. RatchetFreak2                           2923976.61  2.95x   +3.5%
     9. RatchetFreak1                           3076923.08  3.11x   +5.2%
     8. ArrayOfCharFromStringCharAt             3322259.14  3.36x   +8.0%
     7. EdStaub1                                3378378.38  3.41x   +1.7%
     6. RatchetFreak2EdStaub1GreyCatEarlyBail   3508771.93  3.54x   +3.9%
     5. EdStaub1GreyCat1                        3787878.79  3.83x   +8.0%
     4. MatcherReplace                          4716981.13  4.76x   +24.5%
     3. RatchetFreak2EdStaub1GreyCat1           5319148.94  5.37x   +12.8%
     2. RatchetFreak2EdStaub1GreyCatLateBail    6060606.06  6.12x   +13.9%
     1. SteliosAdamantidis                      9615384.62  9.71x   +58.7%

    Rankings: (10.000.000 strings)
    17. ArrayOfByteWindows1251                  1647175.09  1.00x   +0.0%
    16. StringBuilderCodePoint                  1728907.33  1.05x   +5.0%
    15. StringBuilderChar                       2480158.73  1.51x   +43.5%
    14. ArrayOfByteUTF8Const                    2498126.41  1.52x   +0.7%
    13. ArrayOfByteUTF8String                   2591344.91  1.57x   +3.7%
    12. StringReplaceAll                        2626740.22  1.59x   +1.4%
    11. ArrayOfCharFromArrayOfChar              2810567.73  1.71x   +7.0%
    10. RatchetFreak2                           2948113.21  1.79x   +4.9%
     9. RatchetFreak1                           3120124.80  1.89x   +5.8%
     8. ArrayOfCharFromStringCharAt             3306878.31  2.01x   +6.0%
     7. EdStaub1                                3399048.27  2.06x   +2.8%
     6. RatchetFreak2EdStaub1GreyCatEarlyBail   3494060.10  2.12x   +2.8%
     5. EdStaub1GreyCat1                        3818251.24  2.32x   +9.3%
     4. MatcherReplace                          4899559.04  2.97x   +28.3%
     3. RatchetFreak2EdStaub1GreyCat1           5302226.94  3.22x   +8.2%
     2. RatchetFreak2EdStaub1GreyCatLateBail    5924170.62  3.60x   +11.7%
     1. SteliosAdamantidis                      9680542.11  5.88x   +63.4%

* 反射 - Voo的回答

我在“要快得多”的语句上打了一个星号。我认为在这种情况下，没有什么能比反射更快了。它改变了String的内部状态，避免了新的String分配。我不认为有人能够超越它。

我尝试取消注释并运行Voo的算法，但出现了一个错误，即“offset”字段不存在。IntelliJ还抱怨无法解析“count”。此外（如果我没有弄错），安全管理器可能会削减对私有字段的反射访问，因此此解决方案将无法工作。这就是为什么这个算法没有出现在我的测试运行中的原因。否则，我很好奇自己看一眼，尽管我相信非反射性的解决方案无法更快。

- Stelios Adamantidis

避免重复分配tmp buf的另一种选择是让调用者传递（通过引用）足够大小的临时缓冲区。您必须检查是否会破坏某些优化，但希望JVM可以确定String和tmp buf不是同一个对象，仅仅因为它们的类型不同。这不像一个接受两个char *参数的C函数。（如果JVM甚至进行任何有意义的优化；不幸的是，它可能不会使用SIMD来扫描不是`> ='的字符。' '，字符。） - Peter Cordes

你提到了“晚期保释” - 你是指 https://github.com/GreyCat/java-string-benchmark/blob/master/src/ru/greycat/algorithms/strip/RatchetFreak2EdStaub1GreyCat2.java 中的 if (newLen == length) return s; 检查吗？你是在说把它放在 for (j 循环之后吗？也许这有助于JIT看到，如果该循环条件第一次为false，则应跳转到执行 return s; 的代码，否则进入循环。惊讶的是，仅仅不检查相同的条件就能产生如此大的差异，但也许它以某种方式使JIT做得更糟糕。 - Peter Cordes

@PeterCordes 我们在聊天室里讨论吧 :) - Stelios Adamantidis

@PeterCordes 我理解你的意思，也许 copy[idx] = c; 会进行更多检查以确保 arraycopy 没有出错？说实话，我并不知道所有问题的答案 :) （尽管有时我很想知道）。但这可能是进一步调查的好机会（如果有时间的话:( ) - Stelios Adamantidis

是的，就像我之前说的那样，我的两个主要理论是每个字节都进行边界检查（而不仅仅是每个ArrayCopy检查一次）在汇编中的成本很高，或者根本不进行存储会破坏其他优化，例如不保留所有循环变量在寄存器中。例如，编译器不能再证明许多循环不变式，因为它认为存储可能会更改某些变量的某个部分的值。（确定存储何时可以/不能影响其他内容称为“别名分析”）。只读循环使别名分析变得微不足道/不必要。 - Peter Cordes

显示剩余6条评论

1

我是一名低级别的 Java 性能狂热者，但你尝试过展开你的主循环吗？这似乎可以让某些 CPU 并行执行检查。

此外，这里有一些有趣的优化想法。

- Ryan Ransford

我怀疑这里无法进行任何展开，因为(a)算法后续步骤依赖于先前步骤，(b)我甚至没有听说过有人在Java中手动展开循环并产生出色的结果；JIT通常会很好地展开它认为适合任务的内容。不过还是感谢您的建议和链接 :) - GreyCat

0

为什么直接使用“utf-8”字符集名称比使用预分配的静态常量Charset.forName("utf-8")性能更好？

如果您指的是String#getBytes("utf-8")等：这不应该更快 - 除了一些更好的缓存之外 - 因为如果字符集未被缓存，内部会使用Charset.forName("utf-8")。

可能有一件事是您正在使用不同的字符集（或者您的某些代码在透明地使用），但在StringCoding中缓存的字符集不会改变。

- Thomas

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ratchet freak · Accepted Answer

使用一个字符数组可能会更好一些。

int length = s.length();
char[] oldChars = new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

我避免了对s.length();的重复调用。

另一个可能有效的微小优化是

int length = s.length();
char[] oldChars = new char[length+1];
s.getChars(0, length, oldChars, 0);
oldChars[length]='\0';//avoiding explicit bound check in while
int newLen=-1;
while(oldChars[++newLen]>=' ');//find first non-printable,
                       // if there are none it ends on the null char I appended
for (int  j = newLen; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;//the while avoids repeated overwriting here when newLen==j
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);