Repository: benhoyt/goawk
Pull request #99 (2022-02-03 19:26:49)

Optimize CONCAT(CONCAT(a, b), c)
Optimize CONCAT(CONCAT(a, b), c) reported in https://github.com/benhoyt/goawk/issues/91

Added a ConcatN opcode. Could have used MultiIndex opcode (I tried and it works
as is) but "concat" should not be using a separator.

benhoyt: Nice, and thank you! I'll take a closer look at this in the next few days.
benhoyt: Or maybe I'll get to it while the iron's hot. :-) Added a couple of review comments. Could you also please add the benchmark I mentioned and then post your before/after results of running all three benchmarks (ideally with `-count=5` and showing the diff using the benchstat tool). Thanks!
raff: Let me know if you want to go with a single Concat that supports 2+ parameters or keep 2 separate ones, given the benchmark results.

benhoyt: @raff Thanks for the updates. Yeah, I think having a separate ConcatN makes sense with those numbers. Maybe rename `Concat` to `Concat2`?

Could you also please post your before/after results for the other BenchmarkConcat benchmarks?
raff: Do you want Concat2 and ConcatN or Concat2 and Concat ?

I just figured out where to get benchstat, I'll post the before/after results in a bit.

Not sure of why when enabling/disabling the original concat I get a ~4% difference in ConcatSmall:

```
ConcatTwo-16             98.3ns ± 0%  84.0ns ± 6%  -14.58%  (p=0.008 n=5+5)
ConcatSmall-16            250ns ± 1%   259ns ± 2%   +3.91%  (p=0.008 n=5+5)
ConcatLarge-16            713µs ± 2%   712µs ± 5%     ~     (p=0.421 n=5+5)
```
 
benhoyt: Let's go with `Concat2` and `ConcatMulti`. Could you please rename `MultiIndex` to `IndexMulti` while you're at it, to be consistent with that ordering?
raff: This is the output of benchstat.sh. Not sure why there is a bunch of tests that every time I run it show up as slower than before (and completely unrelated to string concatenation):

```
name                     old time/op  new time/op   delta
ForInLoop-16             1.19µs ± 6%   1.33µs ± 2%  +11.44%  (p=0.008 n=5+5)
BuiltinGsub-16           12.6µs ± 0%   14.0µs ± 7%  +10.87%  (p=0.016 n=4+5)
BuiltinIndex-16           834ns ± 1%    904ns ± 3%   +8.31%  (p=0.008 n=5+5)
ForLoop-16               1.77µs ± 2%   1.92µs ± 7%   +8.24%  (p=0.016 n=5+5)
GlobalVars-16             200ns ± 6%    215ns ± 3%   +7.59%  (p=0.008 n=5+5)
BuiltinSplitRegex-16     68.6µs ± 0%   73.5µs ± 8%   +7.22%  (p=0.008 n=5+5)
LocalVars-16              221ns ± 5%    236ns ± 3%   +6.80%  (p=0.016 n=5+5)
BuiltinMatch-16          2.09µs ± 2%   2.21µs ± 4%   +5.82%  (p=0.016 n=5+5)
BinaryOperators-16        322ns ± 0%    341ns ± 1%   +5.74%  (p=0.008 n=5+5)
BuiltinSubAmpersand-16   10.5µs ± 1%   11.0µs ± 5%   +5.15%  (p=0.008 n=5+5)
BuiltinSubstr-16          568ns ± 1%    597ns ± 6%   +5.08%  (p=0.016 n=5+5)
IfStatement-16            107ns ± 1%    112ns ± 1%   +4.56%  (p=0.008 n=5+5)
CondExpr-16               106ns ± 2%    110ns ± 3%   +4.47%  (p=0.008 n=5+5)
BuiltinSub-16            10.6µs ± 1%   11.0µs ± 4%   +4.05%  (p=0.016 n=5+5)
ArrayOperations-16        434ns ± 1%    442ns ± 1%   +1.77%  (p=0.008 n=5+5)
Comparisons-16            245ns ± 0%    250ns ± 2%   +1.70%  (p=0.008 n=5+5)
AugAssign-16              755ns ± 1%    766ns ± 1%   +1.49%  (p=0.008 n=5+5)
IncrDecr-16               114ns ± 4%    110ns ± 7%     ~     (p=0.222 n=5+5)
SimpleBuiltins-16         595ns ± 6%    564ns ±11%     ~     (p=0.222 n=5+5)
BuiltinLength-16          334ns ± 2%    328ns ± 4%     ~     (p=0.278 n=5+5)
BuiltinSplitSpace-16     28.4µs ± 2%   28.7µs ± 6%     ~     (p=0.730 n=5+5)
BuiltinGsubAmpersand-16  12.8µs ± 2%   13.0µs ± 2%     ~     (p=0.095 n=5+5)
BuiltinSprintf-16        7.20µs ± 2%   7.23µs ± 4%     ~     (p=1.000 n=5+5)
RecursiveFunc-16         11.2µs ± 4%   11.3µs ± 6%     ~     (p=0.548 n=5+5)
FuncCall-16              1.99µs ± 1%   2.01µs ± 3%     ~     (p=0.690 n=5+5)
NativeFunc-16            8.08µs ± 2%   8.40µs ± 7%     ~     (p=0.056 n=5+5)
SimplePattern-16         97.8ns ± 3%  101.5ns ± 5%     ~     (p=0.151 n=5+5)
GetField-16               316ns ± 3%    319ns ± 4%     ~     (p=0.548 n=5+5)
SetField-16               640ns ± 0%    642ns ± 2%     ~     (p=0.730 n=4+5)
RegexMatch-16             856ns ± 0%    874ns ± 2%     ~     (p=0.111 n=4+5)
Assign-16                 202ns ± 2%    200ns ± 1%     ~     (p=0.341 n=5+5)
ConcatSmall-16            517ns ± 0%    263ns ± 4%  -49.15%  (p=0.008 n=5+5)
ConcatLarge-16           5.22ms ± 1%   0.71ms ± 1%  -86.46%  (p=0.008 n=5+5)
[Geo mean]               1.46µs        1.28µs       -12.52%
```
benhoyt: Yeah, benchmarks are funny sometimes. You have to run them on a quiet machine, and even then there can be fluctuation due to the compiler moving things around, or the x86 architecture being (too) clever. But here's what I'm seeing, and it's only split/sub that have slowed down a little, so I'm comfortable with this:

