1

I built a contract where users can set an image in a specific coordinate, that position can only have one image. The grid size is 400 height, and dynamic width (Will grow overtime) and there are 3 different image sizes: 10x10, 20x20, 40x40 (pixels).

I need to optimize the loop in order to reduce gas cost which is very high right now.

Here's my current implementation, where coords and sizes are divided by 10 to reduce gas cost.

pragma solidity 0.4.19;


contract Test {

    mapping (uint => bool[40]) public grid;

    function check(uint x, uint y, uint size) public {

        for(uint i = 0; i < size; i++) {
            for(uint j = 0; j < size; j++) {

                if(grid[x + i][y + j]) {
                    // image exists in this slot
                    revert();
                }

                grid[x + i][y + j] = true;

            }
        }
    }

}

Possible sizes:

 - small: 1 (1 slot)
 - medium: 2 (4 slots)
 - big: 4 (16 slots)

Current gas cost:

- Small: 43223
- Medium: 76251
- Big: 163181
4
  • You can save half the gas simply by declaring your mapping to be uint rather than bool in your original code. This is due to how Solidity packs booleans when they are written I think. May be easier than assembly :-) – benjaminion Feb 10 '18 at 18:51
  • @benjaminion just tried, it actually increases a lot, Gas: 351253 for the big picture, instead of 163181. Thanks anyway :), I'm trying everything, even assembly, which I don't really know. I'd rather have a solidity answer, but anything would do. I'm using truffle and ganache for testing the gas costs, just in case there are differences with main net. – Marcos Casagrande Feb 10 '18 at 18:58
  • Yes, I did something wrong :-) Apologies. I think the main way assembly could help you here is if you use it to minimise loads and stores in the bit-packed grid (i.e. check size bits at a time with one load rather than doing size loads; ditto storing). This will be quite complicated and requires deep knowledge of solidity mapping storage. A simple naive translation to assembly may help a little by eliminating bounds checks, but it isn't the big prize. – benjaminion Feb 10 '18 at 19:10
  • I understand, thank you very much. Maybe my code is already optimized, and I'll have to accept that the users are gonna have to pay that amount of gas. I'll probably stick to the solidity code, but just so I can get it out of my head, do you know how to read/write a 2D array or mapping in assembly? Didn't find anything in the web, and I really want to know. – Marcos Casagrande Feb 10 '18 at 19:19
2
+50

You can pack all bools in a row into a single uint and save on storage updates:

pragma solidity 0.4.19;

contract Test {

    mapping (uint => uint) public grid;

    function check(uint x, uint y, uint size) public {

        for(uint i = 0; i < size; i++) {
            uint row = grid[x + i];
            for(uint j = 0; j < size; j++) {
                // if (y + j) bit is set in row
                if((row >> (y + j)) & uint(1) == uint(1)) {
                    // image exists in this slot
                    revert();
                }

                // set bit (y + j)
                row = row | (uint(1) << (y + j)); 
            }
            grid[x + i] = row;
        }
    }
}

New gas costs:

- Small: 42632
- Medium: 63808
- Big: 107750

The bigger the size the greater the improvement.

Note also that subsequent calls to check in the rows that have been touched will cost even cheaper because you will need to pay only 5,000 gas for updating storage slots instead of 20,000. Calling check(0,0,4) followed by check(0,4,4) will cost only 48214 gas.

You can optimise it even further by packing multiple rows into single uint. If every row is 40 bits you can pack [256 / 40] = 6 rows. The code however will be a bit more complex.


Previous answer:

Look into loops in assembly http://solidity.readthedocs.io/en/develop/assembly.html#loops. They allow saving gas on bounds checking.

You can find more examples here

6
  • Thank you for answering, I knew about that, but I don't know any assembly, and I believe it will be a risk if I code a smart contract I don't understand :P. I'm searching how to access a mapping in assembly but I'm not finding any example yet. – Marcos Casagrande Feb 10 '18 at 13:29
  • I tried changing the code to assembly, but I'm having trouble retrieven/saving the mapping/2D array. Care to take a look? – Marcos Casagrande Feb 10 '18 at 18:17
  • Sure, you can include your code in the question. – medvedev1088 Feb 10 '18 at 18:21
  • @MarcosCasagrande benjaminion's idea was in fact good. I updated my answer. – medvedev1088 Feb 12 '18 at 17:22
  • 1
    Wow, very nice improvements. I'm running tests, and everything seems to be working perfectly! Let me a moment to fully understand the code and I'll give you the bounty! – Marcos Casagrande Feb 12 '18 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.