Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Branch Prediction. <a href="http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/" rel="nofollow">http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/</a></p> <p>For the non shuffled case it is much easier to understand. Assume we have a very simple predictor that guesses that the next result will be the same as the previous result:</p> <p>e.g. (c=cat,d=dog,o=owl)</p> <p>animal: CCCCC DDDDD OOOOO</p> <p>prediction: *CCCC CDDDD DOOOO</p> <p>Correct: NYYY NYYY NYYYY </p> <p>As you can see the predictions are only wrong when the animal changes. So, with a thousand animals of each type the predictor is right over 99% of the time.</p> <p>But, the predictor doesn't really work that way, </p> <p>What is really happening** is that each if branch is being predicted to be true or false. Assuming a (40%,30%,20%,10%,0%) distribution like in your example:</p> <p>if (Animal.Type == MostCommonType) true less than half the time (40%) 40 out of 100 (40+30+20+10+0) else if (animal.Type == SecondMostCommonType) //true 50% of the time, 30 out of 60 (30+20+10 + 0) else if (animal.Type == ThirdMostCommonType) // true 66% of the time 20 out of 30 (20+10) else if (animal.Type == FourtMostCommonType) // true 100% of the time 10 out of 10 (10 +0)</p> <p>40%, 50%, and 60% odds don't give the predictor much to work with, and the only good prediction (100%) is on the least common type and least common code path.</p> <p>However, if you reverse the if order:</p> <p>if (animal.Type == FifthMostCommonType) //False 100% of the time 0 out of 100 (40+30+20+10+0) else if (animal.Type == FourtMostCommonType) //False 90% of the time 10 out of 100 (40+30+20+10) else if (Animal.Type == MostCommonType) //False 77% of the time 20 out of 90 (40+30+20+) else if (animal.Type == SecondMostCommonType) //true 57 % of the time, 30 out of 70 (40+30) else if (animal.Type == ThirdMostCommonType) // true 100% of the time 40 out of 40 (40+)</p> <p>Nearly all comparisons are highly predicable.</p> <p>Predicting that the next animal will NOT be the least common animal will be correct more than any other prediction.</p> <p>In short, the total cost of the missed branch predictions in this case is higher than the cost of doing more branches (i.e. if statements)</p> <p>I hope that clears it up a little. Please let me know if any parts are unclear, I'll try to clarify.</p> <p>**well not really really, but much closer to the truth.</p> <p>Edit:</p> <p>The branch predictor in newer processor is fairly complex you can see more detail at <a href="http://en.wikipedia.org/wiki/Branch_predictor#Static_prediction" rel="nofollow">http://en.wikipedia.org/wiki/Branch_predictor#Static_prediction</a></p> <p>Shuffling confounds the predictor by removing the groups of similar data and making each guess or prediction likely to be correct. Imagine a brand new deck of cards. A friend picks up each card and asks you to guess if it is red or black. </p> <p>At this point a fairly good algorithm would be to guess whatever the last card was. You would guess right nearly every time. > 90%</p> <p>After shuffling the deck however, this algorithm would only give 50% accuracy. In fact no algorithm will give you significantly better than 50%. (as far as I know, counting the number of reds and blacks left is the only way to get an edge in this situation.)</p> <p>Edit : Re Sub classing </p> <p>I would guess that this is because of CPU / L1/2/etc cache misses. Since each class implements the return value as a constant i.e. return 0 the return value is part of the function. I suspect if you re implemented the class as shown below you would force a cache miss on every call and see the same (bad) performance shuffled or not.</p> <pre><code> class Rabbit : Animal { int bartVal; // using a local int should force a call to memory for each instance of the class public Rabbit():base(3) { bartVal = 3; } public override int Bart { get { return bartVal; } } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POWhy put High chance clause into the front of nested If else would degenerate performance?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJason Hernandez
    1. USJason Hernandez
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POWhy put High chance clause into the front of nested If else would degenerate performance?
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COThank you very much for the excellent explanation. Would you be able also to share some knowledge regarding the fact that shuffled polymorphism runs slow than non-shuffled version.
      singulars
      1. PO
      1. UScolinfang
    2. COAlso, you should try experimenting with making one of the animals very common (like 90%) and see how that affects your timings :)
      singulars
      1. PO
      1. USJason Hernandez
    3. COThis answer is correct. I did a similar benchmark of this some time ago.
      singulars
      1. PO
      1. USusr
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload