candid icon indicating copy to clipboard operation
candid copied to clipboard

perf: Subtype checking should not perform quadratic traversal

Open christoph-dfinity opened this issue 8 months ago • 0 comments

The equality check performed at the beginning of subtype checking: https://github.com/dfinity/candid/blob/30c388671462aecdc4a3a9753d50dc2e8208c200/rust/candid/src/types/subtype.rs#L39-L41 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).

christoph-dfinity avatar Apr 10 '25 14:04 christoph-dfinity