Terrain Generation Please Help

I am making a terrain generation game like Terraria, it currently uses small blocks (5x5). It generates three types of terrain, Dirt, Stone and caverns. How i have it set up, is one block goes down the side of the window, and spawns smaller blocks which go across the window spawning the actual terrain at random. The cavern generators are blocks that move randomly and destroy the terrain they touch and eventually disappear. The only problem is that it is REALLY slow. The generation can take up to 15 minutes, and the map isn't that big... Is there any way to generate it faster? Any help appreciated, Thanks!
Comments