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

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

4

Issue also occurs with weak_map(agent, <some_map>) and weak_map(session, <some_map>) which is REALLY unfortunate since you can’t iterate over them in order to clean up a key (weak_map(agent) hits the hardest here).

It’s less unfortunate if weak_map(agent) are not handled the same way weak_map(player) are (as a global weak_map and/or a nested one). I couldn’t try adding 1k players on my map but could repro with 50 participant agents (which is easy to get in a real session if the weak_map keys are never removed)

6

Hello @im_a_lama this bug is going to be closed/backlogged due to the fact that this should be resolved when we ship the New VM this year.

1 Like
7

FORT-1148028 has been ‘Closed’. This is working as intended by design.