allow caching of hashCode

[dave-doty]

I've profiled my application and found a huge amount of time is being spent in calls to the getter hashCode on built_value objects that have not changed since the last call to hashCode.

I debugged and was surprised to see that the generated implementation does not cache hashCode. (I recall though that hashCode is cached for built_collection objects.) Is there a way to enable such caching?

For example, one object with 9 fields has a generated hashCode implementation that looks like this:

  @override
  int get hashCode {
    return $jf($jc(
        $jc(
            $jc(
                $jc(
                    $jc(
                        $jc(
                            $jc($jc($jc(0, helix.hashCode), forward.hashCode),
                                start.hashCode),
                            end.hashCode),
                        deletions.hashCode),
                    insertions.hashCode),
                dna_sequence.hashCode),
            is_first.hashCode),
        is_last.hashCode));
  }

That's a lot of calls to $jc. And this is just one object near the bottom of a large object tree (all built_value and built_collection). hashCode is being called on the whole thing quite frequently, so it's making things very janky.

[dave-doty]

Oops, sorry, I just noticed this duplicate issue: #210

In that issue you suggested "if you have a particular case in mind you could hack the .g.dart files yourself and try it."

I'd like to try this to test out some ideas, but I'm not sure how. I can change the generated code in the .g.dart files, but in order for their effect to be tested, the project needs to be recompiled, which calls build_runner, which overwrites the .g.dart files with built_value's auto-generated code. Is there an option on webdev (https://dart.dev/tools/webdev) that tells it to skip the build_runner step so that .g.dart files will not be generated?

[davidmorgan]

$jc is very fast :) ... but I can certainly believe that it's taking a lot of time in a big object tree.

I'm afraid I don't know how to do that with package:build. Another way to experiment would be to change package:built_value_generator; lib/src/value_source_class.dart has a method generateEqualsAndHashcode; you could add both the field and the use of the field there.

I'm not sure it makes sense to always cache hashCode. Do you think it would make sense that you opt-in like this?

@memoized
int get hashCode;

[dave-doty]

Opt-in is okay, although I think opt-out is better. :)

Why? First, it was a surprise to me that the behavior was different from built_collection.

Second, it's a time/memory tradeoff right? If you have few objects then it's best to favor time (i.e, cache the hashCode). If you have so many objects that the memory becomes an issue, they are very likely a few large lists/sets/maps each containing the same type of object, so it would be not too much effort to opt-out of caching hashCode on just those types. I think it would be the rare use case where there are thousands/millions of objects where saving an extra int on each one would make a noticable difference on memory, but there would be so many different types of them that it would be tedious to add many annotations to opt-out.

I don't know how to parse annotations, but I implemented the version that unconditionally caches every hashCode by replacing lines https://github.com/google/built_value.dart/blob/master/built_value_generator/lib/src/value_source_class.dart#L1015 through https://github.com/google/built_value.dart/blob/master/built_value_generator/lib/src/value_source_class.dart#L1031 with this:

result.writeln('int _hashCodeCached = null;');
result.writeln();
result.writeln('@override');
result.writeln('int get hashCode {');
result.writeln('  if (_hashCodeCached == null) {');

if (comparedFields.isEmpty) {
  result.writeln('_hashCodeCached = ${name.hashCode};');
} else {
  result.writeln(r'_hashCodeCached = $jf(');
  result.writeln(r'$jc(' * comparedFields.length);
  // Use a different seed for builders than for values, so they do not have
  // identical hashCodes if the values are identical.
  result.writeln(forBuilder ? '1, ' : '0, ');
  result.write(comparedFields.map((field) => '${field.name}.hashCode').join('), '));
  result.writeln('));');
}
result.writeln('  }');
result.writeln('  return _hashCodeCached;');
result.writeln('}');
result.writeln();

For a feature of my app where I'm click-dragging a selection box, where it fires an update on every mousemove (throttled to be 60 times/sec, so needs to take 1000/60 = 16.66 ms to be jank-free), this reduces the time spent calling hashCode on the various parts of the object tree from ~20 ms down to ~6 ms.

[davidmorgan]

Those are all good points.

My worry is that when you have very few fields, an extra hidden field is surprising. For example if you have just one int, it's surprising that you need memory for two.

It's also the case that not all built_value classes end up being hashed at all. So we might pay that cost for nothing.

20ms->6ms is pretty convincing. I think the opt-in approach sounds good :D will aim to land that next time I do a batch of improvements.

Thanks!