Contoh menarik dari pengalokasi C ++ khusus?

176

Apa saja alasan yang sangat bagus untuk std::allocatormendukung solusi khusus? Sudahkah Anda menghadapi situasi di mana itu benar-benar diperlukan untuk kebenaran, kinerja, skalabilitas, dll? Adakah contoh yang benar-benar pintar?

Pengalokasi khusus selalu menjadi fitur dari Perpustakaan Standar yang belum terlalu saya butuhkan. Saya hanya ingin tahu apakah ada orang di sini di SO dapat memberikan beberapa contoh menarik untuk membenarkan keberadaan mereka.

Naaff
sumber

Jawaban:

121

Seperti yang saya sebutkan di sini , saya telah melihat pengalokasi STL khusus Intel TBB secara signifikan meningkatkan kinerja aplikasi multithreaded hanya dengan mengubah satu

std::vector<T>

untuk

std::vector<T,tbb::scalable_allocator<T> >

(ini adalah cara cepat dan mudah untuk mengalihkan pengalokasi untuk menggunakan tumpukan thread-private TBB yang bagus; lihat halaman 7 dalam dokumen ini )

timday
sumber
3
Terima kasih atas tautan kedua itu. Penggunaan pengalokasi untuk mengimplementasikan tumpukan thread-pribadi pintar. Saya suka bahwa ini adalah contoh yang baik di mana pengalokasi kustom memiliki keuntungan yang jelas dalam skenario yang tidak terbatas sumber daya (embed atau konsol).
Naaff
7
Tautan asli sekarang mati, tetapi CiteSeer memiliki PDF: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.8289
Arto Bendiken
1
Saya harus bertanya: Bisakah Anda memindahkan vektor seperti itu ke thread lain? (Saya kira tidak)
sellibitze
@sellibitze: Karena vektor sedang dimanipulasi dari dalam tugas TBB dan digunakan kembali di beberapa operasi paralel dan tidak ada jaminan thread pekerja TBB yang akan mengambil tugas, saya menyimpulkan itu berfungsi dengan baik. Meskipun diketahui bahwa ada beberapa masalah bersejarah dengan hal-hal yang membebaskan TBB dibuat di satu utas di utas lainnya (tampaknya masalah klasik dengan tumpukan pribadi thread dan pola alokasi & deallokasi produsen-konsumen. TBB mengklaim pengalokasi itu menghindari masalah ini tetapi saya telah melihat sebaliknya Mungkin diperbaiki dalam versi yang lebih baru.)
timday
@ArtoBendiken: Tautan unduhan di tautan Anda tampaknya tidak valid.
einpoklum
81

Satu area di mana pengalokasi kustom dapat bermanfaat adalah pengembangan game, terutama pada konsol game, karena mereka hanya memiliki sedikit memori dan tidak ada swap. Pada sistem seperti itu Anda ingin memastikan bahwa Anda memiliki kontrol ketat atas setiap subsistem, sehingga satu sistem tidak kritis tidak dapat mencuri memori dari yang kritis. Hal-hal lain seperti pengalokasian kumpulan dapat membantu mengurangi fragmentasi memori. Anda dapat menemukan makalah yang panjang dan terperinci tentang topik di:

EASTL - Perpustakaan Template Standar Seni Elektronik

Grumbel
sumber
14
+1 untuk tautan EASTL: "Di antara pengembang game, kelemahan paling mendasar [dari STL] adalah desain pengalokasi pertama, dan kelemahan inilah yang merupakan faktor penyumbang terbesar bagi penciptaan EASTL."
Naaff
65

Saya bekerja pada pengalokasi mmap yang memungkinkan vektor untuk menggunakan memori dari file yang dipetakan memori. Tujuannya adalah untuk memiliki vektor yang menggunakan penyimpanan yang langsung di memori virtual yang dipetakan oleh mmap. Masalah kami adalah meningkatkan pembacaan file yang sangat besar (> 10GB) ke dalam memori tanpa overhead salinan, oleh karena itu saya memerlukan pengalokasi khusus ini.

Sejauh ini saya memiliki kerangka pengalokasi khusus (yang berasal dari std :: pengalokasi), saya pikir itu adalah titik awal yang baik untuk menulis pengalokasi sendiri. Jangan ragu untuk menggunakan kode ini dengan cara apa pun yang Anda inginkan:

