tag:blogger.com,1999:blog-29770020841557334702024-03-19T05:24:21.285-04:00ThornyDevAnonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.comBlogger48125tag:blogger.com,1999:blog-2977002084155733470.post-83760024753881003252015-07-02T18:25:00.001-04:002015-07-08T00:30:37.176-04:00An Exercise in Profiling a Go Program<p>Recently, while working on my current project <a href="https://github.com/quux00/ogonori">ogonori</a>, a Go client for the <a href="http://orientdb.com/orientdb/">OrientDB database</a>, I found that I had a defect in the code that encodes and decodes integer values in the way that the OrientDB binary network protocol requires (namely <a href="https://developers.google.com/protocol-buffers/docs/encoding#types">zigzag encoding</a>, followed by encoding that output as a variable length integer).</p>
<p>After fixing the issue, first with the encoder and then with the decoder, I decided that I should do an exhaustive test of all 64 bit integers: start with MinInt64 (<code class="so">-9223372036854775808</code>), zigzag-encode it, varint encode it, then varint decode it and zigzag-decode it and you should get back the number you started with. Increment by 1 and try it again, until you reach MaxInt64 (<code class="so">9223372036854775807</code>).</p>
<p>(Note: I only have to use the Min/Max range of signed integers, since OrientDB is a Java database and only allows signed ints.)</p>
<p>I ran a small range of the possible 64-bit integer space and found that doing this exhaustive test was going to take a very long time. Since I have 8 CPUs on my system, I decided to first parallelize the test into 8 separate goroutines, each taking 1/8 of the total range:</p>
<script src="https://gist.github.com/quux00/6e62f44f19663ca29848.js"></script>
<p>With this code, I spawn 8 threads, running 10 goroutines. Eight of them do the encoding/decoding test and if any integer encode/decode fails the test it is written to "failure channel" of type <code class="so">chan string</code>, which the main goroutine monitors.</p>
<p>A <code class="so">sync.WaitGroup</code> (a counting semaphore) is created and shared among the goroutines. When each "range tester" finishes, it calls <code class="so">Done()</code> on the WaitGroup to decrement the semaphore. The final (nameless) goroutine waits until all "range tester" goroutines have finished and then closes the single shared failure channel.</p>
<p>Closing of the failure channel, causes the loop over that channel in the main goroutine to exit and the whole program finishes.</p>
<p><br /></p>
<h4><code>/* ---[ Performance Baseline ]--- */</code></h4>
<p>I fired this up with the following smaller testrange:</p>
<div class="precode"><pre><code> ranges := []testrange{
{100000001, 150000001},
{200000001, 250000001},
{300000001, 350000000},
{400000001, 450000000},
{500000001, 550000000},
{600000001, 650000000},
{700000001, 750000000},
{800000001, 850000000},
}
</code></pre></div>
<p>and ran <code class="so">top</code>. To my surprise I was only using ~400% CPU, rather than ~800% (the max my system supports):</p>
<div class="precode"><pre><code>$ top -d1
PID USER PR ... S %CPU %MEM TIME+ COMMAND
1736 midpete+ 20 ... S 420.9 0.0 1:31.33 ogonori
</code></pre></div>
<p>I then looked at the CPU usage of each thread using the <code class="so">-H</code> option to <code class="so">top</code> and saw that my 8 range-tester goroutines were each using only about 50% CPU. And that there was a 9th thread that was also consistently using 40 to 50% CPU. My guess was that this was a GC thread.</p>
<div class="precode"><pre><code>$ top -d1 -H
PID USER PR ... S %CPU %MEM TIME+ COMMAND
1740 midpete+ 20 ... S 50.1 0.0 0:21.47 ogonori
1744 midpete+ 20 ... R 50.1 0.0 0:21.52 ogonori
1742 midpete+ 20 ... S 49.2 0.0 0:21.38 ogonori
1736 midpete+ 20 ... S 47.2 0.0 0:21.53 ogonori
1738 midpete+ 20 ... S 46.2 0.0 0:22.11 ogonori
1745 midpete+ 20 ... R 46.2 0.0 0:20.37 ogonori
1741 midpete+ 20 ... S 45.2 0.0 0:21.41 ogonori
1743 midpete+ 20 ... R 42.3 0.0 0:21.26 ogonori
1739 midpete+ 20 ... S 40.3 0.0 0:21.35 ogonori
1737 midpete+ 20 ... S 3.9 0.0 0:02.07 ogonori
</code></pre></div>
<p>So I have an algorithm that should be trivially parallelizable with no shared memory and no contention (in theory), but it was only using half the CPU available to it. Hmmm...</p>
<p>Next I ran the test on my system several times to get a baseline performance metric:</p>
<div class="precode"><pre><code>$ time ./ogonori -z # the -z switch tells the ogonori code to only this
# benchmark rather than the usual OrientDB tests
Run1: real 3m44.602s
Run2: real 3m42.818s
Run3: real 3m28.917s
Avg ± StdErr: 218.8 ± 5 sec
</code></pre></div>
<p>Then I remembered I had not turned off the CPU power saving throttling on my Linux system (it was set to <code class="so">ondemand</code>), so I ran the following script and repeated the benchmarks:</p>
<div class="precode"><pre><code>#!/bin/bash
for i in /sys/devices/system/cpu/cpu[0-7]
do
echo performance > $i/cpufreq/scaling_governor
done
$ time ./ogonori -z
Run1: real 2m12.605s
Run2: real 2m12.382s
Run3: real 2m13.172s
Run4: real 2m18.992s
Run5: real 2m17.538s
Run6: real 2m14.437s
Avg ± StdErr: 134.9 ± 1 sec
</code></pre></div>
<p>Wow, OK. So that alone gave me about a 60% improvement in throughput. Off to a good start.</p>
<p><br /></p>
<h4><code>/* ---[ Profiling the Code ]--- */</code></h4>
<p>If you've never read <a href="https://blog.golang.org/profiling-go-programs">Russ Cox's 2011 blog post on profiling a Go program</a>, put it on your list - it is a treat to read.</p>
<p>Using what I learned there, I profiled the zigzagExhaustiveTest code to see how and where to improve it.</p>
<div class="precode"><pre><code>$ ./ogonori -z -cpuprofile=varint0.prof
</code></pre></div>
<p>I then opened the .prof file with golang's pprof tool and looked at the top 10 most heavily used functions:</p>
<div class="precode"><pre><code>$ rlwrap go tool pprof ogonori xvarint0.prof
# Using rlwrap gives you bash-like behavior and history
(pprof) top 10
171.48s of 255.92s total (67.01%)
Dropped 171 nodes (cum <= 1.28s)
Showing top 10 nodes out of 36 (cum >= 8.78s)
flat flat% sum% cum cum%
45.98s 17.97% 17.97% 45.98s 17.97% scanblock
25.63s 10.01% 27.98% 33.58s 13.12% runtime.mallocgc
19.20s 7.50% 35.48% 111.35s 43.51% g/q/o/o/b/varint.ReadVarIntToUint
14.94s 5.84% 41.32% 15.62s 6.10% bytes.(*Buffer).grow
12.44s 4.86% 46.18% 12.44s 4.86% runtime.MSpan_Sweep
11.87s 4.64% 50.82% 15.93s 6.22% bytes.(*Buffer).Read
11.33s 4.43% 55.25% 21.56s 8.42% bytes.(*Buffer).WriteByte
11.18s 4.37% 59.62% 11.18s 4.37% runtime.futex
10.13s 3.96% 63.57% 19.16s 7.49% bytes.(*Buffer).Write
8.78s 3.43% 67.01% 8.78s 3.43% runtime.memmove
(pprof) top10 -cum
110.32s of 255.92s total (43.11%)
Dropped 171 nodes (cum <= 1.28s)
Showing top 10 nodes out of 36 (cum >= 25.50s)
flat flat% sum% cum cum%
0 0% 0% 147.62s 57.68% runtime.goexit
2.94s 1.15% 1.15% 147.49s 57.63% main.func·018
19.20s 7.50% 8.65% 111.35s 43.51% g/q/o/o/b/varint.ReadVarIntToUint
0 0% 8.65% 77.81s 30.40% GC
45.98s 17.97% 26.62% 45.98s 17.97% scanblock
4.90s 1.91% 28.53% 38.48s 15.04% runtime.newobject
25.63s 10.01% 38.55% 33.58s 13.12% runtime.mallocgc
6.65s 2.60% 41.15% 31.39s 12.27% g/q/o/o/b/varint.VarintEncode
0 0% 41.15% 30.48s 11.91% System
5.02s 1.96% 43.11% 25.50s 9.96% encoding/binary.Read
</code></pre></div>
<p>We can see that a significant percentage of time (>30%) is being spent in GC, so the program is generating a lot of garbage somewhere - plus the cost of generating new heap data, which the <code class="so">runtime.mallocgc</code> figure tells me is at least 13% of the program run time.</p>
<p>Remember that there are four steps to my algorithm:</p>
<ol>
<li>zigzag encode (<code class="so">varint.ZigzagEncodeUInt64</code>)</li>
<li>varint encode (<code class="so">varint.VarintEncode</code>)</li>
<li>varint decode (<code class="so">varint.ReadVarIntToUint</code>)</li>
<li>zigzag decode (<code class="so">varint.ZigzagDecodeInt64</code>)</li>
</ol>
<p>The zigzag encode/decode steps are simple bit manipulations, so they are fast. Typing <code class="so">web</code> at the pprof prompt launches an SVG graph of where time was spent. The zigzag functions don't even show up - they were dropped off as being too small (not shown here).</p>
<p>So I needed to focus on steps 2 and 3 which take (cumulatively) 43.5% and 12.3%, respectively.</p>
<p>Since <code class="so">varint.ReadVarIntToUint</code> is the biggest offender let's look at it in detail in the pprof tool:</p>
<script src="https://gist.github.com/quux00/16131fa51ba26a748d0b.js"></script>
<p>I've marked the biggest time sinks with an arrow on the left side. Generally one should start with the biggest bottleneck, so let's rank these by cumulative time (2nd col):</p>
<div class="precode"><pre><code>-> 32.41s 111: err = binary.Read(&buf, binary.LittleEndian, &u)
-> 16.83s 73: n, err = r.Read(ba[:])
-> 15.93s 106: buf.WriteByte(y | z)
-> 14.82s 88: var buf bytes.Buffer
-> 8.53s 110: padTo8Bytes(&buf)
</code></pre></div>
<p>First, it is very interesting how expensive creating a bytes.Buffer is. But first we need to deal with <code class="so">binary.Read</code>.</p>
<script src="https://gist.github.com/quux00/b16238a795878248e06b.js"></script>
<p>Because I'm only ever passing in uint64's, the only real functionality I'm using in this function is:</p>
<div class="precode"><pre><code>*data = order.Uint64(bs)
</code></pre></div>
<p><br /></p>
<h4><code>/* ---[ Optimization #1 ]--- */</code></h4>
<p>But it's even worse. If you look back at <code class="so">varint.ReadVarIntToUint</code> you'll see that I'm creating a <code class="so">bytes.Buffer</code> and copying bytes into it only so that I can pass that Buffer (as an <code class="so">io.Reader</code>) into the <code class="so">binary.Read</code> function:</p>
<div class="precode"><pre><code>err = binary.Read(buf, binary.LittleEndian, &u)
</code></pre></div>
<p>which then immediately copies all those bytes back out of the buffer:</p>
<div class="precode"><pre><code>if _, err := io.ReadFull(r, bs); err != nil {
return err
}
</code></pre></div>
<p>So this is nothing but wasteful data copying and the heap allocations for it.</p>
<p><code class="so">binary.Read</code> also does a type switch where a good percentage of time is spent</p>
<div class="precode"><pre><code> 2.01s 4.49s 151: switch data := data.(type) {
</code></pre></div>
<p>and, as stated, the only useful method ever called in it is:</p>
<div class="precode"><pre><code> --> 460ms 2.76s 167: *data = order.Uint64(bs)
</code></pre></div>
<p>So I should try just calling <code class="so">binary.LittleEndian.Uint64(bs)</code> directly.</p>
<p>Here's the revised <code class="so">varint.ReadVarIntToUint</code> function (with everything inlined for easier reading and profiling analysis):</p>
<script src="https://gist.github.com/quux00/0d75432b898e92200449.js"></script>
<p>This change also removes the <code class="so">padTo8Bytes</code> method that wrote one byte at a time to the <code class="so">bytes.Buffer</code> and took >3% of program time itself.</p>
<p>Now let's rerun the benchmarks:</p>
<div class="precode"><pre><code>Run 1: real 0m27.182s
Run 2: real 0m27.053s
Run 3: real 0m28.200s
Run 4: real 0m25.762s
Run 5: real 0m26.031s
Run 6: real 0m26.813s
Avg ± StdErr: 26.8 ± 0.4 sec
</code></pre></div>
<p><em>Outstanding!</em> Throughput increased 5x (134.9/26.8). And using <code class="so">top</code>, I see that the goroutines are consuming nearly all available CPU:</p>
<div class="precode"><pre><code>$ top -d1
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
12983 midpete+ 20 0 352496 5768 2736 R 763.7 0.0 1:35.64 ogonori
$ top -d1 -H
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
13231 midpete+ 20 0 286960 5772 2744 R 97.5 0.0 0:22.51 ogonori
13225 midpete+ 20 0 286960 5772 2744 R 91.7 0.0 0:22.47 ogonori
13227 midpete+ 20 0 286960 5772 2744 R 90.7 0.0 0:23.09 ogonori
13232 midpete+ 20 0 286960 5772 2744 S 90.7 0.0 0:22.26 ogonori
13235 midpete+ 20 0 286960 5772 2744 R 90.7 0.0 0:09.72 ogonori
13230 midpete+ 20 0 286960 5772 2744 R 88.7 0.0 0:22.14 ogonori
13233 midpete+ 20 0 286960 5772 2744 R 73.1 0.0 0:22.70 ogonori
13228 midpete+ 20 0 286960 5772 2744 R 71.2 0.0 0:22.39 ogonori
13229 midpete+ 20 0 286960 5772 2744 R 70.2 0.0 0:23.09 ogonori
</code></pre></div>
<p>I also used pprof to profile this run, so let's examine compare the cumulative top10 before and after:</p>
<p><em>Before</em> (reprinted from above):</p>
<div class="precode"><pre><code>(pprof) top10 -cum
110.32s of 255.92s total (43.11%)
Dropped 171 nodes (cum <= 1.28s)
Showing top 10 nodes out of 36 (cum >= 25.50s)
flat flat% sum% cum cum%
0 0% 0% 147.62s 57.68% runtime.goexit
2.94s 1.15% 1.15% 147.49s 57.63% main.func·018
19.20s 7.50% 8.65% 111.35s 43.51% g/q/o/o/b/varint.ReadVarIntToUint
0 0% 8.65% 77.81s 30.40% GC
45.98s 17.97% 26.62% 45.98s 17.97% scanblock
4.90s 1.91% 28.53% 38.48s 15.04% runtime.newobject
25.63s 10.01% 38.55% 33.58s 13.12% runtime.mallocgc
6.65s 2.60% 41.15% 31.39s 12.27% g/q/o/o/b/varint.VarintEncode
0 0% 41.15% 30.48s 11.91% System
5.02s 1.96% 43.11% 25.50s 9.96% encoding/binary.Read
</code></pre></div>
<p><em>After:</em></p>
<div class="precode"><pre><code>(pprof) top15 -cum
63680ms of 65970ms total (96.53%)
Dropped 33 nodes (cum <= 329.85ms)
Showing top 15 nodes out of 18 (cum >= 930ms)
flat flat% sum% cum cum%
2280ms 3.46% 3.46% 64470ms 97.73% main.func·018
0 0% 3.46% 64470ms 97.73% runtime.goexit
17760ms 26.92% 30.38% 34190ms 51.83% g/q/o/o/b/varint.ReadVarIntToUint
5890ms 8.93% 39.31% 26370ms 39.97% g/q/o/o/b/varint.VarintEncode
8550ms 12.96% 52.27% 16360ms 24.80% bytes.(*Buffer).Write
9080ms 13.76% 66.03% 11500ms 17.43% bytes.(*Buffer).Read
1460ms 2.21% 68.24% 7550ms 11.44% runtime.newobject
4370ms 6.62% 74.87% 6090ms 9.23% runtime.mallocgc
5650ms 8.56% 83.43% 5650ms 8.56% runtime.memmove
4580ms 6.94% 90.37% 4580ms 6.94% bytes.(*Buffer).grow
680ms 1.03% 91.41% 1630ms 2.47% bytes.(*Buffer).Reset
1500ms 2.27% 93.68% 1500ms 2.27% encoding/binary.littleEndian.Uint64
0 0% 93.68% 1030ms 1.56% GC
950ms 1.44% 95.12% 950ms 1.44% bytes.(*Buffer).Truncate
930ms 1.41% 96.53% 930ms 1.41% runtime.gomcache
</code></pre></div>
<p>More good news. In the previous version, GC was taking 30% of the total CPU time. Now, more than 90% of the time is now being spent in the two main workhorse methods: <code class="so">varint.ReadVarIntToUint</code> and <code class="so">varint.VarintEncode</code>. GC time has been reduced to 1.5%!</p>
<p>I suspect the reason that goroutines in the earlier code version only took 40-50% of a CPU is because GC was the contention point. Garbage Collection in golang is a stop-the-world affair, so all other threads are paused until it finishes. By reducing GC to only 1.5%, now the range-testing goroutines can spend far more time running - approaching 100%.</p>
<p><br /></p>
<h4><code>/* ---[ Optimization #2 ]--- */</code></h4>
<p>Are there further improvements we can make? Since the program now spends 40% of its time in <code class="so">varint.VarintEncode</code>, let's look at that function in detail:</p>
<script src="https://gist.github.com/quux00/a9c746a7bb9a54f5a052.js"></script>
<p>Almost 75% of the time in this function is spent writing to the io.Writer (a <code class="so">bytes.Buffer</code>). We write one byte at a time to it. Perhaps it would be better to write it all to a byte slice first and then issue one <code class="so">w.Write</code>.</p>
<p>The new code is then:</p>
<script src="https://gist.github.com/quux00/6c466c07b2c334d91352.js"></script>
<p>And the next round of benchmarks are:</p>
<div class="precode"><pre><code>real 0m38.899s
real 0m45.135s
real 0m38.047s
real 0m42.377s
real 0m32.894s
real 0m37.962s
real 0m38.926s
real 0m37.870s
Avg ± StdErr: 39.0 ± 1.2
</code></pre></div>
<p>Hmm, not good. It looks like this second revision caused my code to go backwards in performance by 30%. To be sure, I reverted the change and re-ran the benchmarks with only optimization #1 again: they returned to the ~25s/run timeframe I saw before. So it is true: this second change made things worse.</p>
<p>And the analysis of <code class="so">top</code> agreed: the goroutines were no long using 90%+ CPU:</p>
<div class="precode"><pre><code>$ top -d1
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
22149 midpete+ 20 0 286960 5776 2744 R 593.9 0.0 1:06.66 ogonori
$ top -d1 -H
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
22205 midpete+ 20 0 229620 7812 2744 R 74.6 0.0 0:10.68 ogonori
22201 midpete+ 20 0 229620 7812 2744 R 73.6 0.0 0:10.14 ogonori
22202 midpete+ 20 0 229620 7812 2744 S 71.6 0.0 0:10.77 ogonori
22207 midpete+ 20 0 229620 7812 2744 S 70.6 0.0 0:10.97 ogonori
22206 midpete+ 20 0 229620 7812 2744 R 68.7 0.0 0:11.14 ogonori
22204 midpete+ 20 0 229620 7812 2744 R 65.7 0.0 0:10.07 ogonori
22199 midpete+ 20 0 229620 7812 2744 R 56.9 0.0 0:10.98 ogonori
22203 midpete+ 20 0 229620 7812 2744 R 53.0 0.0 0:11.19 ogonori
22197 midpete+ 20 0 229620 7812 2744 R 43.2 0.0 0:11.17 ogonori
22200 midpete+ 20 0 229620 7812 2744 S 17.7 0.0 0:09.95 ogonori
22198 midpete+ 20 0 229620 7812 2744 S 3.9 0.0 0:00.77 ogonori
</code></pre></div>
<p>Let's look at the pprof data for revision #2:</p>
<div class="precode"><pre><code>(pprof) top10 -cum
59.31s of 86.44s total (68.61%)
Dropped 92 nodes (cum <= 0.43s)
Showing top 10 nodes out of 24 (cum >= 5.36s)
flat flat% sum% cum cum%
1.95s 2.26% 2.26% 74.02s 85.63% main.func·018
0 0% 2.26% 74.02s 85.63% runtime.goexit
20.71s 23.96% 26.21% 44.80s 51.83% g/q/o/o/b/varint.ReadVarIntToUint
5.57s 6.44% 32.66% 24.39s 28.22% g/q/o/o/b/varint.VarintEncode
15s 17.35% 50.01% 18.71s 21.65% bytes.(*Buffer).Read
5.64s 6.52% 56.54% 13.46s 15.57% runtime.makeslice
0 0% 56.54% 8.39s 9.71% GC
5.86s 6.78% 63.32% 8.23s 9.52% runtime.mallocgc
2.48s 2.87% 66.18% 7.82s 9.05% runtime.newarray
2.10s 2.43% 68.61% 5.36s 6.20% bytes.(*Buffer).Write
</code></pre></div>
<p>Now GC is back up to nearly 10% of the total running time. So let's look at the profile of the <code class="so">VarintEncode</code> function we changed:</p>
<div class="precode"><pre><code>(pprof) list VarintEncode
Total: 1.44mins
5.57s 24.39s (flat, cum) 28.22% of Total
. . 40://
290ms 290ms 41:func VarintEncode(w io.Writer, v uint64) error {
550ms 14.01s 42: bs := make([]byte, 0, 10)
170ms 170ms 43: for (v & 0xffffffffffffff80) != 0 {
2.04s 2.04s 44: bs = append(bs, byte((v&0x7f)|0x80))
320ms 320ms 45: v >>= 7
. . 46: }
680ms 680ms 47: bs = append(bs, byte(v&0x7f))
. . 48:
1.20s 6.56s 49: n, err := w.Write(bs)
120ms 120ms 50: if err != nil {
. . 51: return oerror.NewTrace(err)
. . 52: }
. . 53: if n != len(bs) {
. . 54: return fmt.Errorf("Incorrect number of bytes written. Expected %d. Actual %d", len(bs), n)
. . 55: }
200ms 200ms 56: return nil
. . 57:}
</code></pre></div>
<p>We can see that 58% of the time of this method is spent allocating new memory (the <code class="so">[]byte</code> slice on line 42), thereby causing GC to take longer. Here's why - if you look at the implementation of <code class="so">bytes.Buffer</code>, you'll see that it has a fixed <code class="so">bootstrap</code> array it allocates to handle small buffers and another fixed byte array (<code class="so">runeBytes</code>) to handle writes to <code class="so">WriteByte</code>; both of these allow it to avoid memory allocation for small operations.</p>
<script src="https://gist.github.com/quux00/f51738442374be854031.js"></script>
<p>Since my test code is reusing the same <code class="so">bytes.Buffer</code> for each iteration, no new allocations were occurring during each call to <code class="so">varint.VarintEncode</code>. But with this second revision I'm creating a new byte slice of capacity 10 in each round. So this change should be reverted.</p>
<p><br /></p>
<h4><code>/* ---[ Lessons Learned ]--- */</code></h4>
<p>When you have an algorithm that you think should be CPU bound and your threads are not using ~100% CPU, then you have contention somewhere. In many scenarios that will be IO wait. But if you have no IO in that portion of your app, then you either have hidden thread contention (mutexes) and/or you may have a lot of garbage collection happening, which pauses all your worker threads/goroutines while GC is happening. Use the pprof tool to determine where time is being spent.</p>
<p>For performance sensitive algorithms, you will want to be garbage free in the main path as much as possible. </p>
<p>Once you know where the time is going, you should generally go after the largest bottleneck first. There's always a primary bottleneck somewhere. Removing the bottleneck in one place causes it to move to another. In my case, I wanted that bottleneck to just be CPU speed (or as is often the case, the time to get data from main memory or a CPU cache into a register).</p>
<p>A big lesson learned here is to be wary of convenience methods in Go's standard library. Many are provided for convenience, not performance. The <code class="so">binary.Read(buf, binary.LittleEndian, &u)</code> call in my case is one such example. The third parameter to <code class="so">binary.Read</code> is of type <code class="so">interface{}</code>, so a type switch has to be done to detect the type. If your code is only ever passing in one type (<code class="so">uint64</code> in my case), then go read the stdlib code and figure out if there is a more direct method to call. That change contributed to a 5x throughput improvement in my case!</p>
<p>Next, be careful of too much data copying. While the <code class="so">io.Writer</code> is a nice interface, if you are working with byte slices and want to pass it to some stdlib method that requires <code class="so">io.Writer</code>, you will often copy the data into a <code class="so">bytes.Buffer</code> and pass that in. If the function you call copies those bytes back out to yet another byte slice, then garbage is being generated and time is being wasted. So be aware of what's happening in the methods you call.</p>
<p>Finally, always measure carefully before and after any attempted optimizations. Intuition about where bottlenecks are and what will speed things up are often wrong. The only thing of value is to measure objectively. To end I'll quote "Commander" Pike:</p>
<blockquote>
<p><em>Rule 1. You can't tell where a program is going to spend its time. Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you've proven that's where the bottleneck is. --<a href="http://users.ece.utexas.edu/~adnan/pike.html">Rob Pike's 5 Rules of Programming</a></em></p>
</blockquote>
<p><br /></p>
<h4><code>/* ---[ Misc Appendix Notes ]--- */</code></h4>
<p>The overall int64 space will still take too long to run even with these improvements, so I've settled for sampling from the state space instead.</p>
<p>All benchmark comparisons done were statistically significant (p<0.01) using Student's t-test, as analyzed with this tool: <a href="http://studentsttest.com"><a href='http://studentsttest.com'>http://studentsttest.com</a></a>. The mean and standard errors were also calculated here.</p>
<p>I notice that even with my best optimization (#1), there is still a ninth thread using >70% CPU. I used <code class="so">kill -QUIT</code> on the program to get a stack dump of all the goroutines. I get 10 go routines - the 8 doing the <code class="so">fnRangeTester</code> work, one waiting on the <code class="so">WaitGroup</code> and the main goroutine which is waiting on the <code class="so">range failchan</code> line. So I'm not sure what that 9th thread is doing churning up 50-70% CPU. Anyone know how to tell?</p>
<hr />
<p><strong>[Update - 08-July-2015]</strong></p>
<p>In the comments, Carlos Torres asked for the pprof line-by-line output of the <code class="so">ReadVarIntToUint</code> function after the first optimization. I did two profiling runs and compared the pprof outputs and they were both nearly identical. Here is one of them:</p>
<div class="precode"><pre><code>(pprof) list ReadVarIntToUint
Total: 1.13mins
ROUTINE ======================== g/q/o/o/b/varint.ReadVarIntToUint
18.20s 35.45s (flat, cum) 52.08% of Total
. . 25://
480ms 480ms 26:func ReadVarIntToUint(r io.Reader) (uint64, error) {
. . 27: var (
270ms 270ms 28: varbs []byte
120ms 3.84s 29: ba [1]byte
. . 30: u uint64
. . 31: n int
180ms 180ms 32: err error
. . 33: )
. . 34:
260ms 260ms 35: varbs = make([]byte, 0, 10)
. . 36:
. . 37: /* ---[ read in all varint bytes ]--- */
. . 38: for {
3.84s 15.72s 39: n, err = r.Read(ba[:])
530ms 530ms 40: if err != nil {
. . 41: return 0, oerror.NewTrace(err)
. . 42: }
10ms 10ms 43: if n != 1 {
. . 44: return 0, oerror.IncorrectNetworkRead{Expected: 1, Actual: n}
. . 45: }
3.21s 3.21s 46: varbs = append(varbs, ba[0])
980ms 980ms 47: if IsFinalVarIntByte(ba[0]) {
570ms 570ms 48: varbs = append(varbs, byte(0x0))
. . 49: break
. . 50: }
. . 51: }
. . 52:
. . 53: /* ---[ decode ]--- */
. . 54:
. . 55: var right, left uint
. . 56:
620ms 620ms 57: finalbs := make([]byte, 8)
. . 58:
. . 59: idx := 0
1.08s 1.08s 60: for i := 0; i < len(varbs)-1; i++ {
360ms 360ms 61: right = uint(i) % 8
20ms 20ms 62: left = 7 - right
230ms 230ms 63: if i == 7 {
. . 64: continue
. . 65: }
840ms 840ms 66: vbcurr := varbs[i]
900ms 900ms 67: vbnext := varbs[i+1]
. . 68:
120ms 120ms 69: x := vbcurr & byte(0x7f)
670ms 670ms 70: y := x >> right
670ms 670ms 71: z := vbnext << left
650ms 650ms 72: finalbs[idx] = y | z
780ms 780ms 73: idx++
. . 74: }
. . 75:
540ms 2.19s 76: u = binary.LittleEndian.Uint64(finalbs)
270ms 270ms 77: return u, nil
. . 78:}
</code></pre></div>
<p>If you compare it to the pprof before the optimization, the top half looks about the same, but the bottom half is dramatically different. For example, more than 30s was spent in <code class="so">binary.Read(&buf, binary.LittleEndian, &u)</code> in the original version. The replacement code, <code class="so">binary.LittleEndian.Uint64(finalbs)</code>, only takes up about 2 seconds of processing time.</p>
<p>The only remaining spot I see for any further optimization is the 15s (out of 35s) spent in <code class="so">r.Read(ba[:])</code>. The problem, however, is that with a varint you don't know how many bytes long it is in advance, so you have read and examine them one at a time. There is probably a way to optimize this, but I haven't attempted it yet.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com31tag:blogger.com,1999:blog-2977002084155733470.post-24821407893197642542015-06-07T16:25:00.000-04:002015-07-03T08:26:41.326-04:00Merkle Tree<p>I hit upon the need this week to do checkpointing in a data processing system that has the requirement that no data event can ever be lost and no events can be processed and streamed out of order. I wanted a way to auto-detect this in production in real time.</p>
<p>There are a couple of ways to do this, but since our data events already have a signature attached to them (a SHA1 hash), I decided that a useful way to do the checkpoint is basically keep a hash of hashes. One could do this with a <a href="https://en.wikipedia.org/wiki/Hash_list">hash list</a>, where a chain of hashes for each data element is kept and when a checkpoint occurs the hash of all those hashes <strong>in order</strong> is taken.</p>
<p>A disadvantage of this model is if the downstream system detects a hash mismatch (either due to a lost message or messages that are out-of-order) it would then have to iterate the full list to detect where the problem is.</p>
<p>An elegant alternative is a hash tree, aka a <strong>Merkle Tree</strong> named after its inventor Ralph Merkle.</p>
<p><br /></p>
<h4><code>/* ---[ Merkle Trees ]--- */</code></h4>
<p>Merkle trees are typically implemented as binary trees where each non-leaf node is a hash of the two nodes below it. The leaves can either be the data itself or a hash/signature of the data.</p>
<p>Thus, if any difference at the root hash is detected between systems, a binary search can be done through the tree to determine which particular subtree has the problem. Thus typically only <code class="so">log(N)</code> nodes need to be inspected rather than all <code class="so">N</code> nodes to find the problem area.</p>
<p>Merkle trees are particularly effective in distributed systems where two separate systems can compare the data on each node via a Merkle tree and quickly determine which data sets (subtrees) are lacking on one or the other system. Then only the subset of missing data needs to be sent. Cassandra, based on Amazon's Dynamo, for example, uses Merkle trees as an <a href="https://wiki.apache.org/cassandra/AntiEntropy">anti-entropy measure</a> to detect inconsistencies between replicas.</p>
<p>The <a href="http://adc.sourceforge.net/draft-jchapweske-thex-02.html">Tree Hash EXchange format</a> (THEX) is used in some peer-to-peer systems for file integrity verification. In that system the internal (non-leaf) nodes are allowed to have a different hashing algorithm than the leaf nodes. In the diagram below <code class="so">IH=InternalHashFn</code> and <code class="so">LH=LeafHashFn</code>.</p>
<p><img src="https://docs.google.com/drawings/d/1HQDgOwt3LYc6YlgUk_fZ_gLoYbgfMmy_Sq6EwR4tobg/pub?w=532&h=263"></p>
<p>The THEX system also defines a serialization format and format for dealing with incomplete trees. The THEX system ensures that all leaves are at the same depth from the root node. To do that it "promotes" nodes. That is when a parent only has one child, it cannot does not take a hash of the child hash; instead it just "inherits" it. If that is confusing, think of the Merkle tree as being built from the bottom up: all the leaves are present and hashes of hashes are built until a single root is present.</p>
<p><img src="https://docs.google.com/drawings/d/1b-E2iWmhK3p5PaINOeNuvwNq6DLXXdk9nCujEdJm8Vw/pub?w=666&h=366"></p>
<p><small><b>Notation: The first token is a node label, followed by a conceptual value for the hash/signature of the node. Note that E, H and J nodes all have the same signature, since they only have one child node.</b></small></p>
<p><br /></p>
<h4><code>/* ---[ Merkle Tree as Checkpoint Data ]--- */</code></h4>
<p>I recently published my implementation of a Merkle Tree: <a href="https://github.com/quux00/merkle-tree"><a href='https://github.com/quux00/merkle-tree'>https://github.com/quux00/merkle-tree</a></a></p>
<p>Before I describe the implementation, it will help to see the use case I'm targeting.</p>
<p><img src="https://docs.google.com/drawings/d/1fTZBLqXlwg9eJQmfCNtiAWJ_hrtglmWGkwMFWaWW-yY/pub?w=651&h=137"></p>
<p>The scenario above is a data processing pipeline where messages flow in one direction. All the messages that come out of A go into B and are processed and transformed to some new value-added structure and sent on to C. In between are queues to decouple the systems.</p>
<p>Throughput needs to be as high as possible and every message that comes out of A must be processed by B and sent to C in the same order. No data events can be lost or reordered. System A puts a signature (a SHA1 hash) into the metadata of the event and that metadata is present on the message event that C receives.</p>
<p>To ensure that all messages are received and in the correct order, a checkpoint is periodically created by A, summarizing all the messages sent since the last checkpoint. That checkpoint message is put onto the Queue between A and B; B passes it downstream without alteration so that C can read it. Between checkpoints, system C keeps a running list of all the events it has received so that it can compute the signatures necessary to validate what it has received against the checkpoint message that periodically comes in from A.</p>
<p><br /></p>
<h4><code>/* ---[ My Implementation of a Merkle Tree ]--- */</code></h4>
<p>The THEX Merkle Tree design was the inspiration for my implementation, but for my use case I made some simplifying assumptions. For one, I start with the leaves already having a signature. Since THEX is designed for file integrity comparisons, it assumes that you have segmented a file into fixed size chunks. That is not the use case I'm targeting.</p>
<p>The THEX algorithm "salts" the hash functions in order to ensure that there will be no collisions between the leaf hashes and the internal node hashes. It concatenates the byte <code class="so">0x01</code> to the internal hash and the byte <code class="so">0x00</code> to the leaf hash:</p>
<div class="precode"><pre><code>internal hash function = IH(X) = H(0x01, X)
leaf hash function = LH(X) = H(0x00, X)
</code></pre></div>
<p>It is useful to be able to distinguish leaf from internal nodes (especially when deserializing), so I morphed this idea into one where each Node has a type byte -- <code class="so">0x01</code> identifies an internal node and <code class="so">0x00</code> identifies a leaf node. This way I can leave the incoming leaf hashes intact for easier comparison by the downstream consumer.</p>
<p>So my <code class="so">MerkleTree.Node</code> class is:</p>
<div class="precode"><pre><code>static class Node {
public byte type; // INTERNAL_SIG_TYPE or LEAF_SIG_TYPE
public byte[] sig; // signature of the node
public Node left;
public Node right;
}
</code></pre></div>
<p><br /></p>
<h4><code>/* ---[ Hash/Digest Algorithm ]--- */</code></h4>
<p>Since the leaf nodes are being passed in, my MerkleTree does not know (or need to know) what hashing algorithm was used on the leaves. Instead it only concerns itself with the internal leaf node digest algorithm.</p>
<p>The choice of hashing or digest algorithm is important, depending if you want to maximize performance or security. If one is using a Merkle tree to ensure integrity of data between peers that should not trust one another, then security is paramount and a cryptographically secure hash, such as SHA-256, <a href="https://en.wikipedia.org/wiki/Tiger_%28cryptography%29">Tiger</a>, or SHA-3 should be used.</p>
<p>For my use case, I was not concerned with detecting malicious tampering. I only need to detect data loss or reordering, and have as little impact on overall throughput as possible. For that I can use a CRC rather than a full hashing algorithm.</p>
<p>Earlier I ran some benchmarks comparing the speed of Java implementations of SHA-1, Guava's Murmur hash, CRC32 and <a href="https://en.wikipedia.org/wiki/Adler-32">Adler32</a>. Adler32 (<a href="https://docs.oracle.com/javase/7/docs/api/java/util/zip/Adler32.html">java.util.zip.Adler32</a>) was the fastest of the bunch. The typical use case for the Adler CRC is to detect data transmission errors. It trades off reliability for speed, so it is the weakest choice, but I deemed it sufficient to detect the sort of error I was concerned with.</p>
<p>So in my implementation the Adler32 checksum is hard-coded into the codebase. But if you want to change that we can either make the internal digest algorithm injectable or configurable or you can just copy the code and change it to use the algorithm you want.</p>
<p>The rest of the code is written to be agnostic of the hashing algorithm - all it deals with are the bytes of the signature.</p>
<p><br /></p>
<h4><code>/* ---[ Serialization / Deserialization ]--- */</code></h4>
<p>My implementation has efficient binary serialization built into the MerkleTree and an accompanying <code class="so">MerkleDeserializer</code> class that handles the deserialization.</p>
<p>I chose not to use the Java Serialization framework. Instead the <code class="so">serialize</code> method just returns an array of bytes and deserialize accepts that byte array.</p>
<p>The serialization format is:</p>
<div class="precode"><pre><code>(magicheader:int)(numnodes:int)
[(nodetype:byte)(siglength:int)(signature:[]byte)]
</code></pre></div>
<p>where <code class="so">(foo:type)</code> indicates the name (foo) and the type/size of the serialized element. I use a <a href="https://en.wikipedia.org/wiki/Magic_number_%28programming%29">magic header</a> of <code class="so">0xcdaace99</code> to allow the deserializer to be certain it has received a valid byte array.</p>
<p>The next number indicates the number of nodes in the tree. Then follows an "array" of <code class="so">numnodes</code> size where the elements are the node type (<code class="so">0x01</code> for internal, <code class="so">0x00</code> for leaf), the length of the signature and then the signature as an array of bytes <code class="so">siglength</code> long.</p>
<p>By including the <code class="so">siglength</code> field, I can allow leaf nodes signatures to be "promoted" to the parent internal node when there is an odd number of leaf nodes. This allows the internal nodes to use signatures of different lengths.</p>
<p><br /></p>
<h4><code>/* ---[ Usage ]--- */</code></h4>
<p>For the use case described above, you can imagine that system A does the following:</p>
<div class="precode"><pre><code>List<String> eventSigs = new ArrayList<>();
while (true) {
Event event = receiveEvent();
String hash = computeHash(event);
// ... process and transmit the message to the downstream Queue
sendToDownstreamQueue(hash, event);
eventSigs.add(has);
if (isTimeForCheckpoint()) {
MerkleTree mtree = new MerkleTree(eventSigs);
eventSigs.clear();
byte[] serializedTree = mtree.serialize();
sendToDownstreamQueue(serializedTree);
}
}
</code></pre></div>
<p>And system C would then do something like:</p>
<div class="precode"><pre><code>List<String> eventSigs = new ArrayList<>();
while (true) {
Event event = receiveEvent();
if (isCheckpointMessage(event)) {
MerkleTree mytree = new MerkleTree(eventSigs);
eventSigs.clear();
byte[] treeBytes = event.getDataAsBytes();
MerkleTree expectedTree = MerkleDeserializer.deserialize(treeBytes);
byte[] myRootSig = mytree.getRoot().sig;
byte[] expectedRootSig = expectedTree.getRoot().sig;
if (!signaturesAreEqual(myRootSig, expectedRootSig)) {
evaluateTreeDifferences(mytree, expectedTree);
// ... send alert
}
} else {
String hash = event.getOriginalSignature();
eventSigs.add(hash);
// .. do something with event
}
}
</code></pre></div>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com10tag:blogger.com,1999:blog-2977002084155733470.post-9498501364958112052014-12-25T20:10:00.000-05:002015-03-08T09:04:12.258-04:00Hooking up Kafka to Storm with the KafkaSpout in Storm 0.9.3<p>I have recently published a code example for using the Kafka Spout that is now part of Storm 0.9.3. After wasting a day fighting with incompatible logging frameworks between Kafka and Storm, I found <a href="https://github.com/miguno/kafka-storm-starter">an example project</a> in Scala that had the necessary exclusions to get the uber-jar to run in Storm cluster mode. I've converted that example to Java and Maven, rather than Scala and sbt, and considerably simplified the examples so you can focus on just one thing: getting Kafka hooked up to Storm using the KafkaSpout.</p>
<p>The code repo is here: <a href="https://github.com/quux00/kstorm"><a href='https://github.com/quux00/kstorm'>https://github.com/quux00/kstorm</a></a></p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com9tag:blogger.com,1999:blog-2977002084155733470.post-11129003392715382062014-10-19T11:59:00.000-04:002014-10-19T15:15:50.438-04:00Updated microbenchmarks for Java String tokenization<p>I've been focusing a lot on Java performance lately and ran across a <a href="https://programmers.stackexchange.com/questions/221997/quickest-way-to-split-a-delimited-string-in-java">Programmers StackExchange post</a> asking the most efficient way to tokenize a string in Java. It struck a nerve with me because the most common way to do this is to use <code class="so">String#split</code>. But the <code class="so">split</code> method takes as its tokenization delimiter a string that gets compiled into a regular expression. Which seems nice when you need it, but likely to be rather inefficient if all you need is to split on a character, such as a space. Then I looked up the old <code class="so">StringTokenizer</code> class which I used to use years and years ago. And its Javadoc has this interesting tidbit:</p>
<blockquote>
<p>StringTokenizer is a legacy class that is retained for compatibility reasons although its use is discouraged in new code. It is recommended that anyone seeking this functionality use the split method of String or the java.util.regex package instead. </p>
</blockquote>
<p>Strangely, however, <a href="http://programmers.stackexchange.com/a/222000/55056">the accepted answer</a> for the StackExchange question links to <a href="http://demeranville.com/battle-of-the-tokenizers-delimited-text-parser-performance/">a blog post</a> that shows benchmarks claiming that StringTokenizer is faster than <code class="so">String#split</code>. So why shouldn't I use StringTokenizer if I don't need a regex to split a string into fields?</p>
<p><br /></p>
<h4><code>/* ---[ Someone is wrong on the internet ]--- */</code></h4>
<p><img src="https://sslimgs.xkcd.com/comics/duty_calls.png" alt="Someone is wrong on the internet" title="" /></p>
<p>Well, that blog post needs to be updated for two reasons:</p>
<ol>
<li>it used Java 6, so we need to see whether things are different in Java 7 and 8</li>
<li>microbenchmarks are hard to do correctly and the author used questionable means (for example - there is not much warm up time and his timings are awfully short)</li>
</ol>
<p>The difficulty of doing accurate microbenchmarks has been greatly assuaged by the creation of the <a href="http://openjdk.java.net/projects/code-tools/jmh/">JMH benchmark tool</a>. If you haven't adopted it yet, put it at the top your technical TODO list. The documentation is excellent and it comes with many useful samples.</p>
<p><br /></p>
<h4><code>/* ---[ Splitting a Java string into tokens ]--- */</code></h4>
<p>Of the techniques used in the original post, I am interested in four candidates:</p>
<ol>
<li>tokenize the string yourself with <code class="so">String#indexOf</code></li>
<li>use <code class="so">String#split</code></li>
<li>use the almost deprecated <code class="so">StringTokenizer</code></li>
<li>use Guava's <a href="http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/base/Splitter.html">Splitter</a></li>
</ol>
<p>Here are the reported outcomes of the earlier measurements for these 4 options:</p>
<div class="precode"><pre><code>IndexOf: 50ms
StringTokenizer: 89ms
GuavaSplit: 109ms
Split: 366ms
</code></pre></div>
<p>I reran the author's exact code on my system using Java 7 and got the following:</p>
<div class="precode"><pre><code>IndexOf: 52ms
StringTokenizer: 104ms
GuavaSplit: 119ms
Split: 145ms
</code></pre></div>
<p>So using his benchmark technique, I got the same ordering, though the ratios have changed a bit. In Java 7, split is only 3 times slower than index, rather than 7 times slower.</p>
<p><br /></p>
<h4><code>/* ---[ What does JMH say? ]--- */</code></h4>
<p>I mildly rewrote these benchmarks using JMH. I also made longer strings to tokenize, rather than the two token string used by the blog post author, as that seemed a more realistic data set. And I used three strings, instead of one:</p>
<div class="precode"><pre><code>String[] lines = new String[]{
"0000 12 34 5 666 77 88888 99",
"aa bb cc dd ee ff gg hh ii jj kk ll mm nn oo pp qq rr ss tt uu vv ww xx yy zz",
"Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod"
};
</code></pre></div>
<p>The JMH based benchmark code is listed below. The results are rather interesting. In the original benchmarks raw time is measure, so lower is better. With JMH, I measured throughput (the default metric) in operations/second, so <strong>higher is better</strong>:</p>
<p>With Java 7 (1.7.0_60-b19) the results were:</p>
<div class="precode"><pre><code>m.JavaStringSplits.indexOf thrpt 10 840.147 ± 28.553 ops/ms
m.JavaStringSplits.javaSplit thrpt 10 694.870 ± 3.858 ops/ms
m.JavaStringSplits.stringTokenizer thrpt 10 473.812 ± 8.422 ops/ms
m.JavaStringSplits.guavaSplit thrpt 10 392.759 ± 8.707 ops/ms
</code></pre></div>
<p>And with Java 8 (1.8.0_20-ea):</p>
<div class="precode"><pre><code>m.JavaStringSplits.indexOf thrpt 10 827.136 ± 30.831 ops/ms
m.JavaStringSplits.javaSplit thrpt 10 700.809 ± 7.215 ops/ms
m.JavaStringSplits.stringTokenizer thrpt 10 480.788 ± 16.793 ops/ms
m.JavaStringSplits.guavaSplit thrpt 10 386.398 ± 5.323 ops/ms
</code></pre></div>
<p>With the presumably more robust and accurate JMH model of measuring microbenchmarks, <code class="so">String#split</code> moved up the ranks and handily outperforms both <code class="so">StringTokenizer</code> and Guava <code class="so">Splitter</code>.</p>
<p>My hand-coded splitter using <code class="so">indexOf</code> was about 18% "faster" (higher throughput) than <code class="so">Java#split</code>, so we do see some overhead in <code class="so">Java#split</code>, but for most scenarios I conclude that the Javadoc for StringTokenizer is correct: use <code class="so">String#split</code> for most scenarios unless you know that 1) you don't need regular expressions to tokenize and 2) string splitting is your bottleneck.</p>
<p>A follow-up set of tests that could be done would be on very large strings. In his <a href="http://mechanical-sympathy.blogspot.com/2011/07/let-caller-choose.html">Letter the Caller Choose</a> Mechanical Sympathy post from a few years ago, Martin Thompson advocated devising an API where you pass in the datastructure to be populated during the tokenization, rather than relying one to be created in the underlying tokenization method and passed back to you. He states (but does not demonstrate):</p>
<blockquote>
<p>In the Java world this idiom becomes critical to performance when large arrays are involved. </p>
</blockquote>
<p><br /></p>
<h4><code>/* ---[ Find the flaw ]--- */</code></h4>
<p>One of my favorite interview questions is to put a piece of code in front of someone and say "find the flaws". And Aleksey Shipilëv, the author of JMH, states:</p>
<blockquote>
<p>Your [JMH] benchmarks should be peer-reviewed.</p>
</blockquote>
<p>Mine have not been, so I throw it out to the internet to find the flaws in my quick analysis.</p>
<p><br /></p>
<h4><code>/* ---[ The code and setup ]--- */</code></h4>
<br />
<script src="https://gist.github.com/quux00/8882422fcf40c7adbf1b.js"></script>
<script src="https://gist.github.com/quux00/def9a448bb42493fbedf.js"></script>
<p>Benchmarks were performed on:</p>
<p>Ubuntu (Xubuntu) 14.04 LTS with 3.13.0-37 Linux kernel with 8 Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz cores.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com4tag:blogger.com,1999:blog-2977002084155733470.post-50730759447351552422014-03-17T21:41:00.001-04:002014-03-17T21:52:21.082-04:00Rust namespaces by example<p><br /></p>
<h4><code>/* ---[ Cheat sheet for Rust namespaces ]--- */</code></h4>
<p>Rust namespaces can be a little mind-bending. This brief blog post is meant to provide instruction by example on setting up an application or library of Rust code that uses multiple files in a hierarchical namespace.</p>
<p>Though the current <a href="https://github.com/mozilla/rust/wiki/Docs-project-structure">docs-project-structure guide</a> on the Rust wiki is pretty sparse, you should start there. Then read the section on <a href="http://static.rust-lang.org/doc/master/tutorial.html#crates-and-the-module-system">Crates and Modules in the tutorial</a>.</p>
<p>I used those references plus an examination of how files and namespaces in the libstd code tree are structured to come up with this example.</p>
<p>In this simple example, I want to have an application where things are namespace to the top level module <code class="so">abc</code>. I want to have a couple of files (namespaces) under <code class="so">abc</code>, some additional directories (namespaces) below <code class="so">abc</code>, such as <code class="so">abc::xyz</code> and have modules in the <code class="so">abc::xyz</code> namespace. Furthermore, I want all those namespaces to be able to refer to each - both down the chain and up the chain.</p>
<p>Here is a simple example that illustrates how to do it. I am using Rust-0.10pre (built 16-Mar-2014).</p>
<p>First, I have a project I called "<a href="http://www.space.com/19338-manatee-nebula-celestial-wonder.html">space-manatee</a>", under which I have a <code class="so">src</code> directory and then my code hierarchy starts:</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ tree
.
├── abc
│ ├── mod.rs
│ ├── thing.rs
│ ├── wibble.rs
│ └── xyz
│ ├── mod.rs
│ └── waldo.rs
└── main.rs
2 directories, 6 files
</code></pre></div>
<p>To provide a namespace <code class="so">foo</code> in Rust, you can either create a file called <code class="so">foo.rs</code> or a dir/file combo of <code class="so">foo/mod.rs</code>. The content of my <code class="so">abc/mod.rs</code> is:</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ cat abc/mod.rs
pub mod thing;
pub mod wibble;
pub mod xyz;
</code></pre></div>
<p>All this module does is export other modules in the same directory. It could have additional code in it - functions and data structures, but I elected not to do that.</p>
<p><br><br /><code>xyz</code> is a directory, and since I created the <code class="so">xyz/mod.rs</code> dir/file combo, it is a namespace that can be used and exported.</p>
<p>Let's look into the other files:</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ cat abc/thing.rs
extern crate time;
use time::Tm;
pub struct Thing1 {
name: ~str,
when: time::Tm,
}
pub fn new_thing1(name: ~str) -> ~Thing1 {
~Thing1{name: name, when: time::now()}
}
</code></pre></div>
<p><code class="so">thing.rs</code> pulls in the rustlang <code class="so">time</code> crate and then defines a struct and constructor for it. It doesn't reference any other space-manatee code.</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ cat abc/wibble.rs
use abc::thing;
use abc::thing::Thing1;
pub struct Wibble {
mything: ~Thing1
}
pub fn make_wibble() -> ~Wibble {
~Wibble{mything: thing::new_thing1(~"cthulu")}
}
</code></pre></div>
<p><code class="so">wibble.rs</code>, however, does reference other space-manatee projects, so it uses the fully qualified namespace from the top of the hierarchy, but it does not have to explicitly "import" anything. It can find the <code class="so">thing</code> namespace without a <code class="so">mod</code> declaration because <code class="so">thing.rs</code> is in the same directory.</p>
<p><br><br />OK, let's look into the <code class="so">xyz</code> directory now.</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ cat abc/xyz/mod.rs
pub mod waldo;
</code></pre></div>
<p>That just exports the waldo namespace in the same directory. What's in waldo?</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ cat abc/xyz/waldo.rs
use abc::wibble::Wibble;
pub struct Waldo {
magic_number: int,
w: ~Wibble
}
</code></pre></div>
<p>The Waldo struct references the Wibble struct that is higher than it in the hierarchy. Notice there is no "import" via a <code class="so">mod</code> statement - apparently going up the hierarchy requires no import.</p>
<p>So that's the supporting cast. Let's see how the main.rs program uses them:</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ cat main.rs
extern crate time;
use abc::{thing,wibble};
use abc::thing::Thing1;
use abc::wibble::Wibble;
use abc::xyz::waldo::Waldo;
pub mod abc;
fn main() {
let tg: ~Thing1 = thing::new_thing1(~"fred");
println!("{}", tg.name);
let wb: ~Wibble = wibble::make_wibble();
println!("{}", wb.mything.name);
let wdo = Waldo{magic_number: 42,
w: wibble::make_wibble()};
println!("{:?}", wdo);
}
</code></pre></div>
<p>The only <code class="so">mod</code> "import" <code class="so">main.rs</code> had to do is of the <code class="so">abc</code> namespace - which is in the same directory as main.rs. In fact, that is all you can import. If you try <code class="so">mod abc::thing</code> the compiler will tell you that you aren't doing it right.</p>
<p>By importing <code class="so">abc</code>, you are importing <code class="so">abc/mod.rs</code>. Go back up and look at what <code class="so">abc/mod.rs</code> does - it imports other modules, which in turn import other modules, so they all end up being imported into <code class="so">main.rs</code> as addressable entities.</p>
<p><br><br />Once all those import references are set up, nothing special has to be done to compile and run it:</p>
<div class="precode"><pre><code>quux00:~/rustlang/space-manatee/src$ rustc main.rs
quux00:~/rustlang/space-manatee/src$ ./main
fred
cthulu
abc::xyz::waldo::Waldo{
magic_number: 42,
w: ~abc::wibble::Wibble{
mything: ~abc::thing::Thing1{
name: ~"cthulu",
when: time::Tm{tm_sec: 21i32,
tm_min: 26i32, tm_hour: 21i32, tm_mday: 17i32, tm_mon: 2i32,
tm_year: 114i32, tm_wday: 1i32, tm_yday: 75i32, tm_isdst: 1i32,
tm_gmtoff: -14400i32, tm_zone: ~"EDT", tm_nsec: 663891679i32
}
}
}
}
</code></pre></div>
<p>(I hand formatted the Waldo output for easier reading.)</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com6tag:blogger.com,1999:blog-2977002084155733470.post-43062040103353361392014-03-16T10:24:00.001-04:002014-03-16T10:24:03.021-04:00Select over multiple Rust Channels<p><br /></p>
<h4><code>/* ---[ Channels in Rust ]--- */</code></h4>
<p>The channel paradigm for CSP-based concurrency has received a lot of attention lately since it is the <a href="http://blog.golang.org/pipelines">foundational concurrency paradigm in Go</a> and Clojure has embraced it with core.async. It turns out that <a href="http://www.rust-lang.org/">Rust, the new language from Mozilla</a>, also fully embraces channel-based message passing concurrency.</p>
<p>Both Go and Clojure's core.async have a <code class="so">select</code> operation that allows your code to wait on multiple channels and respond to the first one that is ready. This is based, at least conceptually, on the Unix <a href="http://linux.die.net/man/2/select">select system call</a> that monitors multiple file descriptors.</p>
<p>Rust also has a select operation. And it has a <a href="http://static.rust-lang.org/doc/master/std/macros/macro.select.html">select! macro</a> to make using it easier. Here's an example:</p>
<div class="precode"><pre><code>use std::io::Timer;
fn use_select_macro() {
let (ch, pt): (Sender<~str>, Receiver<~str>) = channel();
let mut timer = Timer::new().unwrap();
let timeout = timer.oneshot(1000);
select! (
s = pt.recv() => println!("{:s}", s),
() = timeout.recv() => println!("timed out!")
);
}
</code></pre></div>
<p>Channels and Ports are now called Senders and Receivers in Rust. As with select in Go, if the Receiver called <code class="so">pt</code> has a message come in before the 1 second timer goes off, its code block will execute. Otherwise, the timer's Receiver will be read from and its code block executed, printing "timed out".</p>
<p>Note that the <code class="so">select!</code> macro uses parens, like a function call, not curly braces like a code block.</p>
<p>The <code class="so">select!</code> macro is currently labelled experimental, since it has some limitations. One I hit this week is that it will fail (as in, not compile) if you embed the Receiver in a struct:</p>
<div class="precode"><pre><code>
fn does_not_compile() {
let (ch, pt): (Sender<~str>, Receiver<~str>) = channel();
let a = A{c: ch, p: pt};
let mut timer = Timer::new().unwrap();
let timeout = timer.oneshot(1000);
select! (
s = a.p.recv() => println!("{:s}", s),
() = timeout.recv() => println!("time out!")
);
}
</code></pre></div>
<p>This fails with <code class="so">error: no rules expected the token '.'</code>. I've filed an issue for it here: <a href="https://github.com/mozilla/rust/issues/12902#issuecomment-37714663"><a href='https://github.com/mozilla/rust/issues/12902#issuecomment-37714663'>https://github.com/mozilla/rust/issues/12902#issuecomment-37714663</a></a></p>
<p><br /></p>
<h4><code>/* ---[ Using the Rust Channel Select API ]--- */</code></h4>
<p>The workaround is to use the Select API directly. Here's how you do it:</p>
<div class="precode"><pre><code>
use std::comm::Select;
use std::io::Timer;
fn select_from_struct() {
let (ch, pt): (Sender<~str>, Receiver<~str>) = channel();
let mut timer = Timer::new().unwrap();
let timeout = timer.oneshot(1000);
let a = A{c: ch, p: pt};
let sel = Select::new();
let mut pt = sel.handle(&a.p);
let mut timeout = sel.handle(&timeout);
unsafe { pt.add(); timeout.add(); }
let ret = sel.wait();
if ret == pt.id() {
let s = pt.recv();
println!("ss: {:?}", s);
} else if ret == timeout.id() {
let () = timeout.recv();
println!("TIMEOUT!!");
}
}
</code></pre></div>
<p>It's a little more code, but fairly straightforward to follow. You wrap your Receivers in a select Handle and them add them add them to the Receiver set via the <code class="so">add</code> method (which must be wrapped in an <code class="so">unsafe</code> block). Each handle gets an id so you can discover which one returned first.</p>
<p>Finally you wait. When the wait returns you check the return id and execute the appropriate block of code, which starts by call <code class="so">recv</code> on the Receiver to get the incoming value (if any).</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com2tag:blogger.com,1999:blog-2977002084155733470.post-25287091481601494102014-01-26T12:28:00.001-05:002014-10-19T10:58:46.195-04:00Debugging Rust with gdb<p><strong>[Update]:</strong> <em>This blog post has been updated to Rust 0.11 as of mid-April 2014. The previous version was for Rust 0.9.</em></p>
<p>This blog entry outlines the current state of my understanding of how to use the gdb debugger for Rust programs. As of this writing, I'm using:</p>
<div class="precode"><pre><code>$ rustc -v
rustc 0.11-pre-nightly (e332287 2014-04-16 00:56:30 -0700)
host: x86_64-unknown-linux-gnu
$ gdb --version
GNU gdb (GDB) 7.6.1-ubuntu
</code></pre></div>
<p>A caveat before we begin: I'm not an expert in gdb and I'm (now less of) a newbie at Rust. I'm cataloging my findings for both my own future reference and to help anyone who needs to see an example in action. I'd welcome feedback on tips for better ways to do this.</p>
<p><br /></p>
<h4><code>/* ---[ GDB ]--- */</code></h4>
<p>I won't give a gdb tutorial. There are lots of good ones on the web, such as these:</p>
<ul>
<li><a href="http://betterexplained.com/articles/debugging-with-gdb/"><a href='http://betterexplained.com/articles/debugging-with-gdb/'>http://betterexplained.com/articles/debugging-with-gdb/</a></a></li>
<li><a href="http://www.unknownroad.com/rtfm/gdbtut/gdbtoc.html"><a href='http://www.unknownroad.com/rtfm/gdbtut/gdbtoc.html'>http://www.unknownroad.com/rtfm/gdbtut/gdbtoc.html</a></a></li>
<li><a href="http://beej.us/guide/bggdb/"><a href='http://beej.us/guide/bggdb'>http://beej.us/guide/bggdb</a></a></li>
</ul>
<p><br /></p>
<h4><code>/* ---[ The setup ]--- */</code></h4>
<p>The example I'll use is modified from an example from <a href="https://github.com/cmr">cmr</a> in this Rust issue: <a href="https://github.com/mozilla/rust/issues/10350"><a href='https://github.com/mozilla/rust/issues/10350'>https://github.com/mozilla/rust/issues/10350</a></a>. I've chosen this one because it shows jumping into both a regular (named) function and an anonymous closure.</p>
<p>The codebase consists of two files, both in the same directory:</p>
<p>quux.rs:</p>
<div class="precode"><pre><code>pub fn quux00(x: || -> int) -> int {
println!("DEBUG 123");
x()
}
</code></pre></div>
<p>and bar.rs</p>
<div class="precode"><pre><code>extern crate quux;
fn main() {
let mut y = 2;
{
let x = || {
7 + y
};
let retval = quux::quux00(x);
println!("retval: {:?}", retval);
}
y = 5;
println!("y : {:?}", y);
}
</code></pre></div>
<p>To compile them with debugging info included use the <code class="so">-g</code> switch (this changed since version 0.9):</p>
<div class="precode"><pre><code>$ rustc -g --crate-type lib quux.rs
$ rustc -g -L . bar.rs
</code></pre></div>
<p>Start the <code class="so">bar</code> program in gdb and let's set some breakpoints:</p>
<div class="precode"><pre><code>$ gdb bar
(gdb) break bar::main
Breakpoint 1 at 0x4042c0: file bar.rs, line 3.
(gdb) rbreak quux00
Breakpoint 2 at 0x43e760: file quux.rs, line 1.
int quux::quux00(int ())(int ());
(gdb) info breakpoints
Num Type Disp Enb Address What
1 breakpoint keep y 0x00000000004042c0 in bar::main at bar.rs:3
2 breakpoint keep y 0x000000000043e760 in quux::quux00 at quux.rs:1
</code></pre></div>
<p>For the first breakpoint, I know the full path, so I just use <code class="so">break</code>.</p>
<p>Sometimes correct full paths in Rust can be tricky, especially for functions that are parametized, so it can be easier to just use <code class="so">rbreak</code>, which takes a regular expression. All functions that match the regex will have a breakpoint set.</p>
<p>The second breakpoint does have the word "quux00" in it, but it's been mangled. There's a way to change that in Rust, but let's move on for the moment.</p>
<p><br /></p>
<h4><code>/* ---[ Aside: rbreak ]--- */</code></h4>
<p>In my playing around so far, I've been unable to use <code class="so">break</code> to set a breakpoint for a function not in the file with the <code class="so">main</code> method, so <code class="so">rbreak</code> has been very useful.</p>
<p>The <code class="so">rbreak</code> command is pretty powerful. According to <a href="https://sourceware.org/gdb/onlinedocs/gdb/Set-Breaks.html">the documentation</a>, if you want to set a breakpoint for all functions, <code class="so">rbreak .</code> will do the trick. You don't want to do this for a rust application, because there are hundreds of functions that get compiled in.</p>
<p>Instead, you'll want to limit the scope of the regex search by limiting the search to a single file with:</p>
<div class="precode"><pre><code>(gdb) rbreak bar.rs:.
</code></pre></div>
<p>But again I've only gotten this to work for the "main" file. If I type <code class="so">rbreak quux.rs:.</code> it doesn't know what I'm talking about. Something for future research.</p>
<p><br /></p>
<h4><code>/* ---[ Let's debug ]--- */</code></h4>
<p>So now we've got two breakpoints set, as indicated by the output from <code class="so">info breakpoints</code>.</p>
<p>Let's start the debugging session:</p>
<div class="precode"><pre><code>(gdb) run
Starting program: /home/midpeter444/lang/rust/sandbox/debug/./bar
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
... deleted a bunch of info about threads starting up ...
Breakpoint 1, bar::main () at bar.rs:3
3 fn main() {
(gdb) n
4 let mut y = 2;
(gdb) n
9 let retval = quux::quux00(x);
(gdb) list
4 let mut y = 2;
5 {
6 let x = || {
7 7 + y
8 };
9 let retval = quux::quux00(x);
10 println!("retval: {:?}", retval);
11 }
12 y = 5;
13 println!("y : {:?}", y);
(gdb) p y
$1 = 2
(gdb) p x
$2 = {int ()} 0x7fffffffd4f8
</code></pre></div>
<p>Interesting that it seemed to skip lines 5-8 when I single stepped with <code class="so">n</code>. But the x value was captured as an unnamed function, as you can see on the last line of the readout.</p>
<p>Now we are on line 8 (confirmed with the <code class="so">frame</code> command below), so let's continue - our breakpoint on the quux00 function should now be tripped:</p>
<div class="precode"><pre><code>(gdb) frame
#0 bar::main () at bar.rs:9
9 let retval = quux::quux00(x);
(gdb) c
Continuing.
Breakpoint 2, quux::quux00 (x={int ()} 0x7fffffffd500) at quux.rs:1
1 pub fn quux00(x: || -> int) -> int {
</code></pre></div>
<p>Yes, it was tripped. Let's look around and single-step through it:</p>
<div class="precode"><pre><code>(gdb) frame
#0 quux::quux00 (x={int ()} 0x7fffffffd500) at quux.rs:1
1 pub fn quux00(x: || -> int) -> int {
(gdb) list
1 pub fn quux00(x: || -> int) -> int {
2 println!("DEBUG 123");
3 x()
4 }
(gdb) s
2 println!("DEBUG 123");
(gdb) p x
$4 = {int ()} 0x7fffffffd390
</code></pre></div>
<p>OK, we're inside the <code class="so">quux00</code> method. We stepped over the first instruction (the <code class="so">println</code>) and inspected the <code class="so">x</code> param, which is our anonymous Rust closure. Let's continue by stepping into the closure and see if that works:</p>
<div class="precode"><pre><code>(gdb) n
DEBUG 123
3 x()
(gdb) s
fn1356 () at bar.rs:6
6 let x = || {
(gdb) n
7 7 + y
(gdb) p y
$5 = 2
(gdb) n
bar::main () at bar.rs:10
10 println!("retval: {:?}", retval);
</code></pre></div>
<p>Excellent. That worked and we even had line numbers. Now we are back in the outer <code class="so">main</code> fn. BTW, note that the "anonymous" closure has a name: <code class="so">fn1356</code> - remember that name, we'll come back to it later.</p>
<p>It's an easy walk to the finish line from here:</p>
<div class="precode"><pre><code>(gdb) list
5 {
6 let x = || {
7 7 + y
8 };
9 let retval = quux::quux00(x);
10 println!("retval: {:?}", retval);
11 }
12 y = 5;
13 println!("y : {:?}", y);
14 }
(gdb) p retval
$3 = 9
(gdb) n
2
(gdb) p y
$4 = 2
(gdb) c
Continuing.
retval: 9
y : 5
[Inferior 1 (process 7007) exited normally]
</code></pre></div>
<p><br /></p>
<h4><code>/* ---[ Round 2: Set breakpoints on all methods in main file ]--- */</code></h4>
<p>Let's start over and set breakpoints on all the functions in the bar.rs file:</p>
<div class="precode"><pre><code>$ gdb bar
(gdb) rbreak bar.rs:.
Breakpoint 1 at 0x4042c0: file bar.rs, line 3.
static void bar::main();
Breakpoint 2 at 0x404520: file bar.rs, line 6.
static int fn1356()();
</code></pre></div>
<p>Aah, there's the name again: <code class="so">fn1356</code>. So that's another way to set a breakpoint on your closures. If we redo the session, we'll see that the breakpoint now gets tripped in the closure as it's being executed (from within the quux00 method):</p>
<div class="precode"><pre><code>(gdb) r
Starting program: /home/midpeter444/lang/rust/sandbox/debug/bar
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Breakpoint 1, bar::main () at bar.rs:3
warning: Source file is more recent than executable.
3 fn main() {
(gdb) c
Continuing.
DEBUG 123
Breakpoint 2, fn1356 () at bar.rs:6
6 let x = || {
(gdb) frame
#0 fn1356 () at bar.rs:6
6 let x = || {
(gdb) n
7 7 + y
(gdb) p y
$1 = 2
</code></pre></div>
<p><br /></p>
<h4><code>/* ---[ Round 3: Demangle function names ]--- */</code></h4>
<p>In the Rust 0.9 version of this post I showed how rust mangled the function names, but that seems to have gone away. You can still explicitly specify not to mangle function names like so:</p>
<div class="precode"><pre><code>#[no_mangle]
pub fn quux00(x: || -> int) -> int {
println("DEBUG 123");
x()
}
</code></pre></div>
<p>I haven't tried anything really complicated with Rust in gdb yet, but hopefully these examples serve to get you going.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com273tag:blogger.com,1999:blog-2977002084155733470.post-67085240131400042592014-01-26T12:16:00.000-05:002014-01-26T12:34:26.954-05:00Telephonic Whispers in Rust, revisited<p><br /></p>
<h4><code>/* ---[ Hitting the big time ]--- */</code></h4>
<p>My <a href="http://thornydev.blogspot.com/2014/01/chinese-whispers-in-rust.html">previous blog entry</a> was a bit of a trifle: it showed an implementation of an toy CSP (Communicating Sequential Process) application in Rust, comparing it to an example implementation in Go by Rob Pike. I discovered, post-hoc, that it hit <a href="http://www.reddit.com/r/rust/comments/1vnrp8/chinese_whispers_in_rust_and_go/">the Rust subreddit</a> and <a href="https://news.ycombinator.com/item?id=7089879">Hacker News</a>. There was some good discussion there and a few complaints.</p>
<p><br /></p>
<h4><code>/* ---[ Clarifications ]--- */</code></h4>
<p>First, the complaints. Of course this example was tuned for how Go works: the example was created by Rob Pike. The point of his example, and my blog post, was that goroutines (Rust tasks) are lightweight (green threads) that are multiplexed onto native OS threads. The example is meant to show that you can spawn up tens of thousands to hundreds of thousands of goroutines (Rust tasks) pretty rapidly. That's not something you can do in Java, for example: <a href="https://github.com/quux00/go-lightly/tree/master/go-lightly-examples/clj-examples#whispers">I've tried on my Linux system</a> and it cried uncle somewhere between 20,000 and 30,000 threads and hosed my system.</p>
<p>The <a href="http://static.rust-lang.org/doc/0.9/guide-tasks.html">Rust guide on Tasks</a> says:</p>
<blockquote>
<p>Rust can create hundreds of thousands of concurrent tasks<br />on a typical 32-bit system</p>
</blockquote>
<p>So remembering the Pike example, I thought I'd try it with Rust. My <em>primary</em> intent was just to show that I figured out how to implement it in Rust and that it worked. When you are learning Rust, getting something to <em>compile</em> is an achievement worth celebrating. The Rust compiler is wonderfully strict - enforcing all its rules in order to provide deterministic, safe memory management with static analysis rather than requiring a managed runtime. (But it can provide a managed runtime with Garbage Collection if you want that model, which is one of things that makes Rust so intriguing.)</p>
<p>The simple timings in my earlier blog post were included only because the numbers were interestingly different. The reasons for that difference was the most interesting part of the community discussion and I certainly learned a few things I didn't know about Rust, so, despite the complaints, I'm glad I included it. There wasn't much point in doing formal extensive benchmarks, as some people suggested, because, as the other posters pointed out, the example is trifling and not something you would typically do.</p>
<p>Second, I called the thing "Chinese Whispers" only because that's what the esteemed Rob Pike called it and I was clearly doing a port of his work in the presentation I cited. The name makes no sense to me, but since there were charges of racism and suggestions of calling it "Broken Telephone", I'll now call it "Telephonic Whispers", since I'm not exactly sure what is "broken" about chaining a series of channels together and passing a message from one end to the other. Seems connected to me.</p>
<p>Third, I updated the blog with a few improvements. I shouldn't have described channels as "first class" in Rust, since that label seems to be reserved for things are a part of the core of a language. Rust channels are not built into the language in the way they are in Go. My point was that while these are in the std library and not in the core language, they are a central aspect of Rust's approach to concurrency. They are just as at hand out of the box as Go's channels are, unlike a language like Java where you have to construct them yourself from other concurrency constructs, such as a <a href="http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/SynchronousQueue.html">SynchronousQueue</a> or a <a href="http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/TransferQueue.html">TransferQueue</a>.</p>
<p><br /></p>
<h4><code>/* ---[ The interesting follow up: segmented stacks ]--- */</code></h4>
<p><a href="http://www.reddit.com/r/rust/comments/1vnrp8/chinese_whispers_in_rust_and_go/ceuatxh">Patrick Walton profiled the Rust code</a> and found that most of the time was spent allocating stacks. Go currently (I'm using version 1.1.2) uses something called "segmented stacks" rather than larger contiguous stacks. In the segmented stack model, you create small stacks for a thread/task/routine and when it needs more space you create another segment and keep track of them in some data structure, such as a linked list.</p>
<p>Since most of the work of the "Telephonic Whispers" example is spent creating a chain of 100,001 channels, it makes sense that systems that build larger stacks for each routine/task will take longer.</p>
<p>An advantage of a segmented stack model is that it allows you to quickly spawn up tasks and if they never need a lot of stack space, less memory is wasted. If the task needs more later, then it gets more on demand.</p>
<p>Rust used to have segmented stacks, but they were removed late in 2013, as announced here by Brian Anderson: <a href="https://mail.mozilla.org/pipermail/rust-dev/2013-November/006314.html"><a href='https://mail.mozilla.org/pipermail/rust-dev/2013-November/006314.html'>https://mail.mozilla.org/pipermail/rust-dev/2013-November/006314.html</a></a>. The Rust team found that the apparent advantages of compact memory caused performance problems and had compatibility issues with integrating with foreign code (typically C) and with LLVM libc optimizations.</p>
<p>And now, as pointed out in the "Chinese Whispers" community discussions, it looks like <a href="https://docs.google.com/document/d/1wAaf1rYoM4S4gtnPh0zOlGzWtrZFQ5suE8qr2sD8uWQ/pub">Go will be moving away from segmented stacks</a> too. The primary issue they cite is what Brian Anderson above calls "stack thrashing": when you have heavy looping and that code is continually hitting a stack boundary, causing stack allocations to happen very frequently, thus significantly affecting performance.</p>
<p><br /></p>
<h4><code>/* ---[ Valid consideration: Number of native threads ]--- */</code></h4>
<p>Another important point made in the "whispers" community discussion was about the underlying threading defaults: in Go version 1, only a single native OS thread is created even if you spawn multiple goroutines. To change that you have to manually set it via the <code class="so">runtime.GOMAXPROCS(int)</code> function. So in the Pike example, only one thread is being used.</p>
<p>Rust v0.9 uses multiple threads by default and has to do synchronization between threads. So that might account for some of the slow down between the Go and Rust versions. But Walton's profiling showed that most of the time is the stack allocation, so this consideration is probably secondary.</p>
<p>I did a small experiment on this front by setting <code class="so">GOMAXPROCS</code> to 8 (the number of CPUs on my system):</p>
<script src="https://gist.github.com/quux00/8635984.js"></script>
<p>Then I did a small simple benchmark where I looped 50 times running the Go "whispers" code either with the default GOMAXPROCS setting or GOMAXPROCS=NumCPU (8). I ran each three times and saw consistent results. Here are two representative runs:</p>
<p>GOMAXPROCS = <strong>default</strong>:</p>
<div class="precode"><pre><code>$ time ./whispers
100001
real 0m5.569s
user 0m5.403s
sys 0m0.168s
</code></pre></div>
<p>GOMAXPROCS = <strong>NumCPU (8)</strong></p>
<div class="precode"><pre><code>$ time ./whispers
100001
real 0m10.801s
user 0m20.413s
sys 0m6.007s
</code></pre></div>
<p>Using more CPUs causes the Go version to run about twice as slow. This would add support to the notion that this is part of the timing difference between Go and Rust for this example is due to the default number of threads that are spun up.</p>
<p><br /></p>
<h4><code>/* ---[ Final thoughts ]--- */</code></h4>
<p>To conclude, I want to state something that is obvious by now and was also discussed the community discussion: if you go to the effort of spawning up lots of tasks in Rust or goroutines in Go, design your application in such a way that they do some amount of significant work. Spawning more tasks or routines can have overhead that you may not need to pay. As <code class="so">strncat</code> <a href="http://www.reddit.com/r/rust/comments/1vnrp8/chinese_whispers_in_rust_and_go/ceuczim">says in the Reddit discussion</a>, Rust does not have true <a href="https://en.wikipedia.org/wiki/Coroutine">coroutines</a>. That doesn't mean you can't use tasks that way, but you'll need to be judicious about how you use them (and how many).</p>
<p>One example I'd like to implement in Rust is another port of some Rob Pike Go code: Lexical scanning and parsing use Goroutines: <a href="https://www.youtube.com/watch?v=HxaD_trXwRE"><a href='https://www.youtube.com/watch?v=HxaD_trXwRE'>https://www.youtube.com/watch?v=HxaD_trXwRE</a></a></p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com6tag:blogger.com,1999:blog-2977002084155733470.post-54008161001046645212014-01-19T19:34:00.000-05:002014-01-26T12:34:13.428-05:00Telephonic Whispers in Rust<p><br /></p>
<h4><code>/* ---[ CSP: an idea whose time has come ]--- */</code></h4>
<p>Of late, the Go language has popularized the CSP (Communicating Sequential Processes) style of programming. Rob Pike gives a great talk on Go's implementation of CSP with Go channels and goroutines in this presentation: <a href="http://www.youtube.com/watch?v=f6kdp27TYZs">Google I/O 2012 - Go Concurrency Patterns</a>.</p>
<p>After watching that presentation, I myself got inspired and wrote a <a href="https://github.com/quux00/go-lightly">Go-inspired CSP library in Clojure</a>. Later, Rich Hickey and team came and built an even better version, <a href="https://github.com/clojure/core.async">core.async</a>, that has gotten a lot of acclaim.</p>
<p>Recently, I've been learning the Rust language and was intrigued and happy to see that the CSP model is also embraced front-and-center by the Rust team. Like Go, the core primitive for message passing is a channel and Rust has lightweight routines (green threads), called tasks in Rust.</p>
<p>One of the first things I did when implementing a CSP library in Go was to port Pike's Go examples from this Google I/O talk to Clojure. Here I do that in Rust for the "Chinese Whispers" example.</p>
<p><br /></p>
<h4><code>/* ---[ Telephonic Whispers ]--- */</code></h4>
<p>Pike shows this example in his 2012 Heroku presentation to show off the idea that you can spawn up a lot of lightweight goroutines and have it run efficiently. Since Rust tasks are lightweight, I wanted to test whether Rust would behave similarly.</p>
<p>In the Chinese Whispers example, a daisy-chain of go routines are formed and they communicate unidirectionally along a series of channels. Go routine A signals to B who signals to C, etc. The message passed along the way is an integer than is incremented on each hand off.</p>
<script src="https://gist.github.com/quux00/8449996.js"></script>
<p>With the Go example, you can run a daisy-chain of 100,000 go routines very efficiently:</p>
<div class="precode"><pre><code>$ time ./chinese-whispers
100001
real 0m0.322s
user 0m0.215s
sys 0m0.105s
</code></pre></div>
<p>Here's my code to do the same in Rust (v 0.9):</p>
<script src="https://gist.github.com/quux00/8450017.js"></script>
<p>A key difference is that in the Rust model a single channel actually comes in two parts: the port end, from which you receive, and a channel end, onto which you send data. The Go model has a single entity, the channel, which can be used for both sending and receiving, though you can create write-only or read-only channel handles.</p>
<p>This separation makes the Rust code a little more intricate and verbose. I also need additional variables, such as the temp variables on lines 16 and 17, since Rust pointers can only be owned by one entity at a time and sending them off into a task (via spawn) means that you've permanently transferred ownership of that reference.</p>
<p>Here is the running speed of the Rust version on my system:</p>
<div class="precode"><pre><code>$ time bin/chinese-whispers
100001
real 0m4.234s
user 0m16.942s
sys 0m3.331s
</code></pre></div>
<p>So Rust can do it just fine, but it is not as efficient as Go. The Go version is about 13 times faster, based on these timed runs on my system.</p>
<br><hr><br>
<b>[Update]:</b> This blog post was discussed on Hacker News and Reddit soon after I published it. I've written a follow-up post addressing some of the complaints and summarizing some of the really interesting points in those community discussions: <a href="http://thornydev.blogspot.com/2014/01/telephonic-whispers-in-rust-revisited.html">http://thornydev.blogspot.com/2014/01/telephonic-whispers-in-rust-revisited.html</a>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com5tag:blogger.com,1999:blog-2977002084155733470.post-91162587680672539372014-01-01T15:36:00.000-05:002015-07-01T21:06:56.392-04:00Debugging Go (golang) programs with gdb<p><br /></p>
<h4><code>/* ---[ Update: July 2015 ]--- */</code></h4>
<p>
At this point, I think the Go community has given up trying to make gdb work with Go programs. It is pretty painful, so I don't recommend it. Recently, I've tried both <a href="https://github.com/derekparker/delve">delve</a> and <a href="https://github.com/mailgun/godebug">godebug</a>, two contributions from the Go community.. I had better luck with godebug. In fact, it performed perfectly for a recent issue I was having and was a joy to work with.
</p>
<hr>
<br>
<h4><code>/* ---[ Debugging Go ]--- */</code></h4>
<p>At the time of this writing, the only debugger I know of for the Go language is the FSF's gdb debugger. gdb can be used to debug programs written in Go and compiled with gccgo or 6g compilers.</p>
<p>At present, I'm using Go version 1.1.2 (on Xubuntu Linux). Do not upgrade to version 1.2 if you want to be able to use gdb. The 1.2 release introduced changes that breaks single stepping through code in gdb: <a href="http://code.google.com/p/go/issues/detail?id=6776"><a href='http://code.google.com/p/go/issues/detail?id=6776'>http://code.google.com/p/go/issues/detail?id=6776</a></a>.</p>
<p>As a side note, I find this situation pretty disappointing. It says that the Go developers are not including gdb compatibility tests in their testing of Go. That really isn't acceptable in my opinion if gdb is the only debugger tool available. Happily, the last entry in the comments from one of the Go maintainers/developers is "If possible, fix this for 1.2.1."</p>
<p><br /></p>
<h4><code>/* ---[ GDB ]--- */</code></h4>
<p>I won't give a gdb tutorial. There are lots of good ones on the web, such as these:</p>
<ul>
<li><a href="http://betterexplained.com/articles/debugging-with-gdb/"><a href='http://betterexplained.com/articles/debugging-with-gdb/'>http://betterexplained.com/articles/debugging-with-gdb/</a></a></li>
<li><a href="http://www.unknownroad.com/rtfm/gdbtut/gdbtoc.html"><a href='http://www.unknownroad.com/rtfm/gdbtut/gdbtoc.html'>http://www.unknownroad.com/rtfm/gdbtut/gdbtoc.html</a></a></li>
<li><a href="http://beej.us/guide/bggdb/"><a href='http://beej.us/guide/bggdb'>http://beej.us/guide/bggdb</a></a></li>
</ul>
<p><br /></p>
<h4><code>/* ---[ Using GDB with Go ]--- */</code></h4>
<p>I've written a unit test, using Go's testing library, for the code I'm debugging. Here's the code under test:</p>
<div class="precode"><pre><code>//
// Read in the username and password properties from the CONFIG_FILE file
// Returns error if CONFIG_FILE cannot be found or opened
//
func readDatabaseProperties() (uname, passw string, err error) {
propsStr, err := ioutil.ReadFile(CONFIG_FILE)
if err != nil {
return
}
for _, line := range strings.Split(string(propsStr), "\n") {
prop := strings.Split(line, "=")
if len(prop) == 2 {
switch prop[0] {
case "username":
uname = prop[1]
case "password":
passw = prop[1]
}
}
}
return
}
</code></pre></div>
<p>And here is the unit test for it:</p>
<div class="precode"><pre><code>func TestReadDatabaseProps(t *testing.T) {
uname, passw, err := readDatabaseProperties()
if err != nil {
t.Errorf(fmt.Sprintf("%v", err))
}
if len(uname) == 0 {
t.Errorf("uname is empty")
}
if len(passw) == 0 {
t.Errorf("passw is empty")
}
}
</code></pre></div>
<p>The CONFIG_FILE on my system has:</p>
<div class="precode"><pre><code>username = midpeter444
password = jiffylube
</code></pre></div>
<p>The unit test is currently failing:</p>
<div class="precode"><pre><code>$ go test -test.run="TestReadDatabaseProps"
--- FAIL: TestReadDatabaseProps (0.00 seconds)
indexer_test.go:150: uname is empty
indexer_test.go:153: passw is empty
FAIL
exit status 1
FAIL fslocate 0.023s
</code></pre></div>
<p>So let's check it out in gdb. First, compile the go code with the following flags:</p>
<div class="precode"><pre><code>$ go test -c -gcflags '-N -l'
</code></pre></div>
<p>The <code class="so">-c</code> flag causes the go compiler to generate an executable in the current directory called <code class="so">xxx.test</code>, where xxx is the name of the directory your code is in. In my case, it generated <code class="so">fslocate.test</code>.</p>
<p>Next ensure you have the <code class="so">GOROOT</code> environment variable <a href="http://golang.org/doc/install">properly set</a> and start gdb.</p>
<div class="precode"><pre><code>$ gdb fslocate.test -d $GOROOT
</code></pre></div>
<p>After doing this, if you see an error about <code class="so">/usr/local/go/src/pkg/runtime/runtime-gdb.py</code>, see my <a href="#sideNote1">side note #1</a> at the bottom of this posting.</p>
<p>The way we just fired up gdb will give you the command line prompt only. If you want to use it that way, I recommend using the <code class="so">frame</code> command in order to keep track of where you are in the code as you single-step through it.</p>
<p>However, I like using the <code class="so">-tui</code> option to gdb which will split the screen and give you a visual display of the code as you step through it.</p>
<div class="precode"><pre><code>$ gdb -tui fslocate.test -d $GOROOT
</code></pre></div>
<p>You get a screen like this. Don't worry about the assembly code - that will switch to your Go code once you get underway.</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyvuN_NkWs7Lch6m-tp3urG5soLSIAYQf89nKZ3nWM2R0BPCJcYutNNz4Y3JHeAYtxosloQQmeRdGpt-qq4M4vXIw2YOJz2hXZchAyNFBw7HSU76Nnf1vels3QuBVqTceict9V1bdc-l8/s1600/gdbtui.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjyvuN_NkWs7Lch6m-tp3urG5soLSIAYQf89nKZ3nWM2R0BPCJcYutNNz4Y3JHeAYtxosloQQmeRdGpt-qq4M4vXIw2YOJz2hXZchAyNFBw7HSU76Nnf1vels3QuBVqTceict9V1bdc-l8/s1600/gdbtui.png" /></a></div>
<p>To proceed, I'm going to set a breakpoint at the start of the test. To do this you'll need to specify the path to the function you want to break on. The code is actually in package "main", but it is in the "fslocate" directory, so I set the breakpoint like this:</p>
<div class="precode"><pre><code>(gdb) b "fslocate.TestReadDatabaseProps"
Breakpoint 1 at 0x43c730: file /home/midpeter444/lang/go/projects/src/
fslocate/indexer_test.go, line 144.
</code></pre></div>
<p>If you get a message like:</p>
<div class="precode"><pre><code>Function "fslocate.TestReadDatabaseProps" not defined.
Make breakpoint pending on future shared library load? (y or n)
</code></pre></div>
<p>You didn't get the path right. See <a href="#sideNote2">side note #2</a> for some help.</p>
<p>Now that we have the breakpoint set, run the program to the breakpoint by typing <code class="so">run</code> or <code class="so">r</code>:</p>
<div class="precode"><pre><code>(gdb) r
</code></pre></div>
<p>Now you'll see that the TUI window jumps to the current line of code and highlights it:</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiPnanwNxPGpDj3Irqi5CQXlxPWS1tLcBpMaHOS3tJNeX2ZNCmi_1AH1hr3LzT129XY8GeksrveVWhBksiwlTFxfX-FNHZenwvHXJvlHpjePw5-T_WHn7PBnOa8V0P2PQ0OBoQi1U5wZsM/s1600/gdbtui2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiPnanwNxPGpDj3Irqi5CQXlxPWS1tLcBpMaHOS3tJNeX2ZNCmi_1AH1hr3LzT129XY8GeksrveVWhBksiwlTFxfX-FNHZenwvHXJvlHpjePw5-T_WHn7PBnOa8V0P2PQ0OBoQi1U5wZsM/s1600/gdbtui2.png" /></a></div>
<p>Next advance line by line with <code class="so">n</code> (or <code class="so">next</code>) to step over to the next line where the function under test is called. Once there I step into it (<code class="so">s</code> or <code class="so">step</code>) and step over the next few lines until I'm here:</p>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQE_hS-6zW8oz97UbbwYsQUdv4G6KTRNlAtbxgJxVYpvu-MRzk70Tm8aFIP6WqOSif_sq_7bIWsqGu_nh59agE7jmn9m0ED8WPkFCy7EYIR75zcz6HHWrzTur3RGU9h9u8iNTVcf7nRec/s1600/gdbtui3.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgQE_hS-6zW8oz97UbbwYsQUdv4G6KTRNlAtbxgJxVYpvu-MRzk70Tm8aFIP6WqOSif_sq_7bIWsqGu_nh59agE7jmn9m0ED8WPkFCy7EYIR75zcz6HHWrzTur3RGU9h9u8iNTVcf7nRec/s1600/gdbtui3.png" /></a></div>
<p>Now let's inspect some of our variables with <code class="so">print</code> or <code class="so">p</code>:</p>
<div class="precode"><pre><code>(gdb) p propsStr
$2 = {array = 0xc2000b3240 "username = midpeter444\npassword = jiffylube\n",
len = 44, cap = 556}
(gdb) p err
$3 = {tab = 0x0, data = 0x0}
(gdb) p line
$4 = 0xc20009b7b0 "username = midpeter444"
</code></pre></div>
<p>The function <code class="so">ioutil.ReadFile</code> returns a byte slice and error. Inspecting them shows the string value of the byte slice, its length and capactiy and that the error is nil (as indicated by its data value being <code class="so">0x0</code>).</p>
<p>So the file read worked. Then we read in the first line as a string and it looks good. Then I called:</p>
<div class="precode"><pre><code>prop := strings.Split(line, "=")
</code></pre></div>
<p>to split the line into a string slice. Inspecting this slice shows us the contents of the slice "struct", but not the contents of the underlying slice array:</p>
<div class="precode"><pre><code>(gdb) p prop
$5 = {array = 0xc2000b1260, len = 2, cap = 2}
</code></pre></div>
<p>To peek into the array in gdb, we can use standard array indexing:</p>
<div class="precode"><pre><code>(gdb) p prop.array[0]
$20 = 0xc20009b7b0 "username "
(gdb) p prop.array[1]
$21 = 0xc20009b7ba " midpeter444"
</code></pre></div>
<p>or we can use the dereferencing operator <code class="so">*</code> and <code class="so">@N</code> to look at N contiguous portions of the array. The inspection so far told us that there are two entries in the array, so this is how to see all of the array entries in one command:</p>
<div class="precode"><pre><code>(gdb) p *prop.array@2
$22 = {0xc20009b7b0 "username ", 0xc20009b7ba " midpeter444"}
</code></pre></div>
<p>And with that I can see the defect in my code: I need to trim the string before comparing to the cases in my switch statement.</p>
<p><br /></p>
<h4><code>/* ---[ Looking into Go structs ]--- */</code></h4>
<p>You can also use dot notation to look into Go structs, using dereferencing where you have pointers rather than values.</p>
<p>For example here's a snippet of code from my fslocate program:</p>
<div class="precode"><pre><code>fse := fsentry.E{"/var/log/hive/foo", "f", false}
// query that new entry
dbChan <- dbTask{QUERY, fse, replyChan}
reply = <-replyChan
</code></pre></div>
<p><code class="so">fse</code> is a struct of type <code class="so">fsentry.E</code>:</p>
<div class="precode"><pre><code>type E struct {
Path string // full path for file or dir
Typ string // DIR_TYPE or FILE_TYPE
IsTopLevel bool // true = specified in the user's config/index file
}
</code></pre></div>
<p><code class="so">reply</code> is a struct of type <code class="so">dbReply</code></p>
<div class="precode"><pre><code>type dbReply struct {
fsentries []fsentry.E
err error
}
</code></pre></div>
<p><code class="so">dbChan</code> is a go channel (that takes dbTasks, another struct).</p>
<p>For that snippet of code I can inspect the contents in gdb:</p>
<div class="precode"><pre><code>(gdb) p fse
$1 = {Path = 0x637690 "/var/log/hive/foo", Typ = 0x61fd20 "f",
IsTopLevel = false}
(gdb) p *dbChan
$3 = {qcount = 1, dataqsiz = 10, elemsize = 56, closed = 0 '\000',
elemalign = 8 '\b', elemalg = 0x5646e0, sendx = 1, recvx = 0,
recvq = {first = 0x0, last = 0x0}, sendq = {first = 0x0,
last = 0x0}, runtime.lock = {key = 0}}
</code></pre></div>
<p>I had to use <code class="so">*</code> on dbChan since channels in go are pointers (references).</p>
<p>The <code class="so">reply</code> struct is a little more tricky:</p>
<div class="precode"><pre><code>(gdb) p reply
$9 = {fsentries = {array = 0xc20007e640, len = 1, cap = 4},
err = {tab = 0x0, data = 0x0}}
</code></pre></div>
<p>Here we see that it has two entries: <code class="so">fsentries</code> and <code class="so">err</code>. The error is null. <code class="so">fsentries</code> is an array of length one, which using the techniques we walked through earlier can be inspected:</p>
<div class="precode"><pre><code>(gdb) p reply.fsentries.array[0]
$11 = {Path = 0xc2000cbfe0 "/var/log/hive/foo", Typ = 0xc2000005d8 "f",
IsTopLevel = false}
</code></pre></div>
<p><br /></p>
<h4><code>/* ---[ Inspecting "slices" of Go arrays ]--- */</code></h4>
<p>Suppose you have a large Go slice and you want to see elements 20 through 24 only. How would you do that? You can use the indexing operator and the <code class="so">@N</code> operator together. Here's a slice of length three, where I look at the last two elements in the last command:</p>
<div class="precode"><pre><code>(gdb) p configDirs
$6 = {array = 0xc2000f8210, len = 3, cap = 3}
(gdb) p *configDirs.array@3
$7 = {0x618dc0 "/d/e", 0x627170 "/new/not/in/db", 0x626fd0 "/a/b/c/foo/bar"}
(gdb) p configDirs.array[1]@2
$8 = {0x627170 "/new/not/in/db", 0x626fd0 "/a/b/c/foo/bar"}
</code></pre></div>
<p>Hopefully, reading through a gdb tutorial and this post are enough to get you through your Go debugging sessions.</p>
<p><br /></p>
<h3>Side note 0: Key bindings with -tui</h3>
<p>One tricky/annoying aspect of running with the TUI is that the arrow keys navigate around the TUI screen rather than on your command line. So to go back and forward in history (usually the up and down arrows) use the bash bindings <code class="so">Ctrl-p</code> and <code class="so">Ctrl-n</code> respectively. To go left and and right on the command line use the bash/emacs bindings <code class="so">Ctrl-f</code> and <code class="so">Ctrl-b</code> respectively.</p>
<p><a name="sideNote1"></a><br /><br /></p>
<h3>Side note 1: python error when starting gdb</h3>
<p>On Ubuntu, I get an error after gdb starts up stating:</p>
<div class="precode"><pre><code>File "/usr/local/go/src/pkg/runtime/runtime-gdb.py", line 358
print s, ptr['goid'], "%8s" % sts[long((ptr['status']))], blk.function
</code></pre></div>
<p>I've been able to ignore this and still use gdb with Go code just fine.</p>
<p>According to <a href="https://groups.google.com/forum/#!topic/golang-nuts/VcmSvq2mSm0">this thread</a>, this is a python version issue used to build gdb and isn't an issue with the Go distribution. It may be specific to Ubuntu-flavored Linux distros. <a href="https://groups.google.com/forum/#!msg/golang-nuts/VcmSvq2mSm0/LfTp3CUhel8J">This posting</a> in that thread says you can fix it with: </p>
<div class="precode"><pre><code>sudo 2to3 -w /usr/local/go/src/pkg/runtime/runtime-gdb.py
</code></pre></div>
<p>But when I did that I now get errors when I try to look inside a string, struct or array:</p>
<div class="precode"><pre><code>(gdb) p propsStr
$1 = []uint8Python Exception <class 'TypeError'> 'gdb.Value' object cannot
be interpreted as an integer:
</code></pre></div>
<p>So I recommend that you back up the <code class="so">/usr/local/go/src/pkg/runtime/runtime-gdb.py</code> file before trying it in case you get the same error I did.</p>
<p><a name="sideNote2"></a><br /><br /></p>
<h3>Side note 2: Function "fslocate.TestReadDatabaseProps" not defined.</h3>
<p>If you get this type of error message when you set a breakpoint on a function:</p>
<div class="precode"><pre><code>Function "fslocate.TestReadDatabaseProps" not defined.
Make breakpoint pending on future shared library load? (y or n)
</code></pre></div>
<p>Then you either got the path wrong or the notation to the path wrong, so type "n" and try again. First check your spelling.</p>
<p>If that doesn't fix it, you might have a nested path. For example in the fslocate project, I have a stringset subdirectory:</p>
<div class="precode"><pre><code>midpeter444 ~/lang/go/projects/src/fslocate
$ tree stringset/
stringset/
├── stringset.go
└── stringset_test.go
</code></pre></div>
<p>In my case the <code class="so">fslocate</code> directory is in my <code class="so">$GOPATH/src</code> directory and the test file is in the <code class="so">fslocate/stringset</code> directory. If I were to go into that directory and compile the test for gdb,<br />the breakpoint path would be:</p>
<div class="precode"><pre><code>(gdb) b "fslocate/stringset.TestReadDatabaseProps"
</code></pre></div>
<p>Notice that you uses slashes for package separators and dots to indicate a function in a package.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com15tag:blogger.com,1999:blog-2977002084155733470.post-88318634203670019462013-10-11T20:22:00.000-04:002013-10-11T20:30:23.780-04:00Launching a Cascading job from Apache Oozie<p>The <a href="http://www.cascading.org/">Cascading framework</a> has its own workflow management system embedded in it, so when I tried to find information online about how to launch a Cascading job from within the <a href="https://oozie.apache.org/">Apache Oozie</a> workflow scheduler tool, I found a <a href="http://daytonward.livejournal.com/531602.html">dearth of information</a>.</p>
<p>In fact, when I asked on the oozie-users mailing list how to do it, the only response I got back was to write an Oozie extension to run Cascading jobs. That may be the right solution long term (don't know enough yet), but I did find a way to get it working with what Oozie provides today.</p>
<p><br /></p>
<h4><code>/*---[ Failed attempts ]---*/</code></h4>
<p>I tried unsuccessfully to use the map-reduce action and the shell action. The former won't work because it wants you to specify the Mapper and Reducer classes explicitly. That doesn't make sense in a Cascading job - you launch your main Cascading class and it auto-generates a bunch of mappers and reducers. Secondly, while you can use the <code class="so">oozie.launcher.action.main.class</code> property and specify your main Cascading class, there seems to be no way to pass arguments to it.</p>
<p>I'm not sure why I couldn't get the shell action to work. I made the exec property <code class="so">/usr/bin/hadoop</code> in order to run it as <code class="so">hadoop jar myjar.jar com.mycompany.MyClass arg1 arg2 argN</code>, but several attempts to make that work failed. There probably is a way to make it work, however.</p>
<p><br /></p>
<h4><code>/*---[ Solution: use the java action ]---*/</code></h4>
<p>In order to launch Cascading jobs, we build an uber-jar (which maven annoyingly calls a <a href="https://maven.apache.org/plugins/maven-shade-plugin/">shaded jar</a>) that has our specific Cascading code and supporting objects, as well as the Cascading library all bundled in it. But that's not enough as all that depends on the myriad Hadoop jars. We then use the <code class="so">hadoop jar</code> invocation as I indicated above because it puts all the Hadoop jars in the classpath.</p>
<p>I didn't think using the Oozie java action would work unless I built a <em>massive</em> uber jar with all the Hadoop dependencies which then have to get farmed around the Hadoop cluster each time you run it -- a great waste.</p>
<p>But I was happily surprised to notice that Oozie sets up the classpath for java (and map-reduce) tasks with all the Hadoop jars present.</p>
<p>So, here's the <code class="so">workflow.xml</code> file that works:</p>
<div class="xmlblock">
<pre>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">workflow-app</span> <span class="nxml-namespace-attribute-xmlns">xmlns</span>=<span class="nxml-namespace-attribute-value-delimiter">'</span><span class="nxml-namespace-attribute-value">uri:oozie:workflow:0.2</span><span class="nxml-namespace-attribute-value-delimiter">'</span> <span class="nxml-attribute-local-name">name</span>=<span class="nxml-attribute-value-delimiter">'</span><span class="nxml-attribute-value">cascading-wf</span><span class="nxml-attribute-value-delimiter">'</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">start</span> <span class="nxml-attribute-local-name">to</span>=<span class="nxml-attribute-value-delimiter">'</span><span class="nxml-attribute-value">stage1</span><span class="nxml-attribute-value-delimiter">'</span> <span class="nxml-tag-slash">/</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">action</span> <span class="nxml-attribute-local-name">name</span>=<span class="nxml-attribute-value-delimiter">'</span><span class="nxml-attribute-value">stage1</span><span class="nxml-attribute-value-delimiter">'</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">java</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">job-tracker</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">${jobTracker}</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">job-tracker</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">name-node</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">${nameNode}</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">name-node</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">configuration</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">property</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">name</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">mapred.job.queue.name</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">name</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">value</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">${queueName}</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">value</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">property</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">configuration</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">main-class</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">com.mycompany.MyCascade</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">main-class</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">java-opts</span><span class="nxml-tag-delimiter">></span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">java-opts</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">arg</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">/user/myuser/dir1/dir2</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">arg</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">arg</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">my-arg-2</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">arg</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">arg</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">my-arg-3</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">arg</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">file</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">lib/${EXEC}#${EXEC}</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">file</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">capture-output</span> <span class="nxml-tag-slash">/</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">java</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">ok</span> <span class="nxml-attribute-local-name">to</span>=<span class="nxml-attribute-value-delimiter">"</span><span class="nxml-attribute-value">end</span><span class="nxml-attribute-value-delimiter">"</span> <span class="nxml-tag-slash">/</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">error</span> <span class="nxml-attribute-local-name">to</span>=<span class="nxml-attribute-value-delimiter">"</span><span class="nxml-attribute-value">fail</span><span class="nxml-attribute-value-delimiter">"</span> <span class="nxml-tag-slash">/</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">action</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">kill</span> <span class="nxml-attribute-local-name">name</span>=<span class="nxml-attribute-value-delimiter">"</span><span class="nxml-attribute-value">fail</span><span class="nxml-attribute-value-delimiter">"</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">message</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">FAIL: Oh, the huge manatee!</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">message</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">kill</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">end</span> <span class="nxml-attribute-local-name">name</span>=<span class="nxml-attribute-value-delimiter">"</span><span class="nxml-attribute-value">end</span><span class="nxml-attribute-value-delimiter">"</span><span class="nxml-tag-slash">/</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">workflow-app</span><span class="nxml-tag-delimiter">></span>
</pre>
</div>
<p>The parameterized variables, such as <code class="so">${EXEC}</code>, are defined in a job.properties in the same directory as the <code class="so">workflow.xml</code> file. The shaded jar is in a lib subdirectory as indicated.</p>
<div class="xmlblock">
<pre>
<span class="variable-name"> </span>
<span class="variable-name">nameNode</span>=hdfs://10.230.138.159:8020
<span class="variable-name">jobTracker</span>=http://10.230.138.159:50300
<span class="variable-name"> </span>
<span class="variable-name">queueName</span>=default
<span class="variable-name"> </span>
<span class="variable-name">oozie.wf.application.path</span>=${nameNode}/user/${user.name}/examples/apps/cascading
<span class="variable-name">EXEC</span>=mybig-shaded-0.0.1-SNAPSHOT.jar
</pre>
</div>
<p>Let me know if you find another way to launch a Cascading job from Oozie or find any problems with this solution.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com4tag:blogger.com,1999:blog-2977002084155733470.post-51587420531274476282013-10-08T22:41:00.001-04:002013-10-11T19:57:24.176-04:00Beautiful Code Ported to Go<p>This week I've been learning Go - the programming language, not the game. I had studied its concurrency primitives for <a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure.html">my Clojure library</a> that would bring the CSP model to Clojure (this was before Rich Hickey and crew created <a href="https://github.com/clojure/core.async">core.async</a>), but until a few days ago I hadn't formally studied the whole of Go with the intention of being proficient in it.</p>
<p>Go has pointers, but it does not have pointer arithmetic. Instead, it has slices - variable sized arrays on which you can use Python-like "slice" notation. I wanted a chance to try that out and found it recently when reading Chapter 1 of <a href="http://www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047">Beautiful Code</a>, which is about a limited regular expression that Rob Pike (co-creator of Go) wrote for the <a href="http://www.amazon.com/Practice-Programming-Addison-Wesley-Professional-Computing/dp/020161586X">Practice of Programming</a> book he co-wrote with Brian Kernighan (who is also the author of Ch. 1 of <em>Beautiful Code</em>).</p>
<p>Pike's code is a limited (pedagogical) regex library that allows the following notation:</p>
<pre>
|------------+------------------------------------------------------------|
| Character | Meaning |
|------------+------------------------------------------------------------|
| c | Matches any literal character c |
| . (period) | Matches any single character |
| ^ | Matches the beginning of the input string. |
| $ | Matches the end of the input string |
| * | Matches zero or more occurrences of the previous character |
|------------+------------------------------------------------------------|
</pre>
<p><br /></p>
<h4><code>/* ---[ The C version ]--- */</code></h4>
<p>Here's Pike's code in C:</p>
<div class="codeblock">
<pre>
<span class="preprocessor"> #include</span> <span class="string"><stdio.h></span>
<span class="type">int</span> <span class="function-name">matchstar</span>(<span class="type">int</span> <span class="string">c</span>, <span class="type">char</span> *<span class="variable-name">regexp</span>, <span class="type">char</span> *<span class="variable-name">text</span>);
<span class="comment-delimiter">/* </span><span class="comment">matchhere: search for regexp at beginning of text </span><span class="comment-delimiter">*/</span>
<span class="type">int</span> <span class="function-name">matchhere</span>(<span class="type">char</span> *<span class="variable-name">regexp</span>, <span class="type">char</span> *<span class="variable-name">text</span>) {
<span class="keyword">if</span> (regexp[0] == <span class="string">'\0'</span>)
<span class="keyword">return</span> 1;
<span class="keyword">if</span> (regexp[1] == <span class="string">'*'</span>)
<span class="keyword">return</span> matchstar(regexp[0], regexp+2, text);
<span class="keyword">if</span> (regexp[0] == <span class="string">'$'</span> && regexp[1] == <span class="string">'\0'</span>)
<span class="keyword">return</span> *text == <span class="string">'\0'</span>;
<span class="keyword">if</span> (*text!=<span class="string">'\0'</span> && (regexp[0]==<span class="string">'.'</span> || regexp[0]==*text))
<span class="keyword">return</span> matchhere(regexp+1, text+1);
<span class="keyword">return</span> 0;
}
<span class="comment-delimiter">/* </span><span class="comment">matchstar: search for c*regexp at beginning of text </span><span class="comment-delimiter">*/</span>
<span class="type">int</span> <span class="function-name">matchstar</span>(<span class="type">int</span> <span class="variable-name">c</span>, <span class="type">char</span> *<span class="variable-name">regexp</span>, <span class="type">char</span> *<span class="variable-name">text</span>) {
<span class="keyword">do</span> {
<span class="comment-delimiter">/* </span><span class="comment">a * matches zero or more instances </span><span class="comment-delimiter">*/</span>
<span class="keyword">if</span> (matchhere(regexp, text))
<span class="keyword">return</span> 1;
} <span class="keyword">while</span> (*text != <span class="string">'\0'</span> && (*text++ == c || c == <span class="string">'.'</span>));
<span class="keyword">return</span> 0;
}
<span class="comment-delimiter">/* </span><span class="comment">match: search for regexp anywhere in text </span><span class="comment-delimiter">*/</span>
<span class="type">int</span> <span class="function-name">match</span>(<span class="type">char</span> *<span class="variable-name">regexp</span>, <span class="type">char</span> *<span class="variable-name">text</span>) {
<span class="keyword">if</span> (regexp[0] == <span class="string">'^'</span>)
<span class="keyword">return</span> matchhere(regexp+1, text);
<span class="keyword">do</span> {
<span class="comment-delimiter">/* </span><span class="comment">must look even if string is empty </span><span class="comment-delimiter">*/</span>
<span class="keyword">if</span> (matchhere(regexp, text))
<span class="keyword">return</span> 1;
} <span class="keyword">while</span> (*text++ != <span class="string">'\0'</span>);
<span class="keyword">return</span> 0;
}
</pre>
</div>
<p>I'll let you read Ch. 1 of <em>Beautiful Code</em> for an analysis, but two things are noteworthy for my purposes:</p>
<ol>
<li>Pike uses pointer arithmetic throughout the code</li>
<li>He uses the unusual do-while loop twice in only 30 or so lines of code</li>
</ol>
<p>So I thought I'd port it to Pike's new language Go.</p>
<p><br /></p>
<h4><code>/* ---[ My Go version ]--- */</code></h4>
<div class="codeblock">
<pre>
<span class="keyword">package</span> pikeregex
<span class="comment-delimiter">// </span><span class="comment">search for c*regex at beginning of text
</span> <span class="keyword">func</span> <span class="function-name">matchstar</span>(c rune, regex []<span class="type">rune</span>, text []<span class="type">rune</span>) bool {
<span class="keyword">for</span> {
<span class="keyword">if</span> <span class="function-name">matchhere</span>(regex, text) {
<span class="keyword">return</span> <span class="constant">true</span>
}
<span class="keyword">if</span> ! (<span class="builtin">len</span>(text) > 0 && (text[0] == c || c == <span class="string">'.'</span>)) {
<span class="keyword">return</span> <span class="constant">false</span>
}
text = text[1:]
}
}
<span class="comment-delimiter">// </span><span class="comment">search for regex at beginning of text
</span> <span class="keyword">func</span> <span class="function-name">matchhere</span>(regex []<span class="type">rune</span>, text []<span class="type">rune</span>) bool {
<span class="keyword">if</span> <span class="builtin">len</span>(regex) == 0 {
<span class="keyword">return</span> <span class="constant">true</span>
}
<span class="keyword">if</span> <span class="builtin">len</span>(regex) > 1 && regex[1] == <span class="string">'*'</span> {
<span class="keyword">return</span> <span class="function-name">matchstar</span>(regex[0], regex[2:], text)
}
<span class="keyword">if</span> regex[0] == <span class="string">'$'</span> && <span class="builtin">len</span>(regex) == 1 {
<span class="keyword">return</span> <span class="builtin">len</span>(text) == 0
}
<span class="keyword">if</span> <span class="builtin">len</span>(text) > 0 && (regex[0] == <span class="string">'.'</span> || regex[0] == text[0]) {
<span class="keyword">return</span> <span class="function-name">matchhere</span>(regex[1:], text[1:])
}
<span class="keyword">return</span> <span class="constant">false</span>
}
<span class="comment-delimiter">// </span><span class="comment">search for regex anywhere in the text
</span> <span class="keyword">func</span> <span class="function-name">Match</span>(regex string, text string) bool {
runerx := <span class="function-name">compile</span>(regex)
runetxt := []<span class="function-name">rune</span>(text)
<span class="keyword">if</span> <span class="builtin">len</span>(runerx) > 0 && runerx[0] == <span class="string">'^'</span> {
<span class="keyword">return</span> <span class="function-name">matchhere</span>(runerx[1:], runetxt)
}
<span class="keyword">for</span> {
<span class="keyword">if</span> <span class="function-name">matchhere</span>(runerx, runetxt) {
<span class="keyword">return</span> <span class="constant">true</span>
}
<span class="keyword">if</span> <span class="builtin">len</span>(runetxt) == 0 {
<span class="keyword">return</span> <span class="constant">false</span>
}
runetxt = runetxt[1:]
}
}
<span class="comment-delimiter">// </span><span class="comment">one enhancement: allow + (1 or more) notation
</span> <span class="keyword">func</span> <span class="function-name">compile</span>(regex string) (regslc []<span class="type">rune</span>) {
regslc = <span class="builtin">make</span>([]rune, 0, <span class="builtin">len</span>(regex) + 10)
<span class="keyword">for</span> _, r := <span class="keyword">range</span> regex {
<span class="keyword">if</span> r == <span class="string">'+'</span> {
regslc = <span class="builtin">append</span>(regslc, regslc[<span class="builtin">len</span>(regslc) - 1], <span class="string">'*'</span>)
} <span class="keyword">else</span> {
regslc = <span class="builtin">append</span>(regslc, r)
}
}
<span class="keyword">return</span> regslc
}
</pre>
</div>
<p>This is as straight a port as I could make it. And I think it translates well to Go. I've capitalized the <code class="so">Match</code> method, as that is the public one to be exported to other libraries.</p>
<p>Instead of pointer arithmetic I used slice notation, as in this recursive call to <code class="so">matchhere</code>:</p>
<div class="codeblock">
<pre>
<span class="comment-delimiter"> // </span><span class="comment">C version
</span> <span class="keyword">return</span> <span class="function-name">matchhere</span>(regexp+1, text+1);
<span class="comment-delimiter"> // </span><span class="comment">Go version
</span> <span class="keyword">return</span> <span class="function-name">matchhere</span>(regex[1:], text[1:])
</pre>
</div>
<p>Also in the C code you check whether you are at the end of the text string by looking for the NUL char: <code class="so">*text == '\0'</code>. In Go, you can use the builtin <code class="so">len</code> function: <code class="so">len(text) == 0</code>. That statement is true if you keep recursively slicing <code class="so">text[1:]</code> until you get to an empty string, or rather in my code, an empty slice of runes.</p>
<p><br /></p>
<h4><code>/* ---[ Runeology ]--- */</code></h4>
<p>Runes are the Go 'char' type. A rune is an integer value identifying a Unicode code point. When you iterate over strings, you get runes, which are of variable size (number of bytes). </p>
<p>You have to be careful with strings in Go: <code class="so">text[2]</code> returns the third byte, <strong>not</strong> the third rune in the string. If you want the third rune, you might try to use the <code class="so">utf8.DecodeRuneInString(text[2:])</code> function. But this would only work with ASCII, as you are slicing at the third byte and asking the utf8 library to parse the first rune from that point. But if the first rune in the string is two bytes long, you'll be getting the second rune in the string, not the third. If it's three bytes long, you're really in trouble.</p>
<p>The safest way is to do what I did in the code: convert the string to a slice of runes (<code class="so">[]rune</code>) immediately and then work it that. Now when you index <code class="so">runeslice[2]</code> you know you are getting the third rune.</p>
<p><br /></p>
<h4><code>/* ---[ No do-while ]--- */</code></h4>
<p>Go doesn't have a do-while loop. It doesn't even have a <code class="so">while</code> statement: just <code class="so">for</code>. But, as <a href="https://twitter.com/rob_pike/status/387791668021166080">Rob Pike reminded me</a> in a critique of the first version of this blog entry, a do-while can be adequately mimicked with an infinite for loop:</p>
<div class="codeblock">
<pre>
<span class="keyword">func</span> <span class="function-name">matchstar</span>(c rune, regex []<span class="type">rune</span>, text []<span class="type">rune</span>) bool {
<span class="keyword">for</span> {
<span class="keyword">if</span> <span class="function-name">matchhere</span>(regex, text) {
<span class="keyword">return</span> <span class="constant">true</span>
}
<span class="keyword">if</span> ! (<span class="builtin">len</span>(text) > 0 && (text[0] == c || c == <span class="string">'.'</span>)) {
<span class="keyword">return</span> <span class="constant">false</span>
}
text = text[1:]
}
}
</pre>
</div>
<p>The stated intent of Go was to be as minimal as possible. Pike, in <a href="http://thechangelog.com/100/">a recent podcast interview</a>, said that the core team that created Go (which includes <a href="https://en.wikipedia.org/wiki/Ken_Thompson">Ken Thompson</a>) all had to agree that a feature was essential for it be included. Many candidate features were dropped, including the do-while loop. Of note, <a href="http://golang.org/ref/spec#Goto_statements">goto</a> was not, which I find quite interesting. <code class="so">goto</code> is only mentioned once (almost in passing) in the <a href="http://golang.org/doc/effective_go.html">Effective Go</a> guide, so I'm interested in what the essential use case for it was.</p>
<p><br /></p>
<h4><code>/* ---[ One addition ]--- */</code></h4>
<p>Finally, in the <em>Beautiful Code</em> chapter, Kernighan suggests a number of enhancements the reader can make. I've only done one - allowing the <code class="so">+</code> (1 or more) operator by mildly precompiling the regex, turning <code class="so">x+</code> into <code class="so">xx*</code>, allowing me to use Pike's original (ported) code untouched.</p>
<p>The above code is available on GitHub: <a href='https://github.com/midpeter444/pikeregex'>https://github.com/midpeter444/pikeregex</a></p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com1tag:blogger.com,1999:blog-2977002084155733470.post-49784806267557705602013-09-25T23:01:00.000-04:002013-09-25T23:09:17.834-04:00How to compile Groovy scripts and run them on systems with no Groovy installed<p><br /></p>
<h4><code>/*---[ Problem ]---*/</code></h4>
<p>This week I was faced with the need to write a Groovy script that would run on a Hadoop node at work, but we don't yet have groovy installed on the Hadoop nodes (and I don't have privileges to do that). Since Groovy is our defined scripting language, I had two options in the meantime:</p>
<ol>
<li>Download the groovy zip package, just unzip it in my user directory on the Hadoop node and run my thing.</li>
<li>Compile the groovy script to bytecode and build an uber-jar with groovy in it and then run it like a Java program (with <code class="so">java -cp myjar.jar blah blah blah</code>).</li>
</ol>
<p><br /></p>
<h4><code>/*---[ Solution ]---*/</code></h4>
<p>Since the second sounded like more of a challenge and would teach me a few things I hadn't done yet, I picked that. It worked out - here's my cheat sheet for future reference.</p>
<p><br /></p>
<h5><code>/*---[ Quoth the Maven ]---*/</code></h5>
<p>Create a new maven project:</p>
<div class="precode"><pre><code>mvn archetype:generate -DarchetypeArtifactId=maven-archetype-quickstart \
-DinteractiveMode=false -DgroupId=net.thornydev -DartifactId=script
</code></pre></div>
<p><br /></p>
<h5><code>/*---[ Two plugins ]---*/</code></h5>
<p>To compile groovy to bytecode use the <a href="http://groovy.codehaus.org/Groovy-Eclipse+compiler+plugin+for+Maven">groovy-eclipse-compiler plugin</a>. Yes, I know that sounds weird, but you don't need to fire up Eclipse. You don't even need to have Eclipse installed. </p>
<p>To build the uberjar having your compiled script and all of groovy, use the <a href="https://maven.apache.org/plugins/maven-shade-plugin/">maven-shade-plugin</a>. Like most things about maven, I find name "shade-plugin" irritating, but it gets the job done.</p>
<p>Finally include groovy-all.jar as a dependency.</p>
<p>Here's my pom:</p>
<pre class="brush: xml">
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
<modelVersion>4.0.0</modelVersion>
<groupId>net.thornydev</groupId>
<artifactId>script</artifactId>
<packaging>jar</packaging>
<version>1.0</version>
<name>script</name>
<url>http://maven.apache.org</url>
<build>
<plugins>
<plugin>
<artifactId>maven-compiler-plugin</artifactId>
<version>2.3.2</version>
<configuration>
<compilerId>groovy-eclipse-compiler</compilerId>
</configuration>
<dependencies>
<dependency>
<groupId>org.codehaus.groovy</groupId>
<artifactId>groovy-eclipse-compiler</artifactId>
<version>2.7.0-01</version>
</dependency>
</dependencies>
</plugin>
<plugin>
<groupId>org.apache.maven.plugins</groupId>
<artifactId>maven-shade-plugin</artifactId>
<version>2.1</version>
<executions>
<execution>
<phase>package</phase>
<goals>
<goal>shade</goal>
</goals>
</execution>
</executions>
</plugin>
</plugins>
</build>
<dependencies>
<dependency>
<groupId>org.codehaus.groovy</groupId>
<artifactId>groovy-all</artifactId>
<version>2.0.7</version>
</dependency>
</dependencies>
</project>
</pre>
<p><br /></p>
<h5><code>/*---[ Treat groovy like a first class citizen ]---*/</code></h5>
<p>Put your groovy file(s) in the <code class="so">src/main/java</code> directory, <strong>not</strong> <code class="so">src/main/groovy</code> like that other Groovy compiler tool wants. </p>
<p>The directory structure:</p>
<div class="precode"><pre><code>$ tree
.
├── pom.xml
└── src
├── main
│ └── java
│ └── net
│ └── thornydev
│ └── GroovyApp.groovy
</code></pre></div>
<p>The Groovy code:</p>
<pre class="brush: java">
package net.thornydev;
class Script {
def main(args) {
println "Hello ${args[0]}. I'm groovy."
}
}
new Script().main(args)
</pre>
<p><br /></p>
<h5><code>/*---[ Package, push, run ]---*/</code></h5>
<p>Next: <code class="so">mvn clean package</code></p>
<p>Then scp the <code class="so">script-1.0.jar</code> in the target dir to your desired system and run it:</p>
<div class="precode"><pre><code>$ java -cp script-1.0.jar net.thornydev.GroovyApp thornydev
Hello thornydev. I'm groovy.
</code></pre></div>
<p>QED.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com3tag:blogger.com,1999:blog-2977002084155733470.post-75416638088539494522013-08-17T11:19:00.000-04:002013-08-17T14:38:17.508-04:00VMWare Player Crashes in Ubuntu After Kernel Upgrade<p><br /></p>
<h4><code>/*---[ Annoyance ]---*/</code></h4>
<p>With Xubuntu 13.04, every time I get a kernel upgrade, which seems to happen at least once a month, my VMWare Player no longer works. I'm sure this is not specific to Xubuntu - probably any Ubuntu-13.04 based distro will have this problem.</p>
<p>The first time it happened, I spent a while trying to fix it and get it to recompile and then ended up deciding to uninstall and reinstall, but even that was a mess because the <code class="so">vmware-uninstaller</code> doesn't work and tells you to use the installer and then I downloaded a really old version of VMWare Player that for some reason VMWare still has up and and came up as a top choice in google. When I installed that, it complained about all sorts of kernel issues, including that it wouldn't install on a system with KVM enabled, so I disabled KVM and it still wouldn't work. Then I figured out I had a really old version (like version 2 instead of 5!).</p>
<p><br /></p>
<h4><code>/*---[ Solution ]---*/</code></h4>
<p>The solution is quite simple, so I'm documenting it here to save others headache.</p>
<p>If you have a kernel upgrade and VMWare player won't start, this is what I do:</p>
<ol>
<li>Uninstall: <code class="so">sudo vmware-installer -u vmware-player</code></li>
<li>Download the latest VMPlayer for Linux from here: <a href='https://www.vmware.com/products/player/'>https://www.vmware.com/products/player/</a></li>
<li>Reinstall: <code class="so">sudo ./VMware-Player-5.0.2-1031769.x86_64.bundle</code></li>
</ol>
<p>Only takes a few minutes and all is back to normal.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com1tag:blogger.com,1999:blog-2977002084155733470.post-52091246014091482552013-07-05T14:56:00.000-04:002013-09-16T17:05:00.668-04:00Querying JSON records via Hive<p><br /></p>
<h4><code>/* ---[ Opacity: A brief rant ]--- */</code></h4>
<p>Despite the popularity of Hadoop and its ecosystem, I've found that much of it is frustratingly underdocumented or at best opaquely documented. An example proof of this is the O'Reilly Programming Hive book, whose authors say they wrote it because so much of Hive is poorly documented and exists only in the heads of its developer community.</p>
<p>But even the Programming Hive book lacks good information on how to effectively use Hive with JSON records, so I'm cataloging my findings here.</p>
<p><br /></p>
<h4><code>/* ---[ JSON and Hive: What I've found ]--- */</code></h4>
<p>I've only been playing with Hive about two weeks now, but here's what I found with respect to using complex JSON documents with Hive.</p>
<p>Hive has two built-in functions, <code class="so">get_json_object</code> and <code class="so">json_tuple</code>, for dealing with JSON. There are also a couple of JSON SerDe's (Serializer/Deserializers) for Hive. I like this one the best: <a href='https://github.com/rcongiu/Hive-JSON-Serde'>https://github.com/rcongiu/Hive-JSON-Serde</a></p>
<p>I will document using these three options here.</p>
<p>Let's start with a simple JSON document and then move to a complex document with nested subdocuments and arrays of subdocuments.</p>
<p>Here's the first document:</p>
<pre class="brush: javascript">
{
"Foo": "ABC",
"Bar": "20090101100000",
"Quux": {
"QuuxId": 1234,
"QuuxName": "Sam"
}
}
</pre>
<p>We are going to store this as a Text document, so it is best to have the whole JSON entry on a single line in the text file you point the Hive table to.</p>
<p>Here it is on one line for easy copy and pasting:</p>
<pre class="brush: javascript">
{"Foo":"ABC","Bar":"20090101100000","Quux":{"QuuxId":1234,"QuuxName":"Sam"}}
</pre>
<p>Let's create a Hive table to reference this. I've put the above document in a file called simple.json:</p>
<pre class="brush: sql">
CREATE TABLE json_table ( json string );
LOAD DATA LOCAL INPATH '/tmp/simple.json' INTO TABLE json_table;
</pre>
<p>Since there are no delimiters, we leave off the ROW FORMAT section of the table DDL</p>
<p><br /></p>
<h4>Built in function #1: get_json_object</h4>
<p>The <code class="so">get_json_object</code> takes two arguments: tablename.fieldname and the JSON field to parse, where '$' represents the root of the document.</p>
<pre class="brush: sql">
select get_json_object(json_table.json, '$') from json_table;
</pre>
<p>Returns the full JSON document.</p>
<p>So do this to query all the fields:</p>
<pre class="brush: sql">
select get_json_object(json_table.json, '$.Foo') as foo,
get_json_object(json_table.json, '$.Bar') as bar,
get_json_object(json_table.json, '$.Quux.QuuxId') as qid,
get_json_object(json_table.json, '$.Quux.QuuxName') as qname
from json_table;
</pre>
<p>You should get the output:</p>
<div class="precode"><pre><code>foo bar qid qname
ABC 20090101100000 1234 Sam
</code></pre></div>
<p>(Note: to get the header fields, enter <code class="so">set hive.cli.print.header=true</code> at the hive prompt or in your <code class="so">$HOME/.hiverc</code> file.)</p>
<p>This works and has a nice JavaScript like "dotted" notation, but notice that you have to parse the same document once for every field you want to pull out of your JSON document, so it is rather inefficient.</p>
<p>The Hive wiki recommends using <code class="so">json_tuple</code> for this reason.</p>
<p><br /></p>
<h4>Built in function #2: json_tuple</h4>
<p>So let's see what <code class="so">json_tuple</code> looks like. It has the benefit of being able to pass in multiple fields, but it only works to a single level deep. You also need to use Hive's slightly odd <code class="so">LATERAL VIEW</code> notation:</p>
<pre class="brush: sql">
select v.foo, v.bar, v.quux, v.qid
from json_table jt
LATERAL VIEW json_tuple(jt.json, 'Foo', 'Bar', 'Quux', 'Quux.QuuxId') v
as foo, bar, quux, qid;
</pre>
<p>This returns:</p>
<div class="precode"><pre><code>foo bar quux qid
ABC 20090101100000 {"QuuxId":1234,"QuuxName":"Sam"} NULL
</code></pre></div>
<p>It doesn't know how to look inside the Quux subdocument. And this is where <code class="so">json_tuple</code> gets clunky fast - you have to create another lateral view for each subdocument you want to descend into:</p>
<pre class="brush: sql">
select v1.foo, v1.bar, v2.qid, v2.qname
from json_table jt
LATERAL VIEW json_tuple(jt.json, 'Foo', 'Bar', 'Quux') v1
as foo, bar, quux
LATERAL VIEW json_tuple(v1.quux, 'QuuxId', 'QuuxName') v2
as qid, qname;
</pre>
<p>This gives us the output we want:</p>
<div class="precode"><pre><code>foo bar qid qname
ABC 20090101100000 1234 Sam
</code></pre></div>
<p>With a complicated highly nested JSON doc, json_tuple is also quite inefficient and clunky as hell. So let's turn to a custom SerDe to solve this problem.</p>
<p><br /></p>
<h4>The best option: rcongiu's Hive-JSON SerDe</h4>
<p>A SerDe is a better choice than a json function (UDF) for at least two reasons:</p>
<ol>
<li>it only has to parse each JSON record once</li>
<li>you can define the JSON schema in the Hive table schema, making it much easier to issue queries against.</li>
</ol>
<p>I reviewed a couple of SerDe's and by far the best one I've found is <a href="https://github.com/rcongiu/Hive-JSON-Serde">rcongiu's Hive-JSON SerDe</a>.</p>
<p>To get that SerDe, clone the project from GitHub and run <code class="so">mvn package</code>. It creates a <code class="so">json-serde-1.1.6.jar</code> in the target directory. If you have a place you like to put your jars for runtime referencing move it there. </p>
<p>Then tell Hive about it with:</p>
<div class="precode"><pre><code>ADD JAR /path/to/json-serde-1.1.6.jar;
</code></pre></div>
<p>You can do this either at the hive prompt or put it in your <code class="so">$HOME/.hiverc</code> file.</p>
<p>Now let's define the Hive schema that this SerDe expects and load the simple.json doc:</p>
<pre class="brush: sql">
CREATE TABLE json_serde (
Foo string,
Bar string,
Quux struct<QuuxId:int, QuuxName:string>
)
ROW FORMAT SERDE 'org.openx.data.jsonserde.JsonSerDe';
LOAD DATA LOCAL INPATH '/tmp/simple.json' INTO TABLE json_serde;
</pre>
<p>With the openx JsonSerDe, you can define subdocuments as maps or structs. I prefer structs, as it allows you to use the convenient dotted-path notation (e.g., Quux.QuuxId) and you can match the case of the fields. With maps, all the keys you pass in have to be lowercase, even if you defined them as upper or mixed case in your JSON.</p>
<p>The query to match the above examples is beautifully simple:</p>
<pre class="brush: sql">
SELECT Foo, Bar, Quux.QuuxId, Quux.QuuxName
FROM json_serde;
</pre>
<p>Result:</p>
<div class="precode"><pre><code>foo bar quuxid quuxname
ABC 20090101100000 1234 Sam
</code></pre></div>
<p><br><br />And now let's do a more complex JSON document:</p>
<pre class="brush: javascript">
{
"DocId": "ABC",
"User": {
"Id": 1234,
"Username": "sam1234",
"Name": "Sam",
"ShippingAddress": {
"Address1": "123 Main St.",
"Address2": null,
"City": "Durham",
"State": "NC"
},
"Orders": [
{
"ItemId": 6789,
"OrderDate": "11/11/2012"
},
{
"ItemId": 4352,
"OrderDate": "12/12/2012"
}
]
}
}
</pre>
<p>Collapsed version:</p>
<pre class="brush: javascript">
{"DocId":"ABC","User":{"Id":1234,"Username":"sam1234","Name":"Sam","ShippingAddress":{"Address1":"123 Main St.","Address2":"","City":"Durham","State":"NC"},"Orders":[{"ItemId":6789,"OrderDate":"11/11/2012"},{"ItemId":4352,"OrderDate":"12/12/2012"}]}}
</pre>
<p>Hive Schema:</p>
<pre class="brush: sql">
CREATE TABLE complex_json (
DocId string,
User struct<Id:int,
Username:string,
Name: string,
ShippingAddress:struct<Address1:string,
Address2:string,
City:string,
State:string>,
Orders:array<struct<ItemId:int,
OrderDate:string>>>
)
ROW FORMAT SERDE 'org.openx.data.jsonserde.JsonSerDe';
</pre>
<p>Load the data:</p>
<pre class="brush: sql">
LOAD DATA LOCAL INPATH '/tmp/complex.json'
OVERWRITE INTO TABLE complex_json;
</pre>
<p>First let's query something from each document section. Since we know there are two orders in the orders array we can reference them both directly:</p>
<pre class="brush: sql">
SELECT DocId, User.Id, User.ShippingAddress.City as city,
User.Orders[0].ItemId as order0id,
User.Orders[1].ItemId as order1id
FROM complex_json;
</pre>
<p>Result:</p>
<div class="precode"><pre><code>docid id city order0id order1id
ABC 1234 Durham 6789 4352
</code></pre></div>
<p>But what if we don't know how many orders there are and we want a list of all a user's order Ids? This will work:</p>
<pre class="brush: sql">
SELECT DocId, User.Id, User.Orders.ItemId
FROM complex_json;
</pre>
<p>Result:</p>
<div class="precode"><pre><code>docid id itemid
ABC 1234 [6789,4352]
</code></pre></div>
<p>Oooh, it returns an array of ItemIds. Pretty cool. One of Hive's nice features.</p>
<p>Finally, does the openx JsonSerDe require me to define the whole schema? Or what if I have two JSON docs (say version 1 and version 2) where they differ in some fields? How constraining is this Hive schema definition?</p>
<p>Let's add two more JSON entries to our JSON document - the first has no orders; the second has a new "PostalCode" field in Shipping Address.</p>
<pre class="brush: javascript">
{
"DocId": "ABC",
"User": {
"Id": 1235,
"Username": "fred1235",
"Name": "Fred",
"ShippingAddress": {
"Address1": "456 Main St.",
"Address2": "",
"City": "Durham",
"State": "NC"
}
}
}
{
"DocId": "ABC",
"User": {
"Id": 1236,
"Username": "larry1234",
"Name": "Larry",
"ShippingAddress": {
"Address1": "789 Main St.",
"Address2": "",
"City": "Durham",
"State": "NC",
"PostalCode": "27713"
},
"Orders": [
{
"ItemId": 1111,
"OrderDate": "11/11/2012"
},
{
"ItemId": 2222,
"OrderDate": "12/12/2012"
}
]
}
}
</pre>
<p>Collapsed version:</p>
<pre class="brush: javascript">
{"DocId":"ABC","User":{"Id":1235,"Username":"fred1235","Name":"Fred","ShippingAddress":{"Address1":"456 Main St.","Address2":"","City":"Durham","State":"NC"}}}
{"DocId":"ABC","User":{"Id":1236,"Username":"larry1234","Name":"Larry","ShippingAddress":{"Address1":"789 Main St.","Address2":"","City":"Durham","State":"NC","PostalCode":"27713"},"Orders":[{"ItemId":1111,"OrderDate":"11/11/2012"},{"ItemId":2222,"OrderDate":"12/12/2012"}]}}
</pre>
<p>Add those records to complex.json and reload the data into the complex_json table.</p>
<p>Now try the query:</p>
<pre class="brush: sql">
SELECT DocId, User.Id, User.Orders.ItemId
FROM complex_json;
</pre>
<p>It works just fine and gives the result:</p>
<div class="precode"><pre><code>docid id itemid
ABC 1234 [6789,4352]
ABC 1235 null
ABC 1236 [1111,2222]
</code></pre></div>
<p>Any field not present will just return null, as Hive normally does even for non-JSON formats.</p>
<p>Note that we cannot query for User.ShippingAddress.PostalCode because we haven't put it on our Hive schema. You would have to revise the schema and then reissue the query.</p>
<p><br /></p>
<h4><code>/* ---[ A tool to automate creation of Hive JSON schemas ]--- */</code></h4>
<p>One feature missing from the openx JSON SerDe is a tool to generate a schema from a JSON document. Creating a schema for a large complex, highly nested JSON document is quite tedious.</p>
<p>I've created a tool to automate this: <a href="https://github.com/midpeter444/hive-json-schema"><a href='https://github.com/midpeter444/hive-json-schema'>https://github.com/midpeter444/hive-json-schema</a></a>.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com531tag:blogger.com,1999:blog-2977002084155733470.post-24185026271507620412013-03-03T22:36:00.001-05:002013-10-11T19:52:08.700-04:00Signing and Promoting your Clojure libraries on Clojars<p>Phil Hagelberg, the creator and primary maintainer of Leiningen, has been advocating that Clojurians sign their Clojure libraries for the releases repository in Clojars. By itself, this isn't sufficient to provide security to avoid malicious code from causing havoc with public code repositories, but it is a necessary first step. Phil has talked about his ideas on how to get to a more complete model of security in a couple of places:</p>
<ul>
<li>Exhibit A: <a href="https://groups.google.com/forum/?fromgroups=#!topic/clojars-maintainers/2yM7-9te3oo">Posting on Clojars-maintainers Google Group</a></li>
<li>Exhibit B: <a href="http://mostlylazy.com/2012/09/21/episode-8-phil-hagelberg-empowering-userspace-in-heroku-leiningen-and-emacs/">Mostly Lazy podcast Episode 8</a></li>
<li>Exhibit C: <a href="https://www.youtube.com/watch?v=sBSUIKMdQ4w">Clojure Conj 2012 presentation</a></li>
</ul>
<p><br /></p>
<h4><code>/* ---[ Signing your Clojure libraries ]--- */</code></h4>
<p>My first experience deploying a signed jar to Clojars was a little rocky, so I'm providing this how-to report to help others (including future me).</p>
<p>I have only done this on (Xubuntu) Linux, but I imagine it will work fairly similarly on Macs. Not sure about Windows, as I seem to have constant trouble getting Clojure and Windows to play nicely together. I have used GPG on Windows that comes with <a href="http://msysgit.github.com/">mysysgit</a>, so that will probably work with these instructions as well, but I haven't tried it.</p>
<p><br /></p>
<h5><code>/* ---[ STEP 1: Generate GPG Keys ]--- */</code></h5>
<p>Clojars security is based on PGP keys, so you need to a have a PGP public/private keyset. GnuPG (GPG) is the generally recommended tool for that.</p>
<p>If you already have GPG installed and can't remember if you've already created a keyset, try this first:</p>
<div class="precode"><pre><code>gpg --list-keys
</code></pre></div>
<p>If you see your name and email in the list, then you have. If not, generate them with:</p>
<div class="precode"><pre><code>gpg --gen-key
</code></pre></div>
<p>Accepting the defaults you are prompted with is fine. See <a href="http://www.madboa.com/geek/gpg-quickstart/">this article</a> for details on this step. When completed this will create your public key ring and secret/private key ring:</p>
<div class="precode"><pre><code>$ ls ~/.gnupg
pubring.gpg pubring.gpg~ random_seed secring.gpg trustdb.gpg
</code></pre></div>
<p><br /></p>
<h5><code>/* ---[ STEP 2: Publish your public GPG key to a keyserver ]--- */</code></h5>
<p>By publishing your public key, others can download it and verify that your signed library is in fact signed by you.</p>
<p>To publish your key you will need to get its ID.</p>
<div class="precode"><pre><code>$ gpg --list-keys
/home/midpeter444/.gnupg/pubring.gpg
------------------------------------
pub 2048R/5414B325 2012-11-12
uid Michael Peterson <<a href='mailto:myemail@fubar.com'>myemail@fubar.com</a>>
</code></pre></div>
<p>The 8 characters after the '/' on the "pub" row of your key is your key's ID. Now publish it:</p>
<div class="precode"><pre><code>$ gpg --send-key 5414B325
</code></pre></div>
<p>If you don't specify a key server it will choose the GnuPG keyserver. If you want to target a specify keyserver use the <code class="so">--keyserver</code> option <a href="http://www.madboa.com/geek/gpg-quickstart/">as shown here</a>.</p>
<p><br /></p>
<h5><code>/* ---[ STEP 3: Add your GPG key to your Clojars account ]--- */</code></h5>
<p>When you sign up for Clojars there is a section in your Profile to add two keys: 1) an SSH public key and a PGP public key. The SSH key is for secure transport of the library from your system to the Clojars repo via scp. It is not related to signing your jars.</p>
<p>Your library will be signed with your PGP private key that resides only on your system. That signature indicates that the owner of the private key (the one paired with the public key you just published) signed this code artifact. It allows someone else to know who signed it and whether the code artifact has been changed since it was signed and deployed.</p>
<p>By having your PGP public key on Clojars, you allow Clojars to verify that one of its members signed the artifact. This check happens when you promote your release to the release repo (more on that below).</p>
<p><em>Note:</em> Clojars is not a keyserver, so putting it there will not allow others to verify the signature. That is why in step 2 we published it to a public keyserver.</p>
<p>To add your public key to Clojars you create an "ASCII-armored" version of the binary public key, which you generate with:</p>
<div class="precode"><pre><code>gpg --armor --export <a href='mailto:your@email.here'>your@email.here</a> code
</code></pre></div>
<p>Once you have it, what exactly do you paste into the Clojars text box? The BEGIN and END delimiter lines and everything in between, like so:</p>
<pre>
-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: GnuPG v1.4.11 (GNU/Linux)
mQENBFChf/ABCAC/2nK75NwOsg7nkI5NNTCqBMk5DMX0JWu17EZoii/6vH88KlTm
0xeIHwv3leMZbtjqTNzFPfGh5xQo7zH+Y2CBPG8gq9QKv9aB587vuzwCtN/uaP6Z
mjQlafc5HK8gn5PMULWJC0V46g+y39g8bDSEZDInGFFWF7kCOXMcsJnNuoXWbajz
WwV8lcr56EKeenRS3lV4GWd/W+aSjCkaq1SM+9XP3qZYC9lOuaYfkzxfTsf5hpvG
wfTJVOaaPDtfhefgzrK6+znvMC1TsKMKU8bpX7u9WaHn9jD24UE6idzSn84uPuNK
5Jms4r7r6y+kfMSrWK0KUH+Gp0Bs+6kVu6S1ABEBAAG0J01pY2hhZWwgUGV0ZXJz
b24gPG1wZXRlcnNvbjJAZ21haWwuY29tPokBOAQTAQIAIgUCUKF/8AIbAwYLCQgH
AwIGFQgCCQoLBBYCAwECHgECF4AACgkQeBe9+DhXuBiGzAf/aC43wc/TrNSMeWkN
6X92YpPu8SYh1bcDOEm7FvBSWZg/NSf4VBNqP6TXjobIGfSX8hFGrgrkB/ZDMY6N
Ec9UxpnhVC2gOn9TZzOCNfbvN4SAcBWm9vfABEQxIcXsOXEGxLWsW3FSeK2fp5Iv
S19eQ6Z6N2jw/H6xLpd5Zrvw4vAROOVKiYNkQKkqU95hqJQz+9xPOBwDIIL2isQ2
qd0fgDryue7D31XJ/Qrwxa++I70ew4u3TqYboUAL6aTIAxSGmMlbk2CDvVusRUw5
lrN7qxWejq61Qlhx+l9xEEBcq5HflQZpFENn95xT6l6IiLiiEWT4Gju4EwZz+CUO
pe99QrkBDQRQoX/wAQgAq6SDCbXHh6GKFnb1as0zzlngwv6MiA5eaY+83qOgeXov
UVOZBQU8vBmVuF/3Pd5Q7asTOy+40sBYcuCwsMvtXPX0s7A0pdSn5A7DFelVRM5y
oQheASDCtlnp1xpL/8GTr/YuYlQSgC5zqcv23FatrKQ5ljPDV+tbe40T0HQ1491x
g+QPmnS4jofcOGBJ/AcAPAXU17zEiip/JmDOGfpvAf+igRNW5nyGfCkkrHeAaovR
tkqMMtq3YZBBrfgYIuGOZYzIz/lOCDyVb6QP2B/rn6ub5UeB0oYJa98uW7Zmx1vn
ZIPgtbDFRoAj2NV1JEAgmZABcYYQVVpRuvyEC+94FwARAQABiQEfBBgBAgAJBQJQ
oX/wAhsMAAoJEHgXvfg4V7gYfcMH/3hiqNPHlb9FxY4p8gIj6JWdj++CXXjRg4Re
4QWP/JvRH5v4z8DLstcJmezgerHyFqSb7ylo108qONW+x9Q1tNRe+ey9YOeg4581
tdXLMPaGjU0jz5aCKnKQR7LJjOTS4SPPU4dYURDUUkmKgU4tmbQVdkXyT45rCh6b
tB655w1aYSLbA93E3DKkdqoN1gCTlwzsiayLsu1kiWSUopOlPKcwLjyo1OpRC2ph
3T7RuF+whq/NQ8SYSz6GgWh8tSMt/SDpJ5/YOveyH7iAuwcL4pNgGYSjAPklSolp
UZwJPsLOqDSxnlc7RKwX9hsdDL7tybYAX2P7BOGpoNDeN1ZMIEA=
=Kyc/
-----END PGP PUBLIC KEY BLOCK-----
</pre>
<p><br /></p>
<h5><code>/* ---[ STEP 4: Prepare your project and its metadata ]--- */</code></h5>
<p>With Clojars you can publish SNAPSHOTS or releases. The latter can be "promoted" if you meet all the criteria in your project.clj, which are:</p>
<ul>
<li>you cannot have the word SNAPSHOT in your version</li>
<li>you should have your license filled in</li>
<li>you need to have the :scm section filled in
<ul><li>you can either do this manually, as in the example below</li>
<li>or lein in theory can automatically do this for you if you are using GitHub and its remote "ID" is origin (though I've had issues even in that case)</li></ul></li>
</ul>
<p>Here is an example project.clj:</p>
<div class="codeblock">
<pre>
(<span class="keyword">defproject</span> <span class="function-name">thornydev/go-lightly</span> <span class="string">"0.4.0"</span>
<span class="constant">:description</span> <span class="string">"Clojure library to facilitate CSP concurrent programming based on Go concurrency constructs"</span>
<span class="constant">:url</span> <span class="string">"<a href='https://github.com/midpeter444/go-lightly'>https://github.com/midpeter444/go-lightly</a>"</span>
<span class="constant">:license</span> {<span class="constant">:name</span> <span class="string">"Eclipse Public License"</span>
<span class="constant">:url</span> <span class="string">"<a href='http://www.eclipse.org/legal/epl-v10.html'>http://www.eclipse.org/legal/epl-v10.html</a>"</span>}
<span class="constant">:profiles</span> {<span class="constant">:dev</span> {<span class="constant">:dependencies</span> [[criterium <span class="string">"0.3.1"</span>]]}}
<span class="constant">:dependencies</span> [[org.clojure/clojure <span class="string">"1.5.0"</span>]]
<span class="constant">:scm</span> {<span class="constant">:name</span> <span class="string">"git"</span>
<span class="constant">:url</span> <span class="string">"<a href='https://github.com/midpeter444/go-lightly'>https://github.com/midpeter444/go-lightly</a>"</span>})
</pre>
</div>
<p><br /></p>
<h5><code>/* ---[ STEP 5: Commit your code ]--- */</code></h5>
<p>Make sure you have committed all your changes into Git (or Hg, SVN or whatever SCM you are using). Tag the release if you are so inclined and (optional) push it to GitHub or your remote or central hosting server.</p>
<p><br /></p>
<h5><code>/* ---[ STEP 6: Deploy to Clojars ]--- */</code></h5>
<p>From the top of your project directory, enter:</p>
<div class="precode"><pre><code>lein deploy clojars
</code></pre></div>
<p>In my case, my gpg-agent prompted me twice for my GPG passphrase and then the deploy happened.</p>
<p>When you do this lein will create a pom and a jar and upload those to Clojars. That pom.xml should include SCM information that looks like this:</p>
<div class="codeblock">
<pre>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">scm</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">tag</span><span class="nxml-tag-delimiter">></span><span class="nxml-text">12f653361a88c4df14</span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">tag</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-element-local-name">url</span><span class="nxml-tag-delimiter">></span><span class="nxml-text"><a href='https://github.com/midpeter444/go-lightly'>https://github.com/midpeter444/go-lightly</a></span><span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">url</span><span class="nxml-tag-delimiter">></span>
<span class="nxml-tag-delimiter"><</span><span class="nxml-tag-slash">/</span><span class="nxml-element-local-name">scm</span><span class="nxml-tag-delimiter">></span>
</pre>
</div>
<p>The tag there should be the SHA1 of the last commit (in the case of Git). <em>Note:</em> Don't confuse it with a "tag" that you create with "git tag".</p>
<p>If the deploy was successful, your jar should be signed and (possibly) ready for Promotion.</p>
<p><br /></p>
<h5><code>/* ---[ STEP 7: Check whether your jar was signed ]--- */</code></h5>
<p>Create a new lein project and make your deployed library one of its dependencies. Then in that new project run:</p>
<div class="precode"><pre><code>$ lein deps :verify
:signed [criterium "0.3.1"]
:unsigned [enlive "1.0.1"]
:signed [org.clojure/tools.macro "0.1.1"]
:signed [org.clojure/clojure "1.5.0"]
:bad-signature [thornydev/go-lightly "0.4.0"]
</code></pre></div>
<p>You see that some are signed and some are not. Obviously, you want yours to say <code class="so">:signed</code>. If it has <code class="so">unsigned</code> then you are probably either using Lein 1 or you didn't generate your GPG keys. If it has <code class="so">:bad-signature</code> then something got corrupted on the Clojars server. In my case above, I promoted and tried to redeploy, which uncovered a bug in lein/clojars that caused some files to get overwritten when they shouldn't. This issue should be fixed soon. If you do have that problem, delete your local copy from your ~/.m2 directory and contact someone on the #leiningen IRC channel.</p>
<p><br /></p>
<h5><code>/* ---[ Optional STEP 8: Promote to release status ]--- */</code></h5>
<p>If you are eligible to promote to release status, you will see a "Promote" button on your Clojars page. If you are not, you may be missing SCM information, which is what happened to me recently.</p>
<p>Note that once you promote you can no longer deploy to that version again, so make sure you're ready to make it immutable. After that, you can only add new versions.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com29tag:blogger.com,1999:blog-2977002084155733470.post-66100901732173222622013-01-13T21:12:00.002-05:002013-03-03T10:09:35.858-05:00Go Concurrency Constructs in Clojure, part 4: idioms and tradeoffs<blockquote class="bordered">
The Go approach to concurrent software can be characterized as: Don't communicate by sharing memory, share memory by communicating.... You use the channel to pass the data back and forth between the Go routines and make your concurrent program operate that way.
<br /><br />
--Rob Pike, Google IO 2012 conference talk
</blockquote>
<blockquote class="bordered">
Programmers know the benefits of everything and the tradeoffs of nothing.
<br /><br />
--Rich Hickey, Strangeloop 2011 talk "Simple Made Easy"
</blockquote>
<style type="text/css">
<!--
div.clojure { font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; color: #000000; background: #ececec; font-size: 10pt; text-decoration: none; }
span.default { font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; color: #000000; background: #ececec; font-size: 10pt; text-decoration: none; }
span.default a { font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; color: #000000; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.string { color: #8b2252; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.string a { color: #8b2252; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.doc { color: #8b2252; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.doc a { color: #8b2252; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.variable-name { color: #a0522d; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.variable-name a { color: #a0522d; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.comment { color: #b22222; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.comment a { color: #b22222; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.comment-delimiter { color: #b22222; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.comment-delimiter a { color: #b22222; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.preprocessor { color: #483d8b; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.preprocessor a { color: #483d8b; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.builtin { color: #483d8b; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.builtin a { color: #483d8b; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.function-name { color: #0000ff; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.function-name a { color: #0000ff; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.keyword { color: #a020f0; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.keyword a { color: #a020f0; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
span.constant { color: #008080; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: none; }
span.keyword a { color: #008080; font-family: "DejaVu Sans Mono", "Lucida Console", Monaco, monospace font-stretch: normal; font-weight: 700; font-style: normal; background: #ececec; font-size: 10pt; text-decoration: underline; }
-->
<p></style></p>
<script type="text/javascript">
<!--
// this function is needed to work around
// a bug in IE related to element attributes
function hasClass(obj)
{
var result = false;
if (obj.getAttributeNode("class") != null)
{
result = obj.getAttributeNode("class").value;
}
return result;
}
function stripe(id)
{
// the flag we'll use to keep track of
// whether the current row is odd or even
var even = false;
// if arguments are provided to specify the colors
// of the even & odd rows, then use the them;
// otherwise use the following defaults:
var evenColor = arguments[1] ? arguments[1] : "#fff";
var oddColor = arguments[2] ? arguments[2] : "#ddd";
// obtain a reference to the desired table
// if no such table exists, abort
var table = document.getElementById(id);
if (! table) { return; }
// by definition, tables can have more than one tbody
// element, so we'll have to get the list of child
// <tbody>s
var tbodies = table.getElementsByTagName("tbody");
// and iterate through them...
for (var h = 0; h < tbodies.length; h++)
{
// find all the <tr> elements...
var trs = tbodies[h].getElementsByTagName("tr");
// ... and iterate through them
for (var i = 0; i < trs.length; i++)
{
// avoid rows that have a class attribute
// or backgroundColor style
if (! hasClass(trs[i]) &&
! trs[i].style.backgroundColor)
{
// get all the cells in this row...
var tds = trs[i].getElementsByTagName("td");
// and iterate through them...
for (var j = 0; j < tds.length; j++)
{
var mytd = tds[j];
// avoid cells that have a class attribute
// or backgroundColor style
if (! hasClass(mytd) &&
! mytd.style.backgroundColor)
{
mytd.style.backgroundColor =
even ? evenColor : oddColor;
}
}
}
// flip from odd to even, or vice-versa
even = ! even;
}
}
}
function toggle_invis( name )
{
var filter =
{ acceptNode:
function( node )
{ var classname = node.id;
if( classname )
{ var classbase = classname.substr( 0, name.length );
if( classbase == name ) { return NodeFilter.FILTER_ACCEPT; } }
return NodeFilter.FILTER_SKIP; } };
var walker = document.createTreeWalker( document.body ,
NodeFilter.SHOW_ELEMENT ,
filter ,
false );
while( walker.nextNode() )
{
var e = walker.currentNode;
if( e.style.display == "none" ) { e.style.display = "inline"; }
else { e.style.display = "none"; }
}
}
-->
</script>
<p><br /></p>
<h4><code>/* ---[ Functional Clojure Idioms ]--- */</code></h4>
<p>In the preface to <a href="http://eloquentruby.com/">Eloquent Ruby</a>, Russ Olsen relates a story that after teaching a Ruby class one of his students complained that his Ruby programs tended to end up looking like his Java programs. I remember that same experience when I first learned Ruby in the early 2000s. In fact, I set up conventions for myself in Ruby to try to "force" it to be more like Java. I hadn't fully grokked that changing languages does not mean just learning the syntax and libraries. It means adopting the idioms, the approaches and even the constraints that the designer put into the language and that have arisen in the language community. It often means changing the way you think. That is certainly true of Clojure, perhaps more than any language I've ever learned. (<em>Side note:</em> I haven't learned Haskell yet!)</p>
<p>Go is intended primarily to be systems-programming language, with a strong focus on writing concurrent server programs. While it does include some more "modern" functional features, such as closures and first class functions, it is not a functional programming language.</p>
<p>These blog posts and the go-lightly library are my attempt to think about <strong>how</strong> to adopt a Go-like CSP concurrency programming style into Clojure. But we should also think about <strong>when</strong> to adopt this style of programming. I don't have an answer yet and I'm writing this library to explore this area.</p>
<p>The Go-channel model is a message passing model, which you could view as a poor-man's <a href="https://en.wikipedia.org/wiki/Actor_model">Actor model</a>, something Rich Hickey considered for the Clojure language and decided to leave out. He outlines those reasons in the <a href="http://clojure.org/state">clojure.org/state</a> page (see the "Message Passing and Actors" section in particular).</p>
<p>On the blog lead-in above, I quote Pike saying that Go's model is to share memory by communicating, rather than the other way around. Hickey argues that the message-passing model is a complex model. Remember that "complex", in the Clojure community, is an objective measure of how entwined things are. Sharing memory by communicating is more complex as you have to coordinate entities, particularly if you have blocking waits. If one depends directly on the other, you have an entangled system. Coordinating multiple entities can be difficult and with blocking operations can lead to deadlocks. If you use timeouts to overcome potential deadlocks, then you have to add special logic to your code to deal with it. Sharing memory with immutable values or STM-protected values is often a simpler, less complected, model.</p>
<p>Go (synchronous) channels are for synchronizing threads or routines. When you need to synchronize in other languages you have constructs like CountDownLatches, CyclicBarriers, waiting on a future, a join in a fork-join model or, the lowest level, mutexes and semaphores. The synchronous channel provides an <em>easier</em> model that also allows message passing. But remember that easy is not necessarily <a name="fromFoot1">simple</a> [<a href="#foot1">footnote 1</a>] and consider the tradeoffs.</p>
<p><br /></p>
<h4><code>/* ---[ Channels as Queues ]--- */</code></h4>
<p>Go buffered channels, on the other hand, are not synchronous communication tools. They are queues for asynchronous workflows. By decoupling producer(s) and consumer(s), they are less complected. Hickey, in his <a href="http://www.infoq.com/presentations/Simple-Made-Easy">Simple Made Easy</a> talk, has a table listing paired concepts where one is more complex and the other simple. On his chart, Actors are juxtaposed with queues: Actors are complex, queues are simple. And in the <a href="https://www.youtube.com/watch?v=ROor6_NGIWU">2012 Clojure conj keynote</a>, Hickey stated that queues have been underemphasized in the Clojure community so far.</p>
<p>Thus, as far as channels go, the asynchronous buffered ones are more idiomatic in Clojure than synchronous channels. In fact, an async concurrent queue is used in the Clojure Programming book's webcrawler example. For contrast, I implemented this webcrawler <a href="https://github.com/midpeter444/go-lightly/blob/master/go-lightly-examples/clj-examples/src/thornydev/go_lightly/webcrawler/webcrawler.clj">example using go-lightly</a>.</p>
<p>On the other hand, from what I've seen, synchronous channels are very idiomatic in Go, and perhaps even preferred over buffered channels. That is the impression I've gotten from watching Pike's talks and reading a few threads on the golang mailing list. For example, see <a href="https://groups.google.com/forum/?hl=fr&fromgroups=#!topic/golang-nuts/koCM3i-bbMs">this thread</a> where one participant says:</p>
<div class="precode"><pre><code>Go channels can be asynchronous, but most of the time that's not
what you want. When communicating between goroutines running on the
same machine a synchronous send/recv improves program flow. Synchronous
channels have a lot of advantages by making program flow predictable
and easier to think about.
</code></pre></div>
<p>I'll leave it there as an open question deserving careful thought.</p>
<p><br /></p>
<h4><code>/* ---[ Making channels more idiomatic ]--- */</code></h4>
<p>As I've been doing various example programs with go-lightly, I've noticed that the code structure can be more imperative than functional, in part because channels are not composable data structures. You can't pass a channel to map, reduce or filter, since it does not implement the ISeq interface.</p>
<p>To remedy this, I've added four functions to go-lightly to allow you to treat it like a seq when retrieving from it.</p>
<p>The first two functions convert the current values on a channel to a seq or a vector <strong>without</strong> removing them from the channel. The latter two functions remove or <em>drain</em> the channel either immediately (non-lazy) or as you read from it in a lazy fashion.</p>
<hr />
<p><strong>(channel->seq chan)</strong><br />"Takes a snapshot of all values on a channel <em>without</em> removing the values from the channel. Returns a (non-lazy) seq of the values.</p>
<hr />
<p><strong>(channel->vec chan)</strong><br />"Takes a snapshot of all values on a channel <em>without</em> removing the values from the channel. Returns a vector of the values."</p>
<hr />
<p><strong>(drain chan)</strong><br />"Removes all the values on a channel and returns them as a non-lazy seq."</p>
<hr />
<p><strong>(lazy-drain chan)</strong><br />"Lazily removes values from a channel. Returns a Cons lazy-seq until it reaches the end of the channel (as determined by getting a nil value when asking for the next value on the channel)."</p>
<hr />
<p>All the sequences will end once a nil value is pulled off the queue, which represents the end of the queue. Since the <code class="so">lazy-drain</code> function is lazy if something else added to the queue before the end of the queue is reached, it will read that additional value, where the non-lazy <code class="so">drain</code> method will not.</p>
<p>A REPL session will illustrate how these work.</p>
<p>First let's look at <code class="so">channel->seq</code> using a buffered channel:</p>
<div class="clojure">
<pre>
<span class="comment-delimiter">;; </span><span class="comment">define a channel with capacity of 7
</span> user=> (<span class="keyword">def</span> <span class="function-name">ch</span> (go/channel 7))
#'user/ch
user=> (<span class="builtin">dotimes</span> [i 6] (<span class="preprocessor">.put</span> ch i))
nil
user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> [0, 1, 2, 3, 4, 5]>
<span class="comment-delimiter">;; </span><span class="comment">grab the values into a non-lazy seq
</span> user=> (<span class="keyword">def</span> <span class="function-name">cseq</span> (go/channel->seq ch))
#'user/cseq
user=> cseq
(0 1 2 3 4 5)
user=> (<span class="variable-name">type</span> cseq)
<span class="preprocessor">clojure.lang.ArraySeq</span>
<span class="comment-delimiter">;; </span><span class="comment">the values have not been removed from the channel
</span> user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> [0, 1, 2, 3, 4, 5]>
<span class="comment-delimiter">;; </span><span class="comment">if a value is removed from the channel the seq is not affected
</span> user=> (<span class="preprocessor">.take</span> ch)
0
user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> [1, 2, 3, 4, 5]>
user=> cseq
(0 1 2 3 4 5)
</pre>
</div>
<p><code class="so">channel->vec</code> behaves the same way except it returns a vector, not a seq.</p>
<p>Next let's look at the drain functions using a buffered channel:</p>
<div class="clojure">
<pre>
user=> (<span class="keyword">def</span> <span class="function-name">ch</span> (go/channel 7))
#'user/ch
user=> (<span class="builtin">dotimes</span> [i 6] (<span class="preprocessor">.put</span> ch i))
nil
user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> [0, 1, 2, 3, 4, 5]>
<span class="comment-delimiter">;; </span><span class="comment">calling drain returns a seq of all the values on the
</span> <span class="comment-delimiter">;; </span><span class="comment">channel and removes them
</span> user=> (<span class="keyword">def</span> <span class="function-name">dseq</span> (go/drain ch))
#'user/dseq
user=> (<span class="variable-name">type</span> dseq)
<span class="preprocessor">clojure.lang.IteratorSeq</span>
user=> dseq
(0 1 2 3 4 5)
user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> []>
<span class="comment-delimiter">;; </span><span class="comment">add more elements to the queue; the seq is not affected
</span> user=> (<span class="builtin">dotimes</span> [i 6] (<span class="preprocessor">.put</span> ch (<span class="variable-name">+</span> 100 i)))
nil
user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> [100, 101, 102, 103, 104, 105]>
user=> dseq
(0 1 2 3 4 5)
<span class="comment-delimiter">;; </span><span class="comment">now let's lazily drain the queue into a lazy-seq Cons
</span> user=> (<span class="keyword">def</span> <span class="function-name">zseq</span> (go/lazy-drain ch))
#'user/zseq
user=> (<span class="variable-name">type</span> zseq)
<span class="preprocessor">clojure.lang.Cons</span>
<span class="comment-delimiter">;; </span><span class="comment">realize the first three elements - takes only those
</span> <span class="comment-delimiter">;; </span><span class="comment">off the channel
</span> user=> (<span class="variable-name">take</span> 3 zseq)
(100 101 102)
user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> [103, 104, 105]>
<span class="comment-delimiter">;; </span><span class="comment">take more than are on the channel - get only what's available
</span> user=> (<span class="variable-name">take</span> 100 zseq)
(100 101 102 103 104 105)
<span class="comment-delimiter">;; </span><span class="comment">the channel is now empty
</span> user=> ch
#<<span class="preprocessor">LinkedBlockingQueue</span> []>
<span class="comment-delimiter">;; </span><span class="comment">what if we try to take/read them again? They are still
</span> <span class="comment-delimiter">;; </span><span class="comment">in the lazy-seq since it caches the results</span>
user=> (<span class="variable-name">take</span> 100 zseq)
(100 101 102 103 104 105)
<span class="comment-delimiter">;; </span><span class="comment">we can use higher order functions - composability!
</span> user=> (<span class="variable-name">map</span> str (<span class="variable-name">filter</span> odd? zseq))
(<span class="string">"101"</span> <span class="string">"103"</span> <span class="string">"105"</span>)
</pre>
</div>
<p><br /><br />These functions also work with synchronous channel, but are not as useful. In particular <code class="so">lazy-seq</code> faces a race condition with producers that try to transfer multiple consecutive values as shown below:</p>
<div class="clojure">
<pre>
<span class="comment-delimiter">;; </span><span class="comment">create a synchronous channel
</span> user=> (<span class="keyword">def</span> <span class="function-name">c</span> (go/channel))
#'user/c
<span class="comment-delimiter">;; </span><span class="comment">queue up 6 values to be put onto the queue but
</span> <span class="comment-delimiter">;; </span><span class="comment">only one can go on at a time waiting for a consumer
</span> user=> (go/go (<span class="builtin">dotimes</span> [i 6] (<span class="preprocessor">.transfer</span> c i)))
#<core$future_call$reify__6110@5d47522a: <span class="constant">:pending></span>
user=> c
<span class="comment-delimiter">;; </span><span class="comment">channel->vec and channel->seq will grab one value since
</span> <span class="comment-delimiter">;; </span><span class="comment">a producer is waiting for a consumer</span><span class="comment">
</span> #<<span class="preprocessor">LinkedTransferQueue</span> [0]>
user=> (go/channel->vec c)
[0]
user=> c
#<<span class="preprocessor">LinkedTransferQueue</span> [0]>
<span class="comment-delimiter">;; </span><span class="comment">drain also takes only the first value and also removes it
</span> <span class="comment-delimiter">;; </span><span class="comment">from the channel, allowing the next val to be put on the channel
</span> user=> (go/drain c)
(0)
user=> c
#<<span class="preprocessor">LinkedTransferQueue</span> [1]>
<span class="comment-delimiter">;; </span><span class="comment">lazy-drain looks like it works!
</span> user=> (<span class="variable-name">take</span> 2 (go/lazy-drain c))
(1 2)
user=> c
#<<span class="preprocessor">LinkedTransferQueue</span> [3]>
<span class="comment-delimiter">;; </span><span class="comment">but it has a race condition with the producer, so may
</span> <span class="comment-delimiter">;; </span><span class="comment">not get everything we "queued" up to transfer
</span> user=> (go/lazy-drain c)
(3 4)
user=> c
#<<span class="preprocessor">LinkedTransferQueue</span> [5]>
</pre>
</div>
<p><br /></p>
<h4><code>/* ---[ Next ]--- */</code></h4>
<p>I've now created a <a href="https://github.com/midpeter444/go-lightly/wiki">go-lightly wiki</a> with fairly extensive documentation and I've implemented a number of <a href="https://github.com/midpeter444/go-lightly/tree/master/go-lightly-examples/clj-examples">example applications using go-lightly</a>.</p>
<p>A couple of things you may want to look into if you find this topic interesting:</p>
<ul>
<li>I've added formal abstractions for the Channel types in go-lightly. Channel, BufferedChannel and TimeoutChannel all implement the <a href="https://github.com/midpeter444/go-lightly/wiki/go-lightly-GoChannel-API">GoChannel protocol</a>.</li>
<li>As mentioned above, I have done a go-lightly centric implementation of a simple web crawler app based on the example at the end of Ch. 4 from the <a href="http://www.clojurebook.com/">O'Reilly Clojure Programming</a> book. This will provide a good contrast between the two concurrency approaches.</li>
<li>I have added the ability to preferentially read from one or more channels in a <code class="so">select</code> or <code class="so">selectf</code>.</li>
<li>I implemented Pike's Chinese Whispers <a href="https://github.com/midpeter444/go-lightly/tree/master/go-lightly-examples/clj-examples#whispers">example in go-lightly</a> to see how many "Go routines" <a href="https://github.com/midpeter444/go-lightly/wiki/Go-routines">could be spawned in Clojure</a> compared to Go. This is certainly an area where the JVM is less powerful than Go.</li>
</ul>
<p><br /></p>
<h4><code>/* ---[ Resources and Notes ]--- */</code></h4>
<p><a name="foot1"></a><br /><strong>[1]</strong> If you've spent much time in the Clojure community, you know I'm referring to the distinction that Hickey drew between the concepts of <em>easy</em>, a subjective concept, and <em>simple</em>, an objective one in his <a href="http://www.infoq.com/presentations/Simple-Made-Easy">Simple Made Easy</a> presentation. If you haven't watched it, well, <a href="https://twitter.com/bodil/status/221322654492274688">listen to Bodil</a>. (<a href="#fromFoot1">Jump back</a>)</p>
<p>Blog entries in this series:</p>
<ul>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure.html">Go Concurrency Constructs in Clojure, part 1</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure2.html">Go Concurrency Constructs in Clojure, part 2: select</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure3.html">Go Concurrency Constructs in Clojure, part 3: why go-lightly?</a></li>
</ul>
<p>The Clojure go-lightly library on GitHub: <a href="https://github.com/midpeter444/go-lightly"><a href='https://github.com/midpeter444/go-lightly'>https://github.com/midpeter444/go-lightly</a></a></p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com2tag:blogger.com,1999:blog-2977002084155733470.post-23879700476792366662013-01-12T13:49:00.000-05:002013-03-03T09:44:45.284-05:00Go Concurrency Constructs in Clojure, part 3: why go-lightly?<blockquote class="bordered">
There's a legendary example called the concurrent prime sieve, which is kind of an amazing thing. It was the first truly beautiful concurrent program I think I ever saw.
<br /><br />
--Rob Pike, Google IO 2012 conference talk
</blockquote>
<p><br /></p>
<h4><code>/* ---[ Why go-lightly? ]--- */</code></h4>
<p>In <a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure.html">part 1</a> and <a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure2.html">part 2</a> of this blog series, I introduced the basics of Go channels, Go routines and the Go select statement. I then walked through initial implementations of these ideas in the <a href="https://github.com/midpeter444/go-lightly">go-lightly library</a> and how to use the <a href="https://github.com/ztellman/lamina">lamina</a> channel and facilities to do Go-style CSP concurrent programming.</p>
<p>If the lamina library, which is 2+ years old now (thus reasonably mature and stable) and under active development, can be used for this, why am I proposing a new library? Well, I might have built one anyway just to get familiar with CSP style programming and improve my Clojure skills, but ultimately, I do think there is a good justification for us to consider a new library focused just around this.</p>
<p>The lamina library is fundamentally focused an asynchronous event-driven programming. Since dealing with callbacks can get messy and is hard to structure in a functional way, the core construct and central metaphor of Zach Tellman's approach to async programming is a channel that is used for putting and pulling events. Since a key focus of async event-driven programming is to avoid blocking, there are very few blocking operations in the lamina library. One case where it is provided is that you can choose to wait on pulling a value out of a channel. This is the part we've seen in use to emulate Go channels.</p>
<p>However, the primary use case for lamina channels is an event queue, which means you want it to be unbounded and non-blocking, especially for events being put onto the queue. Thus, lamina uses a Java ConcurrentLinkedQueue underneath.</p>
<p>Go channels, however, come in two flavors: <strong>bounded, blocking queues</strong> of size 0 (every put has to have a corresponding take) and <strong>bounded, asynchronous queues</strong> of a size you specify in the <code class="so">make</code> function. The lamina channel really maps to neither, though in some scenarios it can be used for async queues or blocking queues where you need to block on read (but not write).</p>
<p>As I discussed in the first blog entry, Java's util.concurrent library already provides these Go channel types and even more variations on them. The <strong>bounded, blocking queue</strong> maps to a <code class="so">SynchronousQueue</code> or a <code class="so">TransferQueue</code> (if you only use the <code class="so">transfer</code> and <code class="so">take</code> methods). The <strong>bounded, asynchronous queue</strong> maps to <code class="so">LinkedBlockingQueue</code>.</p>
<p>Thus, go-lightly proposes to wrap these Java concurrent queues, specifically facilitating a Go-style CSP concurrency semantics.</p>
<p><br /></p>
<h4><code>/* ---[ Why bounded blocking queues? ]--- */</code></h4>
<p>So what is a use case where I really need a bounded blocking queue? </p>
<p>First from here on out I will use the term <strong>channel</strong> or <strong>Go channel</strong> to refer to a blocking queue of size 0 and <strong>buffered channel</strong> to refer to a non-blocking queue of arbitrary size: this is the Go terminology.</p>
<p>Rephrasing the question - when would I need a channel and not a buffered channel? With a buffered channel you "fire-and-forget" and let some other thread pluck it off the buffered channel when it's ready.</p>
<p>A channel, on the other hand, is a synchronization mechanism between threads/routines similar to a CountDownLatch, CyclicBarrier or join of a fork-join model, except you not only synchronize threads, but pass messages between them, so it is synchronizing communication tool.</p>
<p><br /></p>
<h4><code>/* ---[ Beautiful concurrency ]--- */</code></h4>
<p>The <a href="http://play.golang.org/p/9U22NfrXeq">golang site</a> provides an example a concurrent prime sieve algorithm that, as implemented, requires blocking channels. If you were to use a lamina channel or buffered channel you'd potentially have some threads running way ahead of the others unnecessarily consuming memory and wasting CPU cycles.</p>
<p>This is the "first truly beautiful concurrent program" Pike referred to in his Google IO 2012 talk.</p>
<p>Let's look at the Go implementation from the Golang website first:</p>
<script src="https://gist.github.com/4519593.js"></script>
<p>The <code class="so">Generate</code> and <code class="so">Filter</code> functions absolutely need to synchronize - when they push data onto a channel, they need to wait until the consumer (a chained filter function or main) is ready to pull it off.</p>
<p>Here is a Clojure version using go-lightly:</p>
<script src="https://gist.github.com/4470515.js"></script>
<p>Happily, the implementations are pretty much the same line-for-line.</p>
<p><br /></p>
<h4><code>/* ---[ Next ]--- */</code></h4>
<p>In the next blog entry, I will contrast the Go CSP concurrency model to the Clojure concurrency model and add some functions to allow channels to interoperate with the Clojure seq abstraction.</p>
<p><br /></p>
<h4><code>/* ---[ Resources ]--- */</code></h4>
<p>Both of the prime sieve examples are available in the GitHub go-lightly repo:</p>
<ul>
<li><a href="https://github.com/midpeter444/go-lightly/blob/master/go-lightly-examples/go-examples/src/concPrimeSieve/concPrimeSieve.go">Go version</a></li>
<li><a href="https://github.com/midpeter444/go-lightly/blob/master/go-lightly-examples/clj-examples/src/thornydev/go_lightly/primes/conc_prime_sieve.clj">Clojure go-lightly version</a></li>
</ul>
<p>Blog entries in this series:</p>
<ul>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure.html">Go Concurrency Constructs in Clojure, part 1</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure2.html">Go Concurrency Constructs in Clojure, part 2: select</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure4.html">Go Concurrency Constructs in Clojure, part 4: idioms and tradeoffs</a></li>
</ul>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com1tag:blogger.com,1999:blog-2977002084155733470.post-70836195486872823822013-01-05T19:10:00.000-05:002013-10-11T20:01:15.769-04:00Go Concurrency Constructs in Clojure, part 2: select<blockquote class="bordered">
"The select statement is a key part of why concurrency is built into Go as features of the language, rather than just a library. It's hard to do control structures that depend on libraries."
<br><br>
-Rob Pike, 2012 Google IO Conference
</blockquote>
<p>In the <a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure.html">first blog entry</a> of this series, I introduced some simple examples of the CSP (Communicating Sequential Processes) model of concurrency that have been built into the Go language. I'm blogging my investigation of how we might leverage this style of concurrent programming in Clojure.</p>
<p>The key benefit of the CSP approach is that you can use normal sequential semantics and control flows that are easy to reason about while building concurrent flows and processes. Channels are used to communicate and synchronize processes to bring control and deterministic behavior to an otherwise non-deterministic concurrent environment. We can do this without locks or other low-level constructs that are hard to reason about. The CSP constructs are built on top of those low-level primitives (or at least compare-and-swap mechanisms), but they are hidden from view from the application developer.</p>
<p><br /></p>
<h4><code>/* ---[ A construct to wait for the next available channel ]--- */</code></h4>
<p>Go comes with a ready-made control structure called <code class="so">select</code>. It provides a shorthand way to specify how to deal with multiple channels, as well as allow for timeouts and non-blocking behavior (via a "default" clause). It looks like a switch/case statement in C-based languages, but is different in that all paths involving a channel are evaluated, rather than just picking the first one that is ready.</p>
<p>Let's look at an example (adapted from <a href="http://www.youtube.com/watch?v=f6kdp27TYZs&feature=youtu.be">Pike's 2012 Google IO talk</a>):</p>
<div class="codeblock">
<pre>
<span class="keyword">select</span> {
<span class="keyword">case</span> v1 := <-c1:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c1\n"</span>, v1)
<span class="keyword">case</span> v2 := <-c2:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c2\n"</span>, v2)
}
</pre>
</div>
<p>This select wraps two channels. It evaluates both channels and there are four possible scenarios:</p>
<ol>
<li>c1 is ready to give a message, but c2 is not. The message from c1 is read into the variable v1 and the code clause for that first case is executed.</li>
<li>c2 is ready to give a message, but c1 is not. v2 then is assigned to the value read from c2 and its code clause is executed.</li>
<li>Both c1 and c2 are ready to give a message. One of them is randomly chosen to execute and the other does not execute. Note this means that you cannot depend on the order your clauses will be executed in.</li>
<li>Neither c1 nor c2 are ready to give a message. The select will block until the first one is ready, at which point it will be read from the channel and execute the corresponding code clause.</li>
</ol>
<p>Select statements can also have a default to make it non-blocking:</p>
<div class="codeblock">
<pre>
<span class="keyword">select</span> {
<span class="keyword">case</span> v1 := <-c1:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c1\n"</span>, v1)
<span class="keyword">case</span> v2 := <-c2:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c2\n"</span>, v2)
<span class="keyword">default</span>:
fmt.<span class="function-name">Println</span>(<span class="string">"no channel was ready to communicate"</span>)
}
</pre>
</div>
<p>If neither channel is ready, the select executes the default clause and returns immediately.</p>
<p>Finally, select statements can also have a timeout:</p>
<div class="codeblock">
<pre>
<span class="keyword">for</span> {
<span class="keyword">select</span> {
<span class="keyword">case</span> v1 := <-c1:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c1\n"</span>, v1)
<span class="keyword">case</span> v2 := <-c2:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c2\n"</span>, v2)
<span class="keyword">case</span> <-time.<span class="function-name">After</span>(1 * time.Second):
fmt.<span class="function-name">Println</span>(<span class="string">"You're too slow!"</span>)
}
}
</pre>
</div>
<p>In this example, the select is wrapped in an infinite loop, which will stop the first time any one round takes longer than 1 second to read from either channel. But we can also set a timeout on the loop as a whole:</p>
<div class="codeblock">
<pre>
timeout := time.<span class="function-name">After</span>(1 * time.Second)
<span class="keyword">for</span> {
<span class="keyword">select</span> {
<span class="keyword">case</span> v1 := <-c1:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c1\n"</span>, v1)
<span class="keyword">case</span> v2 := <-c2:
fmt.<span class="function-name">Printf</span>(<span class="string">"received %v from c2\n"</span>, v2)
<span class="keyword">case</span> <-timeout:
fmt.<span class="function-name">Println</span>(<span class="string">"Time's up!"</span>)
}
}
</pre>
</div>
<p>Now the loop will always cease after 1 second and in that one second it will read as many times as possible from either channel.</p>
<p>Here is an example of using selects with timeouts in a Go program:</p>
<script src="https://gist.github.com/4439889.js"></script>
<p><br /></p>
<h4><code>/* ---[ Implementing select in Clojure ]--- */</code></h4>
<p>Let's evaluate some of the ways we could emulate or implement the behavior of select in Clojure. While Go does have closures, treats functions as first class entities and deemphasizes object-orientation and inheritance, Go is not a functional language. So how should something like <code class="so">select</code> be done in Clojure? What is the essence of what it accomplishes?</p>
<p>Let's first turn to the <a href="http://racket-lang.org/">Racket language</a>, a Lisp that is a descendant of Scheme. It has Events in the language. I am not deeply knowledgable about Racket, but from the research I've done the <a href="https://cxwangyi.wordpress.com/2012/07/22/why-go-use-racket/">analog of select in Racket is sync</a>. The <a href="http://docs.racket-lang.org/reference/sync.html#(def._((quote._~23~25kernel)._sync))">sync function</a> takes one or more "synchronizable events" and blocks until the first one is ready and returns that result:</p>
<div class="codeblock">
<pre>
(<span class="keyword">let</span> ((msg (sync evt1 evt2 evt3)))
<span class="comment-delimiter">;; </span><span class="comment">do something with the first message result here
</span> )
</pre>
</div>
<p>As with Go's <code class="so">select</code>, Racket's <code class="so">sync</code> will choose to read from one of the events at random if more than one is ready.</p>
<p>Notice that the Racket version does <strong>not</strong> take a code block to execute for each event. In functional programming, it is preferable and more natural to return a value from an operation. Go's select is truly a control structure (in the C language sense of the word) - it does not return a value.</p>
<p>So let's implement Racket's sync in Clojure.</p>
<p>In order to implement select/sync in Clojure using the Java Queue libraries we used in the previous blog entry, we will need to able to check whether more than one of the queues has a value ready without blocking. That is why I selected the TransferQueue over the SynchronousQueue.</p>
<p>Next we have to decide what to name it. <code class="so">sync</code> is already taken in clojure.core and has a specific and important enough meaning in Clojure that is best avoided. <code class="so">select</code> is also used -- it is a function clojure.set namespace -- but since it is not in clojure.core, I'll go with it in my go-lightly namespace.</p>
<p>My initial implementation to get started is a simple one - it will check all the channels to see if any are ready and if not, do a short sleep. To do the check, it uses the <code class="so">.peek</code> method of TransferQueue, since it neither blocks nor throws an exception if the queue is empty. </p>
<script src="https://gist.github.com/4449661.js"></script>
<p>You pass <code class="so">select</code> one or more channels and it immediately filters for those that already have a ready value. If there are any it picks one of those ready ones at random, dequeues the value and returns it. Only the one value is dequeued, so the other channels remain untouched.</p>
<p>If none are ready, it will "probe" the channels between short sleeps to get the first value it can find. This is an unsophisticated implementation, but it works for simple uses. (I'll provide a usage example after we add timeouts and "defaults" next.)</p>
<p><br /></p>
<h4><code>/* ---[ Adding "default" and timeouts to Clojure select ]--- */</code></h4>
<p>The <code class="so">default</code> clause in Go's select statement is a short circuit to not block if no channels are ready. Since Clojure's select is not a control structure, the most natural choice is to add another function, which I've called <code class="so">select-nowait</code>.</p>
<p>As before it takes one or more channels (as a varargs list) and an optional sentinel keyword value. If no channels are ready, <code class="so">select-wait</code> will return the sentinel keyword (if provided) or nil.</p>
<div class="codeblock">
<pre>
user=> (select-nowait ch1 ch2 ch3 <span class="constant">:bupkis</span>)
<span class="constant">:bupkis</span>
</pre>
</div>
<p>For timeouts, the Go example above shows that they come in two flavors: a timeout per round (timer starts each time you call select) or a timeout for a "conversation" that could involve multiple rounds of selecting the next value.</p>
<p>Let's take these one a time, as they will have different solutions in my implementation. For a timeout-per-select call, I've created a <code class="so">select-timeout</code> function that takes a timeout (in milliseconds) as the first argument.</p>
<div class="codeblock">
<pre>
<span class="comment-delimiter">;; </span><span class="comment">returns a value from one of the channels if it can
</span> <span class="comment-delimiter">;; </span><span class="comment">be read within 1 sec. Otherwise it times out and
</span> <span class="comment-delimiter">;; </span><span class="comment">returns :go-lightly/timeout
</span> user=> (select-timeout 1000 ch1 ch2 ch3)
<span class="constant">:go-lightly/timeout</span>
</pre>
</div>
<p>For an overall timeout, I provide two options.</p>
<p>First, following the pattern in <a href="https://gist.github.com/3146759#file-clojure-channels-3-select-clj">Alexey Kachayev's example</a> of doing this with the lamina library - we build a channel that will have a timeout sentinel value once the timer goes off. Use the go-lightly <code class="so">timeout-channel</code> factory fn and then pass that timeout channel to the select function.</p>
<p>In order for the timeout-channel to be effective, you have to be continuously calling <code class="so">select</code> until you hit the timeout. Also the current implementation of select doesn't preferentially look at the timeout channel first and select that over other channels if it is ready, but I'll be fixing that in later in the series.</p>
<p>You can also pass a timeout-channel into <code class="so">select-timeout</code> if you want both types of timers running.</p>
<p>Second, I've added a general purpose <code class="so">with-timeout</code> macro to the go-lightly.core library that wraps any arbitrary set of statements in a timeout.</p>
<p>Go <a href="https://github.com/midpeter444/go-lightly/blob/master/go-lightly/src/thornydev/go_lightly.clj">here</a> if you want to see the full implementation of these timeout methods.</p>
<p>All of these options are shown in this Clojure go-lightly example implementation of the Go "boring" select example:</p>
<script src="https://gist.github.com/4448219.js"></script>
<p><em>Note</em>: the channels here are no longer raw LinkedTransferQueues - they are go-lightly GoChannel type entities. See the <a href="https://github.com/midpeter444/go-lightly/wiki">go-lightly wiki</a> for a detailed explanation. </p>
<p><br /></p>
<h4><code>/* ---[ Emulating Go's select in lamina ]--- */</code></h4>
<p>lamina's analog to select is its <code class="so">join</code> operation, which basically routes the output of multiple lamina channels into a single channel:</p>
<div class="codeblock">
<pre>
user=> (<span class="variable-name">use</span> 'lamina.core)
nil
user=> (<span class="keyword">def</span> <span class="function-name">ch1</span> (channel))
#'user/ch1
user=> (<span class="keyword">def</span> <span class="function-name">ch2</span> (channel))
#'user/ch2
user=> (<span class="keyword">def</span> <span class="function-name">ch3</span> (channel))
#'user/ch3
user=> (<span class="type">join</span> ch1 ch3)
true
user=> (<span class="type">join</span> ch2 ch3)
true
user=> [ch1 ch2 ch3]
[<== [ … ] <== [ … ] <== […]]
user=> (enqueue ch1 <span class="constant">:one</span>)
<span class="constant">:lamina/enqueued</span>
user=> (enqueue ch2 <span class="constant">:two</span> <span class="constant">:three</span>)
<span class="constant">:lamina/enqueued</span>
user=> [ch1 ch2 ch3]
[<== [ … ] <== [ … ] <== [<span class="constant">:one</span> <span class="constant">:two</span> <span class="constant">:three</span> …]]
</pre>
</div>
<p>You can then read from the downstream channel:</p>
<div class="codeblock">
<pre>
user=> @(read-channel ch3)
<span class="constant">:one</span>
user=> @(read-channel ch3)
<span class="constant">:two</span>
</pre>
</div>
<p>To create a whole-conversation timeout, you can call the <code class="so">periodically</code> fn that invokes your fn every 'period' milliseconds and returns the value. This was the inspiration for go-lightly's <code class="so">timeout-channel</code>.</p>
<p>To create a per-round timeout, you can use either the <code class="so">read-channel*</code> macro or the <code class="so">channel->lazy-seq</code> function, both of which take a per-read timeout.</p>
<p>This program that demonstrates these options (and a few others) using lamina (with some helper functions from go-lightly):</p>
<script src="https://gist.github.com/4463174.js"></script>
<p><br /></p>
<h4><code>/* ---[ Implementing Go's select in Clojure ]--- */</code></h4>
<p>So we can provide Racket's <code class="so">sync</code> functionality in Clojure either by implementing it ourselves or using lamina, but it is not as powerful as Go's select. What if you need to know not only the next value on the channels, but which channel it was read from? In that case, providing a function to execute per channel is a nice model. But to be more or less functional, the select statement still needs to return a value.</p>
<p>Let's hit an important point here: as I quoted at the start of this post, Piked has said that "it's hard to do control structures that depend on libraries". This is true in some languages, but not all - especially not in Lisps. You can do control structures with macros or sometimes just with functions and this is one of the key advantages of Lisp languages.</p>
<p>In the go-lightly library, I've implemented this as <code class="so">selectf</code> and it turns out I didn't need a macro.</p>
<p>Here's an example of using go-lightly's <code class="so">selectf</code> from the <a href="https://github.com/midpeter444/go-lightly/blob/master/go-lightly-examples/clj-examples/src/thornydev/go_lightly/sleeping_barber/barber.clj">sleeping-barbers example app</a> in the go-lightly-examples project:</p>
<div class="codeblock">
<pre>
(<span class="keyword">defn</span> <span class="function-name">barber-shop</span> [clients-ch]
(<span class="builtin">let</span> [barber-ch (channel)]
(<span class="builtin">loop</span> [shop-state {<span class="constant">:free-barbers</span> (init-barber-vector)
<span class="constant">:waiting-clients</span> []}]
(<span class="builtin">-></span> (selectf
clients-ch #(client-walked-in % barber-ch shop-state)
barber-ch #(barber-available % barber-ch shop-state))
(<span class="builtin">recur</span>)))))
</pre>
</div>
<p><code class="so">selectf</code> takes pairs of arguments where the first member of the pair is a channel (or the <code class="so">:default</code> keyword) and the second member of the pair is a function that takes one argument - the value read from that channel. (A function paired with <code class="so">:default</code> takes no arguments.)</p>
<p>The return value of <code class="so">selectf</code> is whatever the fn you provide returns. In the example above, I pass this value to the <code class="so">recur</code> form so that I can reset the <code class="so">shop-state</code> local var without having to use an atom to manage state changes.</p>
<p>And here is the implementation of <code class="so">selectf</code>:</p>
<div class="codeblock">
<pre>
(<span class="keyword">defn</span> <span class="function-name">selectf</span>
<span class="doc">"Control structure variable arity fn. Must be an even number of arguments where
the first is either a GoChannel to read from or the keyword :default. The second
arg is a function to call if the channel is read from. Handler fns paired with
channels should accept one argument - the value read from the channel. The
handler function paired with :default takes no args. If no :default clause is
provided, it blocks until a value is read from a channel (which could include
a TimeoutChannel). Returns the value returned by the handler fn."</span>
[& args]
(<span class="builtin">binding</span> [*choose-fn* choose-tuple]
(<span class="builtin">let</span> [chfnmap (<span class="variable-name">apply</span> array-map args)
[keywords chans] (partition-bifurcate
keyword?
(<span class="variable-name">reduce</span> #(<span class="variable-name">conj</span> % %2) [] (<span class="variable-name">keys</span> chfnmap)))
choice (doselect chans nil (<span class="variable-name">first</span> keywords))]
<span class="comment-delimiter">;; </span><span class="comment">invoke the associated fn
</span> (<span class="builtin">if</span> choice
((chfnmap (<span class="variable-name">nth</span> choice 0)) (<span class="variable-name">nth</span> choice 1))
((chfnmap (<span class="variable-name">first</span> keywords)))))))
</pre>
</div>
<p>I won't give a full explanation of this implementation and all its helper functions, but notice this piece:</p>
<div class="codeblock">
<pre>
(<span class="builtin">let</span> [chfnmap (<span class="variable-name">apply</span> array-map args)
...
])
</pre>
</div>
<p>That's all that is required to turn the argument pairs into a control structure. It creates a map of channels to fns and once you have a map in Clojure, programming is straightforward.</p>
<p><br /></p>
<h4><code>/* ---[ Next ]--- */</code></h4>
<p>In the next entry we'll implement some more interesting CSP examples in Go and Clojure and think about the pros and cons of using lamina vs. go-lightly.</p>
<p><br /></p>
<h4><code>/* ---[ Resources ]--- */</code></h4>
<p>All of the code in this blog series, including the Go and lamina example code, is in the <a href="https://github.com/midpeter444/go-lightly">go-lightly project</a> on GitHub.</p>
<p>Lamina library: <a href="https://github.com/ztellman/lamina"><a href='https://github.com/ztellman/lamina'>https://github.com/ztellman/lamina</a></a></p>
<p>The Go examples are from Rob Pike's talk <a href="http://www.youtube.com/watch?v=f6kdp27TYZs&feature=youtu.be">Google I/O 2012 - Go Concurrency Patterns</a></p>
<p><a href="https://github.com/kachayev">Alexey Kachayev</a> wrote down the Go code that Pike used in the 2012 Google IO presentation, which otherwise doesn't seem to have been made available. Alexey published them as gists. They won't compile out of the box, so I've been modifying them, but wanted to link to his gists: <a href='https://gist.github.com/3124594'>https://gist.github.com/3124594</a>.</p>
<p>Alexey also then brainstormed on ways to implement these examples in Clojure using the lamina library. Those gists are at: <a href='https://gist.github.com/3146759'>https://gist.github.com/3146759</a></p>
<p><strong>Links to this blog series:</strong></p>
<ul>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure.html">Go Concurrency Constructs in Clojure, part 1: introduction</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure3.html">Go Concurrency Constructs in Clojure, part 3: why go-lightly?</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure4.html">Go Concurrency Constructs in Clojure, part 4: idioms and tradeoffs</a></li>
</ul>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com2tag:blogger.com,1999:blog-2977002084155733470.post-76403352638007456472013-01-01T22:59:00.000-05:002013-07-03T22:51:41.123-04:00Go Concurrency Constructs in Clojure, part 1<blockquote class="bordered">
If you look at the programming languages of today, you'd probably get this idea that the world is object-oriented, but it's not. It's actually parallel.... There's all these things that are happening simultaneously in the world and yet the computing tools we have are really not very good at expressing that kind of world view. And that seems like a failing.
<br /><br />
--Rob Pike, 2012 Heroku Waza conference
</blockquote>
<p><br /></p>
<h4><code>/* ---[ Go ]--- */</code></h4>
<p>The Go language recently turned <a href="http://blog.golang.org/2012/11/go-turns-three.html">3 years old</a>, so it is about 2 years Clojure's junior. I have only started investigating Go and one of the things that has captured my attention are its primitives for concurrency. Rob Pike, the leading spokesman for Go and one of its co-creators, has done a number of interesting talks on Go concurrency patterns and how it is built into the language. If you haven't watched them, here are two that I recommend:</p>
<ul>
<li><a href="http://www.youtube.com/watch?v=f6kdp27TYZs&feature=youtu.be">Google I/O 2012 - Go Concurrency Patterns</a></li>
<li><a href="http://vimeo.com/49718712">Concurrency is not Parallelism</a> (<a href="https://rspace.googlecode.com/hg/slide/concur.html#landing-slide">slides here</a>)</li>
</ul>
<p>I'll be referring to the first one through this post.</p>
<p>Pike talks a lot about how Go routines and channels are first class entities in the language, with simple syntax and keywords baked in. Go routines are akin to threads that you kick off to run in "the background". Pike's analogy is to think of them like launching a process on the command line with the ampersand. Staying with the Unix analogy, if you launch a process in the background and then need to communicate with it, what do you do? In Unix/Linux you have a number of options, such as a socket, a pipe or some other form of IPC or to use shared memory.</p>
<p>The Go language creators have chosen the "channel" as a core "inter-routine" communication mechanism. Quoting Pike: "The Go model is not to communicate by sharing memory, but to share memory by communicating".</p>
<p>What is called "inter-routine" here would be called inter-process in Erlang or traditional C/Unix programming or "inter-thread" communication in languages like Java. But for Go it is more appropriate to say "inter-routine". Pike emphasizes that go routines are lighter weight than threads. Go routines can be shared or multiplexed onto multiple running threads over their lifetime, avoiding thread starvation issues. They have their own stack frame, but I believe it is managed on the heap (need to research this more).</p>
<p>The roots of the Go routine and Go channel start in Tony Hoare's <a href="https://en.wikipedia.org/wiki/Communicating_sequential_processes">Communicating Sequential Processes</a> paper (now <a href="http://www.usingcsp.com/cspbook.pdf">book</a>). CSP addresses concurrency interaction patterns - how separate processes (in the Unix or Erlang sense), threads or routines communicate and coordinate with each other via <strong>message passing</strong>. We want constructs that reduce the complexity of inter-process/inter-thread communication using primitives that are easy to use and reason about. This means not having to be a deep expert in a system's memory model in order to do concurrent programming. Instead, it hides semaphores, mutexes, barriers and other low level concurrency constructs in higher-level abstractions.</p>
<p><br /></p>
<h4><code>/* ---[ Go-style CSP in Clojure? ]--- */</code></h4>
<p>My primary interest here is in what support for Go-like CSP patterns exist, or can be made to exist, in Clojure. Clojure, after all, promises to bring sanity to concurrent programming by means of efficient immutable data structures and software transaction memory for mutable state.</p>
<p>Go channels come in two forms: synchronous blocking channels that cannot hold multiple entries and non-synchronous buffered channels that can have multiple entries. I'll explain the nuances of <em>synchronous</em> here in a moment.</p>
<p>The <a href="http://golang.org/ref/spec">Go spec</a> says: <em>A channel provides a mechanism for two concurrently executing functions to synchronize execution and communicate by passing a value of a specified element type</em>.</p>
<p>Does Clojure have this? There are two things in Clojure or Java we can potentially use to emulate Go channels:</p>
<ul>
<li>Java concurrency queues. In particular, SynchronousQueue, BlockingQueue and TransferQueue.</li>
<li>Zach Tellman's Clojure <a href="https://github.com/ztellman/lamina">lamina library</a>, whose primary focus is asynchronous event-based programming.</li>
</ul>
<p>In this blog series, I will introduce the <a href="https://github.com/midpeter444/go-lightly">go-lightly Clojure library</a> I built to have Go concurrency constructs. The GitHub repo for it also has many examples, some of which use Java concurrent queues directly, some of which use the lamina library and many of which use the go-lightly library.</p>
<p><strong>Note:</strong> I also ran across the <a href="http://www.cs.kent.ac.uk/projects/ofa/jcsp/">Java CSP (JCSP) project</a>, which I haven't investigated yet, but might be something to build a Clojure library around.</p>
<p><br /></p>
<h4><code>/* ---[ "boring" basics ]--- */</code></h4>
<p>In his initial examples to show how Go channels work, Pike uses a background process that is, as he calls it, "boring" - it just prints its name or the word "boring" at random intervals. After listening for a while, the "main" process gets tired and wants to leave or end the conversation.</p>
<p>Here are the first two examples in Go from his 2012 Google IO talk, modified slightly to work from one main function:</p>
<script src="https://gist.github.com/4428907.js"></script>
<p>Here is the output from each option (single vs. multiple):</p>
<div class="precode"><pre><code>$ ./boring-generators single
You say: "boring! 0"
You say: "boring! 1"
You say: "boring! 2"
You say: "boring! 3"
You say: "boring! 4"
You're boring: I'm leaving.
$ ./boring-generators multiples
Joe 0
Ann 0
Joe 1
Ann 1
Joe 2
Ann 2
Joe 3
Ann 3
Joe 4
Ann 4
Joe 5
Ann 5
Joe 6
Ann 6
Joe 7
Ann 7
Joe 8
Ann 8
Joe 9
Ann 9
You're boring: I'm leaving.
</code></pre></div>
<hr />
<p>See <a href="#appendix1">appendix 1</a> if you would like to compile and run this on your system. I'll frequently list the outputs during this blog series, but it helps to see the latency between print statements to get a better feel for how these examples work.</p>
<p>See <a href="#appendix2">appendix 2</a> for links my GitHub project with this code and to other gists with related code examples.</p>
<hr />
<p>Pike calls this the generator pattern because the invoked "boring" function creates a (synchronous) channel, then creates a closure that references that channel, launches that closure as a go routine and immediately returns the channel to the calling function.</p>
<p>The go routine <strong>sends</strong> messages to the channel with the <code class="so"><-</code> operator. <br />For example, <code class="so">c <- "hello kitty"</code> sends the feline greeting into the channel.</p>
<p>The other function <strong>receives</strong> messages from the channel with the same operator, by putting the channel on the right side of the operator: <code class="so"><- c</code>.</p>
<p>These are blocking operations with a synchronous channel. If the sender sends a message to the channel when there is no receiver waiting, it will block until a receiver comes and grabs its message off the channel. And, conversely, a receiver will block waiting for a sender if there isn't already one pushing to the channel.</p>
<p>In the <code class="so">multipleGenerators</code> version, two go routines are created, each with its own channel. The receiving "main" function now receives from each channel consecutively in a defined order, which is why you always get Joe's output first, then Ann's.</p>
<p>One final thing to note: we don't explicitly do any work to shutdown the go routines. Go routines will automatically stop operation when the <code class="so">main</code> function exits. Thus, go routines are like daemon threads in the JVM (well, except for the "thread" part ...)</p>
<p><br /></p>
<h4><code>/* ---[ "boring" in Clojure ]--- */</code></h4>
<p>Java has two analogs of a Go synchronous channel: the <a href="http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/SynchronousQueue.html">SynchronousQueue</a> and the <a href="http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/TransferQueue.html">TransferQueue</a>.</p>
<p>The <strong>SynchronousQueue</strong> has the same specs I mentioned above: it allows one sender at a time that will block waiting for a receiver and one receiver at a time that will block waiting for a sender. The "queue", despite its name, has no internal storage. It's <code class="so">size</code> method always returns 0 and its <code class="so">peek</code> method always returns null. If you use just the <code class="so">put</code> method to send and the <code class="so">take</code> function to receive, it behaves like the Go channel in the first example.</p>
<p>The <strong>TransferQueue</strong> is a more liberal - you can use it like a SynchronousQueue or more like a BlockingQueue where you can put multiple messages on the queue and only block if you try to <code class="so">put</code> onto a full queue (if it is bounded) or <code class="so">take</code> from an empty queue. To use it like a SynchronousQueue, use <code class="so">transfer</code> and <code class="so">take</code>. The API is rich enough that you can find other uses also, such as non-blocking <code class="so">offer</code> and <code class="so">poll</code> methods to send and receive without blocking.</p>
<p>In the go-lightly code base examples, I use both, but here I'm going to stick with the TransferQueue for reasons that will become clear when we get to the Go <code class="so">select</code> statement in the next blog entry.</p>
<p>OK, so the channel will be a Java TransferQueue. How do we implement a go routine in Clojure?</p>
<p>Clojure's <code class="so">future</code> function is similar to a go routine in that it launches a new "routine" (Java thread) with its own stack and flow of execution. The interface is similar too: in Go you give an invoked function to the go statement. You do the same to the Clojure future function.</p>
<div class="precode"><pre><code>// launch a go routine in Go
go func() { fmt.Println ("hello kitty") }()
;; launch a thread that returns a future in Clojure
(future (println "sayonara"))
</code></pre></div>
<p>But Clojure futures differ from a go routine in at least two important ways:</p>
<ol>
<li><p>A Clojure future launches a new thread (or rather obtains a thread from the Clojure thread agent pool), whereas, as mentioned before, a Go routine is lighter weight than a Java thread. I don't know of any Clojure or Java facilities for creating something equally lightweight, so I will use threads.</p></li>
<li><p>Clojure futures are <strong>not</strong> daemon threads and I don't think there is any way to tell them to be daemon threads. Thus, you cannot give a future an infinite loop and expect your program to close down. If you launch such a future, you would have to either:</p>
<ol><li>Call <code class="so">(future-cancel myfut)</code> on the future, which means you have to retain a reference to the future. You can't just fork-and-forget.</li>
<li>Set a flag, either through shared memory or a message via a channel, that the future will check periodically to see if it should stop. However, if this future is stuck in a blocking call trying to read from or push onto the blocking queue, this approach won't work.</li></ol></li>
</ol>
<p>In addition, you also need to call <code class="so">(shutdown-agents)</code> at the end of your Clojure program to shut down the agent/future Thread pool.</p>
<p>Thus, Clojure's <code class="so">future</code> requires more bookkeeping than Go's <code class="so">go</code>. </p>
<p>But Clojure has macros to help, so I've written two macros and some helper functions to lessen the bookkeeping.</p>
<p>The first macro is simply called <code class="so">go</code> and has accompanying <code class="so">stop</code> and <code class="so">shutdown</code> functions. The second macro, <code class="so">go&</code>, is meant for fork-and-forget use so I give it the Unix ampersand in the name. It has the least amount of ceremony, but cannot be controlled through the Java Executor framework like the future and agents threads can be.</p>
<script src="https://gist.github.com/4430718.js"></script>
<p>And here's my implementation of the boring-generator using it. To match the Go terminology, Finally, I also define the function <code class="so">channel</code> to simply return a LinkedTransferQueue.</p>
<script src="https://gist.github.com/4430997.js"></script>
<p>While the <code class="so">go&</code> macro is easier to use and more like the actual Go go-routine launcher, it has one downside: it is not REPL-friendly if your go routine doesn't shutdown naturally. In this case it will block on the <code class="so">(.transfer ch)</code> call on line 39 and hang around in memory. And each time you invoke the function in the REPL it creates another daemon, draining JVM resources and memory over time. </p>
<p>Since Go language development is not REPL-based they can get away with it. If you create a main function:</p>
<div class="precode"><pre><code>(defn -main [& args]
(thornydev.go-lightly.boring.generator-tq/multiple-generator&))
</code></pre></div>
<p>and run it from the command line:</p>
<div class="precode"><pre><code>lein run
</code></pre></div>
<p>it will behave just like the Go version. You'll get the same output as the Go example above and it will shutdown gracefully instead of hanging.</p>
<p>But to be REPL friendly, I'll typically use <code class="so">go</code> and <code class="so">stop</code> rather than <code class="so">go&</code>.</p>
<p>Another way to handle this in Go would be to close the channel and have the go-routine check whether the channel is closed before continuing.</p>
<p>Unfortunately, this is not possible with the Java concurrency classes mentioned above - they are not Closeable resources.</p>
<p>However, the go-lightly library and the Clojure lamina libraries both provide the notion of a closeable channel, which leads to our next implementation.</p>
<p><br /></p>
<h4><code>/* ---[ A "boring" lamina implementation ]--- */</code></h4>
<p>The <a href="https://github.com/ztellman/lamina">lamina</a> library created by Zach Tellman provides constructs for handling evented asynchronous programming. It defines a channel whose purpose is to be a event-driven data structure that represents a stream of messages or events. A lamina channel has basic send (<code class="so">enqueue</code>) and receive (<code class="so">receive</code> or <code class="so">read-channel</code>) functionality, but also is composable with other channels using classic functional programming constructs, such as map, reduce and filter. It also provides very useful fork/join operators.</p>
<p>For the "boring" example, we only need the ability to enqueue, read, and close the channel and check whether the channel is closed.</p>
<script src="https://gist.github.com/4431580.js"></script>
<p>Since the "boring" go routine stops when the channel is closed, this use of the <code class="so">go&</code> macro is REPL-friendly and works as expected when run standalone from the command line.</p>
<p><br /></p>
<h4><code>/* ---[ More macro goodness ]--- */</code></h4>
<p>Finally, let's add one more macro to clean up that last example. If you've done much Clojure or Lisp programming, you know that a common macro pattern is a <code class="so">with-xxx</code> binding macro that cleans up resources for you.</p>
<p>Clojure in fact has a <code class="so">with-open</code> binding macro that will call "close" on all the things specified in the bindings. So that should work here, right? Well, the devil being in the details, it doesn't. <code class="so">with-open</code> actually calls the Java Closeable interface method <code class="so">.close</code>, not "close". And lamina channels do not implement Java's Closeable interface - they do not have a <code class="so">.close</code>. So I grabbed the source for clojure.core/with-open and made my own (and put it in the go-lightly.util namespace):</p>
<div class="precode"><pre><code>(defmacro with-channel-open
"bindings => [name init ...]
Evaluates body in a try expression with names bound to the values
of the inits, and a finally clause that calls (close name) on each
name in reverse order."
[bindings & body]
(assert (vector? bindings) "a vector for its binding")
(assert (even? (count bindings)) "an even number of forms in binding vector")
(cond
(= (count bindings) 0) `(do ~@body)
(symbol? (bindings 0)) `(let ~(subvec bindings 0 2)
(try
(with-channel-open ~(subvec bindings 2) ~@body)
(finally
(~'close ~(bindings 0)))))
:else (throw (IllegalArgumentException.
"with-open only allows Symbols in bindings"))))
</code></pre></div>
<p>So with that in place we can revise the "boring" lamina implementation:</p>
<script src="https://gist.github.com/4431922.js"></script>
<p><br /></p>
<h4><code>/* ---[ Looking ahead ]--- */</code></h4>
<p>In the <a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure2.html">next installment</a> we'll dig into the Go <code class="so">select</code> statement, and further evaluate how to use the Java concurrency queues and the lamina libraries as Go channels.</p>
<p><a name="appendix1"></a><br /><br /></p>
<h4><code>/* ---[ Appendix 1: Compile and run Go examples ]--- */</code></h4>
<p>If you don't have Go installed, see the <a href="http://golang.org/doc/install">golang install guide</a>. On Ubuntu, it is as simple as:</p>
<div class="precode"><pre><code>sudo apt-get install golang-go
</code></pre></div>
<p>Next, decide where you want your go projects to live (mine are in <code class="so">$HOME/lang/go/projects</code>). cd to that directory and do:</p>
<div class="precode"><pre><code>$ export GOPATH=$HOME/lang/go/projects # change to yours
$ mkdir src
$ mkdir src/boring-generators # your Go project name here
$ cd boring-generators
$ emacs boring-generators.go # or whatever editor you like
$ go build # this invokes the compiler
</code></pre></div>
<p>You will then have a <code class="so">boring-generators</code> executable that you can run:</p>
<div class="precode"><pre><code>$ ./boring-generators
</code></pre></div>
<p>(<em>Note:</em> I didn't find that setting GOPATH was really necessary, but it is in the instructions, so YMMV).</p>
<p><a name="appendix2"></a><br /><br /></p>
<h4><code>/* ---[ Appendix 2: Resources ]--- */</code></h4>
<p><a href="https://github.com/kachayev">Alexey Kachayev</a> wrote down the Go code that Pike used in the 2012 Google IO presentation, which doesn't seem to have been made available. Alexey published them as gists. They won't compile out of the box, so I've been modifying them, but wanted to link to his gists: <a href='https://gist.github.com/3124594'>https://gist.github.com/3124594</a>.</p>
<p>Alexey also then brainstormed on ways to implement these examples in Clojure using the lamina library. Those gists are at: <a href='https://gist.github.com/3146759'>https://gist.github.com/3146759</a></p>
<p>My code for working through these ideas are in my <a href="https://github.com/midpeter444/go-lightly">go-lightly project</a> on GitHub.</p>
<p>Links to this blog series:</p>
<ul>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure2.html">Go Concurrency Constructs in Clojure, part 2: select</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure3.html">Go Concurrency Constructs in Clojure, part 3: why go-lightly?</a></li>
<li><a href="http://thornydev.blogspot.com/2013/01/go-concurrency-constructs-in-clojure4.html">Go Concurrency Constructs in Clojure, part 4: idioms and tradeoffs</a></li>
</ul>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com6tag:blogger.com,1999:blog-2977002084155733470.post-37549125100301455302012-12-26T20:02:00.000-05:002012-12-26T20:36:15.464-05:00My CS/Programming Top 10 for 2012 <p>As many will do and I did <a href="http://thornydev.blogspot.com/2011/12/my-csprogramming-top-10-for-2011.html">last year</a>, I looked through my notes, <a href="https://github.com/midpeter444">projects</a>, <a href="https://twitter.com/midpeter444">tweets</a>, <a href="http://thornydev.blogspot.com/">blog entries</a> and <a href="https://dl.dropbox.com/u/23673690/howto-wiki.html">personal wiki</a> to assemble the highlights of my year on all topics computer science and software engineering.</p>
<p>These are the top 10 "things" that added the most to my knowledge, impressed me as excellent tools, and added to the joy of being a software developer. Here's my list in no particular order:</p>
<ol>
<li><a href="#top1">Security Now podcast</a></li>
<li><a href="#top2">Chrome Dev Tools</a></li>
<li><a href="#top3">Emacs 24</a></li>
<li><a href="#top4">Groovy</a></li>
<li><a href="#top5">Clojure</a></li>
<li><a href="#top6">z (rupa/z)</a></li>
<li><a href="#top7">Xubuntu</a></li>
<li><a href="#top8">Coursera</a></li>
<li><a href="#top9">Fiddler2 and Wireshark</a></li>
<li><a href="#top10">TrueCrypt and other encryption tools</a></li>
<li>One that should be on the list: <a href="#datomic">Datomic</a></li>
</ol>
<p><a name="top1"></a><br /><br /></p>
<h4><code>/* ---[ 1. Security Now podcast ]--- */</code></h4>
<p>In March I did <a href="http://thornydev.blogspot.com/2012/03/technical-podcasts-i-listen-to.html">a short blog entry</a> on the podcasts I was listening to or had heard of and wanted to try out. Good technical podcasts are a gold mine of information that you can use to fill the interstices of your day - while commuting, cleaning the kitchen or taking a walk.</p>
<p>The podcast that had the biggest impact on me in 2012 is <a href="http://twit.tv/show/security-now">Security Now</a>, done by Steve Gibson and Leo Laporte, one of the flagship podcasts of the <a href="http://twit.tv/">twit.tv network</a>.</p>
<p>To date, they have done 384 episodes, starting in August 2005 and the vast majority are still relevant and worth listening to. You can download them from <a href="https://www.grc.com/securitynow.htm">Steve's GRC Security Now website</a>.</p>
<p>The focus, of course, is on computer security, mostly for the individual user, not at the corporate level. The podcast also covers networking theory and practice in great detail, since the network is mainly how malware spreads and is a vast attack surface for it. For example, this year Steve did a <a href="http://twit.tv/show/security-now/343">deep dive into SPDY</a>, the <a href="https://en.wikipedia.org/wiki/SPDY">networking protocol</a> developed by Google to speed up the web by reducing page load time by overcoming the TCP slow start problem.</p>
<p>And there's plenty of focus on cryptography and security. A highlight of the year was Steve's episode on <a href="http://twit.tv/show/security-now/374">Elliptic Curve Crypto</a>, a crypto technology that will likely be used more heavily in days to come.</p>
<p>In addition, you learn a lot about how hard drives work, since Steve wrote <a href="https://www.grc.com/sr/spinrite.htm">SpinRite</a>, a disk maintenance and recovery utility, which I use for maintenance on my spinning disks.</p>
<p>Also, starting with episode #233 ("Let's Design a Computer, part 1"), Steve does a 8+ episode series on the basics of how computers work, including what machine language is, how assembly language works, the role of stacks and registers, hardware interrupts and RISC vs. CISC architectures. You can learn (or be refreshed on) in surprising levels of detail for an audio-only medium. Steve is very good at explaining this stuff.</p>
<p>This year, while keeping up with the weekly new broadcasts, I went back and started at episode 1. At this point I've listened to about half of the episodes, so this will continue to be my mainstay into 2013.</p>
<p><a name="top2"></a><br /><br /></p>
<h4><code>/* ---[ 2. Chrome Dev Tools ]--- */</code></h4>
<p>This year I got back into JavaScript programming. I remember the horrible days of debugging by alert statements, which contributed to the general consensus that JavaScript was a toy language and a piece of ill-thought out crap. Despite its warts, a result of its ridiculously over-short allowed design period, Brendan Eich created a rather fascinating and powerful programming language. Even though we like to complain about its issues, <a href="http://yuiblog.com/crockford/">I agree with Crockford</a> that given the conditions under which it was developed, we got better than we deserved and Mr. Eich is to thank for that.</p>
<p>So I was pleased to discover the awesome Chrome Dev Tools for browser based JavaScript development. JavaScript debugging can actually be pleasurable. Some resources to get you started if you aren't using it:</p>
<ul>
<li><a href="https://developers.google.com/chrome-developer-tools/">Main Google site for it</a></li>
<li><a href="http://javascriptjabber.com/006-jsj-chrome-dev-tools-with-paul-irish/">JavaScript Jabber podcast</a></li>
<li><a href="https://developers.google.com/chrome-developer-tools/docs/videos">Videos!</a></li>
</ul>
<p><a name="top3"></a><br /><br /></p>
<h4><code>/* ---[ 3. Emacs24 ]--- */</code></h4>
<p>Emacs is alive and well. In fact it is thriving more than ever. I've been a long time user of emacs and I use it for everything except Java (which really needs a full IDE).</p>
<p><a href="https://www.gnu.org/software/emacs/">Emacs 24</a>, released this year, is a great text editor. I use it on both Linux and Windows, the exact <a href="https://github.com/midpeter444/emacs24-setup">same set up</a> on both.</p>
<p>Most notably Emacs has package repositories now. Three, in fact, that I know of:<br />* <a href="http://emacswiki.org/emacs/ELPA">ELPA</a>, which is <a href="http://elpa.gnu.org/">maintained/sponsored by GNU</a> and has only the core emacs packages that adhere to the copyleft licensing model of the Free Software Foundation.<br />* <a href="http://marmalade-repo.org/">Marmalade</a><br />* <a href="http://melpa.milkbox.net/">MELPA</a>, which is where most of the bleeding edge work goes.</p>
<p>I used ELPA and MELPA by default, but I sometimes switch over to Marmalade if it has something not on the others. Generally MELPA and Marmalade seem to have the same packages, though MELPA often has the most recent. To make things confusing, MELPA moved to a date-based versioning system, like "20121206.1504", rather than the more traditional major.minor versioning system, such as "0.19".</p>
<p>There is a still a big learning curve to emacs and some things are still pretty esoteric (I still have trouble getting themes to work), but when people ask me why I use emacs I say: "if programming is your main career and hobby wouldn't you want to use the most powerful tool available? It's worth the few months of learning to enjoy the benefits for the rest of your life." But isn't emacs "old"??? (as if that's a bad thing) Seriously, when I use emacs I feel like I'm tapping into some of the collective wisdom of our programming culture from the last 30 years.</p>
<p>And no disrespect to vim. I like vim too. Pick one of those two and learn it. Stop using Notepad++ or worse.</p>
<p>A few emacs highlights from my year:</p>
<ul>
<li><p>I love the <a href="https://github.com/clojure/tools.nrepl">nrepl</a> <a href="http://jkpl.lepovirta.org/how-do-i/clojure-nrepl-emacs.html">package</a> for Clojure. Now I can use those <a href="https://github.com/kingtim/nrepl.el#clojure-buffer-commands">fancy keystrokes</a> to auto-evaluate Clojure s-expressions. With the <a href="https://github.com/purcell/ac-nrepl">ac-nrepl</a> package, it has code completion and will show you the argument signature for functions in the minibuffer! Some IDE-like goodness right there.</p></li>
<li><p><a href="http://emacswiki.org/emacs/ParEdit">paredit</a>. When I talk to people about Clojure (or Lisp in general), I sometimes get the story of how horrible it was balancing parentheses at 3 in the morning the day their CS class assignment was due. I am happy to announce to anyone that doesn't know: <strong>that problem is solved</strong>. It's name is paredit. Here is <a href="http://www.slideshare.net/mudphone/paredit-preso">the slide deck</a> I originally learned it from.</p></li>
<li><p>Learn to use emacs macros in two ways:</p>
<ul><li>named macros you'll use a lot and save in your init.el (or macros.el if you want a separate file).</li>
<li>temp unnamed macros to automate some task you need to do some one-time repetitive thing, say, 10 times in a file. This <a href="https://www.youtube.com/watch?v=dE2haYu0co8">EmacsRocks video</a> shows a great example of that.</li></ul></li>
</ul>
<p><a name="top4"></a><br /><br /></p>
<h4><code>/* ---[ 4. Groovy ]--- */</code></h4>
<p>When I was first learning Ruby, many years ago, I remember experiencing <a href="http://www.artima.com/intv/rubyP.html">Matz' principle of least surprise</a>. Once you learned the basic gist of Ruby and its blocks and classes, you could often just guess how to do something or what a method would be called and it would work. It was a very satisfying experience.</p>
<p>This year I joined a new company and they have largely adopted Groovy as their primary scripting language. As I jumped in to learn it, I had that deja vu feeling of learning Ruby, this time wrappering the Java language we know and love.</p>
<p>For example, I started to write a Groovy script that would have to recursively traverse a directory structure, and I remembered the pain of doing this in Java with its FilenameFilters and other APIs you had to learn to get anything done. I said to myself "I hope Groovy has made this easier". Holy smokes, they wrapped <code class="so">java.io.File</code> to have an <code class="so">eachFileRecurse</code> method that takes a closure:</p>
<div class="precode"><pre><code>new File('.').eachFileRecurse {
if (it.name =~ /.*\.txt/) println it;
}
</code></pre></div>
<p>There is also an <code class="so">eachDirRecurse</code> and variations where you can pass in a file type filter.</p>
<p>The more I learn about Groovy the more I like it. In fact, the "groovy-JDK" is one of my favorite things: <a href='http://groovy.codehaus.org/groovy-jdk/'>http://groovy.codehaus.org/groovy-jdk/</a>. The Groovy creators and contributors have wrapped a large number of the Java classes, using the Groovy metaclass concept, and given them additional useful methods. Such as:</p>
<ul>
<li><p>String now has an <code class="so">eachLine</code> method and versions of <code class="so">replaceAll</code> and <code class="so">replaceFirst</code> that take a closure, allowing arbitrarily complex logic to be executed to determine the replacement string.</p></li>
<li><p>Map now has an <code class="so">any</code> method that takes a predicate closure to see if at least one entry passes the predicate test. It also now has map and reduce, though the authors unfortunately followed Ruby in calling them <code class="so">collect</code> and <code class="so">inject</code> respectively.</p></li>
<li><p>And thank the gods, they wrappered the horrible <code class="so">java.util.Date</code> class and made it more useful.</p></li>
</ul>
<p>It provides many functional programming constructs, such as closures (the lambdas of Groovy), immutable data structures, higher order functions and very importantly: <strong>regex, list and map literals</strong>, akin to JavaScript or Closure literals (though the map literal syntax is different in Groovy).</p>
<p>With GStrings you get string interpolation and multi-line strings. And Groovy gives you simpler syntax for accessing getters and setters - you grab them like properties.</p>
<p>In short when you are hacking out large swaths of boilerplate in Java, using tedious syntax to do stuff with Maps, Lists, Regular Expressions and a variety of other things, you constantly think to yourself, "man I wish I could be doing in this in Groovy". Groovy makes programming a pleasure.</p>
<p>I'm still learning it and look forward to using it for years to come.</p>
<p><a name="top5"></a><br /><br /></p>
<h4><code>/* ---[ 5. Clojure ]--- */</code></h4>
<p>And speaking of bringing the joy back to programming, Clojure is a combination of elegance, joy and ... <em>wait a minute, how do I do this in Clojure?</em> I ran across <a href="http://tech.puredanger.com/2012/02/05/clojure-values/comment-page-1/#comment-296111">someone</a> who described himself as a "perennial Clojure beginner". I can identify with that. Since I don't come from a Lisp or functional programming background, the last year learning Clojure has been like learning to ride a bicycle again. Except this bicycle is tricked out and has gears, knobs and restrictions that are different from the other bicycles.</p>
<p>I've started proselytizing co-workers about Clojure. I get the "why Clojure?" question a lot, so here is my version:</p>
<ul>
<li>Combines the best of Lisp, such as macros, and Java/JVM, such as its world class garbage collector (which a language built on immutable data structures needs)</li>
<li>Brilliant design for immutable data structures that is now being adopted by other languages (Scala for one)</li>
<li>Functional programming model, but with practical bent (not Haskell, but more pure than Common Lisp)</li>
<li>STM: software transaction memory -- brilliant solution to shared mutable state</li>
<li>Designed for concurrency (in a couple of different ways)</li>
<li>A fast dynamic language: faster than ruby and python, comparable to Java in many areas and can drop into Java easily when performance is the most important thing</li>
<li>ClojureScript: bring the power of Clojure macro writing, namespaces and better syntax to doing your JavaScript work</li>
<li>Data centric (like lisps), but even better by being abstraction centric</li>
<li>Clean design for solving the “expression problem”: <a href='http://www.ibm.com/developerworks/java/library/j-clojure-protocols/?ca=drs'>http://www.ibm.com/developerworks/java/library/j-clojure-protocols/?ca=drs</a></li>
<li>Separation of concerns – an overall philosophy to tease things apart into simple (non-completed) pieces: <a href='http://www.infoq.com/presentations/Simple-Made-Easy'>http://www.infoq.com/presentations/Simple-Made-Easy</a>
<ul><li>Example: polymorphism is not tied to inheritance</li></ul></li>
<li>Simple and elegant syntax. For example, I find Scala to be powerful but overwhelming and confusing in its approach to syntax and expression</li>
<li>Community:
<ul><li>Small focused libraries (separation of concerns, non-complected)</li>
<li>Datomic => one of the greatest examples of separation of concerns there is</li>
<li>Core.logic => modern logic programming easily integrated into your program</li></ul></li>
<li>Finally, an argument <em>ad hominem</em>: Rich Hickey. You need to watch the series of presentations he’s made over the past 5 years (perhaps one every week <a href="https://twitter.com/bodil/status/221322654492274688">as Bodil suggests</a>). Unquestionably the most impactful thinker in CS I’ve ever encountered. Even if you end up not agreeing with all of his views, you will learn a lot and think about things in a different way, possibly changing the way you think about our craft.</li>
</ul>
<p>Finally, as a coda to this paean to Clojure: The O'Reilly <a href="http://www.clojurebook.com/">Clojure Programming</a> book came out this year. Chas Emerick, Brian Carper and Christophe Grand have written a fantastic book. It is a book you will learn from and come back to for its insights, examples and reference material for many years. Definitely belongs on my top 10 for 2012 list.</p>
<p><a name="top6"></a><br /><br /></p>
<h4><code>/* ---[ 6. rupa/z ]--- */</code></h4>
<p>The z shell script (<em>not zsh</em>) is one of my favorite discoveries of 2012. To give it more press, I gave it its own blog entry, which you read here: <a href="http://thornydev.blogspot.com/2012/12/an-irritation-no-longer.html"><a href='http://thornydev.blogspot.com/2012/12/an-irritation-no-longer.html'>http://thornydev.blogspot.com/2012/12/an-irritation-no-longer.html</a></a>.</p>
<p>Here's the short summary: z is a 200-line shell script compatible with bash and z-shell that is a clever LRU-type cache of your directory visitations - the cache weighting is based on both frequency and recentness, which the author dubs "frecency". As you navigate around to different directories, it keeps track of where you've been, how often you've been there and how recently.</p>
<p>To navigate somewhere you've been, pass a part of the path to the z command and it will take you to the highest weighted directory in your cache.</p>
<p><a name="top7"></a><br /><br /></p>
<h4><code>/* ---[ 7. Xubuntu ]--- */</code></h4>
<p>I'm a Linux guy. I was on the Ubuntu bandwagon for many years. I played with Linux Mint a little. I've got Fedora and CentOS running in VirtualBox VMs. But when Unity came out on Ubuntu, I struggled to get used to its desktop model. It does not fit how I work. I tried it for a month and was considering what to switch to when I saw a <a href="http://linux.slashdot.org/story/11/08/04/0115232/linus-torvalds-ditches-gnome-3-for-xfce">Slashdot article</a> that Linus Torvalds was adopting XFCE to get away from the strangeness of many modern Linux desktop environments.</p>
<p>So that prompted me to try <a href="http://xubuntu.org/">Xubuntu</a>, based on XFCE and also <a href="http://lubuntu.net/">Lubuntu</a>, based on the LXDE desktop. Lubuntu was a little too minimal for me, but Xubuntu clicked for me right away. I don't like the Dash of Unity and I really really hate the fact that when I try to open a new console shell it brings the current one to the forefront. That is not what I want. I'll use Alt-Tab for that.</p>
<p>Xubuntu behaves as you expect. Click the terminal icon and it opens a new terminal. Xubuntu puts shortcut icons on the bottom, similar to Apple's desktop, but without the annoying enlargement animations. I don't do a lot of customization of my desktop. I just want one that has sane defaults and Xubuntu is that for me.</p>
<p>Ubuntu also stirred up criticism for its integration with Amazon affiliated advertisements, making the Dash a purchasing platform, in the process creating data leaks. Now you don't even have privacy when operating your desktop. The <a href="https://www.eff.org/deeplinks/2012/10/privacy-ubuntu-1210-amazon-ads-and-data-leaks">EFF write-up</a> summarizes this nicely.</p>
<p>You can turn it off, but even among Linux users I suspect the "<a href="http://www.mylinuxrig.com/post/9120015925/linux-and-the-tyranny-of-the-default">tyranny of the default</a>" will mean that most users are leaking data and thus are at the mercy of Canonical, which people are starting to develop some mistrust for.</p>
<p>Well, Xubuntu doesn't have Dash. So you get the goodness of the Ubuntu ecosystem without the privacy violations. Its defaults are sane.</p>
<p>Try it out.</p>
<p><a name="top8"></a><br /><br /></p>
<h4><code>/* ---[ 8. Coursera and Online Education ]--- */</code></h4>
<p>2012 is the year that online education skyrocketed. I've done a few <a href="http://www.codeschool.com/">CodeSchool courses</a> and enjoyed those. But now there's <a href="http://www.udacity.com/">Udacity</a> and <a href="https://www.coursera.org/">Coursera</a> and <a href="http://www.udemy.com/">Udemy</a> and <a href="https://www.edx.org/">edX</a> and probably 10 more I don't know about.</p>
<p>This year I took a Coursera course: <a href="https://www.coursera.org/course/progfun">Functional Programming Principles in Scala</a> taught by Martin Odersky. It was a great experience. The format is excellent - each week there is about 2 to 3 hours of video lectures and a programming assignment that takes anywhere from 5 to 15 hours to complete. The examples were challenging enough to make the time investment worth it. And I got a nice certificate at the end for having a passing grade.</p>
<p>Uploading assignments was done via a command in Scala's sbt tool; it was easy and seamless. The assignments were graded automatically in about 10 minutes and gave good feedback, allowing you to fix problems and resubmit. The only part of the course I didn't enjoy was using the Scala Eclipse IDE, which is still quite painful compared to Java in Eclipse or Clojure in Emacs.</p>
<p>It's amazing what you can get online for free these days. I've signed up for <a href="https://www.coursera.org/course/algs4partI">two</a> <a href="https://www.coursera.org/course/insidetheinternet">more</a> courses and have my eye on <a href="https://www.coursera.org/course/crypto">a cryptography course</a> there as well.</p>
<p><a name="top9"></a><br /><br /></p>
<h4><code>/* ---[ 9. Fiddler2 and Wireshark ]--- */</code></h4>
<p>I spent a good deal of time this year maintaining and enhancing a large "legacy" web app written that uses Ajax calls to communicate with the Java back-end. In many cases, the shortcut to figuring out what is going on is to watch the traffic between the browser and server. <a href="https://fiddler2.com/fiddler2/">Fiddler2</a> is an invaluable tool for that.</p>
<p>I also tried <a href="https://www.wireshark.org/">Wireshark</a>, but the output from Fiddler2 is just as intuitive and easy to follow as can be, since it focuses only on HTTP traffic.</p>
<p>Wireshark is more general purpose. I started learning it this year and want to get better at configuring and customizing it, so I can use it effectively (and efficiently) on Linux, since Fiddler2 is unfortunately a Windows-only product.</p>
<p><a name="top10"></a><br /><br /></p>
<h4><code>/* ---[ 10. TrueCrypt, GPG and other encryption tools ]--- */</code></h4>
<p>If you aren't using encryption for your files, hard drives and passwords, make it your new year resolution to learn the tools. Ever since <a href="https://en.wikipedia.org/wiki/Phil_Zimmermann">Phil Zimmerman</a> bravely pioneered encryption for the everyman, the suite of tools available to do this have gotten better and better.</p>
<p>I use <a href="http://www.gnupg.org/">GPG</a> to encrypt individual files, <a href="http://www.truecrypt.org/">TrueCrypt</a> to encrypt thumb drives and external drives and <a href="https://www.eff.org/deeplinks/2012/11/privacy-ubuntu-1210-full-disk-encryption">Ubuntu's full disk encryption</a> for my laptops. If you have a laptop and thumb drives, they should be encrypted.</p>
<p>A nice file encryption tool on Windows is <a href="http://www.axantum.com/AxCrypt/Default.html">AxCrypt</a>.</p>
<p>For passwords, I use <a href="https://lastpass.com">LastPass</a>, which I believe does it all correctly and securely in a "trust no one" fashion.</p>
<p>Consider using an encrypted "Trust No One" backup and file syncing service. Dropbox is not encrypted, nor is SkyDrive or Google Drive or many other popular services. Do not upload anything to those systems that you wouldn't mind having broadcast on the internet or at least read by employees of those companies.</p>
<p>Steve Gibson (of the Security Now podcast) did a multi-episode analysis of backup and file syncing services from an encryption and "trust no one" perspective. Start with <a href="https://www.grc.com/securitynow.htm">episode #349</a>. There are a number of good solutions. I use <a href="https://spideroak.com/">SpiderOak</a> on Linux.</p>
<p>If you already know and do this stuff, have a <a href="https://cryptoparty.org/wiki/CryptoParty">CryptoParty</a> in your area. If you live in my area (Raleigh/Durham, North Carolina, USA), join the <a href="http://www.dc919.org/">DC919</a> group.</p>
<p><a name="datomic"></a><br /><br /></p>
<h4><code>/* ---[ Datomic: Mine goes to 11 ]--- */</code></h4>
<p>While I did attend a <a href="http://www.datomic.com/">Datomic</a> training course this year and wrote <a href="http://thornydev.blogspot.com/2012/06/datomic-initial-analysis.html">a fairly long blog post</a> about it, I just haven't made the time to really study it yet. I fully intend to, as I think it is one of the most profound and important things to have come out in 2012. I've queued it up to be on my top 10 list in 2013.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com3tag:blogger.com,1999:blog-2977002084155733470.post-8116433604318800752012-12-24T15:43:00.000-05:002012-12-24T15:46:18.549-05:00An irritation no longer: command line joy<p><br /></p>
<h4><code>/* ---[ pushd and dirs ]--- */</code></h4>
<p>I have long been a command line person. I hate having to use the mouse. One thing that is a little cumbersome about the command line is jumping around into various deeply nested directory structures. I've long been a user of <code class="so">pushd</code>, <code class="so">dirs</code> and <code class="so">popd</code> on Unix/Linux/Cygwin consoles. But if you are alternating between 3 or more directories with some regularity, those commands require some care to use correctly.</p>
<p><br /></p>
<h4><code>/* ---[ Improvement #1: pd ]--- */</code></h4>
<p>An improvement on that is a small bash function that I <a href="http://unix.stackexchange.com/questions/31161/quick-directory-navigation-in-the-terminal">found on stackexchange</a>:</p>
<div class="precode"><pre><code>function pd() {
if [ "$1" ]; then
pushd "${1/#[0-9]*/+$1}";
else
pushd;
fi > /dev/null
}
</code></pre></div>
<p>which simplifies using <code class="so">pushd</code>. A basic session of use would be:</p>
<div class="precode"><pre><code>midpeter444:~/lang/clojure/concurrency-fun$ pd .
midpeter444:~/lang/clojure/concurrency-fun$ dirs
0 ~/lang/clojure/concurrency-fun
1 ~/lang/clojure/concurrency-fun
midpeter444:~/lang/clojure/concurrency-fun$ cd ~/.mozilla/
midpeter444:~/.mozilla$ dirs
0 ~/.mozilla
1 ~/lang/clojure/concurrency-fun
midpeter444:~/.mozilla$ pd .
midpeter444:~/.mozilla$ cd /tmp
midpeter444:/tmp$ dirs
0 /tmp
1 ~/.mozilla
2 ~/lang/clojure/concurrency-fun
midpeter444:/tmp$ pd 2
midpeter444:~/lang/clojure/concurrency-fun$
</code></pre></div>
<p>pd can take either a dot, which means "remember this directory" or a number which refers to the position on the dirs history list. The random-access list metaphor is easier to work with the the <code class="so">pushd</code> stack-based metaphor.</p>
<p><br /></p>
<h4><code>/* ---[ Vast Improvement #2: z ]--- */</code></h4>
<p>But recently I discovered rupa/z or "z" and now I only occasionally use <code class="so">pd</code> anymore. <strong>z is the biggest change and improvement to my command line life in years.</strong> I really love it. It works with cygwin as well for my time on Windows machines in my day job.</p>
<p>If you use the command line much, go get it now: <a href='https://github.com/rupa/z'>https://github.com/rupa/z</a></p>
<p>What is it?</p>
<p>First it is <strong>not</strong> z-shell (I'm a bash user), which is what I thought initially. (It doesn't help that the main GitHub page for it starts with "ZSH USERS BACKWARD COMPATIBILITY WARNING").</p>
<p>What it is, is a 200-line shell script compatible with bash and z-shell that is basically a clever LRU-type cache of your directory visitations - the cache weighting is based on both frequency and recentness, which the author dubs "frecency". As you navigate around to different directories, it keeps track of where you've been, how often you've been there and how recently.</p>
<p>To see your current cache in ascending order of 'frecency', just type <code class="so">z</code>:</p>
<div class="precode"><pre><code>midpeter444:~$ z
0.313808 /home/midpeter444/apps/apache-ant-1.8.4/bin
0.313808 /home/midpeter444/lang/clojure/books/land-of-lisp/wizards-adventure/doc
0.313808 /home/midpeter444/lang/java/projects/mybatis-koans
0.392263 /tmp
0.429067 /home/midpeter444/lang/clojure/source-code
0.627622 /home/midpeter444/lang/lisp
0.784525 /home/midpeter444/.mozilla/firefox
0.83702 /home/midpeter444/lang/clojure/projects/clj-how-tos/clj-sockets
0.86298 /home/midpeter444/media/ebooks
1.62 /home/midpeter444/Dropbox/scripts-and-config-files
2.32335 /home/midpeter444/lang/clojure/sandbox/src/sandbox
5.6486 /home/midpeter444/lang/clojure/books/land-of-lisp/wizards-adventure
8.54205 /home/midpeter444/lang/clojure/books/land-of-lisp/orc-battle
10.7351 /home/midpeter444/lang/clojure/projects/clj-how-tos/clj-sockets
20.9559 /home/midpeter444/lang/clojure/books/land-of-lisp
30.7926 /home/midpeter444/lang/clojure/books/land-of-lisp/webserver
32.099 /home/midpeter444/Downloads
192.24 /home/midpeter444/lang/clojure/concurrency-fun
</code></pre></div>
<p>The number on left indicates the frecency score. So ambiguous entries will resolve in favor of the one with the higher score.</p>
<p>To navigate somewhere you've been, pass a part of the path to the z command:</p>
<div class="precode"><pre><code>midpeter444:~$ z fun
midpeter444:~/lang/clojure/concurrency-fun$
midpeter444:~$ z lisp
midpeter444:~/lang/clojure/books/land-of-lisp/webserver$
midpeter444:~$ z moz
midpeter444:~/.mozilla$
</code></pre></div>
<p>It also has tab-completion. If I hit tab for the example above where I typed <code class="so">moz</code> it expands to:</p>
<div class="precode"><pre><code>$ z /home/midpeter444/.mozilla
</code></pre></div>
<p>Now the only part of the command line usage I once found irritating is pure joy.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com0tag:blogger.com,1999:blog-2977002084155733470.post-16135222679004240102012-12-15T16:43:00.000-05:002012-12-15T16:48:25.934-05:00Programming Praxis Amazon Interview Question, part 2<p>In <a href="http://thornydev.blogspot.com/2012/12/programming-praxis-would-amazon-hire-me.html">part 1 of this blog entry</a> I covered two relatively efficient implementations of an algorithm to keep the top N entries in a stream of points that came from the <a href="http://programmingpraxis.com/2012/11/27/amazon-interview-question/">Programming Praxis</a> web site:</p>
<blockquote class="bordered">
Given a million points (x, y), give an O(n) solution to find the 100 points closest to (0, 0).
</blockquote>
<p>I was happy with my ad-hoc solution since it performed twice as fast as using a sorted-set data structure.</p>
<p>The answer chosen by the author of the Programming Praxis site used a <a href="http://www.csanimated.com/animation.php?t=Heap_(data_structure)">Heap data structure</a>, where the max value is kept at the top of the heap. His implementation for this exercise was a mutable heap, so it wasn't not a viable candidate for a Clojure implementation. However, he has links to other praxis challenges where he implemented heaps (in Scheme), some of which use immutable data structures. I chose to (manually) <a href="https://en.wikipedia.org/wiki/Source-to-source_compiler">transpile</a> his Scheme-based <a href="http://programmingpraxis.com/2009/05/05/priority-queues/">"Leftist heap"</a>:</p>
<script src="https://gist.github.com/4299232.js"></script>
<p>This is only one implementation of a heap and there might be (probably is) one that is more efficient, but I chose this as a representative to see how it would compare to the other solutions.</p>
<p>Here is my implementation of the "top 100" challenge using the Leftist Priority Queue Heap:</p>
<script src="https://gist.github.com/4299281.js"></script>
<p>The Priority Queue does not keep track of its size and I didn't want to modify the data structure to do that. To compensate, I used the Clojure <code class="so">split-at</code> function to split the points vector into two lazy-seqs: the first <code class="so">max-size</code> entries from the <code class="so">points</code> vector, which are just directly inserted into the heap and the rest.</p>
<p>Those remaining points then have to be sifted: if a point's distance from the origin is less than the first element on the heap, then that top entry on the heap needs to be pulled off and the new point is inserted. That is done with the code:</p>
<div class="precode"><pre><code>(q/pq-insert dist-lt? pt (q/pq-rest dist-lt? pq))
</code></pre></div>
<p><code class="so">pq-rest</code> is like Clojure's <code class="so">pop</code> - it gives you the data structure minus its head and we insert the new point into that remaining data structure.</p>
<p>The <code class="so">dist-lt?</code> function is a comparator function required by the Leftist Heap algorithm.</p>
<p>I did this additional exercise, because I suspected that a heap would a more efficient implementation that a fully sorted-set.</p>
<p>Here are some representative benchmark results again using the Clojure criterium tool. (This time I truncated some of the output to make it easier to read.)</p>
<div class="precode"><pre><code>user=> (def points (shuffle (for [x (range 500) y (range 200)] [x y])))
#'user/points
user=> (count points)
100000
;; this is the "ad-hoc" solution from part 1
user=> (bench (topN points 100))
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 525.526800 ms
;; this is the sorted-set solution from part 1
user=> (bench (topNSS points 100))
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 1.250241 sec
;; this is the new heap-based implementation
user=> (bench (top-heap points 100))
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 1.063965 sec
</code></pre></div>
<p>I've only shown three results, but I ran them many times in varied order and got remarkably consistent results.</p>
<p>So without going into specific precision, the heap-based implementation is about 20% faster than the sorted-set implementation and my ad-hoc solution is about 50% faster than the heap-based implementation.</p>
<p>Which is about what I expected. I thought the heap-based solution might even be a little faster than this. One problem with the heap implementation I'm using is that it's central function (<code class="so">merge</code>) uses true recursion. I didn't see an easy way to make it use loop-recur or a lazy-seq. If anyone sees a clever way to do that, I'd love to hear it.</p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com0tag:blogger.com,1999:blog-2977002084155733470.post-36372244191142817172012-12-14T18:57:00.000-05:002012-12-16T09:58:46.382-05:00Programming Praxis - Would Amazon hire me?<p>I was finishing up my work for the day and decided to check <a href="https://news.ycombinator.com/">Hacker News</a>. High on the list that day was <a href="http://programmingpraxis.com/">Programming Praxis</a>, which I'd never seen before and the featured post was the following <a href="http://programmingpraxis.com/2012/11/27/amazon-interview-question/">Amazon interview question</a>:</p>
<blockquote class="bordered">
Given a million points (x, y), give an O(n) solution to find the 100 points closest to (0, 0).
</blockquote>
<p>I had been planning to go home and start working on Dice of Doom (in Clojure) from Chapter 16 of Conrad Barski's <a href="http://landoflisp.com/">Land of Lisp</a>, but this problem sounded intriguing enough that I would take it up.</p>
<p>After sketching out a few ideas, I concluded that a strict O(n) solution isn't possible, but something near-O(n) would be feasible. Similar to how Clojure's persistent data structures often operate in "<a href="http://www.infoq.com/articles/in-depth-look-clojure-collections#_ftnref">essentially constant</a>" time -- <code class="so">O(log-32 n)</code> being close enough to constant time to be considered basically a constant factor.</p>
<p>I decided to try an ad-hoc solution and then a sorted-set implementation. My guess was that the ad-hoc solution would be faster and that gave me a good excuse to try out Hugo Duncan's <a href="https://github.com/hugoduncan/criterium">criterium</a> benchmark tool to prove it (or prove me wrong).</p>
<p><br /></p>
<h4><code>/* ---[ The ad-hoc solution ]--- */</code></h4>
<p>The approach I decided upon was to use an unsorted hash-map with mixed keys.</p>
<p>One key <code class="so">:ct</code> would keep track of the count: how many entries ("points") were in the hashmap. It's max would the max-size (100 in the challenge statement).</p>
<p>The second key <code class="so">:hd</code>, short for highest distance, would keep track of the entry (or entries) with the farthest distance from the the center point.</p>
<p>The rest of the keys are integers representing the distance to the origin. This distance key is mapped to a vector of points. Each point is a tuple (vector) of the x and y coordinate.</p>
<p>I decided to interpret distance from (0,0) not as the square root of the sum of the squares of x and y, but rather the absolute value of x plus the absolute value of y, but it wouldn't be too hard to imagine this with the other distance formula.</p>
<p>So the data structure would look like this:</p>
<div class="precode"><pre><code>{:ct 4
:hd 7
0 [[0 0]]
2 [[1 1] [0 2]]
3 [[1 2] [0 3] [3 0]]
6 [[5 1]]
7 [[4 3]]}
</code></pre></div>
<p>In this example, the data structure has 7 points, 1 with distance 0, 2 with distance 2, and so on.</p>
<p>Based on showing you this data structure I probably don't need to describe the algorithm I'm going to use. Rob Pike's <a href="http://www.faqs.org/docs/artu/ch01s06.html#rule5">Rule 5</a> is: </p>
<blockquote class="bordered">
Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming
</blockquote>
<p>Or <a href="https://en.wikiquote.org/wiki/Fred_Brooks">Brooks' famous statement</a>: </p>
<blockquote class="bordered">
Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.
</blockquote>
<p>So now the fun is to implement this in Clojure's immutable data structures using nicely composed functions.</p>
<p>We know we have to iterate through all the input points - there's our O(n) cost without doing any thing else - and we want to end up with one data structure. Therefore, we'll use <code class="so">reduce</code>.</p>
<p>Even though the problem statement says the closest 100 points, for testing, I want to parameterize the max-size and what set of points I'll feed it, so the main function will look like this:</p>
<pre>
(def init-map {:hd Long/MIN_VALUE, :ct 0})
(defn topN [points max-size]
(reduce (mk-sift-fn max-size) init-map points))
</pre>
<p><code class="so">points</code> will be a collection or seq of x-y tuples and <code class="so">max-size</code> will indicate how many points the final data structure should retain. I pass max-size to a "make-sift-function", which is a higher-order function that will return the function that will "sift" through each point and determine whether it goes into the data structure and if so, where. A place for everything and everything in its place.</p>
<pre>
(defn mk-sift-fn [max-size]
(fn [m pt]
(let [dist (distance pt)]
(if (< (:ct m) max-size)
(add-point m dist pt)
(if (< dist (:hd m))
(-> m (remove-point (:hd m)) (add-point dist pt))
m)))))
</pre>
<p>The flow to the function returned by <code class="so">mk-sift-fn</code> is:</p>
<ul>
<li><p>if you haven't seen max-size entries yet, add it to the map (letting the <code class="so">add-point</code> fn figure out where to stick it)</p></li>
<li><p>if the data structure is at max capacity, then if the distance from (0,0) of the current point under consideration is less than the current <em>highest</em> distance in the map, then we have to remove one point that maps to the highest-point and add this new point.</p></li>
</ul>
<p>I use the <code class="so">-></code> threading macro to weave through the remove-point and add-point functions, allowing nice composition of the functions with immutable structures.</p>
<p>Here is the full implementation with all the helper methods:</p>
<script src="https://gist.github.com/4282769.js"></script>
<p>Here's an example run with a small data set:</p>
<div class="precode"><pre><code>user=> (require '[sandbox.top100 :refer [topN]] :reload)
nil
user=> (def points (shuffle (for [x (range 2 5) y (range 3)] [x y])))
#'user/points
user=> points
[[3 1] [3 0] [4 0] [2 2] [2 1] [3 2] [4 1] [4 2] [2 0]]
user=> (topN points 5)
{2 [[2 0]], 3 [[3 0] [2 1]], 4 [[4 0] [2 2]], :hd 4, :ct 5}
</code></pre></div>
<p><br /></p>
<h4><code>/* ---[ The sorted-set solution ]--- */</code></h4>
<p>Clojure's sorted-sets are binary (persistent) trees. The sort order I use for the sorted set is distance from (0,0) <em>descending</em>. </p>
<p>As before, we'll directly add the first <code class="so">max-size</code> entries we see. After that, we have to remove entries from the set if one with a shorter distance is seen.</p>
<p>Due to our sort order, the point with the greatest distance would be at the top of the tree and is easily removed in constant time using <code class="so">disj</code> when we find a point that is closer to the origin. However, we then have to add that new point to the sorted set and all of these additions average O(log-n) insertion time. I was pretty sure my ad-hoc solution would be more efficient overall because of this extra sort time for all elements that get added.</p>
<p>To define a sorting comparator in Clojure, you use the <code class="so">sorted-set-by</code> fn which takes a comparator of your choosing.</p>
<p>I stated above that the sort order would by distance descending, but since this is a sorted <em>set</em>, not a sorted list or vector, that won't actually work: </p>
<div class="precode"><pre><code>user=> (require '[sandbox.top100 :refer [distance]] :reload)
nil
user=> (defn by-dist [pt1 pt2]
#_=> (> (distance pt1) (distance pt2)))
#'user/by-dist
user=> points
[[3 1] [3 0] [4 0] [2 2] [2 1] [3 2] [4 1] [4 2] [2 0]]
user=> (apply sorted-set-by by-dist points)
#{[4 2] [3 2] [3 1] [3 0] [2 0]}
</code></pre></div>
<p>We lost some points in the set. We have <code class="so">[3 1]</code>, but not <code class="so">[4 0]</code>. Since these have the same "value" in the eyes of the set and a set can keep only one value, the other is dropped.</p>
<p>So I made the sort-by method to take into account equal distances and then do a secondary sort based on the value of the x coordinate, thus keeping all the points we are fed:</p>
<div class="precode"><pre><code>(defn dist-then-first [pt1 pt2]
(let [dist1 (distance pt1)
dist2 (distance pt2)]
(if (= dist1 dist2)
(> (first pt1) (first pt2))
(> dist1 dist2))))
</code></pre></div>
<p>As before I used reduce to iterate over all the input points. The overall solution is nicely shorter than the ad-hoc one:</p>
<script src="https://gist.github.com/4285360.js"></script>
<p><br /></p>
<h4><code>/* ---[ Performance showdown ]--- */</code></h4>
<p>At the Clojure Conj this year, I discovered Hugo Duncan's <a href="https://github.com/hugoduncan/criterium">criterium</a> benchmark tool, which gives you more robust benchmarks than simply using <code class="so">time</code>.</p>
<p>I used it to compare the solutions above. I redefined the points vector to have 100,000 points. I ran <code class="so">bench</code> twice (in the opposite order). The first time I kept the closest 6 points. The second time I kept the closest 100.</p>
<div class="precode"><pre><code>user=> (def points (shuffle (for [x (range 500) y (range 200)] [x y])))
#'user/points
user=> (count points)
100000
user=> (use 'criterium.core)
nil
user=> (bench (topNSS points 6))
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 1.022929 sec
Execution time std-deviation : 10.070356 ms
Execution time lower quantile : 1.006426 sec ( 2.5%)
Execution time upper quantile : 1.044943 sec (97.5%)
user=> (bench (topN points 6))
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 545.035140 ms
Execution time std-deviation : 4.335731 ms
Execution time lower quantile : 538.861529 ms ( 2.5%)
Execution time upper quantile : 554.198797 ms (97.5%)
user=> (bench (topN points 100))
Evaluation count : 120 in 60 samples of 2 calls.
Execution time mean : 531.174287 ms
Execution time std-deviation : 4.642063 ms
Execution time lower quantile : 522.942875 ms ( 2.5%)
Execution time upper quantile : 541.571260 ms (97.5%)
user=> (bench (topNSS points 100))
Evaluation count : 60 in 60 samples of 1 calls.
Execution time mean : 1.260036 sec
Execution time std-deviation : 15.670337 ms
Execution time lower quantile : 1.240810 sec ( 2.5%)
Execution time upper quantile : 1.292583 sec (97.5%)
</code></pre></div>
<p>Sweet! My ad-hoc solutions runs twice as fast for this dataset. In the end, it's a trade off between the more elegant code and performance, which is often the case.</p>
<hr />
<p><strong>[Updates]</strong> </p>
<ul>
<li>See <a href="http://thornydev.blogspot.com/2012/12/programming-praxis-amazon-interview.html">part 2</a> to compare another solution using a heap data structure.</li>
<li>The code for this exercise is now available on my GitHub account: <a href='https://github.com/midpeter444/clojure-qad/tree/master/top100'>https://github.com/midpeter444/clojure-qad/tree/master/top100</a></li>
</ul>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com1tag:blogger.com,1999:blog-2977002084155733470.post-26094179539673887722012-10-01T22:49:00.000-04:002012-10-01T22:49:52.628-04:00Reading user input from STDIN in Clojure<p>Recently I was working on a simple Clojure program where I need to read input from STDIN. I hadn't actually done this before, so I searched online and found others had similar questions, but had to cobble an answer together due to two issues:</p>
<ol>
<li><p>In most languages you use a while loop, check for some condition (or input) to be false in order to stop. Clojure actually has a while loop construct, but making it work seems tricky and likely involves mutable state. Paying the overhead of STM (Software Transactional Memory) in order to do a simple input loop, seems like excessive overkill.</p></li>
<li><p>When you try to read from STDIN using <code class="so">lein run</code>, it doesn't work. The input is ignored.</p></li>
</ol>
<p>So, here's what I have working that is reasonably idiomatic and concise.</p>
<p>In my code example, I want to read a user's input until they type in a sentinel value, which I chose to be <code class="so">:done</code>. Here I just echo the output back:</p>
<script src="https://gist.github.com/3815736.js?file=stdin.clj"></script>
<p>The trick to getting it work with with Leiningen (I'm using lein-2.0.0-preview10) is to use <code class="so">lein trampoline run</code>, rather than <code class="so">lein run</code>. The trampoline feature allows you to run your app in a separate JVM process rather than within the Leiningen process (as a child process). Running it as a child process somehow blocks STDIN input from being captured.</p>
<p>Example usage:</p>
<div class="precode"><pre><code>$ lein trampoline run -m example.stdin
Enter text:
First line
You entered: >>First line<<
Second line
You entered: >>Second line<<
Foo
You entered: >>Foo<<
:done
End
</code></pre></div>
<p>In all likelihood, you would want to capture and retain the input lines in a collection. To do that use an accumulator in your loop:</p>
<script src="https://gist.github.com/3815846.js?file=stdin-acc.clj"></script>
<p>Ideas on more idiomatic ways to do this in Clojure are welcome. </p>
Anonymoushttp://www.blogger.com/profile/14830786689829173576noreply@blogger.com1