Clever Geek Handbook

STL, pengalokasi, memori bersama dan fitur-fiturnya



Memori bersama adalah cara tercepat untuk bertukar data antar proses. Tetapi tidak seperti mekanisme streaming (pipa, soket semua garis, antrian file ...), di sini programmer memiliki kebebasan penuh untuk bertindak, sebagai hasilnya, mereka menulis siapa yang mereka inginkan.



Jadi penulis pernah bertanya-tanya bagaimana jika ... jika ada penurunan alamat segmen memori bersama dalam proses yang berbeda. Ini sebenarnya yang terjadi ketika proses memori bersama bercabang, tetapi bagaimana dengan proses yang berbeda? Selain itu, tidak semua sistem memiliki garpu.



Tampaknya alamatnya bertepatan, lalu apa? Paling tidak, Anda dapat menggunakan petunjuk absolut dan ini akan menghemat banyak sakit kepala. Ini akan menjadi mungkin untuk bekerja dengan string dan kontainer C ++ yang dibangun dari memori bersama.



Omong-omong, contoh yang bagus. Bukan berarti penulis benar-benar menyukai STL, tetapi ini adalah kesempatan untuk mendemonstrasikan tes yang ringkas dan dapat dipahami untuk kinerja teknik yang diusulkan. Teknik yang memungkinkan (seperti yang terlihat) untuk secara signifikan menyederhanakan dan mempercepat komunikasi antar proses. Apakah itu berhasil dan bagaimana Anda harus membayar, kami akan memahami lebih lanjut.



pengantar



Ide memori bersama sederhana dan elegan - karena setiap proses beroperasi dalam ruang alamat virtualnya sendiri, yang diproyeksikan ke fisik seluruh sistem, jadi mengapa tidak mengizinkan dua segmen dari proses yang berbeda untuk melihat area memori fisik yang sama.



Dan dengan perkembangan sistem operasi 64-bit dan penggunaan cache yang koheren di mana-mana , gagasan tentang memori bersama mendapat angin kedua. Sekarang ini bukan hanya penyangga siklik - implementasi DIY dari "pipa", tetapi "pengalihan kontinum" yang nyata - perangkat yang sangat misterius dan kuat, terlebih lagi, hanya kemisteriusannya yang setara dengan kekuatannya.



Mari kita lihat beberapa contoh penggunaan.



  • “shared memory” MS SQL. (~10...15%)
  • Mysql Windows “shared memory”, .
  • Sqlite WAL-. , . (chroot).
  • PostgreSQL fork - . , .





    .1 PostgreSQL ()


Secara umum, memori bersama ideal seperti apa yang ingin kita lihat? Ini adalah jawaban yang mudah - kami berharap objek di dalamnya dapat digunakan seolah-olah itu adalah objek yang dibagikan di antara utas proses yang sama. Ya, Anda memerlukan sinkronisasi (dan Anda tetap membutuhkannya), tetapi sebaliknya, Anda hanya perlu mengambil dan menggunakannya! Mungkin ... itu bisa diatur.



Bukti konsep membutuhkan tugas yang minimal berarti :



  • ada analog dari std :: map <std :: string, std :: string> yang terletak di memori bersama
  • kami memiliki N proses yang secara asinkron menambah / mengubah nilai dengan awalan yang sesuai dengan nomor proses (mis .: key_1_ ... untuk nomor proses 1)
  • sebagai hasilnya, kita bisa mengontrol hasil akhirnya


Mari kita mulai dengan hal yang paling sederhana - karena kita memiliki std :: string dan std :: map , kita memerlukan pengalokasi STL khusus.



Alokator STL



Misalkan ada fungsi xalloc / xfree untuk bekerja dengan memori bersama sebagai analog malloc / free . Dalam kasus ini, pengalokasi terlihat seperti ini: 



template <typename T>
class stl_buddy_alloc
{
public:
	typedef T                 value_type;
	typedef value_type*       pointer;
	typedef value_type&       reference;
	typedef const value_type* const_pointer;
	typedef const value_type& const_reference;
	typedef ptrdiff_t         difference_type;
	typedef size_t            size_type;
public:
	stl_buddy_alloc() throw()
	{	// construct default allocator (do nothing)
	}
	stl_buddy_alloc(const stl_buddy_alloc<T> &) throw()
	{	// construct by copying (do nothing)
	}
	template<class _Other>
	stl_buddy_alloc(const stl_buddy_alloc<_Other> &) throw()
	{	// construct from a related allocator (do nothing)
	}

	void deallocate(pointer _Ptr, size_type)
	{	// deallocate object at _Ptr, ignore size
		xfree(_Ptr);
	}
	pointer allocate(size_type _Count)
	{	// allocate array of _Count elements
		return (pointer)xalloc(sizeof(T) * _Count);
	}
	pointer allocate(size_type _Count, const void *)
	{	// allocate array of _Count elements, ignore hint
		return (allocate(_Count));
	}
};


Ini cukup untuk mengaitkan std :: map & std :: string padanya 




template <typename _Kty, typename _Ty>
class q_map : 
    public std::map<
        _Kty, 
        _Ty, 
        std::less<_Kty>, 
        stl_buddy_alloc<std::pair<const _Kty, _Ty> > 
    >
{ };

typedef std::basic_string<
        char, 
        std::char_traits<char>, 
        stl_buddy_alloc<char> > q_string


Sebelum berurusan dengan fungsi xalloc / xfree yang dideklarasikan , yang bekerja dengan pengalokasi di atas memori bersama, ada baiknya memahami memori bersama itu sendiri.



Berbagi memori



Utas yang berbeda dari proses yang sama berada di ruang alamat yang sama, yang berarti bahwa setiap penunjuk non- utas_lokal di utas apa pun melihat tempat yang sama. Dengan memori bersama, dibutuhkan upaya ekstra untuk mencapai efek ini.



Windows



  • Mari buat file ke pemetaan memori. Memori bersama, seperti memori biasa, ditutupi oleh mekanisme paging, di sini, antara lain, ditentukan apakah kita akan menggunakan paging bersama atau mengalokasikan file khusus untuk ini. 



    HANDLE hMapFile = CreateFileMapping(
	INVALID_HANDLE_VALUE,     // use paging file
	NULL,                     // default security
	PAGE_READWRITE,           // read/write access
	(alloc_size >> 32)        // maximum object size (high-order DWORD)
	(alloc_size & 0xffffffff),// maximum object size (low-order DWORD)
	"Local\\SomeData");       // name of mapping object


    Awalan nama file "Lokal \\" berarti bahwa objek akan dibuat di namespace lokal sesi.
  • Untuk bergabung dengan pemetaan yang sudah dibuat oleh proses lain, gunakan 



    HANDLE hMapFile = OpenFileMapping(
	FILE_MAP_ALL_ACCESS,      // read/write access
	FALSE,                    // do not inherit the name
	"Local\\SomeData");       // name of mapping object
  • Sekarang Anda perlu membuat segmen yang menunjuk ke tampilan yang sudah jadi 



    void *hint = (void *)0x200000000000ll;
unsigned char *shared_ptr = (unsigned char*)MapViewOfFileEx(
	hMapFile,                 // handle to map object
	FILE_MAP_ALL_ACCESS,      // read/write permission
	0,                        // offset in map object (high-order DWORD)
	0,                        // offset in map object (low-order DWORD)
	0,                        // segment size,
	hint);                    //


    ukuran segmen 0 berarti bahwa ukuran tampilan yang dibuat, dengan mempertimbangkan pergeseran, akan digunakan.



    Yang terpenting di sini adalah petunjuk. Jika tidak ditentukan (NULL), sistem akan memilih alamat sesuai kebijakannya. Tetapi jika nilainya bukan nol, upaya akan dilakukan untuk membuat segmen dengan ukuran yang diinginkan dengan alamat yang diinginkan. Dengan mendefinisikan nilainya sebagai hal yang sama dalam proses yang berbeda, kami mencapai degenerasi alamat memori bersama. Dalam mode 32-bit, menemukan potongan besar ruang alamat yang bersebelahan yang tidak terisi tidaklah mudah, dalam mode 64-bit tidak ada masalah seperti itu, Anda selalu dapat menemukan sesuatu yang cocok.


Linux



