Extension method performance concerns

[jonasfj]

Maybe extension methods gets a bit slow, if you have many of them.

In package:typed_sql I model database queries using tuples with an expression objects for each column. So Query<(Expr<A>, Expr<B>, ...)> represents a query returning rows with (A, B ...,). To make this work I have extension methods for Query<(Expr<A>,)>, Query<(Expr<A>, Expr<B>)>, and so forth.

Thus, I generate need $$N$$ extensions to support queries with up-to $$N$$ columns, well, actually to support joins I end up generating $$O(N^2)$$ extensions.

Arguably, this is a bit extreme, if $$N$$ gets too large. But for reasonably values of $$N$$ this shouldn't be a problem. However, I've noticed that if I scale up $$N$$ a bit, things become a bit slow.

Below you'll find a graph of the time it takes to run:

• dart analyze lib/,
• dart test/sqlite/sqlite_test.dart (simple test with in-memory database, in Dart JIT mode),
• dart compile exe test/sqlite/sqlite_test.dart.

The graph also plots size of the generated code, do note that the non-generated code in lib/ is around ~10k, and there is a few dependencies too.

Raw numbers here:

N	Analyze	VM	AOT	LoC
4	3s	4s	4s	5k
8	6s	6s	5s	16k
12	12s	11s	8s	42k
16	14s	23s	15s	85k
20	23s	49s	31s	148k
24	47s	93s	62s	237k

This was generated with Dart SDK version: 3.9.0-63.0.dev (dev) (Sun Apr 27 17:07:04 2025 -0700) on "linux_x64".

---

Note that my code has $$O(N^2)$$ extension methods, and performance does seem to scale linear with the LOC count (lines of code). So maybe there is no problem at all, even if 31s seems a bit long to wait for 150k lines of code.

[lrhn]

Most likely the cost is in resolution. Not only do you have N^2 extension methods, I'm guessing they also have the same ~N names, so every invocation needs to check which ones apply, and of those which one is most specific.

Runtime shouldn't be affected, every invocation is a static function. If you try to do dart compile exe, does the time scale with N at all, or is that only because it scales with payload, not code? (If you have N-wide tuples, your payload also depends on N, so you can't compare the complexity directly.)

If we don't already cache, we probably could cache resolution in some ways, which are not too expensive to look up.

If we have decided once that extension Foo, which has a foo member, does not apply to type Bar, then we don't need to repeat a subtyping check (plus possibly generic inference) the next time you do bar.foo. (But if Foo is generic, we might need to do it again anyway, because Foo<A> and Foo<B> can behave differently wrt. extensions. That too could be something we could try to recognize, to avoid doing extra work that doesn't actually matter - an extension on Object does apply to both Foo<A> and Foo<B>, no need to check the type argument.)

If we have recognized that among applicable extension E1,...,Ek, for type Foo, Ei is most specific, then it's likely that there will be more invocations in the same library (where the same extensions are available), so we could cache that resolution too. (That one can be linear in N, so it matters.)
Or simply, for each foo.bar in a library (or any part file hierarchy which have the same extension imports, when we get parts with imports), cache the result for (type of foo, ID bar), to recognize if it comes up again in the same extension context.
(But I think cross-library caching might be valuable too, some people like to write many small libraries, and likely all with the same imports. It's very likely that all the extensions on a particular type comes from one import anyway, so they're always going to be the same set of available and applicable extensions throughout the application.)