#include <memory>
#include <stdio.h>

namespace mmap_allocator_namespace
{
        // See StackOverflow replies to this answer for important commentary about inheriting from std::allocator before replicating this code.
        template <typename T>
        class mmap_allocator: public std::allocator<T>
        {
public:
                typedef size_t size_type;
                typedef T* pointer;
                typedef const T* const_pointer;

                template<typename _Tp1>
                struct rebind
                {
                        typedef mmap_allocator<_Tp1> other;
                };

                pointer allocate(size_type n, const void *hint=0)
                {
                        fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T));
                        return std::allocator<T>::allocate(n, hint);
                }

                void deallocate(pointer p, size_type n)
                {
                        fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p);
                        return std::allocator<T>::deallocate(p, n);
                }

                mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); }
                mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { }
                template <class U>                    
                mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { }
                ~mmap_allocator() throw() { }
        };
}

Untuk menggunakan ini, nyatakan wadah STL sebagai berikut:

using namespace std;
using namespace mmap_allocator_namespace;

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>());

Sebagai contoh, dapat digunakan untuk mencatat kapan saja memori dialokasikan. Apa yang diperlukan adalah struct rebind, atau wadah vektor menggunakan metode alokasi / deallocate superclasses.

Pembaruan: Pengalokasi pemetaan memori sekarang tersedia di https://github.com/johannesthoma/mmap_allocator dan merupakan LGPL. Jangan ragu untuk menggunakannya untuk proyek Anda.

Johannes Thoma
sumber
17
Hanya kepala, berasal dari std :: pengalokasi sebenarnya bukan cara idiomatik untuk menulis pengalokasi. Alih-alih, Anda harus melihat alokasiator, yang memungkinkan Anda untuk menyediakan fungsionalitas minimum, dan kelas karakter akan menyediakan sisanya. Perhatikan bahwa STL selalu menggunakan pengalokasi Anda melalui pengalokasian, tidak secara langsung, sehingga Anda tidak perlu merujuk pengalokasian sendiri. Tidak ada banyak insentif untuk berasal dari std :: pengalokasi (walaupun kode ini mungkin merupakan titik awal yang membantu terlepas dari).
Nir Friedman
25

Saya bekerja dengan mesin penyimpanan MySQL yang menggunakan c ++ untuk kodenya. Kami menggunakan pengalokasi khusus untuk menggunakan sistem memori MySQL daripada bersaing dengan MySQL untuk memori. Hal ini memungkinkan kami untuk memastikan kami menggunakan memori sebagai pengguna yang mengkonfigurasi MySQL untuk digunakan, dan bukan "ekstra".

Thomas Jones-Low
sumber
21

Berguna menggunakan pengalokasi khusus untuk menggunakan kumpulan memori alih-alih tumpukan. Itu salah satu contoh di antara banyak lainnya.

Untuk sebagian besar kasus, ini tentu saja merupakan optimasi prematur. Tapi itu bisa sangat berguna dalam konteks tertentu (perangkat tertanam, game, dll).

Martin Cote
sumber
3
Atau, ketika kumpulan memori itu dibagikan.
Anthony
9

Saya belum menulis kode C ++ dengan pengalokasian STL khusus, tetapi saya dapat membayangkan server web yang ditulis dalam C ++, yang menggunakan pengalokasi khusus untuk penghapusan otomatis data sementara yang diperlukan untuk menanggapi permintaan HTTP. Pengalokasi khusus dapat membebaskan semua data sementara sekaligus setelah respons dihasilkan.

Kemungkinan penggunaan lainnya untuk pengalokasi khusus (yang telah saya gunakan) adalah menulis unit test untuk membuktikan bahwa perilaku fungsi tidak tergantung pada beberapa bagian dari inputnya. Pengalokasi khusus dapat mengisi wilayah memori dengan pola apa pun.