Semuanya pada dasarnya sama di sini.



  • Buat objek memori bersama 



      int fd = shm_open(
                 “/SomeData”,               //  ,   /
                 O_CREAT | O_EXCL | O_RDWR, // flags,  open
                 S_IRUSR | S_IWUSR);        // mode,  open

  ftruncate(fd, alloc_size);


    ftruncate . shm_open /dev/shm/. shmget\shmat SysV, ftok (inode ).




  • int fd = shm_open(“/SomeData”, O_RDWR, 0);




  •   void *hint = (void *)0x200000000000ll;
  unsigned char *shared_ptr = (unsigned char*) = mmap(
                   hint,                      // 
                   alloc_size,                // segment size,
                   PROT_READ | PROT_WRITE,    // protection flags
                   MAP_SHARED,                // sharing flags
                   fd,                        // handle to map object
                   0);                        // offset


    hint.




Mengenai petunjuk, apa batasan nilainya? Sebenarnya ada berbagai macam batasan.



Pertama , arsitektural / hardware. Beberapa kata harus dikatakan di sini tentang bagaimana alamat virtual berubah menjadi alamat fisik. Jika ada cache TLB yang terlewat , Anda harus mengakses struktur pohon yang disebut tabel halaman . Misalnya, di IA-32 terlihat seperti ini:





Gbr. 2 kasus halaman 4K, diambil di sini



Masuk ke pohon adalah isi dari register CR3, indeks di halaman-halaman tingkat yang berbeda adalah fragmen dari alamat virtual. Dalam hal ini, 32 bit menjadi 32 bit, semuanya adil.



Di AMD64, gambar terlihat sedikit berbeda.





Gambar. 3 AMD64, 4K halaman, diambil dari sini



CR3 sekarang memiliki 40 bit signifikan, bukan 20 sebelumnya, dalam pohon 4 level halaman, alamat fisik dibatasi hingga 52 bit sedangkan alamat virtual dibatasi hingga 48 bit.



Dan hanya dalam (dimulai dengan) mikroarsitektur Ice Lake (Intel) yang diizinkan untuk menggunakan 57 bit alamat virtual (dan masih 52 fisik) saat bekerja dengan tabel halaman 5 tingkat.



Sejauh ini, kami hanya berbicara tentang Intel / AMD. Hanya untuk perubahan, dalam arsitektur Aarch64 , tabel halaman bisa 3 atau 4 level, memungkinkan penggunaan 39 atau 48 bit di alamat virtual, masing-masing ( 1 ).



Kedua, pembatasan perangkat lunak. Microsoft, secara khusus, memberlakukan (44 bit hingga 8.1 / Server12, 48 mulai dari) opsi-opsi OS yang berbeda berdasarkan, antara lain, pertimbangan pemasaran.



Ngomong-ngomong, 48 digit, ini masing-masing 65 ribu kali 4GB, mungkin di ruang terbuka seperti itu selalu ada sudut tempat Anda bisa tetap berpegang pada petunjuk Anda.



Pengalokasi memori bersama



Pertama-tama. Pengalokasi harus hidup di memori bersama yang dialokasikan, menempatkan semua data internalnya di sana.



Kedua. Kita berbicara tentang alat komunikasi antar proses, setiap pengoptimalan yang terkait dengan penggunaan TLS tidak relevan.



Ketiga. Karena beberapa proses terlibat, pengalokasi itu sendiri dapat hidup untuk waktu yang sangat lama, mengurangi fragmentasi memori eksternal menjadi sangat penting .



Keempat. Memanggil OS untuk memori tambahan tidak diperbolehkan. Jadi, dlmalloc , misalnya, mengalokasikan potongan yang relatif besar secara langsung melalui mmap . Ya, itu bisa disapih dengan menaikkan ambang batas, tapi tetap saja.



Kelima. Fasilitas sinkronisasi dalam proses standar tidak cocok, baik global dengan overhead yang sesuai atau sesuatu yang terletak langsung di memori bersama, seperti spinlock, diperlukan. Katakanlah terima kasih untuk cache yang koheren. Dalam posix ada juga semaphore bersama tanpa nama untuk kasus ini .



Secara total, dengan mempertimbangkan semua hal di atas dan juga karena ada pengalokasi langsung dengan metode kembar (ramah disediakan oleh Alexander Artyushin, sedikit direvisi), pilihan ternyata mudah.



