ints in parallel code

[Paolo Carlini-3]

Hi Johannes,

today was going through the parallel code to do some more or less
formatting and uglifications fixes, when I noticed something potentially
much more serious: I'm seeing many plain ints around, also for things
which look like indexes in data, differences of iterators, things like
that. That would be not 64-bit clean, a rather serious issue these days,
but automatically replacing longs would be in general essentially enough
to fix the problem (ptrdiff_t can be more correct in some cases). Can
you look a bit into this?

Thanks,
Paolo.

[Paolo Carlini-3]

Paolo Carlini wrote:
> today was going through the parallel code to do some more or less
> formatting and uglifications fixes, when I noticed something potentially
> much more serious: I'm seeing many plain ints around, also for things
> which look like indexes in data, differences of iterators, things like
> that.
In particular, I wish you could double check the various ints used in
the *multiway* functions, which seem all suspect to me.

Paolo.

[Johannes Singler-2]

Paolo Carlini wrote:
> Paolo Carlini wrote:
>> today was going through the parallel code to do some more or less
>> formatting and uglifications fixes, when I noticed something potentially
>> much more serious: I'm seeing many plain ints around, also for things
>> which look like indexes in data, differences of iterators, things like
>> that.
> In particular, I wish you could double check the various ints used in
> the *multiway* functions, which seem all suspect to me.

All the ints in multiway*.h address sequences, i. e. the functions are
limited to about 2^31 sequences.  The number of elements in these
sequences can be much higher.

In principle, you are right, the sequences are passed using iterators,
and their difference could be 64 bits.  In practice, we are much further
away from having more than 2^31 sequences, than having more than 2^31
elements e. g. for sorting.

Anyway, do you want me to replace it with the appropriate
difference_type?  It might have performance implications, though.

Johannes

[Paolo Carlini-3]

Hi,
> All the ints in multiway*.h address sequences, i. e. the functions are
> limited to about 2^31 sequences.  The number of elements in these
> sequences can be much higher.
>
> In principle, you are right, the sequences are passed using iterators,
> and their difference could be 64 bits.  In practice, we are much further
> away from having more than 2^31 sequences, than having more than 2^31
> elements e. g. for sorting.
>  
Ok... Then, please help me summarizing the issue: if the user has a
"data set" of 2^34 alements, will it be automatically "split", ie,
processed, in chunks each < 2^31 elements?
> Anyway, do you want me to replace it with the appropriate
> difference_type?  It might have performance implications, though.
>  
In general, if you want my opinion, these days unless you have *very
clear* benchmarking numbers in front of you, it's always a very good
idea to use the correct types, to begin with: if the difference can need
64 bits to be represented, use a 64-bit type.

Paolo.

[Johannes Singler-2]

Paolo Carlini wrote:

> Hi,
>> All the ints in multiway*.h address sequences, i. e. the functions are
>> limited to about 2^31 sequences.  The number of elements in these
>> sequences can be much higher.
>>
>> In principle, you are right, the sequences are passed using iterators,
>> and their difference could be 64 bits.  In practice, we are much further
>> away from having more than 2^31 sequences, than having more than 2^31
>> elements e. g. for sorting.
>>  
> Ok... Then, please help me summarizing the issue: if the user has a
> "data set" of 2^34 alements, will it be automatically "split", ie,
> processed, in chunks each < 2^31 elements?

No, for sorting, we will have p sequences, for p the number of threads
used.  That should be safe for an int anyway (omp_get_num_threads also
returns an int restrictions).
In general, the number of sequences is determined by the caller.

>> Anyway, do you want me to replace it with the appropriate
>> difference_type?  It might have performance implications, though.
>>  
> In general, if you want my opinion, these days unless you have *very
> clear* benchmarking numbers in front of you, it's always a very good
> idea to use the correct types, to begin with: if the difference can need
> 64 bits to be represented, use a 64-bit type.

The attached patch should get rid of most hard-coded occurrences of int.


Tested x86_64-unknown-linux-gnu: No regressions

Please approve for mainline.

2009-11-09  Johannes Singler  <singler@...>

        * include/parallel/multiway_merge.h (multiway_merge_*,
        __sequential_multiway_merge, parallel_multiway_merge):
        Replace int by appropriate difference_type (typedef to
        _SeqNumber) or _ThreadIndex.
        * include/parallel/multiseq_selection.h (multiseq_partition,
        multiseq_selection): Replace int by appropriate difference_type
        (typedef to _SeqNumber)
        * include/parallel/base.h (__get_max_threads): Replace int by
        _ThreadIndex.
        * include/parallel/balanced_quicksort.h
        (__qsb_local_sort_with_helping, __parallel_sort_qsb): Likewise.
        * include/parallel/set_operations.h (__parallel_set_operation):
        Likewise.
        * include/parallel/unique_copy.h (__parallel_unique_copy):
        Likewise.
        * include/parallel/multiway_mergesort.h (_SplitConsistently,
        parallel_sort_mwms_pu, parallel_sort_mwms): Likewise.
        * include/parallel/partial_sum.h
        (__parallel_partial_sum_linear): Likewise.
        * include/parallel/partition.h (__parallel_partition): Replace
        int by appropriate difference_type or _ThreadIndex.

Johannes

Index: include/parallel/multiway_merge.h
===================================================================
--- include/parallel/multiway_merge.h (revision 154027)
+++ include/parallel/multiway_merge.h (working copy)
@@ -490,26 +490,28 @@
 
       typedef _DifferenceTp _DifferenceType;
       typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
+      typedef typename std::iterator_traits<_RAIterIterator>
  ::value_type::first_type
  _RAIter1;
       typedef typename std::iterator_traits<_RAIter1>::value_type
  _ValueType;
 
-      int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
 
       _LT __lt(__k, __comp);
 
       // Default value for potentially non-default-constructible types.
       _ValueType* __arbitrary_element = NULL;
 
