{'fraction_non_alphanumeric': 0.03414302700866315, 'fraction_numerical': 0.010056055715984372, 'mean_word_length': 4.242386464826358, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Using parallelism techniques to improve sequential and multi-core sorting performance

We propose new sequential sorting operations by adapting techniques and methods used for designing parallel sorting algorithms. Although the norm is to parallelize a sequential algorithm to improve performance, we adapt a contrarian approach: we employ parallel computing techniques to speed up sequential sorting. Our methods can also work for multi-core sorting with minor adjustments that do not necessarily require full parallelization of the original sequential algorithm. The proposed approach leads to the development of asymptotically efficient deterministic and randomized sorting operations whose practical sequential and multi-core performance, as witnessed by an experimental study, matches or surpasses existing optimized sorting algorithm implementations. We utilize parallel sorting techniques such as deterministic regular sampling and random oversampling. We extend the notion of deterministic regular sampling into deterministic regular oversampling for sequential and multi-core sorting and demonstrate its potential. We then show how these techniques can be used for sequential sorting and also lead to better multi-core sorting algorithm performance as witnessed by the undertaken experimental study.


Introduction
Comparison-based sequential (or serial) sorting is a computational problem for which software libraries provide generic optimized implementations that are stable and/or can sort in-place. For the remainder, stable sorting is to mean that equally valued keys retain in the output their relative input order, and sorting is in-place if the same space is used to store the input and the output and all other extra space used is constant relative to the number of keys to be sorted. Examples of such software library-based sorting implementations include qsort available through the C Standard Library, or the sort and stable sort variants available in the C++ Standard Template Library.
The problem of sorting keys in parallel has also been studied extensively. One major requirement in parallel algorithm design is the minimization of interprocessor communication that reduces non-computational overhead and thus speeds up parallel running time. In order to shorten communication several techniques are employed that allow coarse (eg. several consecutive keys at a time) rather than fine-grained (eg. few individual keys) communication. Coarse-grained communication usually takes advantage of locality of reference as well. In parallel sorting, if one wants to sort n keys in parallel using p processors, one obvious way to achieve this is to somehow split the n keys into p sequences of approximately the same size and then sort these p sequences independently and in parallel using a fast sequential algorithm so that the concatenation (as opposed to merging) of the p sorted sequences would generate the sorted output.
For p = 2 this essentially becomes quicksort [11]. Generating p sequences of approximately the same size is not straightforward, whether p = 2 or p > 2. One way to effect a p-way splitting as used by [2] for external memory sequential sorting is to pick a random sample of p − 1 keys and use them as splitters (i.e. pivot keys). This is easy to implement but not very effective in making sure that the p resulting sequences effected by the p − 1 splitters are balanced in size [2]. Key sampling employed in parallel sorting has been studied in [12,14,15] that provide algorithms with satisfactory and scalable theoretical performance. Using the technique of random oversampling, fully developed and refined in the context of parallel sorting [12,15,14], one can pick the p − 1 splitters by using a sample of ps − 1 keys where s is the random oversampling factor. After sorting the sample of size ps − 1, one can then identify the p − 1 splitters as equidistant keys in the sorted sample.
One can trace the technique of random oversampling to original quicksort [11]. Quicksort allows for a variety of choices for the splitter (pivot) key: first, last, or middle. Other choices can be the median of those three keys, or in general, the median of 2t + 1 sample keys [11], for some choice of t. The median of three or 2t + 1 sample keys is an early instance of the use of the technique of oversampling in splitter selection: draw a larger sample from the input to pick a better (or more reliable) candidate from it as the splitter.
In [14] it is shown that the p subsequences of the n input keys induced by the p − 1 splitters resulting from random oversampling will retain with high probability O(n/p) keys each and will thus be balanced in size up to multiplicative constant factors. In [3], it is shown that by fine-tuning and carefully regulating the oversampling factor s, the p sequences will retain with high probability (1 + ǫ)n/p keys and will thus be more finely balanced. Parameter 0 < ǫ < 1 is a parameter that is controlled by s. The bounds on processor imbalance during sorting are tighter than those of any other random sampling or oversampling algorithm [12,2,14,15].
Thus if one was to extend say a traditional quick-sort method to use oversampling, one would need to add more steps or phases to the sorting operation. These would include a sample selection phase, a sample-sort phase, a splitter selection phase, followed by a phase that splits the input keys around the chosen splitters. Then the split keys are to be sorted either recursively by this same extended method or by the traditional quick-sort method.
In this work we propose a sample-based randomized sorting operation SqRan that does not follow this traditional pattern of sample and splitter selection but instead follows the pattern of deterministic regular sampling [16] and in particular deterministic regular oversampling [4] (to be described shortly), that are developed in the context of parallel sorting [16]. In such an approach key sorting precedes sample and splitter selection similarly to multi-way merging [13], followed at the end by a multi-way merging that is less locality-sensitive.
Deterministic regular sampling [16] works as follows. First split regularly and evenly n input keys into p sequences of equal size (the first n/p or so keys become part of the first sequence, the next n/p keys part of the second and so on). Sort the p sequences independently, and then pick from each sequence p − 1 sample (and equidistant) keys for a total sample of size p(p − 1). A sorting (or multi-way merging) of these sample keys can be followed by the selection of p − 1 equidistant splitters from the sorted sample. One can then prove that if the n keys are split around the p − 1 splitters, then none of the p resulting sequences will be of size more than 2n/p [16]. In [4,5,6] the notion of regular sampling is extended to include oversampling thus giving rise to deterministic regular oversampling. In that context choosing a larger sample p(p − 1)s deterministically, with s being now the regular oversampling factor, one can claim that each one of the p sequences split by the p − 1 splitters is of size no more than (1 + δ)n/p, where δ > 0 also depends on the choice of s.
Randomized oversampling-based sorting is supposed to be superior to deterministic regular sampling or oversampling-based sorting as the regular oversampling factor s can not be finelytuned as much as the random oversampling factor s [4,5].
In this work we introduce a template for sequential sorting using as basis the deterministic sorting algorithm introduced in [4,5,6]. We "deparallelize" a parallel deterministic sorting algorithm that uses regular oversampling by converting it into a sequential algorithm. Local (to a processor) simultaneous sorting can be done by a single processor in turn using any fast and available sorting implementation which can include qsort, sort, stable sort and we shall call it SomeSort generically. The deterministic sorting operation that results will be called SqDet depicted in Algorithm 1. If instead of regular oversampling a random oversampling is employed, but otherwise the steps remained the same, the same template could be used for a randomized sorting operation to be called similarly SqRan and depicted in Algorithm 2. Therefore the same template can be be used for SqDet and SqRan except that in the former case deterministic regular oversampling is used [4,5,6], and in the latter case random oversampling is used in a way that deviates from the traditional approach of [12,14,3], where sampling precedes key sorting.
Since both operations SqDet and SqRan are sequential, the choice of p is not controlled by the number of available processors or cores. The choice of p will primarily be affected by other characteristics of the host architecture such as multiple memory hierarchies (eg. cache memory) that affect locality of reference. The existence of multiple cores can also affect the choice of p. In our discussion to follow for the case of multi-core sorting we shall introduce parameter m to be the number of available cores. In general, we shall assume that p ≥ m.
Even though SqDet and SqRan look similar, random oversampling is provably theoretically better than deterministic regular oversampling. The oversampling parameter in SqRan can vary more widely than in SqDet thus resulting in more balanced work-load during the multi-way merging phase that takes into more advantage locality of reference issues (eg. cache memory).
In the following section we first introduce SqDet and analyze its performance characteristics and then show how one can slightly modify the sampling phase of it to generate operation SqRan .

Operation SqDet
The proposed operation SqDet is depicted in Algorithm 1 and is based on a non-iterative variant of the bulk-synchronous [17,18] parallel sorting algorithm of [4,5]. It is deterministic regular sampling based [16] but also extends regular sampling to deterministic regular oversampling and thus utilizes an efficient partitioning scheme that splits -almost evenly and independently of the input distribution -an arbitrary number of sorted sequences and deals with them independently of each other. In Section 2.2 this baseline template operation is augmented to handle transparently and in optimal asymptotic efficiency duplicate keys. In our approach duplicate handling does not require doubling of computation time, excessive increase of space requirements (or in the context of parallel computing, communication time as well) that other regular sampling/oversampling approaches, sequential or parallel, seem to require [8,9,10].
Algorithm 1 describes operation SqDet (X, n, p, SomeSort ). X denotes the input sequence and n the number of keys of X. Sorting in SqDet is performed by the supplied SomeSort function.
Algorithm 1 SqDet (X, n, p, SomeSort ) {sort n keys of X; utilize SomeSort for sorting } 1: BaselineSorting. The n input keys are regularly and evenly split into p sequences each one of size approximately n/p. Each sequence is then sorted by SomeSort . Let X k , 0 ≤ k ≤ p − 1, be the k-th sequence after sorting.
2: Partitioning: Sample Selection. Let r = ⌈ω n ⌉ and s = rp. Form locally a sample T k from the sorted X k . The sample consists of rp − 1 evenly spaced keys of X k that partition it into rp evenly sized segments; append the maximum of the sorted X k (i.e. the last key) into T k so that the latter gets rp keys. Merge all T k into a sorted sequence T of rp 2 keys.
3: Partitioning: Splitter Selection. Form the splitter sequence S that contains the (i · s)-th 4: Partitioning: Split input keys. Then split the sorted X k around S into sorted subse- Thus SqDet serves as a template for performing sorting that can utilize highly-optimized existing (software library) sorting algorithms. The parameter p is user-specified and denotes the number of sequences input X will be split into; naturally, a wrapper function of SqDet can set the value of p to some specific value depending on the available processor architecture. One can thus vary p in ways that will take full advantage of multiple memory hierarchies or the underlying processor architecture whose behavior and characteristics might not be easily understood by the average programmer/user.
Within SqDet parameter s is the regular oversampling factor whose value is regulated through the choice of ω n that also affects r. Function ω n could have been included in the parameter list of SqDet . However, because it is a function of n its value can be set permanently through n inside SqDet after some initial calibration/benchmarking. The theorem and proof that follow simplify the results shown in a more general context in [4,5]. Operation SqDet in Algorithm 1 corresponds to the simplest case of the deterministic algorithm in [5] where an analysis for all possible values of processor size versus problem size is presented.
Theorem 1 For any n and p ≤ n, and any function ω n of n such that ω n = Ω(1), ω n = O(lg n) and p 2 ω 2 n = o(n), operation SqDet requires time An lg (n/p) + Bn lg p + o(n lg n), if SomeSort requires An lg n time to sort n keys and it takes Bn lg p time to merge n keys of p sorted sequences, for some constants A, B ≥ 1.
Proof: The input sequence is split arbitrarily into p sequences of about the same size (plus or minus one key). This is step 1 of SqDet . Moreover, the keys are distinct since in an extreme case, we can always make them so by, for example, appending to them the code for their memory location. We later explain how we handle duplicate keys without doubling (in the worst case) the number of comparisons performed. Parameter r determines the desired upper bound in key imbalance of the p sorted sequences Y k that will form the output. The term 1 + 1/r = 1 + 1/⌈ω n ⌉ that will characterize such an imbalance is also referred to as bucket expansion in sampling based randomized sorting algorithms [1].
Note. In the discussion to follow we track constant values for key sorting and multi-way merging but use asymptotic notation for other low-order term operations.
In step 1, each one of the p sequences is sorted independently of each other using SomeSort . As each such sequence is of size at most ⌈n/p⌉, this step requires time A⌈n/p⌉ lg ⌈n/p⌉ per sequence or a total of Ap⌈n/p⌉ lg ⌈n/p⌉. Algorithm SomeSort is any sequential sorting algorithm of such performance. The overall cost of this step is An lg (n/p) + O(p lg n).
Subsequently, within each sorted subsequence X k , ⌈ω n ⌉p − 1 = rp − 1 evenly spaced sample keys are selected, that partition the corresponding sequence into rp evenly sized segments. Additionally, the largest key of each sequence is appended to T k . Let s = rp be the size of the so identified sequence T k .
Step i.e. Bps lg p = Bp 2 r lg p. In step 3, a sequence S of evenly spaced splitters is formed from the sorted sample by picking as splitters keys t is , 1 ≤ i < p. This step takes time O(p).
Step 4 splits X k around the sample keys in S. Each one of the p sorted sequences decides the position of every key it holds with respect to the p − 1 splitters by way of sequential merging the p − 1 splitters of S with the input keys of X k in p − 1 + n/p time per sequence. Alternately this can be achieved by performing a binary search of the splitters into the sorted keys in time p lg (n/p), and subsequently counting the number of keys that fall into each one of the p so identified subsequences induced by the p − 1 splitters. The overall running time of this step over all p sequences is thus O(p 2 + n) if merging is performed or p 2 lg (n/p) if binary search is performed.
In step 4, X k,j is the j-th sorted subsequence of X k induced by S. This subsequence will become part of the Y j -th output sequence in step 5. In step 5, p output sequences Y j are formed that will eventually be concatenated. Each such output sequence Y j is formed from the at most p sorted subsequences X k,j for all k, formed in step 4. When this step is executed, by way of Lemma 1 to be shown next, each Y j will comprise of at most p = min {p, n max } sorted subsequences X k,j for a total of at most n max keys for Y j , and n keys for Y , where n max = (1 + 1/⌈ω n ⌉)(n/p) + ⌈ω n ⌉p. The cost of this step is that of multi-way merging n keys by some deterministic algorithm [13], which is Bn lg p, as long as ω 2 n p = O(n/p), as needed by Lemma 1 to follow.
BaselineSorting and Merging thus contribute An lg (n/p) + O(p lg n) and Bn lg p respectively. Sample selection and sample-sorting contributions amount to O(p 2 r lg p).
Step 4 contribu- . Summing up all these computation terms we get that the total runtime is An lg (n/p)+Bn lg p+O(p 2 r lg n+n). If p 2 r = o(n), this is An lg n+(A−B)n lg p+ o(n lg n). Note that in the statement of the theorem we use a stronger condition p 2 r 2 = p 2 ω 2 n = o(n) for Lemma 1 to be applicable.
It remains to show that at the completion of step 4 the input keys are partitioned into (almost) evenly sized subsequences. The main result is summarized in the following lemma.

Lemma 1
The maximum number of keys n max per output sequence Y j in SqDet is given by (1 + 1/⌈ω n ⌉)(n/p) + ⌈ω n ⌉p, for any ω n such that ω n = Ω(1) and ω n = O(lg n), provided that Proof: Although it is not explicitly mentioned in the description of algorithm SqDet we may assume that we initially pad the input so that each sequence has exactly ⌈n/p⌉ keys. At most one key is added to each sequence (the maximum key can be such a choice). Before performing the sample selection operation, we also pad the input so that afterwards, all segments have the same number of keys that is, x = ⌈⌈n/p⌉/s⌉. The padding operation requires time at most O(s), which is within the lower order terms of the analysis of Theorem 1, and therefore, does not affect the asymptotic complexity of the algorithm. We note that padding operations introduce duplicate keys; a discussion of duplicate handling follows this proof.
Consider an arbitrary splitter t is , where 1 ≤ i < p. There are at least isx keys which are not larger than s is , since there are is segments each of size x whose keys are not larger than s is .
Likewise, there are at least (ps − is − p + 1)x keys which are not smaller than s is , since there are ps − is − p + 1 segments each of size x whose keys are not smaller than s is . Thus, by noting that the total number of keys has been increased (by way of padding operations) from n to psx, the number of keys b i that are smaller than s is is bounded as follows.
A similar bound can be obtained for b i+1 . Substituting s = ⌈ω n ⌉p we therefore conclude the following.
The difference n i = b i+1 − b i is independent of i and gives the maximum number of keys per split sequence. Considering that x ≤ (n + ps)/(ps) and substituting s = ⌈ω n ⌉p, the following bound is derived.
By substituting in the numerator of the previous expression s = ⌈ω n ⌉p, we conclude that the maximum number of keys n max per output sequence of SqDet is bounded above as follows.
The lemma follows.

Duplicate-key Handling
Algorithm SqDet , as described, does not handle duplicate keys properly. A naive way to handle duplicate keys is by making the keys distinct. This could be achieved by attaching to each key the address of the memory location it is stored in. For data types whose bit or byte size is comparable to the size of the address describing them, such a transformation leads -in most cases -to a doubling of the overall number of comparisons performed and the communication time in the worst case. For more complex data types such as strings of characters the extra cost may be negligible.
An alternative way to handle duplicate keys in a transparent way that provides asymptotic optimal efficiency and tags only a small fraction of the keys is the following one. This seems to be an improvement over other approaches [8,9,10] that require "doubling" (as explained earlier.) Procedure SomeSort must then be implemented by means of a stable sequential sorting algorithm as well. Two tags for each input key are already implicitly available by default, and no extra memory is required to access them. These are the sequence identifier that stores a particular input key and the index of the key in the local array that stores that sequence. No additional space is required for the maintenance of this tagging. In our duplicate-key handling method such tags are only used for sample and splitter-related activity.
For sample sorting every sample key is augmented into a record that includes this additional tag information (array index and sequence identifier storing the key). Since sample size is o(1) of the input keys, the memory overhead incurred is small, as is the corresponding computational overhead.
The attached tag information is used in step 2 to form the sample and in sample sorting/merging and then in splitter selection, and finally in step 4, as all these steps require distinct keys to achieve stability. In step 4 in particular, a binary search operation of a splitter key into the locally sorted keys involves first a comparison of the two keys, and if the comparison is not resolved that way the use of sequence identifiers or array indexes as well. If merging is used instead, a similar resolution applies. In the multi-way merging of the Merging phase, stability is resolved by the merging algorithm itself. The computation overhead of duplicate handling that is described by this method is within the lower order terms of the analysis and therefore, the optimality claims still hold unchanged. The results on key imbalance still hold as well. This same duplicate handling method is also used in SqRan .

Operation SqRan
In this section we show how to modify SqDet to form randomized operation SqRan . Random oversampling-based algorithms in the traditional approach of [12,15,14,3] do not involve a Base-lineSorting phase that thus distinguishes SqDet and SqRan from other similar approaches.
Algorithm 2 SqRan (X, n, p, SomeSort ) {sort n keys of X; utilize SomeSort for sorting } 1: BaselineSorting. The n input keys are regularly and evenly split into p sequences each one of size approximately n/p. Each sequence is then sorted by SomeSort . Let X k , 0 ≤ k ≤ p − 1, be the k-th sequence after sorting. 4: Partitioning: Split input keys. Split the sorted X k around S into sorted subsequences Although partitioning and oversampling in the context of sorting are well established techniques [12,15,14], the analysis in [3] summarized in Claim 1 below allows one to quantify precisely the key imbalance of the output sequences Y j . Let X = x 1 , x 2 , . . . , x n be an ordered sequence of keys indexed such that x i < x i+1 , for all 1 ≤ i ≤ n − 1. The implicit assumption is that keys are unique.
Let Y = {y 1 , y 2 , . . . , y ps−1 } be a randomly chosen subset of ps − 1 ≤ n keys of X also indexed such that y i < y i+1 , for all 1 ≤ i ≤ ps − 2, for some positive integers p and s. Having randomly selected set Y , a partitioning of X − Y into p subsets, X 0 , X 1 , . . . , X p−1 takes place. The following result shown in [3] is independent of the distribution of the input keys.
Then the probability that any one of the X i , for all i, 0 ≤ i ≤ p − 1, is of size more than ⌈(1 + ε)(n − p + 1)/p⌉ is at most n −ρ .
In such traditional randomized algorithms that use oversampling the complexity of splitting keys around the splitters is inconsequential. For each input key a binary search operation on the p − 1 splitters determines the position of that input key in one of the p output sequences that will be formed and then sorted. This is much more involved than say step 4 of SqDet that can involve a binary search of the p − 1 splitters into each one of the p sorted sequences of approximately n/p keys, an operation that has better locality of reference. Operation

Multi-core adaptations
We perform a minimal and straightforward modification that involves minimal parallelization: the adaptation of step 1 and potentially step 5 for multi-core and other parallel architectures. In the experimental study of the following section, only step 1 of McRan was thus modified to take advantage of multi-core architectures. If a processor with m cores is available, the p sorting operations of step 1 (BaselineSorting) can be distributed evenly among the m cores. The contribution to the runtime of this would be (An/m) lg (n/p). Similarly for step 5 we would get a time reduction to (Bn/m) lg p. For all these claims to hold we must have that m ≤ p and p should also be a multiple of m. Thus the runtime of Theorem 2 or Theorem 1 can be reduced by a multiplicative factor m As we have already mentioned the multi-core implementation of the experimental study forfeits the parallelization of step 5. As a result its runtime is expected to behave according to the expression (An/m) lg (n/p) + Bn lg p, where low-order terms are not shown. In fact it is written so that it can spawn a number of threads t which can be higher than the number of available cores.

Experimental Study
Operations SqDet and SqRan developed under this work have been implemented in ANSI C and their performance studied for a variety of SomeSort functions with the intent to verify whether the theoretical analysis can be verified in practice. Moreover, McRan , the version or SqRan that takes advantage of multi-core architectures as described in the previous section was also implemented.
The resulting source code is publically available through the author's web-page [7].  Table 2, we vary s by using parameter a defined as s = log 1+a n.
This is equivalent to choosing ω n ≈ log a/2 n. For such a definition of a, values of a running between 0.2 and 1.8 in increments of 0.4 are being used in the timing data reported. For SqDet sample size is regulated by parameter r = ω n and we choose it be a small integer in the range 1-5.
In Table 1 timing results for SqRan are reported, where SomeSort is each one of qs, hs, rq and the default s, as specified earlier, is used. We observe that even for the smallest problem size, and the most time-efficient SomeSort (i.e. qsort) operation SqRan offers better (though marginally) performance than standalone qsort. For increasing problem sizes, the best savings occur for increasing values of p, up to a point that makes sample size which is dependent on p a contributing factor. One can potentially extract better performance out of SqRan by fine-tuning p and s to values other that the ones chosen. A smaller sample size that is a fraction of the theoretically chosen one can speed things up as well. This is shown in Table 2 where for a fixed problem size of n = 8192000 the 2.74 or so running time of qs is bested not by the default s (implied by a = 1.0) but by a slight smaller s obtained for a = 0.2 or a = 0.4. Such savings however are marginal and thus using the default value for s is satisfactory enough. For hs or rq the use of SqRan improves upon the standalone use of hs or rq by 30% or more and 15% or more respectively.
In Table 3 and Table 4 Table 3 is higher and can reach 4 or so for the former and 2.9 for the latter. Note that using a quick-sort based algorithm (qs or rq) for SomeSort in a multi-threaded/multi-core set-up, best performance is obtained for p = 4 i.e. for a value equal to the number of cores. This has to do with the inherent values of A and B of Theorem 2 for qs, hs, rq. Note that the architecture used for the experimental study is a quad-core processor that supports up to 8 threads (two per core) in hardware. Thus we have been able to run McRan using 8 threads so that we can take full advantage of the underlying hardware support. As it is evident from Table 4 further improvement in performance is possible and overall execution times are lower for all problem sizes and choices of the SomeSort function. Moreover Table 5 and Table 6 confirm our previous findings: varying sample size can improve performance but only slightly relative to the default value used.
Overall, all three choices of SomeSort can benefit from the use of our proposed operation SqRan .
The benefits are modest and marginal for qs and maximized for the slowest of our implementation.
However when the multi-core version of our proposed operation is employed i.e. McRan , that uses just a marginal and "naive" parallelization (eg assignment of BaselineSorting tasks to different threadsc/cores), savings can be significant and speed up in performance by a factor of 1.5 to 2.5 is possible even for the system's qsort implementation. Thus employing our proposed sorting operation McRan and using in it qsort for SomeSort can lead to two-fold to three-fold increase in performance relative to using the standalone qsort function.
Finally Table 7 and Table 8 present some experimental results related to operation SqDet .   Table 1 are slightly better than those of SqDet consistently as they should be.
For the small problem size, it is possible that the regularity of the sample in SqDet affects overall performance marginally. The imbalance of the sizes of sequences Y j in step 5 of SqDet are indeed higher than those of SqRan for the value of r = 1 used in Table 7 and the default s of Table 1 . Note that in the former case the imbalance as controlled by ω n is r = ⌈omega n ⌉ and r = 1. For Table 1,        Table 8: SqDet : varying sample parameters r and p for n = 8192000