Last active
March 30, 2023 13:40
Star
You must be signed in to star a gist
Bit Array iterator test bail early forEach - pre-alloc output array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{"title":"Bit Array iterator test bail early forEach - pre-alloc output array","initialization":"class BitArray1 {\n constructor(length) {\n this.bits = new Uint32Array(Math.ceil(length / 32));\n this.length = length;\n }\n\n forEach(cb) {\n const {bits, length} = this;\n let i = 0, v = 0;\n while(i + 32 < length) {\n v = bits[i >> 5];\n for (let j = 1; j; j <<= 1) {\n\t cb((v & j) ? true : false, i++, bits);\n }\n }\n v = bits[i >> 5];\n for(; i < length; i++) {\n cb((v & 1) ? true : false, i, bits);\n v >>= 1;\n }\n }\n}\n\nclass BitArray2 {\n constructor(length) {\n this.bits = new Uint32Array(Math.ceil(length / 32));\n this.length = length;\n }\n\n forEach(cb) {\n const {bits, length} = this;\n let i = 0;\n while(i + 32 < length) {\n const v = bits[i >> 5];\n if (v === 0) {\n for (let j = 0; j < 32; j++) cb(false, i++, bits);\n continue;\n }\n for (let j = 1; j; j <<= 1) {\n cb((v & j) ? true : false, i++, bits);\n }\n }\n let v = bits[i >> 5];\n while(i < length) {\n cb((v & 1) ? true : false, i++, bits);\n v >>>= 1;\n }\n }\n}\n\nconst bitArr1 = new BitArray1(10000);\nconst bitArr2 = new BitArray2(10000);\n","setup":"const out = [false];\nfor (let i = 0; i < bitArr1.length; i++) out[i] = false;\n{\n const {random} = Math;\n for (let i = 0, {bits} = bitArr1; i < bits.length; i++) {\n bits[i] =\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000 &\n random() * 0x100000000;\n }\n bitArr2.bits.set(bitArr1.bits);\n}","tests":[{"name":"forEach no bail","code":"bitArr1.forEach((v, i) => out[i] = v);","results":{"aborted":false,"count":622,"cycles":7,"hz":7621.563223613278,"stats":{"moe":0.000004259707004825067,"rme":3.2465626251342603,"sem":0.0000021733199004209527,"deviation":0.000017250191927704506,"mean":0.00013120667908412544,"variance":2.9756912154264164e-10,"numSamples":63},"times":{"cycle":0.08161055439032602,"elapsed":6.247,"period":0.00013120667908412544,"timeStamp":1680183619390}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/111.0.0.0 Safari/537.36":{"aborted":false,"count":976,"cycles":2,"hz":9274.455002794863,"stats":{"moe":6.500327947132916e-7,"rme":0.6028699904909414,"sem":3.3164938505780187e-7,"deviation":0.0000023684503467605407,"mean":0.00010782304725168751,"variance":5.609557045070126e-12,"numSamples":51},"times":{"cycle":0.10523529411764701,"elapsed":6.179,"period":0.00010782304725168751,"timeStamp":1680183416324}},"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/111.0":{"aborted":false,"count":622,"cycles":7,"hz":7621.563223613278,"stats":{"moe":0.000004259707004825067,"rme":3.2465626251342603,"sem":0.0000021733199004209527,"deviation":0.000017250191927704506,"mean":0.00013120667908412544,"variance":2.9756912154264164e-10,"numSamples":63},"times":{"cycle":0.08161055439032602,"elapsed":6.247,"period":0.00013120667908412544,"timeStamp":1680183619390}}}},{"name":"forEach with bail","code":"bitArr2.forEach((v, i) => out[i] = v);\n","results":{"aborted":false,"count":638,"cycles":4,"hz":7996.124499217302,"stats":{"moe":0.0000016471076541054445,"rme":1.3170477865840884,"sem":8.403610480129819e-7,"deviation":0.000006722888384103855,"mean":0.00012506058404892077,"variance":4.519722822511855e-11,"numSamples":64},"times":{"cycle":0.07978865262321146,"elapsed":5.966,"period":0.00012506058404892077,"timeStamp":1680183625643}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/111.0":{"aborted":false,"count":638,"cycles":4,"hz":7996.124499217302,"stats":{"moe":0.0000016471076541054445,"rme":1.3170477865840884,"sem":8.403610480129819e-7,"deviation":0.000006722888384103855,"mean":0.00012506058404892077,"variance":4.519722822511855e-11,"numSamples":64},"times":{"cycle":0.07978865262321146,"elapsed":5.966,"period":0.00012506058404892077,"timeStamp":1680183625643}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/111.0.0.0 Safari/537.36":{"aborted":false,"count":761,"cycles":4,"hz":9943.642839604086,"stats":{"moe":4.576461008388334e-7,"rme":0.45506693736787956,"sem":2.3349290859124154e-7,"deviation":0.0000019112218265498796,"mean":0.00010056676573470088,"variance":3.652768870280658e-12,"numSamples":67},"times":{"cycle":0.07653130872410736,"elapsed":6.213,"period":0.00010056676573470088,"timeStamp":1680183422509}}}},{"name":"inlined \"simple\" for-loop","code":"const {bits, length} = bitArr1;\nfor (let i = 0; i < length; i++)\n out[i] = (bits[i >> 5] & (1 << (i & 31))) ? true : false;","results":{"aborted":false,"count":2473,"cycles":5,"hz":28654.270549731234,"stats":{"moe":9.103757191584147e-7,"rme":2.6086152158671356,"sem":4.64477407733885e-7,"deviation":0.0000035677186653961645,"mean":0.00003489881196816506,"variance":1.272861647541619e-11,"numSamples":59},"times":{"cycle":0.08630476199727219,"elapsed":6.093,"period":0.00003489881196816506,"timeStamp":1680183631614}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/111.0":{"aborted":false,"count":2473,"cycles":5,"hz":28654.270549731234,"stats":{"moe":9.103757191584147e-7,"rme":2.6086152158671356,"sem":4.64477407733885e-7,"deviation":0.0000035677186653961645,"mean":0.00003489881196816506,"variance":1.272861647541619e-11,"numSamples":59},"times":{"cycle":0.08630476199727219,"elapsed":6.093,"period":0.00003489881196816506,"timeStamp":1680183631614}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/111.0.0.0 Safari/537.36":{"aborted":false,"count":4510,"cycles":4,"hz":58022.721160617795,"stats":{"moe":1.5362207303163866e-7,"rme":0.8913570707630833,"sem":7.837860868961157e-8,"deviation":6.415565618930182e-7,"mean":0.00001723462774577242,"variance":4.1159482210799005e-13,"numSamples":67},"times":{"cycle":0.07772817113343362,"elapsed":6.288,"period":0.00001723462774577242,"timeStamp":1680183428732}}}},{"name":"in-lined for-loop avoid lookup + bail","code":"const {bits, length} = bitArr1;\nlet i = 0;\nwhile(i + 32 < length) {\n const v = bits[i >> 5];\n if (v === 0) {\n for (let j = 0; j < 32; j++) out[i++] = false;\n continue;\n } \n for (let j = 1; j; j <<= 1) {\n out[i++] = (v & j) ? true : false;\n }\n}\nlet v = bits[i >> 5];\nwhile(i < length) {\n out[i++] = (v & 1) ? true : false;\n v >>>= 1;\n}","results":{"aborted":false,"count":3086,"cycles":5,"hz":36402.54918316743,"stats":{"moe":4.523328273658949e-7,"rme":1.646606799534817,"sem":2.3078205477851782e-7,"deviation":0.0000017876301095214548,"mean":0.000027470603637351885,"variance":3.1956214084676885e-12,"numSamples":60},"times":{"cycle":0.08477428282486792,"elapsed":6.196,"period":0.000027470603637351885,"timeStamp":1680183637712}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/111.0.0.0 Safari/537.36":{"aborted":false,"count":6173,"cycles":4,"hz":79134.25473071364,"stats":{"moe":8.023722506485438e-8,"rme":0.6349513007167789,"sem":4.093735972696652e-8,"deviation":3.2749887781573216e-7,"mean":0.000012636752609889422,"variance":1.0725551497056387e-13,"numSamples":64},"times":{"cycle":0.0780066738608474,"elapsed":6.167,"period":0.000012636752609889422,"timeStamp":1680183435028}},"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/111.0":{"aborted":false,"count":3086,"cycles":5,"hz":36402.54918316743,"stats":{"moe":4.523328273658949e-7,"rme":1.646606799534817,"sem":2.3078205477851782e-7,"deviation":0.0000017876301095214548,"mean":0.000027470603637351885,"variance":3.1956214084676885e-12,"numSamples":60},"times":{"cycle":0.08477428282486792,"elapsed":6.196,"period":0.000027470603637351885,"timeStamp":1680183637712}}}}]} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment