Last active
February 26, 2024 10:36
-
-
Save JobLeonard/2dc59964ac15bbc22d58f1f9ee0a6d3e to your computer and use it in GitHub Desktop.
Verifying alexharri.com/blog/bit-set-iteration benchmarks - 50% randomly set bits, TypedArray
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":"Verifying alexharri.com/blog/bit-set-iteration benchmarks - 50% randomly set bits, TypedArray","initialization":"// Veryfying the nrs in https://alexharri.com/blog/bit-set-iteration\nconst WORD_LEN = 32;\nconst WORD_LOG = Math.log2(WORD_LEN);\n\nconst randomInit = () => (Math.random() * 0x100000000) >>> 0;\n\n// Typed Array Versions\nclass BitSetBasicTA {\n constructor(size) {\n this.words = new Uint32Array(size);\n for (let i = 0; i < size; i++) {\n this.words[i] = randomInit();\n }\n }\n \n forEach(callback) {\n const words = this.words;\n\n for (let wordIndex = 0; wordIndex < words.length; wordIndex++) {\n const word = words[wordIndex];\n\n for (let i = 0; i < WORD_LEN; i++) {\n const bitIsSetToOne = (word & (1 << i)) !== 0;\n if (bitIsSetToOne) {\n const index = (wordIndex << WORD_LOG) + i;\n callback(index);\n }\n }\n }\n }\n}\n\n// Returns the number of non-zero bits in `n`\nfunction hammingWeight(n) {\n n -= (n >> 1) & 0x55555555;\n n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);\n return (((n + (n >>> 4)) & 0xf0f0f0f) * 0x1010101) >> 24;\n}\n\nclass BitSetOptimizedTA {\n constructor(size) {\n this.words = new Uint32Array(size);\n for (let i = 0; i < size; i++) {\n this.words[i] = randomInit();\n }\n }\n \n forEach(callback) {\n const words = this.words;\n for (let wordIndex = 0; wordIndex < words.length; wordIndex++) {\n let word = words[wordIndex];\n while (word !== 0) {\n const lsb = word & -word;\n const index = (wordIndex << WORD_LOG) + hammingWeight(lsb - 1);\n callback(index);\n word ^= lsb;\n }\n }\n }\n}\n\n\nclass BitSetCLZ_TA {\n constructor(size) {\n this.words = new Uint32Array(size);\n for (let i = 0; i < size; i++) {\n this.words[i] = randomInit();\n }\n }\n \n forEach(callback) {\n const words = this.words;\n const clz32 = Math.clz32;\n for (let wordIndex = 0; wordIndex < words.length; wordIndex++) {\n let word = words[wordIndex];\n while (word !== 0) {\n const index = 31 - clz32(word);\n callback(index);\n word ^= (1 << index);\n }\n }\n }\n}\n\nconst size = 10000;\nconst basic = new BitSetBasicTA(size);\nconst optimized = new BitSetOptimizedTA(size);\nconst clz = new BitSetCLZ_TA(size);","setup":"// runs before each test","tests":[{"name":"basic.forEach(() => {})","code":"basic.forEach(() => {});","results":{"aborted":false,"count":24,"cycles":3,"hz":285.5443188578229,"stats":{"moe":0.00005192066575088443,"rme":1.4825651136480988,"sem":0.000026490135587185934,"deviation":0.00020519170793589512,"mean":0.0035020833333333314,"variance":4.210363700564968e-8,"numSamples":60},"times":{"cycle":0.08404999999999996,"elapsed":5.83,"period":0.0035020833333333314,"timeStamp":1708943728149}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":24,"cycles":3,"hz":285.5443188578229,"stats":{"moe":0.00005192066575088443,"rme":1.4825651136480988,"sem":0.000026490135587185934,"deviation":0.00020519170793589512,"mean":0.0035020833333333314,"variance":4.210363700564968e-8,"numSamples":60},"times":{"cycle":0.08404999999999996,"elapsed":5.83,"period":0.0035020833333333314,"timeStamp":1708943728149}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":31,"cycles":6,"hz":382.0422535211269,"stats":{"moe":0.00004753348888300481,"rme":1.8159801210584592,"sem":0.000024251780042349393,"deviation":0.00019249253652808793,"mean":0.0026175115207373264,"variance":3.7053376619017265e-8,"numSamples":63},"times":{"cycle":0.08114285714285711,"elapsed":6.089,"period":0.0026175115207373264,"timeStamp":1708943581208}}}},{"name":"optimized.forEach(() => {})","code":"optimized.forEach(() => {});","results":{"aborted":false,"count":39,"cycles":3,"hz":412.64233079828136,"stats":{"moe":0.00030994663125619534,"rme":12.789710034463189,"sem":0.00015813603635520172,"deviation":0.0011727682335727517,"mean":0.00242340624158806,"variance":0.0000013753853296773524,"numSamples":55},"times":{"cycle":0.09451284342193433,"elapsed":5.973,"period":0.00242340624158806,"timeStamp":1708943733984}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":39,"cycles":3,"hz":412.64233079828136,"stats":{"moe":0.00030994663125619534,"rme":12.789710034463189,"sem":0.00015813603635520172,"deviation":0.0011727682335727517,"mean":0.00242340624158806,"variance":0.0000013753853296773524,"numSamples":55},"times":{"cycle":0.09451284342193433,"elapsed":5.973,"period":0.00242340624158806,"timeStamp":1708943733984}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":60,"cycles":3,"hz":754.4110248103058,"stats":{"moe":0.00001654669655897385,"rme":1.2483010308280622,"sem":0.000008442192121925434,"deviation":0.00006753753697540347,"mean":0.001325537362409897,"variance":4.561318900703991e-9,"numSamples":64},"times":{"cycle":0.07953224174459382,"elapsed":5.896,"period":0.001325537362409897,"timeStamp":1708943587302}}}},{"name":"clz.forEach(() => {})","code":"clz.forEach(() => {});","results":{"aborted":false,"count":54,"cycles":4,"hz":666.4542560725529,"stats":{"moe":0.00002367566264368413,"rme":1.5778746134221238,"sem":0.000012079419716165371,"deviation":0.000095877421652832,"mean":0.0015004780761594175,"variance":9.192479982794939e-9,"numSamples":63},"times":{"cycle":0.08102581611260855,"elapsed":6.009,"period":0.0015004780761594175,"timeStamp":1708943739962}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":54,"cycles":4,"hz":666.4542560725529,"stats":{"moe":0.00002367566264368413,"rme":1.5778746134221238,"sem":0.000012079419716165371,"deviation":0.000095877421652832,"mean":0.0015004780761594175,"variance":9.192479982794939e-9,"numSamples":63},"times":{"cycle":0.08102581611260855,"elapsed":6.009,"period":0.0015004780761594175,"timeStamp":1708943739962}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":68,"cycles":3,"hz":864.8929116898962,"stats":{"moe":0.000008941861722189791,"rme":0.7733752820833159,"sem":0.000004562174348056016,"deviation":0.0000370632796122521,"mean":0.001156212505021137,"variance":1.373686695615982e-9,"numSamples":66},"times":{"cycle":0.07862245034143732,"elapsed":5.876,"period":0.001156212505021137,"timeStamp":1708943593204}}}},{"name":"basic.forEach(value => sum += value)","code":"let sum = 0;\nbasic.forEach(value => sum += value);","results":{"aborted":false,"count":21,"cycles":3,"hz":248.56973762083237,"stats":{"moe":0.000028796476848510368,"rme":0.7157932694638597,"sem":0.000014692080024750187,"deviation":0.00011380436251400826,"mean":0.004023015873015875,"variance":1.2951432927219808e-8,"numSamples":60},"times":{"cycle":0.08448333333333338,"elapsed":5.868,"period":0.004023015873015875,"timeStamp":1708943745977}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":21,"cycles":3,"hz":248.56973762083237,"stats":{"moe":0.000028796476848510368,"rme":0.7157932694638597,"sem":0.000014692080024750187,"deviation":0.00011380436251400826,"mean":0.004023015873015875,"variance":1.2951432927219808e-8,"numSamples":60},"times":{"cycle":0.08448333333333338,"elapsed":5.868,"period":0.004023015873015875,"timeStamp":1708943745977}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":24,"cycles":3,"hz":303.3801697658759,"stats":{"moe":0.00005147639611941165,"rme":1.5616917793642584,"sem":0.000026263467407863088,"deviation":0.00020845980998236775,"mean":0.0032961943451073894,"variance":4.345549237788487e-8,"numSamples":63},"times":{"cycle":0.07910866428257735,"elapsed":5.881,"period":0.0032961943451073894,"timeStamp":1708943599085}}}},{"name":"optimized.forEach(value => sum += value)","code":"let sum = 0;\noptimized.forEach(value => sum += value);","results":{"aborted":false,"count":30,"cycles":3,"hz":194.7308132875143,"stats":{"moe":0.0011757215698417315,"rme":22.894921749495346,"sem":0.0005998579437968019,"deviation":0.0034977428140199676,"mean":0.005135294117647059,"variance":0.000012234204793028322,"numSamples":34},"times":{"cycle":0.15405882352941178,"elapsed":5.736,"period":0.005135294117647059,"timeStamp":1708943751850}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":30,"cycles":3,"hz":194.7308132875143,"stats":{"moe":0.0011757215698417315,"rme":22.894921749495346,"sem":0.0005998579437968019,"deviation":0.0034977428140199676,"mean":0.005135294117647059,"variance":0.000012234204793028322,"numSamples":34},"times":{"cycle":0.15405882352941178,"elapsed":5.736,"period":0.005135294117647059,"timeStamp":1708943751850}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":38,"cycles":3,"hz":469.63175729248337,"stats":{"moe":0.00005320722551577536,"rme":2.498780281963104,"sem":0.000027146543630497634,"deviation":0.00021546901020378368,"mean":0.0021293278924857865,"variance":4.642689435819823e-8,"numSamples":63},"times":{"cycle":0.08091445991445989,"elapsed":5.876,"period":0.0021293278924857865,"timeStamp":1708943604971}}}},{"name":"clz.forEach(value => sum += value)","code":"let sum = 0;\nclz.forEach(value => sum += value);","results":{"aborted":false,"count":75,"cycles":2,"hz":579.7901711761457,"stats":{"moe":0.000037351161055032655,"rme":2.165583606172517,"sem":0.00001905671482399625,"deviation":0.0001235016273378249,"mean":0.0017247619047619052,"variance":1.525265195509098e-8,"numSamples":42},"times":{"cycle":0.1293571428571429,"elapsed":5.834,"period":0.0017247619047619052,"timeStamp":1708943757591}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":75,"cycles":2,"hz":579.7901711761457,"stats":{"moe":0.000037351161055032655,"rme":2.165583606172517,"sem":0.00001905671482399625,"deviation":0.0001235016273378249,"mean":0.0017247619047619052,"variance":1.525265195509098e-8,"numSamples":42},"times":{"cycle":0.1293571428571429,"elapsed":5.834,"period":0.0017247619047619052,"timeStamp":1708943757591}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":48,"cycles":3,"hz":605.215163791783,"stats":{"moe":0.00003590638320703591,"rme":2.1731087593816767,"sem":0.000018319583268895874,"deviation":0.00014769720215525623,"mean":0.0016523049319101958,"variance":2.1814463524490627e-8,"numSamples":65},"times":{"cycle":0.0793106367316894,"elapsed":5.945,"period":0.0016523049319101958,"timeStamp":1708943610852}}}}]} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment