Changeset 16261

Timestamp:

10/28/18 21:26:06 (6 years ago)

Author:

bburlacu

Message:

#2950: Fix bug in HashUtil.ToByteArray(). Improve hashing performance (10-15% gain) by avoiding array allocations for child node indices.

Location:

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing

Files:

• HashExtensions.cs (modified) (5 diffs)
• HashUtil.cs (modified) (1 diff)

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

@@ -82 +82 @@
       var node = nodes[i];
       var hashes = new int[node.Arity + 1];
-      int idx = 0;
-      foreach (int c in nodes.IterateChildren(i)) {
-        hashes[idx++] = nodes[c].CalculatedHashValue;
-      }
-      hashes[idx] = node.HashValue;
+      for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, k++) {
+        hashes[k] = nodes[j].CalculatedHashValue;
+      }
+      hashes[node.Arity] = node.HashValue;
       return HashUtil.JSHash(hashes);
     }
@@ -137 +136 @@
           } else { // i have some non-terminal children
             var sorted = new HashNode<T>[size];
-            var indices = nodes.IterateChildren(i);
+            var indices = new int[node.Arity];
+            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
+              indices[k] = j;
+            }
             Array.Sort(indices, sort);
 
@@ -158 +160 @@
 
     /// <summary>
-    /// Get a function node's child indices from left to right
+    /// Get a function node's child indicest
     /// </summary>
     /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
@@ -184 +186 @@
         }
         node.Size = node.Arity;
-        foreach (int j in nodes.IterateChildren(i)) {
+
+        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
           node.Size += nodes[j].Size;
         }
@@ -199 +202 @@
         }
 
-        foreach (var j in nodes.IterateChildren(i)) {
+        var arity = node.Arity;
+        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
           if (node.HashValue == nodes[j].HashValue) {
             nodes[j].Enabled = false;

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashUtil.cs

@@ -90 +90 @@
 
     public static byte[] ToByteArray(this int[] input) {
-      const int size = sizeof(int);
       var bytes = new byte[input.Length * sizeof(int)];
-      for (int i = 0; i < input.Length; ++i) {
-        Array.Copy(BitConverter.GetBytes(bytes[i]), 0, bytes, i * size, size);
+      int pos = 0;
+      foreach (var v in input) {
+        var b0 = (byte)((v >> 24) & 0xFF);
+        var b1 = (byte)((v >> 16) & 0xFF);
+        var b2 = (byte)((v >> 8) & 0xFF);
+        var b3 = (byte)(v & 0xFF);
+        bytes[pos++] = b0;
+        bytes[pos++] = b1;
+        bytes[pos++] = b2;
+        bytes[pos++] = b3;
       }
       return bytes;