{"id":7230,"date":"2016-09-17T08:30:12","date_gmt":"2016-09-17T12:30:12","guid":{"rendered":"http:\/\/esr.ibiblio.org\/?p=7230"},"modified":"2016-09-17T08:38:56","modified_gmt":"2016-09-17T12:38:56","slug":"thinking-like-a-master-programmer","status":"publish","type":"post","link":"http:\/\/esr.ibiblio.org\/?p=7230","title":{"rendered":"Thinking like a master programmer"},"content":{"rendered":"<p>To do large code changes correctly, factor them into a series of smaller steps such that each revision has a well-defined and provable relationship to the last.<\/p>\n<p>(This is the closest I&#8217;ve ever come to a 1-sentence answer to the question &#8220;How the <em>fsck<\/em> do you manage to code with such ridiculously high speed and low defect frequency? I was asked this yet again recently, and trying to translate the general principle into actionable advice has been on my mind. I have two particular NTPsec contributors in mind&#8230;)<\/p>\n<p>So here&#8217;s a case study, and maybe your chance to catch me in a mistake.<\/p>\n<p><!--more--><\/p>\n<p>NTP needs a 64-bit scalar type for calendar calculations; what it actually wants is 32 bits of seconds since a far-past epoch and 32 bits of fractional-second precision, which you can think of as a counter for units of seconds * 1e-32. (The details are a little messier than this, but never mind that for now.)<\/p>\n<p>Consequently, one of the archaisms in the NTP code is an internal type called vint64.  It dates from the era of 32-bit machines (roughly 1977 to 2008).  In those days you couldn&#8217;t assume your C compiler had int64_t or uint64_t (64-bit integer and unsigned-integer types).  Even after the 64-bit hardware transition, it was some years before you could safely assume that compilers for the remaining 32-bit machines (like today&#8217;s Raspberry Pis) would support int64_t\/uint64_t.<\/p>\n<p>Thus, a vint64 is an NTP structure wrapping 2 32-bit integers.  It comes with a bunch of small functions that do 64-bit scalar arithmetic using it. Also, sadly, there was a lot of code using it that didn&#8217;t go through the functional interface, instead exposing the guts of the vint64 structure in unclean ways.<\/p>\n<p>This is, for several reasons, an obvious cleanup target.  Today in 2016 we <em>can<\/em> assume that all compilers of interest to us have 64-bit scalars.  In fact the NTP code itself has long assumed this, though the assumption is so well-hidden in the ISC library off to the side that many people who have worked in the main codebase probably do not know it&#8217;s there.<\/p>\n<p>If all the vint64s in NTP became typedefs to a scalar 64-bit type, we could use native machine operations in most cases and replace a lot of function calls and ugly exposed guts with C&#8217;s arithmetic operators. The result would be more readable, less bulky, and more efficient.  In this case we&#8217;d only pare away about 300LOC, but relentless pursuit of such small improvements adds up to large ones.<\/p>\n<p>The stupid way to do it would have been to try to go from vint64 to int64_t\/uint64_t in one fell swoop. NSF and LF didn&#8217;t engage me to be that stupid.<\/p>\n<p>Quoting myself: &#8220;A series of smaller steps such that each revision has a well-defined and provable relationship to the last.&#8221;<\/p>\n<p>Generally, in cases like this, the thing to do is separate changing the interface from changing the implementation.  So:<\/p>\n<p>1. First, encapsulate vint64 into an abstract data type (ADT) with an entirely functional interface &#8211; un-expose the guts.<\/p>\n<p>2. Then, change the implementation (struct to scalar), changing the ADT methods <em>without disturbing any of the outside calls to them<\/em> &#8211; if you have to do the latter, you failed step 1 and have to clean up your abstract data type.<\/p>\n<p>3. Finally, hand-expand the function calls to native C scalar operations.  Now you no longer have an ADT, but that&#8217;s OK; it was scaffolding. You knew you were going to discard it.<\/p>\n<p>The goal is that at each step it should be possible, and relatively easy to eyeball-check that the transformation you did is correct. Helps a lot to have unit tests for the code you&#8217;re modifying &#8211; then, one of your checks is that the unit tests don&#8217;t go sproing at any step.  If you don&#8217;t have unit tests, <em>write them<\/em>.  They&#8217;ll save your fallible ass. The better your unit tests are, the more time and pain you&#8217;ll save yourself in the long run.<\/p>\n<p>OK, so here&#8217;s you chance to catch me in a mistake.<\/p>\n<p>https:\/\/gitlab.com\/NTPsec\/ntpsec\/commit\/13fa1219f94d2b9ec00ae409ac4b54ee12b1e93f<\/p>\n<p>That is the diff where I pull all the vint64 guts exposure into a ADT (done with macro calls, not true functions, but that&#8217;s a C implementation detail).<\/p>\n<p>Can you find an error in this diff?  If you decide not, how did it convince you?  What properties of the diff are important?<\/p>\n<p>(Don&#8217;t pass over that last question lightly.  It&#8217;s central.)<\/p>\n<p>If you&#8217;re feeling brave, try step 2. Start with &#8216;typedef uint64_t vint4;&#8217;, replacing the structure definition, and rewrite the ten macros near the beginning of the diff.  (Hint: you&#8217;ll need two sets of them.)<\/p>\n<p>Word to the newbies: <em>this is how it&#8217;s done<\/em>. Train your brain so that you analyze programming this way &#8211; mostly smooth sequences of refactoring steps with only occasional crisis points where you add a feature or change an assumption.<\/p>\n<p>When you can do this at a microlevel, with code, you are inhabiting the mindset of a master programmer.  When you can do it with larger design elements &#8211; data structures and entire code subsystems &#8211; you are getting inside system-architect skills.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>To do large code changes correctly, factor them into a series of smaller steps such that each revision has a well-defined and provable relationship to the last. (This is the closest I&#8217;ve ever come to a 1-sentence answer to the question &#8220;How the fsck do you manage to code with such ridiculously high speed and&hellip; <a class=\"more-link\" href=\"http:\/\/esr.ibiblio.org\/?p=7230\">Continue reading <span class=\"screen-reader-text\">Thinking like a master programmer<\/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":[13],"tags":[],"class_list":["post-7230","post","type-post","status-publish","format-standard","hentry","category-software","entry"],"_links":{"self":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7230","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=7230"}],"version-history":[{"count":2,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7230\/revisions"}],"predecessor-version":[{"id":7232,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/7230\/revisions\/7232"}],"wp:attachment":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=7230"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=7230"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=7230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}