I used to use the MemoryCache in .Net but recently read about a DB using using a linked-list, which only had to check the prefix of the list in \$O(1)\$ complexity, to time values out, as opposed to ln N; the heap-based approach that's default for variable timeout, min-heaps.
I'd appreciate a review of this code; in terms of how optimal it is and if there are obvious mistakes in it, that I'm missing. The general idea is that count(R) >>> count(W).
I considered using ReaderWriterLockSlim in upgradeable mode, but I may very well have two threads with read locks trying to acquire a write upgrade simultaneously in this piece of code, so I decided against. The check of the queue head is supposed to be quick enough to avoid contention around this resource.
This code is intended to be used in a low-latency F# API as part of Logibit Hawk.
I'd also like this code to be non-allocating, besides the single int64 that's the
Instant (x2) and the allocated-outside string reference. Returning Choice-values (allocating) is intentional however, and will be changed to Result in the future.
module Settings = open NodaTime open System.Collections.Generic open System.Collections.Concurrent let private tsem = obj () let private runTimeouts (timeouts: Queue<_>) (cache: ConcurrentDictionary<string, Instant>) (now: Instant) = /// Iterate until the head is due later than now. Tail-recursion needed. let rec iter () = if timeouts.Count = 0 then () else let struct (nonce, timeout) = timeouts.Peek() if timeout > now then () else ignore (timeouts.Dequeue()) ignore (cache.TryRemove nonce) iter () lock tsem iter let nonceValidatorMem (clock: IClock) (keepFor: Duration) = // We will use a queue, because it's O(1) on dequeue/peek and since the duration is a constant for the // life time of this validator, we know the head is due closest in time. let timeouts = Queue<_>() // The cache stores the nonces and when they were added let cache = ConcurrentDictionary<_, _>() fun (nonce: string, ts: Instant) -> let now = clock.GetCurrentInstant() do runTimeouts timeouts cache now // https://docs.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.tryadd?view=netframework-4.7.1 // returns true if the nonce was successfully added if cache.TryAdd (nonce, now) then do lock tsem (fun () -> timeouts.Enqueue (struct (nonce, now + keepFor))) Choice1Of2 () else Choice2Of2 AlreadySeen