Bad Performance due to Redundant Imports

[markhildreth-gravity]

We recently noticed that ruleguard was running very slowly for us. I was able to track it down to this code:

go-ruleguard/ruleguard/engine.go

Lines 175 to 190 in 5757289

	func (state *engineState) addCachedPackage(pkgPath string, pkg *types.Package) {
	state.pkgCache[pkgPath] = pkg
	// Also add all complete packages that are dependencies of the pkg.
	// This way we cache more and avoid duplicated package loading
	// which can lead to typechecking issues.
	//
	// Note that it does not increase our memory consumption
	// as these packages are reachable via pkg, so they'll
	// not be freed by GC anyway.
	for _, imported := range pkg.Imports() {
	if imported.Complete() {
	state.addCachedPackage(imported.Path(), imported)
	}
	}
	}

What we discovered was that when Imports() returns a slice of packages. For example, my main package might import mypackage and errors. But then when I recurse into mypackage, that package itself might import errors as well. This causes us to process the error package (e.g., add a value in the hash map and recursively go through the deps) a second time. With a large enough dependency tree, we end up spending minutes in code that is literally iterating through packages and hashing the package names.

I ended up creating a fix for us here, although not confident enough I understand the Go reflection system to know if it is a good solution.