Using Jest with coverage and BenchmarkJS helped me identify optimization opportunities for my recursive lib

Cover image from picwalls.

The problem I tried to solve

By default, GraphQL adds a __typeName attribute to every element for each query. This attribute helps you determine what type represents each object.

GraphQL services provide a few meta fields, the rest of which are used to expose the Introspection system.

Source: https://graphql.org/learn/queries/#meta-fields

But when you have to invoke a mutation, you cannot pass everything. GraphQL will complain if you have unknown attributes for a given input or type. Hence, you need to remove, at least, the __typeName attribute.

In addition, we can have multiple structures: a simple object, an array of simple objects, an object with nested object, an array of objects with nest... Ok, yes, a lot of possibilities.

So, how could you remove each of those attributes without knowing that much about the structure of the data?

The first solution

Github repo: https://github.com/lgraziani2712/deep-delete

The key point to solve the problem is recursivity. Since you don't know how many objects and array you have, the function must access and process those structures and then return each time the data is not an array nor an object (the base case).

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself).

Source: https://en.wikipedia.org/wiki/Recursion_(computer_science)#Recursive_functions_and_algorithms

First commit solution:

function deepDelete(keyToSearch, data) {
  if (Array.isArray(data)) {
    // Recursive case
    return data.map(element => deepDelete(keyToSearch, element));
  }
  if (!data || typeof data !== 'object') {
    // Base case (anything different than array or data)
    return data;
  }

  return Object.keys(data).reduce((partial, key) => {
    if (key === keyToSearch) {
      // Base case (the key to be deleted)
      return partial;
    }
    // Recursive case
    partial[key] = deepDelete(keyToSearch, data[key]);

    return partial;
  }, {});
}

Limitations of this solution

• What would happen if I want to remove more than one key? I need to process my data multiple time just for that? (It's insane, yeah).

  This is solved in v1.1.0. You can pass an array of strings as a first param.

• Is it really works as expected?

  • I'm not 100% sure. It doesn't have tests.

  Are since v2.1.0.

• How many times (hence, resource consumtion) is the function called?

  • I don't know. I don't have metrics nor code coverage.

  Are since v2.1.0.

• What really are the types that must accept the data parameter? Can be anything, or just one or two?

  Since v2.1.0 it only accepts Object | Array<Object>

• Can take advantage of things like V8 TurboFan optimizing compiler?

  • I don't really know.

Latests benchmark results

Before I talk about how I found optimization opportunities, I want to show you the latests benchmark results:

As you can see (or hear), the version v2.1.0 is the fastest.

Test Coverage really helped me find optimization opportunities

When I was writting tests, I configured Jest to generate the test coverage, to help me know if I was testing everything. What I didn't know was that the coverage it also tells you how many times a line is executed, as you can see in the following image:

Let's analyse the result:

• Line 10 was executed 10/24 times. The data parameter had an array 10 times.
• Line 13 was executed 8/24 times. The data parameter had an empty value or something different than an object.
• Line 17 was executed 6/24 times, so there were 6 objects.
• Line 19 was executed 4/8 times, which means that there were deleted four keys.
• Line 21 was executed 4/8 times. This means that the object had other 4 keys that were needed to be processed by calling deepDelete again just to returns itself.

Viewing this made me think that there were a lot of function calls, more than the necessary. At that point, deepDelete was being called for every type of value. Every. Type. Of. Value. There are two lines in where was possible to improve this. Those lines are 10 and 21. Instead of just invoking the function, it could check if the element is an array or an object, and if not, not calling it.

This improvement was made for version 2.0.1:

With this changes and a few minor fixes & improvements, I was able to reach v2.1.0 and get the results of the benchmark mentioned before.

Conclusion

Code coverages not also let you know which paths of your application you're testing but it also can help determine optimization points. Using it in conjunction with BenchmarkJS you'll be able to have more metrics about your code!