Poin
sumber
5
Sepertinya contoh pertama adalah pekerjaan destruktor, bukan pengalokasi.
Michael Dorst
2
Jika Anda khawatir tentang program Anda tergantung pada isi awal memori dari heap, menjalankan cepat (yaitu semalam!) Di valgrind akan memberi tahu Anda satu atau lain cara.
cdyson37
3
@anthropomorphic: Destuktor dan pengalokasi kustom akan bekerja bersama, destruktor akan berjalan terlebih dahulu, kemudian penghapusan pengalokasi kustom, yang belum akan memanggil free (...), tetapi free (...) akan dipanggil nanti, saat melayani permintaan telah selesai. Ini bisa lebih cepat daripada pengalokasi default dan mengurangi fragmentasi ruang alamat.
Poin
8

Ketika bekerja dengan GPU atau co-prosesor lain, terkadang bermanfaat untuk mengalokasikan struktur data dalam memori utama dengan cara khusus . Cara khusus ini mengalokasikan memori dapat diimplementasikan dalam pengalokasi kustom dengan cara yang nyaman.

Alasan mengapa alokasi khusus melalui runtime akselerator dapat bermanfaat saat menggunakan akselerator adalah sebagai berikut:

  1. melalui alokasi khusus, runtime atau driver akselerator diberitahu tentang blok memori
  2. selain itu sistem operasi dapat memastikan bahwa blok memori yang dialokasikan terkunci pada halaman (ada yang menyebut ini memori yang disematkan ), yaitu, subsistem memori virtual dari sistem operasi mungkin tidak memindahkan atau menghapus halaman di dalam atau dari memori
  3. jika 1. dan 2. tahan dan transfer data antara blok memori yang dikunci halaman dan akselerator diminta, runtime dapat langsung mengakses data dalam memori utama karena ia tahu di mana itu dan dapat dipastikan sistem operasinya tidak pindahkan / hapus
  4. ini menghemat satu salinan memori yang akan terjadi dengan memori yang dialokasikan dengan cara yang tidak dikunci-halaman: data harus disalin dalam memori utama ke area pementasan yang dikunci halaman dari dengan akselerator dapat menginisialisasi transfer data (melalui DMA )
Sebastian
sumber
1
... jangan lupa blok memori yang disejajarkan dengan halaman. Ini sangat berguna jika Anda berbicara dengan driver (yaitu dengan FPGA via DMA) dan tidak ingin kerumitan dan overhead menghitung offset dalam-halaman untuk pencar daftar DMA Anda.
Jan
7

Saya menggunakan pengalokasi khusus di sini; Anda bahkan mungkin mengatakan itu bekerja mengatasi manajemen memori dinamis kustom lainnya.

Latar Belakang: kami memiliki kelebihan untuk malloc, calloc, gratis, dan berbagai varian operator yang baru dan hapus, dan penghubung dengan senang hati membuat STL menggunakannya untuk kami. Ini memungkinkan kami melakukan hal-hal seperti pengumpulan objek kecil otomatis, deteksi kebocoran, pengalokasian isian, isian gratis, alokasi padding dengan pengawal, penyelarasan garis cache untuk semua dokumen tertentu, dan bebas penundaan.

Masalahnya adalah, kita berjalan di lingkungan yang tertanam - tidak ada cukup memori di sekitar untuk benar-benar melakukan akuntansi deteksi kebocoran dengan benar selama periode yang diperpanjang. Setidaknya, tidak dalam RAM standar - ada tumpukan RAM lain yang tersedia di tempat lain, melalui fungsi alokasi khusus.

Solusi: tulis pengalokasi khusus yang menggunakan tumpukan yang diperluas, dan gunakan hanya di bagian dalam arsitektur pelacakan kebocoran memori ... Segala sesuatu yang lain default ke normal baru / hapus kelebihan yang melakukan pelacakan kebocoran. Ini menghindari pelacakan pelacak itu sendiri (dan juga menyediakan sedikit fungsi pengemasan tambahan, kami tahu ukuran simpul pelacak).

Kami juga menggunakan ini untuk menjaga data profil biaya fungsi, untuk alasan yang sama; menulis entri untuk setiap panggilan fungsi dan kembali, serta sakelar ulir, bisa menjadi mahal dengan cepat. Alokasi kustom lagi memberi kita allocs lebih kecil di area memori debug yang lebih besar.

Leander
sumber
5

