How to speed up interval lookup for a piecewise defined function?
It'll take some testing to be entirely certainly, but a few possibilities to consider:

if (x &gt;= *cache &amp;&amp; x &lt; *(cache + 1)) {


I'd try replacing this with:

if (static_cast&lt;unsigned&gt;(x-*cache) &lt; static_cast&lt;unsigned&gt;(*(cache+1) - *cache)) {


[Technically, unsigned is a place-holder here. It should really be something like std::make_unsigned&lt;input_type&gt;::type. That is, if the input is (say) long long, you want unsigned long long, not just unsigned int.]

This basically replaces two comparisons (that must be executed serially, thanks to &amp;&amp; imposing a sequence point) with one plus a little extra math. The math can typically be done in parallel, and the branch becomes more predictable as well.

if (x &lt; *begin || x &gt; *end) {
    outside = true;
} else {
    outside = false;


I'd at least try just assigning the result of the comparison:

outside = x &lt; *begin || x &gt; *end;


Again, you can try the same "trick" as above, and get something like:

outside = static_cast&lt;unsigned&gt;(x-*begin) &lt;= static_cast&lt;unsigned&gt;(*end-*begin);


As before, this replaces two relatively unpredictable comparisons with one relatively predictable one.

if (n_ &lt; 64) {
[3%]    position = std::find_if(begin, end, std::bind2nd(std::greater_equal&lt;argument_type&gt;(), x)) - 1;
    } else {    
        position = std::upper_bound(begin, end, x) - 1;
    }


If you're spending significantly more time in the linear search than the binary search, I'd try reducing the cut-off between the two, perhaps to 32 instead of 64.

As with any micro-optimization, none of these is really guaranteed to be effective. It's even possible your compiler may be incorporating one or more of them into the code it generates, so they'll do no good at all, or even that its optimizer won't recognize the resulting patterns in the code as well, so they could actually hurt performance. The only real way to find out is some testing and profiling.