~adam-hraska+lp/helenos/cht-bench

« back to all changes in this revision

Viewing changes to kernel/generic/src/bench/cht_bench.c

  • Committer: Adam Hraska
  • Date: 2012-08-04 11:43:17 UTC
  • Revision ID: adam.hraska+hos@gmail.com-20120804114317-9te94sj6zv8wrbnq
Added pure (concurrent) hash table lookup benchmarks (no checking of upd_frac like in update tests).

Show diffs side-by-side

added added

removed removed

Lines of Context:
151
151
static void deinit_cht(const bench_info_t *b, void *p);
152
152
static size_t rcu_upd_cht(bench_loop_input_t *in);
153
153
 
 
154
static size_t s_lookup_ht(bench_loop_input_t *in);
 
155
static size_t bkt_s_lookup_ht(bench_loop_input_t *in);
 
156
static size_t rcu_lookup_cht(bench_loop_input_t *in);
 
157
 
154
158
 
155
159
static size_t shift_loop(bench_loop_input_t *input);
156
160
static size_t div_127_loop(bench_loop_input_t *input);
251
255
                .desc = "Updates a hash table protected by a spinlock/bucket." 
252
256
        },
253
257
        { 
 
258
                .f = rcu_lookup_cht, 
 
259
                .ctor = init_cht, 
 
260
                .dtor = deinit_cht,
 
261
                .name = "cht-lookup-rcu",
 
262
                .desc = "Looks up keys in a CHT protected by rcu." 
 
263
        },
 
264
        { 
 
265
                .f = s_lookup_ht, 
 
266
                .ctor = init_ht, 
 
267
                .dtor = deinit_ht,
 
268
                .name = "ht-lookup-s-lock",
 
269
                .desc = "Looks up keys in a hash table protected by a spinlock." 
 
270
        },
 
271
        { 
 
272
                .f = bkt_s_lookup_ht, 
 
273
                .ctor = init_ht, 
 
274
                .dtor = deinit_ht,
 
275
                .name = "ht-upd-bkt-lock",
 
276
                .desc = "Looks up keys in a hash table protected by a spinlock/bucket." 
 
277
        },
 
278
        { 
254
279
                .f = shift_loop, 
255
280
                .ctor = init_nop_bench, 
256
281
                .dtor = deinit_nop_bench,
1447
1472
 
1448
1473
 
1449
1474
/*-------------------------------------------------------------------*/
 
1475
 
 
1476
static inline size_t s_lookup_ht_kernel(ht_upd_t *data, size_t id, size_t k, 
 
1477
        size_t key)
 
1478
{
 
1479
        link_t *item = hash_table_find(&data->ht, &key);
 
1480
 
 
1481
        if (item) {
 
1482
                ASSERT(data->inserted_bitmap[id][k]);
 
1483
                ht_elem_t *e = member_to_inst(item, ht_elem_t, ht_link);
 
1484
                ASSERT(e->key == key);
 
1485
                return e->key;
 
1486
        } else {
 
1487
                ASSERT(!data->inserted_bitmap[id][k]);
 
1488
                return 0;
 
1489
        }
 
1490
}
 
1491
 
 
1492
static size_t s_lookup_ht(bench_loop_input_t *in)
 
1493
{
 
1494
        ht_upd_t *data = (ht_upd_t*)in->data;
 
1495
        
 
1496
        /* Sum keys in the hash table a store the result in dummy. */
 
1497
        size_t dummy = 0;
 
1498
        
 
1499
        for (size_t loops = 0; loops < default_loop_cnt ; ++loops) {
 
1500
                in->seed = next_rand(in->seed);
 
1501
                size_t k = in->seed % data->key_cnt_per_thr;
 
1502
                size_t key = (k << 8) + in->id;
 
1503
 
 
1504
                spinlock_lock(&data->bktlock[0]);
 
1505
                
 
1506
                dummy += s_lookup_ht_kernel(data, in->id, k, key);
 
1507
 
 
1508
                spinlock_unlock(&data->bktlock[0]);
 
1509
        }
 
1510
        /* Use the dummy total to prevent the compiler from removing the loop. */
 
1511
        in->dummy = dummy;
 
1512
        return default_loop_cnt;
 
1513
}
 
1514
 
 
1515
static size_t bkt_s_lookup_ht(bench_loop_input_t *in)
 
1516
{
 
1517
        ht_upd_t *data = (ht_upd_t*)in->data;
 
1518
        
 
1519
        /* Sum keys in the hash table a store the result in dummy. */
 
1520
        size_t dummy = 0;
 
1521
        
 
1522
        for (size_t loops = 0; loops < default_loop_cnt ; ++loops) {
 
1523
                in->seed = next_rand(in->seed);
 
1524
                size_t k = in->seed % data->key_cnt_per_thr;
 
1525
                size_t key = (k << 8) + in->id;
 
1526
                size_t bkt = key % ht_bucket_cnt;
 
1527
 
 
1528
                spinlock_lock(&data->bktlock[bkt]);
 
1529
                
 
1530
                dummy += s_lookup_ht_kernel(data, in->id, k, key);
 
1531
 
 
1532
                spinlock_unlock(&data->bktlock[bkt]);
 
1533
        }
 
1534
        /* Use the dummy total to prevent the compiler from removing the loop. */
 
1535
        in->dummy = dummy;
 
1536
        return default_loop_cnt;
 
1537
}
 
1538
 
 
1539
 
 
1540
static size_t rcu_lookup_cht(bench_loop_input_t *in)
 
1541
{
 
1542
        ht_upd_t *data = (ht_upd_t*)in->data;
 
1543
        
 
1544
        /* Sum keys in the hash table a store the result in dummy. */
 
1545
        size_t dummy = 0;
 
1546
        
 
1547
        for (size_t loops = 0; loops < default_loop_cnt ; ++loops) {
 
1548
                in->seed = next_rand(in->seed);
 
1549
                size_t k = in->seed % data->key_cnt_per_thr;
 
1550
                size_t key = (k << 8) + in->id;
 
1551
 
 
1552
                /* Update the table - add *or* remove one item. */
 
1553
                rcu_read_lock();
 
1554
                //spinlock_lock(&data->slock);
 
1555
 
 
1556
                cht_link_t *item = cht_find_lazy(&data->cht, &key);
 
1557
                //cht_link_t *item = cht_find(&data->cht, &key);
 
1558
 
 
1559
                if (item) {
 
1560
                        ASSERT(data->inserted_bitmap[in->id][k]);
 
1561
                        ht_elem_t *e = member_to_inst(item, ht_elem_t, cht_link);
 
1562
                        ASSERT(e->key == key);
 
1563
                        dummy += e->key;
 
1564
                } else {
 
1565
                        ASSERT(!data->inserted_bitmap[in->id][k]);
 
1566
                }
 
1567
 
 
1568
                //spinlock_unlock(&data->slock);
 
1569
                rcu_read_unlock();
 
1570
        }
 
1571
        /* Use the dummy total to prevent the compiler from removing the loop. */
 
1572
        in->dummy = dummy;
 
1573
        return default_loop_cnt;
 
1574
}
 
1575
 
1450
1576
/*-------------------------------------------------------------------*/
1451
1577
/*-------------------------------------------------------------------*/
1452
1578