tag:blogger.com,1999:blog-20714536055355009802024-02-21T01:23:28.442-08:00Otherwise I'd ForgetThis is my blog on various technical software issues.Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-2071453605535500980.post-53767535979381048762017-05-13T14:12:00.003-07:002017-05-13T14:58:02.988-07:00Is my H2 query slow because of a missing index?Making sure the proper indexes are in place is one of the first things you should do when trying to speed up query execution.<br />
<br />
<a href="https://github.com/eostermueller/javaPerformanceTroubleshooting" target="_blank">This github repo</a> has several running examples of performance defects that you can run on your own machine. Test 05b is a demonstration of a slow <a href="http://www.h2database.com/" target="_blank">H2</a> query because it is missing an index.<br />
<br />
One reason you might expect that a particular query was slow is if you saw something fishy in your very nice SQL response time metrics from <a href="http://glowroot.org/">glowroot.org</a>. In following screenshot, note that the query in the top row is more than 10 times slower than the other two.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9-DQXDUZSa6pWdCduIv803lyRkb53jGN7W58hJNU5xtZsSW6zwDopzhcbdWdnRbcEw9Xy8BBRg_JnBz_yWH5MFiMfEZhS0yv64zLIOtj8ms3NW2Jxtv1Xh5wkzp2yt7t0UDj5md_ZVEw/s1600/jpt_ch09_t05b_slowQuery.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="200" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh9-DQXDUZSa6pWdCduIv803lyRkb53jGN7W58hJNU5xtZsSW6zwDopzhcbdWdnRbcEw9Xy8BBRg_JnBz_yWH5MFiMfEZhS0yv64zLIOtj8ms3NW2Jxtv1Xh5wkzp2yt7t0UDj5md_ZVEw/s400/jpt_ch09_t05b_slowQuery.png" width="400" /></a></div>
<br />
Here is the query -- its average response time is 358.5ms.<br />
<blockquote class="tr_bq">
<span style="font-family: "courier new" , "courier" , monospace;">SELECT hid from history WHERE aid = ?</span></blockquote>
<br />
<br />
So to find out whether the right indexes are in place for this query, you need to get the query's <a href="https://www.simple-talk.com/sql/performance/execution-plan-basics/" target="_blank">execution plan</a>. To get this, you first load the H2 administrative console. My H2 DB is running on my local box, so here is the URL: <a href="http://localhost:8082/">http://localhost:8082/</a><br />
<br />
Then, you have to submit a particular query to get the execution plan. All you need to do is prefix your query with the word 'explain' and then you need to replace all your bind variable question marks with actual (or at least legal) values. I also had to prefix my table name with the schema name. Here is the result:<br />
<blockquote class="tr_bq">
<span style="font-family: "courier new" , "courier" , monospace;">EXPLAIN SELECT hid from s01.history WHERE aid = 235</span></blockquote>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgsnzLMpQEzpVpVXwJ_rKGFzkqKiUVZh_A7ZtT1hOSbPLzTnKzHSxr410g738IG4DPxdfvAX6iTlYMeWZ1UJEfFDcf1PSg3J_kPZyB5EICK6OI37cd43hZg2Tz-y-WDpWwOBxV_gH29Yqw/s1600/h2-explain-plan_tableScan.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="460" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgsnzLMpQEzpVpVXwJ_rKGFzkqKiUVZh_A7ZtT1hOSbPLzTnKzHSxr410g738IG4DPxdfvAX6iTlYMeWZ1UJEfFDcf1PSg3J_kPZyB5EICK6OI37cd43hZg2Tz-y-WDpWwOBxV_gH29Yqw/s640/h2-explain-plan_tableScan.png" width="640" /></a></div>
<br />
<div>
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span></div>
<br />
<br />
Towards the bottom of the above screenshot, you will see this text:<br />
<span style="font-family: "courier new" , "courier" , monospace;"><br /></span>
<br />
<blockquote class="tr_bq">
<span style="font-family: "courier new" , "courier" , monospace;">/* S02.HIST</span><span style="font-family: "courier new" , "courier" , monospace;">ORY.tableScan */</span></blockquote>
<br />
The text "tableScan" indicates that no index was used to, probably, process the WHERE clause, which is "WHERE aid = 235". The next question to ask is whether any index exists on the column aid? And sure enough, on the left below my DDL is missing an index on the aid column, and the DDL on the right contains the new index that fixes the problem.<br />
<span id="docs-internal-guid-d60e2e24-0394-ba8d-0c20-2c5931055484"><br /></span>
<br />
<div dir="ltr" style="margin-left: 0pt;">
<table style="border-collapse: collapse; border: none; width: 468pt;"><colgroup><col width="*"></col><col width="*"></col></colgroup><tbody>
<tr style="height: 0pt;"><td style="border-bottom: solid #000000 1pt; border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-top: solid #000000 1pt; padding: 5pt 5pt 5pt 5pt; vertical-align: top;"><div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">CREATE TABLE HISTORY (</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> hid bigint not null,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> tid int ,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> bid int,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> aid int,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> delta int,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> mtime timestamp,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> filler char(22) );</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">ALTER TABLE HISTORY add primary key (hid);</span></div>
</td><td style="border-bottom: solid #000000 1pt; border-left: solid #000000 1pt; border-right: solid #000000 1pt; border-top: solid #000000 1pt; padding: 5pt 5pt 5pt 5pt; vertical-align: top;"><div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">CREATE TABLE HISTORY (</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> hid bigint not null,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> tid int ,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> bid int,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> aid int,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> delta int,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> mtime timestamp,</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"> filler char(22) );</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">ALTER TABLE HISTORY add primary key (hid);</span></div>
<div dir="ltr" style="line-height: 1.2; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: yellow; color: black; font-family: "arial"; font-size: 11pt; font-style: normal; font-variant: normal; font-weight: 400; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;">CREATE INDEX HIST_ACCOUNT ON HISTORY(aid);</span></div>
</td></tr>
</tbody></table>
</div>
<div dir="ltr" style="margin-left: 0pt;">
Once the new DDL has been committed, the execution plan should specify the name of the index it uses to process the WHERE aid = ? instead of saying "tableScan". So, the "HIST_ACCOUNT" index name used above (in yellow) should show up in the execution plan. Let's check.</div>
<div dir="ltr" style="margin-left: 0pt;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-yTQbQDKp9hgLo2Xdoc12GleP6bTN7ttk_Sp6574nrP1oxW7SPCAwEeZaEoYDqQ2dY6mYINfNFtNF1neFOZZXmgP7BP8Bk1IxpLxBViEl18t8-meS-P3WgVA89ZqB43dSoAduNkmfW5U/s1600/h2-explain-plan.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="430" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh-yTQbQDKp9hgLo2Xdoc12GleP6bTN7ttk_Sp6574nrP1oxW7SPCAwEeZaEoYDqQ2dY6mYINfNFtNF1neFOZZXmgP7BP8Bk1IxpLxBViEl18t8-meS-P3WgVA89ZqB43dSoAduNkmfW5U/s640/h2-explain-plan.png" width="640" /></a></div>
<div dir="ltr" style="margin-left: 0pt;">
<br /></div>
<div dir="ltr" style="margin-left: 0pt;">
And sure enough, its there! The "tableScan" has been replaced with this:</div>
<div dir="ltr" style="margin-left: 0pt;">
<span style="font-family: "courier new" , "courier" , monospace;"><br class="Apple-interchange-newline" /></span>
<br />
<blockquote class="tr_bq">
<span style="font-family: "courier new" , "courier" , monospace;">/* S02.HIST_ACC</span><span style="font-family: "courier new" , "courier" , monospace;">OUNT: AID = 235</span><span style="font-family: "courier new" , "courier" , monospace;"> */</span></blockquote>
</div>
<div dir="ltr" style="margin-left: 0pt;">
Now, lets see whether the new index improved performance. I ran the test again, and here is the glowroot data:</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhG5jTqbCqIabDaR_p29A7hfKO45HLAbruFsMkIL6vE1sAI7RxIH1It5wgkgMMIGC_0zU3N_ygqlE8ASA4gidQmCdakTeuMyauNK7Rgs4brnZweRym47_dMidGHnxQZ4O1AC3OYNVbV_Iw/s1600/glowroot_sql-rt-improved.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="208" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhG5jTqbCqIabDaR_p29A7hfKO45HLAbruFsMkIL6vE1sAI7RxIH1It5wgkgMMIGC_0zU3N_ygqlE8ASA4gidQmCdakTeuMyauNK7Rgs4brnZweRym47_dMidGHnxQZ4O1AC3OYNVbV_Iw/s400/glowroot_sql-rt-improved.png" width="400" /></a></div>
<div dir="ltr" style="margin-left: 0pt;">
Sure enough, the "SELECT hid from HISTORY" query now has 0.21ms response time. Before adding the index, it was 358.5ms, which is more than 350ms slower.<br />
<br />
If getting rid of the tableScan does not improve query response time, check out <a href="http://www.h2database.com/html/performance.html" target="_blank">this H2 performance page</a>.</div>
<div dir="ltr" style="margin-left: 0pt;">
<br /></div>
<div dir="ltr" style="margin-left: 0pt;">
So here is the summary, and whether you are using H2, Oracle, DB2, SQL Server Postgres or whatever, the steps are roughly the same.</div>
<div dir="ltr" style="margin-left: 0pt;">
<ol>
<li>Run the "EXPLAIN" to get the execution plan of the query.</li>
<li>Check for any "table scan" or "full table scan" in the execution plan.</li>
<li>Find what index is missing, and add it in the DDL and re-run the DDL to recreate the table. Columns in the WHERE clause and in any JOIN clauses are good candidates for indexes.</li>
<li>Re-run the "EXPLAIN" to make sure the "tableScan" is replaced by the name of the index that you added.</li>
<li>Re-test your query to see if execution response time improves.</li>
</ol>
</div>
<div dir="ltr" style="margin-left: 0pt;">
NOTE: The schema names in my screenshots and text are a bit messed up (sometimes s01, sometimes s02) because of some oddities in my environment.</div>
Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-76827312350845119292017-04-23T18:28:00.001-07:002017-05-28T10:17:29.874-07:00The Math Behind Manual Thread Dump Profiling<div style="background-color: white;">
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div>
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c"></span><br />
<div dir="ltr" style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px; line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">“Manual Thread Dump Sampling” for Java uses simple thread dumps like a mini Java profiler. This little-known and low-overhead approach to capturing performance data is extremely effective, especially considering that Java Profilers are not welcome in production, user acceptance, and many other computing environments.</span></span></div>
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c">
</span>
<br />
<div dir="ltr" style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px; line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;"><br /></span></span></div>
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c">
</span>
<br />
<div dir="ltr" style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px; line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c"><span style="background-color: transparent; color: black; font-family: "arial"; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;"> The instructions are surprisingly (perhaps shockingly) basic.</span></span></div>
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c">
</span><br />
<ol style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px; margin-bottom: 0pt; margin-top: 0pt;"><span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c">
<li dir="ltr" style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; list-style-type: decimal; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">Apply load.</span></div>
</li>
<li dir="ltr" style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; list-style-type: decimal; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">Using JStack, take about 4 thread dumps, a few seconds between each dump.</span></div>
</li>
<li dir="ltr" style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; list-style-type: decimal; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">if you see something that you could fix….</span></div>
</li>
<ol style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; list-style-type: lower-alpha; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">...and it shows up on two+ stacktraces, ones that are actually under load,</span></div>
</li>
<li dir="ltr" style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; list-style-type: lower-alpha; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">...then it is worth fixing</span></div>
</li>
</ol>
<li dir="ltr" style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; list-style-type: decimal; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="background-color: transparent; font-size: 11pt; vertical-align: baseline; white-space: pre-wrap;">As you peruse the thread dump in your favorite text editor, it is often helpful to only include that stacktraces that include activity from your package space.</span></div>
</li>
</span></ol>
<span id="docs-internal-guid-b589a0f5-9d77-4bec-c9f0-e781933e7b6c">
<div>
<span style="font-family: "arial";"><span style="font-size: 14.6667px; white-space: pre-wrap;"><br /></span></span></div>
<div>
<span style="font-family: "arial";"><span style="font-size: 14.6667px; white-space: pre-wrap;">Here is <a href="https://github.com/eostermueller/littleMock" target="_blank">a little server-side Java application</a> I've put together to demonstrate this technique.</span></span></div>
<div>
<span style="font-family: "arial";"><span style="font-size: 14.6667px; white-space: pre-wrap;"><br /></span></span>
<span style="font-family: "arial"; font-size: 14.6667px; white-space: pre-wrap;">I use this technique in my day job at least a few times a week -- so the demo is more than enough of an explanation for me. But if you are moved by a more detailed, math-based explanations for why its possible to glean actionable performance data from such a small number of samples, then perhaps the following two pieces will help.</span><br />
<span style="font-family: "arial"; font-size: 14.6667px; white-space: pre-wrap;"><br /></span>
<span style="font-family: "arial"; font-size: 14.6667px; white-space: pre-wrap;">The first piece is by Mike Dunlavey, author of <a href="https://books.google.com/books?id=8A43E1UFs_YC&printsec=frontcover&dq=mike+dunlavey&hl=en&sa=X&ved=0ahUKEwisjubd97vTAhUD6mMKHVWSBrIQ6AEIJTAA#v=onepage&q=mike%20dunlavey&f=false" target="_blank">this book</a>, which is a bit dated. He wrote the following math-based defense of this approach. Note that he uses the term "random pausing" instead of the java-focused that I've landed on ("Manual Thread Dump Sampling"). </span><span style="font-family: "arial";"><span style="font-size: 14.6667px; white-space: pre-wrap;">Although I didn't learn this technique from Mike Dunlavey, he certainly seems to be </span></span><span style="font-family: "arial"; font-size: 14.6667px; white-space: pre-wrap;">the first one to document this approach -- not for Java, but for C and C++. The text for his section was taken <a href="https://scicomp.stackexchange.com/questions/2173/what-are-some-good-strategies-for-improving-the-serial-performance-of-my-code/2719#2719" target="_blank">from here</a>.</span><br />
<span style="font-family: "arial"; font-size: 14.6667px; white-space: pre-wrap;"><br /></span>
<span style="font-family: "arial"; font-size: 14.6667px; white-space: pre-wrap;">The second piece is from <a href="http://asmsa.org/contact-us/faculty-staff-directory/66" target="_blank">Nick Seward</a>, a great STEM teacher (with some <a href="http://asmsa.org/news-events/164/in-realistic-3d-instructors-printer-gaining-international-notice" target="_blank">interesting</a> <a href="http://conceptforge.org/" target="_blank">creds</a>) from <a href="http://asmsa.org/" target="_blank">an extraordinary high school</a>, where my 17 year old attends.</span><br />
<br /></div>
<h2>
<span style="font-family: "arial"; font-size: large; white-space: pre-wrap;">Mike Dunlavey</span></h2>
</span></div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
Scientific software is not that much different from other software, as far as how to know what needs tuning.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
The method I use is <a href="http://stackoverflow.com/a/378024/23771" style="border: 0px; color: #18529a; cursor: pointer; margin: 0px; padding: 0px; text-decoration-line: none;"><em style="border: 0px; margin: 0px; padding: 0px;">random pausing</em></a>. Here are some of the speedups it has found for me:</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
If a large fraction of time is spent in functions like <code style="background-color: #eff0f1; border: 0px; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; margin: 0px; padding: 1px 5px; white-space: pre-wrap;">log</code> and <code style="background-color: #eff0f1; border: 0px; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; margin: 0px; padding: 1px 5px; white-space: pre-wrap;">exp</code>, I can see what the arguments to those functions are, as a function of the points they are being called from. Often they are being called repeatedly with the same argument. If so, memoizing produces a massive speedup factor.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
If I'm using BLAS or LAPACK functions, I may find that a large fraction of time is spent in routines to copy arrays, multiply matrices, choleski transform, etc.</div>
<ul style="border: 0px; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin: 0px 0px 1em 30px; padding: 0px;">
<li style="border: 0px; margin: 0px 0px 0.5em; padding: 0px; word-wrap: break-word;"><div style="border: 0px; clear: both; padding: 0px;">
The routine to copy arrays is not there for speed, it is there for convenience. You may find there is a less convenient, but faster, way to do it.</div>
</li>
<li style="border: 0px; margin: 0px; padding: 0px; word-wrap: break-word;"><div style="border: 0px; clear: both; padding: 0px;">
Routines to multiply or invert matrices, or take choleski transforms, tend to have character arguments specifying options, such as 'U' or 'L' for upper or lower triangle. Again, those are there for convenience. What I found was, since my matrices were not very big, the routines were spending more than half their time calling the subroutine for <em style="border: 0px; margin: 0px; padding: 0px;">comparing characters</em> just to decipher the options. Writing special-purpose versions of the most costly math routines produced massive speedup.</div>
</li>
</ul>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
If I can just expand on the latter: matrix-multiply routine DGEMM calls LSAME to decode its character arguments. Looking at inclusive percent time (the only statistic worth looking at) profilers regarded as "good" could show DGEMM using some percent of total time, like 80%, and LSAME using some percent of total time, like 50%. Looking at the former, you would be tempted to say "well it must be heavily optimized, so not much I can do about that". Looking at the latter, you would be tempted to say "Huh? What's that all about? That's just a teeny little routine. This profiler must be wrong!"</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
It's not wrong, it's just not telling you what you need to know. What random pausing shows you is that DGEMM is on 80% of stack samples, and LSAME is on 50%. (You don't need a lot of samples to detect that. 10 is usually plenty.) What's more, on many of those samples, DGEMM is <em style="border: 0px; margin: 0px; padding: 0px;">in the process of calling LSAME</em> from a couple different lines of code.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
So now you know why <em style="border: 0px; margin: 0px; padding: 0px;">both</em> routines are taking so much inclusive time. You also know where in <em style="border: 0px; margin: 0px; padding: 0px;">your code</em> they are being called from to spend all this time. That's why I use random pausing and take a jaundiced view of profilers, no matter how well-made they are. They're more interested in getting measurements than in telling you what's going on.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
It's easy to assume the math library routines have been optimized to the nth degree, but in fact they have been optimized to be usable for a wide range of purposes. You need to see what's <em style="border: 0px; margin: 0px; padding: 0px;">really</em> going on, not what is easy to assume.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
ADDED: So to answer your last two questions:</div>
<blockquote style="background-color: #fff9e3; border-bottom-color: initial; border-bottom-style: initial; border-image: initial; border-left-color: rgb(255, 235, 142); border-left-style: solid; border-right-color: initial; border-right-style: initial; border-top-color: initial; border-top-style: initial; border-width: 0px 0px 0px 2px; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin: 0px 0px 10px; padding: 10px; quotes: none;">
<div style="border: 0px; clear: both; padding: 0px;">
What are the most important things to try first?</div>
</blockquote>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
Take 10-20 stack samples, and don't just summarize them, understand what each one is telling you. Do this first, last, and in-between. <em style="border: 0px; margin: 0px; padding: 0px;">(There is no "try", young Skywalker.)</em></div>
<blockquote style="background-color: #fff9e3; border-bottom-color: initial; border-bottom-style: initial; border-image: initial; border-left-color: rgb(255, 235, 142); border-left-style: solid; border-right-color: initial; border-right-style: initial; border-top-color: initial; border-top-style: initial; border-width: 0px 0px 0px 2px; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin: 0px 0px 10px; padding: 10px; quotes: none;">
<div style="border: 0px; clear: both; padding: 0px;">
How do I know how much performance I can get?</div>
</blockquote>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
The stack samples will give you a very rough estimate of what fraction <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-1-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-1" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-2" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-3" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span> of time will be saved. (It follows a <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B2;</mi><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo>,</mo><mo stretchy="false">(</mo><mi>n</mi><mo>&#x2212;</mo><mi>s</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></math>" id="MathJax-Element-2-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-4" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 9.947em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 8.281em;"><span style="border: 0px; clip: rect(1.669em 1008.23em 2.892em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-5" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-6" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">β<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-7" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-8" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-9" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-10" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-11" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">,</span><span class="mo" id="MathJax-Span-12" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.169em; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-13" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span><span class="mo" id="MathJax-Span-14" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">−</span><span class="mi" id="MathJax-Span-15" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-16" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span><span class="mo" id="MathJax-Span-17" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-18" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-19" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.203em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>β</mi><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo>,</mo><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mi>s</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></math></span></span> distribution, where <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math>" id="MathJax-Element-3-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-20" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.503em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.392em;"><span style="border: 0px; clip: rect(1.892em 1000.39em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-21" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-22" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math></span></span> is the number of samples that displayed what you are going to fix, and <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>" id="MathJax-Element-4-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-23" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.614em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.503em;"><span style="border: 0px; clip: rect(1.892em 1000.5em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-24" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-25" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math></span></span> is the total number of samples. That doesn't count the cost of the code that you used to replace it, which will hopefully be small.) Then the speedup ratio is <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mn>1</mn><mo>&#x2212;</mo><mi>x</mi><mo stretchy="false">)</mo></math>" id="MathJax-Element-5-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-26" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 4.336em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 3.614em;"><span style="border: 0px; clip: rect(1.669em 1003.56em 2.836em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-27" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mn" id="MathJax-Span-28" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">1</span><span class="texatom" id="MathJax-Span-29" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-30" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-31" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">/</span></span></span><span class="mo" id="MathJax-Span-32" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mn" id="MathJax-Span-33" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-34" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">−</span><span class="mi" id="MathJax-Span-35" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-36" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.137em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.263em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>x</mi><mo stretchy="false">)</mo></math></span></span>which can be large. Notice how this behaves mathematically. If <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>=</mo><mn>10</mn></math>" id="MathJax-Element-6-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-37" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 3.447em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 2.836em;"><span style="border: 0px; clip: rect(1.669em 1002.84em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-38" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-39" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span><span class="mo" id="MathJax-Span-40" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">=</span><span class="mn" id="MathJax-Span-41" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">10</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.937em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>=</mo><mn>10</mn></math></span></span>, and <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi><mo>=</mo><mn>5</mn></math>" id="MathJax-Element-7-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-42" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 2.669em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 2.225em;"><span style="border: 0px; clip: rect(1.669em 1002.17em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-43" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-44" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-45" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">=</span><span class="mn" id="MathJax-Span-46" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">5</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.003em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi><mo>=</mo><mn>5</mn></math></span></span>, the mean and mode of <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-8-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-47" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-48" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-49" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span> is 0.5, for a speedup ratio of 2. Here's the distribution:<br />
<img alt="enter image description here" src="https://i.stack.imgur.com/byABj.jpg" style="border: 0px; margin: 0px; max-width: 100%; padding: 0px;" /><br />
If you are risk-averse then, yes, there is a small probability (.03%) that <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-9-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-50" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-51" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-52" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span> is less than 0.1, for a speedup of less than 11%. But balancing that is an equal probability that <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-10-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-53" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-54" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-55" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span> is greater than 0.9, for a speedup ratio of greater than 10! If you're getting money in proportion to program speed, that's not bad odds.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
As I've pointed out to you before, you can repeat the whole procedure until you can't any more, and the compounded speedup ratio can be quite large.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
ADDED: In response to Pedro's concern about false positives, let me try to construct an example where they might be expected to occur. We never act on a potential problem unless we see it two or more times, so we would expect false positives to occur when we see a problem the fewest possible times, especially when the total number of samples is large. Suppose we take 20 samples and see it twice. That estimates its cost is 10% of total execution time, the mode of its distribution. (The mean of the distribution is higher - it is <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mn>3</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>22</mn><mo>=</mo><mn>13.6</mn><mi mathvariant="normal">&#x0025;</mi></math>" id="MathJax-Element-11-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-56" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 15.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 12.947em;"><span style="border: 0px; clip: rect(1.614em 1012.89em 2.836em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-57" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-58" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-59" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-60" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-61" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-62" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span><span class="texatom" id="MathJax-Span-63" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-64" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-65" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">/</span></span></span><span class="mo" id="MathJax-Span-66" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-67" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span><span class="mo" id="MathJax-Span-68" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-69" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">2</span><span class="mo" id="MathJax-Span-70" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span><span class="mo" id="MathJax-Span-71" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">=</span><span class="mn" id="MathJax-Span-72" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">3</span><span class="texatom" id="MathJax-Span-73" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-74" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-75" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">/</span></span></span><span class="mn" id="MathJax-Span-76" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">22</span><span class="mo" id="MathJax-Span-77" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">=</span><span class="mn" id="MathJax-Span-78" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">13.6</span><span class="mi" id="MathJax-Span-79" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">%</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.203em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.263em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mn>3</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>22</mn><mo>=</mo><mn>13.6</mn><mi mathvariant="normal">%</mi></math></span></span>.) The lower curve in the following graph is its distribution:</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
<img alt="enter image description here" src="https://i.stack.imgur.com/EQIw5.jpg" style="border: 0px; margin: 0px; max-width: 100%; padding: 0px;" /></div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
Consider if we took as many as 40 samples (more than I ever have at one time) and only saw a problem on two of them. The estimated cost (mode) of that problem is 5%, as shown on the taller curve.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
What is a "false positive"? It is that if you fix a problem you realize such a smaller gain than expected, that you regret having fixed it. The curves show (if the problem is "small") that, while the gain <em style="border: 0px; margin: 0px; padding: 0px;">could</em> be less than the fraction of samples showing it, on average it will be larger.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
There is a far more serious risk - a "false negative". That is when there is a problem, but it is not found. (Contributing to this is "confirmation bias", where absence of evidence tends to be treated as evidence of absence.)</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
What you get with a profiler (a good one) is you get much more precise measurement (thus less chance of false positives), at the expense of much less precise information about what the problem actually <em style="border: 0px; margin: 0px; padding: 0px;">is</em> (thus less chance of finding it and getting <em style="border: 0px; margin: 0px; padding: 0px;">any</em> gain). That limits the overall speedup that can be achieved.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
I would encourage users of profilers to report the speedup factors they actually get in practice.</div>
<hr style="background-color: #d6d9dc; border: 0px; color: #d6d9dc; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; height: 1px; margin-bottom: 20px;" />
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
There's another point to be made re. Pedro's question about false positives.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
He mentioned there could be a difficulty when getting down to small problems in highly optimized code. (To me, a small problem is one that accounts for 5% or less of total time.)</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
Since it is entirely possible to construct a program that is totally optimal except for 5%, this point can only be addressed empirically, as in <a href="https://scicomp.stackexchange.com/a/1870/1262" style="border: 0px; color: #18529a; cursor: pointer; margin: 0px; padding: 0px; text-decoration-line: none;"><em style="border: 0px; margin: 0px; padding: 0px;">this answer</em></a>. To generalize from empirical experience, it goes like this:</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
A program, as written, typically contains several opportunities for optimization. (We can call them "problems" but they are often perfectly good code, simply capable of considerable improvement.) This diagram illustrates an artificial program taking some length of time (100s, say), and it contains problems A, B, C, ... that, when found and fixed, save 30%, 21%, etc. of the original 100s.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
<img alt="enter image description here" src="https://i.stack.imgur.com/8RmbL.jpg" style="border: 0px; margin: 0px; max-width: 100%; padding: 0px;" /></div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
Notice that problem F costs 5% of the original time, so it is "small", and difficult to find without 40 or more samples.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
However, the first 10 samples easily find problem A.** When that is fixed, the program takes only 70s, for a speedup of 100/70 = 1.43x. That not only makes the program faster, it magnifies, by that ratio, the percentages taken by the remaining problems. For example, problem B originally took 21s which was 21% of the total, but after removing A, B takes 21s out of 70s, or 30%, so it is easier to find when the entire process is repeated.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
Once the process is repeated five times, now the execution time is 16.8s, out of which problem F is 30%, not 5%, so 10 samples find it easily.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
So that's the point. Empirically, programs contain a series of problems having a distribution of sizes, and any problem found and fixed makes it easier to find the remaining ones. In order to accomplish this, none of the problems can be skipped because, if they are, they sit there taking time, limiting the total speedup, and failing to magnify the remaining problems. <em style="border: 0px; margin: 0px; padding: 0px;">That's why it is very important to find the problems that are <strong style="border: 0px; margin: 0px; padding: 0px;">hiding</strong>.</em></div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
If problems A through F are found and fixed, the speedup is 100/11.8 = 8.5x. If one of them is missed, for example D, then the speedup is only 100/(11.8+10.3) = 4.5x. <em style="border: 0px; margin: 0px; padding: 0px;">That's the price paid for false negatives.</em></div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
So, when the profiler says "there doesn't seem to be any significant problem here" (i.e. good coder, this is practically optimal code), maybe it's right, and maybe it's not. (A <em style="border: 0px; margin: 0px; padding: 0px;">false negative</em>.) You don't know for sure if there are more problems to fix, for higher speedup, unless you try another profiling method and discover that there are. In my experience, the profiling method does not need a large number of samples, summarized, but a small number of samples, where each sample is understood thoroughly enough to recognize any opportunity for optimization.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
** It takes a minimum of 2 hits on a problem to find it, unless one has prior knowledge that there is a (near) infinite loop. (The red tick marks represent 10 random samples); The average number of samples needed to get 2 or more hits, when the problem is 30%, is <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>0.3</mn><mo>=</mo><mn>6.67</mn></math>" id="MathJax-Element-12-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-80" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 6.169em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 5.114em;"><span style="border: 0px; clip: rect(1.669em 1005.06em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-81" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mn" id="MathJax-Span-82" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">2</span><span class="texatom" id="MathJax-Span-83" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-84" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-85" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">/</span></span></span><span class="mn" id="MathJax-Span-86" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">0.3</span><span class="mo" id="MathJax-Span-87" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">=</span><span class="mn" id="MathJax-Span-88" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">6.67</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.003em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>2</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mn>0.3</mn><mo>=</mo><mn>6.67</mn></math></span></span> (<a href="http://en.wikipedia.org/wiki/Negative_binomial_distribution" rel="nofollow noreferrer" style="border: 0px; color: #18529a; cursor: pointer; margin: 0px; padding: 0px; text-decoration-line: none;">negative binomial distribution</a>). 10 samples find it with 85% probability, 20 samples - 99.2% (<a href="http://en.wikipedia.org/wiki/Binomial_distribution" rel="nofollow noreferrer" style="border: 0px; color: #18529a; cursor: pointer; margin: 0px; padding: 0px; text-decoration-line: none;">binomial distribution</a>). To get the probability of finding the problem, in R, evaluate <code style="background-color: #eff0f1; border: 0px; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; margin: 0px; padding: 1px 5px; white-space: pre-wrap;">1 - pbinom(1, numberOfSamples, sizeOfProblem)</code>, for example: <code style="background-color: #eff0f1; border: 0px; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; margin: 0px; padding: 1px 5px; white-space: pre-wrap;">1 - pbinom(1, 20, 0.3) = 0.9923627</code>.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
ADDED: The fraction of time saved, <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-13-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-89" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-90" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-91" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span>, follows a Beta distribution <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#x03B2;</mi><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo>,</mo><mo stretchy="false">(</mo><mi>n</mi><mo>&#x2212;</mo><mi>s</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></math>" id="MathJax-Element-14-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-92" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 9.947em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 8.281em;"><span style="border: 0px; clip: rect(1.669em 1008.23em 2.892em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-93" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-94" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">β<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-95" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-96" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-97" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-98" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-99" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">,</span><span class="mo" id="MathJax-Span-100" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.169em; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-101" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span><span class="mo" id="MathJax-Span-102" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">−</span><span class="mi" id="MathJax-Span-103" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-104" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span><span class="mo" id="MathJax-Span-105" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-106" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-107" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.203em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>β</mi><mo stretchy="false">(</mo><mi>s</mi><mo>+</mo><mn>1</mn><mo>,</mo><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mi>s</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></math></span></span>, where <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>" id="MathJax-Element-15-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-108" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.614em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.503em;"><span style="border: 0px; clip: rect(1.892em 1000.5em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-109" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-110" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math></span></span> is the number of samples, and <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math>" id="MathJax-Element-16-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-111" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.503em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.392em;"><span style="border: 0px; clip: rect(1.892em 1000.39em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-112" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-113" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi></math></span></span> is the number that display the problem. However, the speedup ratio <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math>" id="MathJax-Element-17-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-114" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.892em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-115" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-116" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">y</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.937em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math></span></span>equals <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mn>1</mn><mo>&#x2212;</mo><mi>x</mi><mo stretchy="false">)</mo></math>" id="MathJax-Element-18-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-117" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 4.336em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 3.614em;"><span style="border: 0px; clip: rect(1.669em 1003.56em 2.836em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-118" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mn" id="MathJax-Span-119" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">1</span><span class="texatom" id="MathJax-Span-120" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-121" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-122" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">/</span></span></span><span class="mo" id="MathJax-Span-123" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mn" id="MathJax-Span-124" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-125" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">−</span><span class="mi" id="MathJax-Span-126" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span><span class="mo" id="MathJax-Span-127" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.137em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.263em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mn>1</mn><mo>−</mo><mi>x</mi><mo stretchy="false">)</mo></math></span></span> (assuming all of <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math>" id="MathJax-Element-19-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-128" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-129" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-130" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">x<span style="border: 0px; display: inline-block; height: 1px; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.003em;"></span></span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>x</mi></math></span></span> is saved), and it would be interesting to understand the distribution of <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math>" id="MathJax-Element-20-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-131" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.892em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-132" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-133" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">y</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.937em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math></span></span>. It turns out <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo>&#x2212;</mo><mn>1</mn></math>" id="MathJax-Element-21-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-134" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 2.614em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 2.169em;"><span style="border: 0px; clip: rect(1.669em 1002.06em 2.892em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-135" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-136" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">y</span><span class="mo" id="MathJax-Span-137" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">−</span><span class="mn" id="MathJax-Span-138" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.203em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi><mo>−</mo><mn>1</mn></math></span></span> follows a <a href="http://en.wikipedia.org/wiki/Beta_prime_distribution" rel="nofollow noreferrer" style="border: 0px; color: #18529a; cursor: pointer; margin: 0px; padding: 0px; text-decoration-line: none;"><em style="border: 0px; margin: 0px; padding: 0px;">BetaPrime</em></a> distribution. I simulated it with 2 million samples, arriving at this behavior:</div>
<pre style="background-color: #eff0f1; border: 0px; color: #242729; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; font-size: 13px; margin-bottom: 1em; max-height: 600px; overflow: auto; padding: 5px; width: auto; word-wrap: normal;"><code style="border: 0px; font-family: Consolas, Menlo, Monaco, "Lucida Console", "Liberation Mono", "DejaVu Sans Mono", "Bitstream Vera Sans Mono", "Courier New", monospace, sans-serif; margin: 0px; padding: 0px; white-space: inherit;"> distribution of speedup
ratio y
s, n 5%-ile 95%-ile mean
2, 2 1.58 59.30 32.36
2, 3 1.33 10.25 4.00
2, 4 1.23 5.28 2.50
2, 5 1.18 3.69 2.00
2,10 1.09 1.89 1.37
2,20 1.04 1.37 1.17
2,40 1.02 1.17 1.08
3, 3 1.90 78.34 42.94
3, 4 1.52 13.10 5.00
3, 5 1.37 6.53 3.00
3,10 1.16 2.29 1.57
3,20 1.07 1.49 1.24
3,40 1.04 1.22 1.11
4, 4 2.22 98.02 52.36
4, 5 1.72 15.95 6.00
4,10 1.25 2.86 1.83
4,20 1.11 1.62 1.31
4,40 1.05 1.26 1.14
5, 5 2.54 117.27 64.29
5,10 1.37 3.69 2.20
5,20 1.15 1.78 1.40
5,40 1.07 1.31 1.17
</code></pre>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
The first two columns give the 90% confidence interval for the speedup ratio. The mean speedup ratio equals <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mi>n</mi><mo>&#x2212;</mo><mi>s</mi><mo stretchy="false">)</mo></math>" id="MathJax-Element-22-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-139" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 7.225em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 6.003em;"><span style="border: 0px; clip: rect(1.669em 1005.95em 2.836em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-140" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-141" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-142" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span><span class="mo" id="MathJax-Span-143" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">+</span><span class="mn" id="MathJax-Span-144" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">1</span><span class="mo" id="MathJax-Span-145" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span><span class="texatom" id="MathJax-Span-146" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-147" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mo" id="MathJax-Span-148" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">/</span></span></span><span class="mo" id="MathJax-Span-149" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">(</span><span class="mi" id="MathJax-Span-150" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">n</span><span class="mo" id="MathJax-Span-151" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">−</span><span class="mi" id="MathJax-Span-152" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.281em; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-153" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">)</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 1.137em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.263em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mrow class="MJX-TeXAtom-ORD"><mo>/</mo></mrow><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mi>s</mi><mo stretchy="false">)</mo></math></span></span> except for the case where <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi><mo>=</mo><mi>n</mi></math>" id="MathJax-Element-23-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-154" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 2.669em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 2.225em;"><span style="border: 0px; clip: rect(1.892em 1002.23em 2.669em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-155" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-156" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">s</span><span class="mo" id="MathJax-Span-157" style="border: 0px; display: inline; font-family: STIXGeneral-Regular; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">=</span><span class="mi" id="MathJax-Span-158" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px 0px 0px 0.336em; position: static; transition: none; vertical-align: 0px;">n</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.67em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.063em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>s</mi><mo>=</mo><mi>n</mi></math></span></span>. In that case it is undefined and, indeed, as I increase the number of simulated <span class="MathJax" data-mathml="<math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math>" id="MathJax-Element-24-Frame" role="presentation" style="border: 0px; direction: ltr; display: inline; float: none; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; position: relative; white-space: nowrap; word-spacing: normal; word-wrap: normal;" tabindex="0"><nobr aria-hidden="true" style="border: 0px; line-height: normal; margin: 0px; max-height: none; max-width: none; min-height: 0px; min-width: 0px; padding: 0px; transition: none; vertical-align: 0px;"><span class="math" id="MathJax-Span-159" style="border: 0px; display: inline-block; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0.558em;"><span style="border: 0px; display: inline-block; font-size: 18px; height: 0px; line-height: normal; margin: 0px; padding: 0px; position: relative; transition: none; vertical-align: 0px; width: 0.447em;"><span style="border: 0px; clip: rect(1.892em 1000.45em 2.892em -999.997em); left: 0em; line-height: normal; margin: 0px; padding: 0px; position: absolute; top: -2.497em; transition: none; vertical-align: 0px;"><span class="mrow" id="MathJax-Span-160" style="border: 0px; display: inline; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;"><span class="mi" id="MathJax-Span-161" style="border: 0px; display: inline; font-family: STIXGeneral-Italic; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px;">y</span></span><span style="border: 0px; display: inline-block; height: 2.503em; line-height: normal; margin: 0px; padding: 0px; position: static; transition: none; vertical-align: 0px; width: 0px;"></span></span></span><span style="border-bottom-style: initial; border-color: initial; border-image: initial; border-left-style: solid; border-right-style: initial; border-top-style: initial; border-width: 0px; display: inline-block; height: 0.937em; line-height: normal; margin: 0px; overflow: hidden; padding: 0px; position: static; transition: none; vertical-align: -0.33em; width: 0px;"></span></span></nobr><span class="MJX_Assistive_MathML" role="presentation" style="border: 0px; clip: rect(1px 1px 1px 1px); display: inline; height: 1px !important; left: 0px; line-height: normal; margin: 0px; overflow: hidden !important; padding: 0px; position: static; top: 0px; transition: none; user-select: none; vertical-align: 0px; width: 1px !important;"><math xmlns="http://www.w3.org/1998/Math/MathML"><mi>y</mi></math></span></span> values, the empirical mean increases.</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
This is a plot of the distribution of the speedup factors, and their means, for 2 hits out of 5, 4, 3, and 2 samples. For example, if 3 samples are taken, and 2 of them are hits on a problem, and that problem can be removed, the average speedup factor would be 4x. If the 2 hits are seen in only 2 samples, the average speedup is undefined - conceptually because programs with infinite loops exist with non-zero probability!</div>
<div style="border: 0px; clear: both; color: #242729; font-family: Arial, "Helvetica Neue", Helvetica, sans-serif; font-size: 15px; margin-bottom: 1em; padding: 0px;">
<img alt="enter image description here" src="https://i.stack.imgur.com/pZ9Q9.jpg" style="border: 0px; margin: 0px; max-width: 100%; padding: 0px;" /></div>
</div>
<h2 style="color: #222222; font-family: arial, sans-serif;">
<span style="font-size: large;">
Nick Seward</span></h2>
<ul style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<li>It doesn't seem like this would help you if all of your functions used the same amount of time. The worst case scenario is that all of your functions can be optimized equally.</li>
<li>This does work well with the assumption that one of your functions will dominate (not a bad assumption). The question is how well will it capture that with 10 samples. Say that the ground truth is that it takes up 30% of the CPU time. Ideally we would want 3 of the random samples to reflect this. Using the binomial distribution, there is a 60% chance of seeing it 3 or more time, 85% for 2 or more, and 97% for 1 or more. That leaves you with a 3% chance of missing it all together. </li>
<li>I would guess the items up for optimization usually take more than 30% of the time so this approach is even better.</li>
</ul>
</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
If something is to be flagged for a look it will need to show up. So with my above example there is a 3% chance that it won't get flagged. If you bump that to 15 samples then the chance of missing it goes to 0.5%. I would think of it as flipping a coin. What is the chance of getting tails over and over. The more you flip it...the less likely. If all you are looking for is identification then this is great. If you actually want to know exactly how much time is spent in each function then this isn't good enough. It seems like he proposes looking closely at all 10 samples in the hopes of finding something to optimize. I would personally do more samples (say 20) and only look at samples that show up more than once to minimize false positives.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
So to hopefully putting this more clearly, it isn't claiming that it can get accurate results with just 10 samples. It is claiming that a problem can be found with great certainty if it takes a reasonable fraction of the execution time. You can fix the problem which in turn exposes the next problem to this 10 sample technique. If you are only worried about problems taking 30% of the time and 3% chance of not finding it is okay then this is the way to go.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
Here is a formula that I would use</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
n=samples needed</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
e=acceptable chance of false negative (.005 would mean 0.5% chance of not finding the problem)</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
p=problem size(.3 would mean find problems that take over 30% of the execution time)</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
n>=log(e)/log(1-p)</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
For example: If you want a .1% chance of a false negative and the problem you are hunting take 5% of the runtime then you would need 135 samples. For 30% problems, you only need 30 samples. You have to be stalking a big problem.</div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
Below is a graph to tell you how many samples you need (for 30% problems) where a false negative is defined as getting less than k hits, where k is a positive integer. That IMHO allows you to switch from 10 samples that all require your inspection to more samples but less of them meet the k-hit requirement so the human gets to save time. I don't show it here but the ratio of false positive decrease as k increase. The false positives are actually minimized when e=0.05 for the 30% problem. </div>
<img alt="Inline image 1" class="CToWUd a6T" height="285" src="https://mail.google.com/mail/u/0/?ui=2&ik=d7b85b93ac&view=fimg&th=15a74281a1fc5a5e&attid=0.1&disp=emb&realattid=ii_15a741026c89f041&attbid=ANGjdJ9HB0hwIYYvM_zSxWAPxNJLtVCJtevS-9CpCHSwIW8J2wgZHv6SR3w1Stk5gx2duQRWeh_gyiozZg3LBwkkVat86SRbfftXfamgaVRMH9QPTaXZKQdTeZVvPLA&sz=w946-h570&ats=1492995021774&rm=15a74281a1fc5a5e&zw&atsh=1" style="background-color: white; color: #222222; cursor: pointer; font-family: arial, sans-serif; font-size: 12.8px; outline: 0px;" tabindex="0" width="473" /><br />
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
<br /></div>
<div style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">
In closing, with a small number of samples you can nearly guarantee that you will find a large enough problem. However, you will have to sort through many false positives. If more samples are cheap, get as many as is feasible and use the largest k that will give you an acceptable e. Doing this will have your false positives and false negatives trend towards zero. That said...the beauty of 10 samples is that it is easy to examine 10 places in your code.</div>
<div>
<br /></div>
Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-55868181136700730242016-03-12T15:23:00.003-08:002016-03-12T15:23:49.585-08:00Chatter about SELECT N+1Here is my little reference to conversations about the SELECT N+1 <a href="http://ostermueller.blogspot.com/2014/10/chatty-sql-performance-anti-patterns.html" target="_blank">SQL Performance Anti-Pattern</a><br />
<div class="wiki-content" id="main-content" style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px;">
<div style="margin-top: 10px;">
<a class="external-link" href="http://blog.jooq.org/tag/object-relational-mapping/" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank"><br class="Apple-interchange-newline" />http://blog.jooq.org/tag/object-relational-mapping/</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://stackoverflow.com/tags/select-n-plus-1/hot" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://stackoverflow.com/tags/select-n-plus-1/hot</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://stackoverflow.com/questions/97197/what-is-the-n1-selects-issue" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://stackoverflow.com/questions/97197/what-is-the-n1-selects-issue</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://use-the-index-luke.com/sql/join/nested-loops-join-n1-problem" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://use-the-index-luke.com/sql/join/nested-loops-join-n1-problem</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://thecuttingledge.com/?p=169" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://thecuttingledge.com/?p=169</a><br /><a class="external-link" href="http://ayende.com/blog/1328/combating-the-select-n-1-problem-in-nhibernate" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://ayende.com/blog/1328/combating-the-select-n-1-problem-in-nhibernate</a><br /><a class="external-link" href="http://pramatr.wordpress.com/2009/02/05/sql-n-1-selects-explained/" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://pramatr.wordpress.com/2009/02/05/sql-n-1-selects-explained/</a><br /><a class="external-link" href="http://docs.telerik.com/data-access/developers-guide/profiling-and-tuning/profiler-and-tuning-advisor/data-access-profiler-n-plus-one-problem" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://docs.telerik.com/data-access/developers-guide/profiling-and-tuning/profiler-and-tuning-advisor/data-access-profiler-n-plus-one-problem</a><br /><a class="external-link" href="http://www.hibernatingrhinos.com/products/nhprof/learn/alert/selectnplusone" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://www.hibernatingrhinos.com/products/nhprof/learn/alert/selectnplusone</a><br /><a class="external-link" href="http://www.pbell.com/index.cfm/2006/9/17/Understanding-the-n1-query-problem" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://www.pbell.com/index.cfm/2006/9/17/Understanding-the-n1-query-problem</a><br /><a class="external-link" href="http://dotnet.dzone.com/news/select-n1-problem-%E2%80%93-how" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://dotnet.dzone.com/news/select-n1-problem-%E2%80%93-how</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://java.dzone.com/articles/martin-fowler-orm-hate" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://java.dzone.com/articles/martin-fowler-orm-hate</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://learningviacode.blogspot.com/2012/07/the-n-1-select-problem-in-hibernate.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.com/2012/07/the-n-1-select-problem-in-hibernate.html</a><br /><a class="external-link" href="http://learningviacode.blogspot.com/2012/08/fetch-join-for-collection.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.com/2012/08/fetch-join-for-collection.html</a><br /><a class="external-link" href="http://learningviacode.blogspot.com/2012/08/fetch-subselect.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.com/2012/08/fetch-subselect.html</a><br /><a class="external-link" href="http://learningviacode.blogspot.sg/2012/08/batch-size-n.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.sg/2012/08/batch-size-n.html</a></div>
<div style="margin-top: 10px;">
<a class="external-link" href="http://learningviacode.blogspot.in/2012/07/lazyextra.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.in/2012/07/lazyextra.html</a></div>
<div style="margin-top: 10px;">
<br /></div>
</div>
<div id="likes-and-labels-container" style="background-color: white; clear: both; color: #333333; font-family: Arial, sans-serif; font-size: 13px; margin: 10px 0px; overflow: hidden; padding: 10px 0px;">
<div id="likes-section" style="float: left; width: 416.625px;">
</div>
</div>
Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-44325123756285428692014-11-16T13:56:00.000-08:002017-09-16T20:48:57.119-07:00The Worst Server Side Performance Problem<div class="tr_bq">
I've been working in software performance for the last 8 years, and by far the worst performance problem has been "too many database calls." But don't take my word for it. Here are some outside opinions from people who should know.</div>
<br />
Martin Fowler has written two books on the "<a href="http://stackoverflow.com/questions/1711/what-is-the-single-most-influential-book-every-programmer-should-read">Most Influential Book Every Programmer Should Read</a>" list. In 2003, he wrote,<br />
<br />
<blockquote class="tr_bq">
"Try to pull back multiple rows at once. In particular,<br />
never do repeated queries on the same table to get multiple rows." (<a href="http://www.informit.com/articles/article.aspx?p=30661&seqNum=3">link</a>). </blockquote>
<br />
He used the "never" word, but more than 10 years later, it is still common place for code to hit the same table multiple times when the end user makes a single click.<br />
<br />
Fast forward to 2010. <a href="http://www.dynatrace.com/">DynaTrace</a> is a .NET and Java monitoring tool that has seen lots of production action. Andi Grabner of DynaTrace put "too many database calls" at <a href="http://apmblog.compuware.com/2010/06/15/top-10-performance-problems-taken-from-zappos-monster-and-co/">number one</a> on the list of worst performance problems.<br />
<br />
Just a few years later in 2012, this problem shows up as #4 on <a href="http://java.dzone.com/articles/top-10-causes-java-ee">DZone's list</a> of biggest performance headaches: <br />
<blockquote class="tr_bq">
"Too many external system calls are performed in a synchronous and sequential manner."</blockquote>
<br />
When DynaTrace revised their list in 2013, client side performance problems were now the largest problem, but <a href="http://apmblog.compuware.com/2013/04/10/top-8-application-performance-landmines/">"too many database calls" remained the largest problem on the server side</a>.<br />
<br />
The "SELECT N+1" is a specialization of this problem. Also in 2013, AppDynamics <a href="http://www.appdynamics.com/blog/apm/common-application-problems-and-how-to-fix-them-the-select-n-1-problem/">wrote up the SELECT N+1</a> in their "Common Performance Problems"series. here's part of their post:<br />
<br />
<blockquote style="background-color: white; border: 0px; color: #3f3f3f; font-family: Sintony, sans-serif; font-size: 14px; font-stretch: inherit; line-height: 22px; margin-bottom: 15px; padding: 0px; vertical-align: baseline;">
Here’s how it usually goes down: You have two database tables with a parent/child relationship (like blogs and posts, or products and line items), and you want to iterate through all of them. So you do this:<br />
<code style="border: 0px; font-family: Arial, Helvetica, serif; font-size: inherit; font-stretch: inherit; font-variant: inherit; line-height: 1.5; margin: 0px; padding: 0px 8px; vertical-align: baseline;">SELECT id FROM Parent</code>and then executing a query for each record:<br />
<code style="border: 0px; font-family: Arial, Helvetica, serif; font-size: inherit; font-stretch: inherit; font-variant: inherit; line-height: 1.5; margin: 0px; padding: 0px 8px; vertical-align: baseline;">SELECT * FROM Child WHERE parent_id = ?</code></blockquote>
See how they talk about parent and child relationships? It is quite ironic that their own blog surfaces this issue, because their monitoring tool does nothing to help you identify those parent-child relationships. Nothing. <br />
<br />
The following year, in 2014, Steven Haines, author of <a href="http://www.amazon.com/Pro-Java-Performance-Management-Optimization/dp/1590596102/ref=sr_1_9?s=books&ie=UTF8&qid=1437860940&sr=1-9&keywords=steven+haines&pebp=1437860953564&perid=0Q8S9WTZ0CEAW3Q2WH3G" target="_blank">Pro Java EE 5 Performance Management and Optimization</a>, wrote <a href="http://www.google.com/url?q=http%3A%2F%2Finfo.appdynamics.com%2Frs%2Fappdynamics%2Fimages%2FTop_10_Java_Performance_Problems_eBook.pdf&sa=D&sntz=1&usg=AFQjCNFACvPl4K1Qf3WSHCoYZzVdtNZeAQ" target="_blank">a piece for AppDynamics</a>. The SELECT N+1 issue shows up as the number one issues on this updated list. This problem just isn't going away!<br />
<br />
This year, in 2015, people are still talking about the same problem. Check out this survey question, from "<a href="http://java.dzone.com/articles/announcing-dzone-guide-0" target="_blank">DZone Guide to Performance and Monitoring</a>" (2015 Edition), where a few hundred IT professionals chimed on on the question. "Too many DB queries" shows up as the number two root cause of performance problems.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgT3fzxnn3tnEkzLaUGEbsD2vFRtVUo6wIg1i0LlV1gnuXW38KdyoOsBjeL-ubWrqZVdGniL4wM4vUld884l47FUD82eO3v0FIT9pDLKgglYQNzv3FDcsDLymNiFzXMb_QoAS1lyXXQofc/s1600/Screen+Shot+2015-06-16+at+1.57.46+AM.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgT3fzxnn3tnEkzLaUGEbsD2vFRtVUo6wIg1i0LlV1gnuXW38KdyoOsBjeL-ubWrqZVdGniL4wM4vUld884l47FUD82eO3v0FIT9pDLKgglYQNzv3FDcsDLymNiFzXMb_QoAS1lyXXQofc/s1600/Screen+Shot+2015-06-16+at+1.57.46+AM.png" /></a></div>
<br />
<style type="text/css">
@page { margin: 0.79in }
p { margin-bottom: 0.1in; direction: ltr; color: #000000; line-height: 120%; text-align: left; orphans: 2; widows: 2; background: #ffffff }
p.western { font-family: "Times New Roman", serif }
a.western:visited { so-language: en-US }
a.cjk:visited { so-language: en-US }
a.ctl:visited { so-language: ar-SA }
a:link { color: #0000ff }
</style>
<br />
<div class="western">
Near the beginning of “<a href="https://www.amazon.com/Java-Performance-Definitive-Guide-Getting/dp/1449358454/ref=sr_1_1?ie=UTF8&qid=1499709086&sr=8-1&keywords=java+performance+the+definitive+guide" target="_blank">Java Performance: TheDefinitive Guide</a>”, Scott Oaks has a peculiar little section that is
aptly named “Look Elsewhere: The Database Is Always the
Bottleneck.” It is really just a page or two that cautions against
blaming Java for all your performance woes, because database
performance issues, regardless of the programming language, will very
likely eclipse any vanilla Java performance issues. <br />
<br />
Slow individual db queries are the highest reported performance problem (54.8%) in <a href="https://zeroturnaround.com/rebellabs/developer-productivity-report-2015-java-performance-survey-results/" target="_blank">this 2015 report</a> from the JRebel/XRebel people. The amorphous category of "inefficient app code" is 2nd (51.5%), and "too many db calls" is third with 38.6%.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhRGOHQNW1aJYs_Wzc9r7R6wNNEq6R2VXdhMx7sKFtqg0CKpEyAQtVLY-aE7c8HPeaUY3hlwzcwG9NUTv4ZiiFm8XaKIJuNe7H5Uw5wPH_92xVYAcBiLJVCiImfcJ8OoQFX5whG6RgFJXs/s1600/too-many-db-calls.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="434" data-original-width="614" height="226" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhRGOHQNW1aJYs_Wzc9r7R6wNNEq6R2VXdhMx7sKFtqg0CKpEyAQtVLY-aE7c8HPeaUY3hlwzcwG9NUTv4ZiiFm8XaKIJuNe7H5Uw5wPH_92xVYAcBiLJVCiImfcJ8OoQFX5whG6RgFJXs/s320/too-many-db-calls.png" width="320" /></a></div>
<br />
<br /></div>
<div class="western">
So we have famed and published Java architects and performance engineers (Martin Fowler, Scott Oaks, Steven Haines), we have two of this biggest application performance monitoring tools in the market (Dynatrace and AppDynamics) and relatively current surveys (DZone) from in the field. For this important group of experts, no other performance problem bubbles to the top ten list of server-side performance issues more than "too many database calls."</div>
<br />
Performance engineers deal with dozens upon dozens of SQL statements in every trace session. We need a tool that quickly identifies those relationships from all of that SQL text.<br />
<br />Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-31127942074876324572014-10-19T07:25:00.003-07:002014-10-20T03:37:35.163-07:00Part 2: The Neglected Basics: does the magic list exist?<a href="http://ostermueller.blogspot.com/2014/10/a-forbidden-discussion-in-software.html">In Part 1 of this series</a>, I was complaining that we rarely draw the line between the development and performance teams, divvying up the responsibilities for making the system perform. Who's going to do which parts? When the developers do nothing, we end up something real similar to the spectacular failure of the healthcare.gov launch. When developers do too much, we risk <a href="http://en.wikipedia.org/wiki/Program_optimization#When_to_optimize">premature optimization</a>.<br />
<br />
But before we can assign tasks to groups, we need to decide on the list of tasks. Does such a list exist? Let me tell you a quick story about me getting grilled by a 'new sheriff in town' performance manager.<br />
<br />
I switched from java development to performance tuning in 2006. Once of my first performance managers had come from the functional QA side of the house and he immediately took me off guard. "How can we train performance engineers if you all don't even have a plan to begin with?", he asked me. I was a little stunned. blink. blink. I was just asking for a training budget and he wanted to question my credentials. He was skeptical that performance people had any clue what they were doing, and was eager to put me on the spot, and I had just enough doubt to question myself. Do we really have a repeatable game plan for delivering well performing applications into production?<br />
<br />
Several years later after a lot more performance work, I can report that that notion is silly, that we don't know what kills performance. The performance teams I've led over the last 8 years have become board stiff (bored but overworked, actually -- not a good combination). We bolt the monitoring tools onto the applications and look under the covers. What we see is mostly the same boring, preventable problems on the list, year after year (<a href="http://ostermueller.blogspot.com/2014/10/chatty-sql-performance-anti-patterns.html">here are 3 big hitters on my list</a>). Perhaps your list is completely different than our list. <br />
<br />
I'm good if your list and my list are different -- I just think all projects need to establish _some_ list of performance anti-patterns to be avoided, and someone needs to assign throats-to-choke to each item on the list. Do your development teams do this? Are performance considerations even included in design?<br />
<br />
Assembling this magic list is not an easy task. Don't have time right now, but I need to finish my blog entry about which group is best suited for various tasks. Part 3.<br />
<br />
Also unfinished is an entry about how I kinda crashed and burned with my first two attempts to get development teams to work with a list. Hopefully you can learn from these mis-steps which will be Part 4.<br />
<br />
<br />Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-26102081548082832552014-10-18T13:23:00.000-07:002014-10-19T07:27:07.052-07:00Part 1: A Forbidden Discussion in Software DevelopmentAs a performance engineer, I feel a bit tarnished after the launch failure of healthcare.gov. I was in no way involved and those responsible do not own the monopoly on launch failures. But from the outside, does it really look like we know what we're doing, like we have a 'big plan?'<br />
<br />
One thing missing from such a 'big plan' is a discussion of who is responsible for specific tasks for ensuring system performance. We have not drawn a line for ourselves and said whether the development team or the performance tuning team is responsible for various tasks, like these:<br />
<ul>
<li>Who validates that the SQL queries hit the right indexes ? (sorry, I can't do "indices")</li>
<li>Who makes sure the static data in database is cached, keeping us from fetching to death those little bits of rarely-changing data.</li>
<li>Who keeps the <a href="http://pramatr.wordpress.com/2009/02/05/sql-n-1-selects-explained/">SELECT N+1 anti-pattern</a> out of the code base?</li>
</ul>
<div>
And I'm just getting started, the list goes on: pagination for long lists, memory leak detection, CPU profiling, setting throughput goals. Which team is going to tackle these? Dev or performance? We need to draw the line and explicitly say who owns what. We need to start talking about this.<br />
<br />
I have seen dozens of development teams, in the company I work for and elsewhere, that resist being tasked with performance concerns. Why is this? Do we deeply yearn to be blind folded and in plaid pajamas, spewing crappy performing code that functions beautifully? If that is true, we also delight in defending these plaid pajamas not out of laziness or negligence, but out of the most noble intentions: avoiding <a href="http://en.wikipedia.org/wiki/Program_optimization#When_to_optimize">premature optimization</a>. I'm a java architect as well as a performance engineer and I'm at times guilty of this over-zealotry, too.<br />
<br />
I feel obliged, at this point, to defend my cred as a performance engineer and put myself on the record. Wasting time on over-optimization is indeed a problem that deserves considerable concern, like setting and sticking to your performance goals. But as an industry, to the peril of the likes of healthcare.gov, we have failed to define the middle ground, to flesh out design & development's share of the responsibility for performance. The discussion to divvy out these chores seems oddly forbidden.<br />
<br /></div>
<div>
Before we draw the line, before we decide who's responsible for 'what', we first need to agree on the 'what' part. Does a short-list really exist -- a list of performance anti-patterns that should be avoided in most cases? If not, then perhaps we don't have a 'big plan', after all.<br />
<br />
<a href="http://ostermueller.blogspot.com/2014/10/part-2-does-game-plan-for-performance.html">Keep reading here</a> for part 2.<br />
<br />
<br /></div>
Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-91217543982666682492014-10-18T11:00:00.002-07:002016-03-12T15:24:38.406-08:00Chatty SQL Performance Anti-Patterns<h3 id="ChattyDBPerformanceAnti-Patterns-AntiPattern1:"SELECTN+1"" style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 16px; line-height: 1.5625; margin: 30px 0px 0px;">
<span style="font-size: 14px; font-weight: normal; line-height: 20px;">Year after year, these three SQL "data access" anti-patterns cause a large percentage of the performance problems we see as performance engineers.</span></h3>
<h3 id="ChattyDBPerformanceAnti-Patterns-AntiPattern1:"SELECTN+1"" style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 16px; line-height: 1.5625; margin: 30px 0px 0px;">
Anti Pattern 1: "SELECT N+1"</h3>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<u><em>ANTI-PATTERN</em></u>: When code, instead of joining two tables, iterates through the result set of the parent table and executes <code>SELECT</code>s to the child table. <a href="http://ostermueller.blogspot.com/2016/03/chatter-about-select-n1.html" target="_blank">Much has been written on this topic</a>. </div>
<div class="code panel pdl" style="background-color: white; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 1px solid rgb(204, 204, 204); color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin: 10px 0px; overflow: auto; padding: 0px;">
<div class="codeContent panelContent pdl" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; margin: 0px; overflow: hidden; padding: 0px;">
<div class="syntaxhighlighter nogutter java" id="highlighter_152164" style="font-size: 1em !important; margin: 0px !important; overflow: auto !important; position: relative !important; width: 1326px;">
<table border="0" cellpadding="0" cellspacing="0" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 14px !important; height: auto !important; left: auto !important; line-height: 20px !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: 1326px;"><tbody style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<tr style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><td class="code" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 0px 0px 15px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: 1311px;"><div class="container" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 15px 0px 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 0px 15px !important; position: relative !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre-wrap !important; width: auto !important;" title="Hint: double-click to select code">
<div class="line number1 index0 alt2" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">ResultSet parentRs = myStatement.executeQuery(strParentSELECT);</code></div>
<div class="line number2 index1 alt1" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java keyword" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; color: rgb(0, 102, 153) !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-weight: bold !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">while</code><code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">(rs.next()) {</code></div>
<div class="line number3 index2 alt2" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java spaces" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">String myId = rs.getString(</code><code class="java value" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; color: rgb(0, 153, 0) !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">1</code><code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">);</code></div>
<div class="line number4 index3 alt1" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java spaces" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">ResultSet childRs = statement.executeQuery(</code><code class="java string" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; color: blue !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">"select * from child where id = "</code> <code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">+ myId); </code></div>
<div class="line number5 index4 alt2" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"> </code><code class="java comments" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; color: rgb(0, 130, 0) !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">//do something with childRs</code></div>
<div class="line number6 index5 alt1" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">} </code></div>
</div>
</td></tr>
</tbody></table>
</div>
</div>
</div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<u><em>TO REFACTOR (Option 1)</em></u>: Join the parent and child tables. Here is <a class="external-link" href="http://learningviacode.blogspot.com/2012/08/fetch-join-for-collection.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">one way </a>to tackle this with Hibernate, if the # of rows is reasonable small enough (perhaps < 200) to be retrieved in one trip.<br />
If more than 200 rows are to be returned, consider using hibernate <a class="external-link" href="http://learningviacode.blogspot.sg/2012/08/batch-size-n.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">batch size parameter</a>.</div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<u><em>TO REFACTOR (Option 2)</em></u>: Instead of JOINing, use a sub-select, like this:</div>
<div class="code panel pdl" style="background-color: white; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 1px solid rgb(204, 204, 204); color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin: 10px 0px; overflow: auto; padding: 0px;">
<div class="codeContent panelContent pdl" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; margin: 0px; overflow: hidden; padding: 0px;">
<div class="syntaxhighlighter nogutter java" id="highlighter_488333" style="font-size: 1em !important; margin: 0px !important; overflow: auto !important; position: relative !important; width: 1326px;">
<table border="0" cellpadding="0" cellspacing="0" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; font-size: 14px !important; height: auto !important; left: auto !important; line-height: 20px !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: 1326px;"><tbody style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">
<tr style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;"><td class="code" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 0px 0px 15px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: 1311px;"><div class="container" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 15px 0px 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 0px 15px !important; position: relative !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: pre-wrap !important; width: auto !important;" title="Hint: double-click to select code">
<div class="line number1 index0 alt2" style="background-attachment: initial !important; background-clip: initial !important; background-image: none !important; background-origin: initial !important; background-position: initial !important; background-repeat: initial !important; background-size: initial !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px 1em 0px 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; white-space: nowrap !important; width: auto !important;">
<code class="java plain" style="background: none !important; border-bottom-left-radius: 0px !important; border-bottom-right-radius: 0px !important; border-top-left-radius: 0px !important; border-top-right-radius: 0px !important; border: 0px !important; bottom: auto !important; box-sizing: content-box !important; float: none !important; font-family: Consolas, 'Bitstream Vera Sans Mono', 'Courier New', Courier, monospace !important; height: auto !important; left: auto !important; margin: 0px !important; min-height: inherit !important; outline: 0px !important; overflow: visible !important; padding: 0px !important; position: static !important; right: auto !important; top: auto !important; vertical-align: baseline !important; width: auto !important;">select * from CHILD where CHILD.MY_KEY in (select MY_PARENT_KEY from parent);</code></div>
</div>
</td></tr>
</tbody></table>
</div>
</div>
</div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<br />
This describes the relationship between just two tables. Often we see a parent table driving the results of an entire pattern of table accesses. Instead of SELECT N+1, we have SELECT N(x) +1, where (x) is the pattern of SQL statements instead of a single child table.<br />
<a href="http://eostermueller.github.io/wuqispank/images/patterns_anonymous.png">This diagram</a> (from <a href="http://wuqispank.org/">wuqiSpank</a>) shows a pattern (in yellow) of SQL statements that is repeatedly executed.</div>
<h3 id="ChattyDBPerformanceAnti-Patterns-AntiPattern2:UnCached-Static" style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 16px; line-height: 1.5625; margin: 30px 0px 0px;">
Anti Pattern 2: UnCached - Static</h3>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
Static tables are those that generally get less than 1 update an hour during an average day of production traffic. All tables in a schema should be categorized as either static or dynamic, <a href="https://spdwiki.fnis.com/display/ACBS/DB+Tables" style="color: #3b73af; text-decoration: none;">as seen here</a>. <br />
<br />
<u><em>ANTI-PATTERN</em></u>: Source code repeatedly <code>SELECT</code>s static data, even though that data rarely changes.<br />
<br />
<u><em>TO REFACTOR</em></u>: <a href="https://spdwiki.fnis.com/display/Prime/Ehcache+configuration" style="color: #3b73af; text-decoration: none;">Use EHCache </a>(which includes Hibernate integration). The goal is to enable EHCache to essentially 'interrupt' the jdbc request and instead return results from an in-memory cache. EHCache manages a configurable cache refresh process.</div>
<h3 id="ChattyDBPerformanceAnti-Patterns-AntiPattern3:UnCached-Dynamic" style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 16px; line-height: 1.5625; margin: 30px 0px 0px;">
Anti Pattern 3: UnCached - Dynamic</h3>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<u><em>ANTI-PATTERN</em></u>: Source code retrieves dynamic data (perhaps customer or account data) from db and re-queries that same data before the business process has completed.<br />
<br />
<u><em>TO REFACTOR</em></u>: Temporarily store the initial query results so they are available to subsequent code. For example, say that two web service calls are made after a user clicks a button. Both calls require the same five SQL queries for initialization. Solution: Refactor code into a single web service call instead of two.</div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<br /></div>
<div>
<h1 id="ChattyDBPerformanceAnti-Patterns-References" style="background-color: white; border-bottom-color: rgb(204, 204, 204); color: #333333; font-family: Arial, sans-serif; font-size: 24px; font-weight: normal; line-height: 1.25; margin: 30px 0px 0px;">
References</h1>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
The following show that "SELECT N+1" is a widely problematic.</div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://blog.jooq.org/tag/object-relational-mapping/" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://blog.jooq.org/tag/object-relational-mapping/</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://stackoverflow.com/tags/select-n-plus-1/hot" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://stackoverflow.com/tags/select-n-plus-1/hot</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://use-the-index-luke.com/sql/join/nested-loops-join-n1-problem" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://use-the-index-luke.com/sql/join/nested-loops-join-n1-problem</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://thecuttingledge.com/?p=169" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://thecuttingledge.com/?p=169</a><br />
<a class="external-link" href="http://ayende.com/blog/1328/combating-the-select-n-1-problem-in-nhibernate" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://ayende.com/blog/1328/combating-the-select-n-1-problem-in-nhibernate</a><br />
<a class="external-link" href="http://pramatr.wordpress.com/2009/02/05/sql-n-1-selects-explained/" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://pramatr.wordpress.com/2009/02/05/sql-n-1-selects-explained/</a><br />
<a class="external-link" href="http://docs.telerik.com/data-access/developers-guide/profiling-and-tuning/profiler-and-tuning-advisor/data-access-profiler-n-plus-one-problem" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://docs.telerik.com/data-access/developers-guide/profiling-and-tuning/profiler-and-tuning-advisor/data-access-profiler-n-plus-one-problem</a><br />
<a class="external-link" href="http://www.hibernatingrhinos.com/products/nhprof/learn/alert/selectnplusone" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://www.hibernatingrhinos.com/products/nhprof/learn/alert/selectnplusone</a><br />
<a class="external-link" href="http://www.pbell.com/index.cfm/2006/9/17/Understanding-the-n1-query-problem" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://www.pbell.com/index.cfm/2006/9/17/Understanding-the-n1-query-problem</a><br />
<a class="external-link" href="http://dotnet.dzone.com/news/select-n1-problem-%E2%80%93-how" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://dotnet.dzone.com/news/select-n1-problem-%E2%80%93-how</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://java.dzone.com/articles/martin-fowler-orm-hate" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://java.dzone.com/articles/martin-fowler-orm-hate</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://learningviacode.blogspot.com/2012/07/the-n-1-select-problem-in-hibernate.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.com/2012/07/the-n-1-select-problem-in-hibernate.html</a><br />
<a class="external-link" href="http://learningviacode.blogspot.com/2012/08/fetch-join-for-collection.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.com/2012/08/fetch-join-for-collection.html</a><br />
<a class="external-link" href="http://learningviacode.blogspot.com/2012/08/fetch-subselect.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.com/2012/08/fetch-subselect.html</a><br />
<a class="external-link" href="http://learningviacode.blogspot.sg/2012/08/batch-size-n.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.sg/2012/08/batch-size-n.html</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://learningviacode.blogspot.in/2012/07/lazyextra.html" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://learningviacode.blogspot.in/2012/07/lazyextra.html</a></div>
<div style="background-color: white; color: #333333; font-family: Arial, sans-serif; font-size: 14px; line-height: 20px; margin-top: 10px;">
<a class="external-link" href="http://stackoverflow.com/questions/97197/what-is-the-n1-selects-issue" rel="nofollow" style="color: #3b73af; text-decoration: none;" target="_blank">http://stackoverflow.com/questions/97197/what-is-the-n1-selects-issue</a></div>
</div>
Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-712494830367998212014-10-12T22:30:00.000-07:002016-03-12T14:21:29.719-08:00Chunky Outperforms Chatty<h1 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 2.25em; line-height: 1.2; margin-bottom: 16px; margin-left: 0px; margin-right: 0px; margin-top: 0px !important; padding-bottom: 0.3em; position: relative;">
</h1>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
<a href="https://github.com/eostermueller/chunkyOutperformsChatty" target="_blank">This repo on github</a> contains Java code and results from a performance comparison of 5 different SQL data access strategies, ranging from very chatty to very chunky.</div>
<ul class="task-list" style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px; margin-top: 0px; padding: 0px 0px 0px 2em;">
<li style="box-sizing: border-box;">Chatty = many SQL invocations that touch relatively few records.</li>
<li style="box-sizing: border-box;">Chunky = fewer SQL invocations that touch more records.</li>
</ul>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
The two chunkiest strategies (1 & 2) outperform the rest, with roughly 30% or more tps. <span style="line-height: 25.6000003814697px;">Surprisingly, though, these two high-performance strategies don't seem to be real popular. As a performance engineer, my world has been covered up with a lot of chatty for the last 8 years.</span><br />
<span style="line-height: 25.6000003814697px;"><br /></span>
<span style="line-height: 25.6000003814697px;">But I'm not alone, being fan of the chunky -- consider </span><a href="http://martinfowler.com/" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; line-height: 25.6000003814697px; text-decoration: none;">Martin Fowler</a>, who has written about <a href="http://java.dzone.com/articles/martin-fowler-orm-hate">ORM (object relational mapping) extensively</a>. He also has two books on the <a href="http://stackoverflow.com/questions/1711/what-is-the-single-most-influential-book-every-programmer-should-read/1713#1713">'most influential programmer book,' list</a>. He<span style="line-height: 25.6000003814697px;"> was </span><a href="http://www.informit.com/articles/article.aspx?p=30661&seqNum=3" style="line-height: 25.6000003814697px;">preaching chunky</a><span style="line-height: 25.6000003814697px;"> way back in 2003:</span></div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; color: #333333; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: 1.45; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><code style="background: transparent; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; line-height: inherit; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">"Try to pull back multiple rows at once. In particular,
never do repeated queries on the same table to get multiple rows."
</code></pre>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
...and others are adding to the chunky chorus ( <a href="http://apmblog.compuware.com/2010/06/15/top-10-performance-problems-taken-from-zappos-monster-and-co/" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;">here</a> <a href="http://blogs.msdn.com/b/alikl/archive/2008/04/28/performance-sin-chatty-database-access-and-loops-plus-another-free-performance-tool.aspx" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;">here</a> <a href="http://dotnet.dzone.com/news/select-n1-problem-%E2%80%93-how" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;">here</a> ). My post here focuses on the code, the data and the performance. Fowler <a href="http://martinfowler.com/articles/dblogic.html">did a similar comparison</a> but focused on code style and where to put business logic. But Fowler's test was a bit extreme -- he worked with 1,000 db records to show the poor performance of chunky. These tests show the problem by selecting just 100 records.<br />
<br />
But keep in mind that performance isn't everything:<br />
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: 1.45; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><code style="background: transparent; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; line-height: inherit; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand."
</code></pre>
<div style="box-sizing: border-box; line-height: 25.6000003814697px; margin-bottom: 16px;">
(taken from Fowler's <a href="http://www.amazon.com/Refactoring-Improving-Design-Existing-Code/dp/0201485672">Refactoring: Improving the Design of Existing Code</a>)<br />
<br /></div>
</div>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 1.75em; line-height: 1.225; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
<a aria-hidden="true" class="anchor" href="https://github.com/eostermueller/chunkyOutperformsChatty/blob/master/README.md#five-scenarios" name="user-content-five-scenarios" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; bottom: 0px; box-sizing: border-box; color: #4183c4; display: block; left: 0px; margin-left: -30px; padding-left: 30px; padding-right: 6px; position: absolute; text-decoration: none; top: 0px;"><br /></a>Five Strategies</h2>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
The throughput of five different implementations of the same XML-over-HTTP web service was tested. The web service is a simple account and transaction inquiry to the Postgres <a href="http://www.postgresql.org/docs/9.2/static/pgbench.html" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;">pgbench db</a>.</div>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
The following graph shows throughput in red (tps / higher is better) and the strategy number in blue. See how the blue line rises like steps? The test ran each strategy for 1 minute, then moved on to the next larger strategy number: 1,2,3,4,5 and then it repeated 8 more times. Each request inquired upon 5 differnt accounts. In the graph below, strategy=scenario.</div>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
<a href="https://github.com/eostermueller/chunkyOutperformsChatty/blob/master/results/fiveAccounts/tps-by-scenario.png" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;" target="_blank"><img alt="Inquiry for 5 accountIds" src="https://github.com/eostermueller/chunkyOutperformsChatty/raw/master/results/fiveAccounts/tps-by-scenario.png" style="border: 0px; box-sizing: border-box; max-width: 100%;" /></a></div>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
The requirements for the web service:</div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; color: #333333; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: 1.45; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><code style="background: transparent; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; line-height: inherit; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">Given 1 to N account numbers, return transaction history and balance info
</code><span style="background-color: transparent; line-height: inherit;">for all accounts. </span><span style="background-color: transparent; line-height: inherit;">All 5 strategies must build the response data using
the exact same pojos </span><span style="background-color: transparent; line-height: inherit;">and the same XML serialization code.</span></pre>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
Stragey 1 has the fewest SQL invocations, 5 has the most (5 is a little extreme, actually), and 2, 3 and 4 line up inbetween (yes, in order).</div>
<table style="border-collapse: collapse; border-spacing: 0px; box-sizing: border-box; color: #333333; display: block; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px; margin-top: 0px; overflow: auto; width: 858px; word-break: normal;"><thead style="box-sizing: border-box;">
<tr style="background-color: white; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; box-sizing: border-box;"><th style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">Tables</th><th align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">PGBENCH_ACCOUNTS</th><th align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">PGBENCH_HISTORY</th><th align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">Notes</th></tr>
</thead><tbody style="box-sizing: border-box;">
<tr style="background-color: white; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; box-sizing: border-box;"><td style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"><a href="https://github.com/eostermueller/chunkyOutperformsChatty/tree/master/src/main/java/com/github/eostermueller/pgbench/dataaccess_1" style="background: transparent; box-sizing: border-box; color: #4183c4; text-decoration: none;">Strategy_1</a></td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT, OUTER JOIN to PGBENCH_HISTORY</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"></td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">The Chunkiest of the 5. Rarely seen in the wild</td></tr>
<tr style="background-color: #f8f8f8; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; box-sizing: border-box;"><td style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"><a href="https://github.com/eostermueller/chunkyOutperformsChatty/tree/master/src/main/java/com/github/eostermueller/pgbench/dataaccess_2" style="background: transparent; box-sizing: border-box; color: #4183c4; text-decoration: none;">Strategy_2</a></td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">Rarely seen in the wild</td></tr>
<tr style="background-color: white; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; box-sizing: border-box;"><td style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"><a href="https://github.com/eostermueller/chunkyOutperformsChatty/tree/master/src/main/java/com/github/eostermueller/pgbench/dataaccess_3" style="background: transparent; box-sizing: border-box; color: #4183c4; text-decoration: none;">Strategy_3</a></td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT per account</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"></td></tr>
<tr style="background-color: #f8f8f8; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; box-sizing: border-box;"><td style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"><a href="https://github.com/eostermueller/chunkyOutperformsChatty/tree/master/src/main/java/com/github/eostermueller/pgbench/dataaccess_4" style="background: transparent; box-sizing: border-box; color: #4183c4; text-decoration: none;">Strategy_4</a></td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT per account</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT per account</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"></td></tr>
<tr style="background-color: white; border-top-color: rgb(204, 204, 204); border-top-style: solid; border-top-width: 1px; box-sizing: border-box;"><td style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;"><a href="https://github.com/eostermueller/chunkyOutperformsChatty/tree/master/src/main/java/com/github/eostermueller/pgbench/dataaccess_5" style="background: transparent; box-sizing: border-box; color: #4183c4; text-decoration: none;">Strategy_5</a></td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT per account</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">1 SELECT PER account to retrieve unique IDs. 1 SELECT for each full history record.</td><td align="left" style="border: 1px solid rgb(221, 221, 221); box-sizing: border-box; padding: 6px 13px;">The Chattiest of the 5.</td></tr>
</tbody></table>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 1.75em; line-height: 1.225; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
<a aria-hidden="true" class="anchor" href="https://github.com/eostermueller/chunkyOutperformsChatty/blob/master/README.md#pudding" name="user-content-pudding" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; bottom: 0px; box-sizing: border-box; color: #4183c4; display: block; left: 0px; margin-left: -30px; padding-left: 30px; padding-right: 6px; position: absolute; text-decoration: none; top: 0px;"></a>Validation</h2>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
Any one interested in checking my facts in the table above? I know, you're busy, which is part of why production bound code/sql rarely gets a full vetting. Instead of guessing, let's just look at what happened with each strategy -- graphically -- using <a href="http://wuqispank.org/" target="_blank">wuqiSpank</a>.</div>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
<a href="https://github.com/eostermueller/chunkyOutperformsChatty/blob/master/results/fiveAccounts/5-scenarios_wuqiSpank.png" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;" target="_blank"><img alt="" src="https://github.com/eostermueller/chunkyOutperformsChatty/raw/master/results/fiveAccounts/5-scenarios_wuqiSpank.png" style="border: 0px; box-sizing: border-box; max-width: 100%;" /></a></div>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 1.75em; line-height: 1.225; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
<a aria-hidden="true" class="anchor" href="https://github.com/eostermueller/chunkyOutperformsChatty/blob/master/README.md#instructions" name="user-content-instructions" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; bottom: 0px; box-sizing: border-box; color: #4183c4; display: block; left: 0px; margin-left: -30px; padding-left: 30px; padding-right: 6px; position: absolute; text-decoration: none; top: 0px;"></a></h2>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 1.75em; line-height: 1.225; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
SQL</h2>
<div>
The following are the SQL executed for one invocation of each strategy. The same account numbers (and all their corresponding history records) were used for each strategy.</div>
<h3>
Strategy 1:</h3>
<div>
<span style="font-size: 16px; font-weight: normal; line-height: 25.6000003814697px;">A single query:</span></div>
<div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><span style="font-family: "consolas" , "liberation mono" , "menlo" , "courier" , monospace;"><span style="font-size: 14px; line-height: 20.2999992370605px;">SELECT a.aid, a.bid, a.abalance, a.filler, h.tid, h.hid, h.delta, h.mtime,
h.filler FROM pgbench_accounts a LEFT OUTER JOIN pgbench_history h
ON a.aid = h.aid WHERE a.aid in (?,?,?,?,?) ORDER BY a.aid, h.mtime desc</span></span></pre>
</div>
<h3>
Strategy 2:</h3>
<h3>
<div style="font-size: medium; font-weight: normal;">
<span style="font-size: 16px; line-height: 25.6000003814697px;">2 queries:</span></div>
<div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><span style="font-family: "consolas" , "liberation mono" , "menlo" , "courier" , monospace;"><span style="font-size: 14px; font-weight: normal; line-height: 20.2999992370605px;">SELECT a.aid, a.bid, a.abalance, a.filler FROM pgbench_accounts a
WHERE aid in (?,?,?,?,?)
SELECT tid , hid, bid , aid , delta , mtime , filler
FROM pgbench_history WHERE aid in (?,?,?,?,?) ORDER BY aid, hid</span></span></pre>
</div>
</h3>
<h3>
Strategy 3:</h3>
<h3>
<div>
<code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;"></code><br />
<div style="font-family: Times; font-size: medium; font-weight: normal; line-height: inherit;">
<code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;"><span style="font-size: 16px; line-height: 25.6000003814697px;">6 queries:</span></code></div>
<code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">
<div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><span style="font-family: "consolas" , "liberation mono" , "menlo" , "courier" , monospace;"><span style="font-size: 14px; font-weight: normal; line-height: 20.2999992370605px;">( 1x) SELECT a.aid, a.bid, a.abalance, a.filler
FROM pgbench_accounts a WHERE aid in (?,?,?,?,?)
( 5x) SELECT tid, hid, bid, aid, delta, mtime, filler
from pgbench_history WHERE aid = ?</span></span></pre>
</div>
</code></div>
</h3>
<h3>
Strategy 4:</h3>
<h3>
<code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;"><code style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;"><div>
<span style="font-family: "times"; font-size: medium;"><span style="font-weight: normal; line-height: 25.6000003814697px;">The following two queries were retrieved 5 times each, for a total of 10 queries:</span></span></div>
<div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><span style="font-family: "consolas" , "liberation mono" , "menlo" , "courier" , monospace;"><span style="font-size: 14px; font-weight: normal; line-height: 20.2999992370605px;">SELECT aid, bid, abalance, filler from pgbench_accounts WHERE aid = ?
SELECT tid, hid, bid, aid, delta, mtime, filler from pgbench_history
WHERE aid = ?</span></span></pre>
</div>
</code></code></h3>
<h3>
Strategy 5:</h3>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
<div style="color: black; font-family: Times; font-size: medium; font-weight: normal; line-height: normal;">
<span style="font-size: 16px; line-height: 25.6000003814697px;">The following 25 queries were executed 5 times for a total of about 125 queries.</span></div>
<div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><span style="font-family: "consolas" , "liberation mono" , "menlo" , "courier" , monospace;"><span style="font-size: 14px; font-weight: normal; line-height: 20.2999992370605px;">( 1x) SELECT aid, bid, abalance, filler from pgbench_accounts WHERE aid = ?
(24x) SELECT hid from pgbench_history WHERE aid = ?</span></span></pre>
</div>
</h2>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 1.75em; line-height: 1.225; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
</h2>
<h2 style="border-bottom-color: rgb(238, 238, 238); border-bottom-style: solid; border-bottom-width: 1px; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 1.75em; line-height: 1.225; margin-bottom: 16px; margin-top: 1em; padding-bottom: 0.3em; position: relative;">
<div>
<div style="box-sizing: border-box; font-size: 16px; font-weight: normal; line-height: 25.6000003814697px; margin-bottom: 16px;">
</div>
</div>
Instructions</h2>
<ol class="task-list" style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px; margin-top: 0px; padding: 0px 0px 0px 2em;">
<li style="box-sizing: border-box;">Install PostGreSQL. I used 9.2</li>
<li style="box-sizing: border-box;">Load pgbench sample data as detailed below.</li>
<li style="box-sizing: border-box;">Add a seuquence / primary key to the pgbench_history table.</li>
<li style="box-sizing: border-box;"><a href="https://github.com/eostermueller/chunkyOutperformsChatty/archive/master.zip" style="background-attachment: initial; background-clip: initial; background-image: initial; background-origin: initial; background-position: initial; background-repeat: initial; background-size: initial; box-sizing: border-box; color: #4183c4; text-decoration: none;">Download the war</a> file and unzipt it to a blank folder.</li>
<li style="box-sizing: border-box;">Make sure the JDBC connection info is right in this file: <code style="background-color: rgba(0, 0, 0, 0.0392157); border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: normal; margin: 0px; padding: 0.2em 0px;">./src/main/webapp/META-INF/context.xml</code></li>
<li style="box-sizing: border-box;">Build it with <code style="background-color: rgba(0, 0, 0, 0.0392157); border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: normal; margin: 0px; padding: 0.2em 0px;">mvn clean package</code></li>
<li style="box-sizing: border-box;">Deploy target/sqlPerfAntiPatterns.war to Tomcat 7+</li>
<li style="box-sizing: border-box;">Run the service using this URL:</li>
</ol>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; color: #333333; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: 1.45; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><code style="background: transparent; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; line-height: inherit; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">localhost:8082/sqlPerfAntiPatterns/sqlPerfServlet?pgbenchScenarioNum=2&pgbenchAccountIds=34591,9483121,78941,111294,9122
</code></pre>
<div style="box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, 'Segoe UI', Arial, freesans, sans-serif; font-size: 16px; line-height: 25.6000003814697px; margin-bottom: 16px;">
The following populates the pgbench_accounts table, but not the pgbench_history table:</div>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; color: #333333; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: 1.45; margin-bottom: 16px; overflow: auto; padding: 16px; word-wrap: normal;"><code style="background: transparent; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; line-height: inherit; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">export DB_NAME=db_pgbench
export SCALE_FACTOR=100
export HOSTNAME=localhost
export PORT=5432
export USER=postgres
pgbench -i -s $SCALE_FACTOR -h $HOSTNAME -p $PORT -U $USER $DB_NAME
</code></pre>
<pre style="background-color: #f7f7f7; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; box-sizing: border-box; color: #333333; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 14px; line-height: 1.45; overflow: auto; padding: 16px; word-wrap: normal;"><code style="background: transparent; border-bottom-left-radius: 3px; border-bottom-right-radius: 3px; border-top-left-radius: 3px; border-top-right-radius: 3px; border: 0px; box-sizing: border-box; display: inline; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; line-height: inherit; margin: 0px; padding: 0px; word-break: normal; word-wrap: normal;">-- add primary key to history table
db_pgbench=# ALTER TABLE pgbench_history ADD COLUMN hid SERIAL PRIMARY KEY;
NOTICE: ALTER TABLE will create implicit sequence "pgbench_history_hid_seq" for serial column "pgbench_history.hid"
NOTICE: ALTER TABLE / ADD PRIMARY KEY will create implicit index "pgbench_history_pkey" for table "pgbench_history"
ALTER TABLE
--added index for searching history for account id's.
CREATE INDEX idx_aid on pgbench_history (aid);</code></pre>
Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-45306219453102652122014-10-12T21:03:00.000-07:002014-10-12T21:03:40.309-07:00<br />
<h2>
wuqiSpank</h2>
<div>
UPDATE: October 12, 2014. Check out http://wuqiSpank.org for the latest release of wuqiSpank.</div>
<div>
<br /></div>
<div>
Yep, that's the name of the monitoring application that I'm writing. wuqi. spank. wuqispank. </div>
<ul>
<li>Is your code SELECTing data from the exact same table multiple times in a single request? </li>
<li>How many round trips does your code make to the database? </li>
<li>Re-executing the exact same SELECT statement?</li>
</ul>
<br />
There are all kinds of performance efficiencies to be gained by refactoring this kind of code.<br />
I'm working on a monitoring tool that will visually answer the above questions by graphing your applications' SQL activity. wuqi = woefully unnecessary query invocation. Spank those wuqi's.<br />
<br />
Here are some of the milestones in writing this monitoring application:<br />
<br />
<ol>
<li>The first step is to get a headless monitoring API that will allow me to write java code that will get notified when SQL statements get executed on a remote JVM. <a href="http://mchr3k.github.io/org.intrace/" target="_blank">InTrace</a> is a great tool for tracing all JVM method invocations, but the GUI is very tightly integrated with the event API....until now: <a href="https://github.com/eostermueller/headlessInTraceClient" target="_blank">this headless version of the InTrace API</a> let's you write monitoring tools to collect events from remote (or local) JVMs.</li>
<li>What code of mine executed this particular SQL statement? To answer this question, wuqispank will need to have stacktrace information for all SQL statements. Need to be able to configure the InTrace agent to send back stacktraces for all (perhaps selected) method calls.</li>
<li>All those stacktraces will take up a lot of bandwidth. <a href="https://github.com/eostermueller/org.intrace" target="_blank">This InTrace enhancement</a> is a fork of the main InTrace repo. It adds GZIP compression to the network events transmitted over the wire.</li>
<li>Need to write a web application that uses the headless InTrace API to graphically display SQL activity....</li>
</ol>
<br />
<br />
<br />
<br />
<br />Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com0tag:blogger.com,1999:blog-2071453605535500980.post-40159510608853512822012-01-12T11:22:00.000-08:002012-01-22T16:36:56.843-08:00InTrace<br />
<div style="background-attachment: initial; background-clip: initial; background-image: none; background-origin: initial; margin-bottom: 10px; padding-bottom: 0px; padding-left: 0px; padding-right: 0px; padding-top: 0px;">
<span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;">This page shows how to use <a href="http://mchr3k.github.com/org.intrace/">InTrace</a> to view </span></span><span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; line-height: 17px;">remote JVM</span><span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;"> activity live on your Windows (or other linux/mac) desktop.</span></span><br />
<span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;"><br /></span></span><br />
<b style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; font-size: xx-large; line-height: 17px;">Installation</b><br />
<br />
<div class="MsoNormal" style="line-height: 12.75pt; margin-bottom: 7.5pt;">
<span style="font-family: Arial, Helvetica, sans-serif;">On the machine of the JVM you want to trace:</span></div>
<div class="MsoNormal" style="margin-bottom: 7.5pt;">
</div>
<ol>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">Download <a href="http://intracesite.appspot.com/files/intrace-agent.jar">this jar file</a> to the machine with the JVM you want to trace. NOTE: To work on IBM JVM's this jar needs a tiny MANIFEST.MF patch, <a href="https://github.com/mchr3k/org.intrace/issues/15#issuecomment-3384718">detailed here</a>. </span></span></li>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">Add this parameter to your JVM start-up parms, using the absolute path to the intrace-agent.jar file: -javaagent:/home/myuser/intrace-agent.jar</span></span></li>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">Restart the JVM.</span></span></li>
</ol>
<div>
<span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">On your Windows desktop:</span></span></div>
<div>
<ol><ol>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">Download <a href="http://intracesite.appspot.com/files/intrace-ui.jar">this InTrace jar file</a> to your windows desktop. </span></span></li>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">Launch the UI with this jar file with "java -jar intrace-ui.jar"</span></span></li>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">In the InTrace UI, click the "Connection" button to specify the host name/ip of the JVM to be traced. Note that there is a default port (9123) that is used to connect.</span></span></li>
<li><span style="color: #333333; font-family: Arial, sans-serif;"><span style="line-height: 17px;">In the InTrace UI, click the "Classes" button to indicate which classes you want to trace/instrument.</span></span></li>
</ol>
</ol>
</div>
<b style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; font-size: xx-large; line-height: 17px;">Overview</b><br />
<span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;">InTrace is an open-source trace utility that lets you view live JVM activity in a window on your Windows desktop. </span></span><span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; line-height: 17px;">The activity of a JVM on remote machine (local too) is shipped via TCP back to your desktop live, as it happens.</span><br />
<span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;"><br /></span></span><br />
<span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;">What kind of JVM activity is traced?</span></span><br />
<ul>
<li><span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; line-height: 17px;">Start/stop time of any/all method entry/exit</span></li>
<li><span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; line-height: 17px;">Values of all parameters passed into any method
</span></li>
<li><span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; line-height: 17px;">Values returned from any method
</span></li>
</ul>
<div>
<span style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif;"><span style="line-height: 17px;"><br /></span></span></div>
<b style="color: #333333; font-family: Arial, Helvetica, FreeSans, sans-serif; font-size: xx-large; line-height: 17px;">Instrumentation</b><br />
<span style="font-family: Arial, Helvetica, sans-serif;">To trace something, you first have to "instrument" it -- that just means you have to tell InTrace which classes you want to watch. To avoid unnecessary overhead, InTrace only traces the class names that you specify. There are two ways to instrument a class, so you can capture trace events from that class:</span><br />
<ul>
<li><span style="font-family: Arial, Helvetica, sans-serif;">Start the InTrace UI and click on the "Classes" button. See the "Installation" section, above, for how to start the UI.</span></li>
<li><span style="font-family: Arial, Helvetica, sans-serif;">Use Manual Instrumentation, below.</span></li>
</ul>
<b style="font-family: Arial, Helvetica, sans-serif; font-size: xx-large;">Optional Manual Instrumentation</b><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Optionally, at JVM startup, you can specify the class names you want to instrument. This is real helpful if you want to instrument the same set of classes every single time you start the JVM.</span><br />
<span style="font-family: Arial, Helvetica, sans-serif;"><br /></span><br />
<span style="font-family: Arial, Helvetica, sans-serif;">Say that you want to trace these three classes:</span><br />
<ul>
<li><span style="font-family: 'Courier New', Courier, monospace;">example.TraceExample</span></li>
<li><span style="font-family: 'Courier New', Courier, monospace;">com.fis.Foobar</span></li>
<li><span style="font-family: 'Courier New', Courier, monospace;">com.fis.HelloWorld</span></li>
</ul>
<span style="font-family: Arial, Helvetica, sans-serif;">Use these java parameters on the JVM running the code you want to trace:</span><br />
<blockquote class="tr_bq">
<span style="font-family: 'Courier New', Courier, monospace;">-javaagent:${lib.dir}/intrace-agent.jar=[regex-example.TraceExample|com.fis.Foobar|com.fis.HelloWorld[instru-true</span></blockquote>
</div>Erik Ostermuellerhttp://www.blogger.com/profile/14283026668109832539noreply@blogger.com2