# Loop optimization checking coordinates in a grid

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
``````
• 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

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.