libstdc++: random_shuffle.h Source File (original) (raw)

32#ifndef _GLIBCXX_PARALLEL_RANDOM_SHUFFLE_H

33#define _GLIBCXX_PARALLEL_RANDOM_SHUFFLE_H 1

41{

51 template<typename _RAIter>

53 {

55 typedef typename _TraitsType::value_type _ValueType;

56 typedef typename _TraitsType::difference_type _DifferenceType;

85 };

90 template<typename _RAIter, typename _RandomNumberGenerator>

92 {

101

102

104

105

107 };

108

109

110

111

112

113 template<typename _RandomNumberGenerator>

114 inline int

116 { return __rng.__genrand_bits(__logp); }

117

118

119

120 template<typename _RAIter, typename _RandomNumberGenerator>

121 void

123 _RandomNumberGenerator>* __pus)

124 {

126 typedef typename _TraitsType::value_type _ValueType;

127 typedef typename _TraitsType::difference_type _DifferenceType;

128

132

133

134 _DifferenceType __length = (__sd->_M_starts[__iam + 1]

137 _DifferenceType* __dist = new _DifferenceType[__sd->_M_num_bins + 1];

139 _ValueType** __temporaries = new _ValueType*[__d->_M_num_threads];

140

141

143 __dist[__b] = 0;

145

147

148

149 for (_DifferenceType __i = 0; __i < __length; ++__i)

150 {

152 __oracles[__i] = __oracle;

153

154

155 ++(__dist[__oracle + 1]);

156 }

157

159 __sd->_M_dist[__b][__iam + 1] = __dist[__b];

160

161# pragma omp barrier

162

163# pragma omp single

164 {

165

166

172 }

173

174# pragma omp barrier

175

179

180# pragma omp barrier

181

183 {

184 for (int __t = 0; __t < __d->_M_num_threads + 1; ++__t)

185 __sd->_M_dist[__s + 1][__t] += __offset;

187 }

188

189 __sd->_M_temporaries[__iam] = static_cast<_ValueType*>

190 (::operator new(sizeof(_ValueType) * __offset));

191

192# pragma omp barrier

193

194

196 __dist[__b] = __sd->_M_dist[__b][__iam];

198 __bin_proc[__b] = __sd->_M_bin_proc[__b];

201

202 _RAIter __source = __sd->_M_source;

203 _DifferenceType __start = __sd->_M_starts[__iam];

204

205

206 for (_DifferenceType __i = 0; __i < __length; ++__i)

207 {

208 _BinIndex __target_bin = __oracles[__i];

209 _ThreadIndex __target_p = __bin_proc[__target_bin];

210

211

212 ::new(&(__temporaries[__target_p][__dist[__target_bin + 1]++]))

213 _ValueType(*(__source + __i + __start));

214 }

215

216 delete[] __oracles;

217 delete[] __dist;

218 delete[] __bin_proc;

219 delete[] __temporaries;

220

221# pragma omp barrier

222

223

225 {

226 _ValueType* __begin =

232

234 std::copy(__begin, __end, __sd->_M_source + __global_offset

237 }

238

242 }

243

244

245

246 template<typename _Tp>

247 _Tp

249 {

250 if (__x <= 1)

251 return 1;

252 else

253 return (_Tp)1 << (__rd_log2(__x - 1) + 1);

254 }

255

256

257

258

259

260

261

262

263 template<typename _RAIter, typename _RandomNumberGenerator>

264 void

267 <_RAIter>::difference_type __n,

269 _RandomNumberGenerator& __rng)

270 {

272 typedef typename _TraitsType::value_type _ValueType;

273 typedef typename _TraitsType::difference_type _DifferenceType;

274

276

278

279 if (__num_threads > __n)

280 __num_threads = static_cast<_ThreadIndex>(__n);

281

282 _BinIndex __num_bins, __num_bins_cache;

283

284#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1

285

286

287

288 __num_bins_cache =

289 std::max<_DifferenceType>(1, __n / (__s.L1_cache_size_lb

290 / sizeof(_ValueType)));

292

293

294

295 __num_bins = std::min<_DifferenceType>(__n, __num_bins_cache);

296

297#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB

298

299 __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);

300#endif

302

303 if (__num_bins < __num_bins_cache)

304 {

305#endif

306

307

308 __num_bins_cache = static_cast<_BinIndex>

309 (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size

310 / sizeof(_ValueType))));

312

313

