如何更快地在 byte[] 中搜索字节?

Question

我在输入流中做简单的行号计算(换行符 #10 的计算数(

for (int i = 0; i < readBytes ; i++) {
if ( b[ i + off ] == 10 ) {                     // New Line (10)
rowCount++;
}
}

我可以做得更快吗？没有一个字节的迭代？ 可能我正在寻找一些能够使用 CPU 特定指令 (simd/sse( 的类。

所有代码：

@Override
public int read(byte[] b, int off, int len) throws IOException {
int readBytes = in.read(b, off, len);
for (int i = 0; i < readBytes ; i++) {
hadBytes = true;                                // at least once we read something
lastByteIsNewLine = false;
if ( b[ i + off ] == 10 ) {                     // New Line (10)
rowCount++;
lastByteIsNewLine = (i == readBytes - 1);   // last byte in buffer was the newline
}
}
if ( hadBytes && readBytes == -1 && ! lastByteIsNewLine ) {   // file is not empty + EOF + last byte was not NewLine
rowCount++;
}
return readBytes;
}

Answer 1

在我的系统上，只需将lastByteIsNewLine和hasBytes部分移出循环即可带来~10%的改进*：

public int read(byte[] b, int off, int len) throws IOException {
int readBytes = in.read(b, off, len);
for (int i = 0; i < readBytes ; i++) {
if ( b[ i + off ] == 10 ) {
rowCount++;
}
}
hadBytes |= readBytes > 0;
lastByteIsNewLine = (readBytes > 0 ? b[readBytes+off-1] == 10 : false);
if ( hadBytes && readBytes == -1 && ! lastByteIsNewLine ) { 
rowCount++;
}
return readBytes;
}

* 6000 毫秒与 6700 毫秒，在 10MB 缓冲区上从填充任意文本的 ByteArrayInputStream 读取的 1,000 次迭代。

Answer 2

我从另一个人的改进开始，并将数组索引计算和字段访问提升到for循环之外。

根据我的JMH基准测试，这又节省了25%，"那个人"的实现时钟为3.6 ms/op，而这个版本为2.7 ms/opByteArrayInputStream。

public int read(byte[] buffer, int off, int len) throws IOException {
int n = in.read(buffer, off, len);
notEmpty |= n > 0;
int count = notEmpty && n < 0 && !trailingLineFeed ? 1 : 0;
trailingLineFeed = (n > 0) && buffer[n + off - 1] == 'n';
for (int max = off + n, idx = off; idx < max;) {
if (buffer[idx++] == 'n') ++count;
}
rowCount += count;
return n;
}

真正损害性能的事情：在阵列上向后索引。

无关紧要的事情：将值与更具可读性的""而不是 10 进行比较。

令人惊讶的是(无论如何对我来说(，仅使用这些技巧之一本身似乎并没有提高性能。它们只是一起使用才能有所作为。

Answer 3

在字符串中转换后，您可以轻松地在readBytes中搜索：

String stringBytes = new String(readBytes);

要获取出现次数，请执行以下操作：

int rowCount = StringUtils.countMatches(stringBytes, "n");

要仅知道n是否包含在readBytes中：

boolean newLineFound = stringBytes.contains("n");

Answer 4

好吧，与其尝试加快某个特定部分的速度(我认为您不能(，不如尝试使用不同的方法。这是一个类，可用于在从输入流读取时跟踪行数。

public class RowCounter {
private static final int LF = 10;
private int rowCount = 0;
private int lastByte = 0;
public int getRowCount() {
return rowCount;
}
public void addByte(int b) {
if (lastByte == LF) {
rowCount++;
}
lastByte = b;
}
public void addBytes(byte[] b, int offset, int length) {
if (length <= 0) return;
if (lastByte == LF) rowCount++;
int lastIndex = offset + length - 1;
for (int i = offset; i < lastIndex; i++) {
if (b[i] == LF) rowCount++;
}
lastByte = b[lastIndex];
}
}

然后在读取输入流时，您可以像这样使用它。

InputStream is = ...;
byte[] b = new byte[...];
int bytesRead;
RowCounter counter = new RowCounter();
while ((bytesRead = is.read(b)) != -1) {
counter.addBytes(b, 0, bytesRead);
}
int rowCount = counter.getRowCount();

或者，您可以轻松地将其适应您需要的任何情况。