<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Kevin Hartman on Medium]]></title>
        <description><![CDATA[Stories by Kevin Hartman on Medium]]></description>
        <link>https://medium.com/@kevin_hartman?source=rss-da997dcaafaf------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*z5wV0ERMDQ8JK1aVzYB1wA.jpeg</url>
            <title>Stories by Kevin Hartman on Medium</title>
            <link>https://medium.com/@kevin_hartman?source=rss-da997dcaafaf------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 17:47:48 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@kevin_hartman/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Encoding MIPS Instructions with C++17]]></title>
            <link>https://medium.com/@kevin_hartman/encoding-mips-instructions-with-c-17-59f9c2170faa?source=rss-da997dcaafaf------2</link>
            <guid isPermaLink="false">https://medium.com/p/59f9c2170faa</guid>
            <category><![CDATA[c]]></category>
            <category><![CDATA[template]]></category>
            <category><![CDATA[cpp]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[mips]]></category>
            <dc:creator><![CDATA[Kevin Hartman]]></dc:creator>
            <pubDate>Wed, 05 Feb 2020 13:51:58 GMT</pubDate>
            <atom:updated>2020-02-05T13:51:58.689Z</atom:updated>
            <content:encoded><![CDATA[<p><a href="https://twitter.com/ctr_peach">Kevin Hartman</a></p><p>I recently started writing an assembler from scratch using C++17 for a somewhat obscure operating system. The assembler’s design supports multiple target architectures, but for now, I only need to support the MIPS I instruction set, which happens to be extremely convenient, in that it’s trivial to encode.</p><p>A single MIPS assembler instruction is comprised of an operation mnemonic along with an optional operand list (e.g. addi $t1,$v0,0xFF). The proper machine encoding of the instruction (i.e. the layout of its 32 bits) is dictated by the instruction’s format type, which is documented for all MIPS I instructions in the <a href="https://cgi.cse.unsw.edu.au/~cs3231/doc/R3000.pdf">IDT R30xx Family Software Reference Manual</a>.</p><h4>The three MIPS Instruction Encoding Formats</h4><figure><img alt="Shows the bit-field layouts of MIPS I-type, J-type- and R-type instructions." src="https://cdn-images-1.medium.com/max/1024/1*l6_PSVKAVbYfpl-AFTROeg.png" /></figure><figure><img alt="I-type have op, RS, RT, and Immediate. J-type have operand and 26-bit target. R-type have op, RS, RT, RD, shift, and function" src="https://cdn-images-1.medium.com/max/1024/1*pnEce-03ZC2mH60COmGRQQ.png" /><figcaption>From IDT R30xx Family Software Reference Manual</figcaption></figure><p>The figure (A.1) shows how the available 32 bits of an instruction are used by each of the three encoding formats.</p><p>Bit-fields rs, rt, and rd encode the index of a CPU register (0 thru 31).</p><p>Bit-fields immediate , target , and shamt encode a user-supplied numeric constant value.</p><p>Bit-fields op and funct encode an assembler-supplied numeric constant value (i.e. flags), used by the CPU to identify and configure itself for the instruction.</p><h4>Declarative Instruction Encoding [C++17][constexpr if]</h4><p>To keep all of the encoding rules in one place, the assembler supports the following declarative syntax:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c089530e484d9a344cf2e78dee279fbc/href">https://medium.com/media/c089530e484d9a344cf2e78dee279fbc/href</a></iframe><p>This map provides the encoding function for each and every MIPS I instruction. The expressions supplied for the map’s values generate these encoding functions via template expansion.</p><p>For example, from the snippet above, IType names a function template which accepts 5 template arguments:</p><ol><li><strong>Opcode. </strong>Numeric constant expression (constant bits), only.</li><li><strong>RS.</strong> Constant bits, or a sentinel value Arg, which tells the function template to read the value from the user-supplied operands (5.).</li><li><strong>RT.</strong> Constant bits, or Arg.</li><li><strong>Immediate.</strong> Constant bits, or Arg.</li><li><strong>Operand parsing function.</strong> Reads the user-provided operands string into a tuple (more on this later).</li></ol><p>Each function template (RType, IType, JType) instantiation results in the generation of a custom function which supplies the <em>constant</em> portions of the instruction’s encoding at compile-time. In other words, the bit-fields of the instruction that are always the same (used by the CPU to identify the operation it should perform) are passed into these function templates as integral constants (non-type integral <a href="https://en.cppreference.com/w/cpp/language/template_parameters">template parameters</a>). In theory, this should allow the compiler to combine all constant portions of the encoded instruction at compile-time.</p><p>The only deviation from this pattern occurs in the presence of the Arg sentinel, which uses a C++17 feature known as the <a href="https://en.cppreference.com/w/cpp/language/if">constexpr if</a> statement to provide special-casing.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/72bec409d339dd43839622c1c673d27c/href">https://medium.com/media/72bec409d339dd43839622c1c673d27c/href</a></iframe><blockquote>Note that the function <em>IsArgSentinel</em> is <em>constexpr</em>.</blockquote><p>The function template shown above (used for MIPS I-type instructions) uses a constexpr if statement to <strong>generate code </strong>to read the value for RS from the user-provided operand string (this is the operands list provided after the mnemonic), <strong>if and only if</strong> RS as specified by the template instantiation is the Arg sentinel.</p><p>A constexpr if statement tests the result of a constant expression (provided as its condition), and <strong>*discards*</strong> the statements of the branch not taken. This condition is evaluated at compile-time, making it possible for the compiler to exclude the failed branch from the function’s code.</p><blockquote>If the value is true, then statement-false is discarded (if present), otherwise, statement-true is discarded. — <a href="https://en.cppreference.com/w/cpp/language/if">cppreference</a>.</blockquote><h4>Reading the Operand String [C++14]</h4><p>The instruction function templates (i.e. IType, RType, JType) make no assumptions about the format of the operand string nor the ordering (or count!) of its contained operands.</p><p>Instead, each of these function templates accept a function pointer<em> </em>(5. from the example above) to an operand string parsing function, which splits the operand string into an std::tuple of the relevant fields for the instruction format.</p><p>The function templates can then simply use the type-based overload of std::get (C++14) to retrieve specific operands:</p><pre>auto&amp; rs_operand = std::get&lt;assembler::RS&gt;(operands);</pre><blockquote>This usage is shown in context for the I-type function template in the previous section.</blockquote><h4>Declarative Operand Parsing</h4><p>To prepare these tuples, we must split an operand string into its components in accordance with the syntax rules of the corresponding assembler instruction.</p><p>The syntax rules for an instruction dictate:</p><ol><li>The <strong>formatting</strong> of the operand list<strong>. </strong>Either tuple-style (e.g. $t0,$v0,0xFF) or offset-style (e.g. $t0,0xFF($v0)).</li><li>The<strong> ordering </strong>of the instruction components to which each operand will bind. For example, is $t0,$v0,0xFF supposed to be RT,RS,Immediate or RS,RT,Immediate?</li></ol><p><strong><em>Both</em></strong> of these rules can be implemented declaratively using function templates as well (see ITypeTuple and ITypeOffset):</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a8abb2dfb1ea0bcf1496919640f8396b/href">https://medium.com/media/a8abb2dfb1ea0bcf1496919640f8396b/href</a></iframe><p>Notice in the above examples that the <strong><em>order</em></strong> of our template parameters (i.e. RS, RT, Immediate) defines the operand order for the instruction.</p><p>The implementation of this syntax relies heavily on the type-based overload of std::get, which allows us to bind the I-th operand from the operand string to whichever tuple field type was provided for the I-th template argument, in the resulting tuple.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/8fbbaa943faba0ebaca00a4611055c09/href">https://medium.com/media/8fbbaa943faba0ebaca00a4611055c09/href</a></iframe><h4>Optional Operands [C++17]</h4><p>You may have noticed the use of std::optional (C++17) above. This type is used to represent a value which may or may not be present. All wrapper operand types extend std::optional:</p><pre>struct RS : std::optional&lt;std::string&gt; { ... };</pre><p>This allows them to be specified as std::nullopt by operand parsing functions for which not all operand types are applicable. For example, many I-type instructions allow only two user-specified operands:</p><pre>// Example: bgez $t0,0xCF<br>//<br>// RS = $t0, Immediate = 0xCF</pre><pre>// Field RT does NOT come from the operand list. It must always<br>// be 1, as required by the bgez reference spec.</pre><pre>{ &quot;bgez&quot;, IType&lt;0b000001, Arg, 1, Arg, ITypeTuple&lt;RS, Immediate&gt;&gt; }</pre><p>An ITypeTuple function template with two template arguments handles this case by filling only two of the three operand fields in the resulting tuple.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/dd0c5559ff2b988b2b958ab918a3d97f/href">https://medium.com/media/dd0c5559ff2b988b2b958ab918a3d97f/href</a></iframe><p>The remaining field (not user-specifiable) will be std::nullopt (RT in the case of bgez), though it will never be read as such, since no code will be generated to read it in the corresponding IType function template instantiation.</p><blockquote>It would have been possible to use variadic template arguments to handle both 2 and 3-tuples using a single function template, but this was decided against for simplicity.</blockquote><h4>Further Reading: `constexpr` Function Parameters</h4><p>In this post, I mentioned the use of a sentinel value Arg used to special-case code generation for reading operands. Perhaps ideally, we could have used something type-safe (perhaps std::optional) as our non-type template argument’s type, but this is <a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0732r0.pdf">not possible in C++17</a>.</p><p>To work around this limitation, a <strong><em>type</em></strong> template parameter can be used in conjunction with the newly introduced constexpr lambda (C++17).</p><blockquote>Though this approach was not chosen due to complexity.</blockquote><p>For a detailed explanation of this solution, check out <a href="https://medium.com/u/b3129e0c6275">Michael Park</a>’s excellent blog post on the topic: “<a href="https://mpark.github.io/programming/2017/05/26/constexpr-function-parameters/#c17">constexpr function parameters</a>”.</p><h4>References</h4><ul><li><a href="https://cgi.cse.unsw.edu.au/~cs3231/doc/R3000.pdf">IDT R30xx Family Software Reference Manual</a></li><li><a href="https://en.cppreference.com/w/cpp/language/if">https://en.cppreference.com/w/cpp/language/if</a> (if constexpr)</li><li><a href="https://en.cppreference.com/w/cpp/utility/optional">https://en.cppreference.com/w/cpp/utility/optional</a></li><li><a href="https://en.cppreference.com/w/cpp/utility/tuple/get">https://en.cppreference.com/w/cpp/utility/tuple/get</a></li><li><a href="https://mpark.github.io/programming/2017/05/26/constexpr-function-parameters/#c17">https://mpark.github.io/programming/2017/05/26/constexpr-function-parameters/</a></li><li><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0732r0.pdf">http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0732r0.pdf</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=59f9c2170faa" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Spark Streaming Transformations : A Deep-dive]]></title>
            <link>https://medium.com/@kevin_hartman/spark-streaming-transformations-a-deep-dive-b82787e53288?source=rss-da997dcaafaf------2</link>
            <guid isPermaLink="false">https://medium.com/p/b82787e53288</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[apache-spark]]></category>
            <category><![CDATA[big-data]]></category>
            <category><![CDATA[analytics]]></category>
            <category><![CDATA[spark]]></category>
            <dc:creator><![CDATA[Kevin Hartman]]></dc:creator>
            <pubDate>Wed, 24 Jan 2018 22:32:32 GMT</pubDate>
            <atom:updated>2019-01-09T21:14:33.324Z</atom:updated>
            <content:encoded><![CDATA[<h4>An in depth look at the data transformation APIs offered by Apache Spark’s streaming extension.</h4><p><a href="https://twitter.com/ctr_peach">Kevin Hartman</a></p><p>This post offers a deep-dive into Spark’s stream transformation APIs. The knowledge presented here has been derived through the work and research done under the development of <a href="http://github.com/CatalystCode/project-fortis">Project Fortis</a>, a production-scale Spark Streaming application which provides planners and scientists with tools to gain insight from social media, public websites, and custom data sources.</p><p>It’s intended for developers with an intermediate to advanced degree of experience writing Spark Streaming applications.</p><h3>The Spark Engine</h3><p>At the core of Spark Streaming is the Spark engine itself. Like other big data engines, it was designed to partition large datasets across multiple worker nodes so that they can be processed in a highly parallel fashion. If you’ve written a Spark application in the past, you’ll likely recall that the parallelized form of these datasets and their intermediate transformation states are represented as <a href="http://spark.apache.org/docs/2.2.0/rdd-programming-guide.html#resilient-distributed-datasets-rdds">RDD</a>s within your Spark driver’s code.</p><p>As a refresher, here’s an example of a simple set of statements you may see in such a driver program:</p><pre>val myString = <strong>new</strong> String(&quot;hello &quot;)<br>val transformedRdd = myDatasetRdd.map(datum =&gt; myString + datum)</pre><pre>// Perform an action to trigger processing:<br>transformedRdd.print()</pre><p>In this snippet, the map function is called on the RDD named myDatasetRdd, and to it is passed an anonymous function with a single argument, which returns that argument prefixed with &quot;hello &quot;.</p><p>It’s very important to understand that the driver program will evaluate the statement myDatasetRdd.map(datum =&gt; myString + datum) <strong><em>as soon as it encounters it</em></strong><em>.</em> Additionally, the map call will return almost instantly. All the map function does is add another stage to your <strong>execution plan</strong> by returning a new RDD which represents the map transformation stage, with a pointer to the original (previous) RDD baked into it. In this way, a list of the transformations that should be applied to your source RDDis prepared under the hood. Other RDD transformations besides map work in the same way.</p><blockquote>If you observe the runtime type of the value of tranformedRdd after the driver executes map, you will see that it’s MapPartitionsRDD. The map function has created this new RDD to represent the state of your old RDD (myDatasetRdd) after having prefixed each of its elements with &quot;hello &quot; .</blockquote><p>The invocation of the anonymous function you’ve defined to actually do that work will <strong><em>not</em></strong> have executed. This is because RDD transformations are<em> lazily evaluated,</em> and the driver thread has yet to encounter an action against transformedRdd (directly or indirectly via any RDDs whose lineage may contain it).</p><blockquote>If Spark’s lazy evaluation model is unfamiliar, please review the <a href="https://spark.apache.org/docs/2.2.0/rdd-programming-guide.html#rdd-operations">relevant section</a> of the Spark Programming Guide.</blockquote><p>Once an action <em>is</em> called against our transformedRdd, our anonymous function will finally be invoked, but not by the driver thread. The workers within our Spark cluster will call it for each element in their respective partitions of myDatasetRdd. You may be wondering how this works, given that other Spark worker threads may be running within other JVM instances (and likely on other machines). In short, the closure of our anonymous function is serialized to worker processes such that it’s available locally when each partition is processed.</p><p>In the example above, observe that our anonymous function has a data dependency on the value of myString. In fact, it’s within the closure of our anonymous function. When this closure is serialized for use by worker processes, its object graph will include the value of myString, making it available on each worker, even though this value will have been computed (new String(&quot;hello&quot;)) within the driver.</p><blockquote>Each JVM process will deserialize its own copy of our anonymous function’s closure. Therefore, you should not assume that edits to objects serialized as part of these closures will be visible to other transformation functions whose closures also include it. For example, if our anonymous function edited myString (and Strings were mutable), another transformation function also making use of myString would not necessarily ever see that edit.</blockquote><p>As a final note, Spark will attempt to remove any parts of our anonymous function’s closure that it doesn’t make use of, prior to serialization. For example, if we had a second field beside myString but no reference to it from within our anonymous function, it would not be included in the serialization. This means there’s no need to worry about the values of unused local fields being sent over the wire unnecessarily.</p><blockquote>Watch out for references to <em>this</em> from within your transformation functions. If your transformation function(s) are defined within a class, a reference to <em>this</em> will include the entire serializable object graph of that class’s instance, which you likely only ever intended to use within the driver.</blockquote><h3>Streaming Extension</h3><p>The Spark Streaming extension (known simply as Spark Streaming) allows the application programmer to define a Spark application just as above, but it offers additional mechanisms to continuously run the set up of Spark transformations as well as their consuming actions on a conceivably endless stream of incoming datasets (RDDs). Beyond that, it offers facilities to create custom “receivers”, which act as factories for these datasets, pulling data from any source imaginable. There are numerous libraries which provide Spark Streaming receiver implementations for popular data sources, such as Twitter (see <a href="http://bahir.apache.org/">Apache Bahir</a>).</p><p>Spark Streaming provides the DStream type to represent a stream of datasets (RDDs), providing a rich set of functions for manipulating incoming data. For this section, we’ll focus on two of the most powerful primitives that it offers:</p><h4>foreachRDD(…)</h4><p>The foreachRDD function on DStreams gives the application programmer access to each incoming RDD within the stream. It’s here that we have the opportunity to define Spark transformations as well as actions which we’d like to perform for each RDD.</p><p>As such, the foreachRDD function accepts as a parameter a user-specified function, which will be called by the Spark Streaming runtime for each RDD in the stream. The simplest overload has the following declaration:</p><pre><strong>def</strong> <strong>foreachRDD</strong>(foreachFunc: RDD[T] =&gt; Unit): Unit</pre><p>Let’s take the example above from our classic Spark application and put it into the context of a Spark Streaming application instead:</p><pre>myDStream.foreachRDD(myDatasetRdd =&gt; {<br>  val myString = <strong>new</strong> String(&quot;hello &quot;)<br>  val transformedRdd = myDatasetRdd.map(datum =&gt; myString + datum)</pre><pre>  // Perform an action to trigger processing:<br>  transformedRdd.print()<br>})</pre><p>Here, we can see that for every incoming RDD, we set up our transformation (which prefixes all elements in the RDD with &quot;hello &quot;) and then trigger its computation by the Spark cluster using an action (in this case, print).</p><p>This seems straight forward, but what might not be so obvious is where the anonymous function which we’ve passed to foreachRDD will run, or even when.</p><p>Here are a few not-so-obvious facts about the function we supply:</p><ol><li><strong>It will be executed locally within the driver</strong>, and will be called for each RDD arriving on the DStream.</li><li><strong>It’s expected to block until the </strong><strong>RDD has been processed</strong> by the Spark cluster (RDD actions have been invoked, which complete synchronously). This is because it’s generally expected that the processing of each RDD will make good use of all cluster resources (just as it would in a non-streaming Spark application), or if it’s known that it will not:</li><li><strong>It can be executed concurrently</strong> if spark.streaming.concurrentJobs is set to something greater than 1. An important implication here is that the function you provide to foreachRDD <em>must</em> be thread-safe.</li><li>Even though this function will run on the driver itself (and hence doesn’t need to be shipped to any other worker/process), <strong>its closure still <em>must</em> be serializable</strong> if checkpointing is enabled. This is because the DStream graph which is serialized as part of your checkpoint metadata will include this function. When recovering from a checkpoint, Spark Streaming will deserialize your old DStream graph, including this function’s closure.</li></ol><h4>transform(…)</h4><p>Similarly to foreachRDD, the transform function on DStreams gives us the opportunity to define Spark transformations on each RDD in the stream. The difference is that transform is not an output operation, and hence instead of returning Unit, it returns a new DStream containing each transformed RDD. This allows the application programmer to defer any output operations to downstream processing.</p><p>The simplest overload has the following definition:</p><pre>def transform[U: ClassTag](transformFunc: RDD[T] =&gt; RDD[U]): DStream[U]</pre><p>Here’s our example again, this time demonstrating how we can pass on our transformed RDDs as a new DStream to downstream logic:</p><pre>transformedDStream = myDStream.transform(myDatasetRdd =&gt; {<br>  val myString = <strong>new</strong> String(&quot;hello &quot;)<br>  val transformedRdd = myDatasetRdd.map(datum =&gt; myString + datum)</pre><pre>  transformedRdd<br>})</pre><pre>transformedDStream.foreachRDD(transformedRdd =&gt; {<br>  // Perform an action to trigger processing:<br>  transformedRdd.print()<br>})</pre><p>Just as is the case with foreachRDD, the transform function will also be executed on the driver.</p><p>In contrast with foreachRDD, here are some parallel facts about the function we supply to transform:</p><ol><li>It will also be executed on the driver.</li><li>While it should be possible to perform RDD actions within the transform function, <a href="https://mail-archives.apache.org/mod_mbox/spark-user/201506.mbox/%3CCA+AHuKkZmdFaDk-947gptn_XdofOc13aao+LuCSii3cPh7zgxQ@mail.gmail.com%3E">it’s not expected</a>. You shouldn’t perform long-running operations here. Set up your transformations on the incoming RDD and return the new (we will abuse this a little later).</li><li>I have no reason to suspect transform’s function will not be executed concurrently under the same conditions as foreachRDD‘s. You should write the function you provide to be reentrant as is the case with foreachRDD.</li><li>It must also be serializable if you’ve enabled checkpointing for the same reasons.</li></ol><h3>Epilogue</h3><p>Throughout this article, we’ve covered details of the Spark Stream extension and hopefully shed some light on the more complex and obscure aspects of the underlying engine’s behavior.</p><p>For some code making use of these concepts, check out <a href="http://github.com/kevinhartman/streaming-conf-sb">streaming-conf-sb</a> on GitHub which implements live configuration of an Apache Spark Streaming application using <a href="https://azure.microsoft.com/en-us/services/service-bus/">Azure Service Bus</a>.</p><p>Feel free to leave a comment if you’d like to see something else captured.</p><h3>Resources</h3><ul><li><a href="http://github.com/CatalystCode/project-fortis">Project Fortis</a></li><li><a href="https://spark.apache.org/">Apache Spark</a></li><li><a href="http://spark.apache.org/docs/2.2.0/rdd-programming-guide.html#resilient-distributed-datasets-rdds">RDD</a></li><li><a href="http://bahir.apache.org/">Apache Bahir</a></li><li><a href="https://azure.microsoft.com/en-us/services/service-bus/">Azure Service Bus</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b82787e53288" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>