in reply to AoHoAoH... am I delusional?
Drop the extra arrays you're currently using to preserve order, and then use Tie::IxHash.
I agree, but trying to tie nested elementss can be a little bit of a pain. I'd recommend anyone considering this to read Preserving order for nested hashes using Tie::IxHash.