1/*
2 Copyright (c) 2005-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17#include "concurrent_vector_v2.h"
18#include <cstdio>
19#include <cstdlib>
20#include "../test/harness_assert.h"
21
22tbb::atomic<long> FooCount;
23
24//! Problem size
25const size_t N = 500000;
26
27struct Foo {
28 int my_bar;
29public:
30 enum State {
31 DefaultInitialized=0x1234,
32 CopyInitialized=0x89ab,
33 Destroyed=0x5678
34 } state;
35 int& bar() {
36 ASSERT( state==DefaultInitialized||state==CopyInitialized, NULL );
37 return my_bar;
38 }
39 int bar() const {
40 ASSERT( state==DefaultInitialized||state==CopyInitialized, NULL );
41 return my_bar;
42 }
43 static const int initial_value_of_bar = 42;
44 Foo() {
45 state = DefaultInitialized;
46 ++FooCount;
47 my_bar = initial_value_of_bar;
48 }
49 Foo( const Foo& foo ) {
50 state = CopyInitialized;
51 ++FooCount;
52 my_bar = foo.my_bar;
53 }
54 ~Foo() {
55 ASSERT( state==DefaultInitialized||state==CopyInitialized, NULL );
56 state = Destroyed;
57 my_bar = ~initial_value_of_bar;
58 --FooCount;
59 }
60 bool is_const() const {return true;}
61 bool is_const() {return false;}
62};
63
64class FooWithAssign: public Foo {
65public:
66 void operator=( const FooWithAssign& x ) {
67 ASSERT( x.state==DefaultInitialized||x.state==CopyInitialized, NULL );
68 ASSERT( state==DefaultInitialized||state==CopyInitialized, NULL );
69 my_bar = x.my_bar;
70 }
71};
72
73inline void NextSize( int& s ) {
74 if( s<=32 ) ++s;
75 else s += s/10;
76}
77
78static void CheckVector( const tbb::concurrent_vector<Foo>& cv, size_t expected_size, size_t old_size ) {
79 ASSERT( cv.size()==expected_size, NULL );
80 ASSERT( cv.empty()==(expected_size==0), NULL );
81 for( int j=0; j<int(expected_size); ++j ) {
82 if( cv[j].bar()!=~j )
83 std::printf("ERROR on line %d for old_size=%ld expected_size=%ld j=%d\n",__LINE__,long(old_size),long(expected_size),j);
84 }
85}
86
87void TestResizeAndCopy() {
88 typedef tbb::concurrent_vector<Foo> vector_t;
89 for( int old_size=0; old_size<=128; NextSize( old_size ) ) {
90 for( int new_size=old_size; new_size<=128; NextSize( new_size ) ) {
91 long count = FooCount;
92 vector_t v;
93 ASSERT( count==FooCount, NULL );
94 v.grow_by(old_size);
95 ASSERT( count+old_size==FooCount, NULL );
96 for( int j=0; j<old_size; ++j )
97 v[j].bar() = j*j;
98 v.grow_to_at_least(new_size);
99 ASSERT( count+new_size==FooCount, NULL );
100 for( int j=0; j<new_size; ++j ) {
101 int expected = j<old_size ? j*j : Foo::initial_value_of_bar;
102 if( v[j].bar()!=expected )
103 std::printf("ERROR on line %d for old_size=%ld new_size=%ld v[%ld].bar()=%d != %d\n",__LINE__,long(old_size),long(new_size),long(j),v[j].bar(), expected);
104 }
105 ASSERT( v.size()==size_t(new_size), NULL );
106 for( int j=0; j<new_size; ++j ) {
107 v[j].bar() = ~j;
108 }
109 const vector_t& cv = v;
110 // Try copy constructor
111 vector_t copy_of_v(cv);
112 CheckVector(cv,new_size,old_size);
113 v.clear();
114 ASSERT( v.empty(), NULL );
115 CheckVector(copy_of_v,new_size,old_size);
116 }
117 }
118}
119
120void TestCapacity() {
121 for( size_t old_size=0; old_size<=10000; old_size=(old_size<5 ? old_size+1 : 3*old_size) ) {
122 for( size_t new_size=0; new_size<=10000; new_size=(new_size<5 ? new_size+1 : 3*new_size) ) {
123 long count = FooCount;
124 {
125 typedef tbb::concurrent_vector<Foo> vector_t;
126 vector_t v;
127 v.reserve( old_size );
128 ASSERT( v.capacity()>=old_size, NULL );
129 v.reserve( new_size );
130 ASSERT( v.capacity()>=old_size, NULL );
131 ASSERT( v.capacity()>=new_size, NULL );
132 for( size_t i=0; i<2*new_size; ++i ) {
133 ASSERT( size_t(FooCount)==count+i, NULL );
134 size_t j = v.grow_by(1);
135 ASSERT( j==i, NULL );
136 }
137 }
138 ASSERT( FooCount==count, NULL );
139 }
140 }
141}
142
143struct AssignElement {
144 typedef tbb::concurrent_vector<int>::range_type::iterator iterator;
145 iterator base;
146 void operator()( const tbb::concurrent_vector<int>::range_type& range ) const {
147 for( iterator i=range.begin(); i!=range.end(); ++i ) {
148 if( *i!=0 )
149 std::printf("ERROR for v[%ld]\n", long(i-base));
150 *i = int(i-base);
151 }
152 }
153 AssignElement( iterator base_ ) : base(base_) {}
154};
155
156struct CheckElement {
157 typedef tbb::concurrent_vector<int>::const_range_type::iterator iterator;
158 iterator base;
159 void operator()( const tbb::concurrent_vector<int>::const_range_type& range ) const {
160 for( iterator i=range.begin(); i!=range.end(); ++i )
161 if( *i != int(i-base) )
162 std::printf("ERROR for v[%ld]\n", long(i-base));
163 }
164 CheckElement( iterator base_ ) : base(base_) {}
165};
166
167#include "tbb/tick_count.h"
168#include "tbb/parallel_for.h"
169#include "../test/harness.h"
170
171//! Test parallel access by iterators
172void TestParallelFor( int nthread ) {
173 typedef tbb::concurrent_vector<int> vector_t;
174 vector_t v;
175 v.grow_to_at_least(N);
176 tbb::tick_count t0 = tbb::tick_count::now();
177 if( Verbose )
178 std::printf("Calling parallel_for.h with %ld threads\n",long(nthread));
179 tbb::parallel_for( v.range(10000), AssignElement(v.begin()) );
180 tbb::tick_count t1 = tbb::tick_count::now();
181 const vector_t& u = v;
182 tbb::parallel_for( u.range(10000), CheckElement(u.begin()) );
183 tbb::tick_count t2 = tbb::tick_count::now();
184 if( Verbose )
185 std::printf("Time for parallel_for.h: assign time = %8.5f, check time = %8.5f\n",
186 (t1-t0).seconds(),(t2-t1).seconds());
187 for( long i=0; size_t(i)<v.size(); ++i )
188 if( v[i]!=i )
189 std::printf("ERROR for v[%ld]\n", i);
190}
191
192template<typename Iterator1, typename Iterator2>
193void TestIteratorAssignment( Iterator2 j ) {
194 Iterator1 i(j);
195 ASSERT( i==j, NULL );
196 ASSERT( !(i!=j), NULL );
197 Iterator1 k;
198 k = j;
199 ASSERT( k==j, NULL );
200 ASSERT( !(k!=j), NULL );
201}
202
203template<typename Iterator, typename T>
204void TestIteratorTraits() {
205 AssertSameType( static_cast<typename Iterator::difference_type*>(0), static_cast<ptrdiff_t*>(0) );
206 AssertSameType( static_cast<typename Iterator::value_type*>(0), static_cast<T*>(0) );
207 AssertSameType( static_cast<typename Iterator::pointer*>(0), static_cast<T**>(0) );
208 AssertSameType( static_cast<typename Iterator::iterator_category*>(0), static_cast<std::random_access_iterator_tag*>(0) );
209 T x;
210 typename Iterator::reference xr = x;
211 typename Iterator::pointer xp = &x;
212 ASSERT( &xr==xp, NULL );
213}
214
215template<typename Vector, typename Iterator>
216void CheckConstIterator( const Vector& u, int i, const Iterator& cp ) {
217 typename Vector::const_reference pref = *cp;
218 if( pref.bar()!=i )
219 std::printf("ERROR for u[%ld] using const_iterator\n", long(i));
220 typename Vector::difference_type delta = cp-u.begin();
221 ASSERT( delta==i, NULL );
222 if( u[i].bar()!=i )
223 std::printf("ERROR for u[%ld] using subscripting\n", long(i));
224 ASSERT( u.begin()[i].bar()==i, NULL );
225}
226
227template<typename Iterator1, typename Iterator2, typename V>
228void CheckIteratorComparison( V& u ) {
229 Iterator1 i = u.begin();
230 for( int i_count=0; i_count<100; ++i_count ) {
231 Iterator2 j = u.begin();
232 for( int j_count=0; j_count<100; ++j_count ) {
233 ASSERT( (i==j)==(i_count==j_count), NULL );
234 ASSERT( (i!=j)==(i_count!=j_count), NULL );
235 ASSERT( (i-j)==(i_count-j_count), NULL );
236 ASSERT( (i<j)==(i_count<j_count), NULL );
237 ASSERT( (i>j)==(i_count>j_count), NULL );
238 ASSERT( (i<=j)==(i_count<=j_count), NULL );
239 ASSERT( (i>=j)==(i_count>=j_count), NULL );
240 ++j;
241 }
242 ++i;
243 }
244}
245
246//! Test sequential iterators for vector type V.
247/** Also does timing. */
248template<typename V>
249void TestSequentialFor() {
250 V v;
251 v.grow_by(N);
252
253 // Check iterator
254 tbb::tick_count t0 = tbb::tick_count::now();
255 typename V::iterator p = v.begin();
256 ASSERT( !(*p).is_const(), NULL );
257 ASSERT( !p->is_const(), NULL );
258 for( int i=0; size_t(i)<v.size(); ++i, ++p ) {
259 if( (*p).state!=Foo::DefaultInitialized )
260 std::printf("ERROR for v[%ld]\n", long(i));
261 typename V::reference pref = *p;
262 pref.bar() = i;
263 typename V::difference_type delta = p-v.begin();
264 ASSERT( delta==i, NULL );
265 ASSERT( -delta<=0, "difference type not signed?" );
266 }
267 tbb::tick_count t1 = tbb::tick_count::now();
268
269 // Check const_iterator going forwards
270 const V& u = v;
271 typename V::const_iterator cp = u.begin();
272 ASSERT( (*cp).is_const(), NULL );
273 ASSERT( cp->is_const(), NULL );
274 for( int i=0; size_t(i)<u.size(); ++i, ++cp ) {
275 CheckConstIterator(u,i,cp);
276 }
277 tbb::tick_count t2 = tbb::tick_count::now();
278 if( Verbose )
279 std::printf("Time for serial for: assign time = %8.5f, check time = %8.5f\n",
280 (t1-t0).seconds(),(t2-t1).seconds());
281
282 // Now go backwards
283 cp = u.end();
284 for( int i=int(u.size()); i>0; ) {
285 --i;
286 --cp;
287 if( i>0 ) {
288 typename V::const_iterator cp_old = cp--;
289 int here = (*cp_old).bar();
290 ASSERT( here==u[i].bar(), NULL );
291 typename V::const_iterator cp_new = cp++;
292 int prev = (*cp_new).bar();
293 ASSERT( prev==u[i-1].bar(), NULL );
294 }
295 CheckConstIterator(u,i,cp);
296 }
297
298 // Now go forwards and backwards
299 cp = u.begin();
300 ptrdiff_t k = 0;
301 for( size_t i=0; i<u.size(); ++i ) {
302 CheckConstIterator(u,int(k),cp);
303 typename V::difference_type delta = i*3 % u.size();
304 if( 0<=k+delta && size_t(k+delta)<u.size() ) {
305 cp += delta;
306 k += delta;
307 }
308 delta = i*7 % u.size();
309 if( 0<=k-delta && size_t(k-delta)<u.size() ) {
310 if( i&1 )
311 cp -= delta; // Test operator-=
312 else
313 cp = cp - delta; // Test operator-
314 k -= delta;
315 }
316 }
317
318 for( int i=0; size_t(i)<u.size(); i=(i<50?i+1:i*3) )
319 for( int j=-i; size_t(i+j)<u.size(); j=(j<50?j+1:j*5) ) {
320 ASSERT( (u.begin()+i)[j].bar()==i+j, NULL );
321 ASSERT( (v.begin()+i)[j].bar()==i+j, NULL );
322 ASSERT( (i+u.begin())[j].bar()==i+j, NULL );
323 ASSERT( (i+v.begin())[j].bar()==i+j, NULL );
324 }
325
326 CheckIteratorComparison<typename V::iterator, typename V::iterator>(v);
327 CheckIteratorComparison<typename V::iterator, typename V::const_iterator>(v);
328 CheckIteratorComparison<typename V::const_iterator, typename V::iterator>(v);
329 CheckIteratorComparison<typename V::const_iterator, typename V::const_iterator>(v);
330
331 TestIteratorAssignment<typename V::const_iterator>( u.begin() );
332 TestIteratorAssignment<typename V::const_iterator>( v.begin() );
333 TestIteratorAssignment<typename V::iterator>( v.begin() );
334
335 // Check reverse_iterator
336 typename V::reverse_iterator rp = v.rbegin();
337 for( size_t i=v.size(); i>0; --i, ++rp ) {
338 typename V::reference pref = *rp;
339 ASSERT( size_t(pref.bar())==i-1, NULL );
340 ASSERT( rp!=v.rend(), NULL );
341 }
342 ASSERT( rp==v.rend(), NULL );
343
344 // Check const_reverse_iterator
345 typename V::const_reverse_iterator crp = u.rbegin();
346 for( size_t i=v.size(); i>0; --i, ++crp ) {
347 typename V::const_reference cpref = *crp;
348 ASSERT( size_t(cpref.bar())==i-1, NULL );
349 ASSERT( crp!=u.rend(), NULL );
350 }
351 ASSERT( crp==u.rend(), NULL );
352
353 TestIteratorAssignment<typename V::const_reverse_iterator>( u.rbegin() );
354 TestIteratorAssignment<typename V::reverse_iterator>( v.rbegin() );
355}
356
357static const size_t Modulus = 7;
358
359typedef tbb::concurrent_vector<Foo> MyVector;
360
361class GrowToAtLeast {
362 MyVector& my_vector;
363public:
364 void operator()( const tbb::blocked_range<size_t>& range ) const {
365 for( size_t i=range.begin(); i!=range.end(); ++i ) {
366 size_t n = my_vector.size();
367 size_t k = n==0 ? 0 : i % (2*n+1);
368 my_vector.grow_to_at_least(k+1);
369 ASSERT( my_vector.size()>=k+1, NULL );
370 }
371 }
372 GrowToAtLeast( MyVector& vector ) : my_vector(vector) {}
373};
374
375void TestConcurrentGrowToAtLeast() {
376 MyVector v;
377 for( size_t s=1; s<1000; s*=10 ) {
378 tbb::parallel_for( tbb::blocked_range<size_t>(0,1000000,100), GrowToAtLeast(v) );
379 }
380}
381
382//! Test concurrent invocations of method concurrent_vector::grow_by
383class GrowBy {
384 MyVector& my_vector;
385public:
386 void operator()( const tbb::blocked_range<int>& range ) const {
387 for( int i=range.begin(); i!=range.end(); ++i ) {
388 if( i%3 ) {
389 Foo& element = my_vector[my_vector.grow_by(1)];
390 element.bar() = i;
391 } else {
392 Foo f;
393 f.bar() = i;
394 size_t k = my_vector.push_back( f );
395 ASSERT( my_vector[k].bar()==i, NULL );
396 }
397 }
398 }
399 GrowBy( MyVector& vector ) : my_vector(vector) {}
400};
401
402//! Test concurrent invocations of method concurrent_vector::grow_by
403void TestConcurrentGrowBy( int nthread ) {
404 int m = 100000;
405 MyVector v;
406 tbb::parallel_for( tbb::blocked_range<int>(0,m,1000), GrowBy(v) );
407 ASSERT( v.size()==size_t(m), NULL );
408
409 // Verify that v is a permutation of 0..m
410 int inversions = 0;
411 bool* found = new bool[m];
412 memset( found, 0, m );
413 for( int i=0; i<m; ++i ) {
414 int index = v[i].bar();
415 ASSERT( !found[index], NULL );
416 found[index] = true;
417 if( i>0 )
418 inversions += v[i].bar()<v[i-1].bar();
419 }
420 for( int i=0; i<m; ++i ) {
421 ASSERT( found[i], NULL );
422 ASSERT( nthread>1 || v[i].bar()==i, "sequential execution is wrong" );
423 }
424 delete[] found;
425 if( nthread>1 && inversions<m/10 )
426 std::printf("Warning: not much concurrency in TestConcurrentGrowBy\n");
427}
428
429//! Test the assignment operator
430void TestAssign() {
431 typedef tbb::concurrent_vector<FooWithAssign> vector_t;
432 for( int dst_size=1; dst_size<=128; NextSize( dst_size ) ) {
433 for( int src_size=2; src_size<=128; NextSize( src_size ) ) {
434 vector_t u;
435 u.grow_to_at_least(src_size);
436 for( int i=0; i<src_size; ++i )
437 u[i].bar() = i*i;
438 vector_t v;
439 v.grow_to_at_least(dst_size);
440 for( int i=0; i<dst_size; ++i )
441 v[i].bar() = -i;
442 v = u;
443 u.clear();
444 ASSERT( u.size()==0, NULL );
445 ASSERT( v.size()==size_t(src_size), NULL );
446 for( int i=0; i<src_size; ++i )
447 ASSERT( v[i].bar()==(i*i), NULL );
448 }
449 }
450}
451
452//------------------------------------------------------------------------
453// Regression test for problem where on oversubscription caused
454// concurrent_vector::grow_by to run very slowly (TR#196).
455//------------------------------------------------------------------------
456
457#include "tbb/task_scheduler_init.h"
458#include <math.h>
459
460typedef unsigned long Number;
461
462static tbb::concurrent_vector<Number> Primes;
463
464class FindPrimes {
465 bool is_prime( Number val ) const {
466 int limit, factor = 3;
467 if( val<5u )
468 return val==2;
469 else {
470 limit = long(sqrtf(float(val))+0.5f);
471 while( factor<=limit && val % factor )
472 ++factor;
473 return factor>limit;
474 }
475 }
476public:
477 void operator()( const tbb::blocked_range<Number>& r ) const {
478 for( Number i=r.begin(); i!=r.end(); ++i ) {
479 if( i%2 && is_prime(i) ) {
480 Primes[Primes.grow_by(1)] = i;
481 }
482 }
483 }
484};
485
486static double TimeFindPrimes( int nthread ) {
487 Primes.clear();
488 tbb::task_scheduler_init init(nthread);
489 tbb::tick_count t0 = tbb::tick_count::now();
490 tbb::parallel_for( tbb::blocked_range<Number>(0,1000000,500), FindPrimes() );
491 tbb::tick_count t1 = tbb::tick_count::now();
492 return (t1-t0).seconds();
493}
494
495static void TestFindPrimes() {
496 // Time fully subscribed run.
497 double t2 = TimeFindPrimes( tbb::task_scheduler_init::automatic );
498
499 // Time parallel run that is very likely oversubscribed.
500 double t128 = TimeFindPrimes(128);
501
502 if( Verbose )
503 std::printf("TestFindPrimes: t2==%g t128=%g\n", t2, t128 );
504
505 // We allow the 128-thread run a little extra time to allow for thread overhead.
506 // Theoretically, following test will fail on machine with >128 processors.
507 // But that situation is not going to come up in the near future,
508 // and the generalization to fix the issue is not worth the trouble.
509 if( t128>1.10*t2 ) {
510 std::printf("Warning: grow_by is pathetically slow: t2==%g t128=%g\n", t2, t128);
511 }
512}
513
514//------------------------------------------------------------------------
515// Test compatibility with STL sort.
516//------------------------------------------------------------------------
517
518#include <algorithm>
519
520void TestSort() {
521 for( int n=1; n<100; n*=3 ) {
522 tbb::concurrent_vector<int> array;
523 array.grow_by( n );
524 for( int i=0; i<n; ++i )
525 array[i] = (i*7)%n;
526 std::sort( array.begin(), array.end() );
527 for( int i=0; i<n; ++i )
528 ASSERT( array[i]==i, NULL );
529 }
530}
531
532//------------------------------------------------------------------------
533
534int TestMain () {
535 if( MinThread<1 ) {
536 std::printf("ERROR: MinThread=%d, but must be at least 1\n",MinThread);
537 }
538
539 TestIteratorTraits<tbb::concurrent_vector<Foo>::iterator,Foo>();
540 TestIteratorTraits<tbb::concurrent_vector<Foo>::const_iterator,const Foo>();
541 TestSequentialFor<tbb::concurrent_vector<Foo> > ();
542 TestResizeAndCopy();
543 TestAssign();
544 TestCapacity();
545 for( int nthread=MinThread; nthread<=MaxThread; ++nthread ) {
546 tbb::task_scheduler_init init( nthread );
547 TestParallelFor( nthread );
548 TestConcurrentGrowToAtLeast();
549 TestConcurrentGrowBy( nthread );
550 }
551 TestFindPrimes();
552 TestSort();
553 return Harness::Done;
554}
555