Last active
February 26, 2024 10:13
-
-
Save JobLeonard/219dd9ed01e98533590fc8de40c886f4 to your computer and use it in GitHub Desktop.
Verifying alexharri.com/blog/bit-set-iteration benchmarks - fully set bits
This file contains hidden or 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 - fully set bits","initialization":"// Veryfying the nrs in https://alexharri.com/blog/bit-set-iteration\nconst WORD_LEN = 32;\nconst WORD_LOG = Math.log2(WORD_LEN);\n\nclass BitSetBasic {\n constructor(size) {\n this.words = [0xFFFFFFFF];\n for (let i = 0; i < size; i++) {\n this.words[i] = 0xFFFFFFFF;\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 BitSetOptimized {\n constructor(size) {\n this.words = [0xFFFFFFFF | 0];\n for (let i = 0; i < size; i++) {\n this.words[i] = 0xFFFFFFFF | 0;\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 {\n constructor(size) {\n this.words = [0xFFFFFFFF | 0];\n for (let i = 0; i < size; i++) {\n this.words[i] = 0xFFFFFFFF | 0;\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 BitSetBasic(size);\nconst optimized = new BitSetOptimized(size);\nconst clz = new BitSetCLZ(size)","setup":"","tests":[{"name":"basic.forEach(() => {})","code":"basic.forEach(() => {});","results":{"aborted":false,"count":38,"cycles":2,"hz":373.0610642057726,"stats":{"moe":0.00005989778551116289,"rme":2.2345531606363536,"sem":0.0000305600946485525,"deviation":0.0002160925015969419,"mean":0.002680526315789474,"variance":4.669596924642434e-8,"numSamples":50},"times":{"cycle":0.10186,"elapsed":5.847,"period":0.002680526315789474,"timeStamp":1708942036955}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":38,"cycles":2,"hz":373.0610642057726,"stats":{"moe":0.00005989778551116289,"rme":2.2345531606363536,"sem":0.0000305600946485525,"deviation":0.0002160925015969419,"mean":0.002680526315789474,"variance":4.669596924642434e-8,"numSamples":50},"times":{"cycle":0.10186,"elapsed":5.847,"period":0.002680526315789474,"timeStamp":1708942036955}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":36,"cycles":4,"hz":450.8680215817285,"stats":{"moe":0.000032892346123742694,"rme":1.4830107021993304,"sem":0.0000167818092468075,"deviation":0.00013425447397446,"mean":0.002217943948412697,"variance":1.8024263782158953e-8,"numSamples":64},"times":{"cycle":0.07984598214285708,"elapsed":5.989,"period":0.002217943948412697,"timeStamp":1708941930255}}}},{"name":"optimized.forEach(() => {})","code":"optimized.forEach(() => {});","results":{"aborted":false,"count":20,"cycles":3,"hz":127.43926722421344,"stats":{"moe":0.0020606277326877293,"rme":26.260488827561655,"sem":0.001051340679942719,"deviation":0.0059472809929981794,"mean":0.007846875000000001,"variance":0.00003537015120967741,"numSamples":32},"times":{"cycle":0.15693750000000004,"elapsed":5.71,"period":0.007846875000000001,"timeStamp":1708942042807}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":20,"cycles":3,"hz":127.43926722421344,"stats":{"moe":0.0020606277326877293,"rme":26.260488827561655,"sem":0.001051340679942719,"deviation":0.0059472809929981794,"mean":0.007846875000000001,"variance":0.00003537015120967741,"numSamples":32},"times":{"cycle":0.15693750000000004,"elapsed":5.71,"period":0.007846875000000001,"timeStamp":1708942042807}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":32,"cycles":6,"hz":407.52351097178683,"stats":{"moe":0.000034920653633679345,"rme":1.4230987374226693,"sem":0.00001781666001718334,"deviation":0.00014364250527233735,"mean":0.0024538461538461537,"variance":2.063316932091346e-8,"numSamples":65},"times":{"cycle":0.07852307692307692,"elapsed":6.06,"period":0.0024538461538461537,"timeStamp":1708941936250}}}},{"name":"clz.forEach(() => {})","code":"clz.forEach(() => {});","results":{"aborted":false,"count":54,"cycles":4,"hz":453.141843148311,"stats":{"moe":0.00006118385127271282,"rme":2.7724963136629217,"sem":0.000031216250649343275,"deviation":0.00020706518153111952,"mean":0.002206814522031913,"variance":4.2875989402515476e-8,"numSamples":44},"times":{"cycle":0.1191679841897233,"elapsed":6.074,"period":0.002206814522031913,"timeStamp":1708942048529}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":54,"cycles":4,"hz":453.141843148311,"stats":{"moe":0.00006118385127271282,"rme":2.7724963136629217,"sem":0.000031216250649343275,"deviation":0.00020706518153111952,"mean":0.002206814522031913,"variance":4.2875989402515476e-8,"numSamples":44},"times":{"cycle":0.1191679841897233,"elapsed":6.074,"period":0.002206814522031913,"timeStamp":1708942048529}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":36,"cycles":3,"hz":462.5267665952893,"stats":{"moe":0.000017489341969785407,"rme":0.8089288791164132,"sem":0.000008923133658053779,"deviation":0.00007249188052772867,"mean":0.002162037037037036,"variance":5.255072742446487e-9,"numSamples":66},"times":{"cycle":0.0778333333333333,"elapsed":5.896,"period":0.002162037037037036,"timeStamp":1708941942315}}}},{"name":"basic.forEach(value => sum += value)","code":"let sum = 0;\nbasic.forEach(value => sum += value);","results":{"aborted":false,"count":21,"cycles":3,"hz":251.234373891091,"stats":{"moe":0.00006684188559134327,"rme":1.6792979276241065,"sem":0.000034103002852726155,"deviation":0.00026195013535176853,"mean":0.003980347054075871,"variance":6.861787341080984e-8,"numSamples":59},"times":{"cycle":0.0835872881355933,"elapsed":5.882,"period":0.003980347054075871,"timeStamp":1708942054608}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":21,"cycles":3,"hz":257.78837191931825,"stats":{"moe":0.000042172694010271366,"rme":1.0871630128359442,"sem":0.00002151668061748539,"deviation":0.00017078335786041012,"mean":0.003879150919627114,"variance":2.916695532207691e-8,"numSamples":63},"times":{"cycle":0.0814621693121694,"elapsed":5.934,"period":0.003879150919627114,"timeStamp":1708941948216}},"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":21,"cycles":3,"hz":251.234373891091,"stats":{"moe":0.00006684188559134327,"rme":1.6792979276241065,"sem":0.000034103002852726155,"deviation":0.00026195013535176853,"mean":0.003980347054075871,"variance":6.861787341080984e-8,"numSamples":59},"times":{"cycle":0.0835872881355933,"elapsed":5.882,"period":0.003980347054075871,"timeStamp":1708942054608}}}},{"name":"optimized.forEach(value => sum += value)","code":"let sum = 0;\noptimized.forEach(value => sum += value);","results":{"aborted":false,"count":15,"cycles":4,"hz":103.74288039056144,"stats":{"moe":0.002147831482326787,"rme":22.28222245701101,"sem":0.0010958323889422382,"deviation":0.006389745944735597,"mean":0.009639215686274509,"variance":0.000040828853238265,"numSamples":34},"times":{"cycle":0.14458823529411763,"elapsed":5.793,"period":0.009639215686274509,"timeStamp":1708942060495}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":20,"cycles":2,"hz":250.4677666269775,"stats":{"moe":0.00003194046361003021,"rme":0.8000056585434514,"sem":0.000016296154903076637,"deviation":0.00012831605202294163,"mean":0.00399252971137521,"variance":1.6465009206754266e-8,"numSamples":62},"times":{"cycle":0.0798505942275042,"elapsed":5.738,"period":0.00399252971137521,"timeStamp":1708941954155}},"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":15,"cycles":4,"hz":103.74288039056144,"stats":{"moe":0.002147831482326787,"rme":22.28222245701101,"sem":0.0010958323889422382,"deviation":0.006389745944735597,"mean":0.009639215686274509,"variance":0.000040828853238265,"numSamples":34},"times":{"cycle":0.14458823529411763,"elapsed":5.793,"period":0.009639215686274509,"timeStamp":1708942060495}}}},{"name":"clz.forEach(value => sum += value)","code":"let sum = 0;\nclz.forEach(value => sum += value);","results":{"aborted":false,"count":29,"cycles":5,"hz":341.39791579741876,"stats":{"moe":0.000059652586037590415,"rme":2.036526854515957,"sem":0.00003043499287632164,"deviation":0.00023574844110387018,"mean":0.002929133289124669,"variance":5.557732748290495e-8,"numSamples":60},"times":{"cycle":0.0849448653846154,"elapsed":6.079,"period":0.002929133289124669,"timeStamp":1708942066293}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/122.0.0.0 Safari/537.36":{"aborted":false,"count":25,"cycles":3,"hz":323.0013070635643,"stats":{"moe":0.00002364797638278429,"rme":0.7638327281047625,"sem":0.000012065294072849128,"deviation":0.00009727351062432844,"mean":0.0030959627039627035,"variance":9.462135869181337e-9,"numSamples":65},"times":{"cycle":0.07739906759906759,"elapsed":5.935,"period":0.0030959627039627035,"timeStamp":1708941959899}},"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":29,"cycles":5,"hz":341.39791579741876,"stats":{"moe":0.000059652586037590415,"rme":2.036526854515957,"sem":0.00003043499287632164,"deviation":0.00023574844110387018,"mean":0.002929133289124669,"variance":5.557732748290495e-8,"numSamples":60},"times":{"cycle":0.0849448653846154,"elapsed":6.079,"period":0.002929133289124669,"timeStamp":1708942066293}}}}]} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment