Trying CPU only vs. GPU only, CPU is now 1:49 where GPU is 1:57 (GPU has never been slower than CPU before). In the new build. I overwrote yesterday's build after doing the first benchmark as I wasn't expecting problems.

Also, what happens without denoising enabled?

Looks like denoise is a major part of the issue.

Turning off denoise eliminates the border tile mark issue.

CPU only without denoise drops from 1:49 to 0:57
GPU only without denoise drops from 1:57 to 0:30 (!)
CPU+GPU without denoise drops from 1:07 to 0:25.

I tested a production scene of mine with todays build and the build from the day before yesterday.
Build: e73647bf5b44 (today)
GPU+CPU with denoise: 9:23
GPU+CPU without denoise: 8:43

Build: 12da679fa094 (17.06.2019)
GPU+CPU with denoise: 10:02
GPU+CPU without denoise: 9:36

So in my tests the todays build renders 6,9% faster with denoise on and 9,5% faster without denoise.
The difference between denoise on and off is about 40sec in the todays build.
The difference between denoise on and off is about 26sec in the build from the 17.06.2019.
Visual in the renderview there is one difference with the renderbuckets. If you have denoise on the buckets are also shown and disapear after the bucket is denoised. So a better visual feedback.
From may side no complaints.

My computer specs are:
Windows 10 Pro
Geforce GTX 1080 Ti
AMD Threadripper 1950X 16Cores 64GB RAM

Ok, thanks to Ray's secret build stash I was able to get a build from a couple of days ago and do a proper test with my quick benchmark file, and the upshot is that the recent changes had absolutely no effect on performance in Cycles for this simple scene on my system here.

I also rendered the standard BMW test scene and it did show a significant improvement with the new changes. I tried to render the Classroom benchmark but the version I have is incompatible with 2.80 (all the chair instances get deleted when you open it etc.)

So I apologize for the false alarm on the performance regression.

The issue of the queued up denoise tiles remains, and is confusing because you can't tell if a tile is still actually rendering or simply waiting for its data dependency on adjacent tile data to be fulfilled. I suppose it's not terrible the way it is now, it was just a bit surprising to see. I think it still makes more sense to only highlight the tile when the task is actually ready to run.

I don't suppose we could color the tile corners differently for render tasks and denoise tasks? Like, have green corners for denoise vs. the orange render ones? That would be super cool.

Just for completeness, here's the result of the performance tests. There are two runs for each test for each Blender version.

Old: 2.80 (sub 74), branch: HEAD, commit date: 2019-06-17 18:32, hash: rB28b06b6a05f7
New: 2.80 (sub 74), branch: master, commit date: 2019-06-19 13:06, hash: rB72690bbeca85

the tests were all with the attached file and show no significant change between versions, apart from the last two which were using the BMW scene from the benchmark suite.

Test			Old 1	Old 2	New 1	New 2
GPU + Denoise		1:56.66	1:55.94	1:54.87	1:55.36
GPU			0:29.36	0:29.45	0:29.28	0:29.19
CPU + GPU + Denoise	1:09.21	1:07.98	1:07:43	1:08.53
CPU + GPU		0:23.36	0:24.96	0:24.56	0:24.65
CPU + Denoise		1:50.94	1:47.32	1:45.92	1:44.70
CPU 			0:56.36	0:56.76	0:58.12	0:56.41

BMW CPU+GPU		2:42.27		2:04.53	
BMW GPU			3:05.96		2:19.02

If you setup Cycles to do a 10,000x10,000 pixel render with 8x8 tiles, then pretty soon things go wrong (with the render view) when the number of active tiles becomes very large due to all the pending denoise operations. It starts displaying a semi-random assortment of the active tiles, some blink on and off, etc. Example:

Edit: the render of 1.5 million tiles finished in about 90 minutes and as far as I can see all the denoise tasks completed successfully.