```
name                    old time/op  new time/op  delta
BuiltinSplitRegex-8     87.7µs ± 0%  94.7µs ± 9%   +7.98%  (p=0.008 n=5+5)
BuiltinSplitSpace-8     35.1µs ± 0%  37.6µs ± 0%   +7.10%  (p=0.008 n=5+5)
BuiltinGsubAmpersand-8  16.2µs ± 0%  17.3µs ± 6%   +6.56%  (p=0.008 n=5+5)
BuiltinSubAmpersand-8   13.6µs ± 0%  14.4µs ± 2%   +5.85%  (p=0.008 n=5+5)
BuiltinSub-8            13.6µs ± 0%  14.3µs ± 3%   +5.45%  (p=0.008 n=5+5)
BuiltinGsub-8           16.2µs ± 0%  16.6µs ± 0%   +2.38%  (p=0.016 n=5+4)
SetField-8               810ns ± 0%   829ns ± 1%   +2.33%  (p=0.008 n=5+5)
BuiltinMatch-8          2.71µs ± 1%  2.69µs ± 3%     ~     (p=0.635 n=5+5)
BuiltinSprintf-8        9.23µs ± 0%  9.27µs ± 1%     ~     (p=0.667 n=5+5)
RecursiveFunc-8         14.9µs ± 0%  14.7µs ± 1%   -1.21%  (p=0.008 n=5+5)
BinaryOperators-8        413ns ± 0%   407ns ± 1%   -1.67%  (p=0.008 n=5+5)
NativeFunc-8            10.8µs ± 0%  10.5µs ± 0%   -2.44%  (p=0.008 n=5+5)
FuncCall-8              2.76µs ± 2%  2.66µs ± 1%   -3.46%  (p=0.008 n=5+5)
CondExpr-8               151ns ± 0%   144ns ± 0%   -4.35%  (p=0.008 n=5+5)
GetField-8               435ns ± 2%   416ns ± 1%   -4.40%  (p=0.008 n=5+5)
IfStatement-8            152ns ± 0%   143ns ± 0%   -5.53%  (p=0.008 n=5+5)
SimpleBuiltins-8         746ns ± 0%   703ns ± 1%   -5.87%  (p=0.008 n=5+5)
RegexMatch-8            1.11µs ± 4%  1.05µs ± 3%   -5.89%  (p=0.032 n=5+5)
BuiltinIndex-8          1.11µs ± 1%  1.04µs ± 0%   -6.05%  (p=0.008 n=5+5)
AugAssign-8              982ns ± 0%   920ns ± 0%   -6.32%  (p=0.008 n=5+5)
ArrayOperations-8        565ns ± 0%   528ns ± 1%   -6.67%  (p=0.008 n=5+5)
SimplePattern-8          134ns ± 0%   125ns ± 1%   -6.69%  (p=0.008 n=5+5)
BuiltinLength-8          429ns ± 0%   400ns ± 2%   -6.70%  (p=0.008 n=5+5)
ForLoop-8               2.50µs ± 0%  2.33µs ± 3%   -6.78%  (p=0.008 n=5+5)
LocalVars-8              300ns ± 2%   279ns ± 1%   -6.93%  (p=0.008 n=5+5)
Comparisons-8            321ns ± 0%   298ns ± 0%   -7.27%  (p=0.029 n=4+4)
GlobalVars-8             269ns ± 1%   249ns ± 3%   -7.58%  (p=0.008 n=5+5)
Assign-8                 261ns ± 0%   240ns ± 1%   -7.76%  (p=0.008 n=5+5)
BuiltinSubstr-8          765ns ± 0%   705ns ± 1%   -7.92%  (p=0.008 n=5+5)
ForInLoop-8             1.78µs ± 4%  1.63µs ± 3%   -8.08%  (p=0.008 n=5+5)
IncrDecr-8               148ns ± 0%   136ns ± 1%   -8.22%  (p=0.016 n=4+5)
ConcatSmall-8            691ns ± 1%   341ns ± 3%  -50.72%  (p=0.008 n=5+5)
ConcatLarge-8           8.35ms ± 2%  1.10ms ± 3%  -86.88%  (p=0.008 n=5+5)
[Geo mean]              1.94µs       1.60µs       -17.75%
```
benhoyt: Thanks again for the contribution, much appreciated! I'll merge this shortly. Actually, looking at this diff now I think I'll revert `Concat2` back to just `Concat` like all the other binary ops (I'll do this after the merge, so don't worry).

