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

32#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H

33#define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1

43{

45 template<typename _DifferenceTp>

47 {

48 typedef _DifferenceTp _DifferenceType;

55 };

60 template<typename _RAIter>

62 {

64 typedef typename _TraitsType::value_type _ValueType;

65 typedef typename _TraitsType::difference_type _DifferenceType;

87 };

95 template<typename _RAIter, typename _DifferenceTp>

96 void

98 _DifferenceTp __num_samples)

99 {

101 typedef typename _TraitsType::value_type _ValueType;

102 typedef _DifferenceTp _DifferenceType;

103

105

106 _DifferenceType* __es = new _DifferenceType[__num_samples + 2];

107

109 __num_samples + 1, __es);

110

111 for (_DifferenceType __i = 0; __i < __num_samples; ++__i)

112 ::new(&(__sd->_M_samples[__iam * __num_samples + __i]))

114 + __es[__i + 1]]);

115

116 delete[] __es;

117 }

118

119

120 template<bool __exact, typename _RAIter,

121 typename _Compare, typename _SortingPlacesIterator>

123 { };

124

125

126 template<typename _RAIter, typename _Compare,

127 typename _SortingPlacesIterator>

129 {

130 void

133 _Compare& __comp,

134 const typename

136 __num_samples) const

137 {

138# pragma omp barrier

139

141 _SortingPlacesIterator> >

144 __seqs[__s] = std::make_pair(__sd->_M_temporary[__s],

148

150

151

152 if (__iam < __sd->_M_num_threads - 1)

155 __comp);

156

158 {

159

161 __sd->_M_pieces[__iam][__seq]._M_end

162 = __offsets[__seq] - __seqs[__seq].first;

163 else

164

165 __sd->_M_pieces[__iam][__seq]._M_end =

167 }

168

169# pragma omp barrier

170

172 {

173

174 if (__iam > 0)

175 __sd->_M_pieces[__iam][__seq]._M_begin =

176 __sd->_M_pieces[__iam - 1][__seq]._M_end;

177 else

178

179 __sd->_M_pieces[__iam][__seq]._M_begin = 0;

180 }

181 }

182 };

183

184

185 template<typename _RAIter, typename _Compare,

186 typename _SortingPlacesIterator>

188 {

189 void

192 _Compare& __comp,

193 const typename

195 __num_samples) const

196 {

198 typedef typename _TraitsType::value_type _ValueType;

199 typedef typename _TraitsType::difference_type _DifferenceType;

200

202

203# pragma omp barrier

204

205# pragma omp single

206 __gnu_sequential::sort(__sd->_M_samples,

209 __comp);

210

211# pragma omp barrier

212

214 {

215

216 if (__num_samples * __iam > 0)

217 __sd->_M_pieces[__iam][__s]._M_begin =

222 __sd->_M_samples[__num_samples * __iam],

223 __comp)

225 else

226

227 __sd->_M_pieces[__iam][__s]._M_begin = 0;

228

229 if ((__num_samples * (__iam + 1)) <

231 __sd->_M_pieces[__iam][__s]._M_end =

236 __sd->_M_samples[__num_samples * (__iam + 1)],

237 __comp)

239 else

240

243 }

244 }

245 };

246

247 template<bool __stable, typename _RAIter, typename _Compare>

248 struct __possibly_stable_sort

249 { };

250

251 template<typename _RAIter, typename _Compare>

252 struct __possibly_stable_sort<true, _RAIter, _Compare>

253 {

254 void operator()(const _RAIter& __begin,

255 const _RAIter& __end, _Compare& __comp) const

256 { __gnu_sequential::stable_sort(__begin, __end, __comp); }

257 };

258

259 template<typename _RAIter, typename _Compare>

260 struct __possibly_stable_sort<false, _RAIter, _Compare>

261 {

262 void operator()(const _RAIter __begin,

263 const _RAIter __end, _Compare& __comp) const

264 { __gnu_sequential::sort(__begin, __end, __comp); }

265 };

