Pengukuran Waktu dengan Akurasi Nanosecond

Beberapa bulan yang lalu suatu momen bersejarah datang untuk saya. Alat sistem operasi standar untuk mengukur waktu sudah tidak cukup bagi saya. Butuh waktu untuk mengukur dengan akurasi nanosecond dan dengan overhead nanosecond.

Saya memutuskan untuk menulis perpustakaan yang akan menyelesaikan masalah ini. Sekilas, sepertinya tidak ada yang istimewa untuk dilakukan. Tetapi setelah diperiksa lebih dekat, seperti biasa, ternyata ada banyak masalah menarik yang harus ditangani. Pada artikel ini, saya akan berbicara tentang masalah dan bagaimana mereka menyelesaikannya.

Karena Anda dapat mengukur berbagai jenis waktu di komputer, saya akan segera mengklarifikasi bahwa di sini kita akan berbicara tentang "waktu oleh stopwatch". Atau waktu jam dinding. Ini waktu nyata, waktu berlalu, dll. Yaitu, waktu "manusia" yang sederhana, yang kami deteksi pada awal tugas dan berhenti pada akhirnya.

Microsecond - hampir selamanya

Pengembang sistem berkinerja tinggi selama beberapa tahun terakhir telah terbiasa dengan skala waktu mikrodetik. Dalam mikrodetik, Anda dapat membaca data dari drive NVMe. Dalam mikrodetik, data dapat dikirim melalui jaringan. Bukan untuk semua orang, tentu saja, tetapi untuk jaringan InifiniBand - dengan mudah.

Pada saat yang sama, mikrodetik juga memiliki struktur. Tumpukan I / O lengkap terdiri dari beberapa komponen perangkat lunak dan perangkat keras. Keterlambatan yang diperkenalkan oleh beberapa dari mereka berada pada tingkat sub-mikrodetik.

Untuk mengukur keterlambatan sebesar ini, akurasi mikrodetik tidak lagi memadai. Namun, tidak hanya keakuratan itu penting, tetapi juga overhead untuk mengukur waktu. Panggilan sistem Linux clock_gettime () mengembalikan waktu dengan ketepatan nanosecond. Pada mesin yang tepat di ujung jari saya (Intel® Xeon® CPU E5-2630 v2 @ 2.60GHz), panggilan ini selesai sekitar 120 ns. Sosok yang sangat bagus. Selain itu, clock_gettime () berfungsi dengan sangat mudah ditebak. Ini memungkinkan Anda untuk memperhitungkan overhead panggilannya dan benar-benar melakukan pengukuran dengan akurasi urutan puluhan nanodetik. Namun, mari kita perhatikan hal ini. Untuk mengukur interval waktu, Anda perlu membuat dua panggilan seperti itu: di awal dan di akhir. Yaitu menghabiskan 240 ns. Jika interval waktu yang padat dari urutan 1-10 μs diukur, maka dalam beberapa kasus seperti itu proses pengukuran itu sendiri akan secara signifikan mengubah proses yang diamati.

Saya memulai bagian ini dengan cara mempercepat tumpukan IO dalam beberapa tahun terakhir. Ini baru, tetapi jauh dari satu-satunya alasan ingin mengukur waktu dengan cepat dan akurat. Kebutuhan seperti itu selalu ada. Sebagai contoh, selalu ada kode yang saya ingin percepat oleh setidaknya 1 jam siklus mikroprosesor. Atau contoh lain, dari artikel asli tentang kerentanan Spectre sensasional:



Di sini, baris 72-74 mengukur waktu pelaksanaan operasi akses memori tunggal. Benar, Spectre tidak tertarik pada nanodetik. Waktu dapat diukur dalam "burung beo." Kami akan kembali ke kakatua dan detik.

Penghitung waktu

Kunci pengukuran waktu yang cepat dan akurat adalah penghitung mikroprosesor khusus. Nilai penghitung ini biasanya disimpan dalam register terpisah dan biasanya - tetapi tidak selalu - dapat diakses dari ruang pengguna. Pada arsitektur yang berbeda, penghitung disebut berbeda:

