As a further data point, the attached patch replaces uses of PrimMonad with ST, and speeds performance back to 0.015 seconds, so it's clearly the use of primitive, and not the switch from uvector to vector, that causes the performance loss.