[wip]fix: zero value may cause incorrect length

[godruoyi]

Description

fix #17

but it still not work with string or something else like below:

func TestGetLengthWithString(t *testing.T) {
    cache := NewTTLCache[string, string](1024)

    for i := 0; i < 1024; i++ {
        s := fmt.Sprintf("hello-%d", i)
        cache.Set(s, s, time.Hour)
    }

    if got, want := cache.Len(), 1024; got != want {
        t.Fatalf("bad cache length, got %v, want %v", got, want)
    }
}

//     ttl_cache_test.go:427: bad cache length, got 827, want 1024

@phuslu any suggestion on this? thanks.

[godruoyi]

the CI failed, that proves that my PR didn't get to the root cause and I still don't know why it happened.

[phuslu]

Thanks! But I'm still thinking about alternatives -- Adding an extra field hit is a performance hit (cpu cache friendless) current implementation.

[godruoyi]

Yeah, it's not a good solution and doesn't fix the problem, so I'll look for another way.

[godruoyi]

hi @phuslu I think we still need to add a field for ttlnode/lrunode to identify when the node value was set, otherwise it's hard for us to deal with zero value. The problem now is that the zero values cause the cache length to be incorrectly, as in the example below.

func TestZeroValueCacheLength(t *testing.T) {
    cache := NewTTLCache[int, int](128, WithShards[int, int](1))

    cache.Set(0, 0, time.Hour)
    cache.Set(1, 1, time.Hour)

    if got, want := cache.Len(), 2; got != want {
        t.Fatalf("curent cache length %v should be %v", got, want)
    }
}

//     ttl_cache_test.go:83: curent cache length 1 should be 2

The reason for this problem is that we delete the zero value when setting a new value, see the code below:

if key != node.key {
    s.tableDelete(uint32(s.tableHasher(noescape(unsafe.Pointer(&node.key)), s.tableSeed)), node.key)
}

// 1. set 0  -> ok
// 2. set 1   -> delete 0
// then the cache length will be 1

So my suggestion is to add a field like hit for both ttlnode/lrunode, we can set it to uint32 or uint64 type, which can better utilize the cpu cache, what do you think?

type ttlnode[K comparable, V any] struct {
    key     K
    expires uint32
    next    uint32
    prev    uint32
    ttl     uint32
    hit     uint32
    value   V
}

[godruoyi]

hey @phuslu any suggestion pls, thank you.

[phuslu]

Sorry reply late, because this is a dilemma in my view, so I’m not too keen on fixing it.

If we prioritize performance, I’m afraid we’ll have to tolerate it—in other words, avoid using "zero-value" as the key. If we prioritize correctness, we could attempt a fix without adding extra space, such as reusing the highest bit of ttl as a hit boolean.

I’m afraid there will still be a performance impact no matter how I address this issue.

[godruoyi]

Thanks for your reply, how are about to using *Key? so that we don't need to add anything.

struct ttlnode { key *Key }

[godruoyi]

move to #24