)]}'
{"/COMMIT_MSG":[{"author":{"_account_id":7730,"name":"Sahid Orentino Ferdjaoui","email":"sahid.ferdjaoui@industrialdiscipline.com","username":"sahid"},"change_message_id":"b2380ca61d655c172ec48d68d796578676f2f209","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_097e6ae4","line":10,"updated":"2015-03-26 16:10:12.000000000","message":"Hum... \"from quadratic to linear\" not sure to see where is the quadratic and how you pass it to linear :-). But it\u0027s sure by using set you remove duplicate uuids.\n\n  O(N) + O(M) + O(P) \u003d O(N+M+P) that is not quadratic ?","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":5511,"name":"Nikola Dipanov","email":"ndipanov@redhat.com","username":"ndipanov"},"change_message_id":"4b5c83689bdc97836e4659c3e30617bba5fd4b94","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_5f62e4d9","line":10,"in_reply_to":"fa963961_097e6ae4","updated":"2015-03-26 16:28:45.000000000","message":"every iteration of the outer loop we do a \u0027if uuid not in existed\u0027 where existed is a list, so that\u0027s m*n in the worst case - no?","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":5511,"name":"Nikola Dipanov","email":"ndipanov@redhat.com","username":"ndipanov"},"change_message_id":"ea802608e88598ef13b966daf060b4c66dbc231e","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_84cc8636","line":10,"in_reply_to":"fa963961_5079aefb","updated":"2015-03-27 09:02:51.000000000","message":"@Kallebe \"So by removing the duplicates you have less uuids in the check \"if uuid not in existed\" that is not true - checking if a string (UUID) is in a set is a O(1) operation - we just hash the string. Checking if a string is in a list of strings consists of traversing the list and comparing every string.\n\n@Joe - I don\u0027t expect this to have a massive impact on performance overall, but was an obvious and easy win.\n\nmicro benchmark here (hint: no surprises, sets are much faster) https://gist.github.com/djipko/6564b8e41a24da05fbb9","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":14271,"name":"Kallebe Monteiro","email":"kallebe.monteiro@lsbd.ufc.br","username":"kallebe"},"change_message_id":"9f2083c7965e7eeaf304c16928206d7543a75cf7","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_62206bf8","line":10,"in_reply_to":"fa963961_5f62e4d9","updated":"2015-03-26 16:57:40.000000000","message":"I think sahid is right, because the change from list to set only removes the duplicates. Previously, with list you could have\n\nL \u003d len(existed) \u003d O(I) + O(M) + O(Orphans) \u003d O(3*M) (supposing M is the largest one)\n\nWith set, you have:\n\nS \u003d len(existed) \u003d O(I) + O(M) + O(Orphans) - duplicates \u003c\u003d O(3*M)\n\nSo by removing the duplicates you have less uuids in the check \"if uuid not in existed\".\n\nThe for is indeed O(self.claim.keys * L) or O(self.claim.keys * S) with S \u003c L. So your change improves the efficiency, but not changing from O(n²) to O(n)","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":1849,"name":"Joe Gordon","email":"joe.gordon0@gmail.com","username":"jogo"},"change_message_id":"93a036912d5cab9bbf8d732407bf08758befed61","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_5079aefb","line":10,"in_reply_to":"fa963961_62206bf8","updated":"2015-03-26 19:02:27.000000000","message":"how about a microbenchmark to see how big of a speedup this really gives us?","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":14271,"name":"Kallebe Monteiro","email":"kallebe.monteiro@lsbd.ufc.br","username":"kallebe"},"change_message_id":"eb7a8bf4de59082288ebc7fa2c3c1f1e624f8b7e","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_5311a2ab","line":10,"in_reply_to":"fa963961_73ab868a","updated":"2015-03-27 11:05:48.000000000","message":"Found this post explaining that https://home.regit.org/2014/11/python-search-string-in-a-set-of-strings/","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":14271,"name":"Kallebe Monteiro","email":"kallebe.monteiro@lsbd.ufc.br","username":"kallebe"},"change_message_id":"fd23b48e6477d943b297e981576ea243207e885f","unresolved":false,"context_lines":[{"line_number":7,"context_line":"PCI tracker: make O(M * N) clean_usage algo linear"},{"line_number":8,"context_line":""},{"line_number":9,"context_line":"By using sets instead of lists we can cut the runtime of a piece of code"},{"line_number":10,"context_line":"that runs on every periodic resource update form quadratic to linear."},{"line_number":11,"context_line":"Easy win."},{"line_number":12,"context_line":""},{"line_number":13,"context_line":"Change-Id: I7b0c1eb8188a428bf7e9f8dee710e9c46ed276eb"}],"source_content_type":"text/x-gerrit-commit-message","patch_set":1,"id":"fa963961_73ab868a","line":10,"in_reply_to":"fa963961_84cc8636","updated":"2015-03-27 10:57:04.000000000","message":"Ok, then. You are right. Better than expected then :) Good change. Thanks.","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"}],"nova/pci/manager.py":[{"author":{"_account_id":6450,"name":"Hans Lindgren","email":"hanlind@kth.se","username":"hanlind"},"change_message_id":"3be072065018766636ae8a1fc34bb34d748e0fe6","unresolved":false,"context_lines":[{"line_number":253,"context_line":"        \"\"\""},{"line_number":254,"context_line":"        existed \u003d set([inst[\u0027uuid\u0027] for inst in instances])"},{"line_number":255,"context_line":"        existed |\u003d set([mig[\u0027instance_uuid\u0027] for mig in migrations])"},{"line_number":256,"context_line":"        existed |\u003d set([inst[\u0027uuid\u0027] for inst in orphans])"},{"line_number":257,"context_line":""},{"line_number":258,"context_line":"        for uuid in self.claims.keys():"},{"line_number":259,"context_line":"            if uuid not in existed:"}],"source_content_type":"text/x-python","patch_set":1,"id":"fa963961_fece3a82","line":256,"updated":"2015-03-27 13:21:34.000000000","message":"While at it you could also turn the list comprehensions into generator expressions.","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"},{"author":{"_account_id":5511,"name":"Nikola Dipanov","email":"ndipanov@redhat.com","username":"ndipanov"},"change_message_id":"340b858c66f6a33bdac86cb890e945baee1dc9e9","unresolved":false,"context_lines":[{"line_number":253,"context_line":"        \"\"\""},{"line_number":254,"context_line":"        existed \u003d set([inst[\u0027uuid\u0027] for inst in instances])"},{"line_number":255,"context_line":"        existed |\u003d set([mig[\u0027instance_uuid\u0027] for mig in migrations])"},{"line_number":256,"context_line":"        existed |\u003d set([inst[\u0027uuid\u0027] for inst in orphans])"},{"line_number":257,"context_line":""},{"line_number":258,"context_line":"        for uuid in self.claims.keys():"},{"line_number":259,"context_line":"            if uuid not in existed:"}],"source_content_type":"text/x-python","patch_set":1,"id":"fa963961_3e9f0205","line":256,"in_reply_to":"fa963961_fece3a82","updated":"2015-03-27 13:30:14.000000000","message":"Done","commit_id":"2e0f130e7fae4fd18de3b3bd2eb04078314f8927"}]}