Mark Adams <mfad...@lbl.gov> writes:
> The existing code seems to have *a line (low=i+1) *that seems to be
> trying to exploit consecutive indices but it is not quite right, I don't
> think,
>
> This is the existing code fragment (this code has been cloned many times
> and there are several instances of this kernel).
>
> I've *added code* that I think might make this do the right thing.
>
> if (col <= lastcol) low = 0;
> else high = nrow;
> lastcol = col;
> while (high-low > 5) {
> t = (low+high)/2;
>
> *if (rp[low] == col) high = low+1;else * if (rp[t] > col) high = t;
> else low = t;
Replacing a single comparison per bsearch iteration with two doesn't
seem like a good choice to me.
> }
> for (i=low; i<high; i++) {
> if (rp[i] > col) break; *// delete this check if you don't add new
> columns*
> if (rp[i] == col) {
> ap[i] += value;
>
> * low = i + 1;* goto noinsert;
I was thinking of a fast-path like while (rp[i] == in[l]) ap[i++] = in[l++];
A bit more logic is needed to avoid running off the end of either array.
