git.ozlabs.org Git - ccan/blob - ccan/jmap/tools/speed.c

   1 /* Simple speed tests for jmap. */
   2 #include <ccan/jmap/jmap.c>
   3 #include <ccan/time/time.c>
   4 #include <stdio.h>
   5 #include <stdlib.h>
   6 #include <unistd.h>
   7
   8 struct object {
   9         /* Some contents. Doubles as consistency check. */
  10         struct object *self;
  11 };
  12
  13 struct jmap_obj {
  14         JMAP_MEMBERS(unsigned int, struct object *);
  15 };
  16
  17 /* Nanoseconds per operation */
  18 static size_t normalize(const struct timeabs *start,
  19                         const struct timeabs *stop,
  20                         unsigned int num)
  21 {
  22         return time_to_nsec(time_divide(time_between(*stop, *start), num));
  23 }
  24
  25 int main(int argc, char *argv[])
  26 {
  27         struct object *objs;
  28         unsigned int i, j;
  29         size_t num;
  30         struct timeabs start, stop;
  31         struct jmap_obj *jmap;
  32
  33         num = argv[1] ? atoi(argv[1]) : 1000000;
  34         objs = calloc(num, sizeof(objs[0]));
  35
  36         for (i = 0; i < num; i++) {
  37                 objs[i].self = &objs[i];
  38         }
  39
  40         jmap = jmap_new(struct jmap_obj);
  41
  42         printf("Initial insert: ");
  43         fflush(stdout);
  44         start = time_now();
  45         for (i = 0; i < num; i++)
  46                 jmap_add(jmap, i, objs[i].self);
  47         stop = time_now();
  48         printf(" %zu ns\n", normalize(&start, &stop, num));
  49
  50         printf("Initial lookup (match): ");
  51         fflush(stdout);
  52         start = time_now();
  53         for (i = 0; i < num; i++)
  54                 if (jmap_get(jmap, i)->self != objs[i].self)
  55                         abort();
  56         stop = time_now();
  57         printf(" %zu ns\n", normalize(&start, &stop, num));
  58
  59         printf("Initial lookup (miss): ");
  60         fflush(stdout);
  61         start = time_now();
  62         for (i = 0; i < num; i++)
  63                 if (jmap_get(jmap, i+num))
  64                         abort();
  65         stop = time_now();
  66         printf(" %zu ns\n", normalize(&start, &stop, num));
  67
  68         /* Lookups in order are very cache-friendly for judy; try random */
  69         printf("Initial lookup (random): ");
  70         fflush(stdout);
  71         start = time_now();
  72         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
  73                 if (jmap_get(jmap, j)->self != &objs[j])
  74                         abort();
  75         stop = time_now();
  76         printf(" %zu ns\n", normalize(&start, &stop, num));
  77
  78         printf("Initial delete all: ");
  79         fflush(stdout);
  80         start = time_now();
  81         for (i = 0; i < num; i++)
  82                 jmap_del(jmap, i);
  83         stop = time_now();
  84         printf(" %zu ns\n", normalize(&start, &stop, num));
  85
  86         printf("Initial re-inserting: ");
  87         fflush(stdout);
  88         start = time_now();
  89         for (i = 0; i < num; i++)
  90                 jmap_add(jmap, i, objs[i].self);
  91         stop = time_now();
  92         printf(" %zu ns\n", normalize(&start, &stop, num));
  93
  94         printf("Deleting first half: ");
  95         fflush(stdout);
  96         start = time_now();
  97         for (i = 0; i < num; i+=2)
  98                 jmap_del(jmap, i);
  99         stop = time_now();
 100         printf(" %zu ns\n", normalize(&start, &stop, num));
 101
 102         printf("Adding (a different) half: ");
 103         fflush(stdout);
 104
 105         start = time_now();
 106         for (i = 0; i < num; i+=2)
 107                 jmap_add(jmap, num+i, objs[i].self);
 108         stop = time_now();
 109         printf(" %zu ns\n", normalize(&start, &stop, num));
 110
 111         printf("Lookup after half-change (match): ");
 112         fflush(stdout);
 113         start = time_now();
 114         for (i = 1; i < num; i+=2)
 115                 if (jmap_get(jmap, i)->self != objs[i].self)
 116                         abort();
 117         for (i = 0; i < num; i+=2)
 118                 if (jmap_get(jmap, i+num)->self != objs[i].self)
 119                         abort();
 120         stop = time_now();
 121         printf(" %zu ns\n", normalize(&start, &stop, num));
 122
 123         printf("Lookup after half-change(miss): ");
 124         fflush(stdout);
 125         start = time_now();
 126         for (i = 0; i < num; i++)
 127                 if (jmap_get(jmap, i+num*2))
 128                         abort();
 129         stop = time_now();
 130         printf(" %zu ns\n", normalize(&start, &stop, num));
 131
 132         /* Hashtables with delete markers can fill with markers over time.
 133          * so do some changes to see how it operates in long-term. */
 134         printf("Details: churning first time\n");
 135         for (i = 1; i < num; i+=2) {
 136                 if (!jmap_del(jmap, i))
 137                         abort();
 138                 jmap_add(jmap, i, objs[i].self);
 139         }
 140         for (i = 0; i < num; i+=2) {
 141                 if (!jmap_del(jmap, i+num))
 142                         abort();
 143                 jmap_add(jmap, i, objs[i].self);
 144         }
 145         for (i = 1; i < 5; i++) {
 146                 printf("Churning %s time: ",
 147                        i == 1 ? "second"
 148                        : i == 2 ? "third"
 149                        : i == 3 ? "fourth"
 150                        : "fifth");
 151                 fflush(stdout);
 152
 153                 start = time_now();
 154                 for (j = 0; j < num; j++) {
 155                         if (!jmap_del(jmap, num*(i-1)+j))
 156                                 abort();
 157                         jmap_add(jmap, num*i+j, &objs[j]);
 158                 }
 159                 stop = time_now();
 160                 printf(" %zu ns\n", normalize(&start, &stop, num));
 161         }
 162
 163         /* Spread out the keys more to try to make it harder. */
 164         printf("Details: reinserting with spread\n");
 165         for (i = 0; i < num; i++) {
 166                 if (!jmap_del(jmap, num*4 + i))
 167                         abort();
 168                 jmap_add(jmap, num * 5 + i * 9, objs[i].self);
 169         }
 170
 171         if (jmap_popcount(jmap, 0, -1) != num)
 172                 abort();
 173
 174         printf("Lookup after churn & spread (match): ");
 175         fflush(stdout);
 176         start = time_now();
 177         for (i = 0; i < num; i++)
 178                 if (jmap_get(jmap, num * 5 + i * 9)->self != objs[i].self) {
 179                         printf("i  =%u\n", i);
 180                         abort();
 181                 }
 182         stop = time_now();
 183         printf(" %zu ns\n", normalize(&start, &stop, num));
 184
 185         printf("Lookup after churn & spread (miss): ");
 186         fflush(stdout);
 187         start = time_now();
 188         for (i = 0; i < num; i++)
 189                 if (jmap_get(jmap, num * 6 + i * 9))
 190                         abort();
 191         stop = time_now();
 192         printf(" %zu ns\n", normalize(&start, &stop, num));
 193
 194         printf("Lookup after churn & spread (random): ");
 195         fflush(stdout);
 196         start = time_now();
 197         for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num)
 198                 if (jmap_get(jmap, num * 5 + j * 9)->self != &objs[j])
 199                         abort();
 200         stop = time_now();
 201         printf(" %zu ns\n", normalize(&start, &stop, num));
 202
 203         printf("Lookup after churn & spread (half-random): ");
 204         fflush(stdout);
 205         start = time_now();
 206         for (i = 0, j = 0; i < num/2; i++, j = (j + 10007) % num) {
 207                 if (jmap_get(jmap, num * 5 + j * 9)->self != &objs[j])
 208                         abort();
 209                 if (jmap_get(jmap, num * 5 + (j + 1) * 9)->self != &objs[j+1])
 210                         abort();
 211         }
 212         stop = time_now();
 213         printf(" %zu ns\n", normalize(&start, &stop, num));
 214
 215         printf("Deleting half after churn & spread: ");
 216         fflush(stdout);
 217         start = time_now();
 218         for (i = 0; i < num; i+=2)
 219                 jmap_del(jmap, num * 5 + i * 9);
 220         stop = time_now();
 221         printf(" %zu ns\n", normalize(&start, &stop, num));
 222
 223         printf("Adding (a different) half after churn & spread: ");
 224         fflush(stdout);
 225
 226         start = time_now();
 227         for (i = 0; i < num; i+=2)
 228                 jmap_add(jmap, num * 6 + i * 9, objs[i].self);
 229         stop = time_now();
 230         printf(" %zu ns\n", normalize(&start, &stop, num));
 231
 232         jmap_free(jmap);
 233         free (objs);
 234
 235         return 0;
 236 }