{"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":0,"created_at":"2018-11-23T13:07:48Z","updated_at":"2018-11-24T13:09:57Z","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/441366865","html_url":"https://github.com/sfackler/rust-phf/issues/132#issuecomment-441366865","issue_url":"https://api.github.com/repos/sfackler/rust-phf/issues/132","id":441366865,"node_id":"MDEyOklzc3VlQ29tbWVudDQ0MTM2Njg2NQ==","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-24T13:09:57Z","updated_at":"2018-11-24T13:09:57Z","author_association":"NONE","body":"I've created a fork for profiling at https://github.com/derekdreery/rust-phf/tree/prof_work/phf_bench . I've been using\r\n\r\n```\r\nvalgrind --tool=callgrind --dump-instr=yes --collect-jumps=yes --simulate-cache=yes ../target/release/phf_bench\r\n```\r\n\r\nto generate callgrind files, and KCacheGrind to view them, but I'm not really enough of an expert at viewing the output to work out what it means. \r\n\r\nCan anyone help? Here is the output:\r\n\r\n[callgrind.out.3154.txt](https://github.com/sfackler/rust-phf/files/2612257/callgrind.out.3154.txt)\r\n"}}
{"actor":{"display_login":"derekdreery"}}