A "contextual serialization" mechanism was added in #3601 and #3673 that allows serializing certain objects once even when they occur multiple times within a larger structure. The only place we use this mechanism in cirq itself is for FrozenCircuit, since a given circuit can be included as a subcircuit multiple times within a larger circuit.

On internal benchmarks, the existing contextual serialization mechanism is a major performance bottleneck, in particular the has_serializable_by_key function takes a significant amount of time even when no contextual serialization is needed because it traverses the entire object being serialized and makes lots of isinstance calls. The reason for these pre-checks is that the context serialization works by changing the outer-most serialized object to instead be a _ContextualSerialization instance, which includes all SerializableByKey instances in an object_dag list created from a pre-order traversal. The current implementation also has the downside that during serialization it finds already-seen instances by traversing the object_dag list itself, potentially incurring quadratic overhead if the list grows large; this is necessary because SerializableByKey instances are not guaranteed to be hashable (though in practice the only existing case of FrozenCircuit is hashable).

This mechanism can be simplified by simply keeping track of SerializableByKey instances as we encounter them and associating them with keys. The first time such an instance is encountered during serialization it is assigned a key and then serialized as a "value": {"cirq_type": "VAL": "key": key, "val": val} where key is the assigned key and val is the normal serialization of the object. If the same instance is encountered later during serialization, it is serialized as a "reference": {"cirq_type": "REF", "key": key}. We require that SerializableByKey instances be hashable so that the internal memoization can use a dict instead of a list, to avoid quadratic overheads from repeatedly searching for memoized instances. This would potentially allow us to use this mechanism on many more types without worrying about the runtime impact. Note that this requires that the traversal order when deserializing be consistent with that used when serializing, so that we never encounter a REF before the corresponding VAL. AFAICT this will always be the case, because the json library respects the order in which object keys appear when deserializing (functions like json.load can take an object_pairs_hook which takes key-value pairs as a list, and when these are collected in a dict and passed to object_hook the python dict implementation also preserves order).

This change gives a significant improvement in serialization performance; on one internal benchmark the time spent in json_serialization.to_json when profiling dropped from 719s to 39s for an 18x speedup.

There's still a bit of work to do to clean up json test cases since in a few places we already had existing .json_inward tests and I need to figure out how to preserve those as well as moving the existing .json tests to be .json_inward tests. But otherwise this is ready for review and would be good to discuss the proposed approach.