Mari kita tinggalkan deskripsi detail implementasi hingga waktu yang lebih baik, sekarang antarmuka publiknya menarik: 



class BuddyAllocator {
public:
	BuddyAllocator(uint64_t maxCapacity, u_char * buf, uint64_t bufsize);
	~BuddyAllocator(){};

	void *allocBlock(uint64_t nbytes);
	void freeBlock(void *ptr);
...
};


Penghancur itu sepele karena BuddyAllocator tidak mengambil sumber daya asing.



Persiapan akhir



Karena semuanya berada di memori bersama, memori ini harus memiliki header. Untuk pengujian kami, header ini terlihat seperti ini: 



struct glob_header_t {
	//     magic
	uint64_t magic_;
	// hint     
	const void *own_addr_;
	//  
	BuddyAllocator alloc_;
	// 
	std::atomic_flag lock_;
	//   
	q_map<q_string, q_string> q_map_;

	static const size_t alloc_shift = 0x01000000;
	static const size_t balloc_size = 0x10000000;
	static const size_t alloc_size = balloc_size + alloc_shift;
	static glob_header_t *pglob_;
};
static_assert (
    sizeof(glob_header_t) < glob_header_t::alloc_shift, 
    "glob_header_t size mismatch");

glob_header_t *glob_header_t::pglob_ = NULL;


  • own_addr_ ditulis saat membuat memori bersama sehingga setiap orang yang melampirkannya dengan nama dapat mengetahui alamat sebenarnya (petunjuk) dan menghubungkan kembali jika perlu
  • tidak baik untuk membuat kode keras dimensi seperti ini, tetapi dapat diterima untuk pengujian
  • konstruktor harus dipanggil dengan proses membuat memori bersama, terlihat seperti ini: 



    glob_header_t::pglob_ = (glob_header_t *)shared_ptr;

