TS String Literal Performance: TypeScript string-parsing opts out of tail-recursion

[JoviDeCroock]

Acknowledgement

• I acknowledge that issues using this template may be closed without further explanation at the maintainer's discretion.

Comment

Hey all,

We've been working on gql.tada the project aims to implement the GraphQL language as TypeScript types. This all works pretty well however we are sometimes hitting performance issues. One of them being when our GraphQL document is lengthy, this seemingly makes TypeScript opt out of tail-recursion when tokenising/parsing the StringLiteral due to hitting an internal limit. The pattern we moved to is slicing the first character and parse like that, maybe that optimisation is currently missing?

On the side, another performance ceiling we have been hitting is with large schema's when we transform the large schema to an introspection (the structure we use to do lookups) we can hit very high memory usage (we have observed 8GB). One thing we are currently doing is to pre-generate the internal TypeScript type and use that instead of our current .d.ts approach.

I realise that all of this is quite vague and I am here to provide any further detail or if pointed in the right direction to figure this out myself. Also apologies if there's a different template for performance concerns, I did not spot one immediately.

Benchmark it yourself

The problematic query in question

git clone git@github.com:0no-co/gql.tada.git
git checkout bench
pnpm i
pnpm build

Now go to examples/example-pokemon-api/src/components/PokemonList.tsx, notice the huge query, if we add more fields we will get a Type instantiation too deep and possibly infinite.

[MartinJohns]

Just FYI, template strings are explicitly not suited/meant for parsing DSL.

#45504 (comment)

"I want to write a full GraphQL parser and provide exact API shapes back"
This is a moderate 👎 - we think we'd be encouraging people to use the wrong tools to solve these problems

Related: #43335

[kitten]

@MartinJohns: We talked to @jakebailey about this, and just because this isn't recommended / accounted for in TypeScript’s type checker, to us, that doesn't mean that there aren't some valuable insights to be had here from discussing what we ran into ❤️

FWIW, we're planning to have a hybrid approach for codegen + in-typesystem parsing in the future to get around linear increases in parsing time, and even ignoring this, the project also has a lot of non-string-literal parsing insights, since we're dealing with large data sets.

For now though, the issue we ran into is that the string literal inferences we're using, which are done character by character, cause a performance cliff, where cost increases per character when we bail out of tail recursion (due to the max tail recursion limit), which is potentially related to allocations for each string literal type.

I'd say, no matter whether we're dealing with a DSL or not, that's potentially an indicator that per-character inference in literals could become more efficient with a fast path, if that's possible

[jakebailey]

Compiling the linked project completes in 4 seconds on my machine; is the problem strictly that you hit a limit? Can you provide an example that hits a limit or is slow?

[RyanCavanaugh]

This feature was designed around modifying property names, e.g. turning

type In = {
  foo: string;
}

into

type Out = {
  getFoo(): string;
}

or parsing short data like /foo/bar -> ["foo", "bar"]

The fact that it even lets you try to do something with literals over 100 characters long was probably a huge mistake. I'd really, really ask that people not try to do this except as a learning exercise, and accept that you're absolutely going to encounter limitations. The editor performance you're going to see from this approaches is going to be uniformly terrible.

If people want to write a lisp interpreter in the type system string parser for fun that's fine, but it's not a mainline scenario and anything even close to it is going way past the design limits of what it's there for. It's like trying to use a kitchen knife as a wheel axle -- you might be able to make it work but it's not what it's there for and the knife manufacturer isn't going to document the bending modulus of it for you.

As such, we're not able to spend time investigating reports like this. That said, if you independently find and verify some fix, PRs would possibly be accepted.

[JoviDeCroock]

I see that there's no interest for this, I made this issue to see if there was a possible collaboration. It is disappointing that it was met with this kind of rude commentary. If anything in this issue could have been seen as bad intent, I apologize. I acknowledge the size of the project and the amount of issues that come in, I was in no way shape or form requesting urgent help or whatever. I was merely suggesting that there's room for improvement and if anyone was up for that to point me in the right direction.

I suspect that issues like this one might arise in the future, as folks explore the boundaries of TypeScript more and more, heck the router-space doing string literal parsing might fall into that bucket soon enough (unless that's also a DSL...). You lot have created something to be proud of and I respect that you have clear boundaries in your project. A design philosophy will allow you to iterate on what matters to your project.

That being said, I suspect that when folks started building types on top of JavaScript there could have been similar reactions... Yet here we are, we got an amazing language that allows us to express complex types on top of JavaScript, maybe someday TypeScript will enable all of these wonderful features and enable us to be even more expressive and push the boundaries of static-types.

[MartinJohns]

It is disappointing that it was met with this kind of rude commentary.

I haven't seen any rude commentary.

[JoviDeCroock]

I am not going to debate what is rude or not but the following comment, at least to me, comes across quite rude for an issue of this kind. It's not like this red-line is documented anywhere, I will however leave it at that.

It's like trying to use a kitchen knife as a wheel axle -- you might be able to make it work but it's not what it's there for and the knife manufacturer isn't going to document the bending modulus of it for you.

[fatcerberus]

That was simply an analogy; any sarcastic or rude intent you read in it is on you.

It's not like this red-line is documented anywhere

FWIW, the documentation for the hypothetical knife probably wouldn't say anywhere "Don't use our product as a wheel axle." 😄 That said, GitHub issues are considered part of documentation, and template string inference not being intended for this use case is well-established by the maintainers here.

[RyanCavanaugh]

I apologize if any rudeness was perceived in that message; it was not my intent and I'll try to do better in the future.

I made this issue to see if there was a possible collaboration

I just want to reiterate that the door is totally open if other people want to optimize something in a way that doesn't incur other significant costs. We're not able to offer time to research optimization approaches, but if you do this and find something that works well, we can help you get it into a workable PR.