1. penghitung cap waktu x86
2. register basis waktu di PowerPC
3. penghitung waktu interval pada Itanium
4. dll.

Di bawah ini saya akan selalu menggunakan nama "penghitung cap waktu" atau TSC, meskipun pada kenyataannya saya akan mengingat penghitung seperti itu, terlepas dari arsitekturnya.

Membaca nilai TSC biasanya - tetapi sekali lagi tidak selalu - dimungkinkan dengan satu instruksi. Berikut adalah contoh untuk x86. Sebenarnya, ini bukan instruksi assembler murni, tetapi assembler inline GNU:

uint32_t eax, edx; __asm__ __volatile__( "rdtsc" : "=a" (eax), "=d" (edx)); 

Instruksi rdtsc menempatkan dua bagian 32-bit dari register TSC di register eax dan edx. Dari jumlah tersebut, Anda dapat "merekatkan" nilai 64-bit tunggal.

Sekali lagi saya perhatikan: instruksi ini (dan sejenisnya) dalam banyak kasus dapat dipanggil langsung dari ruang pengguna. Tidak ada panggilan sistem. Overhead minimum.

Apa yang sekarang perlu dilakukan untuk mengukur waktu?

1. Jalankan satu instruksi seperti itu di awal interval waktu yang menarik bagi kami. Ingat nilai konter
2. Jalankan satu instruksi seperti itu di akhir. Kami percaya bahwa nilai penghitung dari instruksi pertama ke yang kedua akan meningkat. Kalau tidak, mengapa itu dibutuhkan? Ingat nilai kedua
3. Kami mempertimbangkan perbedaan antara dua nilai yang disimpan. Ini adalah waktu kita

Ini terlihat sederhana, tetapi ...

Waktu yang diukur dengan prosedur yang dijelaskan dinyatakan dalam "kakatua". Itu tidak dalam hitungan detik. Tetapi terkadang burung beo adalah yang Anda butuhkan. Ada situasi di mana bukan nilai absolut dari interval waktu yang penting, tetapi bagaimana interval berbeda berhubungan satu sama lain. Contoh Spectre di atas menunjukkan dengan tepat situasi ini. Durasi setiap akses memori individu tidak masalah. Hanya penting bahwa panggilan ke beberapa alamat akan dieksekusi lebih cepat daripada yang lain (tergantung pada apakah data disimpan dalam cache atau memori utama).

Tetapi bagaimana jika bukan beo yang dibutuhkan, tetapi detik / mikrodetik / nanodetik, dll.? Dua kasus yang berbeda secara mendasar dapat dibedakan di sini:

1. Nanodetik diperlukan, tetapi kemudian. Artinya, pertama-tama diperbolehkan melakukan semua pengukuran yang diperlukan pada burung beo dan menyimpannya di tempat lain untuk diproses lebih lanjut (misalnya, dalam memori). Dan hanya setelah pengukuran selesai, perlahan-lahan mengkonversi burung nuri yang dikumpulkan menjadi detik
2. Nanodetik diperlukan "dengan cepat." Misalnya, proses pengukuran Anda memiliki semacam "konsumen" yang tidak Anda kendalikan dan yang mengharapkan waktu dalam format "manusia"

Kasus pertama sederhana, yang kedua - membutuhkan akal. Konversi harus seefektif mungkin. Jika itu menghabiskan banyak sumber daya, itu dapat sangat merusak proses pengukuran. Kami akan berbicara tentang konversi yang efektif di bawah ini. Di sini kita sejauh ini mengidentifikasi masalah ini dan beralih ke masalah lain.

Penghitung waktu tidak semudah yang kita inginkan. Pada beberapa arsitektur:

1. tidak dijamin bahwa TSC diperbarui pada frekuensi tinggi. Jika TSC diperbarui, katakanlah, sekali setiap mikrodetik, maka itu tidak mungkin untuk memperbaiki nanodetik dengan itu.
2. frekuensi TSC diperbarui dapat bervariasi dari waktu ke waktu
3. pada berbagai CPU yang ada dalam sistem, TSC dapat diperbarui pada frekuensi yang berbeda
4. mungkin ada pergeseran antara TSC yang berdetak pada CPU yang berbeda

