Static Search Trees: 40x lebih cepat daripada pencarian biner

 (curiouscoding.nl)
22 poin oleh GN⁺ 2025-01-02 | 2 komentar | Bagikan ke WhatsApp
  • Mengimplementasikan pohon pencarian statis bernama "S+ tree" untuk melakukan pencarian berkecepatan tinggi pada data terurut
  • Berangkat dari kode yang diusulkan dalam post Algorithmica, lalu mengoptimalkannya serta mengimplementasikan ide tambahan dan perbaikan yang diusulkan
  • Setelah menganalisis kode assembly, semua instruksi yang memungkinkan dioptimalkan untuk memaksimalkan performa
  • Memperkenalkan batching untuk meningkatkan throughput dengan memproses banyak kueri secara paralel
  • Tujuannya adalah menjalankan kueri secara efisien pada data terurut sambil mempertahankan throughput tinggi melalui S+ tree

1. Pengenalan dan motivasi

  • Definisi masalah:

    • Input: daftar bilangan bulat tak bertanda 32-bit terurut vals: Vec<u32>
    • Output: struktur data dengan ukuran seminimal mungkin yang mengembalikan nilai yang lebih besar dari atau sama dengan kueri tertentu (q)
    • Metrik: jumlah kueri independen yang dapat diproses per detik

  • Tujuan:

    • Membangun struktur data yang efisien dalam bioinformatika, khususnya meningkatkan kecepatan pencarian suffix array untuk pengindeksan sekuens DNA
    • Menargetkan performa maksimum dengan memanfaatkan kinerja CPU dan instruksi SIMD

  • Bacaan yang direkomendasikan:

    • Penelitian tentang pencarian biner dan layout array (“Array Layouts for Comparison-Based Searching”)
    • Materi pengantar tentang S+ tree dan B-tree statis

2. S+ tree dan optimisasi

2.1 Pencarian biner dan layout Eytzinger

  • Pencarian biner di pustaka standar Rust kurang efisien terhadap cache, dan performanya menurun saat ukuran data bertambah
  • Layout Eytzinger:
    • Menyimpan pohon pencarian biner dalam bentuk array untuk memaksimalkan pemanfaatan cache
    • Performa: hingga 4x lebih cepat daripada pencarian biner untuk data yang melampaui cache L3

2.2 Konsep S+ tree

  • S-tree:
    • Bentuk pohon heksadesimal dengan 15 nilai terurut per node
    • Lebih efisien daripada B-tree dan lebih mudah dipadatkan daripada layout Eytzinger
  • S+ tree:
    • Menyimpan semua data di node leaf, dengan salinan duplikat disimpan di node atas
    • Menyediakan pencarian yang sederhana dan struktur yang efisien

2.3 Optimisasi fungsi find

  • Pencarian linear dasar:
    • Menelusuri data dan mengembalikan nilai yang memenuhi kondisi (tidak efisien)
  • Vektorisasi otomatis:
    • Diubah menjadi kode tanpa branch, meningkatkan performa 2x dengan memanfaatkan instruksi SIMD
  • Implementasi SIMD manual:
    • Dioptimalkan secara manual menggunakan instruksi SIMD, memaksimalkan performa hanya dengan 5 instruksi

3. Batching dan prefetching

3.1 Batching

  • Memproses banyak kueri secara paralel untuk menutupi latensi memori
  • Throughput meningkat seiring pembesaran ukuran batch, lalu jenuh pada ukuran batch maksimum 16

3.2 Prefetching

  • Membawa node berikutnya ke memori lebih awal untuk meningkatkan performa pada data yang melampaui cache L3
  • Dikombinasikan dengan batching, waktu pemrosesan dipangkas dari 45ns/query menjadi 30ns/query

4. Optimisasi layout dan struktur data

4.1 Mengubah ukuran node

  • Mengurangi jumlah nilai per node menjadi 15 untuk menyederhanakan operasi perkalian dan meningkatkan efisiensi cache
  • Memberikan sedikit peningkatan performa untuk data yang berada di dalam cache L3

4.2 Mengubah layout memori

  • Mencoba layout yang disimpan dalam urutan terbalik atau konfigurasi dengan padding minimal
  • Baik layout terbalik maupun pengurangan padding tidak banyak memengaruhi performa

