I noticed this behaviour while solving this leetcode problem:
https://leetcode.com/problems/search-a-2d-matrix/description/
Here is the code:
function searchMatrix(matrix, target) {
const len = matrix.length;
for (let i = 0; i < len; i++) {
//const row = matrix.shift(); // if i access row using matrix.shift() the code executes in less than 100 ms.
const row = matrix[i] // But if i access the row via indexing. then it takes more than 2000ms and sometimes even gives Time limit exceeded.
let start = 0, end = row.length - 1;
while (start <= end) {
const mid = start + Math.floor((end - start) / 2);
if (row[mid] === target) return true;
if (row[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return false;
}
In this code if i access row using const row = matrix.shift();
the code executes in less than 100 ms.
but if i access the row via indexing using const row = matrix[i]
. then it takes more than 2000ms and sometimes even gives Time limit exceeded.
Please help me understand why there is such a huge performance difference.
I checked Ecma script specifications here:
https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.shift
and for shift() , internally java script also uses a while loop with indexing so it should take O(n) time for each row and it should be slower than indexing.
i Tried ChatGpt and Gemini and got some info. But it dint cite any reference so it might be making things up or hallucinating. here is the answer Gemini gave:
“Here are key factors contributing to shift()’s efficiency:
Built-in Optimizations: JavaScript engines are heavily optimized for common array operations like shift(). They often implement them using low-level code that’s significantly faster than plain JavaScript loops. These optimizations can include:
In-Place Shifting: Manipulating internal pointers to elements within the same memory block, minimizing data movement and avoiding unnecessary memory reallocations.
Cache-Friendly Rearrangement: Reordering elements in a way that maximizes cache utilization, leading to faster access times for subsequent operations.
Hidden Overheads in for Loops: While for loops appear simpler, they can involve subtle overheads that shift() often avoids:Variable Lookups: Each iteration of a for loop requires looking up loop variables and condition values, adding some overhead.
Bounds Checks: Loops often involve explicit bounds checks to ensure array access is within valid limits, potentially incurring additional costs.
Potentially Less Efficient Rearrangement: Manually rearranging elements in a for loop might not always be as cache-friendly as the optimized implementations used for shift().
Additional Considerations:Array Size: The performance difference between shift() and indexing can become more pronounced with larger arrays, as shift()’s optimizations become more beneficial for larger data sets.
Data Types: The specific data types stored in the array can also influence performance, as optimizations might be tailored for certain types (e.g., numbers).”