From 0750107074c39f7b846515de47c2857cbdb7e3d6 Mon Sep 17 00:00:00 2001
From: Alan Donovan <adonovan@google.com>
Date: Wed, 29 Jun 2022 13:08:11 -0400
Subject: [PATCH] go/token: use atomics not Mutex for last file cache

Previously, FileSet would cache the last *File found by a lookup,
using a full (exclusive) mutex within FileSet.File, turning a logical
read operation into an update. This was one of the largest sources
of contention in gopls.  This change uses atomic load/store on the
'last' field without a mutex.

Also, in FileSet.AddFile, allocate the File outside the critical
section; all the other operations are typically cheap.

Fixes #53507

Change-Id: Ice8641650d8495b25b0428e9b9320837ff2ca7e1
Reviewed-on: https://go-review.googlesource.com/c/go/+/411909
Reviewed-by: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
---
 src/go/token/position.go  | 34 +++++++++++++++++++---------------
 src/go/token/serialize.go |  2 +-
 2 files changed, 20 insertions(+), 16 deletions(-)

diff --git a/src/go/token/position.go b/src/go/token/position.go
index bd9ae07b28..b5a380a280 100644
--- a/src/go/token/position.go
+++ b/src/go/token/position.go
@@ -8,6 +8,7 @@ import (
 	"fmt"
 	"sort"
 	"sync"
+	"sync/atomic"
 )
 
 // -----------------------------------------------------------------------------
@@ -366,10 +367,10 @@ func (f *File) Position(p Pos) (pos Position) {
 // interval later, using the FileSet.Base should be used as argument
 // for FileSet.AddFile.
 type FileSet struct {
-	mutex sync.RWMutex // protects the file set
-	base  int          // base offset for the next file
-	files []*File      // list of files in the order added to the set
-	last  *File        // cache of last file looked up
+	mutex sync.RWMutex         // protects the file set
+	base  int                  // base offset for the next file
+	files []*File              // list of files in the order added to the set
+	last  atomic.Pointer[File] // cache of last file looked up
 }
 
 // NewFileSet creates a new file set.
@@ -405,6 +406,9 @@ func (s *FileSet) Base() int {
 // For convenience, File.Pos may be used to create file-specific position
 // values from a file offset.
 func (s *FileSet) AddFile(filename string, base, size int) *File {
+	// Allocate f outside the critical section.
+	f := &File{name: filename, size: size, lines: []int{0}}
+
 	s.mutex.Lock()
 	defer s.mutex.Unlock()
 	if base < 0 {
@@ -413,11 +417,11 @@ func (s *FileSet) AddFile(filename string, base, size int) *File {
 	if base < s.base {
 		panic(fmt.Sprintf("invalid base %d (should be >= %d)", base, s.base))
 	}
+	f.base = base
 	if size < 0 {
 		panic(fmt.Sprintf("invalid size %d (should be >= 0)", size))
 	}
 	// base >= s.base && size >= 0
-	f := &File{name: filename, base: base, size: size, lines: []int{0}}
 	base += size + 1 // +1 because EOF also has a position
 	if base < 0 {
 		panic("token.Pos offset overflow (> 2G of source code in file set)")
@@ -425,7 +429,7 @@ func (s *FileSet) AddFile(filename string, base, size int) *File {
 	// add the file to the file set
 	s.base = base
 	s.files = append(s.files, f)
-	s.last = f
+	s.last.Store(f)
 	return f
 }
 
@@ -450,25 +454,25 @@ func searchFiles(a []*File, x int) int {
 }
 
 func (s *FileSet) file(p Pos) *File {
-	s.mutex.RLock()
-	// common case: p is in last file
-	if f := s.last; f != nil && f.base <= int(p) && int(p) <= f.base+f.size {
-		s.mutex.RUnlock()
+	// common case: p is in last file.
+	if f := s.last.Load(); f != nil && f.base <= int(p) && int(p) <= f.base+f.size {
 		return f
 	}
+
+	s.mutex.RLock()
+	defer s.mutex.RUnlock()
+
 	// p is not in last file - search all files
 	if i := searchFiles(s.files, int(p)); i >= 0 {
 		f := s.files[i]
 		// f.base <= int(p) by definition of searchFiles
 		if int(p) <= f.base+f.size {
-			s.mutex.RUnlock()
-			s.mutex.Lock()
-			s.last = f // race is ok - s.last is only a cache
-			s.mutex.Unlock()
+			// Update cache of last file. A race is ok,
+			// but an exclusive lock causes heavy contention.
+			s.last.Store(f)
 			return f
 		}
 	}
-	s.mutex.RUnlock()
 	return nil
 }
 
diff --git a/src/go/token/serialize.go b/src/go/token/serialize.go
index 38c10ebd47..04a48d90f8 100644
--- a/src/go/token/serialize.go
+++ b/src/go/token/serialize.go
@@ -39,7 +39,7 @@ func (s *FileSet) Read(decode func(any) error) error {
 		}
 	}
 	s.files = files
-	s.last = nil
+	s.last.Store(nil)
 	s.mutex.Unlock()
 
 	return nil
-- 
2.48.1