266

267 template<bool __stable, typename _Seq_RAIter,

268 typename _RAIter, typename _Compare,

269 typename _DiffType>

270 struct __possibly_stable_multiway_merge

271 { };

272

273 template<typename _Seq_RAIter, typename _RAIter,

274 typename _Compare, typename _DiffType>

275 struct __possibly_stable_multiway_merge<true, _Seq_RAIter,

276 _RAIter, _Compare, _DiffType>

277 {

278 void operator()(const _Seq_RAIter& __seqs_begin,

279 const _Seq_RAIter& __seqs_end,

280 const _RAIter& __target,

281 _Compare& __comp,

282 _DiffType __length_am) const

283 { stable_multiway_merge(__seqs_begin, __seqs_end, __target,

284 __length_am, __comp, sequential_tag()); }

285 };

286

287 template<typename _Seq_RAIter, typename _RAIter,

288 typename _Compare, typename _DiffType>

289 struct __possibly_stable_multiway_merge<false, _Seq_RAIter,

290 _RAIter, _Compare, _DiffType>

291 {

292 void operator()(const _Seq_RAIter& __seqs_begin,

293 const _Seq_RAIter& __seqs_end,

294 const _RAIter& __target,

295 _Compare& __comp,

296 _DiffType __length_am) const

297 { multiway_merge(__seqs_begin, __seqs_end, __target, __length_am,

298 __comp, sequential_tag()); }

299 };

300

301

302

303

304

305 template<bool __stable, bool __exact, typename _RAIter,

306 typename _Compare>

307 void

309 _Compare& __comp)

310 {

312 typedef typename _TraitsType::value_type _ValueType;

313 typedef typename _TraitsType::difference_type _DifferenceType;

314

316

317

318 _DifferenceType __length_local =

320

321

322

323 typedef _ValueType* _SortingPlacesIterator;

324

326 static_cast<_ValueType*>(::operator new(sizeof(_ValueType)

327 * (__length_local + 1)));

328

329

332 + __length_local,

334

335 __possibly_stable_sort<__stable, _SortingPlacesIterator, _Compare>()

338 __comp);

339

340

341

342

343

344

345 _DifferenceType __num_samples =

348 (__iam, __sd, __comp, __num_samples);

349

350

351 _DifferenceType __offset = 0, __length_am = 0;

353 {

354 __length_am += (__sd->_M_pieces[__iam][__s]._M_end

355 - __sd->_M_pieces[__iam][__s]._M_begin);

356 __offset += __sd->_M_pieces[__iam][__s]._M_begin;

357 }

358

361 _SeqVector;

363

365 {

366 __seqs[__s] =

368 + __sd->_M_pieces[__iam][__s]._M_begin,

370 + __sd->_M_pieces[__iam][__s]._M_end);

371 }

372

373 __possibly_stable_multiway_merge<

374 __stable, typename _SeqVector::iterator,

375 _RAIter, _Compare, _DifferenceType>()(__seqs.begin(), __seqs.end(),

376 __sd->_M_source + __offset, __comp,

377 __length_am);

378

379# pragma omp barrier

380

381 for (_DifferenceType __i = 0; __i < __length_local; ++__i)

382 __sd->_M_temporary[__iam][__i].~_ValueType();

383 ::operator delete(__sd->_M_temporary[__iam]);

384 }

385

386

387

388

389

390

391

392 template<bool __stable, bool __exact, typename _RAIter,

393 typename _Compare>

394 void

396 _Compare __comp,

