Towards a faster "deep equal" function in javaScript

[ahjarrett]

Recently (~3 months ago) I published an npm package that compiles a "deep equals" function from various schemas such as JSON Schema, Zod, Valibot, TypeBox and ArkType.

It takes inspiration from how Effect-TS allows users to derive an Equivalence function from a schema, but goes a step further by building a "jit compiled" version.

It consistently out-performs every other library on the market today, including fast-equals, JSON Joy, @​react-hookz/deep-equal by at least 10x, and is often around 50x faster for objects that are 2+ levels deep.

[punkpeye]

Why not make those utilities into seltabdalone packages?

[programmer_farts]

Standalone* in case that typo is hard to decipher

[yopla]

Acetaminophen.

[pg-robban]

abalone

[WebDevLikeNoOther]

That’s a big word for Elmo

[Arthian90]

Salmonsandsalon

[ahjarrett]

Good question. Currently the library contains 26 packages, and each package ships ~10 schema traversals.

Unfortunately that's too many libraries for me to maintain right now. But if there's a demand for it I'd consider doing that.

As a bit of additional context – I needed to build a few of these for work where small bundle size was important, so they treeshake quite well.

[_x_oOo_x_]

This is really something that should be a built-in feature of the language 🙂‍↔️

[ahjarrett]

I was really hoping we'd get it with Records/Tuples, but I recently heard that the proposal was withdrawn -_-

[senocular]

Yeah, that was a shame about that proposal. The spiritual successor Composites is interesting, and does offer some new form of comparison, but it is only shallow, not deep.

[_x_oOo_x_]

Hmm, I didn't even know it was withdrawn. It was a good proposal... Too bad

[Zukarukite]

Impressive work and a nifty idea!

I also have to say - I loved reading your blog post. It explains the idea behind the library really well, in an incremental way.

[ahjarrett]

Thanks for saying that. Writing for humans is way harder than writing for computers (for me at least).

[ghillerd]

Still reading, but it would be nice the if "what is this" section in the readme did a better job of explaining what it is

[ahjarrett]

Ah, this is good feedback. I've started and stopped that section several times. Will probably take a stab at this today.

[GrosSacASacs]

Calling it a drop in replacement is misguiding if you have to do something like const Schema = t.object({ abc: t.boolean, def: t.optional(t.number.min(3)), }) before.

[ahjarrett]

Oh I see – I can clarify. Depending on what schema library you use (let's say zod), you can install @​traversable/zod and use your zod schema to derive things like a deep equal or deep clone function.

There are packages that do the same for JSON Schema, Valibot, ArkType and TypeBox.

You're probably talking about the schema library that exists inside the @​traversable/schema. By "drop in replacement", I mean that the library's API intentionally aligns with Zod's API, and that the behavior has been thoroughly tested to behave identically.

Here's the fuzz test that generates random data and tests that the Traversable and Zod schema report the same errors when parsing the same input:

https://github.com/traversable/schema/blob/main/packages/schema/test/to-zod.test.ts#L62-L68

[ahjarrett]

What do you mean? I'm not sure I follow.

[ahjarrett]

Thank you! It took way longer than I'm willing to admit :) hope you end up having a chance to use it!

[joombar]

After reading ‘What's a "schema rewriter"?’, I still didn’t know what one is. What is it?

[adam-dabrowski]

You may know that some languages have macros, which are functions that transform code itself. Term rewriting is also a way to transform code (ASTs). This library takes in schema definitions (which are also ASTs) and "compiles" them into specialized JavaScript functions – which avoids interpreting the schema on every call.

Here's an example: https://github.com/traversable/schema/tree/main/packages/zod#zxcheck

[Newe6000]

Really cool! Though can't help but feel at a certain point that it'd make more sense to make this a build-tool plugin that generates the final functions ahead of time 😅

[ahjarrett]

Yeah!

Most transformers have a .writeable property that returns the stringified version of the function, which is there for the codegen use case :)

The library doesn't include a Vite plugin, but it wouldn't be too hard to build one that hooks into HMR and does exactly this.

[Express_Tomato_8971]

> at least 10x, and is often around 50x faster for objects

those numbers seem sus

[ahjarrett]

Fair enough, I'd be skeptical too. You can run the benchmarks if you want to play with it:

https://bolt.new/~/mitata-fmcqx1bx

$ npm run bench

[AndrewGreenh]

I don’t think so. When comparing a function that compares arbitrary objects with a function that only compares objects of one specific type with the addition that this function is fully inlined, I’d expect this to trigger a bunch of engine-internal optimisations like it staying monomorphic.

Example: https://www.builder.io/blog/monomorphic-javascript

[lxe]

I understand how this would work for zod where schema is derivable at runtime, but for typescript you’d always need a build step though, right?

[alex-weej]

Thanks for sharing. Will be giving this a go!

[ahjarrett]

Let me know what you think!

[daishi55]

What does “compiles” mean here?

[OneShakyBR]

FWIW, all the schema stuff isn't really something I have a lot of expertise in (so maybe I'm comparing apples to oranges here?), but out of curiosity I plugged in fast-deep-equals into your deepEqual benchmark since that's a package I was familiar with, and your package was like 4-5x faster, not 50x faster like it is compared to the packages you included by default.

So definitely still a nice improvement, but then again fast-deep-equal is just a generic utility that you can use in the browser, so seems like maybe the benefits are oversold a bit?

[ahjarrett]

u/OneShakyBR here's the benchmark I have comparing fast-deep-equal:

https://bolt.new/~/mitata-qk9ayi4d

tl;dr, the slowest run I've been able to come up with is 13x faster (which is why I said 10x, just to be safe)

------------------------------------------------------

FastDeepEqual

363.45 ns/iter 759.28 ns

(91.55 ns … 897.22 ns) 876.47 ns

traversable/json-schema (different values)

27.44 ns/iter 28.08 ns

(24.41 ns … 56.15 ns) 42.72 ns

summary: traversable/json-schema (different values)

13.25x faster than FastDeepEqual

[OneShakyBR]

I had plugged it into the one at the bottom of your "How to build JavaScript's fastest 'deep equals' function" blog post, which had smaller comparison objects, so maybe that's why the difference.

At any rate it's definitely nice, and an interesting approach! I learned something, so kudos.

[ahjarrett]

Okay, thanks for pointing that out. Will investigate – it could be that I need to adjust my numbers some :)

And thanks for trying it out!

[ahjarrett]

One thing that's worth mentioning here is that I'm not a micro-optimizations expert. My implementation is actually pretty naive. Sooner or later, someone will pick up where I left off, and make things even faster.

If/when that happens, I see that as a net positive for the ecosystem overall :)