{"action":"created","issue":{"url":"https://api.github.com/repos/kwgoodman/bottleneck/issues/123","repository_url":"https://api.github.com/repos/kwgoodman/bottleneck","labels_url":"https://api.github.com/repos/kwgoodman/bottleneck/issues/123/labels{/name}","comments_url":"https://api.github.com/repos/kwgoodman/bottleneck/issues/123/comments","events_url":"https://api.github.com/repos/kwgoodman/bottleneck/issues/123/events","html_url":"https://github.com/kwgoodman/bottleneck/issues/123","id":157766647,"number":123,"title":"Proposal for new design of bottleneck internals","user":{"login":"kwgoodman","id":299024,"avatar_url":"https://avatars.githubusercontent.com/u/299024?v=3","gravatar_id":"","url":"https://api.github.com/users/kwgoodman","html_url":"https://github.com/kwgoodman","followers_url":"https://api.github.com/users/kwgoodman/followers","following_url":"https://api.github.com/users/kwgoodman/following{/other_user}","gists_url":"https://api.github.com/users/kwgoodman/gists{/gist_id}","starred_url":"https://api.github.com/users/kwgoodman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kwgoodman/subscriptions","organizations_url":"https://api.github.com/users/kwgoodman/orgs","repos_url":"https://api.github.com/users/kwgoodman/repos","events_url":"https://api.github.com/users/kwgoodman/events{/privacy}","received_events_url":"https://api.github.com/users/kwgoodman/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2016-05-31T20:46:39Z","updated_at":"2016-06-01T03:07:09Z","closed_at":null,"body":"In the current design we do this to add the function bn.nanmean to bottleneck (I'll only show the float version, you'd also need to add the integer version):\r\n```\r\n\r\n@cython.cdivision(True)\r\ncdef object nanmean_all_DTYPE0(np.flatiter ita, Py_ssize_t stride,\r\n                               Py_ssize_t length, int int_input):\r\n    # bn.dtypes = [['float64'], ['float32']]\r\n    cdef Py_ssize_t i, count = 0\r\n    cdef DTYPE0_t asum = 0, ai\r\n    with nogil:\r\n        while PyArray_ITER_NOTDONE(ita):\r\n            for i in range(length):\r\n                ai = (<DTYPE0_t*>((<char*>pid(ita)) + i * stride))[0]\r\n                if ai == ai:\r\n                    asum += ai\r\n                    count += 1\r\n            PyArray_ITER_NEXT(ita)\r\n    if count > 0:\r\n        return asum / count\r\n    else:\r\n        return NAN\r\n\r\n@cython.cdivision(True)\r\ncdef ndarray nanmean_one_DTYPE0(np.flatiter ita,\r\n                                Py_ssize_t stride, Py_ssize_t length,\r\n                                int a_ndim, np.npy_intp* y_dims,\r\n                                int int_input):\r\n    # bn.dtypes = [['float64'], ['float32']]\r\n    cdef Py_ssize_t i, count\r\n    cdef DTYPE0_t asum = 0, ai\r\n    cdef ndarray y = PyArray_EMPTY(a_ndim - 1, y_dims, NPY_DTYPE0, 0)\r\n    cdef np.flatiter ity = PyArray_IterNew(y)\r\n    with nogil:\r\n        if length == 0:\r\n            while PyArray_ITER_NOTDONE(ity):\r\n                (<DTYPE0_t*>((<char*>pid(ity))))[0] = NAN\r\n                PyArray_ITER_NEXT(ity)\r\n        else:\r\n            while PyArray_ITER_NOTDONE(ita):\r\n                asum = 0\r\n                count = 0\r\n                for i in range(length):\r\n                    ai = (<DTYPE0_t*>((<char*>pid(ita)) + i*stride))[0]\r\n                    if ai == ai:\r\n                        asum += ai\r\n                        count += 1\r\n                if count > 0:\r\n                    asum = asum / count\r\n                else:\r\n                    asum = NAN\r\n                (<DTYPE0_t*>((<char*>pid(ity))))[0] = asum\r\n                PyArray_ITER_NEXT(ita)\r\n                PyArray_ITER_NEXT(ity)\r\n    return y\r\n```\r\n\r\nUnder the new proposal here's the code you'd write instead:\r\n```\r\n@cython.cdivision(True)\r\ncdef inline DTYPE0_t nanmean_DTYPE0(char *p,\r\n                                    Py_ssize_t stride,\r\n                                    Py_ssize_t length,\r\n                                    int int_input) nogil:\r\n    # bn.dtypes = [['float64'], ['float32']]\r\n    cdef Py_ssize_t i, count = 0\r\n    cdef DTYPE0_t ai, asum = 0\r\n    for i in range(length):\r\n        ai = (<DTYPE0_t*>(p + i * stride))[0]\r\n        if ai == ai:\r\n            asum += ai\r\n            count += 1\r\n    if count > 0:\r\n        return asum / count\r\n    else:\r\n        return NAN\r\n```\r\n\r\nThe code is in the `minty_fresh` branch. I only ported nansum and nanmean (called nansum2 and nanmean2 in the branch).\r\n\r\nWhen the length of each dimension of the array is large, performance is the same as before:\r\n```\r\nIn [1]: a=np.random.rand(1000, 10000)\r\nIn [2]: timeit bn.nanmean(a)\r\n100 loops, best of 3: 7.89 ms per loop\r\nIn [3]: timeit bn.nanmean2(a)\r\n100 loops, best of 3: 7.86 ms per loop\r\n```\r\n\r\nFor 1d arrays the overhead has been reduced:\r\n```\r\nIn [4]: a=np.random.rand(10)\r\nIn [5]: timeit bn.nanmean(a)\r\n1000000 loops, best of 3: 226 ns per loop\r\nIn [6]: timeit bn.nanmean2(a)\r\n10000000 loops, best of 3: 184 ns per loop\r\n```\r\n\r\nFor reduction of 2d (or higher) arrays with `axis=None`, overhead has increased because the rewrite uses PyArray_Ravel:\r\n```\r\nIn [7]: a=np.random.rand(10,10)\r\nIn [8]: timeit bn.nanmean(a)\r\n1000000 loops, best of 3: 325 ns per loop\r\nIn [9]: timeit bn.nanmean2(a)\r\n1000000 loops, best of 3: 382 ns per loop\r\n```\r\n\r\nFor repeated calls to the new inline function where each call does hardly any work, performance has decreased (not sure why; I don't even know if the inlining is taking place):\r\n```\r\nIn [10]: a=np.random.rand(1000000,2)\r\nIn [11]: timeit bn.nanmean(a, 1)\r\n100 loops, best of 3: 5.28 ms per loop\r\nIn [12]: timeit bn.nanmean2(a, 1)\r\n100 loops, best of 3: 5.96 ms per loop\r\n```\r\n\r\nAdding a new reduction function to bottleneck is rare. So I'd only want to use the new design if we can improve the performance of the last two cases. On the other hand maybe the new design would make it easier to do things like optimize for reduction along a non-fast axis."},"comment":{"url":"https://api.github.com/repos/kwgoodman/bottleneck/issues/comments/222880938","html_url":"https://github.com/kwgoodman/bottleneck/issues/123#issuecomment-222880938","issue_url":"https://api.github.com/repos/kwgoodman/bottleneck/issues/123","id":222880938,"user":{"login":"jennolsen84","id":10360673,"avatar_url":"https://avatars.githubusercontent.com/u/10360673?v=3","gravatar_id":"","url":"https://api.github.com/users/jennolsen84","html_url":"https://github.com/jennolsen84","followers_url":"https://api.github.com/users/jennolsen84/followers","following_url":"https://api.github.com/users/jennolsen84/following{/other_user}","gists_url":"https://api.github.com/users/jennolsen84/gists{/gist_id}","starred_url":"https://api.github.com/users/jennolsen84/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jennolsen84/subscriptions","organizations_url":"https://api.github.com/users/jennolsen84/orgs","repos_url":"https://api.github.com/users/jennolsen84/repos","events_url":"https://api.github.com/users/jennolsen84/events{/privacy}","received_events_url":"https://api.github.com/users/jennolsen84/received_events","type":"User","site_admin":false},"created_at":"2016-06-01T03:07:09Z","updated_at":"2016-06-01T03:07:09Z","body":"Regarding function pointers and inlining, I remember Bjarne Stroustrup saying that C++'s sort() was faster than qsort because it didn't use function pointers.  Someone did a benchmark here:\r\n\r\n```\r\nhttp://www.martin-ueding.de/en/programming/qsort/index.html\r\n```\r\n\r\n"}}
{"actor":{"display_login":"jennolsen84"}}