Partisi Kustom untuk PLINQ dan TPL

  • Artikel

Untuk menyejajarkan operasi pada sumber data, salah satu langkah pentingnya adalah mempartisi sumber ke dalam beberapa bagian yang dapat diakses secara bersamaan oleh beberapa utas. PLINQ dan Task Parallel Library (TPL) menyediakan partisi default yang bekerja secara transparan saat Anda menulis kueri atau perulangan paralel ForEach. Untuk skenario yang lebih canggih, Anda dapat menyambungkan partisi Anda sendiri.

Jenis Pemartisian

Ada banyak cara untuk mempartisi sumber data. Dalam pendekatan yang paling efisien, beberapa utas bekerja sama untuk memproses urutan sumber asli, daripada secara fisik memisahkan sumber menjadi beberapa suburutan. Untuk array dan sumber terindeks lainnya seperti kumpulan IList yang panjangnya diketahui sebelumnya, pemartisian rentang adalah jenis partisi yang paling sederhana. Setiap utas menerima indeks awal dan akhir yang unik, sehingga dapat memproses rentang sumbernya tanpa menimpa atau ditimpa oleh utas lain. Satu-satunya overhead yang terlibat dalam pemartisian rentang adalah pekerjaan awal pembuatan rentang; tidak ada sinkronisasi tambahan yang diperlukan setelah itu. Oleh karena itu, hal ini dapat memberikan performa yang baik selama beban kerja dibagi secara merata. Kerugian dari pemartisian rentang adalah bahwa jika satu utas selesai lebih awal, itu tidak dapat membantu utas lain menyelesaikan pekerjaan mereka.

Untuk daftar tertaut atau kumpulan lain yang panjangnya tidak diketahui, Anda dapat menggunakan pemartisian potongan. Dalam pemartisian potongan, setiap utas atau tugas dalam perulangan paralel atau kueri mengonsumsi beberapa elemen sumber dalam satu potongan, memprosesnya, dan kemudian kembali untuk mengambil elemen tambahan. Partisi memastikan bahwa semua elemen didistribusikan dan tidak ada duplikat. Potongan mungkin berukuran apa pun. Misalnya, pemartisi yang ditunjukkan dalam Cara: Menerapkan Partisi Dinamis membuat potongan yang hanya berisi satu elemen. Selama potongannya tidak terlalu besar, pemartisian semacam ini secara inheren menyeimbangkan beban karena penetapan elemen ke utas tidak ditentukan sebelumnya. Namun, partisi memang menimbulkan overhead sinkronisasi setiap kali utas perlu mendapatkan potongan lain. Jumlah sinkronisasi yang terjadi dalam kasus ini berbanding terbalik dengan ukuran potongan.

Secara umum, pemartisian rentang hanya lebih cepat ketika waktu eksekusi delegasi kecil hingga sedang, dan sumbernya memiliki sejumlah besar elemen, dan total pekerjaan setiap partisi kira-kira setara. Oleh karena itu, pemartisian potongan umumnya lebih cepat dalam banyak kasus. Pada sumber dengan sejumlah kecil elemen atau waktu eksekusi yang lebih lama untuk delegasi, maka performa pemartisian potongan dan rentang sekitar sama.

Partisi TPL juga mendukung jumlah partisi yang dinamis. Ini berarti mereka dapat membuat partisi dengan cepat, misalnya, ketika perulangan ForEach memunculkan tugas baru. Fitur ini memungkinkan partisi untuk menskalakan bersama dengan perulangan itu sendiri. Partisi dinamis juga secara inheren menyeimbangkan beban. Saat membuat partisi kustom, Anda harus mendukung partisi dinamis agar dapat dikonsumsi dari perulangan ForEach.

Mengonfigurasi Partisi Load Balancing untuk PLINQ

Beberapa overload metode Partitioner.Create memungkinkan Anda membuat partisi untuk array atau sumber IList dan menentukan apakah metode tersebut harus mencoba menyeimbangkan beban kerja di antara utas. Ketika partisi dikonfigurasi untuk menyeimbangkan beban, pemartisian potongan digunakan, dan elemen diserahkan ke setiap partisi dalam potongan kecil saat diminta. Pendekatan ini membantu memastikan bahwa semua partisi memiliki elemen untuk diproses hingga seluruh perulangan atau kueri selesai. Overload tambahan dapat digunakan untuk menyediakan partisi penyeimbangan beban dari sumber IEnumerable apa pun.