314 __num_bins = static_cast<_BinIndex>

315 (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));

316

317#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB

318

319 __num_bins = std::min(static_cast<_DifferenceType>(__s.TLB_size / 2),

320 __num_bins);

321#endif

323#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1

324 }

325#endif

326

328 std::max<_BinIndex>(__num_threads, __num_bins));

329

330 if (__num_threads <= 1)

331 {

335 return;

336 }

337

340 _DifferenceType* __starts;

341

342# pragma omp parallel num_threads(__num_threads)

343 {

344 _ThreadIndex __num_threads = omp_get_num_threads();

345# pragma omp single

346 {

348

349 __sd._M_temporaries = new _ValueType*[__num_threads];

350 __sd._M_dist = new _DifferenceType*[__num_bins + 1];

352 for (_BinIndex __b = 0; __b < __num_bins + 1; ++__b)

353 __sd._M_dist[__b] = new _DifferenceType[__num_threads + 1];

354 for (_BinIndex __b = 0; __b < (__num_bins + 1); ++__b)

355 {

357 __sd._M_dist[__b][0] = 0;

358 }

359 __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];

360 int __bin_cursor = 0;

363

364 _DifferenceType __chunk_length = __n / __num_threads,

365 __split = __n % __num_threads,

366 __start = 0;

367 _DifferenceType __bin_chunk_length = __num_bins / __num_threads,

368 __bin_split = __num_bins % __num_threads;

369 for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)

370 {

371 __starts[__i] = __start;

372 __start += (__i < __split

373 ? (__chunk_length + 1) : __chunk_length);

374 int __j = __pus[__i]._M_bins_begin = __bin_cursor;

375

376

377 __bin_cursor += (__i < __bin_split

378 ? (__bin_chunk_length + 1)

379 : __bin_chunk_length);

380 __pus[__i].__bins_end = __bin_cursor;

381 for (; __j < __bin_cursor; ++__j)

385 __pus[__i]._M_sd = &__sd;

386 }

387 __starts[__num_threads] = __start;

388 }

389

391 }

392

393 delete[] __starts;

395 for (int __s = 0; __s < (__num_bins + 1); ++__s)

396 delete[] __sd._M_dist[__s];

399

400 delete[] __pus;

401 }

402

403

404

405

406

407

408 template<typename _RAIter, typename _RandomNumberGenerator>

409 void

411 _RandomNumberGenerator& __rng)

412 {

414 typedef typename _TraitsType::value_type _ValueType;

415 typedef typename _TraitsType::difference_type _DifferenceType;

416

417 _DifferenceType __n = __end - __begin;

419

420 _BinIndex __num_bins, __num_bins_cache;

421

422#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1

423

424 __num_bins_cache = std::max<_DifferenceType>

425 (1, __n / (__s.L1_cache_size_lb / sizeof(_ValueType)));

427

428

429

430 __num_bins = std::min(__n, (_DifferenceType)__num_bins_cache);

431#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB

432

433 __num_bins = std::min((_DifferenceType)__s.TLB_size / 2, __num_bins);

434#endif

436

437 if (__num_bins < __num_bins_cache)

438 {

439#endif

440

441 __num_bins_cache = static_cast<_BinIndex>

442 (std::max<_DifferenceType>(1, __n / (__s.L2_cache_size

443 / sizeof(_ValueType))));

445

446

447

448 __num_bins = static_cast<_BinIndex>

449 (std::min(__n, static_cast<_DifferenceType>(__num_bins_cache)));

450

451#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB

452

453 __num_bins = std::min<_DifferenceType>(__s.TLB_size / 2, __num_bins);

454#endif

456#if _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1

457 }

458#endif

459

460 int __num_bits = __rd_log2(__num_bins);

461

462 if (__num_bins > 1)

463 {

464 _ValueType* __target =

465 static_cast<_ValueType*>(::operator new(sizeof(_ValueType) * __n));

467 _DifferenceType* __dist0 = new _DifferenceType[__num_bins + 1],

468 * __dist1 = new _DifferenceType[__num_bins + 1];

469

470 for (int __b = 0; __b < __num_bins + 1; ++__b)

471 __dist0[__b] = 0;

472

474

475 for (_DifferenceType __i = 0; __i < __n; ++__i)

476 {

478 __oracles[__i] = __oracle;

479

480

481 ++(__dist0[__oracle + 1]);

482 }

483

484

486 __dist0);

487

488 for (int __b = 0; __b < __num_bins + 1; ++__b)

489 __dist1[__b] = __dist0[__b];

490

491

492 for (_DifferenceType __i = 0; __i < __n; ++__i)

493 ::new(&(__target[(__dist0[__oracles[__i]])++]))

494 _ValueType(*(__begin + __i));

495

496 for (int __b = 0; __b < __num_bins; ++__b)

498 __target + __dist1[__b + 1], __rng);

