9 ms·

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-clas

• acoye 4y ago
  I wonder if Swift's AsyncAwait could be used in such a way.
  • Ryuuke5 4y ago
    Sure it's possible, we need to await for the Task if it already exists on the dictionary, for example we could imagine writing something like this inside an actor to make it threadSafe. 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 }
    • afro88 4y ago
      Great! So much nicer than the Combine (or Rx) version.
    • ninkendo 4y ago
      Hmm, why set `taskDictionary[urlString] = nil` at the bottom there? If the whole point is to cache the result, isn't the point to leave the value there for other requests to pick it up?
      • Ryuuke5 4y ago
        Yup, nice catch, no need to reset it to nil if you wanna keep it in memory indefinitely. 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.
• ralusek 4y ago
  I have written many tools that do something like this, very useful. 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; } So that the promise sticks around for that key while the function is active, but then it clears it so that you're not just building up keys in a map.
  • jdthedisciple 4y ago
    You check for if(promiseMap.get(key)) and in the NO case you do promiseMap.delete(key)? Could you explain why that's necessary? (sorry probs a stupid question)
    • aidos 4y ago
      I’m the no case, the promise is created, and then deleted after the function is resolved. 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.
    • ralusek 4y ago
      So if the promise still exists, that means that there is an active call out for a promise using this key already, so we'll just return it. We know this because when the function that is executing finishes, we delete the promise from the map. 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.
• Cthulhu_ 4y ago
  I didn't know this was a formal design pattern; I do recall having implemented this myself once, as a means to avoid double requests from different components. Later on I switched to using react-query which has something like this built-in, it's been really good.
• idontwantthis 4y ago
  It’s also the clearest and least buggy way to iterate over the results. Map over Await Promise.all(map).
  • unsupp0rted 4y ago
    Partly off-topic, but in JS I tend to avoid iterating over promises with maps because it's always confusing what will/won't work, so I use a basic FOR loop because async/await works in there. How bad is this? Should I switch to Promise.all instead?
    • seedboot 4y ago
      Promise.all/allSettled/etc will allow you to resolve your promises concurrently rather than awaiting each result in the for loop. Depends what your use case is, really.
    • mromnia 4y ago
      Iterating with async/await means you wait for every result before making another call. You basically execute the async calls one by one. 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.
      • dmix 4y ago
        The third major strategy being Promise.any(): - as soon as any of them resolve (any) - when all of them resolve (all) - resolve each in order (for)
    • idontwantthis 4y ago
      Use my approach or yours, but never use forEach with await. I don’t remember exactly why, but it just doesn’t work and will lead to very confusing errors.
• jtwigg 4y ago
  FYI, if you plan to do this in ASP netcore, combine with AsyncLazy for the most optimal results https://github.com/davidfowl/AspNetCoreDiagnosticScenarios/blob/master/AsyncGuidance.md#concurrentdictionarygetoradd https://github.com/davidfowl/AspNetCoreDiagnosticScenarios/b...
  • alexchro93 4y ago
    Neat page from David Fowler. I didn't know about that one. Thank you. 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-concurrentdictionary-thread-safe-using-lazy/ https://andrewlock.net/making-getoradd-on-concurrentdictiona...
  • deleted 4y ago
    [deleted]
• Shorel 4y ago
  I know this as memoization with lazy evaluation, nothing new, but at the same time very useful, and I would argue, it is very CS.
  • sethammons 4y ago
    I've always called it request piggy backing (atop memoization). Our db abstraction at my last gig absolutely required it for scaling purposes. Great tool for the tool belt.
  • hn_throwaway_99 4y ago
    not really quite lazy evaluation, thought, at least in Javascript. Promises begin execution as soon as they are created and there is no way to delay that.
    • marcosdumay 4y ago
      Promises are an implementation of lazy evaluation for Javascript. This is exactly lazy evaluation. 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.
      • anyfoo 4y ago
        Wait. I thought lazy evaluation is defined as evaluation at the time a value is needed. After that I think it will then be in Weak Head Normal Form, which can be thought of as "evaluated at its top level"... but I'm a bit rusty. Basically, an expression gets used somewhere (e.g. pattern matched, in the ADT sense). If it's in WHNF, cool, it's evaluated already (subexpressions within may not yet, but that's their problem--that's exactly what WHNF says). If not, we evaluate it down to WHNF. 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?
• samatman 4y ago
  promise map? 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 }) This is an incomplete implementation, clearly: but I've never missed Promises with coroutines and libuv.
