perf: Subtype checking should not perform quadratic traversal

[christoph-dfinity]

The equality check performed at the beginning of subtype checking:

candid/rust/candid/src/types/subtype.rs

Lines 39 to 41 in 30c3886

	if t1 == t2 {
	return Ok(());
	}

should only do a cheap check for "physical" equality (using ptr_eq on anything non-primitive).

Otherwise we do full traversals of complex nested types at every level (quadratic).

[sasa-tomic]

Here is what Opus 4.6 says about this optimization:

Here's my analysis of issue #603:
The problem: Line 49 of subtype.rs does if t1 == t2. Since Type is Rc with derived PartialEq, this performs a deep structural comparison of the entire type tree. When called recursively at every level of a nested type, you get O(n^2) total work.

rust/candid/src/types/subtype.rs lines 49-49

  if t1 == t2 {

The proposed fix is trivial — use pointer equality instead:

 1 │if std::rc::Rc::ptr_eq(&t1.0, &t2.0) {
 2 │    return Ok(());
 3 │}

Impact on our benchmarks: effectively zero.
check_subtype() is only called from two places in de.rs:

rust/candid/src/de.rs lines 504-504

      self.check_subtype()?;  // in deserialize_service

rust/candid/src/de.rs lines 516-516

      self.check_subtype()?;  // in deserialize_function

None of our 12 benchmarks (vec_int16, vec_nat, vec_nat32, vec_nat64, btreemap, option_list, variant_list, nns, nns_list_proposal, blob, text, extra_args) involve service or function types in the data path. The subtype_() function is never called during normal encode/decode of records, variants, vectors, or primitive types.
Where it WOULD matter:

1. Explicit compatibility checks — service_compatible(), service_equal(), check_rust_type() in candid_parser — called by tooling to verify .did file upgrades
2. Deserializing messages containing service or func types — rare in practice but technically possible
3. Complex recursive service types — where the quadratic blowup would be most visible

Rough estimate: For a service type with ~50 methods each taking/returning complex records (say ~20 fields deep), the current approach does ~50 * 20 = 1000 structural comparisons per subtype check, where each comparison itself traverses the subtree. With Rc::ptr_eq, this drops to 1000 pointer comparisons — orders of magnitude cheaper. But this only affects tooling/validation paths, not hot encode/decode paths.
Verdict: The fix is correct, trivial (one line), and worth doing for correctness/hygiene, but it won't move any of our current benchmark numbers. It's a tooling-path optimization, not a data-path optimization.

[crusso]

I think Claude is wrong: the subtype check happens during decoding, so if you have a vec of services/funcs (think subscriber collection), it might get expensive on the data path, not tooling path.

It seems more like our benchmarks are lacking.

[sasa-tomic]

If it's really a one-liner as Claude suggested - why not do it anyway? Also - benchmark would be great to add, if you have an idea what such benchmark would consist of, let me know @crusso

[sasa-tomic]

I added a benchmark that might help - PTAL #723