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

Perf difference when using looping over collection vs creating a cached projection for that access pattern (large 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: 4 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 < 5000; 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

Latest run results:

No previous run results

This benchmark does not have any results yet. Be the first one to run it!

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

This benchmark measures the performance difference between four approaches to access a specific entity in an object when the key is not available:

1. **Finding item using `find` with `Object.values`:** This approach uses `Object.values(entities)` to get an array of entities and then finds the item that matches the UUID using `Array.prototype.find`.
2. **Finding item using `find` with `Object.keys`:** This approach uses `Object.keys(entities)` to get an array of keys and then finds the key that corresponds to the UUID using `Array.prototype.find`.
3. **Looping with `for..in`:** This approach loops through all entities using `for...in` and checks if the current entity's UUID matches the target UUID.
4. **Finding item using `find` without `Object.values` (accessing entities using the `ids` array):** This approach uses the precomputed `itemIdByUuid` object to directly access the corresponding entity ID.

Let's break down each approach:

### 1. Finding item using `find` with `Object.values`

* **Pros:**
	+ Easy to implement
	+ Uses built-in functions, reducing overhead
* **Cons:**
	+ Creates a new array and iterates through it, which can be slower for large datasets
	+ Requires additional memory allocation

### 2. Finding item using `find` with `Object.keys`

* **Pros:**
	+ Similar to the first approach, but uses keys instead of values
	+ Still easy to implement
* **Cons:**
	+ Creates a new array and iterates through it, which can be slower for large datasets
	+ Requires additional memory allocation

### 3. Looping with `for..in`

* **Pros:**
	+ Uses a straightforward loop that directly accesses the entity data
	+ No additional function calls or memory allocation required
* **Cons:**
	+ Can be slower due to the overhead of the loop and potential issues with object iteration
	+ May not work as expected if the object is modified during iteration

### 4. Finding item using `find` without `Object.values` (accessing entities using the `ids` array)

* **Pros:**
	+ Directly accesses the entity data using the precomputed `itemIdByUuid` object
	+ No additional function calls or memory allocation required
* **Cons:**
	+ Requires the `itemIdByUuid` object to be computed beforehand, which can add overhead
	+ May not work as expected if the object is modified during execution

The benchmark results show that the first three approaches have similar performance characteristics, with looping using `for..in` being the slowest. The fourth approach, which uses the precomputed `itemIdByUuid` object, is significantly faster due to its direct access to the entity data.

In general, when dealing with large datasets and performance-critical code, it's essential to consider the trade-offs between different approaches and choose the one that best balances complexity, overhead, and desired performance.

Related benchmarks: