Let's say you're working with a large relational data structure in JavaScript and need to access the information quickly, often. Hash tables used behind the scenes in JS exposed somehow should make it possible to access large data structures with O(1) efficiency. But my code example below will demonstrate that it's not nearly 0(1) with normal objects. However, a top answer on SO, discussing the efficiency of arrays (and thus objects), claims that arrays should perform "just like regular object values" leveraging a hash table:
In contrast to most languages, which implement arrays with, well, arrays, in Javascript Arrays are objects, and values are stored in a hashtable, just like regular object values. As such:
- Access - O(1)
- Appending - Amortized O(1) (sometimes resizing the hashtable is required; usually only insertion is required)
- Prepending - O(n) via
unshift, since it requires reassigning all the indexes- Insertion - Amortized O(1) if the value does not exist. O(n) if you want to shift existing values (Eg, using
splice).- Deletion - Amortized O(1) to remove a value, O(n) if you want to reassign indices via
splice.- Swapping - O(1)
A few simple tests show that both objects and maps in JavaScript using V8 offer only O(n) or worse performance, with weak maps sometimes but not always offering O(1):
The chart will look significantly different each time you run it, but the one thing that stays consistent is arrays are the only JavaScript data structure of the four that maintain O(1) access efficiency consistently. Not even Weak Maps consistently offer 0(1).
let count;
let start;
let end;
let access;
let counts = [];
//object speed test
let objData = [];
let obj = {}
count = 0;
// don't raise this above i < 5, the loops will hang
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
if (i === 1) j -= 100;
for (let k = 0; k < j; k++) {
count++;
obj['s' + count] = true;
}
start = performance.now()
for (let n = 0; n < 1000; n++) {
// if you access the object iteratively, V8 seems to actually optimize performance massively
// via prediction, but typically with relational data we have non-iterative use cases.
// replace the access line with the following to see that performance optimization
// access = obj['s' + count];
access = obj['s' + Math.floor(Math.random() * count)];
}
end = performance.now()
objData.push(end - start);
counts.push(count);
}
//array speed test
let arrData = [];
let arr = []
count = 0;
// don't raise this above i < 5, the loops will hang
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
if (i === 1) j -= 100;
for (let k = 0; k < j; k++) {
count++;
arr[count] = true;
}
start = performance.now()
for (let n = 0; n < 1000; n++) {
// if you access the object iteratively, V8 seems to actually optimize performance massively
// via prediction, but typically with relational data we have non-iterative use cases.
// replace the access line with the following to see that performance optimization
// access = obj['s' + count];
access = arr[Math.floor(Math.random() * count)];
}
end = performance.now()
arrData.push(end - start);
}
// map speed test
let mapData = [];
let map = new Map();
count = 0;
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
if (i === 1) j -= 100;
for (let k = 0; k < j; k++) {
count++;
map.set('s' + count, true)
}
start = performance.now()
for (let n = 0; n < 1000; n++) {
access = map.get('s' + Math.floor(Math.random() * count));
}
end = performance.now()
mapData.push(end - start);
}
// weak map speed test
let weakMapData = [];
let weakMap = new WeakMap();
let objs = [];
for (let i = 0; i < 1000000; i++) {
objs.push({
data: Math.random()
});
}
let objsLen = objs.length - 1;
count = 0;
for (let i = 0, j = 100; i < 5; i++, j *= 10) {
if (i === 1) j -= 100;
for (let k = 0; k < j; k++) {
count++;
weakMap.set(objs[Math.floor(Math.random() * objsLen)], objs[Math.floor(Math.random() * objsLen)]);
}
start = performance.now()
for (let n = 0; n < 1000; n++) {
access = weakMap.get(objs[Math.floor(Math.random() * objs.length)]);
}
end = performance.now()
weakMapData.push(end - start);
}
let colorSchemes = ['rgb(255, 99, 132)', 'rgb(242, 101, 36)', 'rgb(113, 38, 242)', 'rgb(48, 221, 86)']
var ctx = document.getElementById('myChart').getContext('2d');
var myLineChart = new Chart(ctx, {
type: 'line',
data: {
labels: counts,
datasets: [{
label: 'Objects',
data: objData,
pointBackgroundColor: colorSchemes[0],
backgroundColor: 'rgba(0,0,0,0)',
borderColor: colorSchemes[0],
borderWidth: 2
},
{
label: 'Maps',
data: mapData,
pointBackgroundColor: colorSchemes[1],
backgroundColor: 'rgba(0,0,0,0)',
borderColor: colorSchemes[1],
borderWidth: 2,
},
{
label: 'WeakMaps',
data: weakMapData,
pointBackgroundColor: colorSchemes[2],
backgroundColor: 'rgba(0,0,0,0)',
borderColor: colorSchemes[2],
borderWidth: 2,
},
{
label: 'Arrays',
data: arrData,
pointBackgroundColor: colorSchemes[3],
backgroundColor: 'rgba(0,0,0,0)',
borderColor: colorSchemes[3],
borderWidth: 2,
}
]
}
});<script src="https://cdn.jsdelivr.net/npm/chart.js@2.9.3/dist/Chart.min.js"></script>
<canvas id="myChart" width="400" height="400"></canvas>Is the claim correct and my test wrong? Or is the claim inaccurate, and objects can't offer the same access efficiency as arrays? Shouldn't Weak Maps offer 0(1) access as well?
It's not just that answer. The MDN weak map documentation implies better than 0(n) performance on weak maps by pointing out that an inconvenience of the alternative would be 0(n) efficiency.