• maest 4y ago
  More generally, I believe this is a monad structure.
  • pdpi 4y ago
    Promises are not monads, for one simple reason: they're not referentially transparent. The whole point of OP's example is to double down and take advantage of that.
    • epolanski 4y ago
      Referential transparency is a property of expressions, not type classes. Referential transparency is nowhere in the definition of a monad because a monad is obviously not an expression but a type class. 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.
      • brewmarche 4y ago
        Maybe comonads fit better
• moonchrome 4y ago
  Just make sure Map access is thread safe - awaiting promises is - but updating/reading map keys usually isn't.
  • unrealhoang 4y ago
    js is single-threaded so no problem there.
    • moonchrome 4y ago
      Since OP mentioned Mutexes I assumed he's dealing with multithreaded code, but with JS this works as advertised :)
  • skrebbel 4y ago
    Yep, in multithreaded langs you just want to use a ConcurrentMap or whatever the stdlib has for this. The write is very brief because you only write the promise and not eg keep a proper lock on the key until the result has arrived, so no need for a fancier datastructure.
• wingspan 4y ago
  I love this approach and have used it many times in JavaScript. I often end up adding an additional map in front with the resolved values to check first, because awaiting or then'ing a Promise always means you will wait until the next microtask for the value, instead of getting it immediately. With a framework like React, this means you'll have a flash of missing content even when it is already cached.
  • pflanze 4y ago
    Replacing the promise with the result in the map (using a sum type as the map value type) might be more efficient than maintaining two maps?
  • skrebbel 4y ago
    This surprises me. I had expected the microtask to be executed right after the current one, ie before any layouting etc - isnt that the whole point the "micro" aspect?
    • chmod775 4y ago
      The event loop shouldn't continue the circle until the microtask queue is empty, from what I remember. 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.
    • wingspan 4y ago
• deltasevennine 4y ago
  Can someone explain to me why the second example is better. 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.
  • ohgodplsno 4y ago
    Say you have three elements in your UI that need to fetch some user info. You have two major options: 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.
  • Marazan 4y ago
    Because the computation of Result is _expensive_ and _async_. 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.
• abuckenheimer 4y ago
  This is clever, otherwise you have to coordinate your cache setter and your async function call between potentially many concurrent calls. There are ways to do this coordination though, one implementation I've borrowed in practice in python is modes stampede decorator: https://github.com/ask/mode/blob/master/mode/utils/futures.py#L70 https://github.com/ask/mode/blob/master/mode/utils/futures.p...
• asadawadia 4y ago
  Yeah, saves you from thundering herd problems https://github.com/ben-manes/caffeine 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
• mperreux 4y ago
  This is great. I'm actually running into this problem but across distributed clients. Is there a distributed way to achieve somthing like this with say Redis?
  • jawilson 4y ago
    Technically yes, the promise can first do an RPC to a distributed key/value store, and only then do the expensive computation (which typically is itself an RPC to some other system, perhaps a traditional database). Promise libraries should make this pretty simple to express (though always uglier than blocking calls). 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.
• bschaeffer 4y ago
  I wrote a version of this with Elixir: https://github.com/bschaeffer/til/tree/master/elixir/gen_server_async_reply https://github.com/bschaeffer/til/tree/master/elixir/gen_ser... Didn't know what to call it but PromiseMaps is nice name for it.
  • lightbendover 4y ago
    Promise Caching has a nicer name to it since that's what it is if well-implemented.
• deleted 4y ago
  [deleted]
• lalaithion 4y ago
  What do you mean by first class citizen, here? I’m pretty sure this works in all languages with promises, but I might be misunderstanding something.
• yla92 4y ago
  Anybody knows if there is similar pattern for Python's asyncio?
  • ActorNightly 4y ago
    https://docs.python.org/3.9/library/asyncio-future.html#asyncio.Future https://docs.python.org/3.9/library/asyncio-future.html#asyn...
  • abrichr 4y ago
    How about a dict whose values are asyncio.Future? https://docs.python.org/3/library/asyncio-future.html#asyncio.Future https://docs.python.org/3/library/asyncio-future.html#asynci...
