node / javascript performance : Set vs Object and Map vs Object

12021015.md

Set vs Object

node version : v4.1.2
platform: Intel I7, 16G DDR3, Ubuntu x64

var theSet = new Set();
start = process.hrtime();
/***********************************/
for(let i = 0 ; i < N; i++ ) {
    let v = i%20;
    if (!theSet.has(v))
        theSet.add(v);
}
/***********************************/
console.log('section 1 : ' + timeUse(start));


obj = {};
start = process.hrtime();
/***********************************/
for(let i = 0 ; i < N; i++) {
    let v = i%20;
    if (!obj[v])
        obj[v] = 1;

}
/***********************************/
console.log('section 2 : ' + timeUse(start));

result :

# N = 1M
section 1 : 28348894ns
section 2 : 13017222ns

# N = 1K
section 1 : 1616666ns
section 2 : 109862ns

conclusion: If unnecessary, use Object instead of Set for performance benefit.

Map vs Object

var themap = new Map();
start = process.hrtime();
/***********************************/
for(let i = 0 ; i < N; i++ ) {
    let v = i%20;
    if (!themap.get(v))
        themap.set(v, i);
}
/***********************************/
console.log('section 1 : ' + timeUse(start));


obj = {};
start = process.hrtime();
/***********************************/
for(let i = 0 ; i < N; i++) {
    let v = i%20;
    if (!obj[v])
        obj[v] = 1;
}
/***********************************/
console.log('section 2 : ' + timeUse(start));

result:

# N = 1M
section 1 : 27290298ns
section 2 : 12362120ns

# N = 1K
section 1 : 1749059ns
section 2 : 63746ns

conclusion: same as Set vs Object

The performance depends on the characteristic of the input data.
If you can expect low percentage of duplicates in your data, Set is faster.
Refer to https://github.com/jngbng/set-vs-object

Should be interesting to redo this test with modern Node (native support of ES6), and with non-numerical keys. Most common use case for these data structures remain with string keys, if you have sequential numerical keys, you better use an array... 😄

What a dumb test let v = i%20.

String key access/write speed (Edited because test had too many flaws)

TL;DR:
Objects: slowest key access, slowest key write.
Sets: fastest key access, fastest key write.
Map: fast key access, fast key write.

Results of modified test when keys are relatively long strings (1x2.6Ghz cpu, node-v12.13.0-linux-x64):

All times in nanoseconds. W - write, R - access aka 'read'.
1 Million keys processed.

MapW : 1451322615
MapR : 475388668

SetW : 1345909415
SetR : 342153791

ObjW : 4223606810
ObjR : 813454233

SetW : 1408910400
SetR : 347006460

ObjW : 4063972437
ObjR : 767037134

MapW : 1533040516
MapR : 513181434

ObjW : 3972683227
ObjR : 798928083

MapW : 1498085287
MapR : 512821606

SetW : 1549353712
SetR : 380987238