499

500

501 std::copy(__target, __target + __n, __begin);

502

503 delete[] __dist0;

504 delete[] __dist1;

505 delete[] __oracles;

506

507 for (_DifferenceType __i = 0; __i < __n; ++__i)

508 __target[__i].~_ValueType();

509 ::operator delete(__target);

510 }

511 else

512 __gnu_sequential::random_shuffle(__begin, __end, __rng);

513 }

514

515

516

517

518

519

520 template<typename _RAIter, typename _RandomNumberGenerator>

521 inline void

524 {

526 typedef typename _TraitsType::difference_type _DifferenceType;

527 _DifferenceType __n = __end - __begin;

529 __get_max_threads(), __rng);

530 }

531}

532

533#endif

#define _GLIBCXX_CALL(__n)

Macro to produce log message when entering a function.

End-user include file. Provides advanced settings and tuning options. This file is a GNU parallel ext...

Random number generator based on the Mersenne twister. This file is a GNU parallel extension to the S...

constexpr const _Tp & min(const _Tp &, const _Tp &)

This does what you think it does.

constexpr _OutputIterator partial_sum(_InputIterator __first, _InputIterator __last, _OutputIterator __result)

Return list of partial sums.

GNU parallel code for public use.

uint16_t _ThreadIndex

Unsigned integer to index a thread number. The maximum thread number (for each processor) must fit in...

int __random_number_pow2(int __logp, _RandomNumberGenerator &__rng)

Generate a random number in [0,2^__logp).

uint64_t _SequenceIndex

Unsigned integer to index __elements. The total number of elements for each algorithm must fit into t...

void __parallel_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator __rng=_RandomNumber())

Parallel random public call.

_Tp __round_up_to_pow2(_Tp __x)

Round up to the next greater power of 2.

void __parallel_random_shuffle_drs(_RAIter __begin, _RAIter __end, typename std::iterator_traits< _RAIter >::difference_type __n, _ThreadIndex __num_threads, _RandomNumberGenerator &__rng)

Main parallel random shuffle step.

void __sequential_random_shuffle(_RAIter __begin, _RAIter __end, _RandomNumberGenerator &__rng)

Sequential cache-efficient random shuffle.

void __parallel_random_shuffle_drs_pu(_DRSSorterPU< _RAIter, _RandomNumberGenerator > *__pus)

Random shuffle code executed by each thread.

unsigned short _BinIndex

Type to hold the index of a bin.

_Size __rd_log2(_Size __n)

Calculates the rounded-down logarithm of __n for base 2.

Properties of fundamental types.

Traits class for iterators.

Random number generator, based on the Mersenne twister.

Data known to every thread participating in __gnu_parallel::__parallel_random_shuffle().

_DifferenceType ** _M_dist

Two-dimensional array to hold the thread-bin distribution.

_DRandomShufflingGlobalData(_RAIter &__source)

Constructor.

int _M_num_bins

Number of bins to distribute to.

_ValueType ** _M_temporaries

Temporary arrays for each thread.

_ThreadIndex * _M_bin_proc

Number of the thread that will further process the corresponding bin.

_RAIter & _M_source

Begin iterator of the __source.

_DifferenceType * _M_starts

Start indexes of the threads' __chunks.

int _M_num_bits

Number of bits needed to address the bins.

Local data for a thread participating in __gnu_parallel::__parallel_random_shuffle().

_BinIndex _M_bins_begin

Begin index for bins taken care of by this thread.

_BinIndex __bins_end

End index for bins taken care of by this thread.

uint32_t _M_seed

Random _M_seed for this thread.

_DRandomShufflingGlobalData< _RAIter > * _M_sd

Pointer to global data.

int _M_num_threads

Number of threads participating in total.

class _Settings Run-time settings for the parallel mode including all tunable parameters.

unsigned int TLB_size

size of the Translation Lookaside Buffer (underestimation).

unsigned long long L2_cache_size

size of the L2 cache in bytes (underestimation).

static const _Settings & get()

Get the global settings.