query() performance

[felixhaeberle]

Context

We often spoke about it in the last weeks, so I'll kickstart this now and we will see if there is potential to change something or not.

The current implementation of query operations, specifically the get, update, and delete functions, relies on iterating over the body array to find a specific message based on its ID. This approach has a time complexity of O(n), where n represents the number of messages in the array.

Proposal (Brainstorm)

Considering that the object structure (Resource / Message,...) cannot be changed because we want to prevent a breaking change, we could explore alternative strategies to enhance the performance of these operations within the given constraints. Here are a few suggestions, which come to my mind in general:

Indexing

• create an additional data structure, like an index or a lookup table, to map message IDs to their corresponding array indices
• instead of iterating over the entire array, we can perform direct lookups using the index
• indexing operation can be done during the initialization or whenever the array is modified

Caching

• implement a caching mechanism to store frequently accessed or recently accessed messages in memory
• help avoid repetitive iterations over the array for commonly requested messages

Sorting

• if the messages in the array are sorted based on their IDs, we could consider utilizing binary search algorithms for faster retrieval
• Binary search has a time complexity of O(log n), which can be more efficient than linear search

Partial Updates

• instead of updating the entire message object, we could think of introducing a mechanism to perform partial updates
• only the necessary fields are modified, reducing the overall processing time

---

Although these optimizations may introduce additional complexity, they could have the potential to significantly improve the performance of message operations without modifying the underlying object structure — but as I said, we need to observe the impact of those changes and if the resources are well spend here.

[samuelstroschein]

1. Yes, we can improve the performance.
2. We decided it's not a priority Improve performance of query functions #1009
3. The brainstorming is nice but overarching. Use a profiler, investigate the largest slowdown, and focus on the largest slowdown first. From what we know, we just need an index to speed up get requests which should be doable without breaking changes. See Improve performance of query functions #1009 (comment).

@felixhaeberle Can we close this in favor of #1009 to not have duplicate discussions?