Consider making ty::t "fatter"

[pcwalton]

We could possibly save some time over our structural hashing and equality code if we revamped ty::t to become a packed u64 value in something approaching this form:

• nil, bot, bool, ints, uints, floats, str, self, type, opaque box become constant values
• estr, box, uniq, vec, ptr, rptr become (type tag: u8, mutability flags: u8, vstore/region ID: u16, enclosed type: u32)
• enum, iface, class, res become (type tag: u8, crate ID: u8, substs ID: u16, node ID: u32)
• tup becomes (type tag: u8, tup ID: u32)
• rec becomes (type tag: u8, fieldset ID: u16, tup ID: u32)
• fn becomes (type tag: u8, purity/proto/retstyle flags: u8, constrs ID: u16, signature ID: u32)
• param becomes (type tag: u8, crate ID: u8, parameter ID: u16, node ID: u32)
• var becomes (type tag: u8, vid: u32)
• constr becomes (type tag: u8, constrs ID: u16)
• opaque closure ptr becomes (type tag: u8, closure kind: u8)

We need several side tables:

• A hash table of regions found in the program.
• A table of linearized substs. The table contains subsituted types; at each node is a hash table (or an association list) of self_r and self_ty to ID.
• A fieldset table.
• A table of vstores and regions.
• A table of linearized tuples.
• A table of linearized function types. The return value comes first, followed by the arguments.
• A table of constraints. Doesn't need to be fast; we rarely if ever use constraints.

By "linearized" I mean that the type in question is converted into a list and concatenated into one large string of types encoded in this way. So, for example, a list of 4 types would be 16 bytes long (but note that there are some complications with function parameter modes). This byte string forms the key in the table; thus there is never any need to traverse pointers when doing comparisons for equality, as we simply compare byte strings.

This is very rough, but I think it might speed things up.

[catamorphism]

Nominating for "maturity #4 - well-covered".

[graydon]

possible perf win, not blocking ability-to-measure-quality.

[catamorphism]

Bug triage. Not a release blocker.

[steveklabnik]

triage: unsure what the situation is today compared to then.

[arielb1]

TypeVariants is 4 words ATM (= rustc 1.2.0).

[brson]

This is so ancient I imagine it has nothing to do with today's rustc.

[jonas-schievink]

From a quick look, TypeVariants still exists and is still 4 words large (1 reference, a fat pointer (3 pointers in total) and a DefId which is 64 bits)