Suspected performance issue in the python code to insert Regions into Shapes

[engineeringvase]

In one line: When the Shapes class's insert function with a Region as argument, there seems to be an accumulating amount of time needed for subsequent executions.

Put more plainly: First

someShapes.insert(someRegion)

is very fast, after 1000 insertions it gets slower, after 2000 it gets slower still, ... I made a demo script to test this, see the script and the outcome below. The amount of time needed for the operation seems to increase linearly with the number times it has been executed in the past. For myself I found a workaround: insert each part of the region separately:

for shape in someRegion.each():
    someShapes.insert(shape)

Note, I tried this with the python klayout.db installed through pip (yesterday), and also in the latest KLayout 0.30.2 through the Macro Developer, the exact same linear increase is observed in both cases.

Demo script

import klayout.db as pya
import datetime

# Create layout, cell and layer
ly   = pya.Layout()
l1   = ly.layer(1,0)
main = ly.create_cell("Main")

# Demonstration: add tons of boxes
box1 = pya.Region(pya.Box(4000))
box2 = pya.Region(pya.Box(2000,8000))

print("")
print("## Problematic case")
t0 = datetime.datetime.now()
for i in range(1,20001):
    
    # Time keeping for demo
    if i%1000 == 0: 
        timecost = (datetime.datetime.now() - t0).total_seconds()
        print("Iteration", i, ", Time per 1000 iterations:", timecost)
        t0 = datetime.datetime.now() 
        
    # Problematic execution
    main.shapes(l1).insert(box1)
    main.shapes(l1).insert(box2)
    

print("")
print("## Alternative execution")
t0 = datetime.datetime.now()
for i in range(1,20001):
    
    # Time keeping for demo
    if i%1000 == 0: 
        timecost = (datetime.datetime.now() - t0).total_seconds()
        print("Iteration", i, ", Time per 1000 iterations:", timecost)
        t0 = datetime.datetime.now() 
        
    # Alternative execution
    for shape in box1.each():
        main.shapes(l1).insert(shape)    
    for shape in box2.each():
        main.shapes(l1).insert(shape)    

Script outcome

## Problematic case
Iteration 1000 , Time per 1000 iterations: 0.05159
Iteration 2000 , Time per 1000 iterations: 0.107194
Iteration 3000 , Time per 1000 iterations: 0.16091
Iteration 4000 , Time per 1000 iterations: 0.212394
Iteration 5000 , Time per 1000 iterations: 0.267079
Iteration 6000 , Time per 1000 iterations: 0.320597
Iteration 7000 , Time per 1000 iterations: 0.374572
Iteration 8000 , Time per 1000 iterations: 0.426344
Iteration 9000 , Time per 1000 iterations: 0.482823
Iteration 10000 , Time per 1000 iterations: 0.530373
Iteration 11000 , Time per 1000 iterations: 0.578954
Iteration 12000 , Time per 1000 iterations: 0.635411
Iteration 13000 , Time per 1000 iterations: 0.694576
Iteration 14000 , Time per 1000 iterations: 0.747631
Iteration 15000 , Time per 1000 iterations: 0.799844
Iteration 16000 , Time per 1000 iterations: 0.847128
Iteration 17000 , Time per 1000 iterations: 0.932573
Iteration 18000 , Time per 1000 iterations: 0.960807
Iteration 19000 , Time per 1000 iterations: 1.006917
Iteration 20000 , Time per 1000 iterations: 1.058458

