Uploaded image for project: 'CFEngine Community'
  1. CFEngine Community
  2. CFE-2564

Splayclass is not properly spread

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Rejected
    • Priority: Medium
    • Resolution: Won't Do
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Built-in functions
    • Labels:
      None

      Description

      The hash used for splayclass is Jenkins one-at-a-time
      The values used to create the hash are ascii strings.

      So I created a code to test the result of the hash over ascii strings.

      When using it I found that there is only between 50% and 60% of possible values that are produced.

      Here is a typical example :

      #first argument is the number of tests, second argument is the length of the test string

        ./a.out 100 8 | sort | uniq -c
            8 0
            6 1
           19 10
            9 11
           20 2
           13 3
           10 8
           15 9
      

      4 5 6 7 are never produced.
      This affect agent run repartition since there are some time slot that will never be used.

      So I suggest using a better hashing function.

      Here is the test code :

      #include <stdlib.h>
      #include <stdio.h>
      #include <string.h>
      #include <time.h>
      
      unsigned int StringHash(const char *str, unsigned int seed, unsigned int max)
      {
          unsigned const char *p = str;
          unsigned int h = seed;
          size_t len = strlen(str);
      
          for (size_t i = 0; i < len; i++)
          {
              h += p[i];
              h += (h << 10);
              h ^= (h >> 6);
          }
      
          h += (h << 3);
          h ^= (h >> 11);
          h += (h << 15);
      
          return (h & (max - 1));
      }
      
      int main(int argc, char* argv[]) {
        unsigned char str[255];
        unsigned int h;
        int maxcount=atoi(argv[1]);
        int maxlen=atoi(argv[2]);
        srand(time(NULL));
        for(int i =0; i< maxcount;i++)
        {
          for(int j=0;j<maxlen;j++)
          {
            str[j] = rand()%(127+32)+32;
          }
          str[5] = '\0';
          h = StringHash(str, 0, 12);
          printf("%i\n", h);
        }
        //unsigned int h = StringHash(argv[1], 0, 12);
        //printf("arg '%s' -> %i\n", argv[1], h); 
        //printf("%i\n", h);
      }
      

        Attachments

          Activity

            People

            • Assignee:
              a10003 Eystein Maloy Stenberg
              Reporter:
              peckpeck Benoît Peccatte
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Summary Panel