Home /Modules/impl/string_intern_scaling.sleela

string_intern_scaling.sleela

impl/examples/string_intern_scaling.sleela · 88 line(s) · sleela

#sleela 3.0
material;
< string_intern_scaling.sleela -- regression check for the VM String intern table. >
< Every runtime plain String (concatenation, number to text, read, ...) is interned >
< by impl/core/sleela_core.c intern(). It used to compare the new text with every >
< String the VM had ever made, so each String cost time in proportion to all the >
< Strings before it, and a program that built many Strings slowed down without >
< bound (the lib/java/converter run on the JDK sample spent 90 percent of its time >
< there). intern() now has a hash index. This example checks two things: the >
< answers are still right (equal text gives equal Strings, different text stays >
< different, including texts that share long prefixes), and the cost of a String >
< does not grow with how many Strings already exist. A wrong answer throws, which >
< ends the run with a nonzero status, so make test-sleela fails. >
class StringInternScaling {
  int checks = 0;

  void expect(boolean ok, String what) {
    checks = checks + 1;
    if (!ok) {
      print("FAIL: " + what);
      throw "string_intern_scaling failed: " + what;
    }
  }

  < microseconds to build n fresh Strings of the form tag + i >
  long timeFresh(String tag, int n) {
    long t0 = timeMonotonicNanos();
    int i = 0;
    String s = "";
    while (i < n) {
      s = tag + i;
      i = i + 1;
    }
    return (timeMonotonicNanos() - t0) / 1000;
  }

  void main() {
    < 1. equal text built two ways is the same String >
    String a = "intern" + "-" + 42;
    String b = "intern-" + "42";
    expect(a == b, "equal text built two ways compares equal");
    String c = "intern-43";
    expect(a != c, "different text compares different");

    < 2. many distinct Strings that share a long prefix stay distinct and findable >
    String prefix = "java.base/java/util/concurrent/ConcurrentHashMap.member";
    String[] made = new String[3000];
    int i = 0;
    while (i < 3000) {
      made[i] = prefix + i;
      i = i + 1;
    }
    i = 0;
    int same = 0;
    while (i < 3000) {
      String again = prefix + i;
      if (again == made[i]) { same = same + 1; }
      i = i + 1;
    }
    expect(same == 3000, "3000 rebuilt Strings equal their originals");
    expect(made[0] != made[1], "neighbouring Strings stay distinct");
    expect(made[1] != made[10], "a String is not confused with a longer one");
    expect(made[2999] == prefix + "2999", "the last String is found by its text");
    expect(prefix + "" == prefix, "appending nothing gives the same String");
    expect("" + "" == "", "the empty String is one String");

    < 3. cost per String does not grow with the number of live Strings >
    long early = timeFresh("early-", 2000);
    String[] keep = new String[20000];
    i = 0;
    while (i < 20000) {
      keep[i] = "keep-" + i;
      i = i + 1;
    }
    long late = timeFresh("late-", 2000);
    expect(keep[19999] == "keep-19999", "the 20000th kept String is intact");
    print("2000 Strings: " + early + " us with few live Strings, " + late + " us after 20000 more");
    < Measured 2026-11-13: the hash index takes about 0.6 ms for these 2000 Strings >
    < whatever the count of live Strings; the old linear table took about 110 ms. >
    < The budget sits between the two with room for a slow or busy machine: >
    < 25 microseconds a String, 50 ms in all. A growth check alone is not enough, >
    < because the old table was already slow at the start and so grew only 6x. >
    expect(late <= 50000, "2000 Strings after 20000 live ones take at most 50 ms");
    expect(late <= early * 8 || late <= 5000, "String cost stays flat as live Strings grow");
    print("string_intern_scaling: " + checks + " checks passed");
  }
}