puzpuzpuz / xsync

Concurrent data structures for Go
Apache License 2.0
1.13k stars 40 forks source link

LoadOrCompute should document intended per-key behavior #116

Closed pnegahdar closed 11 months ago

pnegahdar commented 11 months ago

I was wondering if xsync.MapOf holds fine grained locks (per key) on LoadOrCompute(). The documentation doesn't say much about how the function is expected to behave. e.g. would LoadOrCompute('keyA', slowInitializer(a)) block out LoadOrCompute('keyB', slowinitializer(b))?

Wrote a quick test for it:

package main

import (
    "github.com/puzpuzpuz/xsync/v3"
    "sync"
    "time"
)

func main() {
    testM := xsync.NewMapOf[string, int]()
    wg := sync.WaitGroup{}
    wg.Add(3)
    go func() {
        value, loaded := testM.LoadOrCompute("key-one", func() int {
            println("INNER 1 ran")
            time.Sleep(1 * time.Second)
            return 1
        })
        println("FIRST LOADED", loaded, value)
        wg.Done()
    }()
    go func() {
        time.Sleep(500 * time.Millisecond)
        value, loaded := testM.LoadOrCompute("key-one", func() int {
            println("INNER 2 ran")
            time.Sleep(1 * time.Second)
            return 2
        })
        println("SECOND LOADED", loaded, value)
        wg.Done()
    }()

    go func() {
        time.Sleep(100 * time.Millisecond)
        value, loaded := testM.LoadOrCompute("key-two", func() int {
            println("INNER 3 ran")
            time.Sleep(1 * time.Second)
            return 3
        })
        println("THIRD LOADED", loaded, value)
        wg.Done()
    }()

    wg.Wait()

}

Output is:

INNER 1 ran
INNER 3 ran
FIRST LOADED false 1
SECOND LOADED true 1
THIRD LOADED false 3

I expected the third go routine (operating on key-two) not to get blocked by the initializers for the other keys. Reading the code, I guess it makes sense that it does get blocked.

1) Is there a better way to achieve what I want to achieve ? I was hoping I'd avoid making my own map of sync.Once's

2) Would be helpful to clarify this behavior in the docs

pnegahdar commented 11 months ago

Error in my code, sorry!

puzpuzpuz commented 11 months ago

Glad that you found the solution.

The documentation doesn't say much about how the function is expected to behave. e.g. would LoadOrCompute('keyA', slowInitializer(a)) block out LoadOrCompute('keyB', slowinitializer(b))?

When Compute path of the LoadOrCompute method kicks in, it locks the hash table bucket holding keyA. So, if keyB's hash code has the same lower bits as keyA's one, they will be stored in the same bucket and LoadOrCompute('keyB', slowinitializer(b)) would have to wait until Compute on keyA finishes.

On the other hand, the number of buckets starts with 32 on an empty map and grows as the power of 2. In practice it means that a map has quite many buckets which lowers the chance of bucket collisions for Compute calls.

pnegahdar commented 11 months ago

Thanks for the information. Yeah I'm using the map as a "room" table for a chat like server (with a blocking initializer). The behavior of the locked-if-same-bucket is unreliable for these types of cases, I think the function should probably be clarified that it behaves that way (and that its dependent on the hash/bucket palcement). I would have probably been bitten by this if I hadn't dug in deeper.

I ended up writing a OnceMap type thing that uses singleflight to guard the initializer:

package utils

import (
    "github.com/puzpuzpuz/xsync/v3"
    "golang.org/x/sync/singleflight"
)

type OnceMap[T any] struct {
    dat   *xsync.MapOf[string, T]
    group singleflight.Group
}

func (o *OnceMap[T]) LoadOrCompute(key string, fn func() (T, error)) (T, error) {
    // Check cache
    value, found := o.dat.Load(key)
    if found {
        return value, nil
    }
    _, err, _ := o.group.Do(key, func() (interface{}, error) {
        // try again
        if _, found := o.dat.Load(key); found {
            return nil, nil
        }
        // compute
        data, innerErr := fn()
        if innerErr == nil {
            o.dat.Store(key, data)
        }
        return nil, innerErr
    })
    value, _ = o.dat.Load(key)
    return value, err
}

func NewOnceMap[T any]() *OnceMap[T] {
    return &OnceMap[T]{
        dat:   xsync.NewMapOf[string, T](),
        group: singleflight.Group{},
    }
}
puzpuzpuz commented 11 months ago

That's a good input. I'll update the godoc, so that the locking behavior is clear.