## Alternative execution
Iteration 1000 , Time per 1000 iterations: 0.022474
Iteration 2000 , Time per 1000 iterations: 0.022412
Iteration 3000 , Time per 1000 iterations: 0.022726
Iteration 4000 , Time per 1000 iterations: 0.022411
Iteration 5000 , Time per 1000 iterations: 0.023426
Iteration 6000 , Time per 1000 iterations: 0.022177
Iteration 7000 , Time per 1000 iterations: 0.0224
Iteration 8000 , Time per 1000 iterations: 0.022154
Iteration 9000 , Time per 1000 iterations: 0.024215
Iteration 10000 , Time per 1000 iterations: 0.022154
Iteration 11000 , Time per 1000 iterations: 0.021894
Iteration 12000 , Time per 1000 iterations: 0.022275
Iteration 13000 , Time per 1000 iterations: 0.022152
Iteration 14000 , Time per 1000 iterations: 0.022036
Iteration 15000 , Time per 1000 iterations: 0.022192
Iteration 16000 , Time per 1000 iterations: 0.022265
Iteration 17000 , Time per 1000 iterations: 0.026411
Iteration 18000 , Time per 1000 iterations: 0.021993
Iteration 19000 , Time per 1000 iterations: 0.022269
Iteration 20000 , Time per 1000 iterations: 0.022074

[klayoutmatthias]

Hi @engineeringvase,

thanks for bringing this up.

It's in there by design, but I guess it can be modified.

First of all, there is a simple workaround: use "start_changes" and "end_changes" on the Layout:

try:
    ly.start_changes()

    print("")
    print("## Problematic case")
    t0 = datetime.datetime.now()
    for i in range(1,20001):
      
        # Time keeping for demo
        if i%1000 == 0: 
            timecost = (datetime.datetime.now() - t0).total_seconds()
            print("Iteration", i, ", Time per 1000 iterations:", timecost)
            t0 = datetime.datetime.now() 
          
        # Problematic execution
        main.shapes(l1).insert(box1)
        main.shapes(l1).insert(box2)
      
finally:
    ly.end_changes()

this will bring the runtimes down in the first case.

The reason is that Region is not just a container for shapes, it has other faces. For example, it can represent a hierarchical layer in a layout. If you insert that one into a Shapes container, it will flatten this layer and insert the flat shapes into the Shapes container.

As a special (but not unusual) case, the Region may refer to a layer from the same Layout object than the one the Shapes container lives in. This needs special care as recursively iterating the source layer needs a properly built cell tree, region lookup trees and other auxiliary structures. In that case, there is an interaction between reading and writing (which invalidates these structures) with potentially harmful side effects.

The mitigation strategy is to lock the layout's lookup structures during the insert process, but that comes with a rebuild of the lookup structures at the beginning of every insert. As this takes O(n) time (n = number of shapes), you get the increasing time adder. Adding another lock around the sequence will prevent that. The "insert" method alone can't do that as it does not know when you're finished.

Having said that, I think I can remove the internal locking if the copy source is a separate Shapes object or a different Layout. But not in all cases.

I should say that "start_changes ... end_changes" improves performance in many other cases too. But as some functions need up-to-date cell trees and other structures, you should not use that in scenarios where you have for example region queries mixed with shape inserts on the same layer. The region queries would see the original lookup trees before you used "start_changes", not the current ones. The same is true for parent/child relationships of cells or cell bounding boxes.

Matthias

[engineeringvase]

Dear Matthias,

Thank you so much for you for your reply. I will add I am extremely impressed, for years now, with the software, and cannot thank you enough for making it available. Regarding this point, I am a bit confused still.
Below I have made an adapted version of the script, running first the slow method, then the faster (each shape) method, then again the slow method. As you can see, the speed is not determined by the total size of the layout, of the number of shapes added, but simply to the number of regions added.
Does the layout then keep some log of the number of regions inside, and are they not "flattened" into their shapes internally? You mention that the rebuild of the lookup structures scales with the O(n) time (n = number of shapes), but that seems not to be the case, since I am also adding shapes in the middle section, just by a different method. Could you be so kind to enlighten me what I am missing.
To be clear, don't feel obliged to change anything, I understand the most efficient way to do things is write a small helper function. I also only have issues for this particular application, I never had issues in the past. I do not doubt you have many valid reasons to have built things this way.

Helper function

def insert_region(cell, layer, region):
    for shape in region.each():
        cell.shapes(layer).insert(shape)

Demo script 2

import klayout.db as pya
import datetime

# Create layout, cell and layer
ly   = pya.Layout()
l1   = ly.layer(1,0)
main = ly.create_cell("Main")

# Demonstration: add tons of boxes
box1 = pya.Region(pya.Box(4000))
box2 = pya.Region(pya.Box(2000,8000))

print("")
print("## Problematic case")
t0 = datetime.datetime.now()
for i in range(1,10001):
    
    # Time keeping for demo
    if i%1000 == 0: 
        timecost = (datetime.datetime.now() - t0).total_seconds()
        print("Iteration", i, ", Time per 1000 iterations:", timecost)
        t0 = datetime.datetime.now() 
        
    # Problematic execution
    main.shapes(l1).insert(box1)
    main.shapes(l1).insert(box2)
    
    
print("")
print("## Alternative execution")
t0 = datetime.datetime.now()
for i in range(1,10001):
    
    # Time keeping for demo
    if i%1000 == 0: 
        timecost = (datetime.datetime.now() - t0).total_seconds()
        print("Iteration", i, ", Time per 1000 iterations:", timecost)
        t0 = datetime.datetime.now() 
        
    # Alternative execution
    for shape in box1.each():
        main.shapes(l1).insert(shape)    
    for shape in box2.each():
        main.shapes(l1).insert(shape)    
        
        
print("")
print("## Problematic case")
t0 = datetime.datetime.now()
for i in range(1,10001):
    
    # Time keeping for demo
    if i%1000 == 0: 
        timecost = (datetime.datetime.now() - t0).total_seconds()
        print("Iteration", i, ", Time per 1000 iterations:", timecost)
        t0 = datetime.datetime.now() 
        
    # Problematic execution
    main.shapes(l1).insert(box1)
    main.shapes(l1).insert(box2)        

Script outcome 2

## Problematic case
Iteration 1000 , Time per 1000 iterations: 0.051602
Iteration 2000 , Time per 1000 iterations: 0.109496
Iteration 3000 , Time per 1000 iterations: 0.169313
Iteration 4000 , Time per 1000 iterations: 0.219246
Iteration 5000 , Time per 1000 iterations: 0.275647
Iteration 6000 , Time per 1000 iterations: 0.330587
Iteration 7000 , Time per 1000 iterations: 0.38634
Iteration 8000 , Time per 1000 iterations: 0.45064
Iteration 9000 , Time per 1000 iterations: 0.501468
Iteration 10000 , Time per 1000 iterations: 0.554441

## Alternative execution
Iteration 1000 , Time per 1000 iterations: 0.02329
Iteration 2000 , Time per 1000 iterations: 0.023242
Iteration 3000 , Time per 1000 iterations: 0.023486
Iteration 4000 , Time per 1000 iterations: 0.022773
Iteration 5000 , Time per 1000 iterations: 0.025302
Iteration 6000 , Time per 1000 iterations: 0.022686
Iteration 7000 , Time per 1000 iterations: 0.022819
Iteration 8000 , Time per 1000 iterations: 0.023164
Iteration 9000 , Time per 1000 iterations: 0.02532
Iteration 10000 , Time per 1000 iterations: 0.02224

## Problematic case
Iteration 1000 , Time per 1000 iterations: 0.604109
Iteration 2000 , Time per 1000 iterations: 0.662427
Iteration 3000 , Time per 1000 iterations: 0.721284
Iteration 4000 , Time per 1000 iterations: 0.774946
Iteration 5000 , Time per 1000 iterations: 0.845096
Iteration 6000 , Time per 1000 iterations: 0.897098
Iteration 7000 , Time per 1000 iterations: 0.9507
Iteration 8000 , Time per 1000 iterations: 1.004529
Iteration 9000 , Time per 1000 iterations: 1.058148
Iteration 10000 , Time per 1000 iterations: 1.130795

[klayoutmatthias]

Hi @engineeringvase,

Depending on the KLayout version you use, the Box objects you add may be of a different kind when you add them through iteration (Polygon with properties) or not (Polygon). I have not checked the details yet, but if that is the case, these variants form different slots and O(n) applies to every slot individually. Hence the slow variant continues where it ended.

Matthias