Have corelib string canonicalization/interning API

[mkustermann]

Some applications have a need to canonicalize strings to avoid consuming a lot of memory due to duplicated strings. The way this is usually done is to have map that strongly holds on to the canonicalized string - the simplest being Map<String, String>.

Though using such a cache implies that strings may be held on to longer (by the cache) than by the application needs them. It therefore requires the application to manually decide when it's a good time to clear/prune such cache (based on not ideal heuristics). Once cleared, looking up new strings may end up us having duplicate strings in the heap.
=> The current options are somewhat unsatisfactory.

Weakness

One would want a canonicalization mechanism where the cache holds on to the strings only weakly, thereby allowing an implementation to reclaim memory if the application doesn't need them. Unfortunately one cannot build such a cache atm with e.g. WeakReferences since they cannot point to Strings.

(Even if one could build such a cache which weakly holds on to the strings, it would require all components of an application to use the same cache for canonicalization. Independent components of an app may not know about each other and may not have such a common, standardized cache library)

API

Ideally we'd provide a string canonicalization/interning API as part of the core libraries. Java has for this purpose e.g. the String.intern() method.

The specific use cases that could benefit here in our own tooling are e.g. CFE/Analyzer/...

Optimizations

As an optimization one may want the API to allow getting a canonicalized string for

• an existing String
• a substring of an existing string (String, int start, int length)
• a to-be utf-8 decoded string from (Uint8List, int start, int length)

The CFE cache currently supports the above use cases (e.g. in some modes it avoids the utf-8 decoding to temporary string objects - since probability is high to find a matching entry).

VM-specifics

In the VM specifically we'd prefer if the implementation ensures such strings are interned/canonicalized across isolates within the same isolate group.

/cc @lrhn @leafpetersen for library/language
/cc @rakudrama @askeksa-google for web & wasm capabilities
/cc @rmacnak-google for GC

(/cc @jensjoha for CFE)

[mkustermann]

If this is not supportable in performant way on web/wasm, we may also consider offering this in a VM-only dart:* library.

[lrhn]

It's definitely not supportable on web. JS does not provide any way to distinguish string values with the same content.

We could pretend that all strings are already canonicalized, but that would be lying, so the users will not get the memory characteristics they expect. It's better to not pretend.

A VM-only library could introduce extension methods on String like

extension InternedString on String {
  external String get interned;
  external String internedSubstring(int start, [int? end]);
}

[askeksa-google]

With the current string implementation in dart2wasm, we could support this. If we switch to using stringref (which I hope will be a feasible option at some point, in terms of its standardization status), it depends on what is possible in JS.

[rmacnak-google]

The weak canonical string table needs to be visited during the blocking part of GC, but is simple to implement.

[mkustermann]

The weak canonical string table needs to be visited during the blocking part of GC, but is simple to implement.

The question here is of course also whether we can implement this in an efficient way in the VM. Such weak string tables may end up being quite large. Making us spend several ms in blocking part of GC may be problematic.

We should think of ways we could implement this that wouldn't hurt GC responsiveness. Possibly relaxing some things (e.g. an unreachable string in the weak table may not be reclaimed in the immediate next GC). One could e.g. make the weak string pool be sharded into chunks - GC could process at most one weak chunk per GC round (to limit blocking GC time).

[askeksa-google]

Would it be part of the specification that constant strings are already interned, like in Java?

[mkustermann]

@rmacnak-google Do you also intend to optimize the perf by e.g. adding a stub that can lookup & insert in common (non-growth) case without going to runtime? (e.g. using compare-and-swap for updates, so only one writer wins)

[rmacnak-google]

No, I have only mind to investigate making weak processing concurrent by thinking of it as a phase of sweeping.