Posts By: Will Keleher

Node.js `Array.includes` is faster than you'd expect

I've done a few Advent of Code problems, and one thing that's occasionally tripped me up has been my erroneous assumption that accessing the key of an object is fast. It's a fast constant time operation, but whatever hashing node is doing internally to find a key can sometimes be a performance hot-spot. There's a massive difference in speed between Array[index] and Object[key], and that made me start to wonder whether Object[key] was slow enough that there were situations where it'd make more sense to use Array.includes instead.

When I benchmarked it, I was pretty astounded to see that on a sorted array, Array.includes is faster on arrays of 10,000 strings than Object[key]. Internally, I'm guessing Array.includes is using binary-search when it knows that the array is sorted, which is a cool optimization! Here's the gist if you want to test it out. (I'm running these tests on Node 14 on a Mac Mini)

What about unsorted arrays?

When the array is unsorted, Object[key] look-ups start beating Array.includes pretty quickly: once we have ~20 documents, we'd expect to see faster look-ups from keyed object access. This is much more in line with what I expected when setting up this test.

What about Set.has?

Set.has is consistently slower than Object[key]. It can handle more cases than Object[key] can, but from a speed perspective, it's not in the running. I still often use it over Object[key] because I think it does a better job of expressing the intent to someone who's reading the code, and it's still a fast-enough constant time look-up.

What does this all mean?

Absolutely nothing! I still use Set.has for the majority of situations where I need to check membership in a list. For most of the code I write, expressing clear intent is far more important than optimizing performance, and I have yet to profile non-Advent-of-Code performance and find Object[key] or Set.has being a hotspot.

Benchmark Results

110 object access x 25,715,807 ops/sec ±0.70% (94 runs sampled)
2 10 set x 18,422,013 ops/sec ±0.85% (96 runs sampled)
3 10 array x 28,105,533 ops/sec ±0.88% (89 runs sampled)
4Fastest for ordered 10 is array
5 40 object access x 20,175,473 ops/sec ±0.90% (92 runs sampled)
6 40 set x 19,632,409 ops/sec ±0.73% (92 runs sampled)
7 40 array x 27,999,865 ops/sec ±1.09% (94 runs sampled)
8Fastest for ordered 40 is array
9 100 object access x 21,842,706 ops/sec ±0.70% (95 runs sampled)
10 100 set x 18,283,045 ops/sec ±0.78% (95 runs sampled)
11 100 array x 27,860,691 ops/sec ±1.03% (94 runs sampled)
12Fastest for ordered 100 is array
13 1000 object access x 20,026,184 ops/sec ±0.82% (92 runs sampled)
14 1000 set x 14,656,626 ops/sec ±1.37% (89 runs sampled)
15 1000 array x 23,392,774 ops/sec ±1.31% (90 runs sampled)
16Fastest for ordered 1000 is array
17 10000 object access x 14,367,754 ops/sec ±0.58% (93 runs sampled)
18 10000 set x 12,213,161 ops/sec ±0.51% (95 runs sampled)
19 10000 array x 28,067,504 ops/sec ±0.94% (92 runs sampled)
20Fastest for ordered 10000 is array
21 100000 object access x 9,106,145 ops/sec ±1.55% (93 runs sampled)
22 100000 set x 7,918,164 ops/sec ±0.92% (91 runs sampled)
23 100000 array x 78,374 ops/sec ±58.42% (86 runs sampled)
24Fastest for ordered 100000 is object access
25 1000000 object access x 3,296,346 ops/sec ±1.05% (93 runs sampled)
26 1000000 set x 2,076,943 ops/sec ±1.24% (91 runs sampled)
27 1000000 array x 490 ops/sec ±3.50% (40 runs sampled)
28Fastest for ordered 1000000 is object access
29 10 object access x 24,869,178 ops/sec ±0.80% (91 runs sampled)
30 10 set x 19,181,356 ops/sec ±0.98% (92 runs sampled)
31 10 array x 27,691,570 ops/sec ±0.99% (90 runs sampled)
32Fastest for random 10 is array
33 40 object access x 27,450,529 ops/sec ±1.30% (86 runs sampled)
34 40 set x 12,483,804 ops/sec ±1.30% (91 runs sampled)
35 40 array x 16,590,091 ops/sec ±0.92% (92 runs sampled)
36Fastest for random 40 is object access
37 100 object access x 31,040,999 ops/sec ±1.24% (87 runs sampled)
38 100 set x 12,386,070 ops/sec ±1.14% (91 runs sampled)
39 100 array x 16,389,384 ops/sec ±1.22% (91 runs sampled)
40Fastest for random 100 is object access
41 1000 object access x 25,365,248 ops/sec ±1.52% (88 runs sampled)
42 1000 set x 11,275,049 ops/sec ±1.51% (91 runs sampled)
43 1000 array x 16,294,268 ops/sec ±1.23% (88 runs sampled)
44Fastest for random 1000 is object access
45 10000 object access x 16,907,288 ops/sec ±1.47% (89 runs sampled)
46 10000 set x 8,905,038 ops/sec ±1.47% (91 runs sampled)
47 10000 array x 14,777,156 ops/sec ±1.19% (91 runs sampled)
48Fastest for random 10000 is object access
49...
Engineering

When multiple teams share a resource like a code-base, a database, or an analytics pipeline, that resource can often suffer from the Tragedy of the Commons. Well intentioned engineers can add slow code, not prioritize important improvements because those improvements aren't aligned with team incentives, and just generally not leave the codebase or database better than they found it.

ClassDojo has a monolithic backend web-server API, but it and its backing databases often suffered from hard to diagnose performance problems because engineers would accidentally add code with poorly indexed queries, with database fanouts, or that blocked the event loop, and they wouldn't realize that that code was causing any problems. We intentionally made our Model layer request-agnostic, which helps us create better tests & simpler code, but it meant that we didn't have a way of instrumenting database & performance cost by request until Node 14 started supporting AsyncLocalStorage.

AsyncLocalStorage "creates stores that stay coherent through asynchronous operations." This lets us reference a consistent context over the course of a request to get information about the route, store information about how many database requests that request has triggered, count how many documents we've fetched, and dramatically increase our visibility into what every request is doing. Because every single one of our routes is tied to a product area, and each of our product areas is owned by a team, we were suddenly able to give each team insight into any performance problems they'd inadvertently added to the codebase. None of our engineers and teams ever wanted to cause performance problems, but the lack of pre-AsyncLocalStorage system legibility meant that these issues were difficult to track down, and teams always had higher priority work than tracking down unattributed performance problems.

When we set up our AsyncLocalStorage per-request instrumentation system, we found some crazy things:

  • a route that occasionally made 30,000+ database requests because it was fanning out over a large list of items
  • another route that blocked the event-loop for 15-20 seconds a few times a day, and caused timeouts for any other requests that our server was handling at the same time
  • a third route that was occasionally fetching 500,000+ items to render information to return to clients
  • and plenty of other routes that weren't doing things nearly this egregious, but were still bad enough that we wanted to fix them

Once we had this instrumentation, it was incredibly simple for the right team to find and fix these issues. We'd looked into some of these & similar issues before, but finding & fixing them was incredibly time-consuming. Now, we have a single log that triggers an alert and tells you everything you need to know to track down the problem.

What did we track?

  1. Whenever we query one of our databases, we now include a comment with the query with the route name that triggered the request. When we go through our database's slow query logs, this comment shows us where the query actually came from, and lets us accurately attribute our database load. This makes our database optimization work so much simpler because many of our query patterns could be caused by many different routes!
  2. We also track:
  • the number of database queries made per database and per table-model over the course of a request
  • the number of items returned over the course of a request per database and per table-model
  • the total duration spent querying per-database and per table-model

Whenever we exceed safe thresholds for any of these metrics over the course of a request, we log out the details and send an alert to the appropriate team. We also send all of this data to our data warehouse, Redshift, so we can run more detailed queries about what each route is doing.

  1. We track overall event-loop-lag per container, and whenever event-loop-lag crosses 1 second (which is incredibly high!), we log out the same AsyncLocalStorage based request-cost details for all recent requests. This always points to situations where we've fetched a lot of data, and are then doing something computationally complex with it.

Monoliths need Transparency

It's hard to overestimate how much using AsyncLocalStorage like this has helped easily improve our backend web-server's performance. One of the major drawbacks to a monolith like ours can be that teams aren't able to easily isolate their code's performance from that of the rest of the monolith. Having insight into what is actually happening on a granular level is what's going to allow us to continue having an easy time scaling our monolith for a long time.

When the ClassDojo engineering team started using TypeScript on our backend, I was incredibly frustrated. It felt like I needed to constantly work around the type system, and it felt like the types weren't providing any value at all. And, they weren't providing any value to me: I had fundamental misconceptions about how TypeScript worked, and my attempts to work around the Type system by using lots of any and as created some truly abominable TypeScript code.

Type Inference

Whenever you create a variable using let, const, or var, and don't provide a type, TypeScript will infer the type: this means it will use its best guess for the type. These best guesses are pretty good, but they aren't magic!

If you use let or var, TypeScript will assume that it can re-assign to any similar value. If you write let method = "GET";, TypeScript will infer that method is a string, and will let you later reassign method: method = "KonMari". If instead you use const, const method = "GET", TypeScript will infer that method is of type "GET". This means when you use let, you'll often need to use a type. let method: HTTPMethod = "GET" will allow only type-safe reassignment.

When TypeScript infers types for Objects and Arrays, it will similarly give its best guess. In JavaScript, objects are mutable: if you set up a variable like const request = { method: "GET" }, it'll assume that the type that you want is { method: string } to let you update the method field. A type of { method: string } won't be usable by something that wants { method: HTTPMethod }, so you need to either explicitly tell it the type (const request: { method: HTTPMethod } = { method: "GET" }, or tell TypeScript that it's safe to infer a stricter type (const request = { method: "GET" as const }).

Here's a TypeScript playground that explores type inference in a bit more depth, and the type inference part of the handbook is great if you want a detailed introduction.

Why isn't it narrowing?

One of the things that I found most frustrating about TypeScript was writing a clause that felt like it should have narrowed the type of a variable and not have it actually narrow. I'd often use as to bypass the type system entirely and force something to narrow, but overriding TypeScript like this is a real anti-pattern. When I finally learned about type narrowing, and type guards, TypeScript became so much more pleasant to use.

One of the very first things I learned about JavaScript was that you should never use in with Objects because in doesn't differentiate between an object's properties and those of its prototype. In TypeScript, in is crucial to use for type narrowing. If you have a function that takes a type like Error | (Error & { type: "NotFound", table: string }) | (Error & { type: "NotAllowed", reason: string }), you can't write if (!err.type) return because TypeScript doesn't know whether err has that field or not. Instead, you need to write if (!("type" in err)) return and TypeScript won't error, and will correctly narrow the type.

One related confusion was why I couldn't use if statements to narrow a type. I'd try to write code like the following:

Don't do this!

1type NotFound = Error & { NotFound: true; table: string };
2type ServerError = Error & { ServerError: true; message: string };
3type ClientError = Error & { ClientError: true; status: number };
4
5function getResponse(err: Error | NotFound | ServerError | ClientError) {
6 if ((err as ClientError).ClientError) {
7 return { status: (err as ClientError).status, message: "client error" };
8 }
9 if ((err as NotFound).NotFound) {
10 const notFoundError = err as NotFound;
11 return {
12 status: 404,
13 message: `not found in ${notFoundError.table}`;
14 }
15 }
16
17 return {
18 status: 500,
19 message: (err as ServerError).message || "server error",
20 }
21}

TypeScript can automatically discriminate a union type if the members of a union all share a field. This can lead to much simpler, type-safe, and easier to work with code!

1type NotFound = Error & { type: "NotFound", table: string };
2type ServerError = Error & { type: "ServerError", message: string; };
3type ClientError = Error & { type: "ClientError", status: number; };
4
5function getResponse(err: Error | NotFound | ServerError | ClientError) {
6 // doing this first lets TypeScript discriminate using the `type` property
7 if (!("type" in err)) {
8 return {
9 status: 500,
10 message: "server error",
11 }
12 }
13
14 if (err.type === "ClientError") {
15 // err now has type ClientError, so we can use status!
16 return { status: err.status, message: "client error" };
17 }
18
19 if (err.type === "NotFound") {
20 return {
21 status: 404,
22 message: `not found in ${err.table}`
23 }
24 }
25
26 // it even narrows this to ServerError!
27 // although it may be wiser to have an explicit `if` statement and assert that every case is handled
28 return {
29 status: 500,
30 message: err.message,
31 }
32}

Finally, if there are more complex types that you need to narrow, writing a custom type guard function is always an option! This is a function that returns a boolean that lets TypeScript narrow a type whenever you call it!

1// `method isHTTPMethod` tells callers that any string that you've checked with this function is an HTTPMethod
2function isHTTPMethod (method: string): method is HTTPMethod {
3 return ["GET", "PUT", "POST", "DELETE"].includes(method);
4}

Here's a TypeScript playground where you can see how this works.

"Brands" are required for Nominal Typing

TypeScript uses "structural typing", which means that only the shape of something matters, and the name of the type is completely irrelevant. If something looks like a duck, it's a duck as far as TypeScript is concerned. This is surprising if you're coming from a "nominal typing" background where two types with the same shapes can't be assigned to each other.

1// this is valid TypeScript
2type EmailAddress = string;
3type Url = string;
4const emailAddress: EmailAddress = "myEmail@classdojo.com";
5const url: Url = emailAddress;

If you want nominal-style types for a string or number, you need to use "Brands" to create "impossible" types.

1type EmailAddress = string & { __impossible_property: "EmailAddress" };
2type URL = string & { __impossible_property: "Url" };
3const emailAddress = "myEmail@classdojo.com" as EmailAddress; // we need to use `as` here because the EmailAddress type isn't actually possible to create in JS
4const url: URL= emailAddress; // this now errors the way we'd want

(The above isn't how you'd actually want to write this code: I'm writing it in a way that hopefully makes it a bit more clear what's going on. If you'd like to see a more realistic example, take a look at this playground)

TypeScript isn't just "JS with types"

TypeScript is a great language, but just treating it as "JS with types" is a surefire recipe for frustration. It takes time to learn the language, and I wish I'd spent more of that time up-front reading through the docs: it'd have saved a ton of pain. The TypeScript handbook is great, and there are tons of great resources online to help understand TypeScript better. There's still a ton I don't know about TypeScript, but finally learning about inference, type narrowing, and structural typing has made developing with TypeScript so much nicer.

Older posts