interp gives up on sort.Strings but works with sort.Slice

[joeshaw]

A package-level variable whose initializer calls sort.Strings is not evaluated at compile time. The initializer runs at startup instead.

Given this program:

package main

import (
        "runtime"
        "sort"
)

var words = []string{
        "delta", "alpha", "echo", "charlie", "bravo",
        "golf", "foxtrot", "india", "hotel",
}

// table is a package-level variable, so interp normally evaluates build() at
// compile time.
var table = build(words)

func build(w []string) []int32 {
        sorted := append(make([]string, 0, len(w)), w...)
        sort.Strings(sorted)

        t := make([]int32, 4096)
        for i, s := range sorted {
                t[i] = int32(len(s))
        }
        return t
}

func main() {
        var ms runtime.MemStats
        runtime.ReadMemStats(&ms)
        println("TotalAlloc:", int(ms.TotalAlloc))
        println("len:", len(table))
}

The interp phase bails out because of the sort.Strings(sorted) call. Claude tells me it is because of the recursive pdqsort implementation in the standard library. Maybe!

If you swap it out for sort.Slice(sorted, func(i, j int) bool { return sorted[i] < sorted[j] } then it appears to be compiled in.

good  TotalAlloc: 65584
bad   TotalAlloc: 82040

I was able to reproduce this with both TinyGo 0.41.1 and 0.33.0.

[rdon-key]

I dug into this a bit more and found another interp issue along the way.

The sort.Slice case is actually miscompiled rather than working: interp keeps the call at runtime but evaluates the following code using the pre-sort contents of the slice, so the static data ends up wrong. Your program only prints len(table), so it isn't visible there. I opened #5586 for that. Note that this fix makes sort.Slice fall back to runtime evaluation too, so the TotalAlloc difference will go away.

This seems to go a bit deeper than I initially thought, so I'll leave further investigation of #5583 to someone else for now. For the sorting itself, a small custom sort function may be the simplest workaround.