Nested map lookups are very inefficient

General Issues and Bug Reporting
, , ,
1

Summary

Not sure how to explain this, nested map lookups are extremely inefficient somehow, looks like the entire inner map gets copied on each lookup

Happens with [][t]u and [t][u]v but not [][]t nor [t][]u. The performance cost is exponential, it is 100x in the following repro :

MakeBigArray()<transacts>:[]logic = for(I := 0..1000). true

MakeBigMap()<transacts>:[int]logic =
    var TempMap : [int]logic = map{}
    for(I := 0..1000):
        option. set TempMap[I] = true
    TempMap

# Forces lookup by reference
big_array(t:type) := class:
    Array: []t
    Get(Index: int)<reads><decides>:t = Array[Index]

# Forces lookup by reference
big_map(t:type) := class:
    Map: [int]t
    Get(Index: int)<reads><decides>:t = Map[Index]

LookUpArrays()<suspends>:void=
    #####################################################
    ####### NOT LAGGY (first dimension is array) ########
    #####################################################

    # SomeBigArray : []logic = MakeBigArray()

    # # Slow
    # var BigNestedMap : [][]logic = array{MakeBigArray()}

    # profile("Slow Lookup"):
    #     for(__ := 0..1000):
    #         option. BigNestedMap[0][0]
    
    # # Fast
    # var BetterBigNestedMap : []big_array(logic) = array{big_array(logic){Array := SomeBigArray}}

    # profile("Fast Lookup"):
    #     for(__ := 0..1000):
    #         option. BetterBigNestedMap[0].Get[0]

    # SomeBigArray : []logic = MakeBigArray()

    # # Slow
    # var BigNestedMap : [int][]logic = map{}
    # option. set BigNestedMap[0] = MakeBigArray()

    # profile("Slow Lookup"):
    #     for(__ := 0..1000):
    #         option. BigNestedMap[0][0]
    
    # # Fast
    # var BetterBigNestedMap : [int]big_array(logic) = map{}
    # option. set BetterBigNestedMap[0] = big_array(logic){Array := SomeBigArray}

    # profile("Fast Lookup"):
    #     for(__ := 0..1000):
    #         option. BetterBigNestedMap[0].Get[0]

    #####################################################
    ################ LAGGY REPROS #######################
    #####################################################

    # Slow
    var BigNestedMap : [][int]logic = array{MakeBigMap()}

    profile("Slow Lookup"): # 500ms
        for(__ := 0..1000):
            option. BigNestedMap[0][0]
    
    # Fast
    var BetterBigNestedMap : []big_map(logic) = array{big_map(logic){Map := MakeBigMap()}}

    profile("Fast Lookup"): # 5ms
        for(__ := 0..1000):
            option. BetterBigNestedMap[0].Get[0]

    # # Slow
    # var BigNestedMap : [int][int]logic = map{}
    # option. set BigNestedMap[0] = MakeBigMap()

    # profile("Slow Lookup"):
    #     for(__ := 0..1000):
    #         option. BigNestedMap[0][0]
    
    # # Fast
    # var BetterBigNestedMap : [int]big_map(logic) = map{}
    # option. set BetterBigNestedMap[0] = big_map(logic){Map := MakeBigMap()}

    # profile("Fast Lookup"):
    #     for(__ := 0..1000):
    #         option. BetterBigNestedMap[0].Get[0]

Please select what you are reporting on:

Verse

What Type of Bug are you experiencing?

Stability

Steps to Reproduce

See repro

Expected Result

Nested lookups shouldn’t pass anything by copy (?)

Observed Result

Nested lookups pass the whole map by copy (?)

Platform(s)

PC

2

FORT-1148028 has been created and its status is ‘Unconfirmed’. This is now in a queue to be reproduced and confirmed.

3

Just did the same with BigNestedMap[0].Length the cost is 250x after storing the last known Length in the custom big_map container