{"id":7027,"date":"2016-02-15T21:51:37","date_gmt":"2016-02-16T02:51:37","guid":{"rendered":"http:\/\/esr.ibiblio.org\/?p=7027"},"modified":"2016-02-16T12:16:07","modified_gmt":"2016-02-16T17:16:07","slug":"brute-force-beats-premature-optimization","status":"publish","type":"post","link":"http:\/\/esr.ibiblio.org\/?p=7027","title":{"rendered":"Brute force beats premature optimization"},"content":{"rendered":"<p>I made a really common and insidious programming mistake recently.  I&#8217;m going to explain it in detail because every programmer in the world needs the reminder <em>not to do this<\/em>, and I hope confessing that even &#8220;ESR&#8221; falls into such a trap will make the less experienced properly wary of it.<\/p>\n<p>Our sutra for today expounds on the sayings of the masters Donald Knuth and Ken Thompson, who in their wisdom have observed &#8220;Premature optimization is the root of all evil&#8221; and &#8220;When in doubt, use brute force.&#8221;<\/p>\n<p><!--more--><\/p>\n<p>My main side project recently has been <a href=\"http:\/\/www.catb.org\/esr\/src\/\">SRC<\/a>, a simple version-control system for small projects.  One of the constraints I was thinking about when I designed SRC was that the status command &#8211; the one that gives you a display saying which files have been modified since they were checked in &#8211; needs to be really fast.<\/p>\n<p>The reason it needs to be fast is that front-ends for CLIs like SRC&#8217;s tend to rely on it heavily and call it often.  This is, in particular, true of the VC front end in Emacs (which, as it happens, is also my code) &#8211; if the status command is slow, VC will be laggy.<\/p>\n<p>It turns out that all file status checks except one only have to look at inodes<br \/>\n(existence\/nonexistence, file size) and so are as fast as you can get if you&#8217;re going to hit the filesystem at all.  The exception is modified\/unmodified status &#8211; whether your workfile has been edited since it was checked out.<\/p>\n<p>My original plan was just to do a stat(2) on both the master and the workfile and compare modification dates.  That too would only touch the i-node and be fast, but there are a couple of problems with it.<\/p>\n<p>One is that stat(2) times only have 1-second resolution, so a workfile could look unmodified to &#8220;src status&#8221; even if had been changed within a second of checkout. That&#8217;s not good.<\/p>\n<p>The other problem is that, having gotten used to git and to build systems like waf and scons that evaluate &#8220;modified&#8221; based on <em>content<\/em> rather than last-write-time, I&#8217;ve gotten to really like that feature and wanted it in SRC.<\/p>\n<p>OK, so the naive brute-force way to do this would be to read out the last stored version from RCS and compare it byte-by-byte to the workfile.  That&#8217;s easy to do in Python, where one read call can pull the whole file into memory as a string.<\/p>\n<p>I didn&#8217;t do that, which was probably my first wrong turn.  Because of recent experience with repository conversions, I was mentally fixated on very large test loads &#8211; my gut told me to avoid the overhead of reading out the last stored version from RCS every time I wanted to check status, and instead do the obvious trick with a content hash.  That is, keep a hash of the last stored version, hash the workfile on each status check, and compare the two.<\/p>\n<p>Have you already spotted my error here?  I didn&#8217;t <em>measure<\/em>.  Before time-optimizing, I should have coded the naive version, then timed a bunch of status checks to see if there was any noticeable wall-time lag.<\/p>\n<p>I say &#8220;probably&#8221; my first wrong turn because I quickly coded a hash-based implementation that worked without fuss, so I got away with it for a while.  But&#8230;<\/p>\n<p>&#8230;the way I did it was inelegant, and that bothered me.  At that time I couldn&#8217;t think of a reasonable way to store the hash in the RCS master, so I dropped it outboard in a stamp file.  That is, for each RCS master foo,v there was a parallel foo.srcstamp that existed just to hold the content hash from the last checkin.<\/p>\n<p>I didn&#8217;t like this.  I wanted each unit of history to correspond to <em>one<\/em> unit of storage, preferably to an eyeball-friendly flat file.  If you do not understand why I wanted this, sigh&#8230;go slam your noggin against a copy of <cite>The Art of UNIX Programming<\/cite> until you achieve enlightenment.<\/p>\n<p>Then I wrote an SCCS back end &#8211; and had the kludgy idea that I could <a href=\"http:\/\/esr.ibiblio.org\/?p=7023\">recruit the description field in an SCCS master as a key-value store<\/a> to simulate the named symbols that RCS\/SRC has but SCCS doesn&#8217;t.<\/p>\n<p>I still haven&#8217;t done that.  But I wrote trial implementations in the RCS and SCCS back ends that gave me that general key-value store &#8211; RCS also has a description field that can be hijacked.  Tested them and they worked.<\/p>\n<p>The inevitable occurred.  I thought: &#8220;Hey, why don&#8217;t I put the checkin hash in the key-value store, and get rid of those ugly stamp files?&#8221;<\/p>\n<p>So I coded it, and it passed my regression-test suite &#8211; though the function where all the hash-check magic was taking place, modified(), seemed ugly and unpleasantly complex.<\/p>\n<p>I shipped this as 1.8 &#8211; and promptly got a report that <a href=\"http:\/\/esr.ibiblio.org\/?p=7020&#038;cpage=1#comment-1688201\">status checking was broken<\/a>,  A few minutes of repeating the test sequence I&#8217;d been given with increased instrumentation established that the problem was somewhere in the logic of modified().<\/p>\n<p>I stared at modified() for a while, tried to fix to fix it, and failed.  Then I had a rush of sense to the head, replaced the guts of modified() with the stupidest possible brute-force content comparison, and shipped that as 1.9.<\/p>\n<p>Do you see what happened here?  I got mugged by complexity creep &#8211; ended up with code I couldn&#8217;t mentally model properly, afflicted with tricky edge cases, and it broke.  My own damn fault, because I optimized before I measured and one thing led to another.<\/p>\n<p><em>Don&#8217;t do this.<\/em>  Well, not unless you really <em>want<\/em> Master Foo to materialize and whack you upside the head with his shippei (you should be so lucky).<\/p>\n<p>Now I&#8217;m going to do what I should have done in the first place &#8211; not write the fscking optimization until someone tells me the stupid-simple method actually causes a performance problem.  And, you know, it may not ever.  Seek-induced latency is not the scourge it once was; SSDs are wonderful things that way.<\/p>\n<p>Furthermore, the thing I should have remembered is that RCS optimizes for retrieving recent versions by storing delta backwards from a whole-text tip version, rather than forwards from the initial version as SCCS does.  So under RCS tip checkout is mostly a copy from a span of the master file eather than the longest possible sequence of change-delta integrations, and probably reasonably fast.<\/p>\n<p>The only scar tissue left is that I&#8217;ve still got about 40 lines of now-unused key-value store implementation in the code &#8211; sitting quietly, doing nothing.  I&#8217;m sure it&#8217;ll come in useful someday, especially if someone turns up with an actual need for named symbols under the SCCS back end. <\/p>\n<p>I shall regard it as a test of my discipline and detachment, not to do anything with it until I <em>actually need to<\/em>.<\/p>\n<p>Thus, we gain merit by not coding.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I made a really common and insidious programming mistake recently. I&#8217;m going to explain it in detail because every programmer in the world needs the reminder not to do this, and I hope confessing that even &#8220;ESR&#8221; falls into such a trap will make the less experienced properly wary of it. Our sutra for today&hellip; <a class=\"more-link\" href=\"http:\/\/esr.ibiblio.org\/?p=7027\">Continue reading <span class=\"screen-reader-text\">Brute force beats premature optimization<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23,13],"tags":[46],"class_list":["post-7027","post","type-post","status-publish","format-standard","hentry","category-hacker-culture","category-software","tag-version-control","entry"],"_links":{"self":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7027","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=7027"}],"version-history":[{"count":4,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7027\/revisions"}],"predecessor-version":[{"id":7031,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7027\/revisions\/7031"}],"wp:attachment":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7027"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7027"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7027"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}