{"action":"created","issue":{"url":"https://api.github.com/repos/otwcode/otwarchive/issues/2531","repository_url":"https://api.github.com/repos/otwcode/otwarchive","labels_url":"https://api.github.com/repos/otwcode/otwarchive/issues/2531/labels{/name}","comments_url":"https://api.github.com/repos/otwcode/otwarchive/issues/2531/comments","events_url":"https://api.github.com/repos/otwcode/otwarchive/issues/2531/events","html_url":"https://github.com/otwcode/otwarchive/pull/2531","id":176524040,"number":2531,"title":"AO3-4635 Attempt at some matching speed improvements.","user":{"login":"tickinginstant","id":20977630,"avatar_url":"https://avatars.githubusercontent.com/u/20977630?v=3","gravatar_id":"","url":"https://api.github.com/users/tickinginstant","html_url":"https://github.com/tickinginstant","followers_url":"https://api.github.com/users/tickinginstant/followers","following_url":"https://api.github.com/users/tickinginstant/following{/other_user}","gists_url":"https://api.github.com/users/tickinginstant/gists{/gist_id}","starred_url":"https://api.github.com/users/tickinginstant/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tickinginstant/subscriptions","organizations_url":"https://api.github.com/users/tickinginstant/orgs","repos_url":"https://api.github.com/users/tickinginstant/repos","events_url":"https://api.github.com/users/tickinginstant/events{/privacy}","received_events_url":"https://api.github.com/users/tickinginstant/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/otwcode/otwarchive/labels/Has%20Migrations","name":"Has Migrations","color":"207de5"},{"url":"https://api.github.com/repos/otwcode/otwarchive/labels/Priority:%20High","name":"Priority: High","color":"e102d8"}],"state":"open","locked":false,"assignee":{"login":"shalott","id":415001,"avatar_url":"https://avatars.githubusercontent.com/u/415001?v=3","gravatar_id":"","url":"https://api.github.com/users/shalott","html_url":"https://github.com/shalott","followers_url":"https://api.github.com/users/shalott/followers","following_url":"https://api.github.com/users/shalott/following{/other_user}","gists_url":"https://api.github.com/users/shalott/gists{/gist_id}","starred_url":"https://api.github.com/users/shalott/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shalott/subscriptions","organizations_url":"https://api.github.com/users/shalott/orgs","repos_url":"https://api.github.com/users/shalott/repos","events_url":"https://api.github.com/users/shalott/events{/privacy}","received_events_url":"https://api.github.com/users/shalott/received_events","type":"User","site_admin":false},"assignees":[{"login":"shalott","id":415001,"avatar_url":"https://avatars.githubusercontent.com/u/415001?v=3","gravatar_id":"","url":"https://api.github.com/users/shalott","html_url":"https://github.com/shalott","followers_url":"https://api.github.com/users/shalott/followers","following_url":"https://api.github.com/users/shalott/following{/other_user}","gists_url":"https://api.github.com/users/shalott/gists{/gist_id}","starred_url":"https://api.github.com/users/shalott/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shalott/subscriptions","organizations_url":"https://api.github.com/users/shalott/orgs","repos_url":"https://api.github.com/users/shalott/repos","events_url":"https://api.github.com/users/shalott/events{/privacy}","received_events_url":"https://api.github.com/users/shalott/received_events","type":"User","site_admin":false}],"milestone":null,"comments":11,"created_at":"2016-09-13T01:13:43Z","updated_at":"2016-09-19T15:30:43Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/otwcode/otwarchive/pulls/2531","html_url":"https://github.com/otwcode/otwarchive/pull/2531","diff_url":"https://github.com/otwcode/otwarchive/pull/2531.diff","patch_url":"https://github.com/otwcode/otwarchive/pull/2531.patch"},"body":"https://otwarchive.atlassian.net/browse/AO3-4635\r\n\r\nThis pull request is a draft of some code intended to speed up the potential match generation system through various methods. My explanation of the changes and the effects got a bit long-winded, sorry!\r\n\r\n# Speeding up Prompt.match\r\n\r\nTagSet.with_type always triggers a database query, and it can be called up to five times per tag type (three times for one tag set, twice for the other) in a single call to Prompt.match. So I created a new function, TagSet.tag_ids_by_type, which creates a hash mapping from tag types to lists of tag IDs, and then caches the result to avoid duplicate computation. This makes it much faster to compare tag-sets. And since matching can only be run when signups are closed, there shouldn't be any danger of the tags changing out from under the matching code, so that kind of computation caching should be fine.\r\n\r\nI also tried to make Prompt.match slightly more efficient by having it cache the full tag set (base tag set plus optional tag set) that it creates during Prompt.match. In addition, since it's inefficient for Prompt.match to load individual tagsets one-by-one (even if it's not doing it as frequently), I added some scopes with includes() statements to the ChallengeSignup class, to make it easier to ensure that all of the relevant data is loaded along with each challenge signup.\r\n\r\n# Processing in batches, and indexing prompts\r\n\r\nIn the class PotentialMatcherConstrained, the new code processes all matches in batches. It divides all signups into batches of 100, and then for each pair of batches, it performs two computations: one to generate all signup matches when the signups in the first batch are acting as requests, and one to generate all signup matches when the signups in the second batch are acting as requests. Each batch is represented by a class PromptBatch, which builds an index in Ruby mapping from tag ids to lists of prompts, so that it's easier to look up \"candidate\" matches for a prompt -- prompts that are likely to produce prompt matches.\r\n\r\nFor each signup in the request batch, we iterate through its prompt requests, find candidates in the offer batch, and then try to build PotentialPromptMatch objects by calling Prompt.match. Once all of the prompt matches have been generated between that request signup and the offer batch, we group them by offer signup ID, and then try to build and save PotentialMatch objects for that request.\r\n\r\nThis has two advantages, at least in theory: it should reduce the number of SQL queries in most cases (since SQL is only used for loading batches and saving PotentialMatches), and it should reduce the number of calls to Prompt.match in many cases.\r\n\r\n# Miscellaneous Notes\r\n\r\n**Progress:** The way that I did the batching meant that each request was processed more than once (in fact, once for each offer batch), so it wasn't possible to keep the same username-based progress system. Instead, I switched over to showing only percents (but with two decimals of precision, so that for long-running matching tasks, the user has some indication that it's still going).\r\n\r\n**Index Type:** PotentialMatcherConstrained only uses tags of a single tag type to look up \"candidate\" matches. Originally, I used the first required type as the \"index type,\" but this isn't always ideal. For example, in a single-fandom ship-based exchange where the organizer requires a match on fandom (like my second experiment), *everyone* is going to have the same fandom marked in all of their prompts, so looking up prompts by that tag isn't particularly useful.\r\n\r\nSo I added a pre-processing step that tries to check, for each of the required tag types, whether it would make a \"good\" index type. If there are any good index types, it uses the first; otherwise, it falls back to using the first required type. This adds a little extra time to the matching, but in my experiments the slowdown is only 1-2%, and it should provide a significant improvement in, e.g. character-based single fandom exchanges where the mod lists \"fandoms\" as one of the required tag types.\r\n\r\n**Batch Size:** I picked a batch-size of 100 somewhat arbitrarily -- I wanted it to be large enough to provide an improvement, but not too large (since each batch would also have to load all related prompts, tagsets, and tags). I think 100 is probably a good size for the tests that I was doing, where most signups had under 100 tags, but it might be necessary to go smaller for an exchange with really high limits. Maybe it would be good to adjust the batch sizes based on the challenge's prompt requirements?\r\n\r\n**Limits on Matching:** In order to introduce batching the way that I did, I had to forego any limits on the matches, because batching affects the order of processing (and means that if you stop after reaching a minimum number of matches, you're not going to get an even distribution of matches).\r\n\r\nIn the tests that I ran with \"sparse\" matching graphs (relatively small ratio of PotentialMatches to ChallengeSignups), this didn't seem to be much of a problem. And when there are no required types, I have some special-case code in PotentialMatcherUnconstrained that samples random offer IDs to pair with each request (so that it doesn't generate the complete graph). But that's not the only way to have basically unconstrained matching. I have some ideas about maybe trying to add a fall-back to the original matching code if there are no \"good\" index types, but I'm not sure that would catch all of the tricky cases.\r\n\r\n# Testing\r\n\r\nI added some cucumber tests for generating signups for small exchanges, and then checking whether the correct PotentialMatches were generated. (In the process of writing them, I found and corrected a small bug in the original potential matching code, which could occasionally cause two copies of the same PotentialMatch to be generated.)\r\n\r\nIn order to tell whether I was making progress speed-wise, I also wrote some code to generate fake signups for a couple of test exchanges, to evaluate runtimes.\r\n\r\n* Exchange A is a multi-fandom exchange that requires matching fandoms and 1 matching ship, and has ~150 participants.\r\n\r\n* Exchange B is a single-fandom exchange that requires matching fandoms and 1 matching ship, and has ~75 participants. It also has \"fandom\" as one of the required tag types, has more prompts per signup, and has nearly twice as many potential matches as Exchange A (despite only having half as many participants). I believe that's why matching takes longer than the larger exchange.\r\n\r\n* Exchange C is a multi-fandom exchange that requires matching fandoms and all matching characters, and has ~200 participants. It's also very sparse -- there's an average of about 1.5 potential matches per participant, and a lot of participants have no potential matches.\r\n\r\n|                            | Exchange A  | Exchange B  | Exchange C  |\r\n|----------------------------|-------------|-------------|-------------|\r\n| original code              | 102 minutes | 240 minutes | 8.7 minutes |\r\n| only Prompt.match changes  | 5.7 minutes | 8.5 minutes | 1.3 minutes |\r\n| all changes                | 1.5 minutes | 2.0 minutes | 0.9 minutes |\r\n\r\nTo get the times, I used ruby's Benchmark.measure on a call to PotentialMatch.generate_in_background. (So all of the times include checking for invalid signups, potential match generation, and assignment generation.) I ran all of the experiments on a vagrant box on my laptop. Obviously, this doesn't necessarily indicate anything about how this code might perform on real data in production, and there's a fair amount of variation in how much of an improvement it might be, but it seems like a promising direction."},"comment":{"url":"https://api.github.com/repos/otwcode/otwarchive/issues/comments/248027217","html_url":"https://github.com/otwcode/otwarchive/pull/2531#issuecomment-248027217","issue_url":"https://api.github.com/repos/otwcode/otwarchive/issues/2531","id":248027217,"user":{"login":"shalott","id":415001,"avatar_url":"https://avatars.githubusercontent.com/u/415001?v=3","gravatar_id":"","url":"https://api.github.com/users/shalott","html_url":"https://github.com/shalott","followers_url":"https://api.github.com/users/shalott/followers","following_url":"https://api.github.com/users/shalott/following{/other_user}","gists_url":"https://api.github.com/users/shalott/gists{/gist_id}","starred_url":"https://api.github.com/users/shalott/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shalott/subscriptions","organizations_url":"https://api.github.com/users/shalott/orgs","repos_url":"https://api.github.com/users/shalott/repos","events_url":"https://api.github.com/users/shalott/events{/privacy}","received_events_url":"https://api.github.com/users/shalott/received_events","type":"User","site_admin":false},"created_at":"2016-09-19T15:30:43Z","updated_at":"2016-09-19T15:30:43Z","body":"OK, I confess I haven't line-by-lined all the scripts for generating the random exchanges, but will sit down and run them on my dev setup in the next few days and look them over some more, and everything else looks great to me. \r\n\r\nFYI, having talked to the team we would love to push this to staging soon: we have three deploys scheduled, and then I think this one will go next, early in October. Would you be available around then for consult if we turn up any issues? "}}
{"actor":{"display_login":"shalott"}}