compiler: use hash calculation for determining archive staleness #805

myitcv · Apr 23, 2018

Work towards #804 (will require a follow up to zero modification times)

Fixes #440 and likely other stale cache related issues.

myitcv · Apr 23, 2018

@shurcooL @hajimehoshi this is ready for discussion and review.

hajimehoshi · Apr 23, 2018

Basically what this PR does is to remove SrcModTime?

myitcv · Apr 23, 2018

Basically what this PR does is to remove SrcModTime?

Currently staleness of an archive is determined using mod time of the transitive set of input files, the gopherjs binary and the archive itself.

This PR switches from using modtimes (which can give false positives and incorrect answers) to using a hashing strategy similar to the build cache in Go 1.10 (although nowhere near as advanced - we still maintain just a single archive).

It also has the advantage of allowing us to introduce other aspects into the staleness calculation, such as build tags which I have also done and this fixes #440.

This PR also likely fixes a number of other staleness/caching issues that randomly get seen/reported.

It also paves the way for fixing #804 by allowing us to zero the modification times.

build/build.go

hajimehoshi · Apr 23, 2018

build/build.go

 		}

+		binHash := sha256.New()
+		io.Copy(binHash, binFile)
+		binFile.Close()


Actually (*File).Close doesn't usually cause error (if error happens, this is a critical error), but checking error is not bad here?

I'd agree; if that fails we're in serious trouble. I think I'll leave this.

build/build.go

myitcv · Apr 23, 2018

tool.go

