{"action":"created","issue":{"url":"https://api.github.com/repos/Igalia/snabbswitch/issues/97","labels_url":"https://api.github.com/repos/Igalia/snabbswitch/issues/97/labels{/name}","comments_url":"https://api.github.com/repos/Igalia/snabbswitch/issues/97/comments","events_url":"https://api.github.com/repos/Igalia/snabbswitch/issues/97/events","html_url":"https://github.com/Igalia/snabbswitch/pull/97","id":117013654,"number":97,"title":"Add PodHashMap","user":{"login":"andywingo","id":1745903,"avatar_url":"https://avatars.githubusercontent.com/u/1745903?v=3","gravatar_id":"","url":"https://api.github.com/users/andywingo","html_url":"https://github.com/andywingo","followers_url":"https://api.github.com/users/andywingo/followers","following_url":"https://api.github.com/users/andywingo/following{/other_user}","gists_url":"https://api.github.com/users/andywingo/gists{/gist_id}","starred_url":"https://api.github.com/users/andywingo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andywingo/subscriptions","organizations_url":"https://api.github.com/users/andywingo/orgs","repos_url":"https://api.github.com/users/andywingo/repos","events_url":"https://api.github.com/users/andywingo/events{/privacy}","received_events_url":"https://api.github.com/users/andywingo/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/Igalia/snabbswitch/milestones/3","html_url":"https://github.com/Igalia/snabbswitch/milestones/v2.0","labels_url":"https://api.github.com/repos/Igalia/snabbswitch/milestones/3/labels","id":1415920,"number":3,"title":"v2.0","description":"Full fragmentation support, support for running in guest virtual machines, large binding tables, multiple lwaftrs per machine.","creator":{"login":"andywingo","id":1745903,"avatar_url":"https://avatars.githubusercontent.com/u/1745903?v=3","gravatar_id":"","url":"https://api.github.com/users/andywingo","html_url":"https://github.com/andywingo","followers_url":"https://api.github.com/users/andywingo/followers","following_url":"https://api.github.com/users/andywingo/following{/other_user}","gists_url":"https://api.github.com/users/andywingo/gists{/gist_id}","starred_url":"https://api.github.com/users/andywingo/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/andywingo/subscriptions","organizations_url":"https://api.github.com/users/andywingo/orgs","repos_url":"https://api.github.com/users/andywingo/repos","events_url":"https://api.github.com/users/andywingo/events{/privacy}","received_events_url":"https://api.github.com/users/andywingo/received_events","type":"User","site_admin":false},"open_issues":12,"closed_issues":2,"state":"open","created_at":"2015-11-17T14:24:27Z","updated_at":"2015-11-26T15:32:31Z","due_on":null,"closed_at":null},"comments":41,"created_at":"2015-11-15T19:57:29Z","updated_at":"2015-12-08T10:29:30Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/Igalia/snabbswitch/pulls/97","html_url":"https://github.com/Igalia/snabbswitch/pull/97","diff_url":"https://github.com/Igalia/snabbswitch/pull/97.diff","patch_url":"https://github.com/Igalia/snabbswitch/pull/97.patch"},"body":"This is a WIP PR -- it is an implementation of an open-addressed robin hood hash table with linear probing.  The implementation is designed to operate on cdata objects.\r\n\r\nThere is also an attempt at a caching layer, the idea being that if only 1MB of your 40MB table is hot, you can get better perf by adding a cache table.  That table would maximize cache line utilization and also reduce TLB misses.  It works well on my i7 laptop but I think not so well on interlaken.  The best-case perf of adding a cache should be significantly better but in the pessimal case that every lookup misses the cache, total perf would be worse.  Dunno, it exposes the same interface, so you can choose.\r\n\r\nResults on interlaken:\r\n\r\n```\r\nwingo@interlaken:~/snabbswitch/src$ ./snabb snsh apps/lwaftr/phmtest.lua\r\nhash rate test\r\n574.5279184241 million hashes per second (final result: 1543808256)\r\ninsertion rate test\r\n5.0559188134633 million insertions per second\r\nverification\r\nlookup speed test (hits, uniform distribution)\r\n15.615401383563 million lookups per second (final result: 4602468)\r\nlookup speed test (hits, only 16K active entries)\r\n29.995174646259 million lookups per second (final result: 8149854)\r\nlookup speed test (hits, only 16K active entries, 64K entry cache)\r\n32.036958553015 million lookups per second (final result: 23391)\r\nlookup speed test (warm cache hits, only 16K active entries, 64K entry cache)\r\n32.969044296113 million lookups per second (final result: 23391)\r\ncache usage: 32767/65536\r\ncache verification\r\nsuccess\r\n```\r\n\r\nThis PR also includes a simple hash function, one of Bob Jenkins'.  Anyway.  Hashing appears to be ridiculously cheap; it's memory that's costly.  This E5-2620v3 appears to have a worst-case lookup rate of 15M lookups/second, or 66 nanoseconds/lookup.  This is about the cost of a cache miss/RAM fetch per lookup.  In this test, both keys and values are 4-byte integers; I think that given that the hash function is spreading out our lookups so that a cache line is only ever used for the hash and key, it doesn't matter how big the value is, for lookup time anyway.  I could have made 100 byte values is what I'm saying here.\r\n\r\nThe cache didn't appear to do anything for me.  I guess TLB misses aren't a consideration for us, and really if they are, we should be asking for huge pages instead.\r\n\r\nCc @lukego @kbara for their thoughts, if you have any :)"},"comment":{"url":"https://api.github.com/repos/Igalia/snabbswitch/issues/comments/162842487","html_url":"https://github.com/Igalia/snabbswitch/pull/97#issuecomment-162842487","issue_url":"https://api.github.com/repos/Igalia/snabbswitch/issues/97","id":162842487,"user":{"login":"kbara","id":1588250,"avatar_url":"https://avatars.githubusercontent.com/u/1588250?v=3","gravatar_id":"","url":"https://api.github.com/users/kbara","html_url":"https://github.com/kbara","followers_url":"https://api.github.com/users/kbara/followers","following_url":"https://api.github.com/users/kbara/following{/other_user}","gists_url":"https://api.github.com/users/kbara/gists{/gist_id}","starred_url":"https://api.github.com/users/kbara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kbara/subscriptions","organizations_url":"https://api.github.com/users/kbara/orgs","repos_url":"https://api.github.com/users/kbara/repos","events_url":"https://api.github.com/users/kbara/events{/privacy}","received_events_url":"https://api.github.com/users/kbara/received_events","type":"User","site_admin":false},"created_at":"2015-12-08T10:29:30Z","updated_at":"2015-12-08T10:29:30Z","body":"http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-manual-325462.pdf can be useful. Some parts are out of date, but it has quite a bit of info on available counters, etc."}}