Saya menggunakan pengalokasi khusus untuk menghitung jumlah alokasi / alokasi di salah satu bagian dari program saya dan mengukur berapa lama. Ada cara lain yang bisa dicapai tetapi metode ini sangat nyaman bagi saya. Sangat berguna bahwa saya dapat menggunakan pengalokasi khusus hanya untuk sebagian dari wadah saya.

Jørgen Fogh
sumber
4

Satu situasi penting: Ketika menulis kode yang harus bekerja melintasi batas-batas modul (EXE / DLL), penting untuk menjaga alokasi dan penghapusan Anda terjadi hanya dalam satu modul.

Di mana saya bertemu ini adalah arsitektur Plugin di Windows. Sangat penting bahwa, misalnya, jika Anda meneruskan string std :: melintasi batas DLL, bahwa setiap realokasi string terjadi dari tumpukan di mana asalnya, BUKAN tumpukan di DLL yang mungkin berbeda *.

* Ini sebenarnya lebih rumit dari ini, seolah-olah Anda secara dinamis menghubungkan ke CRT, ini mungkin bisa dilakukan. Tetapi jika setiap DLL memiliki tautan statis ke CRT, Anda menuju ke dunia kesakitan, di mana kesalahan alokasi hantu terus terjadi.

Stephen
sumber
Jika Anda melewati objek melintasi batas DLL Anda harus menggunakan pengaturan Multi-threaded (Debug) DLL (/ MD (d)) untuk kedua sisi. C ++ tidak dirancang dengan dukungan modul. Atau Anda dapat melindungi segala sesuatu di balik antarmuka COM dan menggunakan CoTaskMemAlloc. Ini adalah cara terbaik untuk menggunakan antarmuka plugin yang tidak terikat pada kompiler, STL atau vendor tertentu.
gast128
Aturan orang tua untuk itu adalah: Jangan lakukan itu. Jangan gunakan jenis STL di DLL API. Dan jangan lewatkan tanggung jawab bebas memori dinamis melintasi batas DLL API. Tidak ada C ++ ABI - jadi jika Anda memperlakukan setiap DLL sebagai API C, Anda menghindari seluruh kelas masalah potensial. Dengan mengorbankan "kecantikan c ++", tentu saja. Atau seperti komentar lain: Gunakan COM. Just plain C ++ adalah ide yang buruk.
BitTickler
3

Salah satu contoh waktu saya saya gunakan ini bekerja dengan sistem embedded sangat terbatas sumber daya. Katakanlah Anda memiliki 2k ram gratis dan program Anda harus menggunakan sebagian dari memori itu. Anda perlu menyimpan mengatakan 4-5 urutan di suatu tempat yang tidak ada di tumpukan dan Anda perlu memiliki akses yang sangat tepat di mana hal-hal ini disimpan, ini adalah situasi di mana Anda mungkin ingin menulis pengalokasi Anda sendiri. Implementasi default dapat memecah-mecah memori, ini mungkin tidak dapat diterima jika Anda tidak memiliki cukup memori dan tidak dapat memulai kembali program Anda.

Satu proyek yang sedang saya kerjakan adalah menggunakan AVR-GCC pada beberapa chip berdaya rendah. Kami harus menyimpan 8 urutan panjang variabel tetapi dengan maksimum yang diketahui. Itu penerapan standar perpustakaan dari manajemen memoriadalah pembungkus tipis di sekitar malloc / free yang melacak di mana menempatkan item dengan mendahului setiap blok memori yang dialokasikan dengan pointer untuk hanya melewati ujung memori yang dialokasikan itu. Ketika mengalokasikan sepotong memori baru, pengalokasi standar harus berjalan di masing-masing bagian memori untuk menemukan blok berikutnya yang tersedia di mana ukuran memori yang diminta akan cocok. Pada platform desktop ini akan sangat cepat untuk beberapa item ini tetapi Anda harus ingat bahwa beberapa mikrokontroler ini sangat lambat dan primitif dibandingkan. Selain itu masalah fragmentasi memori adalah masalah besar yang berarti kami benar-benar tidak punya pilihan selain mengambil pendekatan yang berbeda.

