So long as we specify that a decorated interval consist
of an 'undecorated' interval together with an associated
decoration, we have said nothing about how that decoration
appears or how it is associated with the interval.
An adequately clever implementation might choose to store
the interval part in one place & the decoration somewhere
else & count on a similarly smart compiler to maintain
the association. So, for example, arrays of intervals
parts could be packed up efficiently on power-of-two
boundaries with arrays of their decorations stored
elsewhere (perhaps ALSO on smaller power-of-two
boundaries).
Such an approach has its merits (it eliminates all your
valid complaints) & its costs (the compiler has to keep
track of things & the hardware assist needs an extra
address path).
But if our definition of decorated intervals is kept as
an abstraction, this sort of thing is an implementation
possibility.