Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

    r16260 r16261  
    8282      var node = nodes[i];
    8383      var hashes = new int[node.Arity + 1];
    84       int idx = 0;
    85       foreach (int c in nodes.IterateChildren(i)) {
    86         hashes[idx++] = nodes[c].CalculatedHashValue;
    87       }
    88       hashes[idx] = node.HashValue;
     84      for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, k++) {
     85        hashes[k] = nodes[j].CalculatedHashValue;
     86      }
     87      hashes[node.Arity] = node.HashValue;
    8988      return HashUtil.JSHash(hashes);
    9089    }
     
    137136          } else { // i have some non-terminal children
    138137            var sorted = new HashNode<T>[size];
    139             var indices = nodes.IterateChildren(i);
     138            var indices = new int[node.Arity];
     139            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
     140              indices[k] = j;
     141            }
    140142            Array.Sort(indices, sort);
    141143
     
    158160
    159161    /// <summary>
    160     /// Get a function node's child indices from left to right
     162    /// Get a function node's child indicest
    161163    /// </summary>
    162164    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
     
    184186        }
    185187        node.Size = node.Arity;
    186         foreach (int j in nodes.IterateChildren(i)) {
     188
     189        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
    187190          node.Size += nodes[j].Size;
    188191        }
     
    199202        }
    200203
    201         foreach (var j in nodes.IterateChildren(i)) {
     204        var arity = node.Arity;
     205        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
    202206          if (node.HashValue == nodes[j].HashValue) {
    203207            nodes[j].Enabled = false;
  • trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashUtil.cs

    r16218 r16261  
    9090
    9191    public static byte[] ToByteArray(this int[] input) {
    92       const int size = sizeof(int);
    9392      var bytes = new byte[input.Length * sizeof(int)];
    94       for (int i = 0; i < input.Length; ++i) {
    95         Array.Copy(BitConverter.GetBytes(bytes[i]), 0, bytes, i * size, size);
     93      int pos = 0;
     94      foreach (var v in input) {
     95        var b0 = (byte)((v >> 24) & 0xFF);
     96        var b1 = (byte)((v >> 16) & 0xFF);
     97        var b2 = (byte)((v >> 8) & 0xFF);
     98        var b3 = (byte)(v & 0xFF);
     99        bytes[pos++] = b0;
     100        bytes[pos++] = b1;
     101        bytes[pos++] = b2;
     102        bytes[pos++] = b3;
    96103      }
    97104      return bytes;
Note: See TracChangeset for help on using the changeset viewer.