Berikut adalah contoh yang menggambarkan masalah terakhir. Misalkan kita memiliki sistem dengan dua CPU: CPU1 dan CPU2. Misalkan TSC pada CPU pertama berada di belakang yang kedua dengan jumlah ticks, yang setara dengan 5 detik. Misalkan lebih lanjut bahwa aliran diluncurkan dalam sistem yang mengukur waktu perhitungan, yang ia lakukan sendiri. Untuk melakukan ini, aliran pertama membaca nilai TSC, kemudian melakukan perhitungan, dan kemudian membaca nilai TSC kedua. Jika sepanjang hidupnya satu utas tetap hanya pada satu CPU - pada apa saja - maka tidak ada masalah. Tetapi bagaimana jika utas dimulai pada CPU1, mengukur nilai TSC pertama di sana, dan kemudian di tengah perhitungan dipindahkan oleh sistem operasi ke CPU2, di mana ia membaca nilai TSC kedua? Dalam hal ini, perhitungan akan tampak 5 detik lebih lama dari yang sebenarnya.

Karena masalah yang tercantum di atas, TSC tidak dapat berfungsi sebagai sumber waktu yang andal pada beberapa sistem. Namun, pada sistem lain "menderita" dari masalah yang sama, TSC masih dapat digunakan. Ini dimungkinkan berkat fitur arsitektur khusus:

1. peralatan dapat menghasilkan interupsi khusus setiap kali frekuensi perubahan TSC diperbarui. Pada saat yang sama, peralatan juga memberikan kesempatan untuk mengetahui frekuensi saat ini. Sebagai alternatif, kecepatan refresh TSC dapat ditempatkan di bawah kendali sistem operasi (lihat “Power ISA Versi 2.06 Revisi B, Buku II, Bab 5”)
2. bersama dengan nilai TSC, peralatan juga dapat memberikan ID CPU tempat nilai ini dibaca (lihat instruksi Intel RDTSCP, "Manual Pengembang Perangkat Lunak Arsitektur Intel 64 dan IA-32", Volume 2)
3. pada beberapa sistem, Anda dapat secara programatik menyesuaikan nilai TSC untuk setiap CPU (lihat instruksi Intel WRMSR dan daftarkan IA32_TIME_STAMP_COUNTER, “Manual Pengembang Perangkat Lunak Arsitektur Perangkat Arsitektur Intel 64 dan IA-32”, Volume 3)

Secara umum, tema tentang bagaimana meter waktu diimplementasikan pada arsitektur yang berbeda sangat menarik dan luas. Jika Anda punya waktu dan minat, saya sarankan menyelam. Antara lain, Anda akan belajar, misalnya, bahwa beberapa sistem memungkinkan Anda untuk menentukan apakah TSC dapat berfungsi sebagai sumber waktu yang andal.

Jadi, ada banyak implementasi arsitektur TSC, masing-masing dengan karakteristiknya sendiri. Tetapi menarik bahwa tren umum telah ditetapkan di semua kebun binatang ini. Perangkat keras dan sistem operasi modern berusaha untuk memastikan bahwa :

1. TSC berdetak pada frekuensi yang sama pada setiap CPU dalam sistem
2. frekuensi ini tidak berubah dalam waktu
3. tidak ada pergeseran antara TSC yang berdetak pada CPU yang berbeda

Ketika mendesain perpustakaan saya, saya memutuskan untuk melanjutkan dari premis ini, dan bukan dari tampilan implementasi perangkat keras.

Perpustakaan

Saya tidak mulai meletakkan pada chip perangkat keras dari sekelompok arsitektur yang berbeda. Sebaliknya, saya memutuskan bahwa perpustakaan saya akan berorientasi pada tren. Dia memiliki fokus empiris murni:

