{"action":"created","issue":{"url":"https://api.github.com/repos/dashpay/dash/issues/1055","repository_url":"https://api.github.com/repos/dashpay/dash","labels_url":"https://api.github.com/repos/dashpay/dash/issues/1055/labels{/name}","comments_url":"https://api.github.com/repos/dashpay/dash/issues/1055/comments","events_url":"https://api.github.com/repos/dashpay/dash/issues/1055/events","html_url":"https://github.com/dashpay/dash/pull/1055","id":180403050,"number":1055,"title":"[PrivateSend] Performance tweak for MN-exclusion list","user":{"login":"crowning-","id":10080039,"avatar_url":"https://avatars.githubusercontent.com/u/10080039?v=3","gravatar_id":"","url":"https://api.github.com/users/crowning-","html_url":"https://github.com/crowning-","followers_url":"https://api.github.com/users/crowning-/followers","following_url":"https://api.github.com/users/crowning-/following{/other_user}","gists_url":"https://api.github.com/users/crowning-/gists{/gist_id}","starred_url":"https://api.github.com/users/crowning-/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/crowning-/subscriptions","organizations_url":"https://api.github.com/users/crowning-/orgs","repos_url":"https://api.github.com/users/crowning-/repos","events_url":"https://api.github.com/users/crowning-/events{/privacy}","received_events_url":"https://api.github.com/users/crowning-/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-09-30T21:10:20Z","updated_at":"2016-10-01T00:59:53Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/dashpay/dash/pulls/1055","html_url":"https://github.com/dashpay/dash/pull/1055","diff_url":"https://github.com/dashpay/dash/pull/1055.diff","patch_url":"https://github.com/dashpay/dash/pull/1055.patch"},"body":"I think it's inefficient to build a vector with ALL Masternodes, shuffle them and then loop over all to find one not in the exclusion vector.\r\n\r\nMy change builds a vector with all not-excluded Masternodes and shuffles that vector  instead.\r\nWhen there's lots of Masternodes and lots of excluded Masternodes this is much more efficient because that vector is much smaller.\r\n\r\nNot a dramatic improvement, but IMO one worth trying.\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/dashpay/dash/issues/comments/250882809","html_url":"https://github.com/dashpay/dash/pull/1055#issuecomment-250882809","issue_url":"https://api.github.com/repos/dashpay/dash/issues/1055","id":250882809,"user":{"login":"UdjinM6","id":1935069,"avatar_url":"https://avatars.githubusercontent.com/u/1935069?v=3","gravatar_id":"","url":"https://api.github.com/users/UdjinM6","html_url":"https://github.com/UdjinM6","followers_url":"https://api.github.com/users/UdjinM6/followers","following_url":"https://api.github.com/users/UdjinM6/following{/other_user}","gists_url":"https://api.github.com/users/UdjinM6/gists{/gist_id}","starred_url":"https://api.github.com/users/UdjinM6/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/UdjinM6/subscriptions","organizations_url":"https://api.github.com/users/UdjinM6/orgs","repos_url":"https://api.github.com/users/UdjinM6/repos","events_url":"https://api.github.com/users/UdjinM6/events{/privacy}","received_events_url":"https://api.github.com/users/UdjinM6/received_events","type":"User","site_admin":false},"created_at":"2016-10-01T00:59:53Z","updated_at":"2016-10-01T00:59:53Z","body":"Well, I'm not that much convinced tbh. \r\n\r\nshuffle\r\n```\r\ntemplate <class RandomAccessIterator, class RandomNumberGenerator>\r\n  void random_shuffle (RandomAccessIterator first, RandomAccessIterator last,\r\n                       RandomNumberGenerator& gen)\r\n{\r\n  iterator_traits<RandomAccessIterator>::difference_type i, n;\r\n  n = (last-first);\r\n  for (i=n-1; i>0; --i) {\r\n    swap (first[i],first[gen(i+1)]);\r\n  }\r\n}\r\n```\r\n\r\nx - number of entries to exclude\r\ny - number of masternodes\r\n\r\nCurrent code:\r\n1. loop to fill vector (1..y)\r\n2. shuffle (y)\r\n3. loop through (1..y)\r\n3.1 inner loop (1..x)\r\n3.2. not found in excluded? **return**\r\ni.e. in the worst case scenario when every first x masternodes match elements of vecToExclude it means that we break on every of 1..x step from inner loop and after doing (x+1)th step of outer loop we should be 100% able to return the answer. Which gives us this:\r\n`loop(y) + shuffle(y) + loop( (1+x+1)*(x+1)/2 )`\r\n\r\nYour code:\r\n1. loop (1..y)\r\n1.1. inner loop (1..x)\r\n1.2 not found in excluded? add\r\n2. shuffle (y - x) and **return**\r\ni.e. no matter how elements and masternodes are sorted it's the same loop with the same kind of break as above but after x steps of outer loop you need to finish it, so it's another (y-x) steps of outer loop each x steps long + shuffle. Which gives us this:\r\n`loop( (1+x)*x/2 + (y-x)*x ) + shuffle(y-x)`\r\n\r\nEven though there is one more loop in current code, we exit early (right after first candidate was found) while in you code you have to continue and keep looping in that double loop till the end.\r\n\r\nSay we have 4000 masternodes, we need to exclude 100 of them and we are extremely unlucky (first 100 masternodes match elements of vecToExclude):\r\n- loop(4000) + shuffle(4000) + loop((1+100+1)*(100+1)/2 == 5 151)\r\n- loop(((1+100)*100/2 == 5 050 + (4000-100)*100) == 395 050) + shuffle(3900)\r\nSo it's 13k vs 399k cycles even when it's the worst case for current code.\r\n\r\nBut let's take this to extreme. We keep vecMasternodesUsed at 90% max of masternode count, so say it's completely full and we need to exclude 4000*0.9=3600 and we are extremely unlucky again (first 3600 masternodes match elements of vecToExclude). You can do the math but it's ~6.5m vs ~7.92m cycles.\r\n\r\nSo, unless I'm missing smth in code or math above, I doubt that there is any improvement in this. Not to mention that we still should have pretty good chances to find the first one on avg a bit quicker than for the worst case scenario I used in examples above."}}
{"actor":{"display_login":"UdjinM6"}}