Source (formatting sucks in comments):

	// I've read long time ago that reverse while loop can help to miss cache
	// Never believed this claim but just in case it's true we will utilize it
	// @note: For test purity we must perform writes and reads in separate functions (6 total)
	// @note: For test purity we must exclude existance checks or even add test only for it (3 extra functions)
	var N	=	1000000;
	// Map => Set => Obj
	setTimeout(function(){
		mapTest(N);
		setTimeout(function(){
			setTest(N);
			setTimeout(function(){
				objTest(N);
			}, 100);
		}, 100);
	}, 16);
	
	// Set => Obj => Map
	setTimeout(function(){
		setTest(N);
		setTimeout(function(){
			objTest(N);
			setTimeout(function(){
				mapTest(N);
			}, 100);
		}, 100);
	}, 16);
	
	// Obj => Map => Set
	setTimeout(function(){
		objTest(N);
		setTimeout(function(){
			mapTest(N);
			setTimeout(function(){
				setTest(N);
			}, 100);
		}, 100);
	}, 16);
	
	
	
	
	function timeDiff(hrtime){
		var t	=	process.hrtime(hrtime);
		return t[1] + t[0] * 1000000000;
	}
	
	
	
	
	
	function mapTest(N){
		var
		themap	=	new Map(),
		tmp		=	null,
		str		=	'this/is/strange/path/name/that/never/will/be/used/231313.js?abcd=0',
		keys	=	(function(){
			var res	=	[];
			for(let i = 0 ; i < N; i++ ){
				res[i]	=	i + str;
			}
			return res;
		})(),
		v		=	null,
		i		=	0,
		start	=	0;
		
		start = process.hrtime();
		i	=	N;
		while(i--){
			v	=	keys[i];
			if (!themap.has(v))
			themap.set(v, i);
		}
		console.log('MapW : ' + timeDiff(start));
		
		start = process.hrtime();
		i	=	N;
		while(i--){
			v	=	keys[i];
			if (themap.has(v))
			tmp	=	themap.get(v, i);
		}
		console.log('MapR : ' + timeDiff(start));
		console.log('');
	}
	
	
	
	function setTest(N){
		var
		theSet	=	new Set(),
		tmp		=	null,
		str		=	'this/is/strange/path/name/that/never/will/be/used/231313.js?abcd=0',
		keys	=	(function(){
			var res	=	[];
			for(let i = 0 ; i < N; i++ ){
				res[i]	=	i + str;
			}
			return res;
		})(),
		v		=	null,
		i		=	0,
		start	=	0;
		
		start = process.hrtime();
		i	=	N;
		while(i--){
			v	=	keys[i];
			if (!theSet.has(v))
			theSet.add(v);
		}
		console.log('SetW : ' + timeDiff(start));
		
		start	=	process.hrtime();
		i	=	N;
		while(i--){
			v	=	keys[i];
			if (theSet.has(v))
			tmp	=	v;
		}
		console.log('SetR : ' + timeDiff(start));
		console.log('');
	}
	
	
	
	function objTest(N){
		var obj	=	{},
		tmp		=	null,
		str		=	'this/is/strange/path/name/that/never/will/be/used/231313.js?abcd=0',
		keys	=	(function(){
			var res	=	[];
			for(let i = 0 ; i < N; i++ ){
				res[i]	=	i + str;
			}
			return res;
		})(),
		v		=	null,
		i		=	0,
		start	=	0;
		
		start	=	process.hrtime();
		i	=	N;
		while(i--){
			v	=	keys[i];
			if (!obj.hasOwnProperty(v))
			obj[v]	=	1;
		}
		console.log('ObjW : ' + timeDiff(start));
		
		start	=	process.hrtime();
		i	=	N;
		while(i--){
			v	=	keys[i];
			if (obj.hasOwnProperty(v))
			tmp	=	obj[v];
		}
		console.log('ObjR : ' + timeDiff(start));
		console.log('');
	}

node --version: v14.17.3

let i = 1;
function intkey() {
    return ++i;
}
const N = 10_000;

function timeUse(start) {
  return process.hrtime.bigint() - start + "ns";
}

function writeObj() {
  const obj = {};
  const start1 = process.hrtime.bigint();
  for (let i = 0; i < N; i++) {
    let v = intkey();
    if (!obj[v]) obj[v] = 1;
  }
  console.log("write obj : " + timeUse(start1));
}

function writeMap() {
  const map2 = new Map();
  const start2 = process.hrtime.bigint();
  for (let i = 0; i < N; i++) {
    let v = intkey();
    if (!map2.get(v)) map2.set(v, i);
  }
  console.log("write map : " + timeUse(start2));
}

function readObj() {
  const obj = {};
  for (let i = 0; i < N; i++) {
    let v = intkey();
    if (!obj[v]) obj[v] = 1;
  }
  const keys = Object.keys(obj);
  const start1 = process.hrtime.bigint();
  keys.map((key) => obj[key]);
  console.log("read obj : " + timeUse(start1));
}

function readMap() {
  const map2 = new Map();
  for (let i = 0; i < N; i++) {
    let v = intkey();
    if (!map2.get(v)) map2.set(v, i);
  }
  const keys = [...map2.keys()];
  const start2 = process.hrtime.bigint();
  keys.map((key) => map2.get(key));
  console.log("read map : " + timeUse(start2));
}

for (let i = 0; i < 10; i++) {
    console.log(`Run ${i + 1}`);
    writeObj();
    writeMap();
    readObj();
    readMap();
    console.log(`--`);
}

Run 1
write obj : 2303917ns
write map : 1865166ns
read obj : 308208ns
read map : 521791ns
--
Run 2
write obj : 2803708ns
write map : 2739375ns
read obj : 755625ns
read map : 206875ns
--
Run 3
write obj : 6042792ns
write map : 1117125ns
read obj : 949792ns
read map : 321958ns
--
Run 4
write obj : 1998833ns
write map : 1553000ns
read obj : 699375ns
read map : 302291ns
--
Run 5
write obj : 2011792ns
write map : 662583ns
read obj : 445417ns
read map : 303583ns
--
Run 6
write obj : 2001375ns
write map : 578333ns
read obj : 422083ns
read map : 228959ns
--
Run 7
write obj : 2040500ns
write map : 872417ns
read obj : 419083ns
read map : 253708ns
--
Run 8
write obj : 2002958ns
write map : 618000ns
read obj : 429000ns
read map : 208916ns
--
Run 9
write obj : 1977958ns
write map : 570084ns
read obj : 415666ns
read map : 216000ns
--
Run 10
write obj : 2005333ns
write map : 787584ns
read obj : 421000ns
read map : 208042ns
--

It should give different result with "x"+v instead of just v.

https://stackoverflow.com/a/62351925/2804342