array-type-performance-32-and-64.js

array-type-performance-32-and-64.js

//Ensure we have reproducible read / write sequence via pseudo-random index sequence.

export const MAX_RAND_INT = 4294967296;
export function splitmixUInt32(seed)
{
 return function() {
   seed |= 0;
   seed = seed + 0x9e3779b9 | 0;
   let t = seed ^ seed >>> 16;
   t = Math.imul(t, 0x21f0aaad);
   t = t ^ t >>> 15;
   t = Math.imul(t, 0x735a2d97);
   return ((t = t ^ t >>> 15) >>> 0);
  }
}

let randomUInt32 = splitmixUInt32(777);

//Goal: Compare array access performance between 64-bit arrays (1 element at a time) and 32-bit (2 elements at a time).
//Each case uses the same 31-bit number range for testing (see arrays-32-test.js).
//https://dev.to/alirezaebrahimkhani/be-careful-about-arrays-v8-engine-advice-1pmk

//constants
const seed = 777;
const randomUInt32 = splitmixUInt32(seed);

const bufferWidthPow = 12;
const bufferSizePow = bufferWidthPow + bufferWidthPow;
const bufferWidth = Math.pow(2, bufferWidthPow);
const bufferSize = bufferWidth * bufferWidth;

const REG = 0;
const SMI = 1;
const I32 = 2;
const U32 = 3;
const I64 = 4;
const U64 = 5;
const OBJ = 6;

let elementTypes = {};
elementTypes[REG] = 'regular';
elementTypes[SMI] = 'SMI';
elementTypes[I32] = 'Int32';
elementTypes[U32] = 'Uint32';
elementTypes[I64] = 'Int64';
elementTypes[U64] = 'Uint64';
elementTypes[OBJ] = 'Obj64x1';

//element type
const _32 = 0;
const _64 = 1;
const _64OBJ = 2;
const COMPONENTS_PER_ELEMENT = 3;
let bitsMult = {}
bitsMult[REG] = 0; //32
bitsMult[SMI] = 0; //32 (31)
bitsMult[I32] = 0; //32
bitsMult[U32] = 0; //32
bitsMult[I64] = 1; //64
bitsMult[U64] = 1; //64
bitsMult[OBJ] = 1; //64 (x2 actually, as 2 fields in object, never mind object pointer itself so 96 total?)

//order
const SEQ = 0;
const RND = 1;
const ORDER_COUNT = 2;
let orderNames = {}
orderNames[RND] = 'random';
orderNames[SEQ] = 'sequential';

//access type
const READ = 0;
const WRIT = 1;
const ACCESS_COUNT = 2;
let accessNames = {}
accessNames[READ] = 'read';
accessNames[WRIT] = 'write';

//--- Data to be tested ---//

let arraysByName = {};
arraysByName[REG] = new Array(bufferSize); //uncertain element type
arraysByName[SMI] = new Array(bufferSize).fill(1); //SMI enforced
arraysByName[I32] = new  Int32Array(bufferSize); //Not sure what kind of data we get here... 31 bits SMI must be casted?
arraysByName[U32] = new Uint32Array(bufferSize);
arraysByName[I64] = new  BigInt64Array(bufferSize >> 1); //div by 2
arraysByName[U64] = new BigUint64Array(bufferSize >> 1); //div by 2
arraysByName[OBJ] = new Array(bufferSize >> 1); //div by 2
for (let i = 0; i < arraysByName[OBJ].length; i++)
	arraysByName[OBJ][i] = {x: 0};

//--- Logic to be tested ---//

//3D table of array access functions. Each '+' signifies a dimensional division.
function calcIndex(elementType, order, access)
{
	return elementType * ACCESS_COUNT * ORDER_COUNT + //highest dimension
		   order       * ACCESS_COUNT + //middle dimension
		   access; //lowest dimension
}
let funcs = new Array(COMPONENTS_PER_ELEMENT * ORDER_COUNT * ACCESS_COUNT);
funcs[calcIndex(_32, SEQ, READ)] = sequentialRead32;
funcs[calcIndex(_32, SEQ, WRIT)] = sequentialWrite32;
funcs[calcIndex(_32, RND, READ)] = randomRead32;
funcs[calcIndex(_32, RND, WRIT)] = randomWrite32;

