optimize range over []byte(string)

[FrankReh]

The current system works but enlists an allocation and memcopy.

As it stands, there is already a mechanism enlisting unsafe and reflect used in the wild for converting a string to a byte slice without the allocation and copy. And the support by tinygo for unsafe and reflect already makes it work. See the example further down.

A function performing the range:

func rangeStringAsBytes(s string) {
	for _, b := range []byte(s) {
		save += b
	}
}

is compiled by tinygo to this wasm function (note the call to runtime_stringToBytes):

function rangeStringAsBytes() {
  var e:int;
  var a:int = stack_pointer - 16;
  stack_pointer = a;
  a[1]:long@4 = 1L;
  var b:int = 0;
  var d:int = 99548[0]:int;
  99548[0]:int = a;
  a[0]:int = d;

  (a + 8)[0]:int = (e = runtime_stringToBytes(85512, 35));

  var c:int = 101304[0]:ubyte;
  loop L_a {
    if (b == 35) {
      101304[0]:byte = c;
      99548[0]:int = d;
      stack_pointer = a + 16;
    } else {
      c = (b + e)[0]:ubyte + c;
      b = b + 1;
      continue L_a;
    }
  }
}

A lead go developer provided a solution using unsafe and reflect. This already works with tinygo.

This idea was fleshed out a bit in
https://stackoverflow.com/questions/59209493/how-to-use-unsafe-get-a-byte-slice-from-a-string-without-memory-copy .
The comments by two go developers are here:
https://groups.google.com/g/golang-nuts/c/Zsfk-VMd_fU/m/O1ru4fO-BgAJ

func unsafeGetBytes(s string) []byte {
	return (*[0x7fff0000]byte)(unsafe.Pointer(
		(*reflect.StringHeader)(unsafe.Pointer(&s)).Data),
	)[:len(s):len(s)]
}

// As in

func rangeUnsafeStringAsBytes(s string) {
	for _, b := range unsafeGetBytes(s) {
		save += b
	}
}

Some benchmarks showing bytes, strings, and manual/unsafe conversions between the two. Starred are the relevant results for this issue.

tinygo/wasm running in nodejs on older mac:
BenchmarkRangeBytes
BenchmarkRangeBytes              	83960235	        14.45 ns/op *
BenchmarkRangeBytes              	82679247	        14.36 ns/op
BenchmarkRangeBytes              	83991829	        14.38 ns/op
BenchmarkRangeStringAsBytes
BenchmarkRangeStringAsBytes      	15033096	        79.55 ns/op *
BenchmarkRangeStringAsBytes      	14958260	        79.64 ns/op
BenchmarkRangeStringAsBytes      	14833155	        79.80 ns/op
BenchmarkRangeUnsafeStringAsBytes
BenchmarkRangeUnsafeStringAsBytes	83963244	        14.51 ns/op *
BenchmarkRangeUnsafeStringAsBytes	81523156	        14.43 ns/op
BenchmarkRangeUnsafeStringAsBytes	83891115	        14.51 ns/op
BenchmarkMapStringLookup
BenchmarkMapStringLookup         	15326641	        78.12 ns/op
BenchmarkMapStringLookup         	15441502	        79.49 ns/op
BenchmarkMapStringLookup         	15446286	        77.92 ns/op
BenchmarkMapBytesLookup
BenchmarkMapBytesLookup          	 8191792	       144.5 ns/op
BenchmarkMapBytesLookup          	 8333955	       143.1 ns/op
BenchmarkMapBytesLookup          	 8344280	       142.8 ns/op
BenchmarkMapUnsafeBytesLookup
BenchmarkMapUnsafeBytesLookup    	15252482	        78.89 ns/op
BenchmarkMapUnsafeBytesLookup    	14966283	        79.39 ns/op
BenchmarkMapUnsafeBytesLookup    	15070021	        79.89 ns/op

The code for this benchmark can be found in issue #2699

[dgryski]

Because the created slice has no name, it can't be modified within the bounds of the loop. I'm pretty sure I can do this one without too much trouble.

[FrankReh]

I ran into another optimization in Tinygo that already does this for the Write case.

tinygo/transform/rtcalls.go

Lines 12 to 18 in 3883550

	// OptimizeStringToBytes transforms runtime.stringToBytes(...) calls into const
	// []byte slices whenever possible. This optimizes the following pattern:
	//
	// w.Write([]byte("foo"))
	//
	// where Write does not store to the slice.
	func OptimizeStringToBytes(mod llvm.Module) {

[eliasnaur]

FWIW, I just hit this in the form of a very surprising allocation by strconv.ParseUint:

$ cat byteslicegarbage_test.go
package byteslicegarbage

import (
	"strconv"
	"testing"
)

func TestAllocs(t *testing.T) {
	var v uint64
	res := testing.Benchmark(func(b *testing.B) {
		for range b.N {
			v, _ = strconv.ParseUint("10", 10, 64)
		}
	})
	if v != 10 {
		t.Fatal("ParseUint")
	}
	if a := res.AllocsPerOp(); a != 0 {
		t.Errorf("ParseUint allocates %d, expected none", a)
	}
}
$ go test
PASS
ok  	blah	1.815s
$ tinygo test
--- FAIL: TestAllocs (2.06s)
    ParseUint allocates 1, expected none
FAIL
FAIL	blah	2.270s

@dgryski do you have any notes for how to implement this optimization?

[dgryski]

We probably need to detect this at a higher level and not rely on the curent string-to-slice logic in the case where we're immediately ranging over it otherwise discarding the result.

[dgryski]

Not sure Go's SSA form gives us what we need:

~/go/src/github.com/dgryski/bug/convert $ ssadump -build F main.go
# Name: command-line-arguments.init
# Package: command-line-arguments
# Synthetic: package initializer
func init():
0:                                                                entry P:0 S:2
	t0 = *init$guard                                                   bool
	if t0 goto 2 else 1
1:                                                           init.start P:1 S:1
	*init$guard = true:bool
	jump 2
2:                                                            init.done P:2 S:0
	return

# Name: command-line-arguments.main
# Package: command-line-arguments
# Location: /Users/dgryski/go/src/github.com/dgryski/bug/convert/main.go:3:6
func main():
0:                                                                entry P:0 S:1
	t0 = convert []byte <- string ("hello, world":string)            []byte
	t1 = len(t0)                                                        int
	jump 1
1:                                                      rangeindex.loop P:2 S:2
	t2 = phi [0: -1:int, 2: t3]                                         int
	t3 = t2 + 1:int                                                     int
	t4 = t3 < t1                                                       bool
	if t4 goto 2 else 3
2:                                                      rangeindex.body P:1 S:1
	t5 = &t0[t3]                                                      *byte
	t6 = *t5                                                           byte
	t7 = println(t6)                                                     ()
	jump 1
3:                                                      rangeindex.done P:1 S:0
	return

We have no obvious indication that the conversion is happening in a range statement. Which means our logic in https://github.com/tinygo-org/tinygo/blob/release/transform/rtcalls.go#L18 needs to be tweaked.

[aykevl]

This should get fixed with #4523.

[dgryski]

Merged to dev. Tagging as next-release.