If your representation allows for it, iterating over 64-bit longs packing 8 bytes each will be faster than iterating per byte. If you need to convert to this representation from your byte array (perhaps using ByteBuffer), the conversion cost may outweigh any performance benefit. Measure this for your specific scenario. Since your ID array is actually 20 bytes, even having 5x 32-bit integers or a mix of int and long could work.
Replace your inner bit-twiddling loop with a call to the built-in numberOfLeadingZeros. This will be simple and fast. If you absolutely need to sacrifice legibility and simplicity in the name of speed, there are faster, more complicated methods.
In my tests, there is a slight performance improvement to using numberOfLeadingZeros; its biggest benefit is simplicity. Packing is much more effectual in reducing execution time. If I had to pick a favourite, it would be the 5x 32-bit int version for its uniformity of representation and execution efficiency.
Timing fixture
import java.nio.ByteBuffer;
import java.nio.IntBuffer;
import java.util.Arrays;
import java.util.HexFormat;
import java.util.List;
import java.util.HashMap;
import java.util.Map;
import static java.lang.System.nanoTime;
import static java.lang.System.out;
public class Main {
private static final IdParser[] parsers = {
new IntLongParser(),
new BuiltinIntParser(),
new BuiltinBytesParser(),
new OldBytesParser(),
};
private static abstract class IdParser {
private static final HexFormat format = HexFormat.of();
public ID parse(String str) {
ByteBuffer buf = ByteBuffer.wrap(format.parseHex(str));
return construct(buf);
}
protected abstract ID construct(ByteBuffer buf);
}
private static class OldBytesParser extends IdParser {
protected ID construct(ByteBuffer buf) {
return new OldBytesID(buf.array());
}
}
private static class BuiltinBytesParser extends IdParser {
protected ID construct(ByteBuffer buf) {
return new BuiltinBytesID(buf.array());
}
}
private static class BuiltinIntParser extends IdParser {
protected ID construct(ByteBuffer buf) {
IntBuffer ibuf = buf.asIntBuffer();
int[] array = new int[ibuf.capacity()];
ibuf.get(array);
return new BuiltinIntID(array);
}
}
private static class IntLongParser extends IdParser {
protected ID construct(ByteBuffer buf) {
IntLongID id = new IntLongID(
buf.getLong(),
buf.getLong(),
buf.getInt()
);
if (buf.hasRemaining())
throw new RuntimeException("Unexpected data while parsing ID");
return id;
}
}
private static abstract class ID {
public abstract int prefixLen();
}
private static class OldBytesID extends ID {
private final byte[] id;
public OldBytesID(byte[] id) { this.id = id; }
public int prefixLen() {
int prefixLength = 0;
for (byte b: id) {
if (b == 0) {
prefixLength += 8; // 1 byte = 8 bits
} else {
int tmp = 0;
for (int i = 7; i >= 0; i--) {
if ((b & (1 << i)) == 0) {
tmp++;
} else {
break;
}
}
prefixLength += tmp;
}
}
return prefixLength;
}
}
private static class BuiltinBytesID extends ID {
private final byte[] id;
public BuiltinBytesID(byte[] id) { this.id = id; }
public int prefixLen() {
int prefix = 0;
for (byte b: id) {
if (b == 0)
prefix += 8;
else
return prefix + Integer.numberOfLeadingZeros(b << 24);
}
return prefix;
}
}
private static class BuiltinIntID extends ID {
private final int[] id;
public BuiltinIntID(int[] id) { this.id = id; }
public int prefixLen() {
int prefix = 0;
for (int i: id) {
if (i == 0)
prefix += 32;
else
return prefix + Integer.numberOfLeadingZeros(i);
}
return prefix;
}
}
private static class IntLongID extends ID {
private final long l1, l2;
private final int i3;
public IntLongID(long l1, long l2, int i3) {
this.l1 = l1; this.l2 = l2; this.i3 = i3;
}
public int prefixLen() {
if (l1 != 0)
return Long.numberOfLeadingZeros(l1);
if (l2 != 0)
return Long.numberOfLeadingZeros(l2) + 64;
return Integer.numberOfLeadingZeros(i3) + 128;
}
}
public static void main(String[] args) {
List<ID> ids = Arrays.stream(parsers)
.map(p -> p.parse(args[0]))
.toList();
// We need to stripe the time trials, because the first few iterations are
// slower while the CPU spins up and/or the OS thread scheduler allocates
// more time.
final int stripeSize = 1_000, iterations = 10_000;
Map<String, Double> times = new HashMap<>();
for (ID id: ids)
times.put(id.getClass().getSimpleName(), 0d);
// Save (even though we overwrite) the prefix results, to prevent the
// inner operation from being optimised away.
Map<String, Long> prefixes = new HashMap<>();
for (int i = 0; i < iterations; i++) {
for (ID id: ids) {
String name = id.getClass().getSimpleName();
Result result = timePrefix(id, stripeSize);
times.put(name, times.get(name) + result.time);
prefixes.put(name, result.prefix);
}
}
for (Map.Entry<String, Long> kv: prefixes.entrySet()) {
out.printf(
"%20s: prefix=%d time=%.1f ns%n",
kv.getKey(), kv.getValue(),
times.get(kv.getKey()) / iterations);
}
}
private record Result(long prefix, double time) { }
private static Result timePrefix(ID id, int stripeSize) {
long prefix = 0;
long start = nanoTime();
for (int i = 0; i < stripeSize; i++)
prefix += id.prefixLen();
double dur = ((double)(nanoTime() - start))/stripeSize;
return new Result(prefix/stripeSize, dur);
}
}
Output
When this is passed:
0000000000000000000000000000000000000002
i.e. an almost-worst-case two bits short of being empty, we get:
IntLongID: prefix=158 time=13.4 ns
BuiltinIntID: prefix=158 time=19.4 ns
BuiltinBytesID: prefix=158 time=37.1 ns
OldBytesID: prefix=158 time=39.4 ns
{0, 1, 0}it would return 23. Is that what is wanted? Or should it return 15? \$\endgroup\$