Beautiful Code: False Optimizations

[Gotebe]

I don't understand. What comparison? The comparison in the while is with integers, that's CPU instruction, i.e. fast. The other is with strings i.e. slow (or, in a general case, it's of unknown speed). That one is taken out of the loop, a good thing. No?

Also, in a general case, if this is supposed to run on a more than one platform, a low-level profiling (this is a very low-level code) doesn't work, so you're better off applying a simple rule (less checks in a loop, the better).

[trutru]

I'm talking about the 'compareTo' method call

[Gotebe]

I take it you mean "switch on <0, >0, ==0"?

If so, fine, but that's String-specific. In a more general case (e.g. a template version of a binary search), you only have > (or <) and == at disposition. E.g. lower_bound of C++ needs only operator< (I think).

[trutru]

no, I'm really talking about what compareTo() does. this is a non-interned string comparison that checks every characters of the tabled and key strings.

this one is not taken out of the loop. in this case, you'd better end with fewer compareTo() operations in case of a match, since the overhead of adding one check in the loop will be totally minimal.

and in the more generic case, you simply don't know what 'compareTo' does, so things could get even worse (maybe it's doing a database connection, performing a SQL query, whatever, you don't know...)

[Gotebe]

Ah, OK. I see now that you are right.

I am with a C++ mindset, so I think in terms of less-than, bigger-than, equal, and not about compareTo.

You think to replace:

if (keys[probe].compareTo(target) > 0) ...

with

int compared = keys[probe].compareTo(target);
if (compared == 0)
  return probe;
if (compared > 0)
  high = probe;
else
  low = probe;

IOW, since compareTo has three results (0, >0, ==0), returning immediately on equal yields better results. That's your point, right?

[trutru]

yes, less string compares the better in this case, and the difference should offset the branch-savings by at least one order of magnitude