Secara umum, penyeimbangan beban mengharuskan partisi untuk meminta elemen yang relatif sering dari partisi. Sebaliknya, partisi yang melakukan partisi statis dapat menetapkan elemen ke setiap partisi sekaligus dengan menggunakan pemartisian rentang atau potongan. Ini membutuhkan lebih sedikit overhead daripada penyeimbangan beban, tetapi mungkin perlu waktu lebih lama untuk dieksekusi jika satu utas berakhir dengan pekerjaan yang jauh lebih banyak daripada yang lain. Secara default ketika melewati IList atau array, PLINQ selalu menggunakan partisi rentang tanpa penyeimbangan beban. Untuk mengaktifkan penyeimbangan beban untuk PLINQ, gunakan metode Partitioner.Create, seperti yang ditunjukkan dalam contoh berikut.

// Static partitioning requires indexable source. Load balancing
// can use any IEnumerable.
var nums = Enumerable.Range(0, 100000000).ToArray();

// Create a load-balancing partitioner. Or specify false for static partitioning.
Partitioner<int> customPartitioner = Partitioner.Create(nums, true);

// The partitioner is the query's data source.
var q = from x in customPartitioner.AsParallel()
        select x * Math.PI;

q.ForAll((x) =>
{
    ProcessData(x);
});

' Static number of partitions requires indexable source.
Dim nums = Enumerable.Range(0, 100000000).ToArray()

' Create a load-balancing partitioner. Or specify false For  Shared partitioning.
Dim customPartitioner = Partitioner.Create(nums, True)

' The partitioner is the query's data source.
Dim q = From x In customPartitioner.AsParallel()
        Select x * Math.PI

q.ForAll(Sub(x) ProcessData(x))

Cara terbaik untuk menentukan apakah akan menggunakan penyeimbangan beban dalam skenario tertentu adalah dengan bereksperimen dan mengukur berapa lama waktu yang dibutuhkan operasi untuk diselesaikan di bawah beban representatif dan konfigurasi komputer. Misalnya, partisi statis mungkin memberikan kecepatan yang signifikan pada komputer multiinti yang hanya memiliki beberapa inti, tetapi dapat mengakibatkan perlambatan pada komputer yang memiliki relatif banyak inti.

Tabel berikut mencantumkan overload metode Create yang tersedia. Partisi ini tidak terbatas hanya untuk digunakan dengan PLINQ atau Task. Mereka juga dapat digunakan dengan konstruksi paralel kustom apa pun.

Overload Menggunakan penyeimbangan beban
Create<TSource>(IEnumerable<TSource>) Selalu
Create<TSource>(TSource[], Boolean) Ketika argumen Boolean ditentukan sebagai true
Create<TSource>(IList<TSource>, Boolean) Ketika argumen Boolean ditentukan sebagai true
Create(Int32, Int32) Tidak pernah
Create(Int32, Int32, Int32) Tidak pernah
Create(Int64, Int64) Tidak pernah
Create(Int64, Int64, Int64) Tidak pernah

Mengonfigurasi Partisi Rentang Statis untuk Parallel.ForEach

Dalam perulangan For, isi perulangan disediakan untuk metode sebagai delegasi. Biaya pemanggilan yang mendelegasikan hampir sama dengan panggilan metode virtual. Dalam beberapa skenario, isi perulangan paralel mungkin cukup kecil sehingga biaya pemanggilan delegasi pada setiap iterasi perulangan menjadi signifikan. Dalam situasi seperti itu, Anda dapat menggunakan salah satu dari overload Create untuk membuat IEnumerable<T> partisi rentang di atas elemen sumber. Kemudian, Anda dapat meneruskan kumpulan rentang ini ke metode ForEach yang isinya terdiri dari loop for biasa. Manfaat dari pendekatan ini adalah bahwa biaya pemanggilan delegasi hanya dikeluarkan sekali per rentang, bukan sekali per elemen. Contoh berikut menunjukkan pola dasar berikut.

using System;
using System.Collections.Concurrent;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {

        // Source must be array or IList.
        var source = Enumerable.Range(0, 100000).ToArray();

        // Partition the entire source array.
        var rangePartitioner = Partitioner.Create(0, source.Length);

        double[] results = new double[source.Length];

        // Loop over the partitions in parallel.
        Parallel.ForEach(rangePartitioner, (range, loopState) =>
        {
            // Loop over each range element without a delegate invocation.
            for (int i = range.Item1; i < range.Item2; i++)
            {
                results[i] = source[i] * Math.PI;
            }
        });

        Console.WriteLine("Operation complete. Print results? y/n");
        char input = Console.ReadKey().KeyChar;
        if (input == 'y' || input == 'Y')
        {
            foreach(double d in results)
            {
                Console.Write("{0} ", d);
            }
        }
    }
}

