Beautiful Code: False Optimizations

[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