<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none"><!-- p { margin-top: 0px; margin-bottom: 0px; }--></style>
</head>
<body dir="ltr" style="font-size:12pt;color:#000000;background-color:#FFFFFF;font-family:Calibri,Arial,Helvetica,sans-serif;">
<p>​[apologies in advance if this is the wrong place to discuss this issue. also apologies for the long setup -- I promise this is about ArrayBlockingQueue, Java, and a performance issue with them]<br>
</p>
<p><br>
</p>
<p>My student and I have been benchmarking various ways to run cross data source joins. The basic setup is as follows:<br>
</p>
<p><br>
</p>
<p>           J2<br>
</p>
<p style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 16px;">           /  \<br>
</p>
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 16px;">
<p>          /    \<br>
</p>
</div>
<p>        R3  J1<br>
</p>
<p></p>
<p style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 16px;">              /  \<br>
</p>
<div>
<p style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 16px;">             /    \<br>
</p>
<div>           R2  R1<br>
</div>
<div><br>
</div>
<div>R1, R2 and R3 are called receive operators as they receive data from the databases. J1 and J2 are inner join operators joining values from R2 with values from R1 and then the result with values from R3.<br>
</div>
<div><br>
</div>
<div>One way to run these queries is the classic producers and consumers approach -- so each operator is a Java thread, and there are bounded queues (ArrayBlockingQueues) between the operators. So the above example has 5 threads and 4
<span style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 16px; background-color: rgb(255, 255, 255);">
ArrayBlockingQueues</span>. So here we interleave I/O with computation.<br>
</div>
<div><br>
</div>
<div>Another way to run this is to first load R3 into J2 in parallel with loading R2 into J1 (the loads build hash maps in J1 and J2), and then have a thread pool with N workers (where N is the number of cores), where each worker takes a value from R1 and joins
 it "up the spine" of the tree -- so matches against the hash map in J1 and then J2. This approach (the phased approach) therefore has an I/O phase, followed by a computation phase.<br>
</div>
<div><br>
</div>
<div><br>
</div>
</div>
<div>On OS X El Capitan (<span style="color: rgb(36, 39, 41); font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; background-color: rgb(255, 255, 255);">1<span style="font-size: 12pt;">0.11.6</span></span>), the queueing approach and
 the phased <span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">approach perform roughly equally (more variation in the run times for the queueing approach, but performance within
 10% of each other). On Linux (</span></span><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">Ubuntu
 16.04 LTS)<span style="font-size: 12pt;"> the queueing approach is almost three times slower than the phased approach!</span></span></span></span><br style="font-family: Calibri, Arial, Helvetica, sans-serif;">
</div>
<div><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><br style="font-family: Calibri, Arial, Helvetica, sans-serif;">
</span></div>
<div><span style="color: rgb(36, 39, 41); background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">On
 top of that the queueing approach runs over twice as fast on OS X as it is does on Linux, despite the fact that I am running OS X on old hardware (mid 2012 Macbook Pro, 3rd Gen </span></span><span style="color: rgb(36, 39, 41); background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">Intel
 Core i5 3210M</span></span></span><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">) and Linux on relatively new hardware (6th Gen </span></span><span style="color: rgb(36, 39, 41); background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">Intel
 Core i7-5500U).</span></span></span></span></div>
<div><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><br style="font-family: Calibri, Arial, Helvetica, sans-serif;">
</span></span></div>
<div><span style="color: rgb(36, 39, 41); font-size: 12pt; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="color: rgb(36, 39, 41); background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">We
 have boiled the problem down to code that doesn't involve databases -- just threads and ArrayBlockingQueues. Attached are 5 Java files which "approximate" the queueing approach by having each receive thread simply output numbers (rather than get values from
 a database) to an ArrayBlockingQueue, and each Join thread simply read its two input queues, adds the values together, and then output the sum to the output queue.</span></span></span></span></div>
<div><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><br style="font-family: Calibri, Arial, Helvetica, sans-serif;">
</span></span></div>
<div><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">On<span style="font-size: 12pt;">
 the same hardware above this code runs in 1 minute </span><span style="font-size: 12pt;">30 secs on OS X, and 2 minutes 13 secs on Linux!</span></span></span></span></span></div>
<div><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="color: rgb(36, 39, 41); font-size: 15px; background-color: rgb(255, 255, 255); font-family: Calibri, Arial, Helvetica, sans-serif;"><br style="font-family: Calibri, Arial, Helvetica, sans-serif;">
</span></span></div>
<div><span style="font-family: Calibri, Arial, Helvetica, sans-serif;"><span style="font-family: Calibri, Arial, Helvetica, sans-serif;">The code is very simple -- just a bunch of threads and a bunch of ArrayBlockingQueues. So I am at a loss to explain the
 size-able performance differences noted above.</span></span><br>
</div>
<div><br>
</div>
<div>Again apologies if this is not the right forum to discuss this issue.<br>
</div>
<div><br>
</div>
<div>graham<br>
<br>
​<br>
</div>
<div id="Signature">
<div name="divtagdefaultwrapper" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:; margin:0">
<div class="BodyFragment"><font size="2">
<div class="PlainText">------  <br>
Graham MATTHEWS, Ph.D.<br>
<span style="background-color:rgb(255,255,255)">Assistant Professor</span><br>
Department of Computer Science |  California Lutheran University<br>
60 W. Olsen Rd.  |  Thousand Oaks, CA 91360<br>
gmatthew@callutheran.edu  | Office location: D19</div>
</font></div>
</div>
</div>
</body>
</html>