{"action":"created","issue":{"url":"https://api.github.com/repos/numba/numba/issues/1383","repository_url":"https://api.github.com/repos/numba/numba","labels_url":"https://api.github.com/repos/numba/numba/issues/1383/labels{/name}","comments_url":"https://api.github.com/repos/numba/numba/issues/1383/comments","events_url":"https://api.github.com/repos/numba/numba/issues/1383/events","html_url":"https://github.com/numba/numba/issues/1383","id":102308676,"number":1383,"title":"Performance Of MergeSort vs Numpy","user":{"login":"jsphon","id":5187727,"avatar_url":"https://avatars.githubusercontent.com/u/5187727?v=3","gravatar_id":"","url":"https://api.github.com/users/jsphon","html_url":"https://github.com/jsphon","followers_url":"https://api.github.com/users/jsphon/followers","following_url":"https://api.github.com/users/jsphon/following{/other_user}","gists_url":"https://api.github.com/users/jsphon/gists{/gist_id}","starred_url":"https://api.github.com/users/jsphon/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jsphon/subscriptions","organizations_url":"https://api.github.com/users/jsphon/orgs","repos_url":"https://api.github.com/users/jsphon/repos","events_url":"https://api.github.com/users/jsphon/events{/privacy}","received_events_url":"https://api.github.com/users/jsphon/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":8,"created_at":"2015-08-21T06:20:53Z","updated_at":"2016-03-03T11:35:38Z","closed_at":null,"body":"Also posted here: http://stackoverflow.com/questions/32133597/how-to-improve-this-merge-sort\r\n\r\nI have written a mergesort in Python/Numba:\r\n\r\n    import numba as nb\r\n    import numpy as np\r\n\r\n    @nb.jit( nopython=True )\r\n    def merge( x ):\r\n        \r\n        n = x.shape[0]\r\n        width=1\r\n        \r\n        r   = x.copy()\r\n        tgt = np.empty_like( r )\r\n        while width<n:\r\n            i=0\r\n            while i<n:\r\n                istart = i\r\n                imid = i+width\r\n                iend = imid+width\r\n                # i has become i+2*width\r\n                i = iend\r\n    \r\n                if imid>n:\r\n                    imid = n\r\n                    \r\n                if iend>n:\r\n                    iend=n\r\n                _merge( r, tgt, istart, imid, iend)\r\n    \r\n            # Swap them round, so that the partially sorted tgt becomes the result,\r\n            # and the result becomes a new target buffer\r\n            r, tgt = tgt, r\r\n            width*=2\r\n            \r\n        return r\r\n    \r\n    @nb.jit( nopython=True )\r\n    def _merge( src_arr, tgt_arr, istart, imid, iend ):\r\n        \"\"\" The merge part of the merge sort \"\"\"\r\n        i0   = istart\r\n        i1   = imid\r\n        for ipos in range( istart, iend ):\r\n            if ( i0<imid ) and ( ( i1==iend ) or ( src_arr[ i0 ] < src_arr[ i1 ] ) ):\r\n                tgt_arr[ ipos ] = src_arr[ i0 ]\r\n                i0+=1\r\n            else:\r\n                tgt_arr[ ipos ] = src_arr[ i1 ]\r\n                i1+=1\r\n\r\nI have written a test for it:\r\n\r\n    def test_merge_multi(self):\r\n        \r\n        n0 = 21\r\n        n1 = 100\r\n        \r\n        for n in range( n0, n1 ):\r\n            x = np.random.random_integers( 0, n, size=n )\r\n        \r\n            with Timer( 'nb' ) as t0:\r\n                r = sas.merge( x )\r\n            with Timer( 'np' ) as t1:\r\n                e = np.sort( x, kind='merge' )\r\n            #print( 'r:%s'%str(r))\r\n            #print( 'e:%s'%str(e))\r\n            print( 'nb/np performance %s'%(t0.interval/t1.interval ))\r\n            np.testing.assert_equal( e, r )\r\n\r\nI used this Timer class:\r\n\r\n    import time\r\n    \r\n    class Timer:    \r\n        \r\n        def __init__(self,title=None):\r\n            self.title=title\r\n            \r\n        def __enter__(self):\r\n            if self.title:\r\n                print( 'Beginning {0}'.format( self.title ) )\r\n            self.start = time.clock()\r\n            return self\r\n    \r\n        def __exit__(self, *args):\r\n            self.end = time.clock()\r\n            self.interval = self.end - self.start\r\n            if self.title:\r\n                print( '{1} took {0:0.4f} seconds'.format( self.interval, self.title ) )\r\n            else:\r\n                pass#\r\n                #print( 'Timer took {0:0.4f} seconds'.format( self.interval ) )\r\n                \r\nThe test results are:\r\n\r\n    nb/np performance 9307.846153856719\r\n    nb/np performance 1.1428571428616743\r\n    nb/np performance 0.7142857142925115\r\n    nb/np performance 0.8333333333302494\r\n    nb/np performance 0.9999999999814962\r\n    nb/np performance 0.9999999999777955\r\n    nb/np performance 0.8333333333456692\r\n    nb/np performance 0.8333333333302494\r\n    nb/np performance 1.0\r\n    nb/np performance 0.8333333333456692\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 0.8333333333456692\r\n    nb/np performance 0.9999999999814962\r\n    nb/np performance 1.0\r\n    nb/np performance 0.9999999999814962\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0000000000185036\r\n    nb/np performance 1.2000000000044408\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0000000000185036\r\n    nb/np performance 1.2000000000088817\r\n    nb/np performance 1.0\r\n    nb/np performance 1.1666666666512469\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 0.9999999999814962\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.1666666666512469\r\n    nb/np performance 1.0\r\n    nb/np performance 1.0\r\n    nb/np performance 1.1666666666512469\r\n    nb/np performance 1.1666666666512469\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.1666666666512469\r\n    nb/np performance 1.1666666666512469\r\n    nb/np performance 1.0\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.3333333333456692\r\n    nb/np performance 1.3333333333024937\r\n    nb/np performance 1.3333333333456692\r\n    nb/np performance 1.1428571428435483\r\n    nb/np performance 1.3333333333209976\r\n    nb/np performance 1.1666666666728345\r\n    nb/np performance 1.3333333333456692\r\n    nb/np performance 1.3333333333209976\r\n    nb/np performance 1.000000000012336\r\n    nb/np performance 1.1428571428616743\r\n    nb/np performance 1.3333333333456692\r\n    nb/np performance 1.3333333333209976\r\n    nb/np performance 1.1428571428616743\r\n    nb/np performance 1.1428571428616743\r\n    nb/np performance 1.3333333333456692\r\n    nb/np performance 1.499999999990748\r\n    nb/np performance 1.2857142857074884\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.2857142857029569\r\n    nb/np performance 1.1428571428616743\r\n    nb/np performance 1.1428571428435483\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.2857142857029569\r\n    nb/np performance 1.1249999999895917\r\n    nb/np performance 1.2857142857029569\r\n    nb/np performance 1.2857142857233488\r\n    nb/np performance 1.4285714285623656\r\n    nb/np performance 1.249999999993061\r\n    nb/np performance 1.1250000000034694\r\n    nb/np performance 1.2857142857029569\r\n\r\ngraphed results (from a different run):\r\n\r\n[![enter image description here][1]][1]\r\n\r\nGraphed results from a longer run:\r\n\r\n[![enter image description here][2]][2]\r\n\r\nPlease note that for n<=20, numpy uses an insertion sort when the mergesort is called: https://github.com/numpy/numpy/blob/master/numpy/core/src/npysort/mergesort.c.src\r\n\r\nSo you can see that for small values of n, the numba version of the mergesort beats the numpy version.\r\n\r\nHowever, as n gets larger, numpy then consistently outperforms numba by a factor of 2.\r\n\r\nWhy is this? And how could I optimise the numba version to beat the numpy version for all n?\r\n\r\n\r\n  [1]: http://i.stack.imgur.com/TyNOU.png\r\n  [2]: http://i.stack.imgur.com/OXMuo.png"},"comment":{"url":"https://api.github.com/repos/numba/numba/issues/comments/191719383","html_url":"https://github.com/numba/numba/issues/1383#issuecomment-191719383","issue_url":"https://api.github.com/repos/numba/numba/issues/1383","id":191719383,"user":{"login":"pitrou","id":1721820,"avatar_url":"https://avatars.githubusercontent.com/u/1721820?v=3","gravatar_id":"","url":"https://api.github.com/users/pitrou","html_url":"https://github.com/pitrou","followers_url":"https://api.github.com/users/pitrou/followers","following_url":"https://api.github.com/users/pitrou/following{/other_user}","gists_url":"https://api.github.com/users/pitrou/gists{/gist_id}","starred_url":"https://api.github.com/users/pitrou/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pitrou/subscriptions","organizations_url":"https://api.github.com/users/pitrou/orgs","repos_url":"https://api.github.com/users/pitrou/repos","events_url":"https://api.github.com/users/pitrou/events{/privacy}","received_events_url":"https://api.github.com/users/pitrou/received_events","type":"User","site_admin":false},"created_at":"2016-03-03T11:35:38Z","updated_at":"2016-03-03T11:35:38Z","body":"I'll note that the best results are obtained with an `int32` array here (Linux x86-64). With an array of `int64` or `int16` for example, Numba is 1.35x slower. This is unlikely due to any issues in Numba itself, rather code generation differences between gcc and LLVM."}}