Fix partition algorithm preparation step.
Added coverage cache to speed up the partitioning.