Return to Question

This is my attempt to answer my own equally named question on SO. In this case, I need a method comparing two strings so that the running time is input independent.

This is my attempt to answer my own equally named question on SO. In this case, I need a method comparing two strings so that the running time is input independent.

It's a really short snippet and I'm mainly interested in ensuring that it really works in constant time.

It's a really short snippet and I'm mainly interested in ensuring that it really works in constant time. In particular, I'm afraid that the loop could indeed get optimized to something like

int i = 0
for (; ; ++i) {
 if (input.charAt(i) != secret.charAt(i)) break;
}
for (; i < length; ++i) {
 delta += input.charAt(i) ^ secret.charAt(i);
}

where the first loop could be faster on some architectures, as -- after unrolling -- it translates to load, xor with memory, and a conditional jump. Assuming some future architecture capable of executing 6 instructions per cycle when there are no data dependencies and no mispredictions, it could be a win. Or the JIT could believe, it makes sense...

##Update due to Ext3h's comment

I'm afraid, the loop could indeed get optimized to something like

int i = 0
for (; ; ++i) {
 if (input.charAt(i) != secret.charAt(i)) break;
}
for (; i < length; ++i) {
 delta += input.charAt(i) ^ secret.charAt(i);
}

where the first loop could be faster on some architectures, as -- after unrolling -- it translates to load, xor with memory, and a conditional jump. Assuming some future architecture capable of executing 6 instructions per cycle when there are no data dependencies and no mispredictions, it could be a win. Or the JIT could believe, it makes sense...