{"action":"created","issue":{"url":"https://api.github.com/repos/sfackler/rust-phf/issues/132","repository_url":"https://api.github.com/repos/sfackler/rust-phf","labels_url":"https://api.github.com/repos/sfackler/rust-phf/issues/132/labels{/name}","comments_url":"https://api.github.com/repos/sfackler/rust-phf/issues/132/comments","events_url":"https://api.github.com/repos/sfackler/rust-phf/issues/132/events","html_url":"https://github.com/sfackler/rust-phf/issues/132","id":383818756,"node_id":"MDU6SXNzdWUzODM4MTg3NTY=","number":132,"title":"Complexity of codegen algorithm","user":{"login":"derekdreery","id":1392222,"node_id":"MDQ6VXNlcjEzOTIyMjI=","avatar_url":"https://avatars0.githubusercontent.com/u/1392222?v=4","gravatar_id":"","url":"https://api.github.com/users/derekdreery","html_url":"https://github.com/derekdreery","followers_url":"https://api.github.com/users/derekdreery/followers","following_url":"https://api.github.com/users/derekdreery/following{/other_user}","gists_url":"https://api.github.com/users/derekdreery/gists{/gist_id}","starred_url":"https://api.github.com/users/derekdreery/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/derekdreery/subscriptions","organizations_url":"https://api.github.com/users/derekdreery/orgs","repos_url":"https://api.github.com/users/derekdreery/repos","events_url":"https://api.github.com/users/derekdreery/events{/privacy}","received_events_url":"https://api.github.com/users/derekdreery/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-11-23T13:07:48Z","updated_at":"2018-11-24T16:07:32Z","closed_at":null,"author_association":"NONE","body":"I've got a list of 14_000_000 passwords that I want to create a hash from. I'm finding that up to say 500_000 it completes more or less instantly, but at 1_000_000 it takes a long time (20mins+). I would guess anecdotally that the `build` step is O(n^2) or thereabouts. Has anyone else done perf work on the generation algorithm?\r\n\r\n# Some timings:\r\n\r\n - `100_000` - 1 sec\r\n - `500_000` - 40 sec\r\n - `1_000_000` - abort after 20 mins\r\n\r\n# Rough complexity\r\n\r\nUsing the first 2 results Gives time = k * size ^ n where n = 2.3, k = 3e-12, so for my 14_000_000 passwords I'm looking at about 24 hours :'( (modulo horrendous assumptions)"},"comment":{"url":"https://api.github.com/repos/sfackler/rust-phf/issues/comments/441377863","html_url":"https://github.com/sfackler/rust-phf/issues/132#issuecomment-441377863","issue_url":"https://api.github.com/repos/sfackler/rust-phf/issues/132","id":441377863,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0MTM3Nzg2Mw==","user":{"login":"derekdreery","id":1392222,"node_id":"MDQ6VXNlcjEzOTIyMjI=","avatar_url":"https://avatars0.githubusercontent.com/u/1392222?v=4","gravatar_id":"","url":"https://api.github.com/users/derekdreery","html_url":"https://github.com/derekdreery","followers_url":"https://api.github.com/users/derekdreery/followers","following_url":"https://api.github.com/users/derekdreery/following{/other_user}","gists_url":"https://api.github.com/users/derekdreery/gists{/gist_id}","starred_url":"https://api.github.com/users/derekdreery/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/derekdreery/subscriptions","organizations_url":"https://api.github.com/users/derekdreery/orgs","repos_url":"https://api.github.com/users/derekdreery/repos","events_url":"https://api.github.com/users/derekdreery/events{/privacy}","received_events_url":"https://api.github.com/users/derekdreery/received_events","type":"User","site_admin":false},"created_at":"2018-11-24T16:07:32Z","updated_at":"2018-11-24T16:07:32Z","author_association":"NONE","body":"That's strange - my experimentations suggests that if the construction is O(n^k) then 2 <= k <= 3, but the paper says k=1. The time definitely does not increase linearly with size as it is at the moment."}}
{"actor":{"display_login":"derekdreery"}}