Image tag sorting optimizations

[cristian-radu]

Describe the bug
A clear and concise description of what the bug is.

In Weave Cloud, we are seeing some issues with workload image tag information not loading during busy times.

More details on this here:
https://weavesupport.zendesk.com/agent/tickets/534

Fluxd logs show:
caller=logging.go:69 component=upstream method=ListImagesWithOptions error="getting all workloads: context deadline exceeded"

Looking at the CPU profile at the time this is happening (see ticket attachments), it would seem that we could do with some optimizations to the algorithm in order to prevent the request deadlines from being exceeded.

[squaremo]

There is already an optimisation for the API calls that Weave Cloud uses -- but it was not followed through. See #2211, which will land in 1.14.0 shortly. This enables a new API method, ListServicesWithOptions, that greatly cuts down the number of workloads observed during a rollout. (The deploy view uses the API method ListImagesWithOptions, which was already enabled.)

If you don't think that will help, then you'll need to be more precise about where you think the inefficiency lies -- "we could do with some optimizations to the algorithm" is not much to go on.

[cristian-radu]

#2211 does look like it would help.
As for optimizing the image sorting, see below for an example.

func randomImages() []Info {
	rand.Seed(time.Now().UnixNano())
	t := time.Now()
	imgs := []Info{}

	for i := 1; i < 500; i++ {
		imgs = append(imgs, mustMakeInfo(fmt.Sprintf("my/Image:%s", strconv.FormatInt(int64(i), 10)), t.Add(-time.Duration(rand.Intn(10080))*time.Minute)))
	}

	return imgs
}

func BenchmarkSort(b *testing.B) {
	var sortImgs = randomImages()
	for n := 0; n < b.N; n++ {
		Sort(sortImgs, NewerByCreated)
	}
}

func BenchmarkSortSliceStable(b *testing.B) {
	var sortSliceStableImgs = randomImages()
	for n := 0; n < b.N; n++ {
		sort.SliceStable(sortSliceStableImgs, func(i, j int) bool { return sortSliceStableImgs[i].CreatedAt.Before(sortSliceStableImgs[j].CreatedAt) })
	}
}

go test -bench=BenchmarkSort
goos: linux
goarch: amd64
pkg: github.com/weaveworks/flux/image
BenchmarkSort-4 5000 234358 ns/op
BenchmarkSortSliceStable-4 300000 4791 ns/op
PASS
ok github.com/weaveworks/flux/image 3.432s

[squaremo]

Your benchmark is flawed -- it runs all but the first trial on an already sorted slice.

Making these changes ...

• constructing a slice at the start of the trial, rather than once for all trials
• using b.N as the size of the slice, rather than the number of iterations
• inlining the equivalent of NewByCreated rather than the simplified version
• adding a benchmark for sort.Slice

.. it's apparent that sort.Slice and sort.Sort are about the same (which makes sense to me -- they differ in convenience of use, but use the same algorithm), while sort.SliceStable is about half as fast. Looking at the docs, sort.SliceStable has an extra log n term.

[squaremo]

@cristian-radu It's possible (and a reasonable suggestion) that each sort could be made a bit more efficient. I think there's room for reducing the number of sorts undertaken -- the most efficient sort being the one you don't have to do -- so I am inclined to start looking there.

[squaremo]

Your benchmark is flawed

.. and so was mine -- I should not use b.N for the size of the input, but for the number of repetitions (i.e., change 2. above is bogus). Nonetheless, the results are more or less the same.

[2opremio]

Closing this, since #2338 seems to have sorted it out. @cristian-radu is this still a problem? Please let me know.