funcs[calcIndex(_64, SEQ, READ)] = sequentialRead64;
funcs[calcIndex(_64, SEQ, WRIT)] = sequentialWrite64;
funcs[calcIndex(_64, RND, READ)] = randomRead64;
funcs[calcIndex(_64, RND, WRIT)] = randomWrite64;

funcs[calcIndex(_64OBJ, SEQ, READ)] = sequentialRead64Obj;
funcs[calcIndex(_64OBJ, SEQ, WRIT)] = sequentialWrite64Obj;
funcs[calcIndex(_64OBJ, RND, READ)] = randomRead64Obj;
funcs[calcIndex(_64OBJ, RND, WRIT)] = randomWrite64Obj;


//randomisers (used for 32- and 64-bit cases)
function getNextRandomValue31()
{
	return randomUInt32() & 0b01111111111111111111111111111110; //lose a bit. >> converts to signed.
}

function getNextRandomValue32()
{
	return randomUInt32();
}

function getNextRandomIndex()
{
	let bitsDiff = 32 - bufferSizePow;
	return randomUInt32() >>> (bitsDiff + 1); //+1 for half the number of possible indices, since we read/write 2 at a time. >>> keeps as unsigned, >> converts to signed.
}

var getNextRandomValue =
[
	getNextRandomValue31,
	getNextRandomValue32,
];

//32-bit
function randomWrite32(array, i, isSMI)
{
	i = getNextRandomIndex(); //overwrite incoming.
	i *= 2; //twice the number of indices
	const value = getNextRandomValue[isSMI]();
	       array[i+0] = value;
	return array[i+1] = value;
}

function randomRead32(array, i)
{
	i = getNextRandomIndex(); //overwrite incoming.
	i *= 2; //twice the number of indices
	return (array[i + 1] << 32) | array[i + 0]; //TODO swap indices? check performance?
}

function sequentialWrite32(array, i, isSMI)
{
	i *= 2; //twice the number of indices
	const value = getNextRandomValue[isSMI]();
	       array[i + 0] = value; 
	return array[i + 1] = value; 
}

function sequentialRead32(array, i)
{
	i *= 2; //twice the number of indices
	return (array[i + 1] << 32) | array[i + 0]; //TODO swap indices? check performance?
}

//64-bit
function randomWrite64(array, i)
{
	i = getNextRandomIndex(); //overwrite incoming2.
	let value = getNextRandomValue31();
	return array[i] = BigInt((value << 32) | value);
}

function randomRead64(array, i)
{
	i = getNextRandomIndex(); //overwrite incoming.
	return array[i];
}

function sequentialWrite64(array, i)
{
	let value = getNextRandomValue31();
	return array[i] = BigInt((value << 32) | value);
}

function sequentialRead64(array, i)
{
	return array[i];
}

//64-bit obj
function randomWrite64Obj(array, i)
{
	i = getNextRandomIndex(); //overwrite incoming2.
	let value = getNextRandomValue31();
	return array[i].x = BigInt((value << 32) | value);
}

function randomRead64Obj(array, i)
{
	i = getNextRandomIndex(); //overwrite incoming.
	return array[i].x;
}

function sequentialWrite64Obj(array, i)
{
	let value = getNextRandomValue31();
	return array[i].x = BigInt((value << 32) | value);
}

function sequentialRead64Obj(array, i)
{
	return array[i].x;
}

//--- Testing logic ---//

const iterationsCount = bufferSize / 2; //usually we'd want to touch each element once on average. But here we touch two elements per func call, so split the count in half. Actually -- could be an arbitrary and separate number.

