I'm wondering if being concerned about the 100 byte overhead is a form of premature optimisation. Hypothetically perl should be able to determine if the arrays are going to have their size changed, or the arrays will be preserved or whatever, and if possible use a something more efficient.
Actually here is where Perl5 could steal a trick from Python and add a Tuple data type, that is an array like data type that is of constant size and contains constant values. Having such a data type would make it possible to write ST's and be MUCH more efficient, since the constantness of the structure would allow the structure to be represented in a much more efficient way. Much of the size issues of perls data structures are due to its dynamic nature, and the fact that we optimise for speed and not space.