Order Preservation in PLINQ

Artikkeli
09/15/2021

In PLINQ, the goal is to maximize performance while maintaining correctness. A query should run as fast as possible but still produce the correct results. In some cases, correctness requires the order of the source sequence to be preserved; however, ordering can be computationally expensive. Therefore, by default, PLINQ does not preserve the order of the source sequence. In this regard, PLINQ resembles LINQ to SQL, but is unlike LINQ to Objects, which does preserve ordering.

To override the default behavior, you can turn on order-preservation by using the AsOrdered operator on the source sequence. You can then turn off order preservation later in the query by using the AsUnordered method. With both methods, the query is processed based on the heuristics that determine whether to execute the query as parallel or as sequential. For more information, see Understanding Speedup in PLINQ.

The following example shows an unordered parallel query that filters for all the elements that match a condition, without trying to order the results in any way.

var cityQuery =
    (from city in cities.AsParallel()
     where city.Population > 10000
     select city).Take(1000);

Dim cityQuery = From city In cities.AsParallel()
                Where city.Population > 10000
                Take (1000)

This query does not necessarily produce the first 1000 cities in the source sequence that meet the condition, but rather some set of 1000 cities that meet the condition. PLINQ query operators partition the source sequence into multiple subsequences that are processed as concurrent tasks. If order preservation is not specified, the results from each partition are handed off to the next stage of the query in an arbitrary order. Also, a partition may yield a subset of its results before it continues to process the remaining elements. The resulting order may be different every time. Your application cannot control this because it depends on how the operating system schedules the threads.

The following example overrides the default behavior by using the AsOrdered operator on the source sequence. This ensures that the Take method returns the first 1000 cities in the source sequence that meet the condition.

var orderedCities =
    (from city in cities.AsParallel().AsOrdered()
     where city.Population > 10000
     select city).Take(1000);

Dim orderedCities = From city In cities.AsParallel().AsOrdered()
                    Where city.Population > 10000
                    Take (1000)

However, this query probably does not run as fast as the unordered version because it must keep track of the original ordering throughout the partitions and at merge time ensure that the ordering is consistent. Therefore, we recommend that you use AsOrdered only when it is required, and only for those parts of the query that require it. When order preservation is no longer required, use AsUnordered to turn it off. The following example achieves this by composing two queries.

var orderedCities2 =
    (from city in cities.AsParallel().AsOrdered()
     where city.Population > 10000
     select city).Take(1000);

var finalResult =
    from city in orderedCities2.AsUnordered()
    join p in people.AsParallel()
    on city.Name equals p.CityName into details
    from c in details
    select new
    {
        city.Name,
        Pop = city.Population,
        c.Mayor
    };

foreach (var city in finalResult) { /*...*/ }

Dim orderedCities2 = From city In cities.AsParallel().AsOrdered()
                     Where city.Population > 10000
                     Select city
                     Take (1000)

Dim finalResult = From city In orderedCities2.AsUnordered()
                  Join p In people.AsParallel() On city.Name Equals p.CityName
                  Select New With {.Name = city.Name, .Pop = city.Population, .Mayor = city.Mayor}

For Each city In finalResult
    Console.WriteLine(city.Name & ":" & city.Pop & ":" & city.Mayor)
Next

Note that PLINQ preserves the ordering of a sequence produced by order-imposing operators for the rest of the query. In other words, operators such as OrderBy and ThenBy are treated as if they were followed by a call to AsOrdered.

Query Operators and Ordering

The following query operators introduce order preservation into all subsequent operations in a query, or until AsUnordered is called:

The following PLINQ query operators may in some cases require ordered source sequences to produce correct results:

Some PLINQ query operators behave differently, depending on whether their source sequence is ordered or unordered. The following table lists these operators.

Operator	Result when the source sequence is ordered	Result when the source sequence is unordered
Aggregate	Nondeterministic output for nonassociative or noncommutative operations	Nondeterministic output for nonassociative or noncommutative operations
All	Not applicable	Not applicable
Any	Not applicable	Not applicable
AsEnumerable	Not applicable	Not applicable
Average	Nondeterministic output for nonassociative or noncommutative operations	Nondeterministic output for nonassociative or noncommutative operations
Cast	Ordered results	Unordered results
Concat	Ordered results	Unordered results
Count	Not applicable	Not applicable
DefaultIfEmpty	Not applicable	Not applicable
Distinct	Ordered results	Unordered results
ElementAt	Return specified element	Arbitrary element
ElementAtOrDefault	Return specified element	Arbitrary element
Except	Unordered results	Unordered results
First	Return specified element	Arbitrary element
FirstOrDefault	Return specified element	Arbitrary element
ForAll	Executes nondeterministically in parallel	Executes nondeterministically in parallel
GroupBy	Ordered results	Unordered results
GroupJoin	Ordered results	Unordered results
Intersect	Ordered results	Unordered results
Join	Ordered results	Unordered results
Last	Return specified element	Arbitrary element
LastOrDefault	Return specified element	Arbitrary element
LongCount	Not applicable	Not applicable
Min	Not applicable	Not applicable
OrderBy	Reorders the sequence	Starts new ordered section
OrderByDescending	Reorders the sequence	Starts new ordered section
Range	Not applicable (same default as AsParallel )	Not applicable
Repeat	Not applicable (same default as AsParallel)	Not applicable
Reverse	Reverses	Does nothing
Select	Ordered results	Unordered results
Select (indexed)	Ordered results	Unordered results.
SelectMany	Ordered results.	Unordered results
SelectMany (indexed)	Ordered results.	Unordered results.
SequenceEqual	Ordered comparison	Unordered comparison
Single	Not applicable	Not applicable
SingleOrDefault	Not applicable	Not applicable
Skip	Skips first n elements	Skips any n elements
SkipWhile	Ordered results.	Nondeterministic. Performs SkipWhile on the current arbitrary order
Sum	Nondeterministic output for nonassociative or noncommutative operations	Nondeterministic output for nonassociative or noncommutative operations
Take	Takes first `n` elements	Takes any `n` elements
TakeWhile	Ordered results	Nondeterministic. Performs TakeWhile on the current arbitrary order
ThenBy	Supplements `OrderBy`	Supplements `OrderBy`
ThenByDescending	Supplements `OrderBy`	Supplements `OrderBy`
ToArray	Ordered results	Unordered results
ToDictionary	Not applicable	Not applicable
ToList	Ordered results	Unordered results
ToLookup	Ordered results	Unordered results
Union	Ordered results	Unordered results
Where	Ordered results	Unordered results
Where (indexed)	Ordered results	Unordered results
Zip	Ordered results	Unordered results

Unordered results are not actively shuffled; they simply do not have any special ordering logic applied to them. In some cases, an unordered query may retain the ordering of the source sequence. For queries that use the indexed Select operator, PLINQ guarantees that the output elements will come out in the order of increasing indices, but makes no guarantees about which indices will be assigned to which elements.

Jaa

Order Preservation in PLINQ

Query Operators and Ordering

See also

Lisäresursseja