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

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