Fix: Improve performance of content destination collision detection.

[erikgeiser]

This PR fixes #387 and #393 by reducing the algorithmic complexity of the content destination collision detection. Previously when appending an element, the destination was compared to all other elements in the content list. Now we simply append and check for collisions once at the end with a single pass through all elements.

For 150000 files with random destinations, the performance compares as follows:

Before: BenchmarkExpandContentGlobs-4   	       1	2982879539110 ns/op
Now   : BenchmarkExpandContentGlobs-4   	       1	9052880061 ns/op

That's a 320x improvement from 50 minutes to 9 seconds for extreme use cases!

Here's the benchmark code:

func BenchmarkExpandContentGlobs(b *testing.B) {
	contents := testContents(150000)
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		_, err := files.ExpandContentGlobs(contents, true)
		if err != nil {
			b.Fatalf("expand content globs: %v", err)
		}
	}
}

func testContents(n int) files.Contents {
	contents := make(files.Contents, n)

	for i := 0; i < n; i++ {
		contents[i] = &files.Content{
			Source:      "../testdata/whatever.conf",
			Destination: randomString(),
		}
	}

	return contents
}

const letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

func randomString() string {
	b := make([]byte, 5+rand.Intn(20))
	for i := range b {
		b[i] = letters[rand.Intn(len(letters))]
	}
	return string(b)
}

Thank you @mjmjelde for reporting this.

[codecov]

Codecov Report

Merging #388 (b29e3c8) into master (685352f) will increase coverage by 0.00%.
The diff coverage is 86.36%.

@@           Coverage Diff           @@
##           master     #388   +/-   ##
=======================================
  Coverage   64.66%   64.67%           
=======================================
  Files          14       14           
  Lines        1834     1826    -8     
=======================================
- Hits         1186     1181    -5     
+ Misses        512      509    -3     
  Partials      136      136           

Impacted Files	Coverage Δ
internal/cmd/package.go	0.00% <ø> (ø)
files/files.go	95.45% <85.71%> (-0.20%)	⬇️
nfpm.go	86.36% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 685352f...b29e3c8. Read the comment docs.

[djgilcrease]

LGTM

[erikgeiser]

I added a commit that removes the duplicate Validate call to fix #393.

[caarlos0]

amazing! thanks!