Skip to content

Instantly share code, notes, and snippets.

@JobLeonard

JobLeonard/README.md

Last active February 26, 2024 10:47
Show Gist options
  • Save JobLeonard/4982f7e3557153267e23b4a88732d6a4 to your computer and use it in GitHub Desktop.
Save JobLeonard/4982f7e3557153267e23b4a88732d6a4 to your computer and use it in GitHub Desktop.
Download ZIP
Verifying alexharri.com/blog/bit-set-iteration benchmarks - 1.6% randomly set bits, TypedArray
Raw
README.md

Verifying alexharri.com/blog/bit-set-iteration benchmarks - 1.6% randomly set bits, TypedArray

view on jsbenchit

Raw
jsBenchIt.json
{"title":"Verifying alexharri.com/blog/bit-set-iteration benchmarks - 1.6% 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 = () => (1 << (Math.random() * 32)) >>> 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 += 2) {\n this.words[i + (Math.random()*2|0)] = 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 += 2) {\n this.words[i + (Math.random()*2|0)] = 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 += 2) {\n this.words[i + (Math.random()*2|0)] = 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":188,"cycles":5,"hz":2378.0988113187714,"stats":{"moe":0.0000035029299705860515,"rme":0.8330313599183587,"sem":0.0000017872091686663528,"deviation":0.000014408940967910512,"mean":0.0004205039736954628,"variance":2.076175798167299e-10,"numSamples":65},"times":{"cycle":0.07905474705474701,"elapsed":5.983,"period":0.0004205039736954628,"timeStamp":1708944382984}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":75,"cycles":2,"hz":849.9005964214709,"stats":{"moe":0.00002960554778001945,"rme":2.5161772715622885,"sem":0.000015104871316336454,"deviation":0.00011403927760441038,"mean":0.0011766081871345032,"variance":1.3004956836535774e-8,"numSamples":57},"times":{"cycle":0.08824561403508774,"elapsed":5.792,"period":0.0011766081871345032,"timeStamp":1708944325348}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":188,"cycles":5,"hz":2378.0988113187714,"stats":{"moe":0.0000035029299705860515,"rme":0.8330313599183587,"sem":0.0000017872091686663528,"deviation":0.000014408940967910512,"mean":0.0004205039736954628,"variance":2.076175798167299e-10,"numSamples":65},"times":{"cycle":0.07905474705474701,"elapsed":5.983,"period":0.0004205039736954628,"timeStamp":1708944382984}}}},{"name":"optimized.forEach(() => {})","code":"optimized.forEach(() => {});","results":{"aborted":false,"count":867,"cycles":5,"hz":11006.994605995198,"stats":{"moe":0.0000012426662456383124,"rme":1.3678020662793209,"sem":6.340133906317921e-7,"deviation":0.000005150749134546141,"mean":0.00009085132098232594,"variance":2.6530216647027816e-11,"numSamples":66},"times":{"cycle":0.07876809529167658,"elapsed":6.014,"period":0.00009085132098232594,"timeStamp":1708944388973}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":587,"cycles":4,"hz":4918.795376359481,"stats":{"moe":0.0000291616039468991,"rme":14.343996266123371,"sem":0.000014878369360662807,"deviation":0.00009642285384159199,"mean":0.00020330180938328115,"variance":9.29736674295701e-9,"numSamples":42},"times":{"cycle":0.11933816210798603,"elapsed":5.81,"period":0.00020330180938328115,"timeStamp":1708944331146}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":867,"cycles":5,"hz":11006.994605995198,"stats":{"moe":0.0000012426662456383124,"rme":1.3678020662793209,"sem":6.340133906317921e-7,"deviation":0.000005150749134546141,"mean":0.00009085132098232594,"variance":2.6530216647027816e-11,"numSamples":66},"times":{"cycle":0.07876809529167658,"elapsed":6.014,"period":0.00009085132098232594,"timeStamp":1708944388973}}}},{"name":"clz.forEach(() => {})","code":"clz.forEach(() => {});","results":{"aborted":false,"count":911,"cycles":4,"hz":11700.059668088279,"stats":{"moe":7.353262585887763e-7,"rme":0.8603361101000795,"sem":3.751664584636614e-7,"deviation":0.0000030708698106991013,"mean":0.00008546964958883787,"variance":9.430241394263135e-12,"numSamples":67},"times":{"cycle":0.0778628507754313,"elapsed":5.99,"period":0.00008546964958883787,"timeStamp":1708944394992}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":976,"cycles":2,"hz":7973.264017823986,"stats":{"moe":0.0000032114944819139247,"rme":2.560609339608458,"sem":0.000001638517592813227,"deviation":0.000010868696135515606,"mean":0.00012541915052160957,"variance":1.1812855568617187e-10,"numSamples":44},"times":{"cycle":0.12240909090909094,"elapsed":5.888,"period":0.00012541915052160957,"timeStamp":1708944336961}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":911,"cycles":4,"hz":11700.059668088279,"stats":{"moe":7.353262585887763e-7,"rme":0.8603361101000795,"sem":3.751664584636614e-7,"deviation":0.0000030708698106991013,"mean":0.00008546964958883787,"variance":9.430241394263135e-12,"numSamples":67},"times":{"cycle":0.0778628507754313,"elapsed":5.99,"period":0.00008546964958883787,"timeStamp":1708944394992}}}},{"name":"basic.forEach(value => sum += value)","code":"let sum = 0;\nbasic.forEach(value => sum += value);","results":{"aborted":false,"count":976,"cycles":2,"hz":2331.442221558674,"stats":{"moe":0.000004644007689942576,"rme":1.0827235605575285,"sem":0.0000021792621726619317,"deviation":0.000008717048690647727,"mean":0.0004289190573770492,"variance":7.598693787512325e-11,"numSamples":16},"times":{"cycle":0.41862499999999997,"elapsed":6.829,"period":0.0004289190573770492,"timeStamp":1708944400987}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":75,"cycles":2,"hz":872.2649319929036,"stats":{"moe":0.000008581397393583619,"rme":0.7485252013918295,"sem":0.000004378263976318173,"deviation":0.00003363008372474264,"mean":0.0011464406779661018,"variance":1.1309825313332e-9,"numSamples":59},"times":{"cycle":0.08598305084745764,"elapsed":5.779,"period":0.0011464406779661018,"timeStamp":1708944342854}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":976,"cycles":2,"hz":2331.442221558674,"stats":{"moe":0.000004644007689942576,"rme":1.0827235605575285,"sem":0.0000021792621726619317,"deviation":0.000008717048690647727,"mean":0.0004289190573770492,"variance":7.598693787512325e-11,"numSamples":16},"times":{"cycle":0.41862499999999997,"elapsed":6.829,"period":0.0004289190573770492,"timeStamp":1708944400987}}}},{"name":"optimized.forEach(value => sum += value)","code":"let sum = 0;\noptimized.forEach(value => sum += value);","results":{"aborted":false,"count":755,"cycles":3,"hz":9784.525879534907,"stats":{"moe":5.500488163069289e-7,"rme":0.5381966878162687,"sem":2.8063715117700457e-7,"deviation":0.0000022799069939296134,"mean":0.00010220219275944452,"variance":5.1979759009691666e-12,"numSamples":66},"times":{"cycle":0.07716265553338061,"elapsed":5.817,"period":0.00010220219275944452,"timeStamp":1708944407821}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":976,"cycles":2,"hz":4754.104275662998,"stats":{"moe":0.000037169926017430856,"rme":17.670970420554532,"sem":0.00001807875779057921,"deviation":0.00009393998109304456,"mean":0.0002103445658773528,"variance":8.824720047761569e-9,"numSamples":27},"times":{"cycle":0.20529629629629634,"elapsed":5.835,"period":0.0002103445658773528,"timeStamp":1708944348638}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":755,"cycles":3,"hz":9784.525879534907,"stats":{"moe":5.500488163069289e-7,"rme":0.5381966878162687,"sem":2.8063715117700457e-7,"deviation":0.0000022799069939296134,"mean":0.00010220219275944452,"variance":5.1979759009691666e-12,"numSamples":66},"times":{"cycle":0.07716265553338061,"elapsed":5.817,"period":0.00010220219275944452,"timeStamp":1708944407821}}}},{"name":"clz.forEach(value => sum += value)","code":"let sum = 0;\nclz.forEach(value => sum += value);","results":{"aborted":false,"count":976,"cycles":2,"hz":10052.434456928842,"stats":{"moe":8.178076839933269e-7,"rme":0.8220958141715693,"sem":4.172488183639423e-7,"deviation":0.000003094400055493122,"mean":0.00009947839046199699,"variance":9.575311703435837e-12,"numSamples":55},"times":{"cycle":0.09709090909090906,"elapsed":5.745,"period":0.00009947839046199699,"timeStamp":1708944413643}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":976,"cycles":2,"hz":7841.554559043348,"stats":{"moe":0.0000014508870304840426,"rme":1.137720980854901,"sem":7.402484849408381e-7,"deviation":0.000004854133932707241,"mean":0.00012752573389248953,"variance":2.356261623665986e-11,"numSamples":43},"times":{"cycle":0.12446511627906978,"elapsed":5.811,"period":0.00012752573389248953,"timeStamp":1708944354479}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":976,"cycles":2,"hz":10052.434456928842,"stats":{"moe":8.178076839933269e-7,"rme":0.8220958141715693,"sem":4.172488183639423e-7,"deviation":0.000003094400055493122,"mean":0.00009947839046199699,"variance":9.575311703435837e-12,"numSamples":55},"times":{"cycle":0.09709090909090906,"elapsed":5.745,"period":0.00009947839046199699,"timeStamp":1708944413643}}}}]}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment