pygame
pygame copied to clipboard
pygame
Improved colliderect() function
Info
Follows #3324. One of #3337 The old colliderect implementation relied heavily on automatic argument "grouping" as a mean to implicitly construct the rect if more than 1 argument were passed. This new implementation relies upon direct access to the elements via FASTCALL, enabling faster argument handling and a more direct collision detection pipeline. I've also added another collision detection function for normalised rects. Using that speeds up the current implementation by an additional 5-6%.
Performance Stats
Overall the new implementation is 36.98% faster than the current one, but in the case of a single Rect argument(69.68% better) or 4 arguments can get up to 118% faster. Using CPython 3.6 or older i saw a 7.1% mean performance reduction(EDIT. now is up to par with 2.1.4 values) Using the code below i got the following results:
--- OLD---
--------- Not normalized Colliding rects ---------
Rect: 0.6726158000019495
4 args: 1.2384678999987955
2 args: 1.3053118999996514
1 tuple arg: 1.1832979999999225
--------- Normalized Colliding rects ---------
Rect: 0.6773214999993797
4 args: 1.2457533000015246
2 args: 1.309086199999001
1 tuple arg: 1.1767221999980393
--------- Non-colliding rects ---------
Rect: 0.6247191000002204
4 args: 1.2045317999982217
2 args: 1.29535400000168
1 tuple arg: 1.1573203999978432
13.090502099996229 seconds
--- NEW ---
--------- Not normalized Colliding rects ---------
Rect: 0.41285819999757223
4 args: 0.9083898999997473
2 args: 1.1966508999976213
1 tuple arg: 1.0859782999978052
--------- Normalized Colliding rects ---------
Rect: 0.4182092000010016
4 args: 0.6948287000013806
2 args: 1.031187399999908
1 tuple arg: 1.0486275000002934
--------- Non-colliding rects ---------
Rect: 0.3959212999980082
4 args: 0.7050670999997237
2 args: 1.0309612000019115
1 tuple arg: 1.0551780999994662
9.98385779999444 seconds
--- PYTHON 3.6.7---
--------- Not normalized Colliding rects ---------
Rect: 0.7407949
4 args: 1.2265097
2 args: 1.3928916
1 tuple arg: 1.3093952
--------- Normalized Colliding rects ---------
Rect: 0.7273856999999992
4 args: 1.1870614000000002
2 args: 1.2928631
1 tuple arg: 1.3021802999999998
--------- Non-colliding rects ---------
Rect: 0.7285181999999999
4 args: 1.1909159000000002
2 args: 1.2929525999999996
1 tuple arg: 1.344197600000001
13.7356662 seconds
I used this code:
import timeit
import pygame
pygame.init()
NUMBER = 10000000
r1 = pygame.rect.Rect(0, 0, 10, 10)
r2 = pygame.rect.Rect(5, 5, 10, 10)
r3 = pygame.rect.Rect(15, 15, 10, 10)
nnr1 = pygame.rect.Rect(10, 10, -10, -10)
nnr2 = pygame.rect.Rect(15, 15, -10, -10)
tottime = 0
GLOB = {"r1": r1, "r2": r2, "r3": r3, "nnr1": nnr1, "nnr2": nnr2}
print("\n--------- Not normalized Colliding rects ---------")
timed = timeit.timeit("nnr1.colliderect(nnr2)",
globals=GLOB, number=NUMBER)
print("Rect: ", timed)
tottime += timed
timed = timeit.timeit("nnr1.colliderect(15, 15, -10, -10)",
globals=GLOB, number=NUMBER)
print("4 args: ", timed)
tottime += timed
timed = timeit.timeit("nnr1.colliderect((15, 15), (-10, -10))",
globals=GLOB, number=NUMBER)
print("2 args: ", timed)
tottime += timed
timed = timeit.timeit("nnr1.colliderect((15, 15, -10, -10))",
globals=GLOB, number=NUMBER)
print("1 tuple arg: ", timed)
tottime += timed
print("\n--------- Normalized Colliding rects ---------")
timed = timeit.timeit("r1.colliderect(r2)",
globals=GLOB, number=NUMBER)
print("Rect: ", timed)
tottime += timed
timed = timeit.timeit("r1.colliderect(5, 5, 10, 10)",
globals=GLOB, number=NUMBER)
print("4 args: ", timed)
tottime += timed
timed = timeit.timeit("r1.colliderect((5, 5), (10, 10))",
globals=GLOB, number=NUMBER)
print("2 args: ", timed)
tottime += timed
timed = timeit.timeit("r1.colliderect((5, 5, 10, 10))",
globals=GLOB, number=NUMBER)
print("1 tuple arg: ", timed)
tottime += timed
print("\n--------- Non-colliding rects ---------")
timed = timeit.timeit("r1.colliderect(r3)",
globals=GLOB, number=NUMBER)
print("Rect: ", timed)
tottime += timed
timed = timeit.timeit("r1.colliderect(15, 15, 10, 10)",
globals=GLOB, number=NUMBER)
print("4 args: ", timed)
tottime += timed
timed = timeit.timeit("r1.colliderect((15, 15), (10, 10))",
globals=GLOB, number=NUMBER)
print("2 args: ", timed)
tottime += timed
timed = timeit.timeit("r1.colliderect((15, 15, 10, 10))",
globals=GLOB, number=NUMBER)
print("1 tuple arg: ", timed)
tottime += timed
print(tottime, " seconds")
New performance metrics with the added _pg_do_notnormalized_rects_intersect() function : (notice how the 4 args not normalized case went from 0.9083898999997473s down to 0.742086800000834s and the total time from 9.983s down to 9.734s)
--------- Not normalized Colliding rects ---------
Rect: 0.40322829999786336
4 args: 0.742086800000834
2 args: 1.1501164000001154
1 tuple arg: 1.025158200001897
--------- Normalized Colliding rects ---------
Rect: 0.40222820000053616
4 args: 0.6949547999975039
2 args: 1.0398936999990838
1 tuple arg: 1.0740198000021337
--------- Non-colliding rects ---------
Rect: 0.40684569999939413
4 args: 0.7239664000007906
2 args: 1.057071499999438
1 tuple arg: 1.0149845000014466
9.734554300001037 seconds
And most importantly the CPython 3.6 version is now basically up to par with the old colliderect implementation:
--------- Not normalized Colliding rects ---------
Rect: 0.6806898
4 args: 1.2065388000000001
2 args: 1.2573678000000001
1 tuple arg: 1.2698702000000006
--------- Normalized Colliding rects ---------
Rect: 0.6692895000000005
4 args: 1.1841387999999995
2 args: 1.2189887000000006
1 tuple arg: 1.2701791
--------- Non-colliding rects ---------
Rect: 0.6717291000000003
4 args: 1.2072072999999985
2 args: 1.2319604999999996
1 tuple arg: 1.2652488999999996
13.1332085 seconds
New stats after latest commit:
--------- Not normalized Colliding rects ---------
Rect: 0.40994370000044
4 args: 0.6392197999994096
2 args: 1.141009800001484
1 tuple arg: 1.0302646000018285
--------- Normalized Colliding rects ---------
Rect: 0.3991593999999168
4 args: 0.5655972999993537
2 args: 1.0292699000019638
1 tuple arg: 1.0392322999978205
--------- Non-colliding rects ---------
Rect: 0.3933633999986341
4 args: 0.5685177999985171
2 args: 1.0291066999998293
1 tuple arg: 1.0239384999986214
9.268623199997819 seconds
Latest test
--------- Not normalized Colliding rects ---------
Rect: 0.40383030000157305
4 args: 0.7056063999989419
2 args: 1.1588473999981943
1 tuple arg: 1.0563916999999492
--------- Normalized Colliding rects ---------
Rect: 0.40069299999959185
4 args: 0.669831899998826
2 args: 1.0328869999975723
1 tuple arg: 1.0233136999995622
--------- Non-colliding rects ---------
Rect: 0.39414380000016536
4 args: 0.6520156000005954
2 args: 1.0341171000000031
1 tuple arg: 1.0242848000016238
9.555962699996599 seconds
Latest test:
--------- Not normalized Colliding rects ---------
Rect: 0.38273279999884835
4 args: 0.6658422000000428
2 args: 1.1407941999987088
1 tuple arg: 0.9429583000001003
--------- Normalized Colliding rects ---------
Rect: 0.4201164999994944
4 args: 0.6050114999998186
2 args: 1.0299127000016597
1 tuple arg: 0.9367297000007966
--------- Non-colliding rects ---------
Rect: 0.39076250000107393
4 args: 0.6168821000010212
2 args: 1.0340894999990269
1 tuple arg: 0.9273178000003099
9.093149800000901 seconds