title: Using interfaces{} in slices seems to incur a 40x slowdown. Is there a way of bypassing this when implementing `interface{}` based datastructures?
body: <p>I am currently trying to implement a tree based datastructure in Go and I am seeing disappointing results in my benchmarking. Because I am trying to be generic as to what values I accept, I am limited to using <code>interface{}</code>.</p>
  
  <p>The code in question is an immutable vector trie. Essentially, any time a value in the vector is modified I need to make a copy of several nodes in the trie. Each of these nodes is implemented as a slice of const (known at compile time) length. For example, writing a value into a large trie will require the copying of 5 seperate 32 long slices. They must be copies to preserve the immutability of the previous contents.</p>
  
  <p>I believe the disappointing benchmark results are because I am storing my data  as <code>interface{}</code> in slices, which get created, copied and appended to often. To measure this I set up the following benchmark</p>
  
  <pre><code>package main
  
  import (
      "math/rand"
      "testing"
  )
  
  func BenchmarkMake10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          _ = make([]int, 10e6, 10e6)
      }
  }
  
  func BenchmarkMakePtr10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          _ = make([]*int, 10e6, 10e6)
      }
  }
  
  func BenchmarkMakeInterface10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          _ = make([]interface{}, 10e6, 10e6)
      }
  }
  
  func BenchmarkMakeInterfacePtr10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          _ = make([]interface{}, 10e6, 10e6)
      }
  }
  func BenchmarkAppend10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          slc := make([]int, 0, 0)
          for jj := 0; jj &lt; 10e6; jj++ {
              slc = append(slc, jj)
          }
      }
  }
  
  func BenchmarkAppendPtr10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          slc := make([]*int, 0, 0)
          for jj := 0; jj &lt; 10e6; jj++ {
              slc = append(slc, &amp;jj)
          }
      }
  }
  
  func BenchmarkAppendInterface10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          slc := make([]interface{}, 0, 0)
          for jj := 0; jj &lt; 10e6; jj++ {
              slc = append(slc, jj)
          }
      }
  }
  
  func BenchmarkAppendInterfacePtr10M(b *testing.B) {
      for ii := 0; ii &lt; b.N; ii++ {
          slc := make([]interface{}, 0, 0)
          for jj := 0; jj &lt; 10e6; jj++ {
              slc = append(slc, &amp;jj)
          }
      }
  }
  
  func BenchmarkSet(b *testing.B) {
      slc := make([]int, 10e6, 10e6)
      b.ResetTimer()
      for ii := 0; ii &lt; b.N; ii++ {
          slc[rand.Intn(10e6-1)] = 1
      }
  }
  
  func BenchmarkSetPtr(b *testing.B) {
      slc := make([]*int, 10e6, 10e6)
      b.ResetTimer()
      for ii := 0; ii &lt; b.N; ii++ {
          theInt := 1
          slc[rand.Intn(10e6-1)] = &amp;theInt
      }
  }
  
  func BenchmarkSetInterface(b *testing.B) {
      slc := make([]interface{}, 10e6, 10e6)
      b.ResetTimer()
      for ii := 0; ii &lt; b.N; ii++ {
          slc[rand.Intn(10e6-1)] = 1
      }
  }
  
  func BenchmarkSetInterfacePtr(b *testing.B) {
      slc := make([]interface{}, 10e6, 10e6)
      b.ResetTimer()
      for ii := 0; ii &lt; b.N; ii++ {
          theInt := 1
          slc[rand.Intn(10e6-1)] = &amp;theInt
      }
  }
  </code></pre>
  
  <p>which gives the following result</p>
  
  <pre><code>BenchmarkMake10M-4                       300       4962381 ns/op
  BenchmarkMakePtr10M-4                    100      10255522 ns/op
  BenchmarkMakeInterface10M-4              100      19788588 ns/op
  BenchmarkMakeInterfacePtr10M-4           100      19850682 ns/op
  BenchmarkAppend10M-4                      20      67090711 ns/op
  BenchmarkAppendPtr10M-4                    1    2784300818 ns/op
  BenchmarkAppendInterface10M-4              1    3457503833 ns/op
  BenchmarkAppendInterfacePtr10M-4           1    3532502711 ns/op
  BenchmarkSet-4                      30000000            43.5 ns/op
  BenchmarkSetPtr-4                   20000000            91.2 ns/op
  BenchmarkSetInterface-4             30000000            43.5 ns/op
  BenchmarkSetInterfacePtr-4          20000000            70.9 ns/op
  </code></pre>
  
  <p>Where the difference on Set and Make seems to be about 2-4x but the difference on Append is about 40x.</p>
  
  <p>From what I understand the performance hit is because behind the scenes interfaces are implemented as pointers, and that pointers must be allocated on the heap. That still doesn't explain why Append is significantly worse than the difference between Set or Make.</p>
  
  <p>Is there a way in the current language of Go without using a code generation tool (e.g., a generics tool that lets the consumer of the library generate a version of the library to store <code>FooType</code>) to work around this 40x performance hit? Alternatively, have I made some error in my benchmarking?</p>