perf(string): drop localeCompare's two per-comparison allocations, and document the approximate ordering as intentional #10094

// @runtime {"name": "string-locale-compare-ascii", "category": "strings", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/string/compare.rs", "function": "js_string_locale_compare"}], "hypothesis": "Hypothesis: canonical normalization and custom primary/case collation add per-comparison work and may diverge from ICU semantics.", "notes": "ascii variant. n counts repeated input tokens, not bytes; UTF-16 length and UTF-8 byte length differ for Unicode. String result hashes sample roughly 32 positions for long strings (at most 63 for short strings), plus length. n seeded short labels, explicit en-US locale; checksum normalizes comparison result to sign as the API specifies.", "asynchronous": false, "output_stderr": false, "fresh_input": false}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function setup(n: number): string[] {
  const choices = ["aBcD" + 'a', "aBcD" + 'z', "aBcD" + 'B', "aBcD" + '7'];
  const values: string[] = [];
  for (let i = 0; i < n; i++) values.push(choices[Math.floor(rnd() * 4)]);
  return values;
}
function run(input: string[]): number {
  let h = 0;
  for (let i = 1; i < input.length; i++) {
    const result = input[i - 1].localeCompare(input[i], 'en-US');
    h = (h * 31 + (result < 0 ? 1 : result > 0 ? 2 : 3)) % 1000000007;
  }
  return h;
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  const preparedInput = setup(n);
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = preparedInput;
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = preparedInput;
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "string-locale-compare-ascii", category: "strings", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

// @runtime {"name": "string-locale-compare-unicode", "category": "strings", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/string/compare.rs", "function": "js_string_locale_compare"}], "hypothesis": "Hypothesis: canonical normalization and custom primary/case collation add per-comparison work and may diverge from ICU semantics.", "notes": "unicode variant. n counts repeated input tokens, not bytes; UTF-16 length and UTF-8 byte length differ for Unicode. String result hashes sample roughly 32 positions for long strings (at most 63 for short strings), plus length. n seeded short labels, explicit en-US locale; checksum normalizes comparison result to sign as the API specifies.", "asynchronous": false, "output_stderr": false, "fresh_input": false}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function setup(n: number): string[] {
  const choices = ["ä中😀Ö" + 'a', "ä中😀Ö" + 'z', "ä中😀Ö" + 'B', "ä中😀Ö" + '7'];
  const values: string[] = [];
  for (let i = 0; i < n; i++) values.push(choices[Math.floor(rnd() * 4)]);
  return values;
}
function run(input: string[]): number {
  let h = 0;
  for (let i = 1; i < input.length; i++) {
    const result = input[i - 1].localeCompare(input[i], 'en-US');
    h = (h * 31 + (result < 0 ? 1 : result > 0 ? 2 : 3)) % 1000000007;
  }
  return h;
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  const preparedInput = setup(n);
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = preparedInput;
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = preparedInput;
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "string-locale-compare-unicode", category: "strings", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();

// @runtime {"name": "sort-objects-locale-key-unicode", "category": "sort", "verification": "checksum", "sources": [{"file": "crates/perry-runtime/src/array/sort.rs", "function": "js_array_sort_with_comparator"}, {"file": "crates/perry-runtime/src/string/compare.rs", "function": "js_string_locale_compare"}, {"file": "crates/perry-runtime/src/string/compare.rs", "function": "locale_compare_default"}], "hypothesis": "Hypothesis: locale_compare_default compares newly lowercased Rust strings lexicographically with String::cmp instead of applying ICU locale collation weights, which may explain different ordering and checksums for umlaut, CJK and emoji keys.", "notes": "n objects; keys and original ids are fully hashed in order. Default-locale ordering may differ because Perry documents approximate collation; report mismatches as correctness findings.", "asynchronous": false, "output_stderr": false, "fresh_input": true}
// Standalone file. Shared helpers/driver are inlined by common.py.

let seed = 0x12345678;
function rnd(): number {
  seed ^= seed << 13; seed ^= seed >>> 17; seed ^= seed << 5;
  return (seed >>> 0) / 4294967296;
}
function numbers(n: number): number[] {
  const a: number[] = [];
  for (let i = 0; i < n; i++) a.push(Math.floor(rnd() * 1000000));
  return a;
}
function hashArray(a: number[]): number {
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + a[i]) % 1000000007;
  return h;
}
// Bounded checksum work avoids making string slicing/indexing part of every
// string benchmark's asymptotic cost. The workload itself consumes its result.
function hashString(s: string): number {
  let h = s.length;
  const step = Math.max(1, Math.floor(s.length / 32));
  for (let i = 0; i < s.length; i += step) h = (h * 31 + s.charCodeAt(i)) % 1000000007;
  return h;
}

function makeStrings(n: number): string[] {
  const tokens: string[] = ["ä", "Ö", "漢", "字", "😀", "🚀"];
  const a: string[] = [];
  for (let i = 0; i < n; i++) a.push(tokens[Math.floor(rnd() * tokens.length)] + ":" + String(Math.floor(rnd() * 1000000)));
  return a;
}

function setup(n: number): {key: string, id: number}[] {
  const keys = makeStrings(n);
  const a: {key: string, id: number}[] = [];
  for (let i = 0; i < n; i++) a.push({key: keys[i], id: i});
  return a;
}
function run(a: {key: string, id: number}[]): number {
  a.sort((x, y) => x.key.localeCompare(y.key));
  let h = a.length;
  for (let i = 0; i < a.length; i++) h = (h * 31 + hashString(a[i].key) + a[i].id) % 1000000007;
  return h;
}

// Size is the final argument: both native Perry and Node expose it reliably.
const n = Number(process.argv[process.argv.length - 1]);
if (!(n > 0)) throw new Error("Expected a positive size argument");
function benchmarkMain(): void {
  seed = 0x12345678;
  
  let checksum = 0;
  let seen = false;
  let warmMs = 0;
  let warmRuns = 0;
  while (warmMs < 200 || warmRuns < 5) {
    seed = 0x12345678;
    const input = setup(n);
    const start = performance.now();
    const value = run(input);
    const elapsed = performance.now() - start;
    if (!(elapsed >= 0)) throw new Error("Invalid monotonic timer");
    warmMs += elapsed;
    warmRuns++;
    if (seen && value !== checksum) throw new Error("CORRECTNESS: unstable checksum during warmup");
    checksum = value;
    seen = true;
  }
  const samples: number[] = [];
  let runs = 0;
  for (let sample = 0; sample < 7; sample++) {
    let elapsed = 0;
    let count = 0;
    // Mutable workloads prepare fresh input BEFORE each timer; immutable
    // workloads reuse setup. Neither preparation nor validation is measured.
    while (elapsed < 20) {
      seed = 0x12345678;
      const input = setup(n);
      const start = performance.now();
      const value = run(input);
      const duration = performance.now() - start;
      if (!(duration >= 0)) throw new Error("Invalid monotonic timer");
      elapsed += duration;
      count++;
      if (value !== checksum) throw new Error("CORRECTNESS: unstable checksum during sampling");
    }
    samples.push(elapsed / count);
    runs += count;
  }
  // Do not depend on Array.sort to compute the median of a sort benchmark.
  for (let i = 1; i < samples.length; i++) {
    const v = samples[i];
    let j = i - 1;
    while (j >= 0 && samples[j] > v) { samples[j + 1] = samples[j]; j--; }
    samples[j + 1] = v;
  }
  console.log(JSON.stringify({name: "sort-objects-locale-key-unicode", category: "sort", n,
    ms_per_run: samples[3], runs, checksum}));
}
benchmarkMain();