@@ -298,11 +298,13 @@ func main() {
 	run := cmdTest.Flags().String("run", "", "Run only those tests and examples matching the regular expression.")
 	short := cmdTest.Flags().Bool("short", false, "Tell long-running tests to shorten their run time.")
 	verbose := cmdTest.Flags().BoolP("verbose", "v", false, "Log all tests as they are run. Also print all text from Log and Logf calls even if the test succeeds.")
+	buildVerbose := cmdTest.Flags().BoolP("bv", "", false, "Use a verbose build context.")


Not essential to have this... but helps to verify when we get cache misses or not in running tests.

I was wondering why we need this besides the existing verbose.

myitcv · Apr 23, 2018

Thanks for taking a look @hajimehoshi - addressed your feedback. PTAL.

build/build.go

myitcv · Apr 24, 2018

@hajimehoshi - I've tweaked a couple of things in my latest commit which also addresses the points you made. I've also moved from gopherjs binary hash to compiler binary hash in case something other than gopherjs is importing this build package. PTAL.

flimzy · Apr 24, 2018

build/build.go

+func init() {
+	// We do this here because it will only fail in truly bad situations, i.e.
+	// machine running out of resources. We also panic if there is a problem
+	// because it's unlikely anything else will be useful/work


Rather than panicking here, would it be useful to fallback to a cache-disabled state?

Maybe that would allow running the gopherjs compiler in unusual environments (such as within a browser?)? (That may already be impossible for other reasons, idk).

That's a fair point. I think I'd like to understand that situation a bit better; because a whole load of logic in build depends on the OS being available (writing archives etc).

The compiler is run within the browser by the playground, but that does not import build, just compiler.

hajimehoshi

lgtm

@shurcooL, please take a look.

hajimehoshi · Apr 24, 2018

build/build.go

+	//
+	// file: <file path>
+	// <file contents>
+	// N bytes


Hmm, I feel like this format is a little bit arbitrary. Can we use JSON or YAML or something formatted? I don't have a strong opinion though...

A possible problem with JSON/YAML is that it's not inherently ordered. While we could find a way to ensure constant ordering, it wouldn't necessarily happen by default, which could lead to false negative cache hits.

The goal here is to create a hash as quickly as possible in order to determine whether we have a cache miss or not. So yes, whilst the format is arbitrary, it is simple. And requires no additional processing in order to write to the hash. Using JSON/YAML adds more overhead in the middle, overhead that is unnecessary because ultimately the output is a 256 bit value. Humans will only ever read this whilst debugging (which itself will be a rare occurrence) with hashDebug = true.

hajimehoshi · Apr 24, 2018

tool.go

@@ -298,11 +298,13 @@ func main() {
 	run := cmdTest.Flags().String("run", "", "Run only those tests and examples matching the regular expression.")
 	short := cmdTest.Flags().Bool("short", false, "Tell long-running tests to shorten their run time.")
 	verbose := cmdTest.Flags().BoolP("verbose", "v", false, "Log all tests as they are run. Also print all text from Log and Logf calls even if the test succeeds.")
+	buildVerbose := cmdTest.Flags().BoolP("bv", "", false, "Use a verbose build context.")


hajimehoshi · Apr 24, 2018

build/build.go

+
+	pkgHash := sha256.New()
+	var hw io.Writer = pkgHash
+	var hashDebugOut *bytes.Buffer


This is an optional suggestion: Instead of bytes.Buffer, how about using text/template?

I'm unclear, why/how would we use text/template here?

myitcv · Apr 24, 2018

@hajimehoshi thanks for taking a look. I've responded to your questions and removed the --bv flag for gopherjs test.

dmitshur · Apr 24, 2018

@shurcooL, please take a look.

Sorry, but I don't have the bandwidth to properly review this change soon (maybe the coming weekend, but maybe not until the one after).

I have the following concern and question: how can we gain enough confidence that this change will not introduce regressions in the build staleness calculations? It would be quite bad if the compiler starts to use old code and not rebuild in some situations, and there are many edge cases.

Also, this PR changes code, but I would first like to see a high level description of the algorithm used, and review that. Afterwards, it would be easier to review the code and make sure it implements the algorithm.

Thanks for working on this. I agree in general that using hash of content can be better than the modify time, as it avoids unnecessary rebuilds when the content hasn't changed but modtime has, but it needs to work in all cases that the previous approach handled. I see you also took on fixing #440 which is great, but that issue needs to be re-verified whether it still exists in latest master version. I hope we can get this PR to a state where we can merge it with high confidence.

myitcv · Apr 28, 2018

Hi @shurcooL - very happy to add more detail. I pushed up the code to help with our discussion.

What follows is based on my understanding of how archive staleness is currently, i.e. in master, calculated. To state the obvious, this understanding might be wrong/incomplete.

Below, ModTime is always a reference to os.FileInfo.ModTime()

how can we gain enough confidence that this change will not introduce regressions in the build staleness calculations?

Currently, an archive for a package P is deemed stale if its ModTime (i.e. the ModTime of the archive on disk) is before either of:

ModTime of the gopherjs binary; more specifically, the running program that has imported github.com/gopherjs/gopher/build
The latest (i.e. most recent) ModTime of the transitive dependencies of P, including standard library packages
The latest (i.e. most recent) ModTime of the Go and JS files of P

Test programs and main packages are not archived.

Here ModTime is acting as a proxy for the contents of the files in question; whether that be the gopherjs binary, or the archives of the dependencies of P. It is therefore possible, and does happen, that the ModTime falls out of "sync" with the contents; i.e. the contents change without the ModTime changing or vice versa. It is therefore an imperfect proxy.

Far better is to follow an approach that uses the actual contents of those files to determine staleness. A hash-based approach does exactly this. The approach I've adopted here is similar to the build cache introduced in Go 1.10, but differs in one important respect: with the go tool, the computed hash effectively acts as a pointer to an area of the cache. With the approach adopted here, the computed hash is simply used to determine whether the archive we have on disk is stale or not. The approach taken by the go tool is far more advanced and robust, but requires a cache eviction policy (else your disk runs out of space); hence as a first cut I have gone for the "hash as a means of determining staleness" approach. A more complex approach could be adopted but doesn't seem particularly worthwhile at this stage.

I would first like to see a high level description of the algorithm used, and review that

The algorithm is therefore quite simple: we take all inputs that go into determining/building a package archive, hash them in a well defined order, compare that hash with the hash in the current archive. If the hashes are different then the archive on disk is stale, at which point we recompile it and rewrite it to disk.

This approach allows us to include arbitrary data in the input hash, including build tags.

So the inputs to the hash calculation are now:

the import path of the package being compiled (for ease of debugging)
a hash of the file contents of the running program that has imported github.com/gopherjs/gopher/build
the build tags being used
the import path and hash of all the transitive dependencies of P
the contents of each of the Go and JS files of the package P

We use crypto/sha256 just as the go tool does for all our hash calculations.

... but it needs to work in all cases that the previous approach handled

Because ModTime is an imperfect proxy for the file contents, there are many cases that don't get handled with the ModTime approach. And it's hard to know when we are going to be bitten by those edge cases. Using the hash-based approach of file contents we side step this entirely and solve all cases.

The one case that is neither handled by the hash-based nor the current ModTime approaches is that of race conditions on the disk on archive. That is, if two gopherjs processes are trying to determine staleness/write an archive at the same time; they effectively race. But given this is not currently handled we can simply note the exception and fix in a future PR if required.

I see you also took on fixing #440 which is great, but that issue needs to be re-verified whether it still exists in latest master version

Based on my understand this will still be broken on master because build tags are not currently part of the calculation for staleness, hence the bug. With this PR they are, hence staleness is correctly calculated.

I hope we can get this PR to a state where we can merge it with high confidence.

So to my mind we can have a high degree of confidence with this PR if we can be confident that we have the correct list of inputs; and I believe we do.

The best way to see this in action (in the absence of specific tests at this point) is to:

cd $(go list -f '{{.Dir}}' github.com/gopherjs/gopherjs) && \
git fetch origin pull/805/head && \
git checkout FETCH_HEAD && \
go install
gopherjs serve -v

Then try out something like the playground via http://localhost:8080/github.com/gopherjs/gopherjs.github.io/playground/. On the first load you should see the following output:

Cache miss for errors
Cache miss for internal/race
Cache miss for runtime
Cache miss for runtime/internal/sys
Cache miss for github.com/gopherjs/gopherjs/js
Cache miss for sync/atomic
Cache miss for sync
Cache miss for io
Cache miss for unicode
Cache miss for unicode/utf8
Cache miss for bytes
Cache miss for bufio
Cache miss for math
Cache miss for syscall
Cache miss for internal/poll
Cache miss for time
Cache miss for github.com/gopherjs/gopherjs/nosync
Cache miss for internal/testlog
Cache miss for os
Cache miss for strconv
Cache miss for reflect
Cache miss for fmt
Cache miss for sort
Cache miss for go/token
Cache miss for strings
Cache miss for path/filepath
Cache miss for go/scanner
Cache miss for go/ast
Cache miss for io/ioutil
Cache miss for go/parser
Cache miss for text/tabwriter
Cache miss for go/printer
Cache miss for go/format
Cache miss for golang.org/x/tools/go/ast/astutil
Cache miss for path
Cache miss for regexp/syntax
Cache miss for regexp
Cache miss for github.com/gopherjs/gopherjs.github.io/playground/internal/imports
Cache miss for encoding/binary
Cache miss for encoding
Cache miss for math/bits
Cache miss for encoding/gob
Cache miss for encoding/base64
Cache miss for unicode/utf16
Cache miss for encoding/json
Cache miss for container/heap
Cache miss for math/rand
Cache miss for math/big
Cache miss for go/constant
Cache miss for go/types
Cache miss for github.com/gopherjs/gopherjs/compiler/astutil
Cache miss for github.com/gopherjs/gopherjs/compiler/typesutil
Cache miss for github.com/gopherjs/gopherjs/compiler/analysis
Cache miss for github.com/gopherjs/gopherjs/compiler/filter
Cache miss for github.com/gopherjs/gopherjs/compiler/prelude
Cache miss for github.com/gopherjs/gopherjs/compiler/vendor/github.com/neelance/astrewrite
Cache miss for net/url
Cache miss for text/template/parse
Cache miss for text/template
Cache miss for go/doc
Cache miss for log
Cache miss for go/build
Cache miss for text/scanner
Cache miss for golang.org/x/tools/go/types/typeutil
Cache miss for github.com/gopherjs/gopherjs/compiler
Cache miss for github.com/neelance/go-angularjs
Cache miss for honnef.co/go/js/dom
Cache miss for honnef.co/go/js/util
Cache miss for honnef.co/go/js/xhr
Cache miss for github.com/gopherjs/gopherjs.github.io/playground

If you empty cache and hard reload the page you should see:

Cache miss for github.com/gopherjs/gopherjs.github.io/playground

And that is because main packages and test programs are not cached.

Indeed if you kill and restart gopherjs serve -v and force reload the page you will see the same output; because none of the inputs have changed with respect to the hash calculation.

If you then kill gopherjs serve -v and instead gopherjs serve --tags blah -v, force reload the page you will see all the cache misses again.

Would very much welcome feedback/questions on the above and this PR.

Thanks.

myitcv · Apr 28, 2018

I've also just added a basic test to show this in action and working.

myitcv · May 5, 2018

Got hit by another staleness bug again this afternoon. Still unclear how the situation with mod times getting out of sync comes about, but the hash-based approach has been 100% good since I started using it.

antong · May 29, 2018

Fixes #827 .

antong · Sep 3, 2018

I've been using this for a while now without problems. Would be really cool to have this merged as the current mod staleness calculation can't be trusted (#827).

The biggest change in this commit is a rewrite of build cache machinery. Previously GopherJS used to store its build cache under $GOPATH/pkg/$GOOS_$GOARCH, and after Go Modules introduction some parts of it were stored under os.UserCacheDir(). Starting from this commit, *all* build cache is located under os.UserCacheDir(), in a manner similar to the modern Go tool. The cache is keyed by a set of build options (such as minification, compiler version, etc.) to ensure that incompatible archives aren't picked up (see gopherjs#440 for example). This change doesn't solve *all* possible cache-related issues (for example, it still relies on timestamps to invalidate the cache, see gopherjs#805), but should eliminate a large class of confusing failure modes. The second important change is to the build order. Previously GopherJS could initiate build of an imported dependency while building the package that imported it (typically for an augmented stdlib package). Now the build is stricter, all imports are built upfront, preventing weird cyclic builds that could happened under the previous system. Lastly, package source modification time has been refactored in a way that doesn't require modification of Package.SrcModTime after the package was loaded. The old side-effect-based behavior was difficult to get right and debug.

Previously GopherJS used to store its build cache under $GOPATH/pkg/$GOOS_$GOARCH, and after Go Modules introduction some parts of it were stored under os.UserCacheDir(). Starting from this commit, *all* build cache is located under os.UserCacheDir(), in a manner similar to the modern Go tool. The cache is keyed by a set of build options (such as minification, compiler version, etc.) to ensure that incompatible archives aren't picked up (see gopherjs#440 for example). This change doesn't solve *all* possible cache-related issues (for example, it still relies on timestamps to invalidate the cache, see gopherjs#805), but should eliminate a large class of confusing failure modes.

nevkontakte · Apr 17, 2022

The codebase have moved on too far to make this pull request easily mergeable, but I think the approach it takes is a good one.

Recently merged #1105 set up some build caching infrastructure that could even allow us to use hash as a cache key (something #805 (comment) mentions as a possible improvement). This might also be the solution for the excessive cache busting #1110 pointed out.

However, there is a tricky issue that neither the current time-based invalidation nor hash-based invalidation in this PR handles: changes to standard library overlays that parseAndAugment function applies. It can both change the set of imported packages (by adding github.com/gopherjs/gopherjs/js or removing some other packages) and the content of the packages. Thus, computed hashes would be mostly correct, but not quite.

Arguably, this is relatively unlikely to affect normal gopherjs users who are not in a habit of patching standard library sources or editing gopherjs overlays. But this does expose a bigger flaw in the GopherJS's build system, and we need to have an idea for how it could be solved with or without this change.

myitcv changed the title ~~[WIP] compiler: use hash calculation for determining staleness~~ [WIP] compiler: use hash calculation for determining archive staleness Apr 23, 2018

myitcv changed the title ~~[WIP] compiler: use hash calculation for determining archive staleness~~ compiler: use hash calculation for determining archive staleness Apr 23, 2018

hajimehoshi suggested changes Apr 23, 2018

View reviewed changes

myitcv commented Apr 23, 2018

View reviewed changes

hajimehoshi reviewed Apr 23, 2018

View reviewed changes

build/build.go Outdated Show resolved Hide resolved

build/build.go Outdated Show resolved Hide resolved

myitcv force-pushed the make_gopherjs_stateleness_hash_based branch from 1b4cb77 to f0ccf72 Compare April 23, 2018 18:55

hajimehoshi reviewed Apr 23, 2018

View reviewed changes

build/build.go Show resolved Hide resolved

build/build.go Outdated Show resolved Hide resolved

build/build.go Outdated Show resolved Hide resolved

myitcv force-pushed the make_gopherjs_stateleness_hash_based branch from 3ed84d1 to b85c2e4 Compare April 24, 2018 06:14

flimzy reviewed Apr 24, 2018

View reviewed changes

hajimehoshi approved these changes Apr 24, 2018

View reviewed changes

myitcv added 11 commits May 4, 2018 20:34

compiler: use hash calculation for determining staleness

e807fdb

Add --bv flag to test to log verbose build context messages

e615455

Add build tags to the hash

69257f7

More readable version of hash for debug purposes

f6baa10

Fix file closing

41c38df

Address feedback from hajimehoshi

d73d4bb

Refactor to prefer defers for Close

9c06cba

Further refactor to use defer for close

82f8b60

Use better key name for gopherjs binary hash

2e40249

Move compiler hash calc to init phase

3d5665a

Remove --bv flag on test

5c358e3

Add basic test of new hash staleness

1ed4e6a

myitcv force-pushed the make_gopherjs_stateleness_hash_based branch from 796778c to 1ed4e6a Compare May 4, 2018 19:35

antong mentioned this pull request May 29, 2018

Incorrect use of stale cached code #827

Open

myitcv mentioned this pull request Oct 10, 2018

Support for vgo builds outside GOPATH #835

Closed

flimzy assigned nevkontakte Dec 28, 2021

nevkontakte mentioned this pull request Feb 16, 2022

WIP: Build sequence and caching overhaul. nevkontakte/gopherjs#5

Closed

nevkontakte mentioned this pull request Feb 16, 2022

Improved build cache invalidation #1105

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

compiler: use hash calculation for determining archive staleness #805

compiler: use hash calculation for determining archive staleness #805

myitcv commented Apr 23, 2018 •

edited

Loading

myitcv commented Apr 23, 2018

hajimehoshi commented Apr 23, 2018

myitcv commented Apr 23, 2018 •

edited

Loading

hajimehoshi Apr 23, 2018

myitcv Apr 23, 2018

myitcv Apr 23, 2018

hajimehoshi Apr 23, 2018

hajimehoshi Apr 24, 2018

myitcv commented Apr 23, 2018

myitcv commented Apr 24, 2018

flimzy Apr 24, 2018

myitcv Apr 24, 2018

hajimehoshi left a comment

hajimehoshi Apr 24, 2018

flimzy Apr 24, 2018 •

edited

Loading

myitcv Apr 24, 2018

hajimehoshi Apr 24, 2018

hajimehoshi Apr 24, 2018

myitcv Apr 24, 2018

myitcv commented Apr 24, 2018

dmitshur commented Apr 24, 2018 •

edited

Loading

myitcv commented Apr 28, 2018

myitcv commented Apr 28, 2018

myitcv commented May 5, 2018

antong commented May 29, 2018

antong commented Sep 3, 2018

nevkontakte commented Apr 17, 2022

Search code, repositories, users, issues, pull requests...

compiler: use hash calculation for determining archive staleness #805

Are you sure you want to change the base?

compiler: use hash calculation for determining archive staleness #805

Conversation

myitcv commented Apr 23, 2018 • edited Loading

myitcv commented Apr 23, 2018

hajimehoshi commented Apr 23, 2018

myitcv commented Apr 23, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

myitcv commented Apr 23, 2018

myitcv commented Apr 24, 2018

Choose a reason for hiding this comment

Choose a reason for hiding this comment

hajimehoshi left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

flimzy Apr 24, 2018 • edited Loading

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

myitcv commented Apr 24, 2018

dmitshur commented Apr 24, 2018 • edited Loading

myitcv commented Apr 28, 2018

myitcv commented Apr 28, 2018

myitcv commented May 5, 2018

antong commented May 29, 2018

antong commented Sep 3, 2018

nevkontakte commented Apr 17, 2022

myitcv commented Apr 23, 2018 •

edited

Loading

myitcv commented Apr 23, 2018 •

edited

Loading

flimzy Apr 24, 2018 •

edited

Loading

dmitshur commented Apr 24, 2018 •

edited

Loading