Thanks both for responding! Re: DelayQueue peek() being special: you're right, I missed that. So my original proposal would not solve my problem. I really want to "block until poll() would return non-null" Let's pretend that's what blockingPeek() would do, though maybe the name is no longer suitable.
Re: John H: good point that I did not really explain what I'm trying to do. Basically I wanted a "keyed" DelayQueue with one added feature: AFTER inserting something into the queue, I discover that the initial delay is too soon and should be postponed. (Use case: imagine something should happen at least once per hour. So we set a timer for one hour and worry if the timer goes off. We need to be able to reset the timer if it happens ahead of schedule, or we'll worry for no reason.) The way I wanted to implement this is to store the "real" expiration in a map. This involves enforcing the invariant that the queue and map remain "in sync". Thus I prefer to hold a lock if I'm mutating either the queue or the map, so that changes appear atomic to other threads. Hope that's clearer now. From: Viktor Klang <viktor.kl...@oracle.com> Sent: Tuesday, May 2, 2023 4:08 AM To: John Hendrikx <john.hendr...@gmail.com>; core-libs-dev@openjdk.org; Yagnatinsky, Mark : Markets Pre Trade <mark.yagnatin...@barclays.com> Subject: Re: a plea for blocking peek CAUTION: This email originated from outside our organisation - viktor.kl...@oracle.com<mailto:viktor.kl...@oracle.com> Do not click on links, open attachments, or respond unless you recognize the sender and can validate the content is safe. Hi, I think the conversation also becomes a bit more difficult since the topic seems to be around DelayQueue-which has slightly different semantics than typical BlockingQueue implementations. For instance, peek() returns the element with the lowest expiry (possibly in the future)-so you cannot really use the blocking peek() for much else than observing the lowest expiry-and the only difference to the non-blocking peek() would be that you can block the reader for as long as the queue is empty without A) removing the element and B) doing busy-waiting with some form of back-off policy which might ending up sleeping for too long. Since queues tend to spend their time being either full or empty (since there's typically either a faster consumption than production or vice versa), I can understand the need to be notified when the queue is no longer empty. With that said, in the case of DelayQueue, it still doesn't mean that the result of a blocking peek() means that the element is consumable at that point. So the question is what you'd use the information for? When composing multiple data structures, especially concurrent ones, I find it easier to reason about the problem space starting with the interaction pattern from the outside (who consumes and who produces), as the less coordination needed the better in terms of throughput (Amdahl's Law & Universal Scalability Law) etc, and if you can design for single-reader or single-writer (or both!) you can get away with much more performant implementations since the coordination need is much lower. ________________________________ From: core-libs-dev <core-libs-dev-r...@openjdk.org<mailto:core-libs-dev-r...@openjdk.org>> on behalf of John Hendrikx <john.hendr...@gmail.com<mailto:john.hendr...@gmail.com>> Sent: Tuesday, 2 May 2023 08:46 To: core-libs-dev@openjdk.org<mailto:core-libs-dev@openjdk.org> <core-libs-dev@openjdk.org<mailto:core-libs-dev@openjdk.org>>; mark.yagnatin...@barclays.com<mailto:mark.yagnatin...@barclays.com> <mark.yagnatin...@barclays.com<mailto:mark.yagnatin...@barclays.com>> Subject: Re: a plea for blocking peek Hi, I think it would help if you describe your problem a bit more directly. Currently there is a lot of mention of difficulty levels, usual approaches and "winning", which really doesn't help to ascertain what you are trying to achieve. For a good re-evaluation of your request, you are going to need to show some (pseudo) code so people can see if this indeed is a good use case, or that there is an elegant alternative solution. It's really hard to glean from your post what you are trying to do. It seems like you have a queue and a map. Items you get from the queue need to be verified against the map. The lock seems to protect the map structure against concurrent modification, and for some reason getting the lock after `take` isn't good enough. --John On 01/05/2023 19:12, mark.yagnatin...@barclays.com<mailto:mark.yagnatin...@barclays.com> wrote: I'm not sure if this I'm breaking etiquette for this list but I'm going to risk resending my first message because it got zero replies. If it was simply too long, please let me know and I'll attempt a shorter version. Here's like to original: https://mail.openjdk.org/pipermail/core-libs-dev/2023-April/104931.html<https://clicktime.symantec.com/15t5jYTFmaQc4V1t88CUj?h=LBFB_Nq9tTnZigIGSEGdtPI-yf5pM2QRYu75ZQPdMrc=&u=https://mail.openjdk.org/pipermail/core-libs-dev/2023-April/104931.html> From: Yagnatinsky, Mark : Markets Pre Trade Sent: Thursday, April 27, 2023 12:28 PM To: core-libs-dev@openjdk.org<mailto:core-libs-dev@openjdk.org> Subject: RE: blocking peek for blocking queues Someone said this is the right list for this, so forwarding from jdk-dev with a small tweak I'd like to make a case for adding a blocking variant of peek() to BlockingQueue. This has apparently been suggested before: https://bugs.openjdk.org/browse/JDK-6653412<https://clicktime.symantec.com/15t5eiFyJxj1eYBxaZoL7?h=8xuZNSBOobjYTAnKJmm6Y3zyDdQB80zgAhmGgE74pOQ=&u=https://bugs.openjdk.org/browse/JDK-6653412> At the time, the verdict was that the proposed use case for a blocking peek was not very compelling, but " If a compelling use case is available,we may reconsider and reopen this RFE" For one thing, that use case was inherently racy, and ideally the standard library should not be encouraging races. And for another thing, this was before the invention of default methods, so a new interface would be needed. I'd like to present what might be a more sympathetic use case, where a blocking peek actually makes it easier to avoid races. (This is not hypothetical; I've spent all day trying to cope with the lack of a blocking peek. I think I succeeded, but it was tough.) Let's start at the beginning. The game known as "multithreaded programming" can be played on 3 difficulty levels: easy, medium, and hard. Easy mode is when the JDK happens to have a high-level tool (e.g., a Collection or an Executor or something) such as DelayQueue that does exactly what you want. Sadly, the JDK is finite, and even Maven Central is finite, so this not guaranteed to happen, though it's nice when it does. At the other extreme is hard mode, when every nanosecond counts and you must resort to the sorts of mental gymnastics that were involved when String.hashCode was re-worked to avoid re-computing hash codes equal to zero. This email is about the medium difficulty level. In this mode, you must glue together two or three collections to get what you want. To be concrete, suppose we want to glue a map together with a blocking queue, since that's a simplified version of what I was doing. (In particular I was using a DelayQueue and a HashMap.) Since we're not playing on hard mode, we're going to allow ourselves to guard the entire data structure by one giant lock whenever it seems convenient, without worrying about performance. In fact, let's give a name to this lock. Since I'm not feeling very creative right now, let's call it LOCK. Similarly, let's call our compound data structure STRUCT. My usual heuristic to "win" (that is, to make sure my code is correct, or at least non-racy) on medium difficulty goes something like this. First, figure out whether there is any way for STRUCT to be "invalid". For instance, maybe "it's valid if and only if every entry in the queue has a corresponding entry in the map". One could then write a brief comment in the code explaining what "valid" means, or perhaps even write an "isValid()" method for testing purposes. Once we've decided what it means for STRUCT to be "valid" (aka, non-corrupt), we can try to maintain the following invariant: EITHER some thread holds the LOCK, and no other thread is using STRUCT right now, OR ELSE the LOCK is not held by any thread, and thus STRUCT is currently in a valid state. Sometimes the invariant above is a bit too strong, and it's convenient to weaken it slightly. So we can instead consider the following rule: RULE: we must never mutate STRUCT unless we hold the LOCK. If we uphold the invariant, then we must be following the rule, but not vice versa. (The rule doesn't forbid queries without the lock; it only forbids writes.) Finally, we come to the point. The lack of a blocking peek in BlockingQueue has forced me to break the above "weakened" rule. I had to invent a new much weaker rule, something like "please carefully think through all possible interleaved executions; if they all work, great!". What went wrong? Well, one of the methods I wanted on STRUCT was basically "call take() on the queue, and then do things with the result". The trouble is that you can't usually afford to hold a lock while calling take(), since it can block forever, and in the meantime you've "locked out" anyone who could have added something and thus unblocked you. Thus, I split my method into two pieces: In PART_ONE we call take() without the LOCK, and once take() returns I grab the lock right away and run PART_TWO. But notice that this breaks the RULE from the previous paragraph: I mutated the STRUCT without holding the LOCK. This means my method is not atomic: it's possible for some other thread to observe that PART_ONE is done but PART_TWO is not started. Typically this means that other threads can now observe the STRUCT in an invalid (aka corrupt/broken) state. Now, suppose we had a blocking peek. How does that help? In that case, we would still break our method into two pieces. To avoid confusion, let's call them PART_A and PART_B. In PART_A we call blockingPeek() without holding the LOCK. Note that we completely ignore the return value from peek; for all we care, the return type is "void" instead of "T". This breaks the "invariant" from a few paragraphs ago since we're technically "using" the STRUCT but it respects the "rule" since we're not mutating it. Once peek returns, PART_B begins. Here, we grab the lock, and do a non-blocking poll() on the queue. It's might return "null" if someone raced us to get the lock. But from our perspective that's okay: it's just like a spurious wakeup from a raw wait() call. The reason it's okay is that we haven't done anything yet, so we can just call blockingPeek() again and hope for better luck next time. Similarly we don't care if poll() returns a different item than blockingPeek() originally did, since we never looked at what peek() returned. The rest of PART_B is basically PART_TWO from the "peek-less" world. Note that this way, our method appears atomic to other threads, since PART_A doesn't actually do anything; all the work happens in PART_B, which is guarded by the LOCK. Thoughts? This message is for information purposes only. It is not a recommendation, advice, offer or solicitation to buy or sell a product or service, nor an official confirmation of any transaction. It is directed at persons who are professionals and is intended for the recipient(s) only. It is not directed at retail customers. This message is subject to the terms at: https://www.cib.barclays/disclosures/web-and-email-disclaimer.html<https://clicktime.symantec.com/15t69hRg4epa8D9VqvCDq?h=-3mwRiHllHKu-mx5mhLnv52Z_4IbikUQWio278f4PQQ=&u=https://www.cib.barclays/disclosures/web-and-email-disclaimer.html>. For important disclosures, please see: https://www.cib.barclays/disclosures/sales-and-trading-disclaimer.html<https://clicktime.symantec.com/15t64sEPc38yiGKaJMo5D?h=oMRxaXIQ3u-OAjHOHoIJ12Q6Xvd18bfr8Zh7uBGFxyU=&u=https://www.cib.barclays/disclosures/sales-and-trading-disclaimer.html> regarding marketing commentary from Barclays Sales and/or Trading desks, who are active market participants; https://www.cib.barclays/disclosures/barclays-global-markets-disclosures.html<https://clicktime.symantec.com/15t5pNeYEC6CURqofgbdM?h=JL4FUcCyPdlJHc30zVvoYnr_RofP7sC0WpF38usDgyc=&u=https://www.cib.barclays/disclosures/barclays-global-markets-disclosures.html> regarding our standard terms for Barclays Corporate and Investment Bank where we trade with you in principal-to-principal wholesale markets transactions; and in respect to Barclays Research, including disclosures relating to specific issuers, see: http://publicresearch.barclays.com<https://clicktime.symantec.com/15t5Zt4grM3REbN331QBV?h=9z3-VRvLZpe8YmOkBXvpzPozW6VCrzt2JEDDz4eDybA=&u=http://publicresearch.barclays.com>. __________________________________________________________________________________ If you are incorporated or operating in Australia, read these important disclosures: https://www.cib.barclays/disclosures/important-disclosures-asia-pacific.html<https://clicktime.symantec.com/15t5uCqpgomntNfjDEzmy?h=2EajesTPX5m7Ra4igt5cBHjbTC0CCpozqCRCa3Bg6BM=&u=https://www.cib.barclays/disclosures/important-disclosures-asia-pacific.html>. __________________________________________________________________________________ For more details about how we use personal information, see our privacy notice: https://www.cib.barclays/disclosures/personal-information-use.html<https://clicktime.symantec.com/15t5z3379RTPJKVekoPvb?h=eF4fDVda50ewe9_uCtYec7foCfszmYGuh4HlJUcCsbU=&u=https://www.cib.barclays/disclosures/personal-information-use.html>. __________________________________________________________________________________ This message is for information purposes only. It is not a recommendation, advice, offer or solicitation to buy or sell a product or service, nor an official confirmation of any transaction. It is directed at persons who are professionals and is intended for the recipient(s) only. It is not directed at retail customers. This message is subject to the terms at: https://www.cib.barclays/disclosures/web-and-email-disclaimer.html. For important disclosures, please see: https://www.cib.barclays/disclosures/sales-and-trading-disclaimer.html regarding marketing commentary from Barclays Sales and/or Trading desks, who are active market participants; https://www.cib.barclays/disclosures/barclays-global-markets-disclosures.html regarding our standard terms for Barclays Corporate and Investment Bank where we trade with you in principal-to-principal wholesale markets transactions; and in respect to Barclays Research, including disclosures relating to specific issuers, see: http://publicresearch.barclays.com. __________________________________________________________________________________ If you are incorporated or operating in Australia, read these important disclosures: https://www.cib.barclays/disclosures/important-disclosures-asia-pacific.html. __________________________________________________________________________________ For more details about how we use personal information, see our privacy notice: https://www.cib.barclays/disclosures/personal-information-use.html. __________________________________________________________________________________