new (&glob_header_t::pglob_->alloc_)
        qz::BuddyAllocator(
                //  
                glob_header_t::balloc_size,
                //  
                shared_ptr + glob_header_t::alloc_shift,
                //   
                glob_header_t::alloc_size - glob_header_t::alloc_shift;

new (&glob_header_t::pglob_->q_map_) 
                q_map<q_string, q_string>();

glob_header_t::pglob_->lock_.clear();
  • proses menghubungkan ke memori bersama menyiapkan semuanya
  • sekarang kami memiliki semua yang kami butuhkan untuk pengujian kecuali fungsi xalloc / xfree 



    void *xalloc(size_t size)
{
	return glob_header_t::pglob_->alloc_.allocBlock(size);
}
void xfree(void* ptr)
{
	glob_header_t::pglob_->alloc_.freeBlock(ptr);
}


Sepertinya Anda bisa mulai.



Percobaan



Tesnya sendiri sangat sederhana: 



for (int i = 0; i < 100000000; i++)
{
        char buf1[64];
        sprintf(buf1, "key_%d_%d", curid, (i % 100) + 1);
        char buf2[64];
        sprintf(buf2, "val_%d", i + 1);

        LOCK();

        qmap.erase(buf1); //   
        qmap[buf1] = buf2;

        UNLOCK();
}


Curid adalah proses / nomor utas, proses yang membuat memori bersama memiliki nol curid, tetapi tidak masalah untuk pengujian.

Qmap , LOCK / UNLOCK berbeda untuk pengujian yang berbeda.



Mari lakukan beberapa tes



  1. THR_MTX - aplikasi multithread, sinkronisasi melalui std :: recursive_mutex ,

    qmap - global std :: map <std :: string, std :: string>
  2. THR_SPN adalah aplikasi multithread, sinkronisasi melalui spinlock: 



    std::atomic_flag slock;
..
while (slock.test_and_set(std::memory_order_acquire));  // acquire lock
…
slock.clear(std::memory_order_release);                 // release lock


    qmap - global std :: map <std :: string, std :: string>
  3. PRC_SPN - beberapa proses yang berjalan, sinkronisasi melewati spinlock: 



    while (glob_header_t::pglob_->lock_.test_and_set(              // acquire lock
        std::memory_order_acquire));                          
…
glob_header_t::pglob_->lock_.clear(std::memory_order_release); // release lock
    qmap - glob_header_t :: pglob _-> q_map_
  4. PRC_MTX - beberapa proses yang berjalan, sinkronisasi melalui mutex bernama .



    qmap - glob_header_t :: pglob _-> q_map_


Hasil (jenis pengujian vs. jumlah proses / utas):

1 2 4 8 enambelas
THR_MTX 1'56 '' 5'41 '' 7'53 '' 51'38 '' 185'49
THR_SPN 1'26 '' 7'38 '' 25'30 '' 103'29 '' 347'04 ''
PRC_SPN 1'24 '' 7'27 '' 24'02 '' 92'34 '' 322'41 ''
PRC_MTX 4'55 '' 13'01 '' 78'14 '' 133'25 '' 357'21 ''


Percobaan dilakukan pada komputer prosesor ganda (48 core) dengan Xeon® Gold 5118 2.3GHz, Windows Server 2016.



Total



  • Ya, dimungkinkan untuk menggunakan objek / kontainer STL (dialokasikan dalam memori bersama) dari proses yang berbeda , asalkan dirancang dengan tepat.
  • , , PRC_SPN THR_SPN. , BuddyAllocator malloc\free MS ( ).
  • . — + std::mutex . lock-free , .




Memori bersama sering digunakan untuk mentransfer aliran data yang besar sebagai semacam "pipa" yang dibuat dengan tangan. Ini adalah ide bagus meskipun Anda perlu mengatur sinkronisasi yang mahal antar proses. Kami melihat bahwa itu tidak murah pada tes PRC_MTX, ketika bekerja, bahkan tanpa persaingan, dalam satu proses menurunkan kinerja secara signifikan.



Penjelasan untuk biaya tinggi sederhana, jika std: (recursive_) mutex (bagian kritis di bawah windows) dapat bekerja seperti spinlock, maka mutex bernama adalah panggilan sistem, memasuki mode kernel dengan biaya yang sesuai. Juga, hilangnya konteks eksekusi oleh utas / proses selalu sangat mahal.



Tetapi karena sinkronisasi proses tidak dapat dihindari, bagaimana kita dapat mengurangi biaya? Jawabannya telah lama ditemukan - buffering. Tidak setiap paket disinkronkan, tetapi sejumlah data - buffer tempat data ini diserialkan. Jika buffer terlihat lebih besar dari ukuran paket, Anda harus lebih jarang melakukan sinkronisasi.



Lebih mudah untuk menggabungkan dua teknik - data dalam memori bersama, dan hanya pointer relatif (dari awal memori bersama) yang dikirim melalui saluran data antarproses (misal: loop melalui localhost). Karena penunjuk biasanya lebih kecil dari paket data, menghemat sinkronisasi.



Dan jika proses yang berbeda memiliki akses ke memori bersama di alamat virtual yang sama, Anda dapat menambahkan sedikit performa lagi.



  • jangan membuat serial data untuk dikirim, jangan deserialisasi saat diterima
  • mengirimkan petunjuk jujur ​​ke objek yang dibuat dalam memori bersama melalui aliran
  • ketika kita mendapatkan objek siap (pointer), kita menggunakannya, lalu kita menghapusnya melalui penghapusan biasa, semua memori secara otomatis dibebaskan. Ini menyelamatkan kita dari mengotak-atik buffer cincin.
  • Anda bahkan tidak dapat mengirim pointer, tetapi (seminimal mungkin - satu byte dengan nilai "Anda memiliki email") pemberitahuan tentang fakta bahwa ada sesuatu dalam antrian


Akhirnya



Apa yang boleh dan tidak boleh dilakukan dengan objek memori bersama.



  1. Gunakan RTTI . Untuk alasan yang jelas. Objek std :: type_info ada di luar memori bersama dan tidak tersedia di seluruh proses.
  2. Gunakan metode virtual. Untuk alasan yang sama. Tabel fungsi virtual dan fungsinya sendiri tidak tersedia di seluruh proses.
  3. Jika kita berbicara tentang STL, semua file yang dapat dieksekusi dari proses yang berbagi memori harus dikompilasi oleh kompilator yang sama dengan pengaturan yang sama, dan STL itu sendiri harus sama.


PS : terima kasih kepada Alexander Artyushin dan Dmitry Iptyshev (Dmitria) untuk membantu menyiapkan artikel ini.


More articles:


All Articles