Imports System.Threading.Tasks
Imports System.Collections.Concurrent

Module PartitionDemo

    Sub Main()
        ' Source must be array or IList.
        Dim source = Enumerable.Range(0, 100000).ToArray()

        ' Partition the entire source array. 
        ' Let the partitioner size the ranges.
        Dim rangePartitioner = Partitioner.Create(0, source.Length)

        Dim results(source.Length - 1) As Double

        ' Loop over the partitions in parallel. The Sub is invoked
        ' once per partition.
        Parallel.ForEach(rangePartitioner, Sub(range, loopState)

                                               ' Loop over each range element without a delegate invocation.
                                               For i As Integer = range.Item1 To range.Item2 - 1
                                                   results(i) = source(i) * Math.PI
                                               Next
                                           End Sub)
        Console.WriteLine("Operation complete. Print results? y/n")
        Dim input As Char = Console.ReadKey().KeyChar
        If input = "y"c Or input = "Y"c Then
            For Each d As Double In results
                Console.Write("{0} ", d)
            Next
        End If

    End Sub
End Module

Setiap utas dalam perulangan menerima sendiri Tuple<T1,T2> yang berisi nilai indeks awal dan akhir dalam subrentang yang ditentukan. Perulangan for dalam menggunakan nilai fromInclusive dan toExclusive untuk mengulang array atau IList secara langsung.

Salah satu overload Create memungkinkan Anda menentukan ukuran partisi, dan jumlah partisi. Overload ini dapat digunakan dalam skenario di mana pekerjaan per elemen sangat rendah sehingga bahkan satu panggilan metode virtual per elemen memiliki dampak nyata pada performa.

Partisi Kustom

Dalam beberapa skenario, mungkin ada baiknya atau bahkan diperlukan untuk mengimplementasikan partisi Anda sendiri. Misalnya, Anda mungkin memiliki kelas kumpulan kustom yang dapat Anda partisi lebih efisien daripada partisi default, berdasarkan pengetahuan Anda tentang struktur internal kelas. Atau, Anda mungkin ingin membuat partisi rentang dengan berbagai ukuran berdasarkan pengetahuan Anda tentang berapa lama waktu yang diperlukan untuk memproses elemen di lokasi yang berbeda dalam kumpulan sumber.

Untuk membuat partisi kustom dasar, ambil kelas dari System.Collections.Concurrent.Partitioner<TSource> dan ambil alih metode virtual, seperti yang dijelaskan dalam tabel berikut.

Metode Deskripsi
GetPartitions Metode ini dipanggil sekali oleh utas utama dan mengembalikan IList(IEnumerator(TSource)). Setiap utas pekerja dalam perulangan atau kueri dapat memanggil GetEnumerator daftar untuk mengambil IEnumerator<T> pada partisi yang berbeda.
SupportsDynamicPartitions Kembalikan true jika Anda menerapkan GetDynamicPartitions, sebaliknya, false.
GetDynamicPartitions Jika SupportsDynamicPartitions adalah true, metode ini secara opsional dapat dipanggil sebagai ganti GetPartitions.

Jika hasilnya harus dapat diurutkan atau Anda memerlukan akses yang diindeks ke dalam elemen, ambil dari System.Collections.Concurrent.OrderablePartitioner<TSource> dan timpa metode virtualnya seperti yang dijelaskan dalam tabel berikut.

Metode Deskripsi
GetPartitions Metode ini dipanggil sekali oleh utas utama dan mengembalikan IList(IEnumerator(TSource)). Setiap utas pekerja dalam perulangan atau kueri dapat memanggil GetEnumerator daftar untuk mengambil IEnumerator<T> pada partisi yang berbeda.
SupportsDynamicPartitions Kembalikan true jika Anda menerapkan GetDynamicPartitions; sebaliknya, false.
GetDynamicPartitions Biasanya, ini hanya memanggil GetOrderableDynamicPartitions.
GetOrderableDynamicPartitions Jika SupportsDynamicPartitions adalah true, metode ini secara opsional dapat dipanggil sebagai ganti GetPartitions.

