Databases
StackOverflow2013
Postsdbo
POWhy does my application spend 24% of its life doing a null check?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhy does my application spend 24% of its life doing a null check?
    primarykey
    data
    text
    <p>I've got a performance critical binary decision tree, and I'd like to focus this question on a single line of code. The code for the binary tree iterator is below with the results from running performance analysis against it.</p> <pre><code> public ScTreeNode GetNodeForState(int rootIndex, float[] inputs) { 0.2% ScTreeNode node = RootNodes[rootIndex].TreeNode; 24.6% while (node.BranchData != null) { 0.2% BranchNodeData b = node.BranchData; 0.5% node = b.Child2; 12.8% if (inputs[b.SplitInputIndex] &lt;= b.SplitValue) 0.8% node = b.Child1; } 0.4% return node; } </code></pre> <p><strong>BranchData is a field, not a property.</strong> I did this to prevent the risk of it not being inlined.</p> <p>The BranchNodeData class is as follows:</p> <pre><code>public sealed class BranchNodeData { /// &lt;summary&gt; /// The index of the data item in the input array on which we need to split /// &lt;/summary&gt; internal int SplitInputIndex = 0; /// &lt;summary&gt; /// The value that we should split on /// &lt;/summary&gt; internal float SplitValue = 0; /// &lt;summary&gt; /// The nodes children /// &lt;/summary&gt; internal ScTreeNode Child1; internal ScTreeNode Child2; } </code></pre> <p>As you can see, the while loop / null check is a massive hit on performance. The tree is massive, so I would expect searching for a leaf to take a while, but I'd like to understand the disproportionate amount of time spent on that one line.</p> <p>I've tried:</p> <ul> <li>Separating the Null check from the while - it's the Null check that's the hit.</li> <li>Adding a boolean field to the object and checking against that, it made no difference. It doesn't matter what's being compared, it's the comparison that's the issue.</li> </ul> <p>Is this a branch prediction issue? If so, what can I do about it? If anything?</p> <p>I won't pretend to understand the <a href="http://en.wikipedia.org/wiki/Common_Intermediate_Language" rel="nofollow noreferrer">CIL</a>, but I'll post it for anyone does so they can try to scrape some information from it.</p> <pre><code>.method public hidebysig instance class OptimalTreeSearch.ScTreeNode GetNodeForState ( int32 rootIndex, float32[] inputs ) cil managed { // Method begins at RVA 0x2dc8 // Code size 67 (0x43) .maxstack 2 .locals init ( [0] class OptimalTreeSearch.ScTreeNode node, [1] class OptimalTreeSearch.BranchNodeData b ) IL_0000: ldarg.0 IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1&lt;class OptimalTreeSearch.ScRootNode&gt; OptimalTreeSearch.ScSearchTree::RootNodes IL_0006: ldarg.1 IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1&lt;class OptimalTreeSearch.ScRootNode&gt;::get_Item(int32) IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode IL_0011: stloc.0 IL_0012: br.s IL_0039 // loop start (head: IL_0039) IL_0014: ldloc.0 IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData IL_001a: stloc.1 IL_001b: ldloc.1 IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2 IL_0021: stloc.0 IL_0022: ldarg.2 IL_0023: ldloc.1 IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex IL_0029: ldelem.r4 IL_002a: ldloc.1 IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue IL_0030: bgt.un.s IL_0039 IL_0032: ldloc.1 IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1 IL_0038: stloc.0 IL_0039: ldloc.0 IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData IL_003f: brtrue.s IL_0014 // end loop IL_0041: ldloc.0 IL_0042: ret } // end of method ScSearchTree::GetNodeForState </code></pre> <p><strong>Edit:</strong> I decided to do a branch prediction test, I added an identical if within the while, so we have</p> <pre><code>while (node.BranchData != null) </code></pre> <p>and</p> <pre><code>if (node.BranchData != null) </code></pre> <p>inside that. I then ran performance analysis against that, and it took six times longer to execute the first comparison as it did to execute the second comparison that always returned true. So it looks like it is indeed a branch prediction issue - and I'm guessing there's nothing I can do about it?!</p> <p><strong>Another Edit</strong></p> <p>The above result would also occur if node.BranchData had to be loaded from the RAM for the while check - it would then be cached for the if statement.</p> <hr/> <p>This is my third question on a similar topic. This time I'm focusing on a single line of code. My other questions on this subject are:</p> <ul> <li><a href="https://stackoverflow.com/questions/16539564/could-i-use-a-faster-data-structure-than-a-tree-for-this">Could I use a faster data structure than a tree for this?</a></li> <li><a href="https://stackoverflow.com/questions/16416084/micro-optimisations-iterating-through-a-tree-in-c-sharp">Micro optimisations iterating through a tree in C#</a></li> </ul>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCommunity
    1. USWill Calderwood
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWhy does my application spend 24% of its life doing a null check?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POWhy does my application spend 24% of its life doing a null check?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POWhy does my application spend 24% of its life doing a null check?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COPlease show the implementation of the `BranchNode` property. Please try to replace `node.BranchData != null` `ReferenceEquals(node.BranchData, null)`. Does it make any difference?
      singulars
      1. POWhy does my application spend 24% of its life doing a null check?
      1. USDaniel Hilgarth
    2. COAre you sure that the 24% are not for the while statement and not the condition expression that part of the while statement
      singulars
      1. POWhy does my application spend 24% of its life doing a null check?
      1. USRune FS
    3. COAnother test: Try to re-write your while loop like this: `while(true) { /* current body */ if(node.BranchData == null) return node; }`. Does it change anything?
      singulars
      1. POWhy does my application spend 24% of its life doing a null check?
      1. USDaniel Hilgarth
 

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