The Universe of Disco

A fun optimization trick from rsync

I was looking at the rsync source code today and I saw a neat trick I'd never seen before. It wants to try to set the mtime on a file, and there are several methods that might work, but it doesn't know which. So it tries them in sequence, and then it remembers which one worked and uses that method on subsequent calls:

    int set_the_mtime(...) {
      static int switch_step = 0;

      switch (switch_step) {

        case 0:
          if (method_0_works(...))
            break;

          switch_step++;
          /* FALLTHROUGH */

        case 1:
          if (method_1_works(...))
            break;

          switch_step++;
          /* FALLTHROUGH */

        case 2:
        ...

        case 17:
          if (method_17_works(...))
            break;

          return -1;   /* ultimate failure */
      }
      return 0;  /* success */
    }

The key item here is the static switch_step variable. The first time the function is called, its value is 0 and the switch starts at case 0. If methods 0 through 7 all fail and method 8 succeeds, switch_step will have been set to 8, and on subsequent calls to the function the switch will jump immediately to case 8.

The actual code is a little more sophisticated than this. The list of cases is built depending on the setting of several compile-time config flags, so that the code that is compiled only includes the methods that are actually callable. Calling one of the methods can produce three distinguishable results: success, real failure (because of permission problems or some such), or a sort of fake failure (ENOSYS) that only means that the underlying syscall is unimplemented. This third type of result is the one where it makes sense to try another method. So the cases actually look like this:

        case 7:
              if (method_7_works(...))
                break;
              if (errno != ENOSYS)
                return -1;   /* real failure */
              switch_step++;
              /* FALLTHROUGH */

On top of this there's another trick: since the various cases are conditionally compiled depending on the config flags, we don't know ahead of time which ones will be included. So the case labels themselves are generated at compile time this way:

        #include "case_N.h"
            if (method_7_works(...))
              break;
            ...
        #include "case_N.h"
            if (method_8_works(...))
              break;
            ...

The first time we #include "case_N.h", it turns into case 0:; the second time, it turns into case 1:, and so on:

    #if !defined CASE_N_STATE_0
    #define CASE_N_STATE_0
            case 0:
    #elif !defined CASE_N_STATE_1
    #define CASE_N_STATE_1
            case 1:
    ...
    #else
    #error Need to add more case statements!
    #endif

Unfortunately you can only use this trick one switch per file. Although I suppose if you really wanted to reuse it you could make a reset_case_N.h file which would contain

    #undef CASE_N_STATE_0
    #undef CASE_N_STATE_1
    ...

[ Addendum 20181028: Simon Tatham brought up a technique for generating the case labels that we agree is better than what rsync did. ]

[Other articles in category /prog] permanent link