{"action":"created","issue":{"url":"https://api.github.com/repos/numpy/numpy/issues/6166","labels_url":"https://api.github.com/repos/numpy/numpy/issues/6166/labels{/name}","comments_url":"https://api.github.com/repos/numpy/numpy/issues/6166/comments","events_url":"https://api.github.com/repos/numpy/numpy/issues/6166/events","html_url":"https://github.com/numpy/numpy/pull/6166","id":99223808,"number":6166,"title":"WIP: Better memory overlap detection","user":{"login":"pv","id":35046,"avatar_url":"https://avatars.githubusercontent.com/u/35046?v=3","gravatar_id":"","url":"https://api.github.com/users/pv","html_url":"https://github.com/pv","followers_url":"https://api.github.com/users/pv/followers","following_url":"https://api.github.com/users/pv/following{/other_user}","gists_url":"https://api.github.com/users/pv/gists{/gist_id}","starred_url":"https://api.github.com/users/pv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pv/subscriptions","organizations_url":"https://api.github.com/users/pv/orgs","repos_url":"https://api.github.com/users/pv/repos","events_url":"https://api.github.com/users/pv/events{/privacy}","received_events_url":"https://api.github.com/users/pv/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":15,"created_at":"2015-08-05T14:56:05Z","updated_at":"2015-08-06T08:58:30Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/numpy/numpy/pulls/6166","html_url":"https://github.com/numpy/numpy/pull/6166","diff_url":"https://github.com/numpy/numpy/pull/6166.diff","patch_url":"https://github.com/numpy/numpy/pull/6166.patch"},"body":"Here's an initial stab at (i) exact solution for whether two arrays overlap in memory, and (ii) using it in array assignment overlap detection.\r\n\r\nAs the problem presumably is np-hard, the algorithm used for (i) scales exponentially with the number of dimensions of the arrays. By limiting the depth of the search, one obtains an improved `may_share_memory` that can deal with several common cases for strided arrays. I use the limited version with a fixed search size to get a (fairly OK) approximate answer.\r\n\r\nCurrently, overlap detection in Numpy appears to be used for making temporary copies for array assignment.\r\n\r\nFirst step at addressing gh-6119, gh-1683 etc.\r\n\r\nThe next step would be to reuse the logic by which we make copies for assignment in also making temporary copies of ufunc input (and maybe updateifcopy for output) arguments.\r\n\r\nThis needs still somewhat more tests, and `max_work` should be tuned appropriately based on benchmarks. Perhaps it needs to depend on the size of the arrays, to balance the cost of making copies against cost of solving the integer program.\r\n\r\nI'm aware there are several other algorithms for solving Diophantine equations in the literature, as the problem apparently also crops up in automatic theorem proving. However, the present one is fairly simple, low on memory requirements, and performance seems OK, so I'd prefer to just roll with it."},"comment":{"url":"https://api.github.com/repos/numpy/numpy/issues/comments/128296103","html_url":"https://github.com/numpy/numpy/pull/6166#issuecomment-128296103","issue_url":"https://api.github.com/repos/numpy/numpy/issues/6166","id":128296103,"user":{"login":"pv","id":35046,"avatar_url":"https://avatars.githubusercontent.com/u/35046?v=3","gravatar_id":"","url":"https://api.github.com/users/pv","html_url":"https://github.com/pv","followers_url":"https://api.github.com/users/pv/followers","following_url":"https://api.github.com/users/pv/following{/other_user}","gists_url":"https://api.github.com/users/pv/gists{/gist_id}","starred_url":"https://api.github.com/users/pv/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pv/subscriptions","organizations_url":"https://api.github.com/users/pv/orgs","repos_url":"https://api.github.com/users/pv/repos","events_url":"https://api.github.com/users/pv/events{/privacy}","received_events_url":"https://api.github.com/users/pv/received_events","type":"User","site_admin":false},"created_at":"2015-08-06T08:58:30Z","updated_at":"2015-08-06T08:58:30Z","body":"I note code relying on non-copy semantics is brittle also in 1D cases\n--- we have previously changed the behavior in some cases:\n.\nimport numpy as np\nx = np.arange(5)[::-1]\nx[1:] += x[:-1]\nprint(np.__version__, x)\n.\nproduces:\n.\n('1.6.2', array([ 4,  7,  9, 10, 10]))\n('1.9.2', array([4, 7, 5, 3, 1]))\n.\nThe only case that works the same in 1.9.x and 1.5.x is probably 1D with\npositive stride. It seems to me non-copy semantics also for this case is\nundefined behavior.\n.\nThe output array from binary ufunc has size>=max(a.size,b.size) and the\nufunc fills all entries.\n"}}