cmd/compile: use delta encoding for filenames in export data position info

This reduces the export data size significantly (15%-25%) for some packages,
especially where the paths are very long or if there are many files involved.
Slight (2%) reduction on average, with virtually no increases in export data
size.

Selected export data sizes for packages with |delta %| > 3%:

                     package   before    after   delta     %

        cmd/asm/internal/arch   11647    11088    -559   -4%
   cmd/compile/internal/amd64     838      600    -238  -27%
     cmd/compile/internal/arm    7323     6793    -530   -6%
   cmd/compile/internal/arm64   19948    18971    -977   -4%
     cmd/compile/internal/big    9043     8548    -495   -4%
  cmd/compile/internal/mips64     645      482    -163  -24%
   cmd/compile/internal/ppc64     695      497    -198  -27%
   cmd/compile/internal/s390x     553      433    -120  -21%
     cmd/compile/internal/x86     744      555    -189  -24%
                     cmd/dist     145      121     -24  -16%
         cmd/internal/objfile   17359    16474    -885   -4%
   cmd/internal/pprof/symbolz    8346     7941    -405   -4%
      cmd/link/internal/amd64   11178    10604    -574   -4%
        cmd/link/internal/arm     204      171     -33  -15%
      cmd/link/internal/arm64     210      175     -35  -16%
     cmd/link/internal/mips64     213      177     -36  -16%
      cmd/link/internal/ppc64     211      176     -35  -16%
      cmd/link/internal/s390x     210      175     -35  -16%
        cmd/link/internal/x86     203      170     -33  -15%
                    cmd/trace     782      744     -38   -4%
                 compress/lzw     402      383     -19   -4%
                   crypto/aes     311      262     -49  -15%
                crypto/cipher    1138      959    -179  -15%
                   crypto/des     315      288     -27   -8%
              crypto/elliptic    6063     5746    -317   -4%
                   crypto/rc4     317      295     -22   -6%
                crypto/sha256     348      312     -36   -9%
                crypto/sha512     487      451     -36   -6%
                       go/doc    3871     3649    -222   -5%
    go/internal/gccgoimporter    2063     1949    -114   -5%
       go/internal/gcimporter    3253     3096    -157   -4%
                         math    4343     3572    -771  -17%
                   math/cmplx    1580     1274    -306  -18%
                    math/rand     982      926     -56   -5%
        net/internal/socktest    2159     2049    -110   -4%
                      os/exec    7928     7492    -436   -4%
                    os/signal     237      208     -29  -11%
                      os/user     717      682     -35   -4%
      runtime/internal/atomic     728      693     -35   -4%
         runtime/internal/sys    2287     2107    -180   -7%
                         sync    1306     1214     -92   -6%

                 all packages 1509255  1465507  -43748   -2%

Change-Id: I98a11521b552166b7f47f2039a29f106748bf5d4
Reviewed-on: https://go-review.googlesource.com/22580
Reviewed-by: Alan Donovan <adonovan@google.com>

3 files changed, 49 insertions, 22 deletions

diff --git a/src/cmd/compile/internal/gc/bexport.go b/src/cmd/compile/internal/gc/bexport.go
index 20c1aeba9d..1cce0c9a44 100644
--- a/src/cmd/compile/internal/gc/bexport.go
+++ b/src/cmd/compile/internal/gc/bexport.go
@@ -4,8 +4,6 @@
 
 // Binary package export.
 // (see fmt.go, parser.go as "documentation" for how to use/setup data structures)
-//
-// Use "-newexport" flag to enable.
 
 /*
 Export data encoding:
@@ -508,25 +506,52 @@ func (p *exporter) pos(n *Node) {
 		return
 	}
 
-	var file string
-	var line int
-	if n != nil {
-		file, line = Ctxt.LineHist.AbsFileLine(int(n.Lineno))
-	}
-
-	if file == p.prevFile && line != p.prevLine {
-		// common case: write delta-encoded line number
-		p.int(line - p.prevLine) // != 0
+	file, line := fileLine(n)
+	if file == p.prevFile {
+		// common case: write line delta
+		// delta == 0 means different file or no line change
+		delta := line - p.prevLine
+		p.int(delta)
+		if delta == 0 {
+			p.int(-1) // -1 means no file change
+		}
 	} else {
-		// uncommon case: filename changed, or line didn't change
+		// different file
 		p.int(0)
-		p.string(file)
-		p.int(line)
+		// Encode filename as length of common prefix with previous
+		// filename, followed by (possibly empty) suffix. Filenames
+		// frequently share path prefixes, so this can save a lot
+		// of space and make export data size less dependent on file
+		// path length. The suffix is unlikely to be empty because
+		// file names tend to end in ".go".
+		n := commonPrefixLen(p.prevFile, file)
+		p.int(n)           // n >= 0
+		p.string(file[n:]) // write suffix only
 		p.prevFile = file
+		p.int(line)
 	}
 	p.prevLine = line
 }
 
+func fileLine(n *Node) (file string, line int) {
+	if n != nil {
+		file, line = Ctxt.LineHist.AbsFileLine(int(n.Lineno))
+	}
+	return
+}
+
+func commonPrefixLen(a, b string) int {
+	if len(a) > len(b) {
+		a, b = b, a
+	}
+	// len(a) <= len(b)
+	i := 0
+	for i < len(a) && a[i] == b[i] {
+		i++
+	}
+	return i
+}
+
 func isInlineable(n *Node) bool {
 	if exportInlined && n != nil && n.Func != nil && n.Func.Inl.Len() != 0 {
 		// when lazily typechecking inlined bodies, some re-exported ones may not have been typechecked yet.
diff --git a/src/cmd/compile/internal/gc/bimport.go b/src/cmd/compile/internal/gc/bimport.go
index 6fe30cdba9..0a8980744d 100644
--- a/src/cmd/compile/internal/gc/bimport.go
+++ b/src/cmd/compile/internal/gc/bimport.go
@@ -297,13 +297,14 @@ func (p *importer) pos() {
 
 	file := p.prevFile
 	line := p.prevLine
-
 	if delta := p.int(); delta != 0 {
+		// line changed
 		line += delta
-	} else {
-		file = p.string()
-		line = p.int()
+	} else if n := p.int(); n >= 0 {
+		// file changed
+		file = p.prevFile[:n] + p.string()
 		p.prevFile = file
+		line = p.int()
 	}
 	p.prevLine = line
 
diff --git a/src/go/internal/gcimporter/bimport.go b/src/go/internal/gcimporter/bimport.go
index 5ba9af1b02..f1385c8c90 100644
--- a/src/go/internal/gcimporter/bimport.go
+++ b/src/go/internal/gcimporter/bimport.go
@@ -204,13 +204,14 @@ func (p *importer) pos() {
 
 	file := p.prevFile
 	line := p.prevLine
-
 	if delta := p.int(); delta != 0 {
+		// line changed
 		line += delta
-	} else {
-		file = p.string()
-		line = p.int()
+	} else if n := p.int(); n >= 0 {
+		// file changed
+		file = p.prevFile[:n] + p.string()
 		p.prevFile = file
+		line = p.int()
 	}
 	p.prevLine = line