Performance is these cases is mainly determined by your database queries. Having a microflow that takes 2.5 seconds to change 1 object seems way to slow to me.
Things you can take into account to optimizing your queries are:
Normally updating association is fast.
You can also take a look at loops. Limit the retrieved list in stead of getting all and have a split inside the loop. Looping thru 200 records is slower than getting 20 objects you want and update them.
The other point is the transaction size. Is the 500 update slower than 500 times one update? Server memory may be in the way. Monitor that.
Maybe your database needs truncating, reindexing, vacuum cleaning, rebuilding?
Add an autonumber attribute to your product entity and sort by it on your retrieval.