Is it okay to use BitMaps with address as keys?
Asking because I see BitMaps are better for sequential keys in docs:
providing the keys are sequential.
Why exactly do they have to be sequential? I didn't really notice anything in the implementation regarding that.
My use-case is to track whether some airdrops (campaigns) are claimed by some addresses. I was thinking of casting address to uint256 to be used as keys.
// campaignManager => campaignId => uint256(claimer) => claimed
mapping(address => mapping(uint256 => BitMaps.BitMap)) internal hasClaimed;
Is this okay? Is this better than a more naive approach like:
// campaignManager => campaignId => claimer => claimed (0 = false, !0 = true)
mapping(address => mapping(uint256 => mapping(address => uint256))) internal hasClaimed;
When the keys are sequential, you will be changing a storage slot from zero to non-zero only once in every 256 new keys added, and from non-zero to non-zero for all other 255 keys.
When the keys are "random addresses", you are likely to change a storage slot from zero to non-zero pretty much on every new key added.
Since the cost of changing a storage slot from zero to non-zero is much higher than the cost of changing a storage slot from non-zero to non-zero (~22K vs ~5K), you can optimize your system performance by using sequential keys.
But as you've noticed, nothing in the BitMaps library requires that you use sequential keys.
Disclaimer:
I've encountered this library, following your question, for the first time.
Everything above is based on my quick analysis of it, so you might want to wait for additional feedback.
2 Likes
There is nothing stopping you from using it that way, however you use BitMaps to save on gas. This is achieved by limiting how much you have to write to the EVM storage. This however does not work unless the "index" value is sequential.
Someone has written a pretty exhaustive explanation how BitMaps work, its pretty indepth but if you wanna know how it "really" works and why it won't work for non-sequencial its definetly a good read
1 Like
Hey @sebastiantf, as I mentioned in your PR, I think the NatSpec of the contract can be improved.
For the record, the way BitMaps work is by packing 256 booleans in a single 32-bytes slot (256 bits), so that each index within ranges of 256 will access the same storage saving gas because the slot is no longer cold.
My use-case is to track whether some airdrops (campaigns) are claimed by some addresses. I was thinking of casting address to uint256 to be used as keys.
This is fine, but I'd suggest a way of taking advantage of the "warm" slot, so perhaps uint256 can be used as keys if the token ids are sequential or consecutive in a way. Note that this will only work if you let multiple people claim the airdrop on a single transaction.
Hope this helps!
1 Like