Performance in managing tree-like structures in multiplayer front-end apps

My wife, a full-stack designer, often asks for my help with CSS whenever a component breaks or she needs to adjust styles or properties. One day she mentioned a product designer struggling to fix a layout issue that occurred when the screen was enlarged. She couldn't understand why the designer couldn't make the change himself. This incident inspired us to create Jux, a code-based product design tool that integrates with the developer's codebase, allowing designers to design real products instead of just static design artifacts (mockups and prototypes).

Jux is a multiplayer, DOM-based design tool where all the elements are constructed from native browser elements. The output is production-ready UI components and compositions, ready to be used immediately in your codebase.

What are we trying to solve?

The DOM is hierarchical by its nature. One key challenge in building our product is data representation and how we communicate with it. We built a DOM-based canvas (think of your typical vector-based design tool, but with real and complex web elements like select boxes, dropdowns, and complete pages).

• Users interact with the canvas… a lot! They change positions, dimensions, colors, etc. This means we are doing LOTS of data updates. It also means searching for the desired node in the tree for each update. As the tree grows, search performance degrades.
• Multiplayer and collaboration support - changes in one client should be immediately reflected in another. While conflict resolution is handled by CRDT on the server side, connected clients need to update their own state by searching for and updating or creating the affected node.
• Browsers run most tasks on the main thread. When the main thread is busy executing our JavaScript code or performing a rendering cycle, the display does not update or respond to user interaction, leading to unresponsive or frozen pages. In other words - a poor user experience.

So considering this complexity, how can we represent tree structures in our UI state?

There are plenty of articles and tutorials on tree-like data structures, their different types, and how to use / search them. What I was lacking was practical examples on how to optimize them for our frontend application considering our unique use cases. This shares some of our research.

Optimizing Tree-like Data Structures for Frontend Performance

As a company committed to delivering seamless user experiences, performance is paramount in our development ethos. Efficiently managing hierarchical data structures like trees is crucial for optimal performance. One powerful technique for optimizing tree structures is normalization. It involves organizing data in a flat, denormalized format, allowing for easier retrieval and manipulation. Below, I’ll discuss why normalization is essential for front-end applications dealing with tree structures and how it can significantly improve performance.

The Challenge of Tree Structures

Tree structures inherently pose challenges for front-end developers due to their hierarchical nature. Rendering a tree often involves deeply nested data structures, leading to performance issues, especially as the tree size grows. Manipulating and updating such structures can become computationally expensive, resulting in sluggish user experiences.

Consider a file explorer component that displays a hierarchical view of directories and files. Each directory can contain subdirectories and files, forming a tree structure. Rendering this tree directly from nested data can result in repetitive computations and re-rendering unaffected parts of the tree upon updates.

The Solution: Normalization

Normalization addresses these challenges by restructuring the data into a flat format, using unique identifiers to establish relationships between entities. Instead of nesting data, normalization involves storing each entity (node) separately and referencing its parent and children via identifiers. This approach facilitates more efficient data retrieval and updates, leading to improved performance.

Let's illustrate this with a simplified example of a tree:

const tree = [
 {
   id: 1,
   name: 'Root',
   parentId: null,
   children: [
     {
       id: 2,
       name: 'Child 1',
       parentId: 1,
       children: [
         {
           id: 3,
           name: 'Grandchild 1',
           parentId: 2,
           children: []
         },
         {
           id: 4,
           name: 'Grandchild 2',
           parentId: 2,
           children: []
         }
       ]
     },
     {
       id: 5,
       name: 'Child 2',
       parentId: 1,
       children: []
     }
   ]
 }
];


To normalize this structure, we'll break it into two parts: a dictionary of nodes and a list of top-level node IDs. Each node will reference its children by their IDs rather than embedding them directly.

const normalizedData = {
 nodes: {
   1: { id: 1, name: 'Root', parentId: null, children: [2, 5] },
   2: { id: 2, name: 'Child 1', parentId: 1, children: [3, 4] },
   3: { id: 3, name: 'Grandchild 1', parentId: 2, children: [] },
   4: { id: 4, name: 'Grandchild 2', parentId: 2, children: [] },
   5: { id: 5, name: 'Child 2', parentId: 1, children: [] }
 },
 rootIds: [1]
};

Benefits of Normalization for Frontend Applications

1. Quick updates: Accessing a node by its ID is very fast with a normalized structure since you can directly reference it in a dictionary (hash map) rather than traversing a nested structure. This structure makes it easy to create, read, update or delete new records; all operations will take place in a linear or constant manner.
2. Filtering and Querying: Filtering nodes based on certain criteria (e.g., all nodes with a specific parentId) is more efficient with a normalized structure.
3. Readability: Organizing data in an easy-to-understand manner facilitates efficient processing and retrieval with straightforward logic.
4. Optimized Rendering: Normalizing tree structures allows for more efficient rendering algorithms. Instead of traversing deeply nested data, rendering components can directly access and display flattened data, resulting in faster rendering times.
5. Simplified State Management: Managing state in frontend applications becomes more manageable with normalized data structures. Libraries like Zustand can efficiently handle normalized data, simplifying state updates and ensuring consistency across components.
6. Enhanced Performance: By reducing unnecessary computations and minimizing re-renders, normalization significantly enhances the overall performance of frontend applications. Users experience smoother interactions, especially when dealing with large or dynamically changing tree structures.
7. Large Data Sets: Normalized structures handle large data sets better since operations on nodes are localized to specific parts of the data rather than traversing potentially large nested structures.

The Results

After implementing normalization, we saw immediate performance improvements. Even with a large number of elements on the canvas, the application remained responsive and fast - a direct result of this architectural change.

Let's conduct a performance test to compare search and update time of nodes between normalized and nested data structures using a simulated React code. This code generates a tree structure with 1k, 10k and 100k random nodes with random order (limited to 10 children per node, and a total tree depth of 14):

1k nodes:
Nested Tree Search Time: 1.1000000 ms
Normalized Tree Search Time: 0.0000000 ms

Nested Tree Update Time: 0.1000000 ms
Normalized Tree Update Time: 0.0000000 ms

10k nodes:
Nested Tree Search Time: 1.0999999 ms
Normalized Tree Search Time: 0.0000000 ms

Nested Tree Update Time: 0.3000000 ms
Normalized Tree Update Time: 0.0000000 ms

100k nodes:
Nested Tree Search Time: 3.5999999 ms
Normalized Tree Search Time: 0.0000000 ms

Nested Tree Update Time: 1.3999999 ms
Normalized Tree Update Time: 0.0000000 ms

As you can see - significant optimization improvements, and this is in addition to framework-specific issues such as reactivity and state management (not covered in this blog post).

Simplicity is Key

Throughout my career, I've learned that the key to building high-performance applications lies in simplicity. It's easy to get caught up in the excitement of big ideas and elegant solutions, but often, the most complicated solutions are not the best.

I've seen developers, including myself, fall into the trap of creating overly complex code, thinking it showcases our skills. However, I've come to realize that this approach is self-deception. The real magic of code lies in its simplicity and maintainability. We should write code not just for ourselves, but for the next person who will work on it. By keeping things simple and easy to understand, we can create applications that are maintainable, scalable, and performant.

Conclusion

Normalizing tree structures in frontend applications is a powerful technique for improving performance and scalability. By restructuring hierarchical data into a flat format, developers can optimize rendering, simplify state management, and enhance overall application performance.

At Jux, techniques like normalization are just one way we're pushing the boundaries of what's possible in design tools - while still always keeping our focus on simplicity.

‍