{"id":21,"date":"2007-10-21T10:01:26","date_gmt":"2007-10-21T15:01:26","guid":{"rendered":"http:\/\/steve.vinoski.net\/blog\/2007\/10\/21\/faster-wf-still\/"},"modified":"2007-10-21T10:01:26","modified_gmt":"2007-10-21T15:01:26","slug":"faster-wf-still","status":"publish","type":"post","link":"https:\/\/steve.vinoski.net\/blog\/2007\/10\/21\/faster-wf-still\/","title":{"rendered":"Faster WF Still"},"content":{"rendered":"<p>OK, so you could say that I&#8217;m a bit obsessed with <a href=\"http:\/\/www.tbray.org\/ongoing\/When\/200x\/2007\/09\/20\/Wide-Finder\">Tim Bray&#8217;s Wide Finder project<\/a>. Just a little. I mean, I started this blog just a few weeks ago and so far almost every posting has been about it:<\/p>\n<ul>\n<li><a href=\"\/blog\/2007\/09\/23\/tim-bray-and-erlang\/\">Tim Bray and Erlang<\/a><\/li>\n<li><a href=\"\/blog\/2007\/09\/29\/more-file-processing-with-erlang\/\">More File Processing with Erlang<\/a><\/li>\n<li><a href=\"\/blog\/2007\/10\/14\/one-more-erlang-wide-finder\/\">One More Erlang Wide Finder<\/a><\/li>\n<li><a href=\"\/blog\/2007\/10\/18\/ok-just-one-more-wf\/\">OK, Just One More WF<\/a><\/li>\n<\/ul>\n<p>There&#8217;s also my Sept.\/Oct. <a href=\"http:\/\/computer.org\/internet\/\">Internet Computing<\/a> column, <a href=\"http:\/\/dsonline.computer.org\/portal\/pages\/dsonline\/2007\/10\/w5tow.html\"><em>Concurrency with Erlang<\/em><\/a>, and sometime in early November, my next column, entitled <em>Reliability with Erlang<\/em>, will be published. Neither column is connected at all to the Wide Finder, but they just further reveal my current obsession with Erlang.<\/p>\n<p>In my <a href=\"\/blog\/2007\/10\/18\/ok-just-one-more-wf\/\">previous post<\/a> I described my fastest solution up to that point, but here&#8217;s an even faster one: <a href=\"\/code\/tbray16.erl\"><code>tbray16.erl<\/code><\/a>, which is identical in every way to <a href=\"\/code\/tbray15.erl\"><code>tbray15.erl<\/code><\/a> from my previous post except that it uses <a href=\"\/code\/wfbm4.erl\"><code>wfbm4.erl<\/code><\/a>, which provides all the performance gains. This version of Boyer-Moore searching includes two simple tweaks:<\/p>\n<ul>\n<li>Uses hard-coded constants for string lengths, since the strings are fixed, rather than constantly recalculating them with <code>length\/1<\/code>.<\/li>\n<li>Fixes a nagging problem with my Boyer-Moore implementation where it wasn&#8217;t handling repeated characters in the fixed pattern very well. What I did in the previous version was choose the lesser of the two shifts if both characters appeared in the pattern, which worked but isn&#8217;t technically correct, and it also meant two <code>dict<\/code> lookups to get the shift values rather than just one. Now, I do the right thing: just keep track of the number of comparisons and subtract that from the shift value, use that if the result is positive and non-zero, otherwise just shift by 1.<\/li>\n<\/ul>\n<p>This version shaves another whole second off the previous version for about a 25% speedup. The fastest I&#8217;ve seen it run on my 8-core Linux box is:<\/p>\n<pre><code>real    0m3.107s\r\nuser    0m16.243s\r\nsys     0m2.134s<\/code><\/pre>\n<p>Meanwhile, Anders Nygren has been exploring <a href=\"http:\/\/www.erlang.org\/pipermail\/erlang-questions\/2007-October\/030029.html\">eliminating using the <code>dict<\/code> altogether for the shift value lookup<\/a>, but nothing I&#8217;ve tried there has been an improvement. But thanks to Anders for prompting me to properly fix that Boyer-Moore code and at least eliminate one of the <code>dict<\/code> lookups.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>OK, so you could say that I&#8217;m a bit obsessed with Tim Bray&#8217;s Wide Finder project. Just a little. I mean, I started this blog just a few weeks ago and so far almost every posting has been about it: Tim Bray and Erlang More File Processing with Erlang One More Erlang Wide Finder OK, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,12],"tags":[],"class_list":["post-21","post","type-post","status-publish","format-standard","hentry","category-erlang","category-performance"],"_links":{"self":[{"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/posts\/21","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/comments?post=21"}],"version-history":[{"count":0,"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/posts\/21\/revisions"}],"wp:attachment":[{"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/media?parent=21"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/categories?post=21"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/steve.vinoski.net\/blog\/wp-json\/wp\/v2\/tags?post=21"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}