• MobiusHorizons 4y ago
  I have a similar pattern when using an rxjs pipeline to do async tasks in response to changes in other values. The typical pattern would be readonly foo = bar.pipe( switchMap(v => doTask(v)), shareReplay(1), ); Where doTask returns a promise or an AsyncSubject. The shareRelpay allows foo to cache the last value so any late subscriber will get the most recent value. This has a problem of returning cached values while new work is happening (eg while a network request is in progress) so instead I like to write readonly foo = bar.pipe( map(v => doTask(v), shareReplay(1), switchMap(v => v), ); This way the shareReplay is caching the promise instead of the result. With this pattern I can interact with this pipeline from code like so async someEventHandler(userInput) { this.bar.next(userInput); const result = await firstValueFrom(this.foo); … } Without the pattern, this code would get the old result if there was ever any cached value
• cauthon 4y ago
  What is a promise in this context?
  • cpburns2009 4y ago
    A promise is an object representing an asynchronous result. Some languages, such as Python, call them futures. A promise object will typically have methods for determining if result is available, getting the result if it is, and registering callback functions to be called with the result when it's available.
    • cauthon 4y ago
      Thank you!
• polyrand 4y ago
  This is only tangentially related to: > 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#proxy_cache_lock https://nginx.org/en/docs/http/ngx_http_proxy_module.html#pr...
  • talos2110 4y ago
    That right there is Cache Stampede[0] prevention. [0]: https://en.wikipedia.org/wiki/Cache_stampede https://en.wikipedia.org/wiki/Cache_stampede
    • psytrx 4y ago
      Interesting! This is an issue I had with an external API which I intended to cache on my serverless workers infra. 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!
      • talos2110 4y ago
        You’re welcome, happy to help. If you are in the .NET space I suggest you to take a look at FusionCache. It has cache stampede protection built in, plus some other nice features like a fail-safe mechanism and soft/hard timeouts https://github.com/jodydonetti/ZiggyCreatures.FusionCache https://github.com/jodydonetti/ZiggyCreatures.FusionCache
• hmm-interesting 4y ago
  can you please explain this a bit more how this avoid fetching the same value twice? maybe with example.
  • kube-system 4y ago
    It sounds like, if you have a process that takes a long time to do, you check to see if you already have initiated that process (see if the key is in the list of promises), rather than firing off another promise for the same request. 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.
• dan-robertson 4y ago
  Be careful with this data structure. If the language allows async exceptions or you have a big where the promise won’t become deferred, there are a lot of edge cases. Examples of edge cases: - 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
  • feoren 4y ago
    - if the language eagerly binds on determined promises (ie it doesn’t schedule your .then function) you can get weird semantic bugs. What would be an example of this? If the promise has been determined, why not just immediately run the .then function?
    • afiori 4y ago
      The reason not to do it is to limit the non-determinism of the order of execution. In Javascript f1(); p.then(f3); f2(); functions are always called in the relative order f1, f2, f3 and never f1, f3 , f2 even if p had already resolved.
  • bloudermilk 4y ago
    Best practice in my experience is to use a timeout on all async operations to handle edge cases 1 & 2 above. The third case isn't possible with JavaScript AFAIK.
  • hinkley 4y ago
    I have a couple pieces of code where we had to add rate limiting because it was just too easy to make too many async calls all at once, and things only got 'worse' as I fixed performance issues in the traversal code that were creating an ersatz backpressure situation. 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 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.
• danellis 4y ago
  > It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. Why would that be true?
  • jchw 4y ago
    I think the actual answer is that it only works in languages where you can eagerly execute async code disconnected from the Promise/Future construct. It would've worked in ES3 using a Promise polyfill. (Which is notable because it does not fit the aforementioned criteria—it had no real async support.)
  • hinkley 4y ago
    It isn’t. The first implementation of promises I worked on was in Java. We used it as part of verifying certificate chains. If you use threads it doesn’t matter if the operations are blocking, as long as you move them off-thread.
• jchw 4y ago
  I believe that any time you await/then you wind up going back to the event loop. It's cheap ish but definitely not free. This is, of course, to make the behavior more predictable, but in this case it might be undesirable. Unfortunately, I don't think there's any obvious way around it. It can sorta be done with vanilla callbacks, but that takes you out of the async/promises world.
• studifi 4y ago
  The data structure here is a Map<T>
• philsnow 4y ago
  Vitess does something similar, "query coalescing", which was designed for loads that are very read-heavy. If 1000 requests come in that end up making the same read query from the database, and they all came in in the same 50ms that it takes to get the results from the database, you can just return the same answer to all of them.
• fabiancook 4y ago
  https://github.com/tc39/proposal-function-memo https://github.com/tc39/proposal-function-memo 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
• nurettin 4y ago
  >> Not a very deep CS-y one 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.
• deleted 4y ago
  [deleted]