function test(order, access, elementType)
{
	let bits = bitsMult[elementType];
	
	let array = arraysByName[elementType];
	let funcIndex = calcIndex(bits, order, access);
	let func = funcs[funcIndex];
	
	let time0 = ( performance || Date ).now();
	let result = 0;
	let isSMI = elementType == SMI ? 1 : 0; //set it globally so as to be seen in func (avoids passing it)
	for (let i = 0; i < iterationsCount; i++)
	{
		result = func(array, i, isSMI);
	}
	let time1 = ( performance || Date ).now();
	let timeDiff = (time1 - time0) / iterationsCount;
	
	//result is logged out to prevent it being optimised out.
	console.log("(test result is ", result, ")", timeDiff); 
	
	//check the native format of this test, filling in the other result by div or mul.
	let timeDiffs = [0,0];
	if (bits == 0) //32
	{
		timeDiffs[0] = timeDiff; //32
		timeDiffs[1] = timeDiff * 2; //64
	}
	else //64
	{
		timeDiffs[0] = timeDiff / 2; //32
		timeDiffs[1] = timeDiff; //64
	}
	
	return timeDiffs;
}

function runTests()
{
	console.log("testing over", bufferSize,"elements and", iterationsCount, "iterations...")
		
	//Lets us decide the output format. we will use the according timeDiffs index / element.
	//note that since tests are either 32- or 64-bit by nature, we either divide or multiply results
	//in test() to make all results match in format (as described by the table heading below).
	//This can skew one's perspective, hence the ability to change this value between 32 or 64.  
	const bitsForOutput = 0; //+1*32 = 32 or 64
	
	let tableStr = `Times in milliseconds by category displayed as if all were ${1+(1-bitsForOutput)}x ${(bitsForOutput + 1) * 32}-bit ops:\n\n`;
	for (let elementType in elementTypes)
	{
		tableStr += elementTypes[elementType] + "\n";
		tableStr += "    sequ".padStart(11, " ") + "rand".padStart(11, " ")+"\n";
		for (let accessName in accessNames)
		{
			let rowStr = accessNames[accessName].slice(0, 4)+" ";
			for (let orderName in orderNames)
			{
				const timeDiffs = test(parseInt(orderName), parseInt(accessName), elementType);
			    rowStr += (timeDiffs[bitsForOutput].toFixed(6).padStart(10, " "))+" ";
			}
			tableStr += rowStr + "\n";
			
		}
		tableStr += "\n"
	}
	
	console.log(tableStr);
}

runTests();

Times in milliseconds by category displayed as if all were 2x 32-bit ops:

regular
       sequ       rand
read   0.000005   0.000088 
writ   0.000023   0.000038 

SMI
       sequ       rand
read   0.000005   0.000058 
writ   0.000028   0.000039 

Int32
       sequ       rand
read   0.000008   0.000060 
writ   0.000022   0.000034 

Uint32
       sequ       rand
read   0.000008   0.000065 
writ   0.000021   0.000032 

Int64
       sequ       rand
read   0.000004   0.000025 
writ   0.000006   0.000017 

Uint64
       sequ       rand
read   0.000004   0.000025 
writ   0.000006   0.000018 

Obj64x1
       sequ       rand
read   0.000002   0.000023 
writ   0.000024   0.000113 

This test is built specifically for considering applications where we'd be accessing struct-like equal to or wider than 64 bits.
Therefore, it is natural that 2x 32 bit operations will be considerably slower -- they are included for reference only.

It is based on doubling the number of array accesses to read or write the same data (see the *32 functions) as 32 bit words.

Results indicate that double access of 64-bit Int TypedArrays reduces all access times substantially. However:

• with both Big(U)int types, assuming we want to operate on the values numerically, a lot of casting (to Number) would be necessary, which can substantially reduce de facto running times (as tested in another example, unfortunately these casts are not fast in JS).
• Obj64x1 is not a great performer on writes; it requires a 64-bit pointer dereference followed by a 64-bit object field read, most likely this additional dereference is the reason. Like 32-bit accesses, this there mainly to provide a worst case bench mark.

We can conclude that if random access is the primary bottleneck (as it often is) and we actually need the data in (U)Int32 formats without infrequent or non-existent casting, we should prefer 64-bit TypedArrays. The trick then is to keep numeric casts infrequent.