{"action":"created","issue":{"url":"https://api.github.com/repos/ZerBea/hcxtools/issues/46","repository_url":"https://api.github.com/repos/ZerBea/hcxtools","labels_url":"https://api.github.com/repos/ZerBea/hcxtools/issues/46/labels{/name}","comments_url":"https://api.github.com/repos/ZerBea/hcxtools/issues/46/comments","events_url":"https://api.github.com/repos/ZerBea/hcxtools/issues/46/events","html_url":"https://github.com/ZerBea/hcxtools/issues/46","id":347652886,"node_id":"MDU6SXNzdWUzNDc2NTI4ODY=","number":46,"title":"Performance bottleneck in addapstaessid","user":{"login":"ChrisLundquist","id":181256,"node_id":"MDQ6VXNlcjE4MTI1Ng==","avatar_url":"https://avatars1.githubusercontent.com/u/181256?v=4","gravatar_id":"","url":"https://api.github.com/users/ChrisLundquist","html_url":"https://github.com/ChrisLundquist","followers_url":"https://api.github.com/users/ChrisLundquist/followers","following_url":"https://api.github.com/users/ChrisLundquist/following{/other_user}","gists_url":"https://api.github.com/users/ChrisLundquist/gists{/gist_id}","starred_url":"https://api.github.com/users/ChrisLundquist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ChrisLundquist/subscriptions","organizations_url":"https://api.github.com/users/ChrisLundquist/orgs","repos_url":"https://api.github.com/users/ChrisLundquist/repos","events_url":"https://api.github.com/users/ChrisLundquist/events{/privacy}","received_events_url":"https://api.github.com/users/ChrisLundquist/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":10,"created_at":"2018-08-04T22:33:09Z","updated_at":"2018-08-06T18:53:36Z","closed_at":"2018-08-06T18:01:00Z","author_association":"NONE","body":"The algorithm here is accidentally N^2 with respect to pcap length and gets \"slower and slower\" as it continues to run.\r\n\r\n```\r\n-rw-r--r-- 1 clundquist clundquist  44G Aug  4 12:36 Kismet-20180709-18-35-12-1.pcapdump\r\n```\r\n\r\n```\r\nstart reading from /srv/wifi/Kismet-20180709-18-35-12-1.pcapdump\r\n28100000 packets processed - be patient!\r\n45900000 packets processed - be patient!\r\n51500000 packets processed - be patient!\r\n56300000 packets processed - be patient!\r\n69700000 packets processed - be patient!\r\n75700000 packets processed - be patient!\r\n111000000 packets processed - be patient!\r\n122000000 packets processed - be patient!\r\n156200000 packets processed - be patient!\r\n163500000 packets processed - be patient!\r\n164600000 packets processed - be patient!\r\n```\r\n\r\n```\r\n# top\r\n29419 clundqu+  20   0   50412  35880   2436 R 100.0  0.1  68:48.60 hcxpcaptool                                                                                                                            \r\n```  \r\n\r\n```\r\n# sudo perf top\r\n92.85%  hcxpcaptool              [.] addapstaessid                                                                                                                                                       \r\n```\r\n\r\n```\r\n  4.68 │ 50:   lea    0x1(%rbp),%rax                                                                                                                                                                       ▒\r\n  2.52 │       add    $0x36,%rbx                                                                                                                                                                           ▒\r\n  3.62 │       cmp    %r12,%rax                                                                                                                                                                            ▒\r\n       │     ↓ je     d0                                                                                                                                                                                   ▒\r\n  5.79 │       mov    %rax,%rbp                                                                                                                                                                            ▒\r\n  4.53 │ 60:   cmp    %r13b,0x15(%rbx)                                                                                                                                                                     ▒\r\n 64.78 │     ↑ jne    50                                                                                                                                                                                   ▒\r\n 12.21 │       mov    0x9(%rbx),%edi                                                                                                                                                                       ▒\r\n  0.05 │       cmp    %edi,(%r8)                                                                                                                                                                           ▒\r\n  1.39 │     ↑ jne    50   \r\n```\r\n\r\nThe above disassembler appears to be this hot code path (I haven't recompiled with debug symbols to verify since I want to let the run finish).\r\n```\r\n2487   zeiger = apstaessidliste;\r\n2488   for (c = 0; c < apstaessidcount; c++) {\r\n2489     if ((essidlen == zeiger->essidlen) &&\r\n2490         (memcmp(mac_ap, zeiger->mac_ap, 6) == 0) &&\r\n2491         (memcmp(mac_sta, zeiger->mac_sta, 6) == 0) &&\r\n2492         (memcmp(essid, zeiger->essid, zeiger->essidlen) == 0)) {\r\n2493       zeiger->status |= status;\r\n2494       return;\r\n2495     }\r\n2496     zeiger++;\r\n2497   }\r\n```\r\n\r\n\r\nThe algorithm here is roughly:\r\n* Check if our global list is allocated\r\n  * if it isn't allocated, make it now\r\n* Check if the given node is our our list (linear search)\r\n* If we didn't find it in our list realloc our list to 1 size bigger to make room (expensive as our list grows)\r\n* Assign our newest node at the end of the list\r\n\r\nThis boils down to \"Find or Create\".\r\n\r\nWe should update this algorithm to something closer to:\r\n\r\n* On start allocate our collection (to remove the branch from a hot code path)\r\n* use `bsearch` for the node\r\n  * If we find the node, we're done\r\n* Check if the collection has room (size == capacity)\r\n  * If we don't have room, allocate more slots, grow by perhaps `max(8, capacity / 4)`, update our capacity\r\n* If we don't find the node append it (ideally we would want an insertion sort)\r\n* qsort (ideally insertion would be better) the collection so that bsearch works next call\r\n\r\nAlternatively we could use a tree `tsearch` and friends, but iterating gets a little more complicated."},"comment":{"url":"https://api.github.com/repos/ZerBea/hcxtools/issues/comments/410814700","html_url":"https://github.com/ZerBea/hcxtools/issues/46#issuecomment-410814700","issue_url":"https://api.github.com/repos/ZerBea/hcxtools/issues/46","id":410814700,"node_id":"MDEyOklzc3VlQ29tbWVudDQxMDgxNDcwMA==","user":{"login":"ChrisLundquist","id":181256,"node_id":"MDQ6VXNlcjE4MTI1Ng==","avatar_url":"https://avatars1.githubusercontent.com/u/181256?v=4","gravatar_id":"","url":"https://api.github.com/users/ChrisLundquist","html_url":"https://github.com/ChrisLundquist","followers_url":"https://api.github.com/users/ChrisLundquist/followers","following_url":"https://api.github.com/users/ChrisLundquist/following{/other_user}","gists_url":"https://api.github.com/users/ChrisLundquist/gists{/gist_id}","starred_url":"https://api.github.com/users/ChrisLundquist/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ChrisLundquist/subscriptions","organizations_url":"https://api.github.com/users/ChrisLundquist/orgs","repos_url":"https://api.github.com/users/ChrisLundquist/repos","events_url":"https://api.github.com/users/ChrisLundquist/events{/privacy}","received_events_url":"https://api.github.com/users/ChrisLundquist/received_events","type":"User","site_admin":false},"created_at":"2018-08-06T18:53:36Z","updated_at":"2018-08-06T18:53:36Z","author_association":"NONE","body":"The next big win appears to be when we check the fcscrc32.\r\n\r\nWe spend about half our time there now instead of searching our data :)\r\n\r\n```\r\n  46.93%  hcxpcaptool      hcxpcaptool               [.] processpacket.part.29     \r\n```        \r\n\r\n```\r\n       │             crc = crc32table[(crc ^buffer[p]) & 0xff] ^(crc >> 8);\r\n  0.01 │ e0:   movzbl (%rcx),%esi\r\n  0.01 │       add    $0x1,%rcx\r\n 12.48 │       xor    %eax,%esi\r\n  2.71 │       shr    $0x8,%eax\r\n 11.16 │       movzbl %sil,%esi\r\n 73.29 │       xor    (%rdx,%rsi,4),%eax\r\n```\r\n                                                                                                                \r\n"}}
{"actor":{"display_login":"ChrisLundquist"}}