for most games accurate collision is not needed, I use a simple and fast box-collide routine with variable box-sizes, no optimizations yet - works great. I check all collisions every frame, no problems so far - there are more critical parts than this, moving 100 enemy-bullets takes more raster-time than 100 checks vs. player!
test for slower objects (most enemy-bullets or upgrades) you can split onto 2 frames