<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by George Papadrosou on Medium]]></title>
        <description><![CDATA[Stories by George Papadrosou on Medium]]></description>
        <link>https://medium.com/@giorgosp?source=rss-5e664ebeff51------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*NRibP8BcNuM9y4-2le3aSQ.jpeg</url>
            <title>Stories by George Papadrosou on Medium</title>
            <link>https://medium.com/@giorgosp?source=rss-5e664ebeff51------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 04:05:16 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@giorgosp/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Optimizing parallel Mergesort with Go tools]]></title>
            <link>https://medium.com/@giorgosp/optimizing-parallel-mergesort-with-golang-tools-ffca702f1e30?source=rss-5e664ebeff51------2</link>
            <guid isPermaLink="false">https://medium.com/p/ffca702f1e30</guid>
            <category><![CDATA[merge-sort]]></category>
            <category><![CDATA[concurrency]]></category>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[golang]]></category>
            <dc:creator><![CDATA[George Papadrosou]]></dc:creator>
            <pubDate>Sat, 04 Apr 2020 14:06:09 GMT</pubDate>
            <atom:updated>2020-04-07T21:02:13.850Z</atom:updated>
            <content:encoded><![CDATA[<h3>Optimizing parallel Merge Sort with Go tools</h3><p>In a <a href="https://medium.com/@giopap/sequential-and-parallel-merge-sort-in-go-74881e92a609">previous post</a>, I wrote a <a href="https://medium.com/@giopap/sequential-and-parallel-merge-sort-in-go-74881e92a609">sequential and a parallel implementation of the Merge Sort algorithm</a>. The parallel implementation was faster, but it was based on my intuition. This time, I try to further optimize it using pprof and the trace tool that Go provides.</p><p>The current parallel implementation tries to bound the number of active goroutines to the number of available processors. We will use it as a baseline for our optimizations.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/06360e2f5e20c48c60c1677e170bfcb6/href">https://medium.com/media/06360e2f5e20c48c60c1677e170bfcb6/href</a></iframe><p>Let’s use pprof to see what our program spends more time on. All benchmarks use an input array of 16 million elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/989/1*qcYiPlwK1ILKpAn7_rOU9g.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/925/1*NqGPzn-BuZF4pasJ7GTy-g.png" /></figure><p>merge() dominates the runtime as we would probably expect. But the implementation also spends too much time juggling with memory. This happens due to these lines:</p><pre>left := make([]<strong>int64</strong>, mid)<br>right := make([]<strong>int64</strong>, len(src)-mid)<br>copy(left, src[:mid])<br>copy(right, src[mid:])</pre><p>They create copies of the left and right part of src before passing them to mergesort(), so that merge() can safely merge them back into the original array.</p><p>We get rid of them by allocating a large temparray once and pass it to merge() . Merge results are then first written to temp and then copied to src, which is our original array. Here is the diff:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/850/1*ffQyuk0l1SXl5kaIljSyeA.png" /></figure><p>Now we only allocate one extra array and copy memory once per merge operation. Let’s run the benchmark again:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/984/1*TLN1x5s_SNGcufp98yvGFw.png" /></figure><p>And compare it with the previous one:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/866/1*S4KOPLOYsdXMV0Ie7kYuLQ.png" /></figure><p>The program now runs much faster and uses a lot less memory! Let’s see pprof:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/924/1*5F_g8Gh3VxeHQHWb7HA0XQ.png" /></figure><p>Clearly less time is spent allocating and moving memory. Τhe flat and cumulative times of runtime.memmove and runtime.mallocgc have decreased by about 50%, as we would expect. merge()expectedly takes more time, since it now has to copy the results from temp to src .</p><p>Now, let’s use the tracetool to check what our goroutines are doing and how they utilize the available processors.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/885/1*4-pe5MDCsLifL1acQwGV3Q.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3gbZBMmsWbrIVQs-xlfU1A.png" /></figure><p>Let’s see the first trace:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MTRCeSdir_eIYyTX3IvsPQ.png" /></figure><p>The first thing we can notice is the gaps. These gaps are time slices when our code doesn’t run. This is not what we want as we don’t fully utilize our processing power. But why do we have these gaps?</p><p>Let’s zoom in a bit and enable all flow events, so we can see how our goroutines are related with each other (a goroutine may spawn or unblock another goroutine).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*fP7NGCI-YU2Ul6GWc4ja4g.png" /></figure><p>Let’s observe the goroutine G23 (light blue) in the middle of the image. It spawns some goroutines that run on the same processor, but it also creates and waits for a new one, G2473, that runs on another processor. By clicking on G23 near its end, we see its end stack trace. It is blocked on the WaitGroup, as it waits for G2473 to finish. Given that the current implementation limits the number of alive goroutines to the number of processors, this is a problem. We want all scheduled goroutines to run in parallel and not wait on any other.</p><p>There is also another issue. There are many goroutines that run for too little time, even less than the go scheduler. We can confirm this by looking at the goroutine analysis screen, by scrolling down and looking at the goroutines with the smaller run time.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*DESX9_vvOK963lISNXT13A.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*OjczOy-Av0w38i2wWrvEAw.png" /></figure><p>Let’s address these bottlenecks by first eliminating the very small goroutines. The problem is in this area:</p><pre>func mergesort(src, temp []<strong>int64</strong>, semChan chan struct{}) {<br>    if len(src) &lt;= 1 {<br>       return<br>    }</pre><p>Our program may create new goroutines even with 1 element. We need to use a bigger cutoff here and resort to sequential sort if the input is small enough. But how small? In the below image, you can see the comparison of different cutoff values that I have benchmarked. All cutoff implementations outperform our previous one, which validates our “cutoff” idea.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*pViHWet0pQcP9yqDhbD5Bw.png" /></figure><p>On my machine and for 16 million of elements to sort, a cutoff of 10000 elements has the best results (combining the runtime and the memory improvements). Generally, <strong>we should run all the benchmarks for various input array sizes </strong>so that we don’t overfit our implementation to the input. However, I am skipping this now as the post is big already.</p><p>So here is the change. If the input array doesn’t have more elements than the cutoff number, we fall back to the built-in sequential sort.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/913/1*35bjVHuqsv0cXrHWuS8joQ.png" /></figure><p>Let’s examine the new trace. Because our program runs faster now, Go has run our benchmark more times, one with b.N=1 and one with b.N=2. That’s why we can distinguish 3 sections in the trace below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*24xBEVt9P3uQjm0GnX9hug.png" /></figure><p>Let’s just zoom in the middle section and see what we get:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*MMF3ifPhZEwuR1o-b8EJ-w.png" /></figure><p>We don’t have so many small goroutines as before. The goroutine analysis page also confirms it. No goroutines run for less than the scheduler wait time (3rd column from the right).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-y2nJLXzypKeMwN-E0KjRw.png" /></figure><p>Now let’s tackle the other bottleneck, that goroutines block on each other. A solution would be do give our processors more work with more goroutines. But how many?</p><p>We will have to benchmark. First, let’s just give it double our processors. On my machine this would be 16 goroutines.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/882/1*HlMOumet_AqGu33Aqtf-0A.png" /></figure><p>Let’s benchmark this change:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*HKqgbk7jpUyc2weDnQdR3Q.png" /></figure><p>So we got another ~16% improvement in the run time. Let’s see the new trace:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wmiZNBir8ZNg1XPtFnQg7A.png" /></figure><p>That’s much much better! There are are still some gaps where our code does not run. Let’s check the Synchronization blocking profile that the trace UI provides:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jfSXQhdYhIPJO2GUFKDZcg.png" /></figure><p>As expected, the program spends a lot of time waiting on a WaitGroup. There is no way (to my knowledge) to get rid of this with this algorithm, since some of our goroutines must wait for the others to finish. A lot of time is also spend reading from the channel that is used to limit the number of alive goroutines.</p><p>We can remove this constraint and let our program create as many goroutines as it needs. It probably seems like a bad idea as it would put a lot of stress on the Go scheduler. But we need to validate our hypothesis. Here is the diff:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/904/1*4Y9LmRjvsPjVDDlzMSrJeQ.png" /></figure><p>We get rid of the semaphore channel and just spawn a new goroutine for every “left” input. Comparing its benchmark with the previous once:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*38LfC0rgXRkC6JcRDjTm6A.png" /></figure><p>It’s actually faster! Let’s see the trace:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VrzPa63NM6kFI9h_Fr86IA.png" /></figure><p>Beautiful isn’t it? And we need to zoom a lot to find any gaps, which are negligible too.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*L_964mttP2TwBQZDgNq30w.png" /></figure><p>We could say at this point that the job is done. Except, we need to clarify one more thing: Why our program is faster since we create more goroutines?</p><p>Checking the Goroutines analysis UI of the trace, we only create ~6k goroutines for an input of 16 million elements.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/911/1*7SiGAT27CgfP0u1OBVhy9w.png" /></figure><p>This is due to our fallback to sequential sorting when the array contains less than 10k elements. If we remove that fallback, the program will create millions of goroutines and it will perform badly indeed.</p><p>This last image shows the comparison between the sequential mergesort, our baseline “intuitive” parallel implementation and our final one, for an input array of 16 million 64bit integers:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/981/1*Fi4zEiGuk98QfCh9HrUGbA.png" /></figure><p>Our optimized parallel implementation is ~2x faster than our baseline parallel one, and ~4.8x faster than the sequential.</p><p><strong>Conclusion</strong></p><p>Benchmarking and profiling is necessary to validate our thoughts and changes about performance improvements. Go makes this quite easy by providing not only a built-in framework for benchmarks, but also tools to profile and trace the execution of our programs. Sometimes, understanding the output of the tools and trying to find the root cause is tricky and challenging, but this is when we learn.</p><p>The code is on <a href="https://github.com/giorgosp/mergesort">Github,</a> with separate branches for every optimization step in case you want to reproduce the results.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ffca702f1e30" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Sequential and Parallel Merge Sort in Go]]></title>
            <link>https://medium.com/@giorgosp/sequential-and-parallel-merge-sort-in-go-74881e92a609?source=rss-5e664ebeff51------2</link>
            <guid isPermaLink="false">https://medium.com/p/74881e92a609</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[golang]]></category>
            <dc:creator><![CDATA[George Papadrosou]]></dc:creator>
            <pubDate>Sun, 29 Sep 2019 22:40:14 GMT</pubDate>
            <atom:updated>2020-04-07T18:29:39.481Z</atom:updated>
            <content:encoded><![CDATA[<p>Recently, I stumbled upon the <a href="https://github.com/pingcap/talent-plan">PingCAP talent-plan</a>, which is “a series of training courses about writing distributed systems in Go and Rust”. Having started learning Go recently, I decided to start with the <a href="https://github.com/pingcap/talent-plan/tree/master/tidb">“Distributed systems in Go”</a> course, where the <a href="https://github.com/pingcap/talent-plan/tree/master/tidb/mergesort">first project</a> is to implement the merge sort algorithm to sort 16 million 64 bit integers.</p><p>The project requirements are:</p><ul><li>Pass the provided unit test.</li><li>Make it perform better than sort.Slice().</li><li>Have a document to describe your idea and record the process of performance optimization with pprof.</li><li>Have a good code style.</li></ul><p>In this post we will just see two implementations of merge sort, a sequential and a parallel (actually concurrent) one. These implementations will be completely unoptimized. <a href="https://medium.com/@giorgosp/optimizing-parallel-mergesort-with-golang-tools-ffca702f1e30">In the next post, we will use the parallel implementation as a baseline for further optimizations.</a></p><h3>What is merge sort?</h3><p>Merge sort is a divide and conquer algorithm that sorts the input array by breaking it into subarrays until they have 1 element, and then merging the results back into a sorted array. The time and space complexities are O(NlogN) and O(n) respectively. We won’t go into details of the asymptotic analysis as there are many great resources about it online.</p><h3>Sequential implementation</h3><p>We can easily implement merge sort using a recursive function. The function splits the array in half, calls itself for each of the subarrays and then merges the resulting arrays in ascending order.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c3cd2c60a1dd965751f8d55beb311355/href">https://medium.com/media/c3cd2c60a1dd965751f8d55beb311355/href</a></iframe><p>The merge function compares the elements of the two input arrays and writes them in sorted order to the result array (which is the input to Mergesort). When it finishes traversing one of the two inputs, it appends the remaining elements of the other to the result.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/42097f6e197f3d151b58c911e8dbbf53/href">https://medium.com/media/42097f6e197f3d151b58c911e8dbbf53/href</a></iframe><p>Running the provided test suite verifies our implementation:</p><pre>&gt; make test<br>go test<br>OK: 1 passed<br>PASS<br>ok   pingcap/talentplan/tidb/mergesort 1.288s</pre><p>We won’t do any profiling in this post but will just write a “parallel” implementation and just run a benchmark to ensure it is faster than the sequential one. We will improve it in <a href="https://medium.com/@giorgosp/optimizing-parallel-mergesort-with-golang-tools-ffca702f1e30">the second post with the pprof and trace tools.</a></p><h3>Parallel implementation</h3><p>An optimization for our solution would be to take advantage of multiple processors and use multiple goroutines to parallelize the execution of <em>some </em>Merge calls. We could say that, since our task is CPU-bound, we want to limit the max number of goroutines running in parallel to equal the number of available processors. Creating more goroutines may even make our program slower, since the Go scheduler will run more and our program less.</p><p>To limit the number of simultaneous goroutines, we can use a <strong>buffered channel</strong> as a <strong>semaphore</strong>. Writing to a full buffered channel will block and will block us (:D) from creating extra goroutines we cannot utilize. Mergesort() will spawn a new goroutine to sort the left subarray but will sort the right subarray itself, while it waits for the other to finish.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/6c58953e68a2d8c3363349de1f189f1b/href">https://medium.com/media/6c58953e68a2d8c3363349de1f189f1b/href</a></iframe><p>Running the provided benchmark suite shows us a ~2.5x improvement over the builtin sort.</p><pre>&gt; make bench<br>go test -bench Benchmark -run xx -count 5 -benchmem<br>goos: linux<br>goarch: amd64<br>pkg: pingcap/talentplan/tidb/mergesort<br>BenchmarkMergeSortParallel-8 1 1334344722 ns/op 3489690688 B/op 50331744 allocs/op<br>BenchmarkMergeSortParallel-8 1 1371397711 ns/op 3489701856 B/op 50331783 allocs/op<br>BenchmarkMergeSortParallel-8 1 1386620551 ns/op 3489690272 B/op 50331746 allocs/op<br>BenchmarkMergeSortParallel-8 1 1350215546 ns/op 3489668848 B/op 50331694 allocs/op<br>BenchmarkMergeSortParallel-8 1 1325400066 ns/op 3489662752 B/op 50331657 allocs/op<br>BenchmarkNormalSort-8 1 3325640673 ns/op 64 B/op 2 allocs/op<br>BenchmarkNormalSort-8 1 3318650150 ns/op 64 B/op 2 allocs/op<br>BenchmarkNormalSort-8 1 3317344986 ns/op 64 B/op 2 allocs/op<br>BenchmarkNormalSort-8 1 3309457091 ns/op 64 B/op 2 allocs/op<br>BenchmarkNormalSort-8 1 3303682084 ns/op 64 B/op 2 allocs/op<br>PASS<br>ok pingcap/talentplan/tidb/mergesort 27.938s</pre><p>While the parallel implementation is faster than the sequential one, it is still quite bad. After all, the sequential implementation ran one 1 processor while the parallel on 8. It is difficult to achieve linear speedup anyway, but for 8x the processing power we have to do something better than 2.5x speedup.</p><p>Also, someone could say we were lucky. We should not rely on intuition for performance but use benchmarks and available tools. So in the <a href="https://medium.com/@giorgosp/optimizing-parallel-mergesort-with-golang-tools-ffca702f1e30">next post, I use this parallel implementation as a baseline and try to improve it using the </a><a href="https://medium.com/@giorgosp/optimizing-parallel-mergesort-with-golang-tools-ffca702f1e30">pprof and </a><a href="https://medium.com/@giorgosp/optimizing-parallel-mergesort-with-golang-tools-ffca702f1e30">trace tools that Go provides.</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=74881e92a609" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>