Non-generic Map in Golang Efficiency

Question

I completely understand that Go doesn't provide support for Generics, opting instead for users to create their own type-specific methods when needed.

However, I am wondering if there is a more efficient way to make a specific map function over a data structure that does not involve looping through the entire list and applying the function, or is this what other languages with generics support do behind the scenes.

Example:

func map(list []string, op func(string)string) []string {
  ouput := make([]string, len(list))
  for i, v := range list {
    output[i] = op(v)
  }
  return output
}

Thanks!

Answer 1

FYI, map is a reserved word, so you can't make your function exactly as written with lowercase map.

That is probably as good as you can get. Generics don't get you around allocating new memory.

It is slightly faster to use append() rather than initializing the whole slice to empty strings at the beginning. For example:

func Map(list []string, op func(string) string) []string {
   output := make([]string, 0, len(list))
   for _, v := range list {
      output = append(output, op(v))
   }
   return output
}

This gave me about a 10% increase in speed.

Update: That was only true for very short slices. Here's a more thorough benchmark--it was actually slower to use append on longer slices. I also tried parallelizing it, which was only worth the overhead on much bigger slices.

Code: https://gist.github.com/8250514

Output (numbers at end of test names are slice lengths):

go test -bench=".*" -test.cpu=2
BenchmarkSliceMake10-2       5000000           473 ns/op
BenchmarkSliceMake100-2       500000          3637 ns/op
BenchmarkSliceMake1000-2       50000         43920 ns/op
BenchmarkSliceMake10000-2       5000        539743 ns/op
BenchmarkSliceAppend10-2     5000000           464 ns/op
BenchmarkSliceAppend100-2     500000          4303 ns/op
BenchmarkSliceAppend1000-2     50000         51172 ns/op
BenchmarkSliceAppend10000-2     5000        595650 ns/op
BenchmarkSlicePar10-2         500000          3784 ns/op
BenchmarkSlicePar100-2        200000          7940 ns/op
BenchmarkSlicePar1000-2        50000         50118 ns/op
BenchmarkSlicePar10000-2        5000        465540 ns/op

Answer 2

Yes, normally this is exactly the sort of thing that generics is used for. If you want, such functions can still be written in Go using reflection, although they're much slower. See, for example, my github.com/synful/illegal/generics package, which uses reflection to implement classic generic functions. I haven't actually benchmarked these, although I'd be very surprised if they were anywhere close to the performance of the type-specific implementation that you provided.

EDIT: Just for kicks, I copied Wes Freeman's first test, and ran it on my reflection-based Map. This was run on a fairly under-powered server, but still. The results speak for themselves (slowness is measured against Wes' results).

BenchmarkSliceMake10-2    200000         14091 ns/op [30.0x    slower]
BenchmarkSliceMake100-2    10000        112137 ns/op [30.83x   slower]
BenchmarkSliceMake1000-2    2000       1177498 ns/op [26.810x  slower]
BenchmarkSliceMake10000-2    100      11513085 ns/op [21.3307x slower]

Note: I used this test in particular because my implementation pre-allocates slices.