1. itu memungkinkan Anda untuk secara eksperimental memverifikasi keandalan TSC sebagai sumber waktu
2. juga memungkinkan Anda untuk secara eksperimental menghitung parameter yang diperlukan untuk dengan cepat mengkonversi kutu ke nanodetik
3. secara alami, perpustakaan menyediakan antarmuka yang nyaman untuk membaca TSC dan mengubah kutu menjadi nanodetik "on the fly"

Kode perpustakaan tersedia di sini. Ini akan dikompilasi dan dieksekusi hanya di Linux.

Dalam kode tersebut, Anda dapat melihat detail implementasi semua metode, yang akan dibahas nanti.

Penilaian Keandalan TSC

Perpustakaan menyediakan antarmuka yang mengembalikan dua peringkat:

1. pergeseran maksimum antara penghitung milik CPU yang berbeda. Hanya CPU yang tersedia untuk proses yang dipertimbangkan. Misalnya, jika suatu proses memiliki tiga CPU yang tersedia, dan pada saat yang sama TSC pada CPU ini adalah 50, 150, 20, maka pergeseran maksimum akan menjadi 150-20 = 130. Secara alami, perpustakaan tidak akan dapat memperoleh pergeseran maksimum yang nyata secara eksperimental, tetapi akan memberikan perkiraan yang sesuai dengan pergeseran ini. Apa yang harus dilakukan selanjutnya dengan penilaian? Bagaimana cara menggunakan Ini sudah memecahkan kode klien. Tetapi artinya kira-kira sebagai berikut. Pergeseran maksimum adalah nilai maksimum dimana dimensi yang dibuat kode klien dapat terdistorsi. Misalkan, dalam contoh kita dengan tiga CPU, kode klien mulai mengukur waktu pada CPU3 (di mana TSC adalah 20), dan berakhir pada CPU2 (di mana TSC adalah 150). Ternyata 130 kutu tambahan akan menyusup ke interval yang diukur. Dan tidak akan pernah lagi. Perbedaan antara CPU1 dan CPU2 akan hanya 100 ticks. Memiliki perkiraan 130 ticks (pada kenyataannya, itu akan jauh lebih konservatif), klien dapat memutuskan apakah nilai distorsi seperti itu cocok untuknya atau tidak
2. Apakah nilai TSC diukur secara berurutan pada kenaikan CPU yang sama atau berbeda. Inilah idenya. Katakanlah kita memiliki beberapa CPU. Misalkan jam mereka disinkronkan dan terus berdetak pada frekuensi yang sama. Kemudian jika Anda pertama kali mengukur waktu pada satu CPU, dan kemudian mengukurnya lagi - sudah pada salah satu CPU yang tersedia - maka digit kedua harus lebih besar dari yang pertama.
   
   Saya akan menyebut estimasi ini di bawah estimasi monotonisitas TSC
   

Sekarang mari kita lihat bagaimana kita bisa mendapatkan estimasi pertama:

1. salah satu prosesor yang tersedia untuk proses tersebut dinyatakan "dasar"
2. maka semua CPU lainnya diurutkan, dan untuk masing-masing shift dihitung: TSC___CPU – TSC___CPU . Ini dilakukan sebagai berikut:
   
   • a) tiga nilai terukur diambil secara berurutan (satu demi satu!): TSC_base_1, TSC_current, TSC_base_2 . Di sini, saat ini menunjukkan bahwa nilai diukur pada CPU saat ini, dan berdasarkan pada basis
   • b) shift TSC___CPU – TSC___CPU harus terletak pada interval [TSC_current – TSC_base_2, TSC_current – TSC_base_1] . Ini berdasarkan asumsi bahwa TSC terus berdetak pada frekuensi yang sama pada kedua CPU.
   • c) langkah a) -b) diulang beberapa kali. Perpotongan semua interval yang diperoleh pada langkah b) dihitung. Interval yang dihasilkan diambil sebagai estimasi shift TSC___CPU – TSC___CPU
   
   
