Data Structure Fee Research

TL;DR

• Tree outer (avl.Tree): O(log N) gas growth — +45% at N=1,000 (TreeMap 1.1M → 2.2M)
• Map outer (map): O(N) gas growth — +1,734% at N=1,000 (MapMap 498K → 9.1M)
• Inner struct ≈ inner map: gas difference < 1%, struct ~7% cheaper on storage
• Inner tree: gas 2x, storage 5.6x — inefficient
• Optimal: TreeStruct (gas 2.2M + storage 333K = total 2.5M ugnot at N=1,000)
• vs current TreeMap: TreeStruct is gas -0.2%, storage -6.6% — practically equivalent

1) Background and Goal

Personal World currently stores world data as avl.Tree → map[string]string. This experiment measures total fees (gas + storage deposit) for 6 alternative outer/inner data structure combinations to identify the optimal storage pattern.

6 combinations tested:

Hypothesis:

• Tree outer = O(log N) gas growth, map outer = O(N) gas growth (full map re-serialization)
• Inner overhead: struct < map < tree

Goals:

• Quantify gas and storage fee differences across combinations
• Determine if map outer is viable at scale or becomes prohibitive
• Identify the most cost-efficient combination for production use

Contract (gno.land/r/akkadia/ds_fee):

package ds_fee
 
import "gno.land/p/nt/avl"
 
type WorldData struct {
	Owner     string
	Name      string
	Slug      string
	SizeID    string
	Size      string
	Seed      string
	Biome     string
	IsVisible string
	Options   string
}
 
var (
	treeTree   = avl.NewTree()                    // avl.Tree → *avl.Tree
	treeMap    = avl.NewTree()                    // avl.Tree → map[string]string
	treeStruct = avl.NewTree()                    // avl.Tree → *WorldData
	mapTree    = make(map[string]*avl.Tree)       // map → *avl.Tree
	mapMap     = make(map[string]map[string]string) // map → map[string]string
	mapStruct  = make(map[string]*WorldData)      // map → *WorldData
)
 
// 6 setters — all share the same signature:
// func Set<Name>(cur realm, key, owner, name, slug, sizeID, size, seed, biome, isVisible, options string)
//
// TreeTree/MapTree: inner avl.Tree with 9 field Set calls
// TreeMap/MapMap:   map[string]string literal with 9 fields
// TreeStruct/MapStruct: &WorldData{...} with 9 fields
 
func GetSize() int { return treeTree.Size() }

2) Test Environment

• Date: 2026-02-09
• Execution: gnodev (local machine)
• Gno RPC: localhost:26657
• Chain ID: dev
• Scripts: bin/gno/research/ds_fee.sh all
• Milestones: 1, 500, 1,000
• Repeat: 3

3) Results

TreeTree

TreeMap

TreeStruct

MapTree

MapMap

MapStruct

4) Analysis

Outer: Tree vs Map

Comparing equivalent inner types to isolate outer structure impact:

• Tree gas grows sub-linearly (O(log N)): only +90% from N=1 to N=1,000
• Map gas grows linearly (O(N)): +1,733% from N=1 to N=1,000 — entire map re-serialized on every write
• Crossover point: Map is cheaper below ~100 entries, Tree wins above that
• Storage: Map is consistently ~2x cheaper (no AVL node overhead)

Inner: Tree vs Map vs Struct

Comparing inner types within Tree outer to isolate inner structure impact:

• Struct vs Map: Gas nearly identical (< 0.2% difference), storage struct is ~6.6% cheaper
• Tree inner: 2x gas, 5.6x storage — each inner avl.Tree stores 9 AVL nodes vs 1 flat object
• Inner tree overhead is dominated by node allocation, not lookup

Total Fee Ranking (at N=1,000)

5) Conclusions

• Outer structure: avl.Tree is clearly superior at scale. Map outer’s O(N) re-serialization makes it 4-5x more expensive at N=1,000 and will only worsen. Map is only viable for very small, bounded collections (< 100 entries).
• Inner structure: *WorldData (struct) and map[string]string are practically equivalent in gas (< 0.2% difference). Struct saves ~7% on storage. Inner *avl.Tree is 2x gas and 6x storage — avoid.
• Optimal combination: TreeStruct (avl.Tree → *WorldData) — lowest total fee at scale.
• Production impact: Current TreeMap is only ~1.1% more expensive than TreeStruct in total fees. Migration is not urgent but worth considering for new contracts.
• Hypothesis confirmed: Tree outer = O(log N) ✓, Map outer = O(N) ✓, Inner struct ≈ map < tree ✓