> I should also point out that the marshal protocol takes care to be
> able to serialize lists, sets and frozensets correctly, the latter
> being added in version 2.4.  This despite the fact that code objects
> don't make use of these.

Code objects do use frozensets:

>>> def f(x):
...     return x in {1,2,3,4,5,6}
... 
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (x) 
              3 LOAD_CONST               7 (frozenset({1, 2, 3, 4, 5, 6})) 
              6 COMPARE_OP               6 (in) 
              9 RETURN_VALUE         

I don't think marshal supports any type that isn't (or hasn't been)
used in code objects.

> Obviously, this shows that marshal is still expected to work and be
> useful even if not for pickling code objects.

The module officially intended for general-purpose serialization is
pickle; if you use marshal for such a purpose, you're on your own.
If you think pickle is not good enough, your improvements are welcome.

> As expected, there is no difference between version 3 and 4 unless
> I employ the recode module to fold common subobjects.  This brings
> an additional saving of some 3% bringing the total reduction up to
> 28% and 18% respectively.

3% doesn't sound like a worthwhile improvement at all.

> The trick of using a bit flag on the type to indicate a slot
> reservation in the instance list is one that has been in use in
> CCP´s own "Marshal" format, a proprietary serialization format
> based on marshal back in 2002 (adding many more special opcodes
> and other stuff)

Why don't you release your "proprietary marshal" on pypi? You would
get feedback and a sense of whether people are interested in your
approach.