hashString causing poor performance

[adamschackart]

Running the following Wren code:

for (i in 0...10) {
    var start = System.clock
    var s = []

    for (j in 0...100000) {
        s.add(" ")
    }

    s.join()
    System.print("%(i) %(System.clock - start)")
}

I get ~10 seconds per iteration on an M4 Mac Mini. When making the following change to wren_value.c:

static void hashString(ObjString* string)
{
  string->hash = 0;
}

I get ~1 second per iteration. Hashes seem to be generated for each new string, whereas in other language (such as Python), they're generated on demand.

[adamschackart]

The following hash function gives a ~2x speedup (__builtin_rotateleft32 would have to be abstracted for MSVC via _rotl). Its quality compared to the original is unknown:

static void hashString(ObjString* string)
{
  uint32_t hash = 0;

  for (uint32_t i = 0; i < string->length; i++)
  {
    hash = __builtin_rotateleft32(hash, 7) + string->value[i];
  }

  // Final mixing step.
  hash += hash >> 16;

  string->hash = hash;
}

[mhermier]

Can you separate the s setup phase from the active join() payload. As this the tests benchmark the array allocation strategy. It also benchmark the garbage collection strategy in the join. I also wonder if the test does not benchmark the CPU page caching.

[adamschackart]

I could if it helps, I wrote it that way to replicate the code path that spiked this (https://github.com/adamschackart/wrench/blob/d9a899d5454c62b96c647c35659e1df2af050a29/wrench_file.c#L925).

Here is a screenshot of kcachegrind, after a few minutes of running valgrind --tool=callgrind ./run_wren example.wren with a debug build on a Xeon E3-1245v5. I terminated the session early because it would have taken much, much longer.

[mhermier]

As expected the allocator takes 1/3 of the time. One solution would be to lazy my compute the hash, have a ByteList (to use as a String builder), or something else... The ByteList solution would solve a lot of issues of the current base API, but there are quite a number of trade of with that solution.