Use of reduce vs entries #846
Replies: 3 comments 7 replies
-
@kenttregenza Hi. TypeBox's internal composition logic is written to run on older versions of JavaScript (which may not support .flatMap), but mostly it's written to replicate (as close as possible) conditional type level logic at runtime. TypeBox has been through a few implementations of this (and a very extensive one on 0.32.0 where a lot of this logic was introduced). The following shows a few iterations of the pattern and general thinking. // -----------------------------------------------------------------
// type level (need to replicate this type at runtime)
// -----------------------------------------------------------------
type TMapping<T extends TSchema[], Acc extends TSchema[] = []> = (
T extends [infer L extends TSchema, ...infer R extends TSchema[]]
? TMapping<R, [...Acc, L]>
: Acc
)
// -----------------------------------------------------------------
// runtime level (#1 - verbatim)
// -----------------------------------------------------------------
const Mapping1 = <T extends TSchema[]>(T: [...T], Acc: TSchema[] = []): T => {
const [L, ...R] = T
return (
T.length > 0
? Mapping1(R, [...Acc, L])
: Acc
) as T
}
// -----------------------------------------------------------------
// runtime level (#2 - reduce)
// -----------------------------------------------------------------
const Mapping2 = <T extends TSchema[]>(T: [...T]): T => {
return T.reduce((Acc, L) => {
return [...Acc, L] // array copy (slow)
}, [] as TSchema[]) as T
}
// -----------------------------------------------------------------
// runtime level (#3 - reduce - no copy)
// -----------------------------------------------------------------
const Mapping3 = <T extends TSchema[]>(T: [...T]): T => {
return T.reduce((Acc, L) => {
Acc.push(L) // avoid array copy
return Acc
}, [] as TSchema[]) as T
} So, currently TypeBox uses the
I think before implementing anything here, it would be good to understand the problem a little better. The 70 second delay you mention is very extensive (and certainly far more than I would expect for TypeBox even with the Mapping2). Would you be able to provide a repro (tRPC + TypeBox) which demonstrates this delay? I would be keen to observe the issue first, then consider a strategy for optimizing (which may involve broadly implementing Mapping3) Keep me posted |
Beta Was this translation helpful? Give feedback.
-
@kenttregenza Heya, Just to be clear on things, when you say the following.
Do you mean
Differences between Inference and Runtime PerformanceIt's important to note that if you're experiencing "Inference Performance" or "Compiler Performance" issues (above), this would be unrelated to the use of .reduce(). Similarly a flatMap() implementation wouldn't lead to improved Inference performance. The reason is that the internal runtime logic used to construct types is decoupled from the type level logic to infer static types. Generally speaking, to improve "Inference or Compiler Performance", you would need to look specifically at the static inference logic. To improve "Composite Performance", there may be room to improve performance there via flatMap (or the Mapping3 pattern shown above) Can you let me know which kind of performance issues you're experiencing? |
Beta Was this translation helpful? Give feedback.
-
You are a machine... So anecdotally I'd say that halved the runtime performance we are experiencing. Thanks for that. An interesting perf question/memory question (since I have no real way of measuring how Typescript builds its Intellisense tables) if I did this const schema1 = Type.Object({
name: Type.String(),
language: Type.String()
})
const schema2 = Type.Object({
title: Type.String(),
note: Type.String()
}) and made it const stringProp = Type.String()
const schema1 = Type.Object({
name: stringProp,
language: stringProp
})
const schema2 = Type.Object({
title: stringProp,
note: stringProp
}) I know this removes all the nice schema "options" but say I was fine with that the Q is if this would this improve inference on Typescript engine... since all the "strings propeties" are now essentially the same object under the hood. Would that reduce the burned on the Typescript language server/inference engine? Or should I just be doing what your latest code is doing... returning as never and defining the function calls with return "types"? I will investigate In any event thank you again for the updates. I think it has really been a good step forward. |
Beta Was this translation helpful? Give feedback.
-
We're using Typebox for our new project along side of tRPC. Our schemas are numerous and complex with "schemas" sometimes haveing 40-50 properties in "layers" (TRecords etc). We use Typebox extensively to help shape our tRPC routes (using compiled validators etc) and data transformations to and from a document data storage.
So be it tRPC or Typebox our tsserver inside VSCode takes sometimes 70s to get through compiling/prepping all the files inour multi-package monorepo. That's fine a once off hit is ok if incremental compilation is happening later (slow but bearable).
The Problem
What we did notice is that when we use the Value part of Typebox inside our Fastify API (Node 20) we are getting significant impact on perf. Now again this could be attributed to the complexity/composition of how we construct our schema (eg we use TComposite) but delving into the Typebox after wrapping every chunk of code in a performance timing I saw most of the problem was using Value and its use of the Javascript reduce method.
We are wondering why this is the case? Is this a legacy code thing? Based on perf metric etc?
AFAICT there are two "patterns" in where reduce is used thoughout Typebox code... one to reduce and array into an array and another to reduce an object into another object.
Array to array
The example patterns
Maybe I am not following but isn't this fairly inefficient? Essential for each item in the array it copies the whole array processed so far the ...acc and then contactenates an additional array of results (from a transform function) onto the end of the array.
This looks like a n! action.... Could really just be a flatMap?
Array of Objects to a newobject
The example patterns
Again this copies the who object (...acc) for every "item"... so if the arr is large the copes are n!
(there is variations of this where it is an array of objects transformed into a single object where each unique key can be an array... something like TComposite)
Could this again benefit from some ES6 functions like fromEntries and entries?
(With TComposite there might be another step where groupBy is involved)
Like the array example on small objects (1-5 props) this probably doesn't really "matter" in perf but on objects with lots of properties (or lots of objects with lots of properties) then it starts being significant.
I would be willing to go through the Typebox codebase to just change all the cases and see but to be honest I don't know how to setup the environment in order to do that and test it (is just a simple download change and submit a pull request? or is there a no-go area on code changes... eg language/platform constraints).
Anyway I thought I'd start asking first if I have missed something obvious or not so obvious before attempting it.
Beta Was this translation helpful? Give feedback.
All reactions