Bad performance when painting over existing tiles #4185

Describe the bug At least on big maps (1024x1024 tiles), painting over existing tiles with the stamp brush results in very poor performance (read: unusable).

To Reproduce

• Create a 1024x1024 maps, 100x100px tiles
• Use 2 tilesets of 100 separate tiles each. Each tileset has its own image ("Collection of images")
• Select all the 100 tiles of tileset 1. Fill the entire map with the bucket fill tool in random mode so that you have different tiles every where.
• Select one tile of tileset 2. Select the stamp brush tool. On the same layer, attempt to paint over existing tiles by clicking and dragging the mouse.
• Notice that performance is so bad it's unusable. Everything hangs for seconds on each mouse drag. The longer the drag, the longer the hang.

Performance is good when you clear a small patch before painting (with the rectangle select tool and hitting delete). So it seems to be a problem with drawing over existing tiles (drawing over empty tiles is fine).

Performance is also good if you paint on a new layer.

Expected behavior Painting should not provoke hangs.

Specifications:

• OS: Arch Linux
• Tiled Version: v1.11.2

I tried to see what was going on by running perf record while painting one tile every second. Please find the perf report attached. I'm not sure how helpful it is.

perf4.txt