Tabel berikut ini menyediakan detail tambahan tentang bagaimana tiga jenis partisi penyeimbang beban mengimplementasikan kelas OrderablePartitioner<TSource>.

Metode/Properti IList / Array tanpa Penyeimbangan Beban IList / Array dengan Penyeimbangan Beban IEnumerable
GetOrderablePartitions Menggunakan pemartisian rentang Menggunakan pemartisian potongan yang dioptimalkan untuk Daftar untuk partitionCount yang ditentukan Menggunakan pemartisian potongan dengan membuat jumlah partisi statis.
OrderablePartitioner<TSource>.GetOrderableDynamicPartitions Menampilan pengecualian yang tidak didukung Menggunakan pemartisian potongan yang dioptimalkan untuk Daftar dan partisi dinamis Menggunakan pemartisian potongan dengan membuat jumlah partisi dinamis.
KeysOrderedInEachPartition Mengembalikan true Mengembalikan true Mengembalikan true
KeysOrderedAcrossPartitions Mengembalikan true Mengembalikan false Mengembalikan false
KeysNormalized Mengembalikan true Mengembalikan true Mengembalikan true
SupportsDynamicPartitions Mengembalikan false Mengembalikan true Mengembalikan true

Partisi Dinamis

Jika Anda ingin agar pemartisi digunakan dalam metode ForEach, Anda harus dapat mengembalikan jumlah partisi yang dinamis. Ini berarti bahwa partisi dapat menyediakan enumerator untuk partisi baru sesuai permintaan kapan saja selama eksekusi perulangan. Pada dasarnya, setiap kali perulangan menambahkan tugas paralel baru, perulangan meminta partisi baru untuk tugas tersebut. Jika Anda mengharuskan data dapat diurutkan, ambil dari System.Collections.Concurrent.OrderablePartitioner<TSource> sehingga setiap item di setiap partisi diberi indeks unik.

Untuk informasi selengkapnya, dan contohnya, lihat Cara: Menerapkan Partisi Dinamis.

Kontrak untuk Partisi

Saat Anda menerapkan partisi kustom, ikuti panduan ini untuk membantu memastikan interaksi yang benar dengan PLINQ dan ForEach di TPL:

  • Jika GetPartitions dipanggil dengan argumen nol atau kurang untuk partitionsCount, tampilkan ArgumentOutOfRangeException. Meskipun PLINQ dan TPL tidak akan pernah lulus dalam partitionCount setara dengan 0, kami tetap menyarankan Agar Anda menjaga terhadap kemungkinan tersebut.

  • GetPartitions dan GetOrderablePartitions harus selalu mengembalikan partitionsCount jumlah partisi. Jika partisi kehabisan data dan tidak dapat membuat partisi sebanyak yang diminta, metode harus mengembalikan enumerator kosong untuk setiap partisi yang tersisa. Jika tidak, baik PLINQ dan TPL akan menampilkan InvalidOperationException.

  • GetPartitions, GetOrderablePartitions, GetDynamicPartitions, dan GetOrderableDynamicPartitions tidak boleh mengembalikan null (Nothing dalam Visual Basic). Jika mereka melakukannya, PLINQ / TPL akan menampilkan InvalidOperationException.

  • Metode yang mengembalikan partisi harus selalu mengembalikan partisi yang dapat menghitung sumber data sepenuhnya dan unik. Seharusnya tidak ada duplikasi dalam sumber data atau item yang dilewati kecuali secara khusus diperlukan oleh desain partisi. Jika aturan ini tidak diikuti, urutan output dapat diacak.

  • Getter Boolean berikut harus selalu secara akurat mengembalikan nilai berikut sehingga urutan output tidak diacak:

    • KeysOrderedInEachPartition: Setiap partisi mengembalikan elemen dengan indeks kunci yang meningkat.

    • KeysOrderedAcrossPartitions: Untuk semua partisi yang dikembalikan, indeks kunci dalam partisi i lebih tinggi dari indeks kunci dalam partisi i-1.

    • KeysNormalized: Semua indeks utama meningkat secara monoton tanpa celah, mulai dari nol.

  • Semua indeks harus unik. Mungkin tidak ada indeks duplikat. Jika aturan ini tidak diikuti, urutan output dapat diacak.

  • Semua indeks harus nonnegatif. Jika aturan ini tidak diikuti, maka PLINQ/TPL dapat menampilkan pengecualian.

Lihat juga