Benchmark: Perf difference when using looping over collection vs creating a cached projection for that access pattern (medium array)

Perf difference when using looping over collection vs creating a cached projection for that access pattern (medium array) (version: 0)

Intent is to measure the benefit of creating multiple "cache projections" (for lack of a better name) when using Redux Toolkit's EntityAdapter. It already handles everything in an "entities" object (keys are ids, values are the entity) and manages a list of ids separately. If we want to access a specific item based on the value of another key on that object, we are forced to loop through all the entities (either with Object.keys, Object.values, a for..in, or using the ids list) to find it. The solution tested here is to maintain another object that's simply a mapping between the key we want to look for and the id of the corresponding object for fast access. It is obviously faster, but by how much?

Comparing performance of: finding item using find with Object.values vs finding item using find with Object.keys vs looping with for..in vs finding item using find without Object.values (accessing entities using the ids array) vs using the itemIdByUuid "projection" we created

Created: 2 years ago by: Registered User

Jump to the latest result

Script Preparation code:

function shuffleArray(array) {
    for (let i = array.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}

var ids = [];
var uuids = [];
var entities = {};
var itemIdByUuid = {};
for(let i = 0; i < 800; i++) {
  const obj = {
    id: `id${i}`,
    uuid: crypto.randomUUID(),
    foo: "bar",
    bar: "foo",
  };
  
  entities[obj.id] = obj;
  ids.push(obj.id);
  itemIdByUuid[obj.uuid] = obj.id;
}

Tests:

finding item using find with Object.values
const randomUUID = uuids[Math.floor(Math.random() * uuids.length)]; const itemMatchingSomeUUID = Object.values(entities).find((obj) => obj.uuid === randomUUID);
finding item using find with Object.keys
const randomUUID = uuids[Math.floor(Math.random() * uuids.length)]; const itemMatchingSomeUUID = Object.keys(entities).find((id) => entities[id].uuid === randomUUID);
looping with for..in
const randomUUID = uuids[Math.floor(Math.random() * uuids.length)]; let itemMatchingSomeUUID = null; for(const id in entities) { if(entities[id].uuid === randomUUID) { itemMatchingSomeUUID = entities[id]; break; } }
finding item using find without Object.values (accessing entities using the ids array)
const randomUUID = uuids[Math.floor(Math.random() * uuids.length)]; const itemMatchingSomeUUID = ids.map((id) => entities[id]).find((obj) => obj.uuid === randomUUID);
using the itemIdByUuid "projection" we created
const randomUUID = uuids[Math.floor(Math.random() * uuids.length)]; const itemMatchingSomeUUID = entities[itemIdByUuid[randomUUID]];

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
finding item using find with Object.values
finding item using find with Object.keys
looping with for..in
finding item using find without Object.values (accessing entities using the ids array)
using the itemIdByUuid "projection" we created

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 27 days ago):

LLMs can make mistakes. Check important info.

This benchmark measures the performance difference between four approaches to access an entity in an object:

1. **Looping through all entities using `Object.keys()` or `Object.values()`**: This approach iterates over all entities and finds the matching one by filtering based on the desired key.

2. **Using a cached projection (in this case, `itemIdByUuid`)**: The benchmark creates a separate object (`itemIdByUuid`) that maps the UUID to the corresponding entity ID. This allows for fast lookup of the entity using its UUID.

Let's analyze each approach:

### Looping through all entities

Pros: Simple and easy to implement. No extra memory allocation is required.

Cons: This approach has a high time complexity (O(n)), where n is the number of entities, making it inefficient for large datasets.

### Using a cached projection (`itemIdByUuid`)

Pros: Fast lookup with an average time complexity of O(1), since UUIDs are unique and can be hashed or used as keys in a hash table. This approach reduces the search space to a constant size, resulting in significant performance improvements.

Cons: Requires additional memory allocation for the `itemIdByUuid` object, which may not be feasible for very large datasets. Additionally, creating and maintaining this projection requires extra code and setup.

Other considerations:

*   The use of `uuids` array to shuffle the array before inserting entities into it introduces some randomness in the benchmark, making it harder to directly compare the performance of different approaches.
*   There's a possibility that due to cache locality and memory access patterns, some browsers might be optimized for certain patterns over others. This could affect the results.

Alternatives:

1.  **Using a data structure like a hash table or binary search tree**: Instead of using `itemIdByUuid`, consider implementing a more advanced data structure like a hash table or a balanced binary search tree. These would provide even faster lookup times (O(1) on average).
2.  **Precomputing and caching the results**: If possible, precompute the required values and cache them in memory. This approach can reduce the number of iterations needed for each test case.
3.  **Using a more efficient searching algorithm**: Depending on the nature of your data and the specific problem you're trying to solve, there may be other searching algorithms that would perform better than `Object.keys()` or `Object.values()`.

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/97.0.4692.71 Safari/537.36

Browser/OS: Chrome 97 on Mac OS X 10.15.7

View result in a separate tab

Test name	Executions per second
finding item using find with Object.values	7282.3 Ops/sec
finding item using find with Object.keys	7720.4 Ops/sec
looping with for..in	7462.6 Ops/sec
finding item using find without Object.values (accessing entities using the ids array)	11216.3 Ops/sec
using the itemIdByUuid "projection" we created	1699303.6 Ops/sec

Related benchmarks:

Perf difference when using looping over collection vs creating a cached projection for that access pattern (medium array) (version: 0)

Comparing performance of: finding item using find with Object.values vs finding item using find with Object.keys vs looping with for..in vs finding item using find without Object.values (accessing entities using the ids array) vs using the itemIdByUuid "projection" we created

Created: 2 years ago by: Registered User

Jump to the latest result

finding item using find with Object.values

finding item using find with Object.keys

looping with for..in

finding item using find without Object.values (accessing entities using the ids array)

using the itemIdByUuid "projection" we created

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated 27 days ago):