8000 ENH: speed up putmask avoiding % in inner loop by jaimefrio · Pull Request #5501 · numpy/numpy · GitHub
[go: up one dir, main page]
Skip to content

ENH: speed up putmask avoiding % in inner loop #5501

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Feb 24, 2015
Merged

ENH: speed up putmask avoiding % in inner loop #5501

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
ENH: speed up putmask avoiding % in inner loop
  • Loading branch information
@jaimefrio
jaimefrio committed Jan 25, 2015
commit fc8db7395f51311e4856eaae25c4b3aa62bd9164
12 changes: 7 additions & 5 deletions numpy/core/src/multiarray/arraytypes.c.src
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3680,21 +3680,23 @@ static void
@name@_fastputmask(@type@ *in, npy_bool *mask, npy_intp ni, @type@ *vals,
npy_intp nv)
{
npy_intp i;
@type@ s_val;
npy_intp i, j;

if (nv == 1) {
s_val = *vals;
@type@ s_val = *vals;
for (i = 0; i < ni; i++) {
if (mask[i]) {
in[i] = s_val;
}
}
}
else {
for (i = 0; i < ni; i++) {
for (i = 0, j = 0; i < ni; i++, j++) {
if (j >= nv) {
j = 0;
}
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Speaking of branch prediction and code bumming, gcc -O2 generates a loop with three conditional jumps, but if this conditional block is replaced with

j *= (j < nv);

there's only two of them. Might be worth a try to see if multiplication is faster than modulo.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

maybe worth a try, though a predicted near branch has among the best low latency/throughput of all instructions, multiplication is I think in the range of latency 4 throughout 1 cycle, likely the reason why the compiler does not do this transformation.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

With the single benchmark I have been using, multiplying clocks in at 2.36 us, slightly better than current master, but noticeably slower than the single if in this PR, that takes 1.56 us.

Playing the "minimize branch misprediction" game, my best effort so far, clocking in at 1.25 us and outperforming the current code in this PR is the following:

i = 0;
while (i < ni) {
    for (j = 0; j < nv; ++j, ++i) {
        if (i >= ni) {
            break;
        }
        in[i] = vals[j];
    }
}

I suppose this is capitalizing on the ability to smartly predict loops. I am not fully sure that it is worth uglying the code like this, neither would I bet any money on the result being consistent across processor architectures. My timings come from a Sandy Bridge Intel i5, FWIW.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The extra performance was of course coming from leaving the mask check out... Putting it back in the following takes the same time (1.55 us) as the much more readable single if in the current PR:

for (i = 0; i < ni;) {
    for (j = 0; j < nv && i < ni; ++j, ++i) {
        if (mask[i]) {
            in[i] = vals[j];
        }
    }
}

if (mask[i]) {
in[i] = vals[i%nv];
in[i] = vals[j];
}
}
}
Expand Down
39 changes: 24 additions & 15 deletions numpy/core/src/multiarray/item_selection.c
View file
Open in desktop
38A9
Original file line number Diff line number Diff line change
Expand Up @@ -427,10 +427,11 @@ NPY_NO_EXPORT PyObject *
PyArray_PutMask(PyArrayObject *self, PyObject* values0, PyObject* mask0)
{
PyArray_FastPutmaskFunc *func;
PyArrayObject *mask, *values;
PyArrayObject *mask, *values;
PyArray_Descr *dtype;
npy_intp i, chunk, ni, max_item, nv, tmp;
npy_intp i, j, chunk, ni, max_item, nv;
char *src, *dest;
npy_bool *mask_data;
int copied = 0;

mask = NULL;
Expand Down Expand Up @@ -469,6 +470,7 @@ PyArray_PutMask(PyArrayObject *self, PyObject* values0, PyObject* mask0)
"the same size");
goto fail;
}
mask_data = PyArray_DATA(mask);
dtype = PyArray_DESCR(self);
Py_INCREF(dtype);
values = (PyArrayObject *)PyArray_FromAny(values0, dtype,
Expand All @@ -483,14 +485,20 @@ PyArray_PutMask(PyArrayObject *self, PyObject* values0, PyObject* mask0)
Py_INCREF(Py_None);
return Py_None;
}
src = PyArray_DATA(values);

if (PyDataType_REFCHK(PyArray_DESCR(self))) {
for (i = 0; i < ni; i++) {
tmp = ((npy_bool *)(PyArray_DATA(mask)))[i];
if (tmp) {
src = PyArray_BYTES(values) + chunk * (i % nv);
PyArray_Item_INCREF(src, PyArray_DESCR(self));
PyArray_Item_XDECREF(dest+i*chunk, PyArray_DESCR(self));
memmove(dest + i * chunk, src, chunk);
for (i = 0, j = 0; i < ni; i++, j++) {
if (j >= nv) {
j = 0;
}
if (mask_data[i]) {
char *src_ptr = src + j*chunk;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could just increment src and dest by chunk each time around, resetting srcalong with j. That would make a difference for dense masks, although there are a other bits in the loop that might take time. Not needed for this PR, though.

char *dest_ptr = dest + i*chunk;

PyArray_Item_INCREF(src_ptr, PyArray_DESCR(self));
PyArray_Item_XDECREF(dest_ptr, PyArray_DESCR(self));
memmove(dest_ptr, src_ptr, chunk);
}
}
}
Expand All @@ -499,16 +507,17 @@ PyArray_PutMask(PyArrayObject *self, PyObject* values0, PyObject* mask0)
NPY_BEGIN_THREADS_DESCR(PyArray_DESCR(self));
func = PyArray_DESCR(self)->f->fastputmask;
if (func == NULL) {
for (i = 0; i < ni; i++) {
tmp = ((npy_bool *)(PyArray_DATA(mask)))[i];
if (tmp) {
src = PyArray_BYTES(values) + chunk*(i % nv);
memmove(dest + i*chunk, src, chunk);
for (i = 0, j = 0; i < ni; i++, j++) {
if (j >= nv) {
j = 0;
}
if (mask_data[i]) {
memmove(dest + i*chunk, src + j*chunk, chunk);
}
}
}
else {
func(dest, PyArray_DATA(mask), ni, PyArray_DATA(values), nv);
func(dest, mask_data, ni, src, nv);
}
NPY_END_THREADS;
}
Expand Down
0