<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META content="MSHTML 6.00.2800.1649" name=GENERATOR></HEAD>
<BODY>
<DIV><SPAN class=507364622-08082010><FONT face="Courier New" color=#0000ff 
size=2>Hi Peter,</FONT></SPAN></DIV>
<DIV><SPAN class=507364622-08082010><FONT face="Courier New" color=#0000ff 
size=2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=507364622-08082010><FONT face="Courier New" color=#0000ff 
size=2>I should have said "need to know the size for correctness". There are 
times when queries like this can be useful for performance heuristics as you 
describe. </FONT></SPAN></DIV>
<DIV><SPAN class=507364622-08082010><FONT face="Courier New" color=#0000ff 
size=2></FONT></SPAN>&nbsp;</DIV>
<DIV><SPAN class=507364622-08082010><FONT face="Courier New" color=#0000ff 
size=2>From the usage you describe you seem to be supplanting the blocking-queue 
semantics with your own - in which case a customized wait/notify strategy may 
well perform better than the general one behind 
put/take.&nbsp;</FONT></SPAN></DIV>
<DIV><SPAN class=507364622-08082010></SPAN>&nbsp;</DIV>
<DIV><SPAN class=507364622-08082010><FONT face="Courier New" color=#0000ff 
size=2>David Holmes</FONT></SPAN><FONT face=Tahoma><FONT size=2><SPAN 
class=507364622-08082010><FONT face="Courier New" 
color=#0000ff>&nbsp;</FONT></SPAN></FONT></FONT></DIV>
<DIV><FONT face=Tahoma><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=507364622-08082010></SPAN></FONT></FONT>&nbsp;</DIV>
<DIV><FONT face=Tahoma><FONT face="Courier New" color=#0000ff size=2><SPAN 
class=507364622-08082010></SPAN></FONT></FONT>&nbsp;</DIV>
<DIV><FONT face=Tahoma><FONT size=2><SPAN 
class=507364622-08082010>&nbsp;</SPAN>-----Original Message-----<BR><B>From:</B> 
concurrency-interest-bounces@cs.oswego.edu 
[mailto:concurrency-interest-bounces@cs.oswego.edu]<B>On Behalf Of </B>Péter 
Kovács<BR><B>Sent:</B> Sunday, 8 August 2010 10:04 PM<BR><B>To:</B> 
concurrency-interest@cs.oswego.edu<BR><B>Subject:</B> Re: [concurrency-interest] 
Asynchronous-nature ofConcurrentLinkedQueue<BR><BR></DIV></FONT></FONT>
<BLOCKQUOTE 
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid">
  <DIV>David,</DIV>
  <DIV><BR></DIV>
  <DIV>&gt; The present code only penalises the misguided client that thinks 
  they need<BR>to know the size.</DIV>
  <DIV><BR></DIV>
  <DIV>Is there a simple, abstract way to demonstrate one shouldn't need this 
  information? (But not too formal, please. :-) )</DIV>
  <DIV><BR></DIV>
  <DIV>I have a scenario where I found useful knowing an approximate size of a 
  LinkedBlockingQueue:</DIV>
  <DIV><BR></DIV>
  <DIV>A number of worker threads</DIV>
  <DIV>
  <OL>
    <LI>put an empty result-holder object on the LBQ, 
    <LI>take their input from a producer,
    <LI>do some processing and
    <LI>put the result into the empty result-holder object.</LI></OL></DIV>
  <DIV>The first two steps are executed in a synchronized block, so the order of 
  results on the LBQ reflects that of the corresponding inputs.</DIV>
  <DIV><BR></DIV>
  <DIV>The LBQ is consumed by a single thread.</DIV>
  <DIV><BR></DIV>
  <DIV>I found that</DIV>
  <DIV>
  <OL>
    <LI>having the worker wait&nbsp;in step#1, when the LBQ is 
    full&nbsp;(&nbsp;<FONT class=Apple-style-span 
    face="'courier new', monospace">if (!lbq.offer(resultHolder)) { wait(); 
    }&nbsp;</FONT>) &nbsp;and 
    <LI>notifying workers waiting, when&nbsp;lbq.size() &lt; maxLbqSize * 4 / 
    5</LI></OL></DIV>
  <DIV>gives about 15% improvement in throughput -- as opposed to 
  the&nbsp;algorithm, where I let workers block in <FONT class=Apple-style-span 
  face="'courier new', monospace">lbq.put(resultHolder)</FONT>.</DIV>
  <DIV><BR></DIV>
  <DIV>My naive hypothesis to explain the gain is that&nbsp;having 
  --&nbsp;during <I>each </I>lbq.take() --&nbsp;to constantly manage the 
  threads&nbsp;which block in lbq.put() might be more expensive than having 
  workers wait and notifying them <I>less frequently</I>.</DIV>
  <DIV><BR></DIV>
  <DIV>I've been having the haunting feeling that this queue-size-checking trick 
  is just a hack to compensate for some non-trivial design (or implementation) 
  flaw elsewhere. But I haven't been able to find a(n easy) way to either prove 
  or refute my hypothesis.</DIV>
  <DIV><BR></DIV>
  <DIV>I'd be grateful if you could offer some thoughts on this.</DIV>
  <DIV><BR></DIV>
  <DIV>Thanks</DIV>
  <DIV>Peter</DIV><BR>
  <DIV class=gmail_quote>On Wed, May 19, 2010 at 12:35 AM, David Holmes <SPAN 
  dir=ltr>&lt;<A 
  href="mailto:davidcholmes@aapt.net.au">davidcholmes@aapt.net.au</A>&gt;</SPAN> 
  wrote:<BR>
  <BLOCKQUOTE class=gmail_quote 
  style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">Greg,<BR>
    <DIV class=im><BR>Gregg Wonderly writes:<BR>&gt; Doug Lea wrote:<BR>&gt; 
    &gt; On 05/18/10 08:03, Kai Meder wrote:<BR>&gt; &gt;&gt; Hello<BR>&gt; 
    &gt;&gt;<BR>&gt; &gt;&gt; reading the Java-Docs of ConcurrentLinkedQueue I 
    wonder what the<BR>&gt; &gt;&gt; "asynchronous nature" mentioned in the 
    size()-doc is?<BR>&gt; &gt;&gt;<BR>&gt; &gt;&gt; "Beware that, unlike in 
    most collections, this method is NOT a<BR>&gt; &gt;&gt; constant-time 
    operation. Because of the asynchronous nature of these<BR>&gt; &gt;&gt; 
    queues, determining the current number of elements requires an O(n)<BR>&gt; 
    &gt;&gt; traversal. "<BR>&gt; &gt;&gt;<BR>&gt; &gt;<BR>&gt; &gt; Because 
    insertion and removal operations can occur concurrently<BR>&gt; &gt; (even 
    while you are asking about the size), you generally<BR>&gt; &gt; don't want 
    to ask about the size (although isEmpty is usually<BR>&gt; &gt; still 
    useful). But if you do ask, the queue<BR>&gt; &gt; will provide an answer by 
    counting up the elements. The<BR>&gt; &gt; answer it returns might not have 
    much bearing to the actual<BR>&gt; &gt; number of elements upon return of 
    the method.<BR>&gt;<BR>&gt; And I guess I am always curious why there is no 
    "counter"<BR>&gt; associated with the queue length. &nbsp;It would provide 
    the<BR>&gt; same "rough" estimate as the "traversal" without the<BR>&gt; 
    &nbsp;repeated overhead would it not?<BR><BR></DIV>Yes but at a cost to 
    every queue operation to maintain that counter. This<BR>penalises the main 
    queue operations to support another operation (size())<BR>that is for most 
    intents and purposes completely useless.<BR><BR>The present code only 
    penalises the misguided client that thinks they need<BR>to know the 
    size.<BR><FONT color=#888888><BR>David<BR></FONT>
    <DIV>
    <DIV></DIV>
    <DIV class=h5><BR>&gt;<BR>&gt; Gregg Wonderly<BR>&gt; 
    _______________________________________________<BR>&gt; Concurrency-interest 
    mailing list<BR>&gt; <A 
    href="mailto:Concurrency-interest@cs.oswego.edu">Concurrency-interest@cs.oswego.edu</A><BR>&gt; 
    <A href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest" 
    target=_blank>http://cs.oswego.edu/mailman/listinfo/concurrency-interest</A><BR><BR>_______________________________________________<BR>Concurrency-interest 
    mailing list<BR><A 
    href="mailto:Concurrency-interest@cs.oswego.edu">Concurrency-interest@cs.oswego.edu</A><BR><A 
    href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest" 
    target=_blank>http://cs.oswego.edu/mailman/listinfo/concurrency-interest</A><BR></DIV></DIV></BLOCKQUOTE></DIV><BR></BLOCKQUOTE></BODY></HTML>