str, bytes: answer equality with equality rather than with an ordering - #8531

Found while checking whether anything else in str still scales worse than CPython. These are not asymptotic -- they are two O(1) answers that were being computed in O(n).

What was happening

Three places answered == and != by taking Ord::cmp of the two buffers and asking whether the result was Equal:

• impl Comparable for PyStr (builtins/str.rs)
• PyBytesInner::cmp (bytes_inner.rs), which serves bytes and bytearray
• Instruction::CompareOpStr (frame.rs), the specialization the interpreter installs after it sees two exact str operands

An ordering has to read the bytes. [u8]: Ord memcmps the common prefix and only then compares the lengths, so "a" * 1_000_000 == "a" * 999_999 -- an answer the lengths give away -- memcmped a megabyte. And CompareOpStr bypasses the Comparable slot, so it had also lost the identity shortcut the slot takes with identical_optimization: a string compared with itself was read end to end.

CPython answers both with _PyUnicode_Equal, which starts if (str1 == str2) return 1; and then compares kinds and lengths before any content; unicode_richcompare and bytes_richcompare special-case Py_EQ/Py_NE the same way.

What this does

Adds PyComparisonOp::eval_eq, which settles Eq and Ne from an equality test and returns None for an ordering operator (without evaluating the test), and answers through it in the three places. Slice equality checks the length first, and CompareOpStr answers an object compared with itself the way the slot it specializes does.

Measurements

n=1,000,000, per comparison, best of 7:

CPython answers the first four in 0.02 µs. The remaining 0.16 µs here is the interpreter loop -- an empty lambda call measures 0.12 µs on the same machine.

Verification

Behaviour is unchanged, so the tests added to operator_comparison.py are a guard on the two new shortcuts rather than a regression test -- they pass on main as well. They go through a function and a loop so the operands are not constants the compiler folds and the specialized instruction is actually reached, and they cover: the same object, equal distinct objects, same-length differences, prefixes ("abc" < "abcd"), the empty string, lone surrogates, astral characters, bytes/bytearray in both directions, and comparison against a non-string.

test_str, test_bytes, test_string, test_dict, test_set, test_operator, test_compare, test_richcmp, test_sort, test_userstring, test_collections, test_json: SUCCESS. (test_bytearray and test_unicode fail identically on main -- neither reaches its tests on either.) cargo clippy --all-targets and cargo fmt --check clean.

Summary by CodeRabbit

• Bug Fixes

  • Improved equality and inequality comparisons for strings, bytes, and bytearrays, including values with different lengths.
  • Preserved correct ordering behavior for less-than and greater-than comparisons.
  • Improved handling of Unicode text, mixed byte types, and comparisons with nonmatching types.

• Tests

  • Added comprehensive coverage for equality, ordering, prefixes, Unicode edge cases, and repeated comparisons.

Are there others?

Every eval_ord call site in the tree (15 outside slot.rs), checked for the same shape -- an ordering used to answer equality where the ordering costs more:

• set.rs, dict.rs, iter.rs, array.rs:1286 compare lengths; frame.rs's int/float specializations, int.rs, float.rs compare scalars; cert.rs compares a bool, function.rs an Option::is_none. An ordering is O(1) on all of those, so there is nothing to save.
• array.rs:1255 already routes Eq/Ne through eq_only before it reaches the ordering path -- the same shape as this change, arrived at independently.
• BigInt: Ord compares sign and limb count before digits, so int equality already short-circuits on magnitude.

The three fixed here are the ones whose operands are buffers, where the ordering reads O(min(len)) bytes to answer a question the lengths settle.

eval_eq sits beside two existing helpers and is not a duplicate of either: map_eq answers only where its predicate holds (its caller handles the other side), and eq_only declares the comparison NotImplemented for an ordering operator -- correct for a type with no ordering, wrong for str, which has one. The doc comment says so.