3. setelah estimasi shift diperoleh untuk setiap CPU relatif terhadap basis, mudah untuk mendapatkan estimasi pergeseran maksimum antara semua CPU yang tersedia:
   
   • a) interval minimum dihitung, yang mencakup semua interval yang dihasilkan yang diperoleh pada langkah 2
   • b) lebar interval ini diambil sebagai estimasi pergeseran maksimum antara TSC yang berdetak pada CPU yang berbeda
   
   

Untuk mengevaluasi monoton di perpustakaan, algoritma berikut ini diterapkan:

1. Katakanlah sebuah proses memiliki N CPU yang tersedia
2. Mengukur TSC pada CPU1
3. Mengukur TSC pada CPU2
4. ...
5. Mengukur TSC pada CPUN
6. Ukur TSC lagi pada CPU1
7. Kami memverifikasi bahwa nilai yang diukur meningkat secara monoton dari yang pertama ke yang terakhir

Penting di sini bahwa nilai pertama dan terakhir diukur pada CPU yang sama. Dan inilah alasannya. Katakanlah kita memiliki 3 CPU. Misalkan TSC pada CPU2 digeser oleh +100 ticks relatif terhadap TSC pada CPU1. Anggap juga bahwa TSC pada CPU3 digeser oleh +100 ticks relatif terhadap TSC pada CPU2. Pertimbangkan rangkaian acara berikut:

• Baca TSC pada CPU1. Biarkan nilai 10 diperoleh
• 2 ticks berlalu
• Baca TSC pada CPU2. Harus 112
• 2 ticks berlalu
• Baca TSC pada CPU3. Harus 214

Sejauh ini, jamnya terlihat disinkronkan. Tapi mari kita ukur TSC pada CPU1 lagi:

• 2 ticks berlalu
• Baca TSC pada CPU1. Harus 16 tahun

Ups! Monoton rusak. Ternyata mengukur nilai pertama dan terakhir pada CPU yang sama memungkinkan Anda mendeteksi lebih atau kurang pergeseran besar di antara jam. Pertanyaan selanjutnya, tentu saja: "Seberapa besar pergeserannya?" Jumlah pergeseran yang dapat dideteksi tergantung pada waktu yang berlalu antara pengukuran TSC berturut-turut. Dalam contoh yang diberikan, ini hanya 2 ticks. Pergeseran antara jam yang melebihi 2 kutu akan terdeteksi. Secara umum, pergeseran yang kurang dari waktu yang berlalu antara pengukuran berturut-turut tidak akan terdeteksi. Jadi, semakin padat pengukuran terletak pada waktunya, semakin baik. Keakuratan kedua perkiraan tergantung pada ini. Semakin padat pengukuran dilakukan:

• semakin rendah estimasi pergeseran maksimum
• semakin percaya diri dalam penilaian monoton

Di bagian selanjutnya, kita akan berbicara tentang bagaimana melakukan pengukuran ketat. Saya akan menambahkan di sini bahwa ketika menghitung perkiraan keandalan TSC, perpustakaan melakukan banyak pemeriksaan "kutu" yang lebih sederhana, misalnya:

• verifikasi terbatas bahwa TSC pada CPU berbeda berdetak pada kecepatan yang sama
• memeriksa apakah penghitung benar-benar berubah dari waktu ke waktu, dan tidak hanya menunjukkan nilai yang sama

Dua metode untuk mengumpulkan nilai penghitung

Di perpustakaan, saya menerapkan dua metode untuk mengumpulkan nilai TSC:

