<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hello Mark,</p>
<p>core-libs-dev is a better place for this discussion
<a class="moz-txt-link-freetext" href="https://mail.openjdk.org/mailman/listinfo/core-libs-dev">https://mail.openjdk.org/mailman/listinfo/core-libs-dev</a></p>
<p>-Jaikiran<br>
</p>
<div class="moz-cite-prefix">On 27/04/23 8:21 am,
<a class="moz-txt-link-abbreviated" href="mailto:mark.yagnatinsky@barclays.com">mark.yagnatinsky@barclays.com</a> wrote:<br>
</div>
<blockquote type="cite"
cite="mid:MN2PR12MB3616452CA59705B1129E4922F96A9@MN2PR12MB3616.namprd12.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<meta name="Generator" content="Microsoft Word 15 (filtered
medium)">
<style>@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}div.WordSection1
{page:WordSection1;}</style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal">I suspect this is the wrong list; if so I
hope someone will redirect me.<o:p></o:p></p>
<p class="MsoNormal">I’d like to make a case for adding a
blocking variant of peek() to BlockingQueue.<o:p></o:p></p>
<p class="MsoNormal">This has apparently been suggested before:<o:p></o:p></p>
<p class="MsoNormal"><a
href="https://bugs.openjdk.org/browse/JDK-6653412"
moz-do-not-send="true" class="moz-txt-link-freetext">https://bugs.openjdk.org/browse/JDK-6653412</a><o:p></o:p></p>
<p class="MsoNormal">At the time, the verdict was that the
proposed use case for a blocking peek was not very compelling.<o:p></o:p></p>
<p class="MsoNormal">For one thing, that use case was inherently
racy, and ideally the standard library should not be
encouraging races.<o:p></o:p></p>
<p class="MsoNormal">And for another thing, this was before the
invention of default methods, so a new interface would be
needed.<o:p></o:p></p>
<p class="MsoNormal">I’d like to present what might be a more
sympathetic use case, where a blocking peek actually makes it
easier to avoid races.<o:p></o:p></p>
<p class="MsoNormal">(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.)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Let’s start at the beginning. The game
known as “multithreaded programming” can be played on 3
difficulty levels: easy, medium, and hard.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">Sadly, the JDK is finite, and even Maven
Central is finite, so this not guaranteed to happen, though
it’s nice when it does.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This email is about the medium difficulty
level. In this mode, you must glue together two or three
collections to get what you want.<o:p></o:p></p>
<p class="MsoNormal">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.)<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">First, figure out whether there is any way
for STRUCT to be “invalid”.<o:p></o:p></p>
<p class="MsoNormal">For instance, maybe “it’s valid if and only
if every entry in the queue has a corresponding entry in the
map”.<o:p></o:p></p>
<p class="MsoNormal">One could then write a brief comment in the
code explaining what “valid” means, or perhaps even write an
“isValid()” method for testing purposes.<o:p></o:p></p>
<p class="MsoNormal">Once we’ve decided what it means for STRUCT
to be “valid” (aka, non-corrupt), we can try to maintain the
following invariant:<o:p></o:p></p>
<p class="MsoNormal">EITHER some thread holds the LOCK, and no
other thread is using STRUCT right now,<o:p></o:p></p>
<p class="MsoNormal">OR ELSE the LOCK is not held by any
thread, and thus STRUCT is currently in a valid state.<o:p></o:p></p>
<p class="MsoNormal">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:<o:p></o:p></p>
<p class="MsoNormal">RULE: we must never mutate STRUCT unless we
hold the LOCK.<o:p></o:p></p>
<p class="MsoNormal">If we uphold the invariant, then we must be
following the rule, but not vice versa.<o:p></o:p></p>
<p class="MsoNormal">(The rule doesn’t forbid queries without
the lock; it only forbids writes.)<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Finally, we come to the point. The lack of
a blocking peek in BlockingQueue has forced me to break the
above “weakened” rule.<o:p></o:p></p>
<p class="MsoNormal">I had to invent a new much weaker rule,
something like “please carefully think through all possible
interleaved executions; if they all work, great!”.<o:p></o:p></p>
<p class="MsoNormal">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”.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">But notice that this breaks the RULE from
the previous paragraph: I mutated the STRUCT without holding
the LOCK.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">Typically this means that other threads can
now observe the STRUCT in an invalid (aka corrupt/broken)
state.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Now, suppose we had a blocking peek. How
does that help? In that case, we would still break our method
into two pieces.<o:p></o:p></p>
<p class="MsoNormal">To avoid confusion, let’s call them PART_A
and PART_B. In PART_A we call blockingPeek() without holding
the LOCK.<o:p></o:p></p>
<p class="MsoNormal">Note that we completely ignore the return
value from peek; for all we care, the return type is “void”
instead of “T”.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">Once peek returns, PART_B begins. Here, we
grab the lock, and do a non-blocking poll() on the queue.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal">Similarly we don’t care if poll() returns a
different item than blockingPeek() originally did, since we
never looked at what peek() returned.<o:p></o:p></p>
<p class="MsoNormal">The rest of PART_B is basically PART_TWO
from the “peek-less” world.<o:p></o:p></p>
<p class="MsoNormal">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.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thoughts?<o:p></o:p></p>
</div>
<p><span style="mso-ansi-language: EN-US" lang="EN-US">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:
<a
href="https://www.cib.barclays/disclosures/web-and-email-disclaimer.html"
moz-do-not-send="true" class="moz-txt-link-freetext">https://www.cib.barclays/disclosures/web-and-email-disclaimer.html</a>.
</span></p>
<p><span style="mso-ansi-language: EN-US" lang="EN-US">For
important disclosures, please see: <a
href="https://www.cib.barclays/disclosures/sales-and-trading-disclaimer.html"
moz-do-not-send="true" class="moz-txt-link-freetext">https://www.cib.barclays/disclosures/sales-and-trading-disclaimer.html</a>
regarding marketing commentary from Barclays Sales and/or
Trading desks, who are active market participants; <a
href="https://www.cib.barclays/disclosures/barclays-global-markets-disclosures.html"
moz-do-not-send="true" class="moz-txt-link-freetext">https://www.cib.barclays/disclosures/barclays-global-markets-disclosures.html</a>
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: <a
href="http://publicresearch.barclays.com"
moz-do-not-send="true" class="moz-txt-link-freetext">http://publicresearch.barclays.com</a>.<br>
__________________________________________________________________________________
<br>
If you are incorporated or operating in Australia, read these
important disclosures: <a
href="https://www.cib.barclays/disclosures/important-disclosures-asia-pacific.html"
moz-do-not-send="true" class="moz-txt-link-freetext">https://www.cib.barclays/disclosures/important-disclosures-asia-pacific.html</a>.<br>
__________________________________________________________________________________<br>
For more details about how we use personal information, see
our privacy notice: <a
href="https://www.cib.barclays/disclosures/personal-information-use.html"
moz-do-not-send="true" class="moz-txt-link-freetext">https://www.cib.barclays/disclosures/personal-information-use.html</a>.
<br>
__________________________________________________________________________________<br>
</span></p>
</blockquote>
</body>
</html>