To further explain why you want to use an AsyncLazy (or Lazy for synchronous programming) when working with ConcurrentDictionary I find this article to be helpful: https://andrewlock.net/making-getoradd-on-concurrentdictiona...

- if the promise never becomes determined (eg bug, async exception) your app will wait forever

- if the promise has high tail latency things can be bad

- if the language eagerly binds on determined promises (ie it doesn’t schedule your .then function) you can get weird semantic bugs.

- changing the keys of the table incrementally instead of just using for memoisation can be really messy

Philosophically, the main problem is that promise caches are a primary enabler of the whole cache anti-pattern situation. People make the mistake of thinking that 'dynamic programming' means memoization and 'memoization' means caching. "Everything you said is wrong." Trying to explain this to people has been a recurring challenge, because it's such a common, shallow but strongly-held misunderstanding.

Youtube recently suggested this video to me, which does a pretty good job of explaining beginning and intermediate DP:

https://www.youtube.com/watch?v=oBt53YbR9Kk

What I love most about this video is that it introduces memoization about 10 minutes in, but by 20% of the way through it has already abandoned it for something better: tabulation. Tabulation is an interative traversal of the problem that gathers the important data not only in one place but within a single stack frame. It telegraphs a information architecture, while recursive calls represent emergent behavior. The reliance on cache to function not only obscures the information architecture, it does so by introducing global shared state. Global shared state and emergent behavior are both poison to the long-term health of a project, and here we have a single data structure that represents both in spades.

We are supposed to be fighting accidental coupling, and especially global variables, not engaging in word games to hide what we are doing.

So I think my answer to OP's question is 'tabulation', which is part data structure and part algorithm.

I modeled mine on the Django ASGI reference library's server implementation, which uses the data structure for maintaining references to stateful event consumers. Exception handling is done with a pre-scheduled long-running coroutine that looks at the map.

I'm curious about your second point -- why exactly do things get bad with high tail latency? Is it only a weakness of the data structure when used for caching? I'm having trouble picturing that.

What would be an example of this? If the promise has been determined, why not just immediately run the .then function?

In Javascript

    f1();
    p.then(f3);
    f2();

By the way, lazy evaluation is the one that offers no guarantees about when your code will be executed. If you can delay the execution, it's not lazy.

Wikipedia states it as: "When using delayed evaluation, an expression is not evaluated as soon as it gets bound to a variable, but when the evaluator is forced to produce the expression's value."

So if evaluation begins effectively at the time the promise is issued, not at the time the promise is awaited, then I would not call that lazy evaluation, and what hn_throwaway_99 said sounds correct to me.

Is my rusty old PL understanding wrong?

Correct.

You've got it right, GP comment has it wrong.

Lazy does not simply mean "evaluated later". From what I understand, in JS, if you call an async function without `await`, it essentially gets added to a queue of functions to execute. Once the calling function stack completes, the async function will be executed.

A queue of functions to execute does not constitute "lazy evaluation" on its own.

“In programming language theory, lazy evaluation, or call-by-need,[1] is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing).”

Haskell would be an apt example here.

To me it seems to be the same thing. Replace result with int and I literally do not see a problem with the first one.

Also why is a mutex or lock needed for Result in javascript? As far as I know... In a single threaded application, mutexes and locks are only needed for memory operations on two or more results.

With a single value, say an int, within javascript you are completely safe in terms of concurrent access. Only 2 more more variables can cause a race condition. Or am I wrong here?

--edit:

Thanks for the replies. I see now. The mutex concept is not around memory access or memory safety. It's solely around the computation itself. When the Promise is "pending". It has nothing to do with safety. The parent did mention this, but I completely glossed over it.

Pretty much every single asynchronous operation other than some `Promise.resolve(foo)` where foo is a static value can fail. Reading from the file system, calling an api, connecting to some database, etc.

If the original promise fails you're gonna return a cached failure.

Mind you, I'm not stating this might be completely useless, but at the end of the day you will be forced to add code logic to check all of those asynchronous computation results which will eventually outweight the cost of only saving the resolved data.

