gnovm/pkg/gnolang: the use of maps for Attributes.data causes a huge memory bloat and lots of calls to internal/runtime/maps.newarray along with lots of garbage collection

[odeke-em]

To reduce memory bloat of the gnovm I've been examining design patterns and one struct out for gnolang.Attributes

gno/gnovm/pkg/gnolang/nodes.go

Lines 164 to 169 in beb48e7

	type Attributes struct {
	Line int
	Column int
	Label Name
	data map[GnoAttribute]interface{} // not persisted
	}

and see

gno/gnovm/pkg/gnolang/nodes.go

Lines 206 to 211 in beb48e7

	func (attr *Attributes) SetAttribute(key GnoAttribute, value interface{}) {
	if attr.data == nil {
	attr.data = make(map[GnoAttribute]interface{})
	}
	attr.data[key] = value
	}

Seems like Attributes needs fast lookups hence opted for O(1) lookups with maps. However, it seems like very few attributes are set per Attributes object and with the use of maps, a ton of memory bloat which is visible when I profile the code from Gno libraries code in #3435.

Top 10 memory consumers

Showing nodes accounting for 92.90MB, 83.87% of 110.76MB total
Dropped 51 nodes (cum <= 0.55MB)
Showing top 10 nodes out of 123
      flat  flat%   sum%        cum   cum%
   47.37MB 42.77% 42.77%    47.37MB 42.77%  internal/runtime/maps.newarray
   10.50MB  9.48% 52.25%    10.50MB  9.48%  internal/runtime/maps.NewEmptyMap
       8MB  7.22% 59.47%        8MB  7.22%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*StaticBlock).InitStaticBlock
    7.51MB  6.78% 66.25%    13.03MB 11.76%  github.com/gnolang/gno/gnovm/pkg/gnolang.Go2Gno
    6.02MB  5.43% 71.68%    10.73MB  9.68%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*defaultStore).SetObject
       4MB  3.61% 75.29%        4MB  3.61%  github.com/gnolang/gno/gnovm/pkg/gnolang.NewBlock
    3.47MB  3.13% 78.43%     3.47MB  3.13%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*Allocator).NewDataArray
    2.52MB  2.27% 80.70%     3.52MB  3.18%  github.com/gnolang/gno/gnovm/pkg/gnolang.toKeyValueExprs
       2MB  1.81% 82.51%        2MB  1.81%  runtime.allocm
    1.51MB  1.36% 83.87%     1.51MB  1.36%  runtime/pprof.(*profMap).lookup

and

Showing nodes accounting for 47.37MB, 42.77% of 110.76MB total
----------------------------------------------------------+-------------
      flat  flat%   sum%        cum   cum%   calls calls% + context 	 	 
----------------------------------------------------------+-------------
                                           47.37MB   100% |   internal/runtime/maps.newGroups
   47.37MB 42.77% 42.77%    47.37MB 42.77%                | internal/runtime/maps.newarray
----------------------------------------------------------+-------------
                                           32.01MB 78.05% |   github.com/gnolang/gno/gnovm/pkg/gnolang.preprocess1.func1
                                               7MB 17.07% |   github.com/gnolang/gno/gnovm/pkg/gnolang.evalConst (inline)
                                            1.50MB  3.66% |   github.com/gnolang/gno/gnovm/pkg/gnolang.constType (inline)
                                            0.50MB  1.22% |   github.com/gnolang/gno/gnovm/pkg/gnolang.tryPredefine.func1
         0     0% 42.77%    41.01MB 37.03%                | github.com/gnolang/gno/gnovm/pkg/gnolang.(*Attributes).SetAttribute
                                           41.01MB   100% |   runtime.mapassign_faststr
----------------------------------------------------------+-------------
                                            4.50MB   100% |   github.com/gnolang/gno/gnovm/pkg/test.(*TestOptions).runTestFiles
         0     0% 42.77%     4.50MB  4.06%                | github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).RunFiles
                                            4.50MB   100% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runFileDecls
----------------------------------------------------------+-------------
                                           42.86MB   100% |   github.com/gnolang/gno/gnovm/pkg/test.loadStdlib (inline)
         0     0% 42.77%    42.86MB 38.70%                | github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).RunMemPackageWithOverrides
                                           42.86MB   100% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runMemPackage
----------------------------------------------------------+-------------
                                           42.86MB 90.50% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runMemPackage
                                            4.50MB  9.50% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).RunFiles
         0     0% 42.77%    47.37MB 42.77%                | github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runFileDecls
                                           41.86MB 88.39% |   github.com/gnolang/gno/gnovm/pkg/gnolang.PredefineFileSet
                                           21.51MB 45.40% |   github.com/gnolang/gno/gnovm/pkg/gnolang.Preprocess
                                            2.14MB  4.53% |   github.com/gnolang/gno/gnovm/pkg/gnolang.SaveBlockNodes
----------------------------------------------------------+-------------
                                           42.86MB   100% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).RunMemPackageWithOverrides
         0     0% 42.77%    42.86MB 38.70%                | github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runMemPackage
                                           42.86MB   100% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runFileDecls
                                            4.21MB  9.82% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).saveNewPackageValuesAndTypes
