mono/unit-tests/test-conc-hashtable.c

   1 /*
   2  * test-conc-hashtable.c: Unit test for the concurrent hashtable.
   3  *
   4  * Copyright (C) 2014 Xamarin Inc
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Library General Public
   8  * License 2.0 as published by the Free Software Foundation;
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Library General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Library General Public
  16  * License 2.0 along with this library; if not, write to the Free
  17  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19
  20 #include "config.h"
  21
  22 #include "utils/mono-threads.h"
  23 #include "utils/mono-conc-hashtable.h"
  24
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <time.h>
  28 #include <assert.h>
  29
  30 #include <pthread.h>
  31
  32 static int
  33 single_writer_single_reader (void)
  34 {
  35         mono_mutex_t mutex;
  36         MonoConcurrentHashTable *h;
  37         int res = 0;
  38
  39         mono_mutex_init (&mutex);
  40         h = mono_conc_hashtable_new (&mutex, NULL, NULL);
  41         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (10), GUINT_TO_POINTER (20));
  42         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (30), GUINT_TO_POINTER (40));
  43         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (50), GUINT_TO_POINTER (60));
  44         mono_conc_hashtable_insert (h, GUINT_TO_POINTER (2), GUINT_TO_POINTER (3));
  45
  46         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (30)) != GUINT_TO_POINTER (40))
  47                 res = 1;
  48         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (10)) != GUINT_TO_POINTER (20))
  49                 res = 2;
  50         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (2)) != GUINT_TO_POINTER (3))
  51                 res = 3;
  52         if (mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (50)) != GUINT_TO_POINTER (60))
  53                 res = 4;
  54
  55         mono_conc_hashtable_destroy (h);
  56         mono_mutex_destroy (&mutex);
  57         if (res)
  58                 printf ("SERIAL TEST FAILED %d\n", res);
  59         return res;
  60 }
  61
  62 static MonoConcurrentHashTable *hash;
  63
  64 static void*
  65 pw_sr_thread (void *arg)
  66 {
  67         int i, idx = 1000 * GPOINTER_TO_INT (arg);
  68         mono_thread_info_attach ((gpointer)&arg);
  69
  70         for (i = 0; i < 1000; ++i)
  71                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + idx), GINT_TO_POINTER (i + 1));
  72         return NULL;
  73 }
  74
  75 static int
  76 parallel_writer_single_reader (void)
  77 {
  78         pthread_t a,b,c;
  79         mono_mutex_t mutex;
  80         int i, j, res = 0;
  81
  82         mono_mutex_init (&mutex);
  83         hash = mono_conc_hashtable_new (&mutex, NULL, NULL);
  84
  85         pthread_create (&a, NULL, pw_sr_thread, GINT_TO_POINTER (1));
  86         pthread_create (&b, NULL, pw_sr_thread, GINT_TO_POINTER (2));
  87         pthread_create (&c, NULL, pw_sr_thread, GINT_TO_POINTER (3));
  88
  89         pthread_join (a, NULL);
  90         pthread_join (b, NULL);
  91         pthread_join (c, NULL);
  92
  93         for (i = 0; i < 1000; ++i) {
  94                 for (j = 1; j < 4; ++j) {
  95                         if (mono_conc_hashtable_lookup (hash, GINT_TO_POINTER (j * 1000 + i)) != GINT_TO_POINTER (i + 1)) {
  96                                 res = j + 1;
  97                                 goto done;
  98                         }
  99                 }
 100         }
 101
 102 done:
 103         mono_conc_hashtable_destroy (hash);
 104         mono_mutex_destroy (&mutex);
 105         if (res)
 106                 printf ("PAR_WRITER_SINGLE_READER TEST FAILED %d\n", res);
 107         return res;
 108 }
 109
 110
 111 static void*
 112 pr_sw_thread (void *arg)
 113 {
 114         int i = 0, idx = 100 * GPOINTER_TO_INT (arg);
 115         mono_thread_info_attach ((gpointer)&arg);
 116
 117         while (i < 100) {
 118                 gpointer res = mono_conc_hashtable_lookup (hash, GINT_TO_POINTER (i + idx + 1));
 119                 if (!res)
 120                         continue;
 121                 if (res != GINT_TO_POINTER ((i + idx) * 2 + 1))
 122                         return GINT_TO_POINTER (i);
 123                 ++i;
 124         }
 125         return NULL;
 126 }
 127
 128 static int
 129 single_writer_parallel_reader (void)
 130 {
 131         pthread_t a,b,c;
 132         mono_mutex_t mutex;
 133         gpointer ra, rb, rc;
 134         int i, res = 0;
 135         ra = rb = rc = GINT_TO_POINTER (1);
 136
 137         mono_mutex_init (&mutex);
 138         hash = mono_conc_hashtable_new (&mutex, NULL, NULL);
 139
 140         pthread_create (&a, NULL, pr_sw_thread, GINT_TO_POINTER (0));
 141         pthread_create (&b, NULL, pr_sw_thread, GINT_TO_POINTER (1));
 142         pthread_create (&c, NULL, pr_sw_thread, GINT_TO_POINTER (2));
 143
 144         for (i = 0; i < 100; ++i) {
 145                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i +   0 + 1), GINT_TO_POINTER ((i +   0) * 2 + 1));
 146                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + 100 + 1), GINT_TO_POINTER ((i + 100) * 2 + 1));
 147                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + 200 + 1), GINT_TO_POINTER ((i + 200) * 2 + 1));
 148         }
 149
 150         pthread_join (a, &ra);
 151         pthread_join (b, &rb);
 152         pthread_join (c, &rc);
 153         res = GPOINTER_TO_INT (ra) + GPOINTER_TO_INT (rb) + GPOINTER_TO_INT (rc);
 154
 155         mono_conc_hashtable_destroy (hash);
 156         mono_mutex_destroy (&mutex);
 157         if (res)
 158                 printf ("SINGLE_WRITER_PAR_READER TEST FAILED %d\n", res);
 159         return res;
 160 }
 161
 162 int running = 1;
 163
 164 static void*
 165 pw_pr_r_thread (void *arg)
 166 {
 167         int key, val, i;
 168         mono_thread_info_attach ((gpointer)&arg);
 169
 170         /* i will not be incremented as long as running is set to 1, this guarantee that
 171            we loop over all the keys at least once after the writer threads have finished */
 172         for (i = 0; i < 2; i += 1 - running) {
 173                 for (key = 1; key < 3 * 1000 + 1; key++) {
 174                         val = GPOINTER_TO_INT (mono_conc_hashtable_lookup (hash, GINT_TO_POINTER (key)));
 175
 176                         if (!val)
 177                                 continue;
 178                         if (key != val)
 179                                 return GINT_TO_POINTER (key);
 180                 }
 181         }
 182         return NULL;
 183 }
 184
 185 static void*
 186 pw_pr_w_add_thread (void *arg)
 187 {
 188         int i, idx = 1000 * GPOINTER_TO_INT (arg);
 189
 190         mono_thread_info_attach ((gpointer)&arg);
 191
 192         for (i = idx; i < idx + 1000; i++)
 193                 mono_conc_hashtable_insert (hash, GINT_TO_POINTER (i + 1), GINT_TO_POINTER (i + 1));
 194         return NULL;
 195 }
 196
 197 static void*
 198 pw_pr_w_del_thread (void *arg)
 199 {
 200         int i, idx = 1000 * GPOINTER_TO_INT (arg);
 201
 202         mono_thread_info_attach ((gpointer)&arg);
 203
 204         for (i = idx; i < idx + 1000; i++)
 205                 mono_conc_hashtable_remove (hash, GINT_TO_POINTER (i + 1));
 206         return NULL;
 207 }
 208
 209 static int
 210 parallel_writer_parallel_reader (void)
 211 {
 212         pthread_t wa, wb, wc, ra, rb, rc;
 213         mono_mutex_t mutex;
 214         gpointer a, b, c;
 215         int res = 0, i;
 216
 217         srand(time(NULL));
 218
 219         mono_mutex_init (&mutex);
 220         hash = mono_conc_hashtable_new (&mutex, NULL, NULL);
 221
 222         for (i = 0; i < 2; i++) {
 223                 running = 1;
 224
 225                 pthread_create (&ra, NULL, pw_pr_r_thread, NULL);
 226                 pthread_create (&rb, NULL, pw_pr_r_thread, NULL);
 227                 pthread_create (&rc, NULL, pw_pr_r_thread, NULL);
 228
 229                 switch (i) {
 230                 case 0:
 231                         pthread_create (&wa, NULL, pw_pr_w_add_thread, GINT_TO_POINTER (0));
 232                         pthread_create (&wb, NULL, pw_pr_w_add_thread, GINT_TO_POINTER (1));
 233                         pthread_create (&wc, NULL, pw_pr_w_add_thread, GINT_TO_POINTER (2));
 234                         break;
 235                 case 1:
 236                         pthread_create (&wa, NULL, pw_pr_w_del_thread, GINT_TO_POINTER (0));
 237                         pthread_create (&wb, NULL, pw_pr_w_del_thread, GINT_TO_POINTER (1));
 238                         pthread_create (&wc, NULL, pw_pr_w_del_thread, GINT_TO_POINTER (2));
 239                         break;
 240                 }
 241
 242                 pthread_join (wa, NULL);
 243                 pthread_join (wb, NULL);
 244                 pthread_join (wc, NULL);
 245
 246                 running = 0;
 247
 248                 pthread_join (ra, &a);
 249                 pthread_join (rb, &b);
 250                 pthread_join (rc, &c);
 251
 252                 res += GPOINTER_TO_INT (a) + GPOINTER_TO_INT (b) + GPOINTER_TO_INT (c);
 253         }
 254
 255         if (res)
 256                 printf ("PAR_WRITER_PAR_READER TEST FAILED %d %d %d\n", GPOINTER_TO_INT (a), GPOINTER_TO_INT (b), GPOINTER_TO_INT (c));
 257
 258         mono_conc_hashtable_destroy (hash);
 259         mono_mutex_destroy (&mutex);
 260
 261         return res;
 262 }
 263
 264 static void
 265 benchmark_conc (void)
 266 {
 267         mono_mutex_t mutex;
 268         MonoConcurrentHashTable *h;
 269         int i, j;
 270
 271         mono_mutex_init (&mutex);
 272         h = mono_conc_hashtable_new (&mutex, NULL, NULL);
 273
 274         for (i = 1; i < 10 * 1000; ++i)
 275                 mono_conc_hashtable_insert (h, GUINT_TO_POINTER (i), GUINT_TO_POINTER (i));
 276
 277
 278         for (j = 0; j < 100000; ++j)
 279                 for (i = 1; i < 10 * 105; ++i)
 280                         mono_conc_hashtable_lookup (h, GUINT_TO_POINTER (i));
 281
 282         mono_conc_hashtable_destroy (h);
 283         mono_mutex_destroy (&mutex);
 284
 285 }
 286
 287 static void
 288 benchmark_glib (void)
 289 {
 290         GHashTable *h;
 291         int i, j;
 292
 293         h = g_hash_table_new (NULL, NULL);
 294
 295         for (i = 1; i < 10 * 1000; ++i)
 296                 g_hash_table_insert (h, GUINT_TO_POINTER (i), GUINT_TO_POINTER (i));
 297
 298
 299         for (j = 0; j < 100000; ++j)
 300                 for (i = 1; i < 10 * 105; ++i)
 301                         g_hash_table_lookup (h, GUINT_TO_POINTER (i));
 302
 303         g_hash_table_destroy (h);
 304 }
 305
 306 int
 307 main (void)
 308 {
 309         MonoThreadInfoCallbacks cb = { NULL };
 310         int res = 0;
 311
 312         mono_threads_init (&cb, sizeof (MonoThreadInfo));
 313         mono_thread_info_attach ((gpointer)&cb);
 314
 315         // benchmark_conc ();
 316         // benchmark_glib ();
 317
 318         res += single_writer_single_reader ();
 319         res += parallel_writer_single_reader ();
 320         res += single_writer_parallel_reader ();
 321         res += parallel_writer_parallel_reader ();
 322
 323         return res;
 324 }