1. Beralih di antara CPU . Dalam metode ini, semua data yang diperlukan untuk menilai keandalan TSC dikumpulkan oleh satu utas yang "melompat" dari satu CPU ke CPU lainnya. Kedua algoritma yang dijelaskan pada bagian sebelumnya cocok untuk metode ini dan tidak cocok untuk yang lain.
   "Beralih di antara CPU" tidak memiliki penggunaan praktis. Metode itu diterapkan hanya demi "bermain-main." Masalah dengan metode ini adalah waktu yang dibutuhkan untuk "menyeret" aliran dari satu CPU ke CPU lainnya sangat besar. Oleh karena itu, banyak waktu berlalu antara pengukuran TSC berturut-turut, dan akurasi estimasi sangat rendah. Misalnya, perkiraan tipikal untuk pergeseran maksimum antara TSC diperoleh di wilayah 23.000 kutu.
   
   Namun, metode ini memiliki beberapa keunggulan:
   
   • itu mutlak deterministik. Jika Anda perlu mengukur TSC secara berurutan pada CPU1, CPU2, CPU3, maka kami hanya mengambil dan melakukannya: beralih ke CPU1, baca TSC, beralih ke CPU2, baca TSC, dan akhirnya, beralih ke CPU3, baca TSC
   • mungkin, jika jumlah CPU dalam sistem tumbuh sangat cepat, maka waktu peralihan di antara mereka harus tumbuh jauh lebih lambat. Karena itu, secara teori, ternyata, sebuah sistem bisa ada - sistem yang sangat besar! - di mana penggunaan metode ini akan dibenarkan. Tapi tetap saja ini tidak mungkin
   
   
2. Pengukuran dipesan menggunakan CAS . Dalam metode ini, data dikumpulkan secara paralel oleh banyak utas. Setiap CPU yang tersedia memulai satu utas. Pengukuran yang dilakukan oleh utas berbeda diatur dalam satu urutan menggunakan operasi “bandingkan-dan-tukar”. Di bawah ini adalah bagian dari kode yang menunjukkan bagaimana hal ini dilakukan.
   Gagasan metode ini dipinjam dari fio , alat yang populer untuk menghasilkan beban I / O.
   
   Estimasi keandalan yang diperoleh dengan kekuatan metode ini sudah terlihat cukup bagus. Misalnya, perkiraan pergeseran maksimum sudah diperoleh pada level beberapa ratus kutu. Pemeriksaan monoton memungkinkan Anda untuk menangkap jam tidak sinkron dalam ratusan kutu.
   
   Namun, algoritma yang diberikan pada bagian sebelumnya tidak cocok untuk metode ini. Penting bagi mereka bahwa nilai-nilai TSC diukur dalam urutan yang telah ditentukan. Metode "pengukuran yang dipesan oleh CAS" tidak memungkinkan hal ini. Alih-alih, pertama urutan panjang pengukuran acak dikumpulkan, dan kemudian algoritma (sudah berbeda) mencoba mencari nilai yang dibaca pada CPU "cocok" dalam urutan ini.
   
   Saya tidak akan memberikan algoritme ini di sini, agar tidak menyalahgunakan perhatian Anda. Anda dapat melihatnya dalam kode. Ada banyak komentar. Secara teori, algoritma ini sama. Poin mendasar yang baru adalah verifikasi tentang bagaimana urutan TSC yang diketik secara acak adalah "kualitatif". Dimungkinkan juga untuk menetapkan tingkat signifikansi statistik minimum yang dapat diterima untuk perkiraan keandalan TSC.
   
   Secara teoritis, pada sistem SANGAT besar, metode "CAS ordered" dapat memberikan hasil yang buruk. Metode ini membutuhkan prosesor untuk bersaing mendapatkan akses ke lokasi memori umum. Jika ada banyak prosesor, maka persaingan bisa berubah menjadi sangat intens. Akibatnya, akan sulit untuk membuat urutan pengukuran dengan sifat statistik yang baik. Namun, saat ini, situasi ini tampaknya tidak mungkin.
   

Saya berjanji beberapa kode. Begini tampilannya membangun pengukuran dalam satu rantai menggunakan CAS.

  for ( uint64_t i = 0; i < arg->probes_count; i++ ) { uint64_t seq_num = 0; uint64_t tsc_val = 0; do { __atomic_load( seq_counter, &seq_num, __ATOMIC_ACQUIRE); __sync_synchronize(); tsc_val = WTMLIB_GET_TSC(); } while ( !__atomic_compare_exchange_n( seq_counter, &seq_num, seq_num + 1, false, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)); arg->tsc_probes[i].seq_num = seq_num; arg->tsc_probes[i].tsc_val = tsc_val; } 

