[SPARK-4480] Avoid many small spills in external data structures (again)

I accidentally closed the PR at #3353 and can't re-open it for some reason. The changes here are identical the the ones there. I'll merge this into master and 1.2 once the tests pass.