popcount in javascript

README.md

popcount in javascript

view on jsbenchit

jsBenchIt.json

{"title":"popcount in javascript","initialization":"// Various popcount implementations taken from:\n// https://stackoverflow.com/questions/43122082/efficiently-count-the-number-of-bits-in-an-integer-in-javascript\n// ... with some modifications.\n\nconst bits32 = new Uint32Array(10000);\nconst bits64 = new Float64Array(10000);\n\nconst {random} = Math;\nfor (let i = 0; i < bits32.length; i++) {\n  bits32[i] = random()*0x100000000 | 0;\n}\nfor (let i = 0; i < bits64.length; i++) {\n  bits64[i] = (random()*0x100000000 | 0) + (random()*0x100000 | 0) * 0x100000000;\n}\n\n\nfunction bitCountBitTwiddling32 (n) {\n  n = n - ((n >> 1) & 0x55555555);\n  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);\n  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;\n}\n\nfunction count1sb32(i) {\n  i = i - ((i >> 1) & 0x55555555);\n  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);\n  i = (i + (i >> 4)) & 0x0f0f0f0f;\n  i = i + (i >> 8);\n  i = i + (i >> 16);\n  return i & 0x3f;\n}\n\n// https://nimrod.blog/posts/algorithms-behind-popcount/\nfunction popcount2(n) {\n    n = (n & 0x55555555) + ((n >> 1) & 0x55555555); // (1) add 2 bits\n    n = (n & 0x33333333) + ((n >> 2) & 0x33333333); // (2) add 4 bits\n    n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F); // (3)\n    n = (n & 0x00FF00FF) + ((n >> 8) & 0x00FF00FF); // (4)\n    n = (n & 0x0000FFFF) + ((n >> 16) & 0x0000FFFF); // (5)\n    return n;\n}\n\nfunction bitCountBitTwiddling64 (n) {\n  let m = n * 2.3283064365386963e-10 | 0;\n  m = m - ((m >> 1) & 0x55555555);\n  m = (m & 0x33333333) + ((m >> 2) & 0x33333333);\n  m = ((m + (m >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;\n  n = n - ((n >> 1) & 0x55555555);\n  n = (n & 0x33333333) + ((n >> 2) & 0x33333333);\n  n = ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;\n  return m + n;\n}\n\nfunction count1sb(num) {\n  let i = num * 2.3283064365386963e-10 | 0;\n  //      if (i > 0) {\n  i = i - ((i >> 1) & 0x55555555);\n  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);\n  i = (i + (i >> 4)) & 0x0f0f0f0f;\n  i = i + (i >> 8);\n  i = i + (i >> 16);\n  let count = i & 0x3f;\n  i = num & 0xffffffff;\n  //      }\n  i = i - ((i >> 1) & 0x55555555);\n  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);\n  i = (i + (i >> 4)) & 0x0f0f0f0f;\n  i = i + (i >> 8);\n  i = i + (i >> 16);\n  count += i & 0x3f;\n  return count;\n}\n\nfunction count64_count1sb32(n) {\n   return count1sb32(n | 0) + count1sb32(n* 2.3283064365386963e-10 | 0);\n}\n\nfunction count64_bitCountBitTwiddling32(n) {\n   return bitCountBitTwiddling32(n | 0) + bitCountBitTwiddling32(n* 2.3283064365386963e-10 | 0);\n}\n\nfunction count64_popcount2(n) {\n   return popcount2(n | 0) + popcount2(n* 2.3283064365386963e-10 | 0);\n}","setup":"","tests":[{"name":"bitCountBitTwiddling64","code":"let t = 0;\nfor (let i =  0; i < bits64.length; i++) {\n  t = bitCountBitTwiddling64(bits64[i]);\n}","results":{"aborted":false,"count":6964,"cycles":5,"hz":90671.33965898475,"stats":{"moe":6.405988522528136e-8,"rme":0.5808395611777065,"sem":3.268361491085783e-8,"deviation":2.6552294273814156e-7,"mean":0.000011028843334189212,"variance":7.050243312032239e-14,"numSamples":66},"times":{"cycle":0.07680486497929367,"elapsed":5.841,"period":0.000011028843334189212,"timeStamp":1694907652457}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":976,"cycles":2,"hz":6803.217158176943,"stats":{"moe":5.413454533176656e-7,"rme":0.36828906765118175,"sem":2.7619665985595184e-7,"deviation":0.0000017248475879647425,"mean":0.00014698928121059272,"variance":2.9750992017077904e-12,"numSamples":39},"times":{"cycle":0.1434615384615385,"elapsed":5.995,"period":0.00014698928121059272,"timeStamp":1694904847038}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":6964,"cycles":5,"hz":90671.33965898475,"stats":{"moe":6.405988522528136e-8,"rme":0.5808395611777065,"sem":3.268361491085783e-8,"deviation":2.6552294273814156e-7,"mean":0.000011028843334189212,"variance":7.050243312032239e-14,"numSamples":66},"times":{"cycle":0.07680486497929367,"elapsed":5.841,"period":0.000011028843334189212,"timeStamp":1694907652457}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":264,"cycles":3,"hz":3399.574820670902,"stats":{"moe":0.0000012364072700304312,"rme":0.4203259023289903,"sem":6.308200357298118e-7,"deviation":0.000005046560285838495,"mean":0.00029415443187764614,"variance":2.5467770718602312e-11,"numSamples":64},"times":{"cycle":0.07765677001569858,"elapsed":6.311,"period":0.00029415443187764614,"timeStamp":1694905177599}}}},{"name":"count1sb","code":"let t = 0;\nfor (let i =  0; i < bits64.length; i++) {\n  t = count1sb(bits64[i]);\n}","results":{"aborted":false,"count":6893,"cycles":7,"hz":90665.17805206253,"stats":{"moe":4.548327898263713e-8,"rme":0.41237495873524294,"sem":2.320575458297813e-8,"deviation":1.9135955453555986e-7,"mean":0.000011029592854555157,"variance":3.6618479112047905e-14,"numSamples":68},"times":{"cycle":0.0760269835464487,"elapsed":6.248,"period":0.000011029592854555157,"timeStamp":1694907658303}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":976,"cycles":2,"hz":8521.642206947798,"stats":{"moe":7.145251102422295e-7,"rme":0.6088927337364212,"sem":3.645536276746069e-7,"deviation":0.000002499253754660308,"mean":0.00011734827345657484,"variance":6.246269330183646e-12,"numSamples":47},"times":{"cycle":0.11453191489361704,"elapsed":5.784,"period":0.00011734827345657484,"timeStamp":1694904853039}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":6893,"cycles":7,"hz":90665.17805206253,"stats":{"moe":4.548327898263713e-8,"rme":0.41237495873524294,"sem":2.320575458297813e-8,"deviation":1.9135955453555986e-7,"mean":0.000011029592854555157,"variance":3.6618479112047905e-14,"numSamples":68},"times":{"cycle":0.0760269835464487,"elapsed":6.248,"period":0.000011029592854555157,"timeStamp":1694907658303}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":976,"cycles":2,"hz":3425.6541161455,"stats":{"moe":5.229460659143846e-7,"rme":0.17914323432217077,"sem":2.514163778434541e-7,"deviation":0.0000011792473409146595,"mean":0.00029191505216095385,"variance":1.3906242910542954e-12,"numSamples":22},"times":{"cycle":0.28490909090909095,"elapsed":6.727,"period":0.00029191505216095385,"timeStamp":1694905183946}}}},{"name":"popcount2","code":"let t = 0;\nfor (let i =  0; i < bits32.length; i++) {\n  t = popcount2(bits32[i]);\n}","results":{"aborted":false,"count":7015,"cycles":8,"hz":91131.37670168995,"stats":{"moe":5.105690343492177e-8,"rme":0.46528859001496636,"sem":2.6049440528021313e-8,"deviation":2.132238602317658e-7,"mean":0.000010973169024686267,"variance":4.546441457213559e-14,"numSamples":67},"times":{"cycle":0.07697678070817417,"elapsed":6.181,"period":0.000010973169024686267,"timeStamp":1694907664556}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":8867,"cycles":3,"hz":83739.03617886244,"stats":{"moe":4.5214320499675253e-7,"rme":3.786203620124988,"sem":2.3068530867181252e-7,"deviation":0.000001710808037167092,"mean":0.000011941861832085689,"variance":2.926864140035518e-12,"numSamples":55},"times":{"cycle":0.1058884888651038,"elapsed":5.997,"period":0.000011941861832085689,"timeStamp":1694904858829}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":7015,"cycles":8,"hz":91131.37670168995,"stats":{"moe":5.105690343492177e-8,"rme":0.46528859001496636,"sem":2.6049440528021313e-8,"deviation":2.132238602317658e-7,"mean":0.000010973169024686267,"variance":4.546441457213559e-14,"numSamples":67},"times":{"cycle":0.07697678070817417,"elapsed":6.181,"period":0.000010973169024686267,"timeStamp":1694907664556}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":4491,"cycles":5,"hz":58557.65683725098,"stats":{"moe":3.792061467779064e-8,"rme":0.2220542341359687,"sem":1.9347252386627876e-8,"deviation":1.54778019093023e-7,"mean":0.000017077186042113934,"variance":2.3956235194360196e-14,"numSamples":64},"times":{"cycle":0.07669364251513368,"elapsed":6.282,"period":0.000017077186042113934,"timeStamp":1694905190769}}}},{"name":"bitCountBitTwiddling32","code":"let t = 0;\nfor (let i =  0; i < bits32.length; i++) {\n  t = bitCountBitTwiddling32(bits32[i]);\n}","results":{"aborted":false,"count":6944,"cycles":5,"hz":91643.11089136678,"stats":{"moe":4.072503931604676e-8,"rme":0.3732169294095745,"sem":2.0778081283697326e-8,"deviation":1.7134044766070693e-7,"mean":0.000010911894961590667,"variance":2.9357549004571455e-14,"numSamples":68},"times":{"cycle":0.07577219861328559,"elapsed":6.058,"period":0.000010911894961590667,"timeStamp":1694907670742}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":8953,"cycles":3,"hz":83940.99934508002,"stats":{"moe":5.788107732400974e-7,"rme":4.8585954737472274,"sem":2.953116190000497e-7,"deviation":0.0000020881684835811327,"mean":0.000011913129552925822,"variance":4.360447615821528e-12,"numSamples":50},"times":{"cycle":0.10665824888734489,"elapsed":5.776,"period":0.000011913129552925822,"timeStamp":1694904864831}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":6944,"cycles":5,"hz":91643.11089136678,"stats":{"moe":4.072503931604676e-8,"rme":0.3732169294095745,"sem":2.0778081283697326e-8,"deviation":1.7134044766070693e-7,"mean":0.000010911894961590667,"variance":2.9357549004571455e-14,"numSamples":68},"times":{"cycle":0.07577219861328559,"elapsed":6.058,"period":0.000010911894961590667,"timeStamp":1694907670742}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":4484,"cycles":5,"hz":58461.99593124867,"stats":{"moe":4.725204804941075e-8,"rme":0.27624490408078173,"sem":2.4108187780311606e-8,"deviation":1.8982806041032892e-7,"mean":0.00001710512930786695,"variance":3.603469251914748e-14,"numSamples":62},"times":{"cycle":0.07669939981647542,"elapsed":6.108,"period":0.00001710512930786695,"timeStamp":1694905197063}}}},{"name":"count1sb32","code":"let t = 0;\nfor (let i =  0; i < bits32.length; i++) {\n  t = count1sb32(bits32[i]);\n}","results":{"aborted":false,"count":7022,"cycles":5,"hz":91464.01420211722,"stats":{"moe":5.470334262702366e-8,"rme":0.5003387306941377,"sem":2.790986868725697e-8,"deviation":2.2674084508362227e-7,"mean":0.000010933261662780288,"variance":5.141141082923519e-14,"numSamples":66},"times":{"cycle":0.07677336339604318,"elapsed":5.989,"period":0.000010933261662780288,"timeStamp":1694907676805}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":9001,"cycles":4,"hz":92143.7768934059,"stats":{"moe":6.109196598596556e-7,"rme":5.629244483790353,"sem":3.116937040100284e-7,"deviation":0.000002311582376116416,"mean":0.000010852604849883934,"variance":5.343413081572016e-12,"numSamples":55},"times":{"cycle":0.09768429625380529,"elapsed":6.114,"period":0.000010852604849883934,"timeStamp":1694904870613}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":7022,"cycles":5,"hz":91464.01420211722,"stats":{"moe":5.470334262702366e-8,"rme":0.5003387306941377,"sem":2.790986868725697e-8,"deviation":2.2674084508362227e-7,"mean":0.000010933261662780288,"variance":5.141141082923519e-14,"numSamples":66},"times":{"cycle":0.07677336339604318,"elapsed":5.989,"period":0.000010933261662780288,"timeStamp":1694907676805}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":4493,"cycles":5,"hz":57838.951271672755,"stats":{"moe":9.291385114821017e-8,"rme":0.5374039709024783,"sem":4.74050260960256e-8,"deviation":3.762657298338326e-7,"mean":0.00001728938678889499,"variance":1.4157589944738672e-13,"numSamples":63},"times":{"cycle":0.07768121484250519,"elapsed":5.924,"period":0.00001728938678889499,"timeStamp":1694905203249}}}},{"name":"count64_popcount2","code":"let t = 0;\nfor (let i =  0; i < bits64.length; i++) {\n  t = count64_popcount2(bits64[i]);\n}","results":{"aborted":false,"count":6882,"cycles":6,"hz":90951.07675367637,"stats":{"moe":7.853828450572639e-8,"rme":0.7143141542182392,"sem":4.007055331924816e-8,"deviation":3.3043024762440905e-7,"mean":0.000010994922058023668,"variance":1.0918414854512827e-13,"numSamples":68},"times":{"cycle":0.07566705360331888,"elapsed":5.971,"period":0.000010994922058023668,"timeStamp":1694907682799}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":7245,"cycles":4,"hz":75901.86922398694,"stats":{"moe":6.95409672373402e-7,"rme":5.2782894009581565,"sem":3.548008532517357e-7,"deviation":0.0000026072431523125387,"mean":0.000013174906102101293,"variance":6.7977168552806245e-12,"numSamples":54},"times":{"cycle":0.09545219470972387,"elapsed":5.884,"period":0.000013174906102101293,"timeStamp":1694904876733}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":3456,"cycles":4,"hz":45135.132375392255,"stats":{"moe":5.39996257464895e-8,"rme":0.24372802562894433,"sem":2.755082946249464e-8,"deviation":2.2040663569995713e-7,"mean":0.000022155689977442088,"variance":4.857908506057362e-14,"numSamples":64},"times":{"cycle":0.07657006456203985,"elapsed":6.085,"period":0.000022155689977442088,"timeStamp":1694905209216}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":6882,"cycles":6,"hz":90951.07675367637,"stats":{"moe":7.853828450572639e-8,"rme":0.7143141542182392,"sem":4.007055331924816e-8,"deviation":3.3043024762440905e-7,"mean":0.000010994922058023668,"variance":1.0918414854512827e-13,"numSamples":68},"times":{"cycle":0.07566705360331888,"elapsed":5.971,"period":0.000010994922058023668,"timeStamp":1694907682799}}}},{"name":"count64_bitCountBitTwiddling32","code":"let t = 0;\nfor (let i =  0; i < bits64.length; i++) {\n  t = count64_bitCountBitTwiddling32(bits64[i]);\n}","results":{"aborted":false,"count":6982,"cycles":5,"hz":91410.21066102479,"stats":{"moe":4.6083597257520997e-8,"rme":0.42125113333278186,"sem":2.351203941710255e-8,"deviation":1.9245433701515468e-7,"mean":0.0000109396969197269,"variance":3.7038671835942735e-14,"numSamples":67},"times":{"cycle":0.07638096389353322,"elapsed":6.06,"period":0.0000109396969197269,"timeStamp":1694907688775}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":5780,"cycles":3,"hz":67381.05303885446,"stats":{"moe":3.7582401684606494e-7,"rme":2.5323418012380037,"sem":1.917469473704413e-7,"deviation":0.0000014975915335560794,"mean":0.00001484096722892357,"variance":2.24278040137885e-12,"numSamples":61},"times":{"cycle":0.08578079058317824,"elapsed":5.962,"period":0.00001484096722892357,"timeStamp":1694904882622}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":4090,"cycles":4,"hz":53946.8017492815,"stats":{"moe":4.535324738234793e-8,"rme":0.2446662645221644,"sem":2.3139411929769354e-8,"deviation":1.8511529543815483e-7,"mean":0.000018536780079151194,"variance":3.426767260515535e-14,"numSamples":64},"times":{"cycle":0.07581543052372838,"elapsed":6.049,"period":0.000018536780079151194,"timeStamp":1694905215344}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":6982,"cycles":5,"hz":91410.21066102479,"stats":{"moe":4.6083597257520997e-8,"rme":0.42125113333278186,"sem":2.351203941710255e-8,"deviation":1.9245433701515468e-7,"mean":0.0000109396969197269,"variance":3.7038671835942735e-14,"numSamples":67},"times":{"cycle":0.07638096389353322,"elapsed":6.06,"period":0.0000109396969197269,"timeStamp":1694907688775}}}},{"name":"count64_count1sb32","code":"let t = 0;\nfor (let i =  0; i < bits64.length; i++) {\n  t = count64_count1sb32(bits64[i]);\n}","results":{"aborted":false,"count":6946,"cycles":8,"hz":91573.29380051375,"stats":{"moe":1.3769693720302318e-8,"rme":0.12609362085923334,"sem":7.025353938929754e-9,"deviation":5.7505000337403694e-8,"mean":0.000010920214382355107,"variance":3.3068250638047987e-15,"numSamples":67},"times":{"cycle":0.07585180909983857,"elapsed":6.055,"period":0.000010920214382355107,"timeStamp":1694907694840}},"platforms":{"Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:109.0) Gecko/20100101 Firefox/117.0":{"aborted":false,"count":7287,"cycles":3,"hz":74076.6962831389,"stats":{"moe":7.319433608323089e-7,"rme":5.421994603683489,"sem":3.7344049022056576e-7,"deviation":0.000002744215951005593,"mean":0.000013499522119314826,"variance":7.53072118575353e-12,"numSamples":54},"times":{"cycle":0.09837101768344714,"elapsed":5.916,"period":0.000013499522119314826,"timeStamp":1694904888589}},"Mozilla/5.0 (Android 11; Mobile; rv:109.0) Gecko/117.0 Firefox/117.0":{"aborted":false,"count":3452,"cycles":4,"hz":45145.03147294378,"stats":{"moe":6.651488702798845e-8,"rme":0.3002816668297839,"sem":3.393616685101452e-8,"deviation":2.693599738157351e-7,"mean":0.000022150831827403148,"variance":7.255479549401351e-14,"numSamples":63},"times":{"cycle":0.07646467146819566,"elapsed":5.875,"period":0.000022150831827403148,"timeStamp":1694905221429}},"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/116.0.0.0 Safari/537.36":{"aborted":false,"count":6946,"cycles":8,"hz":91573.29380051375,"stats":{"moe":1.3769693720302318e-8,"rme":0.12609362085923334,"sem":7.025353938929754e-9,"deviation":5.7505000337403694e-8,"mean":0.000010920214382355107,"variance":3.3068250638047987e-15,"numSamples":67},"times":{"cycle":0.07585180909983857,"elapsed":6.055,"period":0.000010920214382355107,"timeStamp":1694907694840}}}}]}