Bug in Go?

<p><a href="https://play.golang.org/p/gRMj9moIq8">Example</a> on play. Is this a bug in Go or wasn&#39;t I able to find the problem in my code? The version with <em>int</em> produces the expected result (permi). But the same algorithm with <em>byte</em> returns crap (permb).</p> <p>Edit: Problem solved, see explanation by <a href="/u/chewxy">/u/chewxy</a> - thanks for reviewing it.</p> <hr/>**评论：**<br/><br/>itsamemmario: <pre><p>I haven&#39;t read your code in detail, but seems like a problem concerning when your append allocates a new array, and how you handle your pointer to it.</p> <p>The append function realocates an array when it&#39;s size runs out, it seems like in your recursive function the caller holds the slice poiting to a different array than callee. </p> <p>I highly doubt this is a bug in go. But who knows, maybe you&#39;ve struck gold :P</p> <p>It might also be the type conversion you do in the bytes for loop int(i) &lt; len(list) ; i++</p> <p>Curious though. I&#39;ll see if i can dig a little deeper when I get off work.</p></pre>HectorJ: <pre><p>It has something to do with the re-use of the <code>result</code> slice indeed: <a href="https://play.golang.org/p/11f4UFsPF6" rel="nofollow">https://play.golang.org/p/11f4UFsPF6</a> works (I only added line 25)</p> <p>Not sure why the <code>int</code> implementation works though</p></pre>chewxy: <pre><p>Answer: size classes. </p> <p>When Go allocates objects it tries as hard as possible to allocate using a <a href="https://golang.org/src/runtime/sizeclasses.go">size class</a></p> <p>So, let&#39;s look at what happens in the <code>int</code> version:</p> <ol> <li>Loop 0: result is size 0. Allocate 8 bytes (int is 4 bytes in the playground). This means the underlying array is of length 2.</li> <li>Loop 1: result is size 2. Append simply adds to index 0. No reallocation necessary</li> <li>Loop 2: result is size 2. Append simply adds to [1]. No reallocation necessary</li> <li>Loop 3: result is size 2. Need to add one more, so reallocate array - 16 bytes this time. This makes the length 4. And so on and so forth.</li> </ol> <p>Now look at the <code>byte</code> version:</p> <ol> <li>Loop 0: result is size 0. Allocate 8 bytes. This means the underlying array is of length 8.</li> <li>Loop 1: result is size 8. No need to allocate, just add to the result. ... never needs to allocate, hence only 7 is added to it.</li> </ol> <p>I had originally written a slightly nastier comment earlier, because the algorithm is wrong. The <code>byte</code> example is the technically correct answer. </p> <p>If instead of passing in an empty slice, pass in a <code>make([]T, 0, 4)</code> and you can quite easily see where the algorithm goes wrong.</p></pre>HectorJ: <pre><p>Yep, that&#39;s it.</p> <p>I was debugging step-by-step and had just noticed the <code>cap</code> difference when I saw your answer.</p></pre>Chohmoh: <pre><p>Wow, size classes, nasty pitfall. Thanks for pointing it out, it&#39;s clear and logical, now.</p></pre>6_28: <pre><p>Just a side note, the inner loop is unnecessary and can be removed, and then the &#34;used&#34; slice is never used, so it can be removed as well.</p></pre>Chohmoh: <pre><p>Yes, you&#39;re right, thanks.</p></pre>