----------------------------------------------------------+-------------
                                            4.21MB   100% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).runMemPackage
         0     0% 42.77%     4.21MB  3.80%                | github.com/gnolang/gno/gnovm/pkg/gnolang.(*Machine).saveNewPackageValuesAndTypes
                                            4.21MB   100% |   github.com/gnolang/gno/gnovm/pkg/gnolang.(*Realm).FinalizeRealmTransaction

42.77% of the memory bloat spent for the top 10!

Remedies

I believe that we got hit here by innocent thinking but by a naive design choice that resulted in a premature optimization. Maps should be used only when there are so many attributes, for the most part O(n) linear datastructures+lookups beat O(1) data structures that require lots of memory and greatly affect garbage collection.

diff --git a/gnovm/pkg/gnolang/nodes.go b/gnovm/pkg/gnolang/nodes.go
index 0496d37e..156ac133 100644
--- a/gnovm/pkg/gnolang/nodes.go
+++ b/gnovm/pkg/gnolang/nodes.go
@@ -165,7 +165,7 @@ type Attributes struct {
 	Line   int
 	Column int
 	Label  Name
-	data   map[GnoAttribute]interface{} // not persisted
+	data   []*attrKV // not persisted
 }
 
 func (attr *Attributes) GetLine() int {
@@ -193,28 +193,62 @@ func (attr *Attributes) SetLabel(label Name) {
 }
 
 func (attr *Attributes) HasAttribute(key GnoAttribute) bool {
-	_, ok := attr.data[key]
+	_, _, ok := attr.getAttribute(key)
 	return ok
 }
 
 // GnoAttribute must not be user provided / arbitrary,
 // otherwise will create potential exploits.
 func (attr *Attributes) GetAttribute(key GnoAttribute) interface{} {
-	return attr.data[key]
+	val, _, _ := attr.getAttribute(key)
+	return val
+}
+
+func (attr *Attributes) getAttribute(key GnoAttribute) (any, int, bool) {
+	for i, kv := range attr.data {
+		if kv.key == key {
+			return kv.value, i, true
+		}
+	}
+	return nil, -1, false
+}
+
+type attrKV struct {
+	key   GnoAttribute
+	value any
 }
 
 func (attr *Attributes) SetAttribute(key GnoAttribute, value interface{}) {
 	if attr.data == nil {
-		attr.data = make(map[GnoAttribute]interface{})
+		attr.data = make([]*attrKV, 0, 4)
 	}
-	attr.data[key] = value
+
+	for _, kv := range attr.data {
+		if kv.key == key {
+			kv.value = value
+			return
+		}
+	}
+
+	attr.data = append(attr.data, &attrKV{key, value})
 }
 
 func (attr *Attributes) DelAttribute(key GnoAttribute) {
 	if debug && attr.data == nil {
 		panic("should not happen, attribute is expected to be non-empty.")
 	}
-	delete(attr.data, key)
+	_, index, _ := attr.getAttribute(key)
+	if index < 0 {
+		return
+	}
+
+	if index == 0 {
+		attr.data = attr.data[1:]
+	} else if index == len(attr.data)-1 {
+		attr.data = attr.data[:len(attr.data)-1]
+	} else {
+		attr.data = append(attr.data[:index], attr.data[index+1:]...)
+	}
 }
 
 // ----------------------------------------

Preliminary test

When I apply the wisdom, turning Attributes.data into a slice and then using a loop to find values, we get a massive reduction in RAM usage by more than 30% and map creation is no longer in the top 5: it drops from 47.37MB down to 2.50MB! per

Showing nodes accounting for 61.99MB, 73.12% of 84.78MB total
Showing top 10 nodes out of 196
      flat  flat%   sum%        cum   cum%
   19.50MB 23.00% 23.00%    19.50MB 23.00%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*Attributes).SetAttribute
   12.52MB 14.76% 37.77%    18.02MB 21.26%  github.com/gnolang/gno/gnovm/pkg/gnolang.Go2Gno
    7.58MB  8.94% 46.70%     9.15MB 10.79%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*defaultStore).SetObject
       5MB  5.90% 52.60%        5MB  5.90%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*StaticBlock).InitStaticBlock
    3.47MB  4.09% 56.69%     3.47MB  4.09%  github.com/gnolang/gno/gnovm/pkg/gnolang.(*Allocator).NewDataArray
       3MB  3.54% 60.24%        3MB  3.54%  github.com/gnolang/gno/gnovm/pkg/gnolang.NewBlock
       3MB  3.54% 63.77%        3MB  3.54%  github.com/gnolang/gno/gnovm/pkg/gnolang.Nx (inline)
    2.77MB  3.26% 67.04%     2.77MB  3.26%  bytes.growSlice
    2.65MB  3.12% 70.16%     2.65MB  3.12%  internal/runtime/maps.newarray
    2.50MB  2.95% 73.12%     2.50MB  2.95%  runtime.allocm

Kindly cc-ing @notJoon @jaekwon @thehowl @petar-dambovaliev