Jadi yang kami lakukan adalah menerapkan kumpulan memori kami sendiri . Setiap blok memori cukup besar untuk memenuhi urutan terbesar yang kita butuhkan di dalamnya. Ini mengalokasikan blok memori berukuran tetap sebelumnya dan menandai blok memori mana yang saat ini digunakan. Kami melakukan ini dengan menjaga satu integer 8 bit di mana masing-masing bit mewakili jika blok tertentu digunakan. Kami menukar penggunaan memori di sini karena berusaha membuat seluruh proses lebih cepat, yang dalam kasus kami dibenarkan ketika kami mendorong chip mikrokontroler ini mendekati kapasitas pemrosesan maksimumnya.

Ada beberapa kali saya bisa melihat menulis pengalokasi kustom Anda sendiri dalam konteks sistem embedded, misalnya jika memori untuk urutan tidak dalam ram utama seperti yang sering terjadi pada platform ini .

antar jemput87
sumber
3

Tautan wajib ke pembicaraan CppCon 2015 Andrei Alexandrescu tentang pengalokasi:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

Yang menyenangkan adalah hanya dengan membuat mereka membuat Anda memikirkan ide-ide tentang bagaimana Anda akan menggunakannya :-)

einpoklum
sumber
2

Untuk memori bersama, sangat penting bahwa tidak hanya kepala wadah, tetapi juga data yang dikandungnya disimpan dalam memori bersama.

Pengalokasi Boost :: Interprocess adalah contoh yang baik. Namun, seperti yang dapat Anda baca di sini , semua ini tidak cukup, untuk membuat semua wadah STL kompatibel dengan memori yang kompatibel (Karena perbedaan pemetaan pemetaan dalam proses yang berbeda, pointer mungkin "pecah").

ted
sumber
2

Beberapa waktu lalu saya menemukan solusi ini sangat berguna bagi saya: Pengalokasi C ++ 11 yang cepat untuk wadah STL . Ini sedikit mempercepat wadah STL pada VS2017 (~ 5x) serta pada GCC (~ 7x). Ini adalah pengalokasi tujuan khusus berdasarkan kumpulan memori. Ini dapat digunakan dengan wadah STL hanya berkat mekanisme yang Anda minta.

tidak ada yang istimewa
sumber
1

Saya pribadi menggunakan Loki :: Allocator / SmallObject untuk mengoptimalkan penggunaan memori untuk objek kecil - ini menunjukkan efisiensi yang baik dan kinerja yang memuaskan jika Anda harus bekerja dengan sejumlah kecil benda yang sangat kecil (1 hingga 256 byte). Ini bisa sampai ~ 30 kali lebih efisien daripada standar C ++ alokasi baru / hapus jika kita berbicara tentang mengalokasikan sejumlah kecil objek kecil dengan ukuran berbeda. Juga, ada solusi khusus VC yang disebut "QuickHeap", ini membawa kinerja terbaik (mengalokasikan dan membatalkan alokasi operasi hanya membaca dan menulis alamat blok yang dialokasikan / dikembalikan ke tumpukan, masing-masing hingga 99. (9)% kasus - tergantung pada pengaturan dan inisialisasi), tetapi dengan biaya overhead yang penting - perlu dua petunjuk per luas dan satu tambahan untuk setiap blok memori baru. Itu'

Masalah dengan implementasi standar C ++ baru / hapus adalah bahwa itu biasanya hanya pembungkus untuk alokasi C malloc / gratis, dan itu berfungsi baik untuk blok memori yang lebih besar, seperti 1024+ byte. Ini memiliki overhead yang menonjol dalam hal kinerja dan, kadang-kadang, memori tambahan yang digunakan untuk pemetaan juga. Jadi, dalam kebanyakan kasus, pengalokasi kustom diterapkan dengan cara untuk memaksimalkan kinerja dan / atau meminimalkan jumlah memori tambahan yang diperlukan untuk mengalokasikan objek kecil (≤1024 byte).

Keragaman Fraktal
sumber
1

Dalam simulasi grafis, saya telah melihat alokasi kustom digunakan untuk

  1. Batasan keselarasan yang std::allocatortidak secara langsung mendukung.
  2. Minimalkan fragmentasi dengan menggunakan kumpulan terpisah untuk alokasi jangka pendek (hanya kerangka ini) dan jangka panjang.
Adrian McCarthy
sumber