Kode ini dijalankan pada setiap CPU yang tersedia. Semua utas memiliki akses ke variabel seq_counter . Sebelum membaca TSC, stream membaca nilai variabel ini dan menyimpannya dalam variabel seq_num . Kemudian membaca TSC. Kemudian ia mencoba untuk meningkatkan seq_counter satu per satu, tetapi hanya jika nilai variabel tidak berubah sejak dibaca. Jika operasi berhasil, maka ini berarti bahwa utas berhasil "mengintai" nomor urut yang disimpan dalam seq_num di belakang nilai TSC yang diukur. Nomor seri berikutnya, yang akan dapat dipertaruhkan (mungkin sudah ada di utas lain) akan menjadi satu lagi. Untuk nomor ini diambil dari variabel seq_counter , dan setiap panggilan yang berhasil dari __atomic_compare_exchange_n() meningkatkan variabel ini dengan satu.


Poin lain yang layak disebutkan di sini adalah kepedulian bahwa semua aliran yang terlibat dalam pengukuran mulai kurang lebih secara bersamaan. Kami tertarik pada fakta bahwa nilai-nilai TSC yang dibaca pada CPU yang berbeda sangat beragam. Kami tidak puas dengan situasi ketika, misalnya, satu utas dimulai pertama, menyelesaikan pekerjaannya, dan baru kemudian semua lainnya mulai. Urutan TSC yang dihasilkan akan memiliki sifat tidak berguna. Tidak ada perkiraan yang bisa diambil darinya. Awal yang simultan dari semua utas penting - dan untuk ini, langkah-langkah telah diambil di perpustakaan.

Ubah kutu menjadi nanodetik dengan cepat

Setelah memeriksa keandalan TSC, tujuan utama kedua perpustakaan adalah untuk mengubah kutu menjadi nanodetik dengan cepat. Saya meminjam ide konversi ini dari fio yang telah disebutkan. Namun, saya harus membuat beberapa perbaikan yang signifikan, karena seperti yang ditunjukkan oleh analisis saya, pada akhirnya prosedur konversi tidak berfungsi dengan cukup baik. Di sana Anda mendapatkan akurasi rendah.

Saya akan mulai dengan sebuah contoh.

Idealnya, saya ingin mengonversi kutu menjadi nanodetik seperti ini:
ns_time = tsc_ticks / tsc_per_ns
Kami ingin waktu yang dihabiskan untuk konversi menjadi minimal. Oleh karena itu, kami bertujuan untuk menggunakan aritmatika integer eksklusif. Mari kita lihat bagaimana ini bisa mengancam kita.

Jika tsc_per_ns = 3 , maka divisi integer sederhana, dari sudut pandang akurasi, berfungsi dengan baik: ns_time = tsc_ticks / 3 .

Tetapi bagaimana jika tsc_per_ns = 3.333 ? 3, . :
ns_time = (tsc_ticks * factor) / (3.333 * factor) .

factor , . - . , . – . , x86 10+ . , .

:
ns_time = (tsc_ticks * factor / 3.333) / factor .

– . (factor / 3.333) . – - . , factor . – .

factor ? , factor . , , , 64- . , «» . , .

, factor . , . TSC : 3.333 * 1000000000 * 60 * 60 * 24 * 365 = 105109488000000000 . 64- : 18446744073709551615 / 105109488000000000 ~ 175.5 . , (factor / 3.333) , . : factor <= 175.5 * 3.333 ~ 584.9 . , , 512. , :

ns_time = (tsc_ticks * 512 / 3.333) / 512

:

ns_time = tsc_ticks * 153 / 512

. , . 1000000000 * 60 * 60 * 24 * 365 = 31536000000000000 . : 105109488000000000 * 153 / 512 = 31409671218750000 . 126328781250000 , 126328781250000 / 1000000000 / 60 / 60 ~ 35 .

. . ? . . :

ns_time = tsc_ticks * 1258417 / 4194304 (1)

119305 1 ( 0.2 ). . , , . ? ?

:

tsc_ticks = (tsc_ticks_per_1_hour * number_of_hours) + tsc_ticks_remainder

