{"comment":{"url":"https://api.github.com/repos/jgm/cmark/comments/11715326","html_url":"https://github.com/jgm/cmark/commit/cdcb65c5a209a1a3be4a1b9e804f5a4292127509#commitcomment-11715326","id":11715326,"user":{"login":"jgm","id":3044,"avatar_url":"https://avatars.githubusercontent.com/u/3044?v=3","gravatar_id":"","url":"https://api.github.com/users/jgm","html_url":"https://github.com/jgm","followers_url":"https://api.github.com/users/jgm/followers","following_url":"https://api.github.com/users/jgm/following{/other_user}","gists_url":"https://api.github.com/users/jgm/gists{/gist_id}","starred_url":"https://api.github.com/users/jgm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jgm/subscriptions","organizations_url":"https://api.github.com/users/jgm/orgs","repos_url":"https://api.github.com/users/jgm/repos","events_url":"https://api.github.com/users/jgm/events{/privacy}","received_events_url":"https://api.github.com/users/jgm/received_events","type":"User","site_admin":false},"position":null,"line":null,"path":"","commit_id":"cdcb65c5a209a1a3be4a1b9e804f5a4292127509","created_at":"2015-06-17T00:37:39Z","updated_at":"2015-06-17T00:37:39Z","body":"OK, tried your lightweight approach (if I understood it\nright).  Performance is a bit worse for the test case\nwith a million entities (roughly 96 vs 76) but I don't\nthink I'm too worried about that.  Performance shouldn't\nbe at all degraded for sources without many entities.\n\nIt did significantly reduce the binary size -- though as\nI explained in my last message, I'm still not sure why.\nI'm probably missing something simple.\n\nBest\nJohn\n\n+++ Nick Wellnhofer [Jun 16 15 15:26 ]:\n>   On 16/06/2015 22:04, John MacFarlane wrote:\n>   > I've pushed a change to master replacing the gperf hash\n>   > lookup with a binary search. If you have a chance, could\n>   > you have a look at what I've done and let me know if it\n>   > looks sane? It shaves off > 100K from the binary, and\n>   > there's not a noticeable performance hit.\n>   This is not quite what I had in mind but it's an interesting approach.\n>   I can see to failure cases:\n>   * A random invalid entity string can hash to the same value as a\n>   valid one. For example, `&foobarbaz;` could hash to the same\n>   value as `&gt;`.\n>   * There might be hash collisions between valid entity strings.\n>   I didn't check, but it's entirely possible that there are.\n>   What I had in mind is a simple struct like\n>   struct cmark_entity_node {\n>   char *entity_string;\n>   unsigned char replacement_bytes[8];\n>   };\n>   Then do a binary search on a sorted array of these nodes in C with\n>   `entity_string` as key. This involves a lot of string comparisons which\n>   makes\n>   things slower than comparing hash values. But it reduces the size of\n>   the\n>   binary even further.\n>   If you think this is too slow, another approach is to precompute a\n>   traditional, non-perfect hash table. Preferably using open addressing\n>   to\n>   reduce the overall table size.\n>   Nick\n>\n>   —\n>   Reply to this email directly or [1]view it on GitHub.\n>\n>References\n>\n>   1. https://github.com/jgm/cmark/commit/cdcb65c5a209a1a3be4a1b9e804f5a4292127509#commitcomment-11713751\n"}}