expandRangeTable should preallocate ret to reduce memory pressure in append loops

[odeke-em]

Noticed by profiling the cosmos-sdk project which uses this code that has a RAM profile of

ROUTINE ======================== pgregory.net/rapid.expandRangeTable in /Users/emmanuelodeke/go/pkg/mod/pgregory.net/rapid@v0.5.3/strings.go
    6.08MB     6.08MB (flat, cum) 32.29% of Total
         .          .    357:func expandRangeTable(t *unicode.RangeTable, key any) []rune {
         .          .    358:   cached, ok := expandedTables.Load(key)
         .          .    359:   if ok {
         .          .    360:       return cached.([]rune)
         .          .    361:   }
         .          .    362:
         .          .    363:   var ret []rune
         .          .    364:   for _, r := range t.R16 {
         .          .    365:       for i := uint32(r.Lo); i <= uint32(r.Hi); i += uint32(r.Stride) {
    2.64MB     2.64MB    366:           ret = append(ret, rune(i))
         .          .    367:       }
         .          .    368:   }
         .          .    369:   for _, r := range t.R32 {
         .          .    370:       for i := uint64(r.Lo); i <= uint64(r.Hi); i += uint64(r.Stride) {
    3.44MB     3.44MB    371:           ret = append(ret, rune(i))
         .          .    372:       }
         .          .    373:   }
         .          .    374:   expandedTables.Store(key, ret)
         .          .    375:
         .          .    376:   return ret

but we can modify expandRangeTable to preallocate ret by

make([]rune, 0, len(t.R16)+len(t.R32))

After

On re-profiling the same code, we now get this profile

ROUTINE ======================== pgregory.net/rapid.expandRangeTable in /Users/emmanuelodeke/go/pkg/mod/pgregory.net/rapid@v0.5.3/strings.go
    4.20MB     4.20MB (flat, cum) 28.40% of Total
         .          .    357:func expandRangeTable(t *unicode.RangeTable, key any) []rune {
         .          .    358:   cached, ok := expandedTables.Load(key)
         .          .    359:   if ok {
         .          .    360:       return cached.([]rune)
         .          .    361:   }
         .          .    362:
         .          .    363:        ret := make([]rune, 0, len(t.R16)+len(t.R32))
         .          .    364:   for _, r := range t.R16 {
         .          .    365:       for i := uint32(r.Lo); i <= uint32(r.Hi); i += uint32(r.Stride) {
  609.50kB   609.50kB    366:           ret = append(ret, rune(i))
         .          .    367:       }
         .          .    368:   }
         .          .    369:   for _, r := range t.R32 {
         .          .    370:       for i := uint64(r.Lo); i <= uint64(r.Hi); i += uint64(r.Stride) {
    3.61MB     3.61MB    371:           ret = append(ret, rune(i))
         .          .    372:       }
         .          .    373:   }
         .          .    374:   expandedTables.Store(key, ret)
         .          .    375:
         .          .    376:   return ret

[flyingmutant]

Good catch! To preallocate the whole thing, we need a couple of loops to calculated the size; I don't think len(t.R16) + len(t.R32) is a good estimation on the number of runes.

expandRangeTable should only be called once for a particular table and then cached forever, that's why I did not bother to preallocate. Does this slow down the tests in your case, or was it just something you have noticed in the profile when troubleshooting other issues?

[odeke-em]

Good to chat with you @flyingmutant and thanks for your work on this package! I noticed it in profiles, I work on security and performance for the Cosmos Network so I focus on ridding as much CPU and RAM usage in profiles; we use simapp (a simulation app) to run a whole bunch of tests and benchmarks and such profiles if they exist in profiles can become a distraction.