← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/bmagic/oneiric

« back to all changes in this revision

Viewing changes to .pc/g++-4.4.patch/tests/perf/perf.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Roberto C. Sanchez
  • Date: 2011-03-03 12:22:16 UTC
  • mfrom: (4.1.8 sid)
  • Revision ID: james.westby@ubuntu.com-20110303122216-qll5migewxnxe3s5
Tags: 3.7.0-1
http://bugs.debian.org/615929
* New upstream release (Closes: #615929)
* Update to Standards-Version 3.9.1 (no changes)
* Specify Debian source format as '3.0 (quilt)'

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/g++-4.4.patch/tests/perf/perf.cpp
 
1
/*
 
2
Copyright (c) 2002-2009 Anatoliy Kuznetsov.
 
3
 
 
4
Permission is hereby granted, free of charge, to any person 
 
5
obtaining a copy of this software and associated documentation 
 
6
files (the "Software"), to deal in the Software without restriction, 
 
7
including without limitation the rights to use, copy, modify, merge, 
 
8
publish, distribute, sublicense, and/or sell copies of the Software, 
 
9
and to permit persons to whom the Software is furnished to do so, 
 
10
subject to the following conditions:
 
11
 
 
12
The above copyright notice and this permission notice shall be included 
 
13
in all copies or substantial portions of the Software.
 
14
 
 
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
 
16
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
 
17
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
 
18
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
 
19
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
 
20
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
 
21
OTHER DEALINGS IN THE SOFTWARE.
 
22
*/
 
23
 
 
24
#include <bitset>
 
25
#include <iostream>
 
26
#include <time.h>
 
27
#include <stdio.h>
 
28
 
 
29
// No intermix FP with integer SSE in this program
 
30
//#define BM_SET_MMX_GUARD
 
31
//#define BMSSE2OPT
 
32
//#define BMSSE42OPT
 
33
//#define BM64OPT
 
34
 
 
35
#ifdef _MSC_VER
 
36
#pragma warning( push )
 
37
#pragma warning( disable : 4996)
 
38
#endif
 
39
 
 
40
 
 
41
#include "bm.h"
 
42
#include "bmalgo.h"
 
43
#include "bmserial.h"
 
44
//#include "bmdbg.h"
 
45
 
 
46
#include <math.h>
 
47
 
 
48
using namespace std;
 
49
 
 
50
const unsigned BSIZE = 150000000;
 
51
const unsigned int REPEATS = 300;
 
52
 
 
53
typedef  bitset<BSIZE>  test_bitset;
 
54
 
 
55
unsigned platform_test = 1;
 
56
 
 
57
 
 
58
class TimeTaker
 
59
{
 
60
public:
 
61
 
 
62
    TimeTaker(const char* test_name, unsigned repeats) 
 
63
        : test_name_(test_name), repeats_(repeats) 
 
64
    {
 
65
        start_ = clock();
 
66
    }
 
67
 
 
68
    ~TimeTaker()
 
69
    {
 
70
        finish_ = clock();
 
71
        clock_t elapsed_clocks = finish_ - start_;
 
72
        double duration = (double)(finish_ - start_) / CLOCKS_PER_SEC;
 
73
 
 
74
        cout << test_name_ << " ; ";
 
75
        if (platform_test) 
 
76
        {
 
77
            cout << duration << endl;
 
78
            return;
 
79
        }
 
80
 
 
81
        cout <<  elapsed_clocks << ";" << duration << ";";
 
82
        if (repeats_)
 
83
        {
 
84
            double ops_per_sec = (double)repeats_ / duration;
 
85
            cout << ops_per_sec;
 
86
        }
 
87
        cout << endl;
 
88
    }
 
89
 
 
90
private:
 
91
    const char*  test_name_;
 
92
    clock_t      start_;
 
93
    clock_t      finish_;
 
94
    unsigned     repeats_;
 
95
};
 
96
 
 
97
typedef bm::bvector<> bvect;
 
98
 
 
99
 
 
100
void SimpleFillSets(test_bitset& bset, 
 
101
                     bvect& bvect,
 
102
                       unsigned min, 
 
103
                       unsigned max,
 
104
                       unsigned fill_factor,
 
105
                       bool set_flag=true)
 
106
{
 
107
    for (unsigned i = min; i < max; i+=fill_factor)
 
108
    {
 
109
        bset[i] = true;
 
110
        bvect[i] = true;
 
111
    } // for i
 
112
}
 
113
 
 
114
 
 
115
//
 
116
// Interval filling.
 
117
// 111........111111........111111..........11111111.......1111111...
 
118
//
 
119
 
 
120
void FillSetsIntervals(test_bitset& bset, 
 
121
                       bvect& bvect,
 
122
                       unsigned min, 
 
123
                       unsigned max,
 
124
                       unsigned fill_factor,
 
125
                       bool set_flag=true)
 
126
{
 
127
    while(fill_factor==0)
 
128
    {
 
129
        fill_factor=rand()%10;
 
130
    }
 
131
 
 
132
    unsigned i, j;
 
133
    unsigned factor = 10 * fill_factor;
 
134
    for (i = min; i < max; ++i)
 
135
    {
 
136
        unsigned len, end; 
 
137
 
 
138
        do
 
139
        {
 
140
            len = rand() % factor;
 
141
            end = i+len;
 
142
            
 
143
        } while (end >= max);
 
144
        for (j = i; j < end; ++j)
 
145
        {
 
146
            if (set_flag)
 
147
            {
 
148
                bset[j] = true;
 
149
                bvect[j]= true;
 
150
            }
 
151
            else
 
152
            {
 
153
                bset[j] = false;
 
154
                bvect[j] = false;
 
155
            }
 
156
                           
 
157
        } // j
 
158
 
 
159
        i = end;
 
160
 
 
161
 
 
162
        len = rand() % 10;
 
163
 
 
164
        i+=len;
 
165
 
 
166
        {
 
167
            for(unsigned k=0; k < 1000 && i < max; k+=3,i+=3)
 
168
            {
 
169
                if (set_flag)
 
170
                {
 
171
                    bset[i] = true;
 
172
                    bvect[i] = true;            
 
173
                }
 
174
                else
 
175
                {
 
176
                    bset[j] = false;
 
177
                    bvect[j] = false;
 
178
                }
 
179
 
 
180
            }
 
181
        }
 
182
 
 
183
    } // for i
 
184
 
 
185
}
 
186
 
 
187
 
 
188
void MemCpyTest()
 
189
{
 
190
    unsigned* m1 = new unsigned[BSIZE/32];
 
191
    unsigned* m2 = new unsigned[BSIZE/32];
 
192
    
 
193
    unsigned int i,j;
 
194
 
 
195
    if (!platform_test)
 
196
    {
 
197
    TimeTaker tt("Memory ADD transfer test", REPEATS * 4);
 
198
    for (i = 0; i < REPEATS*4; ++i)
 
199
    {
 
200
        for (j = 0; j < BSIZE/32; j+=4)
 
201
        {
 
202
            m1[j+0] += m2[j+0];
 
203
            m1[j+1] += m2[j+1];
 
204
            m1[j+2] += m2[j+2];
 
205
            m1[j+3] += m2[j+3];
 
206
        }
 
207
    }
 
208
    }
 
209
    
 
210
    if (!platform_test)
 
211
    {
 
212
    TimeTaker tt("memcpy transfer test", REPEATS * 4);
 
213
    for (i = 0; i < REPEATS*4; ++i)
 
214
    {
 
215
        memcpy(m1, m2, BSIZE/32 * sizeof(unsigned));
 
216
    }
 
217
    }
 
218
    
 
219
    delete [] m1;
 
220
    delete [] m2;
 
221
}
 
222
 
 
223
 
 
224
void BitCountTest()
 
225
{
 
226
    {
 
227
    bvect*  bv = new bvect();
 
228
    test_bitset*  bset = new test_bitset();
 
229
    unsigned value = 0;
 
230
 
 
231
    FillSetsIntervals(*bset, *bv, 0, BSIZE, 10);
 
232
 
 
233
    if (!platform_test)
 
234
    {
 
235
    TimeTaker tt("BitCount. Random bitvector", REPEATS*2);
 
236
    for (unsigned i = 0; i < REPEATS*2; ++i)
 
237
    {    
 
238
        value+=bv->count();
 
239
    }
 
240
    }
 
241
 
 
242
    volatile unsigned* p = &value;
 
243
    unsigned c1 = *p;
 
244
    c1 = value = 0;
 
245
 
 
246
    if (!platform_test)
 
247
    {
 
248
    TimeTaker tt("BitCount. Random bitvector (STL)", REPEATS*2);
 
249
    for (unsigned i = 0; i < REPEATS*2; ++i)
 
250
    {    
 
251
        value += bset->count();
 
252
    }
 
253
    }
 
254
 
 
255
    c1 = *p;
 
256
    c1 = value = 0;
 
257
 
 
258
    delete bset;
 
259
    delete bv;
 
260
 
 
261
    }
 
262
}
 
263
 
 
264
 
 
265
void BitForEachTest()
 
266
{
 
267
    // setup the test data
 
268
    //
 
269
    unsigned* test_arr = new unsigned[65536];
 
270
        for (unsigned j = 0; j < 65536; ++j)
 
271
        {
 
272
        test_arr[j] = j;                
 
273
        }
 
274
 
 
275
    if (!platform_test)
 
276
    {
 
277
        unsigned bit_list[32];
 
278
    TimeTaker tt("BitList algorithm. Conventional (AND based check)", REPEATS*10);
 
279
    
 
280
 
 
281
        for (unsigned i = 0; i < REPEATS*10; ++i)
 
282
    {    
 
283
                for (unsigned j = 0; j < 65536; ++j)
 
284
                {
 
285
                        bm::bit_list(i*test_arr[j], bit_list);
 
286
                }
 
287
        }
 
288
        }
 
289
        
 
290
    {
 
291
        unsigned bit_list[32];
 
292
    TimeTaker tt("BitList4 algorithm(sub-octet+switch)", REPEATS*10);
 
293
 
 
294
        for (unsigned i = 0; i < REPEATS*10; ++i)
 
295
    {    
 
296
                for (unsigned j = 0; j < 65536; ++j)
 
297
                {
 
298
                        bm::bit_list_4(i*test_arr[j], bit_list);
 
299
                }
 
300
        }
 
301
        }
 
302
        
 
303
        delete test_arr;
 
304
}
 
305
 
 
306
 
 
307
void BitCountSparseTest()
 
308
{
 
309
    {
 
310
    bvect*  bv = new bvect();
 
311
    test_bitset*  bset = new test_bitset();
 
312
    unsigned value = 0, c1;
 
313
    volatile unsigned* p = &value;
 
314
 
 
315
    SimpleFillSets(*bset, *bv, 0, BSIZE, 2500);
 
316
 
 
317
    {
 
318
    TimeTaker tt("BitCount: Sparse bitset ", REPEATS*10);
 
319
    for (unsigned i = 0; i < REPEATS*10; ++i)
 
320
    {    
 
321
        value += bv->count();
 
322
    }
 
323
    }
 
324
 
 
325
    if (!platform_test)
 
326
    {
 
327
    TimeTaker tt("BitCount: Sparse bitset (STL)", REPEATS*10);
 
328
    for (unsigned int i = 0; i < REPEATS*10; ++i)
 
329
    {    
 
330
        value += bset->count();
 
331
    }
 
332
    }
 
333
 
 
334
    c1 = *p;
 
335
    value = c1 = 0;
 
336
    
 
337
 
 
338
    bv->optimize();
 
339
 
 
340
    {
 
341
    TimeTaker tt("BitCount: GAP Sparse bitset", REPEATS*1000);
 
342
    for (unsigned i = 0; i < REPEATS*1000; ++i)
 
343
    {    
 
344
        value += bv->count();
 
345
    }
 
346
    delete bv;
 
347
    delete bset;
 
348
    }
 
349
    c1 = *p;
 
350
    value = c1 = 0;
 
351
 
 
352
    }
 
353
 
 
354
}
 
355
 
 
356
 
 
357
 
 
358
void BitCompareTest()
 
359
{
 
360
    {
 
361
    bvect*  bv1 = new bvect();
 
362
    bvect*  bv2 = new bvect();
 
363
    test_bitset*  bset = new test_bitset();
 
364
    int value = 0;
 
365
 
 
366
    SimpleFillSets(*bset, *bv1, 0, BSIZE, 10);
 
367
    SimpleFillSets(*bset, *bv2, 0, BSIZE, 10);
 
368
 
 
369
    {
 
370
    TimeTaker tt("BitCompare: Random bitvector", REPEATS*10);
 
371
    for (unsigned int i = 0; i < REPEATS*10; ++i)
 
372
    {    
 
373
        value+=bv1->compare(*bv2);
 
374
    }
 
375
    }
 
376
 
 
377
    delete bset;
 
378
    delete bv1;
 
379
    delete bv2;
 
380
 
 
381
    }
 
382
 
 
383
    if (platform_test) return;
 
384
 
 
385
    unsigned cnt = REPEATS * 100000;
 
386
    unsigned* arr1 = new unsigned[cnt];
 
387
    unsigned* arr2 = new unsigned[cnt];
 
388
 
 
389
    unsigned i;
 
390
    for (i = 0; i < cnt; ++i)
 
391
    {
 
392
        if ((rand() % 10) == 0)
 
393
        {
 
394
            arr1[i] = 0;
 
395
        }
 
396
        else 
 
397
        {
 
398
            arr1[i] = rand();
 
399
            arr2[i] = rand();   
 
400
        }
 
401
    }
 
402
 
 
403
    {
 
404
    TimeTaker tt("wordcmp complex: Random words comparison", cnt);
 
405
 
 
406
    for (i = 0; i < cnt; ++i)
 
407
    {    
 
408
        int res2 = bm::wordcmp(arr1[i], arr2[i]);
 
409
        int res = bm::wordcmp0(arr1[i], arr2[i]);
 
410
 
 
411
        if (res != res2)
 
412
        {
 
413
            cerr << "Incorrect result ! " << arr1[i] 
 
414
                 << "<=>" << arr2[i] << " res=" << res <<
 
415
                 endl;
 
416
            exit(1);
 
417
        }
 
418
    }
 
419
    }
 
420
 
 
421
    int c = 0;
 
422
    volatile void* p = &c;
 
423
 
 
424
    {
 
425
    TimeTaker tt("wordcmp0. Random words comparison", cnt);
 
426
    for (i = 0; i < cnt; ++i)
 
427
    {    
 
428
        c += bm::wordcmp0(arr1[i], arr2[i]);
 
429
    }
 
430
    }
 
431
 
 
432
 
 
433
    {
 
434
    TimeTaker tt("wordcmp. Random words comparison", cnt);
 
435
    for (i = 0; i < cnt; ++i)
 
436
    {    
 
437
        c += bm::wordcmp(arr1[i], arr2[i]);
 
438
    }
 
439
    }
 
440
 
 
441
    c = 0;;
 
442
 
 
443
    delete [] arr1;
 
444
    delete [] arr2;
 
445
 
 
446
    char buf[256];
 
447
    sprintf(buf, "%p", p);
 
448
}
 
449
 
 
450
void EnumeratorTest()
 
451
{
 
452
    bvect  bv;
 
453
    test_bitset*  bset = new test_bitset();
 
454
    unsigned value = 0;
 
455
 
 
456
    FillSetsIntervals(*bset, bv, 0, BSIZE, 10);
 
457
 
 
458
    unsigned cnt1 = bv.count();
 
459
    //unsigned cnt2 = bset->count();
 
460
 
 
461
    
 
462
    unsigned i;
 
463
 
 
464
    {
 
465
    TimeTaker tt("bvector<>::enumerator", REPEATS/10);
 
466
    for (i = 0; i < REPEATS/10; ++i)
 
467
    {    
 
468
        bvect::enumerator en = bv.first();
 
469
 
 
470
        for (;en.valid();++en)
 
471
        {
 
472
            value = *en;
 
473
        }
 
474
    }
 
475
    }
 
476
 
 
477
 
 
478
    // -----------------------------------------------
 
479
 
 
480
    unsigned cnt = 0;
 
481
    {
 
482
        TimeTaker tt("bvector<>::get_next()", REPEATS/10);
 
483
        for (i = 0; i < REPEATS/10; ++i)
 
484
        {
 
485
            if (bv.any())
 
486
            {
 
487
                unsigned value = bv.get_first();
 
488
                do
 
489
                {
 
490
                    value = bv.get_next(value);
 
491
                    cnt += value;
 
492
                } while ( value );
 
493
            }
 
494
        }
 
495
    }
 
496
 
 
497
    delete bset;
 
498
//    delete bv;
 
499
 
 
500
    char buf[256];
 
501
    sprintf(buf, "%i %i ", cnt, cnt1);//, cnt2);
 
502
 
 
503
}
 
504
 
 
505
 
 
506
void EnumeratorTestGAP()
 
507
{
 
508
    bvect*  bv = new bvect();
 
509
    test_bitset*  bset = new test_bitset();
 
510
    unsigned i;
 
511
    unsigned value = 0;
 
512
 
 
513
    SimpleFillSets(*bset, *bv, 0, BSIZE, 2500);
 
514
    bv->count();
 
515
 
 
516
    for (int k = 0; k < 2; ++k)
 
517
    {
 
518
 
 
519
    {
 
520
    TimeTaker tt("Sparse bvector (enumerator)", REPEATS*10*(k+1));
 
521
    for (i = 0; i < REPEATS*10*(k+1); ++i)
 
522
    {    
 
523
        bvect::enumerator en = bv->first();
 
524
        bvect::enumerator bend = bv->end();
 
525
 
 
526
        while (en < bend)
 
527
        {
 
528
            value = *en;
 
529
            ++en;
 
530
        }
 
531
    }
 
532
 
 
533
    }
 
534
 
 
535
    // -----------------------------------------------
 
536
 
 
537
    unsigned cnt = 0;
 
538
    {
 
539
    TimeTaker tt("Sparse bvector (get_next())", REPEATS*10*(k+1));
 
540
 
 
541
    for (i = 0; i < REPEATS*10*(k+1); ++i)
 
542
    {
 
543
        if (bv->any())
 
544
        {
 
545
            unsigned value = bv->get_first();
 
546
            do
 
547
            {
 
548
                value = bv->get_next(value);
 
549
                cnt += value;
 
550
            } while ( value );
 
551
        }
 
552
    }
 
553
    }
 
554
    char buf[256];
 
555
    sprintf(buf, "%i", cnt); // to fool some smart compilers like ICC
 
556
 
 
557
    {
 
558
 
 
559
    bv->optimize();
 
560
    }
 
561
 
 
562
    if (!platform_test) 
 
563
    {
 
564
        cout << "Testing optimized vectors." << endl;
 
565
    }
 
566
    }
 
567
 
 
568
    delete bv;
 
569
    delete bset;
 
570
    // -----------------------------------------------
 
571
 
 
572
}
 
573
 
 
574
void SerializationTest()
 
575
{
 
576
        bvect bv_sparse;
 
577
 
 
578
        // prepare a test bitset with a small number of bits set somewhere
 
579
        // far from the beginning
 
580
        for (unsigned i = 0; i < 5; ++i)
 
581
        {
 
582
                bv_sparse[BSIZE/2 + i * 3] = true;              
 
583
        }
 
584
        bv_sparse[100] = true;
 
585
        bv_sparse[70000] = true;
 
586
        bv_sparse[200000] = true;
 
587
 
 
588
        bv_sparse.optimize();
 
589
 
 
590
        unsigned cnt = bv_sparse.count();
 
591
    bvect::statistics st;
 
592
    bv_sparse.calc_stat(&st);
 
593
    unsigned char*  buf = new unsigned char[st.max_serialize_mem];
 
594
 
 
595
    unsigned len, id_size;
 
596
    len = id_size = 0;
 
597
    {
 
598
        TimeTaker tt("Small bvector serialization", REPEATS*70000);
 
599
        for (unsigned i = 0; i < REPEATS*70000; ++i)
 
600
        {
 
601
                len += bm::serialize(bv_sparse, buf, bm::BM_NO_BYTE_ORDER|bm::BM_NO_GAP_LENGTH);
 
602
                id_size += cnt * sizeof(unsigned);
 
603
        }
 
604
        }
 
605
        
 
606
        delete [] buf; buf = 0;
 
607
                
 
608
    bvect*  bv = new bvect();
 
609
    test_bitset*  bset = new test_bitset();
 
610
    unsigned value = 0;
 
611
 
 
612
    SimpleFillSets(*bset, *bv, 0, BSIZE, 4);
 
613
    
 
614
        cnt = bv->count();
 
615
    bv->calc_stat(&st);
 
616
    buf = new unsigned char[st.max_serialize_mem];
 
617
    
 
618
    {
 
619
        TimeTaker tt("Large bvector serialization", REPEATS*4);
 
620
        for (unsigned i = 0; i < REPEATS*4; ++i)
 
621
        {
 
622
                len += bm::serialize(*bv, buf, bm::BM_NO_BYTE_ORDER|bm::BM_NO_GAP_LENGTH);
 
623
                id_size += cnt * sizeof(unsigned);              
 
624
        }
 
625
        }
 
626
    
 
627
        char cbuf[256];
 
628
        sprintf(cbuf, "%i %i %i", id_size, len, value);
 
629
    
 
630
    
 
631
    delete bv;
 
632
    delete bset;        
 
633
    delete [] buf;
 
634
}
 
635
 
 
636
void InvertTest()
 
637
{
 
638
    bvect*  bv = new bvect();
 
639
    test_bitset*  bset = new test_bitset();
 
640
    unsigned i;
 
641
    //unsigned value = 0;
 
642
 
 
643
    SimpleFillSets(*bset, *bv, 0, BSIZE, 2500);
 
644
    {
 
645
    TimeTaker tt("Invert bvector", REPEATS*4);
 
646
    for (i = 0; i < REPEATS*4; ++i)
 
647
    {
 
648
        bv->flip();    
 
649
    }
 
650
    }
 
651
 
 
652
    if (!platform_test)
 
653
    {
 
654
    TimeTaker tt("Invert bvector (STL)", REPEATS*4);
 
655
    for (i = 0; i < REPEATS*4; ++i)
 
656
    {
 
657
        bset->flip();    
 
658
    }
 
659
    }
 
660
 
 
661
    delete bv;
 
662
    delete bset;
 
663
}
 
664
 
 
665
 
 
666
void AndTest()
 
667
{
 
668
    bvect*  bv1 = new bvect();
 
669
    test_bitset*  bset1 = new test_bitset();
 
670
    test_bitset*  bset2 = new test_bitset();
 
671
    bvect*  bv2 = new bvect();
 
672
    unsigned i;
 
673
    //unsigned value = 0;
 
674
 
 
675
    SimpleFillSets(*bset1, *bv1, 0, BSIZE, 100);
 
676
    SimpleFillSets(*bset1, *bv2, 0, BSIZE, 100);
 
677
    {
 
678
    TimeTaker tt("AND bvector test", REPEATS*4);
 
679
    for (i = 0; i < REPEATS*4; ++i)
 
680
    {
 
681
        *bv1 &= *bv2;
 
682
    }
 
683
    }
 
684
 
 
685
    if (!platform_test)
 
686
    {
 
687
    TimeTaker tt("AND bvector test(STL)", REPEATS*4);
 
688
    for (i = 0; i < REPEATS*4; ++i)
 
689
    {
 
690
        *bset1 &= *bset2;
 
691
    }
 
692
    }
 
693
 
 
694
    delete bv1;
 
695
    delete bv2;
 
696
 
 
697
    delete bset1;
 
698
    delete bset2;
 
699
}
 
700
 
 
701
 
 
702
void SubTest()
 
703
{
 
704
    bvect*  bv1 = new bvect();
 
705
    test_bitset*  bset1 = new test_bitset();
 
706
    bvect*  bv2 = new bvect();
 
707
    unsigned i;
 
708
 
 
709
    SimpleFillSets(*bset1, *bv1, 0, BSIZE, 100);
 
710
    SimpleFillSets(*bset1, *bv2, 0, BSIZE, 100);
 
711
    delete bset1;
 
712
 
 
713
    {
 
714
    TimeTaker tt("SUB bvector test", REPEATS*4);
 
715
    for (i = 0; i < REPEATS*4; ++i)
 
716
    {
 
717
        *bv1 -= *bv2;
 
718
    }
 
719
    }
 
720
        
 
721
    delete bv1;
 
722
    delete bv2;
 
723
}
 
724
 
 
725
 
 
726
void XorCountTest()
 
727
{
 
728
    bvect*  bv1 = new bvect();
 
729
    bvect*  bv2 = new bvect();
 
730
    test_bitset*  bset1 = new test_bitset();
 
731
    test_bitset*  bset2 = new test_bitset();
 
732
    unsigned i;
 
733
 
 
734
    SimpleFillSets(*bset1, *bv1, 0, BSIZE, 400);
 
735
    SimpleFillSets(*bset2, *bv2, 0, BSIZE, 500);
 
736
 
 
737
    unsigned count1 = 0;
 
738
    unsigned count2 = 0;
 
739
    unsigned test_count = 0;
 
740
 
 
741
    if (!platform_test)
 
742
    {
 
743
    bvect bv_tmp;
 
744
    TimeTaker tt("XOR COUNT bvector test with TEMP vector", REPEATS*4);
 
745
    for (i = 0; i < REPEATS*4; ++i)
 
746
    {
 
747
        bv_tmp.clear(false);
 
748
        bv_tmp |= *bv1;
 
749
        bv_tmp ^= *bv2;
 
750
        count1 += bv_tmp.count();
 
751
    }
 
752
    }
 
753
 
 
754
    if (!platform_test)
 
755
    {
 
756
    test_bitset*  bset_tmp = new test_bitset();
 
757
    TimeTaker tt("XOR COUNT bvector test with TEMP vector (STL)", REPEATS*4);
 
758
    for (i = 0; i < REPEATS*4; ++i)
 
759
    {
 
760
        bset_tmp->reset();
 
761
        *bset_tmp |= *bset1;
 
762
        *bset_tmp ^= *bset2;
 
763
        test_count += bset_tmp->count();
 
764
    }
 
765
    }
 
766
 
 
767
 
 
768
    {
 
769
    TimeTaker tt("XOR COUNT bvector test", REPEATS*4);
 
770
    for (i = 0; i < REPEATS*4; ++i)
 
771
    {
 
772
        count2 += bm::count_xor(*bv1, *bv2);
 
773
    }
 
774
    }
 
775
 
 
776
    
 
777
    if (!platform_test)    
 
778
        if (count1 != count2)
 
779
        {
 
780
            cout << "Check failed !" << endl;
 
781
            cout << count1 << " " << count2 << " " << test_count << endl;
 
782
            exit(1);
 
783
        }
 
784
    count1 = count2 = 0;
 
785
    
 
786
    // -----------------------------------------
 
787
    if (!platform_test)
 
788
    {
 
789
        cout << "One optimized vector" << endl;
 
790
    }
 
791
    bv2->optimize();
 
792
 
 
793
    if (!platform_test)
 
794
    {
 
795
    bvect bv_tmp;
 
796
    TimeTaker tt("XOR COUNT bvector test with TEMP vector", REPEATS*4);
 
797
    for (i = 0; i < REPEATS*4; ++i)
 
798
    {
 
799
        bv_tmp.clear(false);
 
800
        bv_tmp |= *bv1;
 
801
        bv_tmp ^= *bv2;
 
802
        count1 += bv_tmp.count();
 
803
    }
 
804
    }
 
805
 
 
806
    {
 
807
    TimeTaker tt("XOR COUNT bvector test", REPEATS*4);
 
808
    for (i = 0; i < REPEATS*4; ++i)
 
809
    {
 
810
        count2 += bm::count_xor(*bv1, *bv2);
 
811
    }
 
812
    }
 
813
 
 
814
    if (!platform_test)
 
815
        if (count1 != count2)
 
816
        {
 
817
            cout << "Check failed !" << endl;
 
818
            exit(1);
 
819
        }
 
820
    count1 = count2 = 0;
 
821
 
 
822
    // -----------------------------------------
 
823
    if (!platform_test)
 
824
    {
 
825
        cout << "Both vectors optimized" << endl;
 
826
    }
 
827
    bv1->optimize();
 
828
    //bv1->stat();
 
829
    if (!platform_test)
 
830
    {
 
831
    bvect bv_tmp;
 
832
    TimeTaker tt("XOR COUNT bvector test with TEMP vector", REPEATS*4);
 
833
    for (i = 0; i < REPEATS*4; ++i)
 
834
    {
 
835
        bv_tmp.clear(false);
 
836
        bv_tmp |= *bv1;
 
837
        bv_tmp ^= *bv2;
 
838
        count1 += bv_tmp.count();
 
839
    }
 
840
    }
 
841
 
 
842
    {
 
843
    TimeTaker tt("XOR COUNT bvector test", REPEATS*4);
 
844
    for (i = 0; i < REPEATS*4; ++i)
 
845
    {
 
846
        count2 += bm::count_xor(*bv1, *bv2);
 
847
    }
 
848
    }
 
849
    if (!platform_test)
 
850
        if (count1 != count2)
 
851
        {
 
852
            cout << "Check failed !" << endl;
 
853
            exit(1);
 
854
        }
 
855
    count1 = count2 = 0;
 
856
 
 
857
 
 
858
    delete bv1;
 
859
    delete bv2;
 
860
    
 
861
    delete bset1;
 
862
    delete bset2;    
 
863
}
 
864
 
 
865
 
 
866
void TI_MetricTest()
 
867
{
 
868
    bvect*  bv1 = new bvect();
 
869
    bvect*  bv2 = new bvect();
 
870
    test_bitset*  bset1 = new test_bitset();
 
871
    test_bitset*  bset2 = new test_bitset();
 
872
    unsigned i;
 
873
 
 
874
    SimpleFillSets(*bset1, *bv1, 0, BSIZE, 500);
 
875
    SimpleFillSets(*bset2, *bv2, 0, BSIZE, 250);
 
876
 
 
877
    unsigned count1 = 0;
 
878
    unsigned count2 = 0;
 
879
    unsigned countA=0, countB=0, test_countA=0, test_countB=0;
 
880
    unsigned test_count = 0;
 
881
    double ti1=0, ti2=0;
 
882
 
 
883
    {
 
884
    TimeTaker tt("Tversky Index bvector test vector", REPEATS);
 
885
    for (i = 0; i < REPEATS; ++i)
 
886
    {
 
887
        count1 = bm::count_and(*bv1, *bv2);
 
888
        
 
889
        countA = bm::count_sub(*bv1, *bv2);
 
890
        countB = bm::count_sub(*bv2, *bv1);
 
891
        
 
892
        ti1 = double(count1) / double(0.4*countA + 0.5*countB + count1);
 
893
    }
 
894
    }
 
895
 
 
896
 
 
897
    if (!platform_test)
 
898
    {
 
899
    test_bitset*  bset_tmp = new test_bitset();
 
900
    double test_dice = 0;
 
901
    TimeTaker tt("Dice bvector test with TEMP vector(STL)", REPEATS);
 
902
    for (i = 0; i < REPEATS; ++i)
 
903
    {
 
904
        bset_tmp->reset();
 
905
        *bset_tmp |= *bset1;
 
906
        *bset_tmp &= *bset2;
 
907
        test_count += bset_tmp->count();
 
908
        
 
909
        test_countA += bset1->count();
 
910
        test_countB += bset2->count();
 
911
        
 
912
        test_countA += bset1->count();
 
913
        test_countB += bset2->count();
 
914
        
 
915
        test_dice += double(2*test_count) / double(test_countA + test_countB);
 
916
    }
 
917
    }
 
918
 
 
919
 
 
920
    {
 
921
    bm::distance_metric_descriptor dmd[3];
 
922
    dmd[0].metric = bm::COUNT_AND;
 
923
    dmd[1].metric = bm::COUNT_SUB_AB;
 
924
    dmd[2].metric = bm::COUNT_SUB_BA;    
 
925
    
 
926
    TimeTaker tt("Tversky Index bvector test (pipeline)", REPEATS);
 
927
    for (i = 0; i < REPEATS; ++i)
 
928
    {
 
929
        bm::distance_operation(*bv1, *bv2, &dmd[0], (&dmd[0])+3);
 
930
                
 
931
        ti2 = double(dmd[0].result) / double(0.4*dmd[1].result + 0.5*dmd[2].result + dmd[0].result);
 
932
        
 
933
        dmd[0].result = dmd[1].result = dmd[2].result = 0;
 
934
    }
 
935
    }
 
936
 
 
937
    
 
938
    if (fabs(ti2 - ti1) > 0.1)
 
939
    {
 
940
        cout << "Check failed ! error=" << fabs(ti2 - ti1) << endl;
 
941
        cout << ti1 << " " << ti2 << endl;
 
942
        exit(1);
 
943
    }
 
944
    count1 = count2 = 0;
 
945
 
 
946
    // -----------------------------------------
 
947
    if (!platform_test)
 
948
    {
 
949
        cout << "One optimized vector" << endl;
 
950
    }
 
951
    bv2->optimize();
 
952
    bv1->count(); // trying to fool the CPU cache
 
953
 
 
954
    
 
955
    {
 
956
    TimeTaker tt("Dice metric bvector test", REPEATS);
 
957
    for (i = 0; i < REPEATS; ++i)
 
958
    {
 
959
        count1 = bm::count_and(*bv1, *bv2);
 
960
        
 
961
        countA = bm::count_sub(*bv1, *bv2);
 
962
        countB = bm::count_sub(*bv2, *bv1);
 
963
        
 
964
        ti1 = double(count1) / double(0.4*countA + 0.5*countB + count1);
 
965
    }
 
966
    }
 
967
 
 
968
 
 
969
 
 
970
    {
 
971
    bm::distance_metric_descriptor dmd[3];
 
972
    dmd[0].metric = bm::COUNT_AND;
 
973
    dmd[1].metric = bm::COUNT_SUB_AB;
 
974
    dmd[2].metric = bm::COUNT_SUB_BA;    
 
975
    
 
976
    TimeTaker tt("Tversky Index bvector test(pipeline)", REPEATS);
 
977
    for (i = 0; i < REPEATS; ++i)
 
978
    {
 
979
        bm::distance_operation(*bv1, *bv2, &dmd[0], (&dmd[0])+3);
 
980
                
 
981
        ti2 = double(dmd[0].result) / double(0.4*dmd[1].result + 0.5*dmd[2].result + dmd[0].result);
 
982
        
 
983
        dmd[0].result = dmd[1].result = dmd[2].result = 0;
 
984
    }
 
985
    }
 
986
 
 
987
 
 
988
    if (fabs(ti2 - ti1) > 0.1)
 
989
    {
 
990
        cout << "Check failed !" << endl;
 
991
        cout << ti1 << " " << ti2 << endl;
 
992
        exit(1);
 
993
    }
 
994
    count1 = count2 = 0;
 
995
    count1 = count2 = 0;
 
996
 
 
997
    // -----------------------------------------
 
998
    if (!platform_test)
 
999
    {
 
1000
        cout << "Both vectors optimized" << endl;
 
1001
    }
 
1002
    bv1->optimize();
 
1003
 
 
1004
    {
 
1005
    TimeTaker tt("Tversky index bvector test", REPEATS);
 
1006
    for (i = 0; i < REPEATS; ++i)
 
1007
    {
 
1008
        count1 = bm::count_and(*bv1, *bv2);
 
1009
        
 
1010
        countA = bm::count_sub(*bv1, *bv2);
 
1011
        countB = bm::count_sub(*bv2, *bv1);
 
1012
        
 
1013
        ti1 = double(count1) / double(0.4*countA + 0.5*countB + count1);
 
1014
    }
 
1015
    }
 
1016
 
 
1017
    {
 
1018
    bm::distance_metric_descriptor dmd[3];
 
1019
    dmd[0].metric = bm::COUNT_AND;
 
1020
    dmd[1].metric = bm::COUNT_SUB_AB;
 
1021
    dmd[2].metric = bm::COUNT_SUB_BA;    
 
1022
    
 
1023
    TimeTaker tt("Tversky Index bvector test (pipeline)", REPEATS);
 
1024
    for (i = 0; i < REPEATS; ++i)
 
1025
    {
 
1026
        bm::distance_operation(*bv1, *bv2, &dmd[0], (&dmd[0])+3);
 
1027
                
 
1028
        ti2 = double(dmd[0].result) / double(0.4*dmd[1].result + 0.5*dmd[2].result + dmd[0].result);
 
1029
        
 
1030
        dmd[0].result = dmd[1].result = dmd[2].result = 0;
 
1031
    }
 
1032
    }
 
1033
 
 
1034
    if (fabs(ti2 - ti1) > 0.1)
 
1035
    {
 
1036
        cout << "Check failed !" << endl;
 
1037
        cout << ti1 << " " << ti2 << endl;
 
1038
        exit(1);
 
1039
    }
 
1040
 
 
1041
 
 
1042
    delete bv1;
 
1043
    delete bv2;
 
1044
    
 
1045
    delete bset1;
 
1046
    delete bset2;    
 
1047
}
 
1048
 
 
1049
#ifdef BMSSE2OPT
 
1050
# if(_MSC_VER)
 
1051
#  define BM_ALIGN16 __declspec(align(16))
 
1052
#  define BM_ALIGN16ATTR
 
1053
 
 
1054
# else // GCC
 
1055
 
 
1056
#  define BM_ALIGN16
 
1057
#  define BM_ALIGN16ATTR __attribute__((aligned(16)))
 
1058
# endif
 
1059
 
 
1060
#else
 
1061
 
 
1062
#  define BM_ALIGN16
 
1063
#  define BM_ALIGN16ATTR
 
1064
 
 
1065
#endif 
 
1066
 
 
1067
void BitBlockTransposeTest()
 
1068
{
 
1069
    bm::word_t BM_ALIGN16 block1[bm::set_block_size] BM_ALIGN16ATTR = {0,};
 
1070
    //bm::word_t BM_ALIGN16 block2[bm::set_block_size] = {0xFF,};
 
1071
    unsigned   BM_ALIGN16 tmatrix1[32][bm::set_block_plain_size] BM_ALIGN16ATTR;
 
1072
 
 
1073
    for (unsigned i = 0; i < bm::set_block_size; ++i)
 
1074
    {
 
1075
        block1[i] = 1 | (1 << 5) | (7 << 15) | (3 << 22);
 
1076
    }
 
1077
 
 
1078
    const unsigned blocks_count = 70000;
 
1079
    bm::word_t* blocks[blocks_count];
 
1080
    for (unsigned k = 0; k < blocks_count; ++k)
 
1081
    {
 
1082
        blocks[k] = bm::block_allocator::allocate(bm::set_block_size, 0);
 
1083
        for (unsigned i = 0; i < bm::set_block_size; ++i)
 
1084
        {
 
1085
            blocks[k][i] = 1 | (1 << 5) | (7 << 15) | (3 << 22);
 
1086
        }
 
1087
    }
 
1088
 
 
1089
    unsigned cnt=0;
 
1090
/*
 
1091
    {
 
1092
    TimeTaker tt("Bit-block transpose.", REPEATS*1000);
 
1093
    for (unsigned i = 0; i < REPEATS*1000; ++i)
 
1094
    {
 
1095
        bm::bit_block_transpose(block1, tmatrix1);
 
1096
    }
 
1097
    }
 
1098
 
 
1099
    {
 
1100
    TimeTaker tt("Bit-block trestore.", REPEATS*1000);
 
1101
    for (unsigned i = 0; i < REPEATS*1000; ++i)
 
1102
    {
 
1103
        bm::bit_block_trestore(tmatrix1, block2);
 
1104
        cnt += block2[10];
 
1105
 
 
1106
    }
 
1107
    }
 
1108
 
 
1109
    {
 
1110
    TimeTaker tt("Bit-block transpose distance.", REPEATS*1000);
 
1111
    unsigned distance[bm::set_block_plain_cnt][bm::set_block_plain_cnt];
 
1112
    for (unsigned i = 0; i < REPEATS*1000; ++i)
 
1113
    {
 
1114
        bm::bit_block_tmatrix_distance(tmatrix1, distance);
 
1115
        cnt += distance[1][1];
 
1116
    }
 
1117
    }
 
1118
    printf("", cnt);
 
1119
*/
 
1120
 
 
1121
    unsigned d2[bm::set_block_plain_cnt][bm::set_block_plain_cnt];
 
1122
    {
 
1123
    TimeTaker tt("Bit-block transpose+distance", 100000);
 
1124
    unsigned distance[bm::set_block_plain_cnt][bm::set_block_plain_cnt];
 
1125
    unsigned idx = 0;
 
1126
    for (unsigned i = 0; i < 100000; ++i)
 
1127
    {
 
1128
        bm::vect_bit_transpose<unsigned, 
 
1129
                               bm::set_block_plain_cnt, 
 
1130
                               bm::set_block_plain_size>
 
1131
                               (blocks[idx], bm::set_block_size, tmatrix1);
 
1132
        bm::tmatrix_distance<unsigned, 
 
1133
                             bm::set_block_plain_cnt, 
 
1134
                             bm::set_block_plain_size>
 
1135
                             (tmatrix1, distance);
 
1136
    
 
1137
        cnt += distance[1][1];
 
1138
        ++idx;
 
1139
        if (idx >= blocks_count) idx = 0;
 
1140
        memcpy(d2, distance, sizeof(distance));
 
1141
    }
 
1142
 
 
1143
    }
 
1144
    
 
1145
    char cbuf[256];
 
1146
    sprintf(cbuf, "%i %i", cnt, d2[10][10]);
 
1147
 
 
1148
    for (unsigned i = 0; i < blocks_count; ++i)
 
1149
    {
 
1150
        bm::block_allocator::deallocate(blocks[i], 0);
 
1151
    }
 
1152
 
 
1153
}
 
1154
 
 
1155
void ptest()
 
1156
{
 
1157
    bvect*  bv_small = new bvect(bm::BM_GAP);
 
1158
    bvect*  bv_large = new bvect(bm::BM_GAP);
 
1159
 
 
1160
    test_bitset*  bset = new test_bitset();
 
1161
 
 
1162
    FillSetsIntervals(*bset, *bv_large, 0, 2000000000, 10);
 
1163
 
 
1164
    for (int i = 0; i < 2000; ++i)
 
1165
    {
 
1166
        bv_small->set(i*10000);
 
1167
    }
 
1168
 
 
1169
    {
 
1170
    TimeTaker tt("Operation &= test", REPEATS * 10);
 
1171
    unsigned count = 0;
 
1172
    for (unsigned i = 0; i < REPEATS*10; ++i)
 
1173
    {
 
1174
        bvect t1(bm::BM_GAP);
 
1175
        t1 = *bv_small;
 
1176
        t1 &= *bv_large;
 
1177
        count += t1.count();
 
1178
    }
 
1179
    }
 
1180
 
 
1181
 
 
1182
 
 
1183
    {
 
1184
    TimeTaker tt("Operation &= with enumerator test", REPEATS * 10);
 
1185
    unsigned count = 0;
 
1186
    for (unsigned i = 0; i < REPEATS*10; ++i)
 
1187
    {
 
1188
        bvect t1(bm::BM_GAP);
 
1189
        bvect t2(bm::BM_GAP);
 
1190
        t1 = *bv_small;
 
1191
        
 
1192
        for (bvect::enumerator it = t1.first(); it != t1.end(); ++it) {
 
1193
            if ((*bv_large)[*it]) {
 
1194
                t2.set_bit(*it);
 
1195
            }
 
1196
        }
 
1197
        count += t2.count();
 
1198
    }
 
1199
    }
 
1200
 
 
1201
 
 
1202
}
 
1203
 
 
1204
 
 
1205
int main(void)
 
1206
{
 
1207
//    ptest();
 
1208
 
 
1209
    TimeTaker tt("TOTAL", 1);
 
1210
 
 
1211
    MemCpyTest();
 
1212
 
 
1213
    BitCountTest();
 
1214
 
 
1215
    BitForEachTest();
 
1216
 
 
1217
    BitCountSparseTest();
 
1218
 
 
1219
    BitCompareTest();
 
1220
 
 
1221
    BitBlockTransposeTest();
 
1222
 
 
1223
    EnumeratorTest();
 
1224
    EnumeratorTestGAP();
 
1225
 
 
1226
    AndTest();
 
1227
    SubTest();  
 
1228
 
 
1229
    InvertTest();  
 
1230
 
 
1231
    XorCountTest();
 
1232
 
 
1233
    TI_MetricTest();
 
1234
 
 
1235
    SerializationTest();
 
1236
        
 
1237
    return 0;
 
1238
}
 
1239
 
 
1240
 
 
1241
#ifdef _MSC_VER
 
1242
#pragma warning( pop )
 
1243
#endif
 
1244
 
 
1245
 
 
1246