This is usually a good thing, and even in cases where it isn't, it's often a worthwhile trade-off.

In the common case a failure will either be persistent, or - if load/traffic related - will benefit from a reduction in requests (waiting a while to try again). In both of these cases, where your first key request fails, you want the immediately-following cases to fail fast: "caching" the promise caches the failure for the duration of one request (presumably the cache is emptied once the promise resolves, allowing subsequent key accesses to retry).

The less common case where the above isn't true is where you have very unstable key access (frequent one-off failures). In those cases you might want a cache miss on the second key request, but successful key retrieval usually isn't as critical in such systems which makes the trade off very worthwhile.

In the scenario where that's an issue, you would need to add (extremely trivial 3-5 lines) logic to handle retrying a cached failure. The underlying data structure would continue to be a promise map.

In many cases, another near-in-time request would also fail, so returning a cached failure rather than failing separately is probably a good idea (if you need retry logic, you do it within the promise, and you still need only a single instance.)

(If you are in a system with async and parallel computation both available, you can also use this for expensive to compute pure functions of the key.)

It's unlikely that always doing two is going to be more successful than just trying once and dealing with failure

When the VERY FIRST ASYNC operation is inflight the cache is immediately loaded with a Promise, which blocks all other calls while the FIRST async operation is in flight. This is only relevant to the very FIRST call. That's it. After that the promise is pointless.

As for the Promise failure you can just think of that as equivalent of the value not existing in the cache. The logic should interpret the promise this way.

A practical example of this was an analytics dashboard I was working on years ago -- the UI would trigger a few waves of requests as parts of it loaded (batching was used, but would not be used across the entire page). It was likely that for a given load, there would be four or more of these requests in-flight at once. Each request needed the result of an expensive (~3s+) query and computation. Promise caching allowed operations past the first to trivially reuse the cached promise.

There are certainly other approaches that can be taken, but this works very well as a mostly-drop-in replacement for a traditional cache that shouldn't cause much of a ripple to the codebase.

You have to invalidate/bust the cache when a failure is returned (which is racy, but since cache busting is on the sad path it's a fine place to protect with a plain ol' mutex, assuming you even have real parallelism/preemption in the mix).

Alternatively you can cache promises to functions that will never return failure and will instead internally retry until they succeed. This approach generalizes less well to arbitrary promises, but is more friendly to implementing the custom back off/retry scheme of your choice.

If I understand the pattern correctly, it is to avoid multiple asynchronous requests to a resource that has yet to be cached.

It seems like an optimization to prevent lots of downstream requests that occur in rapid succession before the first request would have finished. I'd also suspect that the entry would be removed from the map on failure.

If you store the promise, then not only does the second attempt know that it doesn't need to make a new request, but it can also await on the promise it finds in the map directly.

Under Javascript, The behavior induced by this pattern is EXACTLY equivalent to that of CACHING the result directly and a BLOCKING call. The pattern is completely pointless if you view it from that angle. Might as well use blocking calls and a regular cache rather then async calls and cached promises.

So then the benefit of this pattern is essentially it's a way for you to turn your async functions into cached non-async functions.

Is this general intuition correct?

--edit: It's not correct. Different async functions will still be in parallel. It's only all blocking and serial under the multiple calls to the SAME function.

1/ Have a higher level source of truth that will fetch it once from your repository (how does it know it needs to fetch? How is cache handled ?) and distribute it to those three elements. Complex, makes components more independent but also more dumb. It's fine to have pure elements, but sometimes you just want to write <UserInfoHeader/> and let it handle its stuff.

2/ Your repository keeps this Map<Key, Promise<T>>, and every time you call getUserInfo(), it checks the map at key "userinfo" and either return the promise (which might be ongoing, or already resolved) or see that it's not there and do the call, writing the promise back into the map. This way, your three components can just call getUserInfo() without giving a damn about any other ones. The first one that calls it pre-resolves it for others.