Patch:
diff --git a/internal/compiler/compiler.go b/internal/compiler/compiler.go
index bdf8e43..f9a8374 100644
--- a/internal/compiler/compiler.go
+++ b/internal/compiler/compiler.go
@@ -633,6 +633,8 @@ func (c *compiler) expr(expr ast.Expr) {
 			c.expr(e.Right)
 			c.patchForward(mark)
 			c.add(Boolean)
+		case lexer.CONCAT:
+			c.concatOp(e)
 		default:
 			// All other binary expressions
 			c.expr(e.Left)
@@ -875,6 +877,36 @@ func (c *compiler) expr(expr ast.Expr) {
 	}
 }
 
+// Generate a Concat2 opcode or, if possible compact multiple `Concat2` into one `ConcatMulti`
+func (c *compiler) concatOp(expr *ast.BinaryExpr) {
+	var values []ast.Expr
+	for {
+		values = append(values, expr.Right)
+		left, isBinary := expr.Left.(*ast.BinaryExpr)
+		if !isBinary || left.Op != lexer.CONCAT {
+			break
+		}
+		expr = left
+	}
+	values = append(values, expr.Left)
+
+	// values are appended right to left
+	// but need to pushed left to right
+
+	if len(values) == 2 {
+		c.expr(values[1])
+		c.expr(values[0])
+		c.add(Concat2)
+		return
+	}
+
+	for i := len(values) - 1; i >= 0; i-- {
+		c.expr(values[i])
+	}
+
+	c.add(ConcatMulti, opcodeInt(len(values)))
+}
+
 // Add (or reuse) a number constant and returns its index.
 func (c *compiler) numIndex(n float64) int {
 	if index, ok := c.indexes.nums[n]; ok {
@@ -922,7 +954,7 @@ func (c *compiler) binaryOp(op lexer.Token) {
 	case lexer.LTE:
 		opcode = LessOrEqual
 	case lexer.CONCAT:
-		opcode = Concat
+		opcode = Concat2
 	case lexer.MUL:
 		opcode = Multiply
 	case lexer.DIV:
@@ -953,6 +985,6 @@ func (c *compiler) index(index []ast.Expr) {
 		c.expr(expr)
 	}
 	if len(index) > 1 {
-		c.add(MultiIndex, opcodeInt(len(index)))
+		c.add(IndexMulti, opcodeInt(len(index)))
 	}
 }
diff --git a/internal/compiler/disassembler.go b/internal/compiler/disassembler.go
index 807be3a..88ca8a3 100644
--- a/internal/compiler/disassembler.go
+++ b/internal/compiler/disassembler.go
@@ -267,9 +267,13 @@ func (d *disassembler) disassemble(prefix string) error {
 			regexIndex := d.fetch()
 			d.writeOpf("Regex %q (%d)", d.program.Regexes[regexIndex], regexIndex)
 
-		case MultiIndex:
+		case IndexMulti:
 			num := d.fetch()
-			d.writeOpf("MultiIndex %d", num)
+			d.writeOpf("IndexMulti %d", num)
+
+		case ConcatMulti:
+			num := d.fetch()
+			d.writeOpf("ConcatMulti %d", num)
 
 		case Jump:
 			offset := d.fetch()
diff --git a/internal/compiler/opcode_string.go b/internal/compiler/opcode_string.go
index ebb2f30..2b3a235 100644
--- a/internal/compiler/opcode_string.go
+++ b/internal/compiler/opcode_string.go
@@ -44,62 +44,63 @@ func _() {
 	_ = x[AugAssignArrayGlobal-33]
 	_ = x[AugAssignArrayLocal-34]
 	_ = x[Regex-35]
-	_ = x[MultiIndex-36]
-	_ = x[Add-37]
-	_ = x[Subtract-38]
-	_ = x[Multiply-39]
-	_ = x[Divide-40]
-	_ = x[Power-41]
-	_ = x[Modulo-42]
-	_ = x[Equals-43]
-	_ = x[NotEquals-44]
-	_ = x[Less-45]
-	_ = x[Greater-46]
-	_ = x[LessOrEqual-47]
-	_ = x[GreaterOrEqual-48]
-	_ = x[Concat-49]
-	_ = x[Match-50]
-	_ = x[NotMatch-51]
-	_ = x[Not-52]
-	_ = x[UnaryMinus-53]
-	_ = x[UnaryPlus-54]
-	_ = x[Boolean-55]
-	_ = x[Jump-56]
-	_ = x[JumpFalse-57]
-	_ = x[JumpTrue-58]
-	_ = x[JumpEquals-59]
-	_ = x[JumpNotEquals-60]
-	_ = x[JumpLess-61]
-	_ = x[JumpGreater-62]
-	_ = x[JumpLessOrEqual-63]
-	_ = x[JumpGreaterOrEqual-64]
-	_ = x[Next-65]
-	_ = x[Exit-66]
-	_ = x[ForIn-67]
-	_ = x[BreakForIn-68]
-	_ = x[CallBuiltin-69]
-	_ = x[CallSplit-70]
-	_ = x[CallSplitSep-71]
-	_ = x[CallSprintf-72]
-	_ = x[CallUser-73]
-	_ = x[CallNative-74]
-	_ = x[Return-75]
-	_ = x[ReturnNull-76]
-	_ = x[Nulls-77]
-	_ = x[Print-78]
-	_ = x[Printf-79]
-	_ = x[Getline-80]
-	_ = x[GetlineField-81]
-	_ = x[GetlineGlobal-82]
-	_ = x[GetlineLocal-83]
-	_ = x[GetlineSpecial-84]
-	_ = x[GetlineArray-85]
-	_ = x[EndOpcode-86]
+	_ = x[IndexMulti-36]
+	_ = x[ConcatMulti-37]
+	_ = x[Add-38]
+	_ = x[Subtract-39]
+	_ = x[Multiply-40]
+	_ = x[Divide-41]
+	_ = x[Power-42]
+	_ = x[Modulo-43]
+	_ = x[Equals-44]
+	_ = x[NotEquals-45]
+	_ = x[Less-46]
+	_ = x[Greater-47]
+	_ = x[LessOrEqual-48]
+	_ = x[GreaterOrEqual-49]
+	_ = x[Concat2-50]
+	_ = x[Match-51]
+	_ = x[NotMatch-52]
+	_ = x[Not-53]
+	_ = x[UnaryMinus-54]
+	_ = x[UnaryPlus-55]
+	_ = x[Boolean-56]
+	_ = x[Jump-57]
+	_ = x[JumpFalse-58]
+	_ = x[JumpTrue-59]
+	_ = x[JumpEquals-60]
+	_ = x[JumpNotEquals-61]
+	_ = x[JumpLess-62]
+	_ = x[JumpGreater-63]
+	_ = x[JumpLessOrEqual-64]
+	_ = x[JumpGreaterOrEqual-65]
+	_ = x[Next-66]
+	_ = x[Exit-67]
+	_ = x[ForIn-68]
+	_ = x[BreakForIn-69]
+	_ = x[CallBuiltin-70]
+	_ = x[CallSplit-71]
+	_ = x[CallSplitSep-72]
+	_ = x[CallSprintf-73]
+	_ = x[CallUser-74]
+	_ = x[CallNative-75]
+	_ = x[Return-76]
+	_ = x[ReturnNull-77]
+	_ = x[Nulls-78]
+	_ = x[Print-79]
+	_ = x[Printf-80]
+	_ = x[Getline-81]
+	_ = x[GetlineField-82]
+	_ = x[GetlineGlobal-83]
+	_ = x[GetlineLocal-84]
+	_ = x[GetlineSpecial-85]
+	_ = x[GetlineArray-86]
+	_ = x[EndOpcode-87]
 }
 
-const _Opcode_name = "NopNumStrDupeDropSwapFieldFieldIntGlobalLocalSpecialArrayGlobalArrayLocalInGlobalInLocalAssignFieldAssignGlobalAssignLocalAssignSpecialAssignArrayGlobalAssignArrayLocalDeleteDeleteAllIncrFieldIncrGlobalIncrLocalIncrSpecialIncrArrayGlobalIncrArrayLocalAugAssignFieldAugAssignGlobalAugAssignLocalAugAssignSpecialAugAssignArrayGlobalAugAssignArrayLocalRegexMultiIndexAddSubtractMultiplyDividePowerModuloEqualsNotEqualsLessGreaterLessOrEqualGreaterOrEqualConcatMatchNotMatchNotUnaryMinusUnaryPlusBooleanJumpJumpFalseJumpTrueJumpEqualsJumpNotEqualsJumpLessJumpGreaterJumpLessOrEqualJumpGreaterOrEqualNextExitForInBreakForInCallBuiltinCallSplitCallSplitSepCallSprintfCallUserCallNativeReturnReturnNullNullsPrintPrintfGetlineGetlineFieldGetlineGlobalGetlineLocalGetlineSpecialGetlineArrayEndOpcode"
+const _Opcode_name = "NopNumStrDupeDropSwapFieldFieldIntGlobalLocalSpecialArrayGlobalArrayLocalInGlobalInLocalAssignFieldAssignGlobalAssignLocalAssignSpecialAssignArrayGlobalAssignArrayLocalDeleteDeleteAllIncrFieldIncrGlobalIncrLocalIncrSpecialIncrArrayGlobalIncrArrayLocalAugAssignFieldAugAssignGlobalAugAssignLocalAugAssignSpecialAugAssignArrayGlobalAugAssignArrayLocalRegexIndexMultiConcatMultiAddSubtractMultiplyDividePowerModuloEqualsNotEqualsLessGreaterLessOrEqualGreaterOrEqualConcat2MatchNotMatchNotUnaryMinusUnaryPlusBooleanJumpJumpFalseJumpTrueJumpEqualsJumpNotEqualsJumpLessJumpGreaterJumpLessOrEqualJumpGreaterOrEqualNextExitForInBreakForInCallBuiltinCallSplitCallSplitSepCallSprintfCallUserCallNativeReturnReturnNullNullsPrintPrintfGetlineGetlineFieldGetlineGlobalGetlineLocalGetlineSpecialGetlineArrayEndOpcode"
 
-var _Opcode_index = [...]uint16{0, 3, 6, 9, 13, 17, 21, 26, 34, 40, 45, 52, 63, 73, 81, 88, 99, 111, 122, 135, 152, 168, 174, 183, 192, 202, 211, 222, 237, 251, 265, 280, 294, 310, 330, 349, 354, 364, 367, 375, 383, 389, 394, 400, 406, 415, 419, 426, 437, 451, 457, 462, 470, 473, 483, 492, 499, 503, 512, 520, 530, 543, 551, 562, 577, 595, 599, 603, 608, 618, 629, 638, 650, 661, 669, 679, 685, 695, 700, 705, 711, 718, 730, 743, 755, 769, 781, 790}
+var _Opcode_index = [...]uint16{0, 3, 6, 9, 13, 17, 21, 26, 34, 40, 45, 52, 63, 73, 81, 88, 99, 111, 122, 135, 152, 168, 174, 183, 192, 202, 211, 222, 237, 251, 265, 280, 294, 310, 330, 349, 354, 364, 375, 378, 386, 394, 400, 405, 411, 417, 426, 430, 437, 448, 462, 469, 474, 482, 485, 495, 504, 511, 515, 524, 532, 542, 555, 563, 574, 589, 607, 611, 615, 620, 630, 641, 650, 662, 673, 681, 691, 697, 707, 712, 717, 723, 730, 742, 755, 767, 781, 793, 802}
 
 func (i Opcode) String() string {
 	if i < 0 || i >= Opcode(len(_Opcode_index)-1) {
diff --git a/internal/compiler/opcodes.go b/internal/compiler/opcodes.go
index 833b906..20d328c 100644
--- a/internal/compiler/opcodes.go
+++ b/internal/compiler/opcodes.go
@@ -66,7 +66,10 @@ const (
 	Regex // regexIndex
 
 	// Multi-index concatenation
-	MultiIndex // num
+	IndexMulti // num
+
+	// Multi-value concatenation
+	ConcatMulti
 
 	// Binary operators
 	Add
@@ -81,7 +84,7 @@ const (
 	Greater
 	LessOrEqual
 	GreaterOrEqual
-	Concat
+	Concat2
 	Match
 	NotMatch
 
diff --git a/interp/vm.go b/interp/vm.go
index 29e40a8..3b42b3b 100644
--- a/interp/vm.go
+++ b/interp/vm.go
@@ -308,7 +308,7 @@ func (p *interp) execute(code []compiler.Opcode) error {
 			re := p.regexes[index]
 			p.push(boolean(re.MatchString(p.line)))
 
-		case compiler.MultiIndex:
+		case compiler.IndexMulti:
 			numValues := int(code[ip])
 			ip++
 			values := p.popSlice(numValues)
@@ -410,10 +410,21 @@ func (p *interp) execute(code []compiler.Opcode) error {
 				p.replaceTop(boolean(ln >= rn))
 			}
 
-		case compiler.Concat:
+		case compiler.Concat2:
 			l, r := p.peekPop()
 			p.replaceTop(str(p.toString(l) + p.toString(r)))
 
+		case compiler.ConcatMulti:
+			numValues := int(code[ip])
+			ip++
+			values := p.popSlice(numValues)
+			var sb strings.Builder
+
+			for _, v := range values {
+				sb.WriteString(p.toString(v))
+			}
+			p.push(str(sb.String()))
+
 		case compiler.Match:
 			l, r := p.peekPop()
 			re, err := p.compileRegex(p.toString(r))


Test patch:
diff --git a/interp/interp_test.go b/interp/interp_test.go
index 5aa2130..9957418 100644
--- a/interp/interp_test.go
+++ b/interp/interp_test.go
@@ -1896,6 +1896,19 @@ BEGIN {
 `, b.N)
 }
 
+func BenchmarkConcatTwo(b *testing.B) {
+	b.StopTimer()
+	benchmarkProgram(b, nil, "", "20", `
+BEGIN {
+  x = "0123456789"
+  for (i = 0; i < %d; i++) {
+    y = x x
+  }
+  print length(y)
+}
+`, b.N)
+}
+
 func BenchmarkConcatSmall(b *testing.B) {
 	b.StopTimer()
 	benchmarkProgram(b, nil, "", "100", `