5. Partisi data

5.1 Partisi berbasis prefiks

  • Memisahkan part berdasarkan bit-bit tinggi data
  • Meningkatkan performa untuk data kecil, tetapi menimbulkan overhead memori

5.2 Subtree terkompresi

  • Mengemas setiap subtree untuk meningkatkan efisiensi ruang
  • Perlu melacak ukuran part, dan kecepatan kueri sedikit menurun

6. Perbandingan multithread

  • Dengan 6 thread, waktu kueri turun dari 27ns menjadi 7ns
  • Batas bandwidth RAM menjadi bottleneck

7. Kesimpulan dan riset lanjutan

  • Peningkatan performa lebih dari 40x dibanding pencarian biner (1150ns/query → 27ns/query)
  • Pekerjaan selanjutnya:
    • Optimisasi keseimbangan data dan pengurangan akses RAM
    • Menangani kueri rentang dan kueri pengurutan
    • Integrasi pencarian suffix array

Bacaan terkait

2 komentar

 
beenzinozino 2025-01-04

Wah... jika ini diterapkan pada pustaka bawaan di berbagai bahasa, dampaknya tampaknya akan sangat besar.
 
GN⁺ 2025-01-02
Opini Hacker News

  • Mengamati bahwa Rust semakin sering digunakan dalam konten algoritma tingkat rendah. Dulu, konten semacam ini umumnya ditulis dalam C(++) atau pseudocode ilmiah. Melihat meningkatnya penggunaan Rust sebagai hal yang positif

    • Tidak terlalu paham Rust, tetapi tetap bisa memahami konten yang ditulis dengan Rust. Mirip seperti programmer Rust yang bisa memahami contoh algoritma yang ditulis dalam C
    • Lebih suka jika Rust menjadi standar, dan berpikir akan bagus juga jika Zig digunakan bersama

  • Metode membagi kueri menjadi batch belum dieksplorasi. Biaya utama ada pada lookup di tabel yang berada di luar cache

    • Jika kuerinya cukup banyak, beberapa level pohon bisa diselesaikan sekaligus
    • Bisa muncul masalah karena hasilnya harus diurutkan ke urutan output yang benar

  • Jumlah nilai int32 tidak terlalu banyak, dan seluruh bitset berukuran 512MB. Untuk struktur data umum, merekomendasikan Roaring Bitmaps

    • Jika hanya membutuhkan lookup sederhana, fungsi hash sempurna minimum layak dipertimbangkan

  • Merasa kagum dengan cara meningkatkan efisiensi tingkat rendah di Rust. Ingin membandingkannya dengan implementasi C++

  • Keunggulan pohon Eytzinger adalah adanya rumus untuk mengonversi indeks node ke posisi traversal inorder

    • Berguna jika penyimpanan kunci dasarnya adalah himpunan kunci yang terurut
    • Dengan Eytzinger, beberapa iterasi loop dapat diprediksi sebelumnya

  • Mengejutkan bahwa ada overhead sekitar ~27ns untuk mencari u32 dalam memori 4GB

    • Penasaran bagaimana optimisasi berjalan pada ukuran batch 8
    • Hasil multithreading juga menarik. Saat beralih dari 1 ke 6 thread, overhead membaik 4 kali lipat

  • Ada banyak diskusi tentang Rust dan C++, tetapi berpikir tentang cara mengimplementasikannya sambil mempertahankan SIMD di Common Lisp

  • Setiap kali membaca tulisan tentang optimisasi tingkat rendah, merasa berterima kasih karena penulis telah meluangkan waktu untuk menghemat nanodetik

    • Bertanya-tanya berapa banyak waktu yang telah dihemat umat manusia karena optimisasi semacam ini terakumulasi

  • Mengira ada kesalahan pada gambar 3 di 1.7. Menyarankan agar label sumbu y pada gambar 1 di 1.3 seharusnya "throughput terbalik"

  • Jika sesekali perlu mendukung penulisan, bisa menggunakan pohon pencarian statis besar dan pohon kecil yang dapat ditulisi

    • Saat perubahan sudah cukup banyak, perubahan tersebut bisa dipindahkan ke versi baru dari pohon statis