Verifying alexharri.com/blog/bit-set-iteration benchmarks - fully set bits, TypedArray

README.md

Verifying alexharri.com/blog/bit-set-iteration benchmarks - fully set bits, TypedArray

view on jsbenchit

jsBenchIt.json

{"title":"Verifying alexharri.com/blog/bit-set-iteration benchmarks - fully 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\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] = 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 BitSetOptimizedTA {\n  constructor(size) {\n    this.words = new Uint32Array(size);\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_TA {\n  constructor(size) {\n    this.words = new Uint32Array(size);\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 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":36,"cycles":4,"hz":454.6337672430545,"stats":{"moe":0.000027660848240524857,"rme":1.257555564072823,"sem":0.000014112677673737172,"deviation":0.00011378004492432745,"mean":0.002199572649572648,"variance":1.2945898622981972e-8,"numSamples":65},"times":{"cycle":0.07918461538461534,"elapsed":5.959,"period":0.002199572649572648,"timeStamp":1708942782522}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":38,"cycles":2,"hz":326.0247855100095,"stats":{"moe":0.00012348687590857003,"rme":4.025978223139271,"sem":0.00006300350811661736,"deviation":0.0004226403809091485,"mean":0.0030672514619883044,"variance":1.7862489157503016e-7,"numSamples":45},"times":{"cycle":0.11655555555555557,"elapsed":5.849,"period":0.0030672514619883044,"timeStamp":1708942696035}},"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":454.6337672430545,"stats":{"moe":0.000027660848240524857,"rme":1.257555564072823,"sem":0.000014112677673737172,"deviation":0.00011378004492432745,"mean":0.002199572649572648,"variance":1.2945898622981972e-8,"numSamples":65},"times":{"cycle":0.07918461538461534,"elapsed":5.959,"period":0.002199572649572648,"timeStamp":1708942782522}}}},{"name":"optimized.forEach(() => {})","code":"optimized.forEach(() => {});","results":{"aborted":false,"count":32,"cycles":7,"hz":411.3195812169586,"stats":{"moe":0.000013051828786537308,"rme":0.5368472750593971,"sem":0.000006659096319661892,"deviation":0.00005327277055729514,"mean":0.0024311995967741936,"variance":2.8379880828502114e-9,"numSamples":64},"times":{"cycle":0.0777983870967742,"elapsed":6.062,"period":0.0024311995967741936,"timeStamp":1708942788486}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":21,"cycles":3,"hz":223.8452427951046,"stats":{"moe":0.0005019371286110428,"rme":11.235623842181653,"sem":0.00025609037174032797,"deviation":0.0018818722164103934,"mean":0.004467372134038801,"variance":0.0000035414430388973663,"numSamples":54},"times":{"cycle":0.09381481481481481,"elapsed":5.817,"period":0.004467372134038801,"timeStamp":1708942701890}},"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":7,"hz":411.3195812169586,"stats":{"moe":0.000013051828786537308,"rme":0.5368472750593971,"sem":0.000006659096319661892,"deviation":0.00005327277055729514,"mean":0.0024311995967741936,"variance":2.8379880828502114e-9,"numSamples":64},"times":{"cycle":0.0777983870967742,"elapsed":6.062,"period":0.0024311995967741936,"timeStamp":1708942788486}}}},{"name":"clz.forEach(() => {})","code":"clz.forEach(() => {});","results":{"aborted":false,"count":36,"cycles":3,"hz":454.20514100324453,"stats":{"moe":0.000026877481809443708,"rme":1.220789041507052,"sem":0.000013713000923185565,"deviation":0.00011055774794537799,"mean":0.0022016483516483507,"variance":1.222301563075373e-8,"numSamples":65},"times":{"cycle":0.07925934065934062,"elapsed":5.917,"period":0.0022016483516483507,"timeStamp":1708942794554}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":30,"cycles":2,"hz":360.69945925666144,"stats":{"moe":0.00005020108285392082,"rme":1.8107503439508097,"sem":0.0000256127973744494,"deviation":0.00020004234239285625,"mean":0.002772391181458451,"variance":4.0016938750020736e-8,"numSamples":61},"times":{"cycle":0.08317173544375353,"elapsed":5.796,"period":0.002772391181458451,"timeStamp":1708942707713}},"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":454.20514100324453,"stats":{"moe":0.000026877481809443708,"rme":1.220789041507052,"sem":0.000013713000923185565,"deviation":0.00011055774794537799,"mean":0.0022016483516483507,"variance":1.222301563075373e-8,"numSamples":65},"times":{"cycle":0.07925934065934062,"elapsed":5.917,"period":0.0022016483516483507,"timeStamp":1708942794554}}}},{"name":"basic.forEach(value => sum += value)","code":"let sum = 0;\nbasic.forEach(value => sum += value);","results":{"aborted":false,"count":21,"cycles":3,"hz":268.53941891528063,"stats":{"moe":0.000033860679513724624,"rme":0.9092927200692158,"sem":0.00001727585689475746,"deviation":0.00013928241110825525,"mean":0.0037238480817428222,"variance":1.9399590044129024e-8,"numSamples":65},"times":{"cycle":0.07820080971659926,"elapsed":5.942,"period":0.0037238480817428222,"timeStamp":1708942800477}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":25,"cycles":2,"hz":251.88916876574305,"stats":{"moe":0.00007265781450779931,"rme":1.8301716500705112,"sem":0.0000370703135243874,"deviation":0.0002673178324194099,"mean":0.0039700000000000004,"variance":7.145882352941174e-8,"numSamples":52},"times":{"cycle":0.09925,"elapsed":5.803,"period":0.0039700000000000004,"timeStamp":1708942713515}},"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":268.53941891528063,"stats":{"moe":0.000033860679513724624,"rme":0.9092927200692158,"sem":0.00001727585689475746,"deviation":0.00013928241110825525,"mean":0.0037238480817428222,"variance":1.9399590044129024e-8,"numSamples":65},"times":{"cycle":0.07820080971659926,"elapsed":5.942,"period":0.0037238480817428222,"timeStamp":1708942800477}}}},{"name":"optimized.forEach(value => sum += value)","code":"let sum = 0;\noptimized.forEach(value => sum += value);","results":{"aborted":false,"count":20,"cycles":2,"hz":253.84631442707152,"stats":{"moe":0.000041280578862024515,"rme":1.0478922801540997,"sem":0.00002106151982756353,"deviation":0.00016849215862050823,"mean":0.003939391447368419,"variance":2.8389607516598504e-8,"numSamples":64},"times":{"cycle":0.07878782894736838,"elapsed":5.84,"period":0.003939391447368419,"timeStamp":1708942806424}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":16,"cycles":3,"hz":107.05711024520801,"stats":{"moe":0.00214503422498802,"rme":22.964116550428677,"sem":0.0010944052168306226,"deviation":0.0063814241728071,"mean":0.009340808823529412,"variance":0.000040722574473286785,"numSamples":34},"times":{"cycle":0.1494529411764706,"elapsed":5.783,"period":0.009340808823529412,"timeStamp":1708942719324}},"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":253.84631442707152,"stats":{"moe":0.000041280578862024515,"rme":1.0478922801540997,"sem":0.00002106151982756353,"deviation":0.00016849215862050823,"mean":0.003939391447368419,"variance":2.8389607516598504e-8,"numSamples":64},"times":{"cycle":0.07878782894736838,"elapsed":5.84,"period":0.003939391447368419,"timeStamp":1708942806424}}}},{"name":"clz.forEach(value => sum += value)","code":"let sum = 0;\nclz.forEach(value => sum += value);","results":{"aborted":false,"count":25,"cycles":2,"hz":320.765890248717,"stats":{"moe":0.00003093672932457108,"rme":0.9923447523179634,"sem":0.00001578404557376076,"deviation":0.0001272550437265501,"mean":0.0031175384615384607,"variance":1.6193846153846177e-8,"numSamples":65},"times":{"cycle":0.07793846153846151,"elapsed":5.74,"period":0.0031175384615384607,"timeStamp":1708942812270}},"platforms":{"Mozilla/5.0 (X11; Linux x86_64; rv:123.0) Gecko/20100101 Firefox/123.0":{"aborted":false,"count":26,"cycles":2,"hz":302.55455449137696,"stats":{"moe":0.00007728273656324832,"rme":2.3382243930768047,"sem":0.00003942996763431037,"deviation":0.0003028673282328799,"mean":0.003305189048239896,"variance":9.1728618510923e-8,"numSamples":59},"times":{"cycle":0.0859349152542373,"elapsed":5.797,"period":0.003305189048239896,"timeStamp":1708942725113}},"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":2,"hz":320.765890248717,"stats":{"moe":0.00003093672932457108,"rme":0.9923447523179634,"sem":0.00001578404557376076,"deviation":0.0001272550437265501,"mean":0.0031175384615384607,"variance":1.6193846153846177e-8,"numSamples":65},"times":{"cycle":0.07793846153846151,"elapsed":5.74,"period":0.0031175384615384607,"timeStamp":1708942812270}}}}]}