{"_id":"2d-sparse-bitmaps","_rev":"2-986b1f62acbd72a13ae98785289a731b","name":"2d-sparse-bitmaps","dist-tags":{"latest":"0.1.0"},"versions":{"0.0.1":{"name":"2d-sparse-bitmaps","version":"0.0.1","description":"Two-dimensional sparse bitmaps","homepage":"https://github.com/electric-sheep-co/2d-sparse-bitmaps-node","repository":{"type":"git","url":"git+https://github.com/electric-sheep-co/2d-sparse-bitmaps-node.git"},"main":"index.js","scripts":{"test-only":"tape test/*.js","lint":"eslint .","test":"eslint . && tape test/*.js"},"author":{"name":"Ryan Joseph","email":"ryan@electricsheep.co","url":"https://electricsheep.co"},"license":"MIT","devDependencies":{"eslint":"^7.4.0","ioredis":"^4.17.3","tape":"^5.0.1","tape-promise":"^4.0.0"},"gitHead":"b5f2c2199217619b79ff134fbdfd5443505cbc5c","bugs":{"url":"https://github.com/electric-sheep-co/2d-sparse-bitmaps-node/issues"},"_id":"2d-sparse-bitmaps@0.0.1","_nodeVersion":"12.16.3","_npmVersion":"6.14.4","dist":{"integrity":"sha512-oX14GFDH8523JH25IusbXxnotwM+mmJbuStOKUlcPcA8X+ygkIe7X6SjuUsZDpBfDUHV7FD44xP6u0jKgP7MoA==","shasum":"71063c143219c48ed6b7d63bd5c2494860e94ff5","tarball":"https://registry.npmjs.org/2d-sparse-bitmaps/-/2d-sparse-bitmaps-0.0.1.tgz","fileCount":16,"unpackedSize":26241,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJfE7bhCRA9TVsSAnZWagAAFqUP/3TH9ALxB/Jd36qQuvFj\nUsPpEUdSAx1tlGJ2QuKxviDjWZxAVoiFNclA7ID7GtfJ+gawcmdwpLn8F5BY\nbOHTGzRMHTfK6ALXnHLLLnMivUB5ptLbY1YMR4CFFWZyK57Bg1v3sbdYyR8I\nUq9lfE6GfCdsFM1yz0+5WkTi8LmcoWZyxn2DxtIiJL6zrSD8eHh6GUGaxtRK\n0kgPcDEsYFH3R5fcW3w+cPLMe0nNUZKcwRtpxIRvf/otVNqlxfXNGEVisyt6\nbHM8Zf+VgZ+MWiW5A6EcXtNfpAWiI5fyGSin/MDCogQNQIzVzWYTuG+Kz2Ui\nsznlNRmzMaJv2w18zJ2Jfd3TsoRpG8ZK1MRqUtpJRAZqxgQJw3Tt2zvdDvjm\nrxClrdux5zIm1JVsVdxFnpYqCUKmx4FD51s2BQx0qN1lUBsu0VKxMVnnf9aK\nh0LmbIud/71cOZ4/kw1tZxtkj9s5P0vg0lYB6hklPx0M6uBdhJdRe7CC077W\nyZsc4fFfL3rjXHdaaJ4eGhE0BuXdY/qOXPkdClhcMSEk351+mlLVW5oM1qvA\nfFV/cqnmlab9JRRHv/za2wXnwu9IdHZ7cOSMoO0wZSkIWzWEJG6u87Y3euXZ\nF2pbh56jW08FGaaqw/4RXtaVDHNsNbrjnG9shkiKoS/vPKsSv/WjmRAEC8j0\n/z+E\r\n=PUM+\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQCTWGFjacdDMcvi+ODiivMQNCGZyjNMCoX7FkeTO1Vl/AIhAP++HdFHyN0euwLDLonYoLWtv10XU6gi/EnjdkKSk/gd"}]},"maintainers":[{"name":"electric-sheep","email":"ryan@electricsheep.co"}],"_npmUser":{"name":"electric-sheep","email":"ryan@electricsheep.co"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/2d-sparse-bitmaps_0.0.1_1595127520707_0.8045045911088247"},"_hasShrinkwrap":false},"0.1.0":{"name":"2d-sparse-bitmaps","version":"0.1.0","description":"Two-dimensional sparse bitmaps","homepage":"https://github.com/electric-sheep-co/2d-sparse-bitmaps-node","repository":{"type":"git","url":"git+https://github.com/electric-sheep-co/2d-sparse-bitmaps-node.git"},"main":"index.js","scripts":{"test-only":"tape test/*.js","lint":"eslint .","test":"eslint . && tape test/*.js"},"author":{"name":"Ryan Joseph","email":"ryan@electricsheep.co","url":"https://electricsheep.co"},"license":"MIT","devDependencies":{"eslint":"^7.4.0","ioredis":"^4.17.3","tape":"^5.0.1","tape-promise":"^4.0.0","yargs":"^15.4.1"},"keywords":["sparse-bitmap","sparse-bitset","sparse-data-structure","data-structure","game-development","cache","redis"],"gitHead":"9ab38de5fd89fb9bc2c89045abd20b2714c636ee","bugs":{"url":"https://github.com/electric-sheep-co/2d-sparse-bitmaps-node/issues"},"_id":"2d-sparse-bitmaps@0.1.0","_nodeVersion":"14.6.0","_npmVersion":"6.14.6","dist":{"integrity":"sha512-FQA9MZTIn/edA73Iql1X+qA5u4yr9K/10isgVPo1WC2841EL5oI/72RyUWK/fp3WxOt4OieQLNg+4L/VrwuK2w==","shasum":"7163ef5e1d626843037138bbd9f307c1b83b9f98","tarball":"https://registry.npmjs.org/2d-sparse-bitmaps/-/2d-sparse-bitmaps-0.1.0.tgz","fileCount":21,"unpackedSize":51762,"npm-signature":"-----BEGIN PGP SIGNATURE-----\r\nVersion: OpenPGP.js v3.0.4\r\nComment: https://openpgpjs.org\r\n\r\nwsFcBAEBCAAQBQJfGlgVCRA9TVsSAnZWagAAhoIP/2aCt7o8lAq2nya54Q2/\ncYqeDtkFoBfe1p9/ymY5q+qbfty//3z7IGCMfHRNXCplit7Ly8BdSRXXEZ7K\n05rJB8YjX/Y/qPWjRqORnAomOb++3Kt02e1RN4JeG1XcPgY/CkXCJddv+sap\nTyaeAF23a9r2PhtQHZL3++nkTTgRYEhXZOOkIu0SL6/jUoM0GK1yCbkrirhN\nfgvteReDy9h3MjkE2u+fhihUfxM1hv7Q8LXDPR6Fam7kgSTBox/B2wlEWihQ\n8Oe0d+JXbQFcf79/CpmnDH0DVy0eMi/eFSz11b047onRBDiJPANL02faxe5v\nHO9m7ywvf5rRXcVZKk1vYNPvOsVLcZQ2hdgtwgLYVmK+9PkSuqCPr1X9hABJ\n+zCHve0S+lDG0bKxBk1t79yNmG2iootIpMXB298dZ1Sz76ss/gnS5h3RzTn8\neKknF5uT1LMZdIA1QMfAIDBn68Pbdu41QMaTBzDj33Yx9D5GjmbqgAvXUXj7\nbZVHVWJGkLMWW3OZ5VzBnTpdiyA2Pd/FrevCR0PW80RWRg20jD+DZHxVJNBj\ncvtRCji4jg6IVK86nyVP7y+Y+o3iKxhTVXc+M4NoJV9Gdb2dqDt+NBILmY9Q\nKKPF0rsXg7VMyUxlZFPn3ye3fRs4eLVM9WPY1mRWd/Ni5dkO+ax9ZvQlhRSs\n/Cdh\r\n=arDG\r\n-----END PGP SIGNATURE-----\r\n","signatures":[{"keyid":"SHA256:jl3bwswu80PjjokCgh0o2w5c2U4LhQAE57gj9cz1kzA","sig":"MEYCIQDVJ+Drq5J5brLFugFhq4cCDo+pQfAu5lspAHZYn/yZ3gIhAKIhrlDDB94U716/h6tkPkig1cCb+m5fl5MputdyB/xH"}]},"maintainers":[{"name":"electric-sheep","email":"ryan@electricsheep.co"}],"_npmUser":{"name":"rpjsf","email":"ryan.joseph@gmail.com"},"directories":{},"_npmOperationalInternal":{"host":"s3://npm-registry-packages","tmp":"tmp/2d-sparse-bitmaps_0.1.0_1595562005130_0.555411909520817"},"_hasShrinkwrap":false}},"time":{"created":"2020-07-19T02:58:40.706Z","0.0.1":"2020-07-19T02:58:40.811Z","modified":"2022-04-04T10:18:59.237Z","0.1.0":"2020-07-24T03:40:05.304Z"},"maintainers":[{"name":"electric-sheep","email":"ryan@electricsheep.co"}],"description":"Two-dimensional sparse bitmaps","homepage":"https://github.com/electric-sheep-co/2d-sparse-bitmaps-node","repository":{"type":"git","url":"git+https://github.com/electric-sheep-co/2d-sparse-bitmaps-node.git"},"author":{"name":"Ryan Joseph","email":"ryan@electricsheep.co","url":"https://electricsheep.co"},"bugs":{"url":"https://github.com/electric-sheep-co/2d-sparse-bitmaps-node/issues"},"license":"MIT","readme":"# 2d-sparse-bitmaps\n\n[![CI Status][1]][2]\n[![Dependencies][3]][4]\n[![Dev Dependencies][5]][6]\n\nA two-dimensional sparse bitmap implementation for [Node.js](https://nodejs.org/) 10 or later, with no required dependencies.\n\nAllows for flexible backing store choice, the primary supported being [Redis](http://redis.io/) (via [`ioredis`](https://github.com/luin/ioredis)).\n\nThe underlying chunked implementation is efficient; the following example needs only 64 bytes to represent two coordinates which are ~1,414,213 units distant each other on the diagonal:\n\n```javascript\nconst TwoD = require('2d-sparse-bitmaps');\nconst bitmap = new TwoD.SparseBitmap({ [TwoD.ChunkWidthKey]: 16 });\n\nawait bitmap.set('so-far-away', 0, 0);\nawait bitmap.set('so-far-away', 1e6, 1e6);\n```\n\nAdditionally, the sparse nature of the data structure allows for performant queries within specified bounds via [`inBounds()`](#get-all-set-bits-in-given-bounds).\n\n## Installation\n\n```shell\n$ npm install 2d-sparse-bitmaps\n```\n\n## Examples\n\nThe included [tests](./test), [benchmarking tool](./tools/benchmark) & [cli](./cli) hopefully provide ample usage examples, and in the case of the [cli](./cli) an easily-accessibly interactive means of working with the library.\n\n## Usage\n\nAll coordinates must be _unsigned_, a limitation that may be removed in future releases.\n\n### Instantiation\n\nWith the default in-memory store:\n\n```javascript\nconst TwoD = require('2d-sparse-bitmaps');\nconst bitmap = new TwoD.SparseBitmap();\n```\n\nWith an [`ioredis`](https://github.com/luin/ioredis) instance:\n\n```javascript\nconst Redis = require('ioredis');\nconst TwoD = require('2d-sparse-bitmaps');\n\nconst rConn = new Redis();\nconst bitmap = new TwoD.SparseBitmap({ [TwoD.BackingStoreKey]: rConn });\n```\n\n#### Full options\n\n| Constant Name | Description | Default | Restrictions |\n| --- | --- | --- | --- |\n| `ChunkWidthKey` | The width in bits of each chunk in the sparse bitmap | 128 | >= 8, must be a multiple of 8 |\n| `KeyPrefixKey` | The string preprended to each `key` before being passed onto the backing store. | `sparse-bitmap` | none |\n| `BackingStoreKey` | The backing store instance to be used.  | [`InMemoryStore`](stores/in-memory.js) | Must conform to the [aforementioned interface][7]. |\n\nEach chunk requires up to `(X / 8) * X` bytes of storage, where `X` is the chosen chunk width. Accordingly, the default chunk width of 128 requires 2048 bytes per chunk.\n\n#### Backing store interface\n\nAny backing store must implement this interface:\n\n```javascript\ngetbit(key, bitPosition);\nsetbit(key, bitPosition, value);\ngetBuffer(key);\n```\n\nIt may optionally implement `pipeline()`, which must return an instance implementing the aforementioned interface *plus* `exec()` for pipeline execution; additionally, the backing store interface methods of this instance must accept an additional callback argument of type `function (err, result)`.\n\nThe default [`InMemoryStore`](stores/in-memory.js) provides an example implementation sans `pipeline()` et. al.\n\n### Get:\n\nCannot be called within `pipelinedMutate()` context. No option to pipeline these calls is available; high-volume searches should be performed with [`inBounds()`](get-all-set-bits-in-given-bounds) instead.\n\nThe bit at `(x, y)` in `key`:\n\n```javascript\nconst xySet = await bitmap.get(key, x, y);\n```\n\n### Set:\n\nThe bit at `(x, y)` in `key`:\n\n```javascript\nawait bitmap.set(key, x, y);\n```\n\n### Unset:\n\nThe bit at `(x, y)` in `key`:\n\n```javascript\nawait bitmap.unset(key, x, y);\n```\n\n### Get all set-bits in given bounds:\n\nCannot be called within `pipelinedMutate()` context. This method performs it's own internal pipelining to be as performant as possible.\n\nWithin the bounding box definition - here named `bBox` - `from` is the top-left coordinate and `to` is the bottom-right coordinate:\n\n```javascript\nconst bBox = {\n  from: { x: …, y: … },\n  to: { x: …, y: … }\n};\n\nconst allInBounds = await bitmap.inBounds(key, bBox);\n```\n\n`allInBounds` will be a list of two-element lists (tuples), where the `x` coordinate is the first value (`[0]`) and `y` is the second (`[1]`).\n\nHas a third optional parameter, `strict`, which if set to `true` will cull the list before return to only include points strictly within the given bounding box; otherwise, points within any _chunk intersected by the bounding box_ will be returned.\n\n### Get a key-bound instance:\n\nThe returned instance has the same interace as above _except_ that all methods _no longer take_ the `key` argument, as tgey are all now bound to `key` specifically:\n\n```javascript\nconst occupiedBitmap = bitmap.boundToKey('occupied');\nawait occupiedBitmap.set(x, y);\nconst check = await occupiedBitmap.get(x, y);\nawait occupiedBitmap.unset(x, y);\nconst occupiedInBounds = await occupiedBitmap.inBounds({ … });\n```\n\n### Pipelined mutation:\n\nWhen executing many mutations (`set()` and `unset()`) in high volume and/or frequency, the `pipelineMutate()` method should be used  to provide a context in which any calls to these mutators - *including methods of instances produced by `boundToKey()`* - will be pipelined appropriately and therefore executed as an atomic unit:\n\n```javascript\nconst bitmap = new TwoD.SparseBitmap({ [TwoD.BackingStoreKey]: new Redis() });\nconst keyBound = bitmap.boundToKey('foobar');\n\nconst scopeReturn = await bitmap.pipelinedMutate(async () => {\n  for (…) {\n    await bitmap.set('foobar', x, y);\n  }\n\n  for (…) {\n    await keyBound.unset(x, y);\n  }\n});\n```\n\nUpon return of the scoped function, the pipeline will be executed (with the results being discarded) and the result of the scoped function returned by `pipelinedMutate()`.\n\nWhen used with a backing store that does not support pipelining, the mutators are executed normally (against the store at call-time), therefore this method may be used with any backing store regardless of its pipelining capability or lack thereof.\n\nBuilding a large pipeline may cause significant runtime memory pressure and as such has the potential to cause out-of-memory conditions. Consumers are advised to create reasonably-sized pipelines, though the author does not (yet) provide guidance as to what qualifies \"reasonably-sized\".\n\nThe accessor methods of `SparseBitmap` - `get()` and `inBounds()` - **cannot be called within a pipelined context!** Doing so is a programming error and will result in an exception being thrown.\n\n## Contributing\n\nAny and all contributions are welcome and the project is accepting of pull requests at all times.\n\n### Testing\n\nThe full test suite (including linting) is run via:\n\n```shell\n$ npm test\n```\n\nIf the `NODE_ENV` environment variable is set to `ci`, all tests against redis will be skipped entirely.\n\nWhen running the tests against redis, the host is assumed to be the local machine on the standard port. Additionally:\n* `REDIS_LOCAL_AUTH` will be used as the connection password, if set.\n* `REDIS_LOCAL_DB` will select the redis DB to test within, if set.\n\nUtilizing [`tape`][9], each individual test file can be executed in isolation:\n\n```shell\n$ node test/default-store.js\n…\n# ok\n```\n\n### Authors\n\n* Ryan Joseph, [Electric Sheep Co.][8]\n\n## Benchmarks\n\nThe following rudimentary benchmarks were performed on an AWS EC2 type *m5a.large* (4 vCPUs, 16GB RAM) running the Ubuntu 20LTS AMI (ID `ami-03ceeb0f46ee38ce7`). Both the backing store redis instance and [`benchmark`](./tools/benchmark) script were run on this VM. All redis [snapshotting](https://redis.io/topics/persistence#snapshotting) was disabled. The EC2 instance was created specifically for this use and had no other workloads during the benchmarking process.\n\nVersion particulars:\n* Linux kernel `5.4.0-1020-aws`\n* Node `14.6.0` (v8 `8.4.371.19-node.12`)\n* Redis `5.0.7 (636cde3b5c7a3923)` (standalone)\n\nThe benchmark run consisted three runs of differing multipliers (1, 3 & 5), each 101 iterations of the full sequence defined in [`benchmark::T.seq.main()`](./tools/benchmark#L54).\n\nThe primary takeaway is the significant increase in performance afforded by pipelined operations.\n\nAccording to this limited dataset, the mean search rate is **~1.2 Gbit/s** (~150 MB/s), though it does depend on how sparsely-populated the search area is (with rates from ~493 Mbit/s - ~2 Gbit/s observed). Without pipelining enabled, this rate drops *drastically* to ~183 Mbit/s (a *6.5x* drop).\n\nThe full data set is linked below, and the Google Sheet used to post-process and analyze the data is [available here][10].\n\n### Raw data\n\n* [full JSON report][11] & [processed CSV][12] for `benchmark -i 101 -w 127`\n* [full JSON report][13] & [processed CSV][14] for `benchmark -i 101 -w 127 -m 3`\n* [full JSON report][15] & [processed CSV][16] for `benchmark -i 101 -w 127 -m 5`\n\n## License\n\n[MIT](LICENSE)\n\n[1]: https://github.com/electric-sheep-co/2d-sparse-bitmaps-node/workflows/CI/badge.svg?branch=main\n[2]: https://github.com/electric-sheep-co/2d-sparse-bitmaps-node/actions?query=workflow%3ACI\n[3]: https://david-dm.org/electric-sheep-co/2d-sparse-bitmaps-node.svg\n[4]: https://david-dm.org/electric-sheep-co/2d-sparse-bitmaps-node\n[5]: https://david-dm.org/electric-sheep-co/2d-sparse-bitmaps-node/dev-status.svg\n[6]: https://david-dm.org/electric-sheep-co/2d-sparse-bitmaps-node?type=dev\n[7]: https://github.com/electric-sheep-co/2d-sparse-bitmaps-node/#backing-store-interface\n[8]: https://electricsheep.co\n[9]: https://www.npmjs.com/package/tape\n[10]: https://docs.google.com/spreadsheets/d/1rFrTLa0Msnghn_Xy5vqghVWRXzJywtWvZrgdLZG-fvM/edit?usp=sharing\n[11]: https://static.2dsb.electricsheep.co/report.20200722T110119219Z.json\n[12]: https://static.2dsb.electricsheep.co/report.20200722T110119219Z.csv\n[13]: https://static.2dsb.electricsheep.co/report.20200722T184653181Z.json\n[14]: https://static.2dsb.electricsheep.co/report.20200722T184653181Z.csv\n[15]: https://static.2dsb.electricsheep.co/report.20200723T102057790Z.json\n[16]: https://static.2dsb.electricsheep.co/report.20200723T102057790Z.csv","readmeFilename":"README.md","keywords":["sparse-bitmap","sparse-bitset","sparse-data-structure","data-structure","game-development","cache","redis"]}