Use BitMaps for more gas-efficient minting / transfer / burning

[0xCLARITY]

I came across another 721 implementation, ERC721Psi, which like 721A supports batch minting, but does so at a reduced gas cost (on the order of ~15k less gas for _mint() in my benchmarking). It also has cheaper transfers and burn functionality.

I thought I would take a look at how to port this over to 721A - but got a bit overwhelmed with the deep optimizations in 721A, like how I would handle the _packedOwnerships and _setExtraDataAt().

I'm happy to contribute / collaborate on a PR - but I feel like it'd be helpful if someone more familiar with the 721A code could take a look at the 721Psi approach and see if:

• It makes sense to try to port this approach over, given the potential gas savings
• If so, a rough roadmap of what would need to be touched to do that.

ERC721Psi Information:

• Medium Post
• 721Psi Repo
• BitMap Repo

[Vectorized]

We have considered and discussed that at great lengths internally and with external experts.

Unfortunately, this is not a feature we are interested to add.

They have removed the storage of the balance data, which makes balanceOf go from O(1) to O(n) complexity.

If you remove that from ERC721A, you will instantly see the minting gas drop by > 20k.
But that will damage on-chain interoperability and future-proofness.

The 15k gas savings you see is due to:

• Removal of a SSTORE to an empty storage slot (-20000 gas).
• Addition of a SSTORE to a non-empty storage slot in the bitmap (+5000 gas).

Keeping an O(1) balanceOf is a non-negotiable requirement of ERC721A.

[sillytuna]

I've reworked the non balanceOf relevant parts of 721Psi for O(1) token lookups and put them into the 721A. I've also merged with my lengthless array version for a small extra advantage. Here are my notes and repo link.

Test Feedback
The main repo test could have a couple more added. The burn tests include moving and checking tokens at the end of the batch and helped me find errors that the main tests didn't, even though this was unrelated to burning.

The repo's gas tests are incomplete because they use a contract to do batches and thus they're heavily skewed by warm storage memory. In addition to those tests, or instead, should be a set of individual calls to e.g. transferFirst, transferMiddle, transferLast - these 3 provide much more useful information for real world use cases.

The results are using slightly different tests to the repo's to allow for some storage warm ups and gas measures.

Results
+5k mint cost per batch on average, with a peak of +25k when crossing 256 token boundaries.

Batch of 100(!)
transferFromFirst 44364 (old) vs 44501 (new) - 137 worse
transferFromMiddle 189840 (old) vs 91608 (new) - 98232 better
transferFromLast 300229 (old) vs 91597 (new) - 208,632 better

Batch of 10
transferFromMiddle 92688 vs 91608 (new) - 1080 better
transferFromLast 101509 vs 91597 (new) - 9912 better

Comments
Is this better? I don't know - perhaps it depends on the batch size. The main downside is a typical 5k increase in mint costs. The upside is it's barely different for repeat transfers and better for virgin transfers - vastly better for larger mint sizes. There are other optimisations possible as per 721Psi if you believe in batch burning.

Code readability is unchanged other than _packedOwnershipOf which is definitely more complex.

Two magic numbers are used from 721Psi - I'd want to know how they're calculated and have a deep set of tests for a large range of token ids (0-10,000,000) including lots of transfers and burns.

Code complexity is reasonable as long as the algorithm is explained. All I've done is partition ids into 256 unit blocks, something I'd been playing with, and used 721Psi's clever trick to make that fast (previously I'd not known about this clever flag search trick, kudos to the dev).

If anyone wants the code, it's here. A previous commit bitscan implementation is prior to the independent lengthless array optimisation (tho I use the same trick in next commit), so may be easier to read.

EDIT: DO NOT USE IN PRODUCTION CODE! You'll want a lot more tests and this was only meant as a draft for testing.

Repo
(not tidied up these commits, be warned)
https://github.com/sillytuna/ERC721A/tree/feature/bitscan

Link to lengthless array optimisation PR:
#394

[sillytuna]

New (100 batch)

|  ERC721AGasReporterMock  ·  mintOne             ·      78279  ·     112479  ·      95379  ·            6  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  mintHundred         ·          -  ·          -  ·     252524  ·            6  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  transferFromFirst   ·          -  ·          -  ·      44501  ·            1  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  transferFromLast    ·          -  ·          -  ·      91597  ·            1  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  transferFromMiddle  ·          -  ·          -  ·      91608  ·            1  ·          -  │
···························|······················|·············|·············|·············|···············|··············

Previous (100 batch)

|  ERC721AGasReporterMock  ·  mintOne             ·      73265  ·      90365  ·      81815  ·            6  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  mintHundred         ·          -  ·          -  ·     247510  ·            6  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  transferFromFirst   ·          -  ·          -  ·      44364  ·            1  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  transferFromLast    ·          -  ·          -  ·     300229  ·            1  ·          -  │
···························|······················|·············|·············|·············|···············|··············
|  ERC721AGasReporterMock  ·  transferFromMiddle  ·          -  ·          -  ·     189840  ·            1  ·          -  │
···························|······················|·············|·············|·············|···············|··············

[sillytuna]

Additional negative - minting gas estimation would be trickier during busy mints. Would need to allow 20k or so above whatever the wallet estimates.