Gre*_*Cat 80 java string optimization performance micro-optimization
从StringJava中删除所有不可打印字符的最快方法是什么？
到目前为止,我已经尝试并测量了138字节,131个字符的字符串:
replaceAll()- 最慢的方法
replaceAll()
codepointAt()逐个获取代码点并附加到StringBuffer
charAt()逐个获取字符并附加到StringBuffer
char[]缓冲区,charAt()逐个获取字符并填充此缓冲区,然后转换回String
char[]缓冲区 - 旧的和新的,一次获取现有String的所有字符,getChars()逐个迭代旧缓冲区并填充新缓冲区,然后将新缓冲区转换为String - 我自己的最快版本
byte[],getBytes()并指定编码为"utf-8"
byte[]缓冲区的相同内容,但将编码指定为常量Charset.forName("utf-8")
byte[]缓冲区相同的东西,但指定编码为1字节本地编码(几乎没有理智的事情要做)
我最好的尝试如下:
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"字符集名称会比使用预先分配的静态const产生更好的性能Charset.forName("utf-8")？
我已尽力收集所有提议的解决方案及其交叉突变,并将其作为github的小型基准框架发布.目前它运动17种算法.其中一个是"特殊的" - Voo1算法(由SO用户Voo提供)采用复杂的反射技巧,从而实现了恒星速度,但它混淆了JVM字符串的状态,因此它是单独进行基准测试的.
欢迎您查看并运行它以确定您的盒子上的结果.这是我对我的结果的总结.它的规格如下:
sun-java6-jdk-6.24-1,JVM将自己标识为
给定不同的输入数据集,不同的算法最终显示出不同的结果.我在3种模式下运行了基准测试:
此模式适用于由StringSource类提供的相同单个字符串作为常量.摊牌是:
Ops / s ? Algorithm ????????????????????????????????????????? 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
以图表形式: 相同的单个字符串图表http://www.greycat.ru/img/os-chart-single.png
源字符串提供程序使用(0..127)字符集预先生成大量随机字符串 - 因此几乎所有字符串都包含至少一个控制字符.算法以循环方式从此预生成的数组接收字符串.
Ops / s ? Algorithm ????????????????????????????????????????? 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
以图表形式: 多个字符串,100%浓度http://www.greycat.ru/img/os-chart-multi100.png
与之前相同,但只有1%的字符串是使用控制字符生成的 - 其他99%是使用[32..127]字符集生成的,因此它们根本不能包含控制字符.这个合成负载在我的位置最接近这个算法的实际应用.
Ops / s ? Algorithm ????????????????????????????????????????? 3 711 952 ? Voo1 ????????????????????????????????????????? 2 851 440 ? EdStaub1GreyCat1 2 455 796 ? EdStaub1 2 426 007 ? ArrayOfCharFromStringCharAt 2 347 969 ? RatchetFreak2EdStaub1GreyCat2 2 242 152 ? RatchetFreak1 2 171 553 ? ArrayOfCharFromArrayOfChar 1 922 707 ? RatchetFreak2EdStaub1GreyCat1 1 857 010 ? RatchetFreak2 1 023 751 ? ArrayOfByteUTF8String 939 055 ? StringBuilderChar 907 194 ? ArrayOfByteUTF8Const 841 963 ? StringBuilderCodePoint 606 465 ? MatcherReplace 501 555 ? StringReplaceAll 381 185 ? ArrayOfByteWindows1251
以图表形式: 多个字符串,1%浓度http://www.greycat.ru/img/os-chart-multi1.png
我很难决定谁提供了最好的答案,但鉴于现实世界的应用程序最好的解决方案是由Ed Staub给出/启发的,我想我的答案是公平的.感谢所有参与此活动的人,您的意见非常有帮助且非常宝贵.随意在您的盒子上运行测试套件并提出更好的解决方案(工作JNI解决方案,任何人？).
rat*_*eak 25
使用1个char数组可以更好地工作
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);
Ed *_*aub 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%左右,因为我理解当前最好的情况.
如果要在潜在的大字符串上使用它并且内存"泄漏"是一个问题,可以使用弱引用.
Voo*_*Voo 11
根据我的措施,我已经击败了当前最好的方法(使用预分配阵列的怪胎解决方案)大约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;
}
对于我的TestString是获取3477148.18ops/s与2616120.89ops/s旧的变体.我很确定唯一的方法就是用C语言编写它(可能不是)或者到目前为止没有人想过的完全不同的方法.虽然我绝对不确定不同平台的时序是否稳定 - 至少在我的盒子(Java7,Win7 x64)上产生可靠的结果.