Tracking Vector Optimizations (3343)

[GalacticEmperor1]

Issue №3343 opened by itzpr3d4t0r at 2022-07-26 16:44:20

# Info

(This follows # 3324 rationale)
The Vector theme has come up multiple times on Discord: we concluded that vectors are underrated and should use more love from the community and us interns.

As a pygame user, I've generally avoided using Vector2 for my projects in favour of either an x and y attribute in a slotted class or a general pos. This is a shame because I've always been fascinated by what vectors can offer in terms of functionality and code simplification and always wanted to switch.
The reason is performance: the same program with vectors did not yield good performance compared to a vector-free program.

I have therefore started an effort to optimize the current vector functions while keeping compatibility with the current use, all in hope of encouraging people to do the switch over without suffering any performance regressions.

---

Comments

# # itzpr3d4t0r commented at 2022-08-01 09:16:09

An update on this. If we want to optimize many functions inside math.c, i will need new API functions that are more performant. That is because using new API reduces code duplication, improves code clarity and makes it more performant.
I have already started work on three new functions for extracting ints from objects, but for vectors i will need three more functions for doubles, as vectors use double as coords and a user is likely to pass vector-like objects that use doubles as well.

For now work on vector improvements is therefore paused until these new functions get implemented, approved and merged.

[lordmauve]

I did some relevant analysis here: lordmauve/wasabi2d#17

The big trick I got to get really good performance out of my implementation was to use Cython's @cython.freelist(32) decorator which keeps a freelist of freed instances, which reduces the use of the allocator, e.g. within numerical expressions that use temporaries.

we concluded that vectors are underrated and should use more love

I've never used Vector in my games because it is mutable. Numerical types should not be mutable in Python imho. Indeed, they should be hashable:

images = {
   Vector2(0, -1): 'player_up',
   Vector2(0, 1): 'player_crouch',
   Vector2(-1, 0): 'player_l',
   Vector2(1, 0): 'player_r',
}

Also, Pygame is not floating point throughout. Vector composes really badly with other parts of Pygame:

>>> r = Rect(0, 0, 10, 10)
>>> r.center = Vector2(2.5, 2.5)
>>> r.center
(3, 3)

So I would say Vector is not underrated, it's a wart.

[gresm]

Hey @lordmauve

Also, Pygame is not floating point throughout. Vector composes really badly with other parts of Pygame

Try pygame.FRect instead.

I've never used Vector in my games because it is mutable. Numerical types should not be mutable in Python imho. Indeed, they should be hashable

That would break nearly all of the code using vectors (a lot!). There were proposals for frozen vectors, but no real work was done in that direction.

The big trick I got to get really good performance out of my implementation was to use Cython's @cython.freelist(32) decorator which keeps a freelist of freed instances

Could you test #3292? I tried doing benchmarks, but the results were inconclusive.

[lordmauve]

Try pygame.FRect instead.

Oh, do we have that now? We called it ZRect when we implemented it in Pygame Zero. Excellent! I'm still going to keep my implementation because it will return (immutable) vectors for the point accessors.

That would break nearly all of the code using vectors (a lot!). There were proposals for frozen vectors, but no real work was done in that direction.

Oh, I'm not saying change Vector2 in place. Vector2 can't be touched, but a new class could be added. Vector2 could be deprecated, demoted in docs, etc.

[gresm]

FRects were added in pygame-ce 2.2.0.
Mutable vectors have a lot of proper applications where it's more sensible to use them over immutable ones (for example, sprite positions), so I disagree with deprecating them. That doesn't mean that frozen vectors don't have a reason to exist. There are many places, where returning a frozen vector would be nicer than a tuple, which we currently do.

[aatle]

I agree that frozen vectors are the way to go. After experiencing both (mutable pygame.Vector2 and immutable pymunk.Vec2d), I can say that mutability of vectors is often more of a liability, and I don't see any applications where they are really better.

• Mutable vectors being shared can result in bugs where a vector is being changed by some other code, or where a shared is replaced with a copy
• When dealing with collections of vectors, the collection has to be deepcopied instead of shallow copied (the latter would cause a bug)
• Mutable vectors are not hashable
• Vectors are more of a numeric type, like int and complex, so it should be immutable
• There has to be double the amount of methods to operate on vectors, sometimes leaving holes in functionality, or ambiguity (such as .from_polar() and .scale_to_length(): both are actually in-place and have no immutability counterpart)

[Starbuck5]

I don't have numbers on me to back this up, but I expect mutable vectors are more performant because they require fewer allocations.

# 2 instances vs 3 instances
vec1 += vec2
vec3 = vec1 + vec2

Another thing I would like to work on with performance is vectorizing the vectors-- using SIMD on them. If you multiply 2 vector2s together it should be able to very efficiently load that into a SIMD register and do that in parallel. I've read that modern computers have dual port ALUs so they can do multiple operations at once, so this might not be as good a boost as I hope. The real win would be if you could have a group of x vectors and apply an operation on them all in parallel.

[Starbuck5]

I did some relevant analysis here: lordmauve/wasabi2d#17

Interesting stuff.

*** wasabigeom.vec2 ***
Addition: 0.04us per op (10000000 samples)
In-place addition: 0.03us per op (10000000 samples)
Dot: 0.04us per op (5000000 samples)
Normalized: 0.04us per op (5000000 samples)

pygame-ce 2.5.3 (SDL 2.30.12, Python 3.9.5)
*** pygame Vector2 ***
Addition: 0.05us per op (5000000 samples)
In-place addition: 0.03us per op (10000000 samples)
Dot: 0.09us per op (5000000 samples)
Normalized: 0.09us per op (5000000 samples)

*** numpy ***
Addition: 0.43us per op (500000 samples)
In-place addition: 0.76us per op (500000 samples)
Dot: 1.07us per op (200000 samples)
Normalized: 3.65us per op (100000 samples)

*** tuples ***
Addition: 0.07us per op (5000000 samples)
In-place addition: 0.06us per op (5000000 samples)
Dot: 0.06us per op (5000000 samples)
Normalized: 0.13us per op (2000000 samples)

This is what I get today (with -O). Impressive performance from wasabigeom.