As to why a promise instead of just the raw result: one can potentially return null (and you need to call again later to refresh, or straight up blocks during the entire call), the other one just gives you back promises and you can just listen to them and update your UI whenever it's ready (which might be in 5 seconds, or right now because the promise has already been resolved)

It's a bad implementation of a cached repository (because it ignores TTL and invalidation as well as many problems that need to be handled) that any junior developer could figure out (so it's everything but obscure), but sometimes, eh, you don't need much more.

So if you get two requests for the computation that computes Result in close succession the Map doesn't have the result in place for the second call and as a result you get no caching effect and make 2 expensive requests.

By caching the Promise instead the second request is caught by the cache and simply awaits the Promise resolving so now you only get 1 expensive request.

Later on I switched to using react-query which has something like this built-in, it's been really good.

> you avoid computing/fetching the same value twice

But this problem comes up in reverse proxies too. In Nginx, you can set the `proxy_cache_lock`[0] directive to achieve the same effect (avoiding double requests).

[0]: https://nginx.org/en/docs/http/ngx_http_proxy_module.html#pr...

[0]: https://en.wikipedia.org/wiki/Cache_stampede

I hit the API's rate limiter when the workers invalidated their cache, even though I staggered the lifetime of the cache keys for each replicated instance. This is how I found out how many Cloudflare workers run on a single edge instance. Hint: It's many.

Didn't know it had a name. I'm delighted, thanks!

[1] https://codesandbox.io/s/recursing-glitter-h4c83u?file=/src/...

Browsers probably used to squeeze layouting and such things in when the event loop completed an iteration or became idle. However nowadays it's entirely possible that have, or will have, browsers that do even work in parallel while the javascript event loop is still running, possibly even beginning to paint while javascript is still running synchronously (haven't seen that yet).

I've seen instances where browsers seem to be like "nah, I'll render this part later" and only would render some parts of the page, but certain layers (scrolling containers) would not be filled on the first paint - despite everything being changed in one synchronous operation!* And I've seen them do that at least 5 years ago.

It seems to me the situation is complicated.

* There was a loading overlay and a list being filled with data (possibly thousands of elements). The loading overlay would be removed after the list was filled, revealing it. What often happened was that the overlay would disappear, but the list still looking empty for a frame or two.

