Slow SPOP command due to re-sorting

[dzvancuks]

I'm using github.com/alicebob/miniredis/v2 v2.21.0 for testing redis in UT. And I need to check code that contains SPOP call that retrieves multiple members. It seems that there is an issue with tests are running very slow, but on live Redis there are no problems. As it turns out issue is in slow SPOP handling in MiniRedis.

To reproduce issue run the following test:

import (
    "github.com/alicebob/miniredis/v2"
    "github.com/go-redis/redis/v8"
    "github.com/stretchr/testify/assert"
)
func Test_MR(t *testing.T) {
    assert := assert.New(t)
    mr := miniredis.RunT(t)
    client := redis.NewClient(&redis.Options{
        Addr: mr.Addr(),
    })

    key := "test"
    items := 10000 // play around with this variable

    arr := []interface{}{}
    for i := 0; i < items; i++ {
        arr = append(arr, i)
    }

    client.SAdd(context.TODO(), key, arr)
    _, err := client.SPopN(context.TODO(), key, int64(items)).Result()
    assert.NoError(err)
}

Then execute test with tracing go test -timeout 30s -run ^Test_MR$ <package name where this test is located> -trace trace.out. After that run trace analysis tool go tool trace trace.out

In traces you will see that MiniRedis is the one that takes almost all CPU resources. It tries to sort slice on every item removal:

sort.pdqsort:114
--
sort.pdqsort:125
sort.pdqsort:125
sort.Sort:48
sort.Strings:164
github.com/alicebob/miniredis/v2.(*RedisDB).setMembers:297
github.com/alicebob/miniredis/v2.(*Miniredis).cmdSpop.func1:403
github.com/alicebob/miniredis/v2.withTx:92
github.com/alicebob/miniredis/v2.(*Miniredis).cmdSpop:384
...

This are the following code lines: https://github.com/alicebob/miniredis/blob/fb75409cf5738c26fecd5e8a23936151a30c7c11/cmd_set.go#L404 and https://github.com/alicebob/miniredis/blob/fb75409cf5738c26fecd5e8a23936151a30c7c11/db.go#L297

My proposal is to use golang's map for set storage. Or continue to use slices and optimize multiple random set member removal.

[alicebob]

Hi,

thanks for your issue.

For the spop (which takes a random one), it doesn't make sense to sort the list, so we could try just skipping the sort in that case (other cases sorting is nice to keep things predictable). I'll give it a try in a few days, or feel free to open a PR. I can't promise that'll fix everything, and there's also a limit how complicated I want to make miniredis in general.

[alicebob]

The linked PR makes the test go from 8 seconds to 0.017 seconds. The set is already a map internally, btw. It uses a list to pick a random element.