tsc_ticks_per_1_hour , number_of_hours tsc_ticks . , , . tsc_ticks , . , tsc_ticks_remainder . , , . , , (1).

. . .

, . 1 . :

tsc_ticks = modulus * number_of_moduli_periods + tsc_ticks_remainder

, :

ns_per_remainder = (tsc_ticks_remainder * factor / tsc_per_nsec) / factor

( , tsc_ticks_remainder < modulus ):

modulus * (factor / tsc_per_nsec) <= UINT64_MAX
factor <= (UINT64_MAX / modulus) * tsc_per_nsec
2 ^ shift <= (UINT64_MAX / modulus) * tsc_per_nsec


, , . . , , , .

, shift , :

factor = 2 ^ shift
mult = factor / tsc_per_nsec


:

ns_per_remainder = (tsc_ticks_remainder * mult) >> shift


, . , – tsc_ticks_remainder number_of_moduli_periods tsc_ticks . , . , . modulus :

modulus = 2 ^ remainder_bit_length

:

number_of_moduli_periods = tsc_ticks >> remainder_bit_length
tsc_ticks_remainder = tsc_ticks & (modulus - 1)

Bagus , tsc_ticks number_of_moduli_periods tsc_ticks_remainder . , tsc_ticks_remainder . , , modulus . :

ns_per_moduli = ns_per_modulus * number_of_moduli_periods

ns_per_modulus . , . , , modulus . modulus , , , modulus .

ns_per_modulus = (modulus * mult) >> shift

! , « ». :

1. tsc_ticks
2. number_of_moduli_periods = tsc_ticks >> remainder_bit_length
3. tsc_ticks_remainder = tsc_ticks & (modulus - 1)
4. ns = ns_per_modulus * number_of_moduli_periods + (tsc_ticks_remainder * mult) >> shift

remainder_bit_length , modulus, ns_per_modulus , mult shift .

, . , performance- .

Jadi disini. , :)

, mult ? :

mult = factor / tsc_per_nsec

: tsc_per_nsec ?
– . tsc_per_nsec (tsc_per_sec / 1000000000) . ..:

mult = factor * 1000000000 / tsc_per_sec

:

1. tsc_per_sec , tsc_per_msec , ?
2. tsc_per_sec ?

. fio . . , , tsc_per_msec = 2599998 . tsc_per_sec = 2599998971 . , : 0.999999626. , , 374 . – tsc_per_sec .

… tsc_per_sec ?

:

start_sytem_time = clock_gettime()
start_tsc = WTMLIB_GET_TSC()
-
end_system_time = clock_gettime()
end_tsc = WTMLIB_GET_TSC()


«- » — . , . , . , end_system_time start_system_time 0,6 . tsc_per_sec = (end_tsc – start_tsc) / 0,6 .

tsc_per_sec . «» - tsc_per_sec , .

, , clock_gettime() WTMLIB_GET_TSC() . , WTMLIB_GET_TSC() , clock_gettime() . TSC. tsc_per_sec . tsc_per_sec . .

Kesimpulan

Mungkin itu saja.

Tetapi topik pengukuran waktu yang efektif tidak terbatas pada hal ini. Ada banyak nuansa. Bagi mereka yang tertarik, saya mengusulkan untuk bekerja secara independen pada masalah-masalah berikut:

• menyimpan parameter konversi dalam cache atau - bahkan lebih baik - di register
• hingga batas apa yang dapat dikurangi modulus(dengan demikian meningkatkan keakuratan konversi)?
• seperti yang telah kita lihat, keakuratan konversi dipengaruhi tidak hanya modulus, tetapi juga oleh ukuran interval waktu, yang berkorelasi dengan kutu ( tsc_per_msecatau tsc_per_sec). Bagaimana menyeimbangkan pengaruh kedua faktor tersebut?
• TSC di mesin virtual. Bisakah saya menggunakannya?
• . , fio timespec. :
  
  tp->tv_sec = nsecs / 1000000000ULL;
  
  , TSC . , ,
  

. , .

, fio, , 700-900 ( ). - . fio. , . , .

!