-      for (int __t = 0; __t < __k; ++__t)
+      for (_SeqNumber __t = 0; __t < __k; ++__t)
  {
           if(__arbitrary_element == NULL
      && _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
             __arbitrary_element = &(*__seqs_begin[__t].first);
  }
 
-      for (int __t = 0; __t < __k; ++__t)
+      for (_SeqNumber __t = 0; __t < __k; ++__t)
  {
           if (__seqs_begin[__t].first == __seqs_begin[__t].second)
             __lt.__insert_start(*__arbitrary_element, __t, true);
@@ -519,7 +521,7 @@
 
       __lt.__init();
 
-      int __source;
+      _SeqNumber __source;
 
       for (_DifferenceType __i = 0; __i < __length; ++__i)
  {
@@ -575,16 +577,18 @@
       typedef _DifferenceTp _DifferenceType;
 
       typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
+      typedef typename std::iterator_traits<_RAIterIterator>
  ::value_type::first_type
  _RAIter1;
       typedef typename std::iterator_traits<_RAIter1>::value_type
  _ValueType;
 
-      int __k = __seqs_end - __seqs_begin;
+      _SeqNumber __k = __seqs_end - __seqs_begin;
 
       _LT __lt(__k, __sentinel, __comp);
 
-      for (int __t = 0; __t < __k; ++__t)
+      for (_SeqNumber __t = 0; __t < __k; ++__t)
  {
 #if _GLIBCXX_ASSERTIONS
           _GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
@@ -595,7 +599,7 @@
 
       __lt.__init();
 
-      int __source;
+      _SeqNumber __source;
 
 #if _GLIBCXX_ASSERTIONS
       _DifferenceType __i = 0;
@@ -921,6 +925,8 @@
 
       typedef _DifferenceTp _DifferenceType;
       typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
+      typedef typename std::iterator_traits<_RAIterIterator>
  ::value_type::first_type
  _RAIter1;
       typedef typename std::iterator_traits<_RAIter1>::value_type
@@ -944,7 +950,7 @@
  return __target;
 
       _RAIter3 __return_target = __target;
-      int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
 
       switch (__k)
  {
@@ -1030,15 +1036,17 @@
      std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
     {
       typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
+      typedef typename std::iterator_traits<_RAIterIterator>
  ::value_type::first_type
  _RAIter1;
       typedef typename std::iterator_traits<_RAIter1>::value_type
  _ValueType;
 
       // __k sequences.
-      int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      _SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
 
-      int __num_threads = omp_get_num_threads();
+      _ThreadIndex __num_threads = omp_get_num_threads();
 
       _DifferenceType __num_samples =
  __gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
@@ -1046,7 +1054,7 @@
       _ValueType* __samples = static_cast<_ValueType*>
  (::operator new(sizeof(_ValueType) * __k * __num_samples));
       // Sample.
-      for (int __s = 0; __s < __k; ++__s)
+      for (_SeqNumber __s = 0; __s < __k; ++__s)
  for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
   {
     _DifferenceType sample_index = static_cast<_DifferenceType>
@@ -1062,9 +1070,9 @@
       _SamplingSorter<__stable, _ValueType*, _Compare>()
  (__samples, __samples + (__num_samples * __k), __comp);
 
-      for (int __slab = 0; __slab < __num_threads; ++__slab)
+      for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
  // For each slab / processor.
- for (int __seq = 0; __seq < __k; ++__seq)
+ for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
   {
     // For each sequence.
     if (__slab > 0)
@@ -1108,15 +1116,17 @@
        std::vector<std::pair<_DifferenceType, _DifferenceType> > *__pieces)
     {
       typedef typename std::iterator_traits<_RAIterIterator>
+ ::difference_type _SeqNumber;
+      typedef typename std::iterator_traits<_RAIterIterator>
  ::value_type::first_type
  _RAIter1;
 
       const bool __tight = (__total_length == __length);
 
       // __k sequences.
-      const int __k = static_cast<int>(__seqs_end - __seqs_begin);
+      const _SeqNumber __k = __seqs_end - __seqs_begin;
 
-      const int __num_threads = omp_get_num_threads();
+      const _ThreadIndex __num_threads = omp_get_num_threads();
 
       // (Settings::multiway_merge_splitting
       //  == __gnu_parallel::_Settings::EXACT).
@@ -1130,7 +1140,7 @@
  new _DifferenceType[__num_threads + 1];
       equally_split(__length, __num_threads, __borders);
 
-      for (int __s = 0; __s < (__num_threads - 1); ++__s)
+      for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
  {
   __offsets[__s].resize(__k);
   multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
@@ -1148,10 +1158,10 @@
  }
       delete[] __borders;
 
-      for (int __slab = 0; __slab < __num_threads; ++__slab)
+      for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
  {
   // For each slab / processor.
-  for (int __seq = 0; __seq < __k; ++__seq)
+  for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
     {
       // For each sequence.
       if (__slab == 0)
@@ -1218,6 +1228,8 @@
  _GLIBCXX_CALL(__length)
 
  typedef _DifferenceTp _DifferenceType;
+        typedef typename std::iterator_traits<_RAIterIterator>
+  ::difference_type _SeqNumber;
  typedef typename std::iterator_traits<_RAIterIterator>
           ::value_type::first_type
           _RAIter1;
@@ -1227,7 +1239,7 @@
  // Leave only non-empty sequences.
  typedef std::pair<_RAIter1, _RAIter1> seq_type;
  seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
- int __k = 0;
+ _SeqNumber __k = 0;
  _DifferenceType __total_length = 0;
  for (_RAIterIterator __raii = __seqs_begin;
              __raii != __seqs_end; ++__raii)
@@ -1263,7 +1275,7 @@
     // Thread __t will have to merge pieces[__iam][0..__k - 1]
     __pieces = new std::vector<
     std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
-    for (int __s = 0; __s < __num_threads; ++__s)
+    for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
       __pieces[__s].resize(__k);
 
     _DifferenceType __num_samples =
@@ -1278,12 +1290,12 @@
 
   _DifferenceType __target_position = 0;
 
-  for (int __c = 0; __c < __k; ++__c)
+  for (_SeqNumber __c = 0; __c < __k; ++__c)
     __target_position += __pieces[__iam][__c].first;
 
   seq_type* __chunks = new seq_type[__k];
 
-  for (int __s = 0; __s < __k; ++__s)
+  for (_SeqNumber __s = 0; __s < __k; ++__s)
     __chunks[__s] = std::make_pair(__ne_seqs[__s].first
    + __pieces[__iam][__s].first,
    __ne_seqs[__s].first
Index: include/parallel/multiseq_selection.h
===================================================================
--- include/parallel/multiseq_selection.h (revision 154027)
+++ include/parallel/multiseq_selection.h (working copy)
@@ -133,19 +133,21 @@
 
       typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
         _It;
+      typedef typename std::iterator_traits<_RanSeqs>::difference_type
+        _SeqNumber;
       typedef typename std::iterator_traits<_It>::difference_type
                _DifferenceType;
       typedef typename std::iterator_traits<_It>::value_type _ValueType;
 
-      _Lexicographic<_ValueType, int, _Compare> __lcomp(__comp);
-      _LexicographicReverse<_ValueType, int, _Compare> __lrcomp(__comp);
+      _Lexicographic<_ValueType, _SeqNumber, _Compare> __lcomp(__comp);
+      _LexicographicReverse<_ValueType, _SeqNumber, _Compare> __lrcomp(__comp);
 
       // Number of sequences, number of elements in total (possibly
       // including padding).
       _DifferenceType __m = std::distance(__begin_seqs, __end_seqs), __nn = 0,
                       __nmax, __n, __r;
 
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         {
           __nn += std::distance(__begin_seqs[__i].first,
                                __begin_seqs[__i].second);
@@ -156,7 +158,7 @@
 
       if (__rank == __nn)
         {
-          for (int __i = 0; __i < __m; __i++)
+          for (_SeqNumber __i = 0; __i < __m; __i++)
             __begin_offsets[__i] = __begin_seqs[__i].second; // Very end.
           // Return __m - 1;
           return;
@@ -174,7 +176,7 @@
 
       __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
       __nmax = __ns[0];
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         {
           __ns[__i] = std::distance(__begin_seqs[__i].first,
                                     __begin_seqs[__i].second);
@@ -187,7 +189,7 @@
       // equality iff __nmax = 2^__k - 1.
       __l = (1ULL << __r) - 1;
 
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         {
           __a[__i] = 0;
           __b[__i] = __l;
@@ -200,21 +202,21 @@
 #define __S(__i) (__begin_seqs[__i].first)
 
       // Initial partition.
-      std::vector<std::pair<_ValueType, int> > __sample;
+      std::vector<std::pair<_ValueType, _SeqNumber> > __sample;
 
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         if (__n < __ns[__i])    //__sequence long enough
           __sample.push_back(std::make_pair(__S(__i)[__n], __i));
       __gnu_sequential::sort(__sample.begin(), __sample.end(), __lcomp);
 
-      for (int __i = 0; __i < __m; __i++)       //conceptual infinity
+      for (_SeqNumber __i = 0; __i < __m; __i++)       //conceptual infinity
         if (__n >= __ns[__i])   //__sequence too short, conceptual infinity
           __sample.push_back(
             std::make_pair(__S(__i)[0] /*__dummy element*/, __i));
 
       _DifferenceType __localrank = __rank / __l;
 
-      int __j;
+      _SeqNumber __j;
       for (__j = 0;
            __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
            ++__j)
@@ -227,9 +229,9 @@
         {
           __n /= 2;
 
-          int __lmax_seq = -1;  // to avoid warning
+          _SeqNumber __lmax_seq = -1;  // to avoid warning
           const _ValueType* __lmax = NULL; // impossible to avoid the warning?
-          for (int __i = 0; __i < __m; __i++)
+          for (_SeqNumber __i = 0; __i < __m; __i++)
             {
               if (__a[__i] > 0)
                 {
@@ -250,7 +252,7 @@
                 }
             }
 
-          int __i;
+          _SeqNumber __i;
           for (__i = 0; __i < __m; __i++)
             {
               _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
@@ -263,7 +265,7 @@
             }
 
           _DifferenceType __leftsize = 0;
-          for (int __i = 0; __i < __m; __i++)
+          for (_SeqNumber __i = 0; __i < __m; __i++)
               __leftsize += __a[__i] / (__n + 1);
 
           _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
@@ -271,18 +273,18 @@
           if (__skew > 0)
             {
               // Move to the left, find smallest.
-              std::priority_queue<std::pair<_ValueType, int>,
-                std::vector<std::pair<_ValueType, int> >,
-                _LexicographicReverse<_ValueType, int, _Compare> >
+              std::priority_queue<std::pair<_ValueType, _SeqNumber>,
+                std::vector<std::pair<_ValueType, _SeqNumber> >,
+                _LexicographicReverse<_ValueType, _SeqNumber, _Compare> >
                 __pq(__lrcomp);
               
-              for (int __i = 0; __i < __m; __i++)
+              for (_SeqNumber __i = 0; __i < __m; __i++)
                 if (__b[__i] < __ns[__i])
                   __pq.push(std::make_pair(__S(__i)[__b[__i]], __i));
 
               for (; __skew != 0 && !__pq.empty(); --__skew)
                 {
-                  int __source = __pq.top().second;
+                  _SeqNumber __source = __pq.top().second;
                   __pq.pop();
 
                   __a[__source]
@@ -297,17 +299,18 @@
           else if (__skew < 0)
             {
               // Move to the right, find greatest.
-              std::priority_queue<std::pair<_ValueType, int>,
-                std::vector<std::pair<_ValueType, int> >,
-                _Lexicographic<_ValueType, int, _Compare> > __pq(__lcomp);
+              std::priority_queue<std::pair<_ValueType, _SeqNumber>,
+                std::vector<std::pair<_ValueType, _SeqNumber> >,
+                _Lexicographic<_ValueType, _SeqNumber, _Compare> >
+                  __pq(__lcomp);
 
-              for (int __i = 0; __i < __m; __i++)
+              for (_SeqNumber __i = 0; __i < __m; __i++)
                 if (__a[__i] > 0)
                   __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i));
 
               for (; __skew != 0; ++__skew)
                 {
-                  int __source = __pq.top().second;
+                  _SeqNumber __source = __pq.top().second;
                   __pq.pop();
 
                   __a[__source] -= __n + 1;
@@ -331,7 +334,7 @@
       // Maximum of left edge, minimum of right edge.
       _ValueType* __maxleft = NULL;
       _ValueType* __minright = NULL;
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         {
           if (__a[__i] > 0)
             {
@@ -357,8 +360,8 @@
             }
         }
 
-      int __seq = 0;
-      for (int __i = 0; __i < __m; __i++)
+      _SeqNumber __seq = 0;
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         __begin_offsets[__i] = __S(__i) + __a[__i];
 
       delete[] __ns;
@@ -392,11 +395,13 @@
 
       typedef typename std::iterator_traits<_RanSeqs>::value_type::first_type
         _It;
+      typedef typename std::iterator_traits<_RanSeqs>::difference_type
+        _SeqNumber;
       typedef typename std::iterator_traits<_It>::difference_type
         _DifferenceType;
 
-      _Lexicographic<_Tp, int, _Compare> __lcomp(__comp);
-      _LexicographicReverse<_Tp, int, _Compare> __lrcomp(__comp);
+      _Lexicographic<_Tp, _SeqNumber, _Compare> __lcomp(__comp);
+      _LexicographicReverse<_Tp, _SeqNumber, _Compare> __lrcomp(__comp);
 
       // Number of sequences, number of elements in total (possibly
       // including padding).
@@ -404,7 +409,7 @@
       _DifferenceType __nn = 0;
       _DifferenceType __nmax, __n, __r;
 
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         __nn += std::distance(__begin_seqs[__i].first,
       __begin_seqs[__i].second);
 
@@ -422,7 +427,7 @@
 
       __ns[0] = std::distance(__begin_seqs[0].first, __begin_seqs[0].second);
       __nmax = __ns[0];
-      for (int __i = 0; __i < __m; ++__i)
+      for (_SeqNumber __i = 0; __i < __m; ++__i)
         {
           __ns[__i] = std::distance(__begin_seqs[__i].first,
                                     __begin_seqs[__i].second);
@@ -435,7 +440,7 @@
       // equality iff __nmax = 2^__k - 1
       __l = __round_up_to_pow2(__r) - 1;
 
-      for (int __i = 0; __i < __m; ++__i)
+      for (_SeqNumber __i = 0; __i < __m; ++__i)
         {
           __a[__i] = 0;
           __b[__i] = __l;
@@ -448,23 +453,23 @@
 #define __S(__i) (__begin_seqs[__i].first)
 
       // Initial partition.
-      std::vector<std::pair<_Tp, int> > __sample;
+      std::vector<std::pair<_Tp, _SeqNumber> > __sample;
 
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         if (__n < __ns[__i])
           __sample.push_back(std::make_pair(__S(__i)[__n], __i));
       __gnu_sequential::sort(__sample.begin(), __sample.end(),
                              __lcomp, sequential_tag());
 
       // Conceptual infinity.
-      for (int __i = 0; __i < __m; __i++)
+      for (_SeqNumber __i = 0; __i < __m; __i++)
         if (__n >= __ns[__i])
           __sample.push_back(
             std::make_pair(__S(__i)[0] /*__dummy element*/, __i));
 
       _DifferenceType __localrank = __rank / __l;
 
-      int __j;
+      _SeqNumber __j;
       for (__j = 0;
            __j < __localrank && ((__n + 1) <= __ns[__sample[__j].second]);
            ++__j)
@@ -478,7 +483,7 @@
           __n /= 2;
 
           const _Tp* __lmax = NULL;
-          for (int __i = 0; __i < __m; ++__i)
+          for (_SeqNumber __i = 0; __i < __m; ++__i)
             {
               if (__a[__i] > 0)
                 {
@@ -492,7 +497,7 @@
                 }
             }
 
-          int __i;
+          _SeqNumber __i;
           for (__i = 0; __i < __m; __i++)
             {
               _DifferenceType __middle = (__b[__i] + __a[__i]) / 2;
@@ -504,7 +509,7 @@
             }
 
           _DifferenceType __leftsize = 0;
-          for (int __i = 0; __i < __m; ++__i)
+          for (_SeqNumber __i = 0; __i < __m; ++__i)
               __leftsize += __a[__i] / (__n + 1);
 
           _DifferenceType __skew = __rank / (__n + 1) - __leftsize;
@@ -512,17 +517,18 @@
           if (__skew > 0)
             {
               // Move to the left, find smallest.
-              std::priority_queue<std::pair<_Tp, int>,
-                std::vector<std::pair<_Tp, int> >,
-                _LexicographicReverse<_Tp, int, _Compare> > __pq(__lrcomp);
+              std::priority_queue<std::pair<_Tp, _SeqNumber>,
+                std::vector<std::pair<_Tp, _SeqNumber> >,
+                _LexicographicReverse<_Tp, _SeqNumber, _Compare> >
+                  __pq(__lrcomp);
 
-              for (int __i = 0; __i < __m; ++__i)
+              for (_SeqNumber __i = 0; __i < __m; ++__i)
                 if (__b[__i] < __ns[__i])
                   __pq.push(std::make_pair(__S(__i)[__b[__i]], __i));
 
               for (; __skew != 0 && !__pq.empty(); --__skew)
                 {
-                  int __source = __pq.top().second;
+                  _SeqNumber __source = __pq.top().second;
                   __pq.pop();
 
                   __a[__source]
@@ -537,17 +543,17 @@
           else if (__skew < 0)
             {
               // Move to the right, find greatest.
-              std::priority_queue<std::pair<_Tp, int>,
-                std::vector<std::pair<_Tp, int> >,
-                _Lexicographic<_Tp, int, _Compare> > __pq(__lcomp);
+              std::priority_queue<std::pair<_Tp, _SeqNumber>,
+                std::vector<std::pair<_Tp, _SeqNumber> >,
+                _Lexicographic<_Tp, _SeqNumber, _Compare> > __pq(__lcomp);
 
-              for (int __i = 0; __i < __m; ++__i)
+              for (_SeqNumber __i = 0; __i < __m; ++__i)
                 if (__a[__i] > 0)
                   __pq.push(std::make_pair(__S(__i)[__a[__i] - 1], __i));
 
               for (; __skew != 0; ++__skew)
                 {
-                  int __source = __pq.top().second;
+                  _SeqNumber __source = __pq.top().second;
                   __pq.pop();
 
                   __a[__source] -= __n + 1;
@@ -573,7 +579,7 @@
 
       // Impossible to avoid the warning?
       _Tp __maxleft, __minright;
-      for (int __i = 0; __i < __m; ++__i)
+      for (_SeqNumber __i = 0; __i < __m; ++__i)
         {
           if (__a[__i] > 0)
             {
@@ -617,7 +623,7 @@
           // We have to calculate an offset.
           __offset = 0;
 
-          for (int __i = 0; __i < __m; ++__i)
+          for (_SeqNumber __i = 0; __i < __m; ++__i)
             {
               _DifferenceType lb
                 = std::lower_bound(__S(__i), __S(__i) + __ns[__i],
Index: include/parallel/base.h
===================================================================
--- include/parallel/base.h (revision 154027)
+++ include/parallel/base.h (working copy)
@@ -81,10 +81,10 @@
   // the OpenMP runtime unless the parallel mode is actually invoked
   // and active, which imples that the OpenMP runtime is actually
   // going to be linked in.
-  inline int
+  inline _ThreadIndex
   __get_max_threads()
   {
-    int __i = omp_get_max_threads();
+    _ThreadIndex __i = omp_get_max_threads();
     return __i > 1 ? __i : 1;
   }
 
Index: include/parallel/balanced_quicksort.h
===================================================================
--- include/parallel/balanced_quicksort.h (revision 154027)
+++ include/parallel/balanced_quicksort.h (working copy)
@@ -245,7 +245,7 @@
   template<typename _RAIter, typename _Compare>
     void
     __qsb_local_sort_with_helping(_QSBThreadLocal<_RAIter>** __tls,
-  _Compare& __comp, int __iam, bool __wait)
+  _Compare& __comp, _ThreadIndex __iam, bool __wait)
     {
       typedef std::iterator_traits<_RAIter> _TraitsType;
       typedef typename _TraitsType::value_type _ValueType;
@@ -460,7 +460,7 @@
       // 2. The largest range has at most length __n
       // 3. Each range is larger than half of the range remaining
       volatile _DifferenceType __elements_leftover = __n;
-      for (int __i = 0; __i < __num_threads; ++__i)
+      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
  {
           __tls[__i]->_M_elements_leftover = &__elements_leftover;
           __tls[__i]->_M_num_threads = __num_threads;
@@ -477,12 +477,12 @@
 #if _GLIBCXX_ASSERTIONS
       // All stack must be empty.
       _Piece __dummy;
-      for (int __i = 1; __i < __num_threads; ++__i)
+      for (_ThreadIndex __i = 1; __i < __num_threads; ++__i)
  _GLIBCXX_PARALLEL_ASSERT(
           !__tls[__i]->_M_leftover_parts.pop_back(__dummy));
 #endif
 
-      for (int __i = 0; __i < __num_threads; ++__i)
+      for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
  delete __tls[__i];
       delete[] __tls;
     }
Index: include/parallel/set_operations.h
===================================================================
--- include/parallel/set_operations.h (revision 154027)
+++ include/parallel/set_operations.h (working copy)
@@ -444,7 +444,7 @@
  if (__iam == 0)
   {
     // Do the last block.
-    for (int __i = 0; __i < __num_threads; ++__i)
+    for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
       __r += __lengths[__i];
 
     __block_begin = __block_begins[__num_threads];
@@ -457,7 +457,7 @@
   }
           else
             {
-              for (int __i = 0; __i < __iam; ++__i)
+              for (_ThreadIndex __i = 0; __i < __iam; ++__i)
          __r += __lengths[ __i ];
 
               // Reset begins for copy pass.
Index: include/parallel/unique_copy.h
===================================================================
--- include/parallel/unique_copy.h (revision 154027)
+++ include/parallel/unique_copy.h (working copy)
@@ -129,7 +129,7 @@
 
  if (__iam == 0)
           {
-            for (int __t = 0; __t < __num_threads; ++__t)
+            for (_ThreadIndex __t = 0; __t < __num_threads; ++__t)
               __begin_output += __counter[__t];
 
             __i = 0;
@@ -154,7 +154,7 @@
           }
  else
           {
-            for (int __t = 0; __t < __iam; __t++)
+            for (_ThreadIndex __t = 0; __t < __iam; __t++)
               __begin_output += __counter[__t];
 
             _OutputIterator __iter_out = __result + __begin_output;
@@ -168,7 +168,7 @@
       }
 
       _DifferenceType __end_output = 0;
-      for (int __t = 0; __t < __num_threads + 1; __t++)
+      for (_ThreadIndex __t = 0; __t < __num_threads + 1; __t++)
  __end_output += __counter[__t];
 
       delete[] __borders;
Index: include/parallel/multiway_mergesort.h
===================================================================
--- include/parallel/multiway_mergesort.h (revision 154027)
+++ include/parallel/multiway_mergesort.h (working copy)
@@ -154,7 +154,7 @@
      __sd->_M_starts[__iam + 1], __offsets.begin(),
      __comp);
 
- for (int __seq = 0; __seq < __sd->_M_num_threads; __seq++)
+ for (_ThreadIndex __seq = 0; __seq < __sd->_M_num_threads; __seq++)
   {
     // for each sequence
     if (__iam < (__sd->_M_num_threads - 1))
@@ -361,7 +361,7 @@
         _SeqVector;
       _SeqVector __seqs(__sd->_M_num_threads);
 
-      for (int __s = 0; __s < __sd->_M_num_threads; ++__s)
+      for (_ThreadIndex __s = 0; __s < __sd->_M_num_threads; ++__s)
  {
   __seqs[__s] =
     std::make_pair(__sd->_M_temporary[__s]
@@ -439,14 +439,14 @@
   __sd._M_offsets = new _DifferenceType[__num_threads - 1];
   __sd._M_pieces
     = new std::vector<_Piece<_DifferenceType> >[__num_threads];
-  for (int __s = 0; __s < __num_threads; ++__s)
+  for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
     __sd._M_pieces[__s].resize(__num_threads);
   __starts = __sd._M_starts = new _DifferenceType[__num_threads + 1];
 
   _DifferenceType __chunk_length = __n / __num_threads;
   _DifferenceType __split = __n % __num_threads;
   _DifferenceType __pos = 0;
-  for (int __i = 0; __i < __num_threads; ++__i)
+  for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)
     {
       __starts[__i] = __pos;
       __pos += ((__i < __split)
Index: include/parallel/partition.h
===================================================================
--- include/parallel/partition.h (revision 154027)
+++ include/parallel/partition.h (working copy)
@@ -103,7 +103,7 @@
  _DifferenceType __num_chunks = ((__right - __left + 1)
  / __chunk_size);
 
- for (int __r = 0; __r < __num_threads; ++__r)
+ for (_ThreadIndex __r = 0; __r < __num_threads; ++__r)
   {
     __reserved_left[__r] = false;
     __reserved_right[__r] = false;
@@ -222,7 +222,7 @@
   // Find spot and swap.
   _DifferenceType __swapstart = -1;
   omp_set_lock(&__result_lock);
-  for (int __r = 0; __r < __leftover_left; ++__r)
+  for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
     if (!__reserved_left[__r])
       {
  __reserved_left[__r] = true;
@@ -247,7 +247,7 @@
   // Find spot and swap
   _DifferenceType __swapstart = -1;
   omp_set_lock(&__result_lock);
-  for (int __r = 0; __r < __leftover_right; ++__r)
+  for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
     if (!__reserved_right[__r])
       {
  __reserved_right[__r] = true;
@@ -269,9 +269,9 @@
 
 #             pragma omp single
       {
- for (int __r = 0; __r < __leftover_left; ++__r)
+ for (_DifferenceType __r = 0; __r < __leftover_left; ++__r)
   _GLIBCXX_PARALLEL_ASSERT(__reserved_left[__r]);
- for (int __r = 0; __r < __leftover_right; ++__r)
+ for (_DifferenceType __r = 0; __r < __leftover_right; ++__r)
   _GLIBCXX_PARALLEL_ASSERT(__reserved_right[__r]);
       }
 
Index: include/parallel/partial_sum.h
===================================================================
--- include/parallel/partial_sum.h (revision 154027)
+++ include/parallel/partial_sum.h (working copy)
@@ -132,7 +132,7 @@
  / ((double)__num_threads + __s.partial_sum_dilation)),
  __borderstart = __n - __num_threads * __chunk_length;
       __borders[0] = 0;
-      for (int __i = 1; __i < (__num_threads + 1); ++__i)
+      for (_ThreadIndex __i = 1; __i < (__num_threads + 1); ++__i)
  {
   __borders[__i] = __borderstart;
   __borderstart += __chunk_length;

[Paolo Carlini-3]

Hi,
> The attached patch should get rid of most hard-coded occurrences of int.
>  
Excellent.
> Tested x86_64-unknown-linux-gnu: No regressions
>
> Please approve for mainline.
>  
Could you please double check for me that the use of _SeqNumber instead
of int, etc, didn't produce overlong lines? Please, don't let me go
through again boring formatting issues ;)

Thanks,
Paolo.

[Paolo Carlini-3]

Paolo Carlini wrote:
> Could you please double check for me that the use of _SeqNumber instead
> of int, etc, didn't produce overlong lines? Please, don't let me go
> through again boring formatting issues ;)
>  
I spotted only one in balanced_quicksort.h, fixed it and committed.

Thanks again,
Paolo.