https://github.com/ben-manes/caffeine cache does something similar by caching the future that gets returned on look-ups if the value is still being computed

    readonly foo = bar.pipe(
        switchMap(v => doTask(v)),
        shareReplay(1),
    );

    readonly foo = bar.pipe(
        map(v => doTask(v),
        shareReplay(1),
        switchMap(v => v),
    );

    async someEventHandler(userInput) {
        this.bar.next(userInput);
        const result = await firstValueFrom(this.foo);
        …
    }

How bad is this? Should I switch to Promise.all instead?

Promise.all runs them all simultaneously and waits until they are all complete. It returns an array of results in the same order as the calls, so it's usually pretty straightforward to use.

Both approaches have a purpose, so it's not like you "should" strictly use one. But you should be aware of both and be able to use the one that fits the need.

- as soon as any of them resolve (any)

- when all of them resolve (all)

- resolve each in order (for)

Just gotta be careful with memory leaks, so (for a TS example) you might want to do something like this:

    const promiseMap<key, Promise<any>> = new Map();

    async function keyedDebounce<R>(key: string, fn: () => R) {
      const existingPromise = promiseMap.get(key);
      if (existingPromise) return existingPromise;

      const promise = new Promise(async (resolve) => {
        const result = await fn(); // ignore lack of error handling

        // avoid memory leak by cleaning up
        promiseMap.delete(key); 

        // this will call the .then or awaited promises everywhere
        resolve(result); 
      });

      promiseMap.set(key, promise);

      return promise;
    }

  const promiseMap<key, Promise<any>> = new Map();

  async function keyedDebounce<R>(key: string, fn: () => R) {
    const existingPromise = promiseMap.get(key);
    if (existingPromise) return existingPromise;
  
    const promise = fn().then(result => {
      promiseMap.delete(key);
  
      return result;
    });
  
    promiseMap.set(key, promise);
  
    return promise;
  }

Could you explain why that's necessary? (sorry probs a stupid question)

A purpose of this might be, let's say you rebuild some structure very frequently, like hundreds of times per second or whatever. You can call this function for a given key as many times as you want while that async process is executing, and it will only execute it once, always returning the same promise.

I’m not entirely sure of the use of this pattern where your using a map and deleting the keys as you go - seems like you’d end up doing more work kinda randomly depending on how the keys were added. I’d just relive the whole map when I was done with it.

OP is intentionally caching results of, presumably, expensive computations or network calls. It's a cache. There is no memory leak. OP just did not detail how cache invalidation/replacement happens. The 2nd comment adds a rather rudimentary mechanism of removing items from cache as soon as they are ready. You get the benefit of batching requests that occur before the resolve, but you get the downside of requests coming in right after the resolve hitting the expensive process again. Requests don't neatly line up at the door and stop coming in as soon as your database query returns.

Typically you would use an LRU mechanism. All caches (memcached, redis, etc.) have a memory limit (whether fixed or unbounded, i.e. all RAM) and a cache replacement policy.

I've mostly used this overall pattern with something like Dataloader, where you throw away the entire cache on every request, so the GC problem doesn't crop up.

This might be relevant to this exact pattern

  const getThing = (async function (arg1, arg2) {
    console.log({ arg1, arg2 });
    return arg1 + (arg2 || 0);
  }).memo();

  console.log(await getThing(1)); // New promise
  console.log(await getThing(2)); // New promise
  console.log(await getThing(1)); // Returns promise from earlier

yes, in fact this is more like a pattern than an actual data structure, since you might as well replace it with a list of futures. And a comparison between future based concurrency and thread based parallelism is like apples to oranges.

But it isn't surprising that this pattern ended up at the top since it is what the users of this site would be most familiar with.

Didn't know what to call it but PromiseMaps is nice name for it.

Why would that be true?

https://docs.python.org/3/library/asyncio-future.html#asynci...

    private var tasksDictionary: Dictionary<String, Task<Data, Error>>

    func getData(at urlString: String) async throws -> Data {
        if let currentTask = tasksDictionary[urlString] {
            return await currentTask.value
        }
        let currentTask = Task { 
           return try await URLSession.shared.data(from: URL(string:urlString)!) 
        }
        tasksDictionary[urlString] = currentTask
        let result = await currentTask.value
        tasksDictionary[urlString] = nil
        return result
    }

I guess making it nil can be also used if you don't wanna make the same request when there is one already in flight, in case you have a 403 error and need to request a refresh token, you don't wanna make two simultaneous requests, but you also don't wanna catch it indefinitely either.

I say expensive because even in a data center, an RPC is going to take on the order of 1ms. The round-trip from a client like a browser is much greater especially where the client (if this is what you meant by "client") has a poor internet connection.

Therefore this pattern is usually done inside of an API server in the data-center. Additional benefits of the server side approach is that an API server can better control the cache keys (you could put the API server "build number" in the cache key so you can do rolling updates of your jobs), TTL, etc. Also, you don't want a rogue computer you don't control to directly talk to a shared cache since a rogue computer could put dangerous values into your cache, remove elements from the cache they shouldn't, etc.

If you get 10 requests to fire function lookUpSomethingThatTakesAWhile(id) that returns a promise, rather than firing off 10 promises, you fire it off once, look up the ID in your map for the next nine, and return that same promise for the next 9.

It is definitely true that Promise is a data type that _could_ admit a monad instance. It has:

- a data type M a which is Promise a

- a function pure with the signature a => M a, which is x => Promise.resolve(x)

- a bind function with the signature M a => a => M b => M b which is essentialy `then`

But a monad requires three properties to hold true: Right identity, Left identity and associativity. Right identity holds for every function `f: a => M b`, but left identity and associativity do not hold.

do you mean

    setmetatable({}, {__index = function(tab, key)
          local co = coroutine.running()
          uv.read(fd, function(err, result)
               tab[key] = result
               return coroutine.resume(result)
            end)
          return coroutine.yield()
      end })