It's actually super simple. You just use subbitmaps instead of bitmaps.
The biggest difficulty is putting non-standard size tiles into the same bitmap. (Check that awesome packer tool in that other thread the guy ported to Allegro.)
If the tiles are the same size, it's as simple as loading the bitmap, and then running one or two for loops to create the sub-bitmaps into your array.
Performance WILL be better. Each bitmap is a texture. If you request a texture change too often (ala every draw call) its much slower and represents a bottleneck. I ran into that issue when I was making a Minecraft space clone way back when Minecraft was in its infancy. I called a texture change per block and it was much faster when I tried to reduce swaps by lining up similar blocks into one call. (I didn't realize back then I could use a texture atlas instead. Oh, youth...)
(Not the best pics, but I lost most of them in a HDD crash.)