398 {

400

402 typedef typename _TraitsType::value_type _ValueType;

403 typedef typename _TraitsType::difference_type _DifferenceType;

404

405 _DifferenceType __n = __end - __begin;

406

407 if (__n <= 1)

408 return;

409

410

411 if (__num_threads > __n)

412 __num_threads = static_cast<_ThreadIndex>(__n);

413

414

416 _DifferenceType* __starts;

417 _DifferenceType __size;

418

419# pragma omp parallel num_threads(__num_threads)

420 {

421 __num_threads = omp_get_num_threads();

422

423# pragma omp single

424 {

427

428 __sd._M_temporary = new _ValueType*[__num_threads];

429

430 if (!__exact)

431 {

432 __size =

434 * __num_threads;

435 __sd._M_samples = static_cast<_ValueType*>

436 (::operator new(__size * sizeof(_ValueType)));

437 }

438 else

440

441 __sd._M_offsets = new _DifferenceType[__num_threads - 1];

444 for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)

445 __sd._M_pieces[__s].resize(__num_threads);

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

447

448 _DifferenceType __chunk_length = __n / __num_threads;

449 _DifferenceType __split = __n % __num_threads;

450 _DifferenceType __pos = 0;

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

452 {

453 __starts[__i] = __pos;

454 __pos += ((__i < __split)

455 ? (__chunk_length + 1) : __chunk_length);

456 }

457 __starts[__num_threads] = __pos;

458 }

459

460

461 parallel_sort_mwms_pu<__stable, __exact>(&__sd, __comp);

462 }

463

464 delete[] __starts;

466

467 if (!__exact)

468 {

469 for (_DifferenceType __i = 0; __i < __size; ++__i)

472 }

473

476 }

477

478}

479

480#endif

Includes the original header files concerned with iterators except for stream iterators....

#define _GLIBCXX_CALL(__n)

Macro to produce log message when entering a function.

Implementation of sequential and parallel multiway merge.

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

_ForwardIterator uninitialized_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result)

Copies the range [first,last) into result.

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...

_RAIterOut multiway_merge(_RAIterPairIterator __seqs_begin, _RAIterPairIterator __seqs_end, _RAIterOut __target, _DifferenceTp __length, _Compare __comp, __gnu_parallel::sequential_tag)

Multiway Merge Frontend.

void __determine_samples(_PMWMSSortingData< _RAIter > *__sd, _DifferenceTp __num_samples)

Select _M_samples from a sequence.

void parallel_sort_mwms_pu(_PMWMSSortingData< _RAIter > *__sd, _Compare &__comp)

PMWMS code executed by each thread.

_OutputIterator __equally_split(_DifferenceType __n, _ThreadIndex __num_threads, _OutputIterator __s)

function to split a sequence into parts of almost equal size.

void multiseq_partition(_RanSeqs __begin_seqs, _RanSeqs __end_seqs, _RankType __rank, _RankIterator __begin_offsets, _Compare __comp=std::less< typename std::iterator_traits< typename std::iterator_traits< _RanSeqs >::value_type::first_type >::value_type >())

Splits several sorted sequences at a certain global __rank, resulting in a splitting point for each s...

void parallel_sort_mwms(_RAIter __begin, _RAIter __end, _Compare __comp, _ThreadIndex __num_threads)

PMWMS main call.

Traits class for iterators.

Struct holding two objects of arbitrary type.

A standard container which offers fixed time access to individual elements in any order.

constexpr iterator begin() noexcept

_DifferenceType _M_begin

Begin of subsequence.

_DifferenceType _M_end

End of subsequence.

Data accessed by all threads.

_DifferenceType * _M_offsets

Offsets to add to the found positions.

_ValueType * _M_samples

Samples.

_RAIter _M_source

Input __begin.

_DifferenceType * _M_starts

Start indices, per thread.

std::vector< _Piece< _DifferenceType > > * _M_pieces

Pieces of data to merge [thread][__sequence].

_ThreadIndex _M_num_threads

Number of threads involved.

_ValueType ** _M_temporary

Storage in which to sort.

unsigned int sort_mwms_oversampling

Oversampling factor for parallel std::sort (MWMS).

static const _Settings & get()

Get the global settings.