std :: vector (ab) menggunakan penyimpanan otomatis

46

Pertimbangkan cuplikan berikut:

#include <array>
int main() {
  using huge_type = std::array<char, 20*1024*1024>;
  huge_type t;
}

Jelas itu akan crash pada sebagian besar platform, karena ukuran tumpukan standar biasanya kurang dari 20MB.

Sekarang pertimbangkan kode berikut:

#include <array>
#include <vector>

int main() {
  using huge_type = std::array<char, 20*1024*1024>;
  std::vector<huge_type> v(1);
}

Anehnya itu juga crash! Traceback (dengan salah satu versi libstdc ++ terbaru) mengarah ke include/bits/stl_uninitialized.hfile, di mana kita dapat melihat baris berikut:

typedef typename iterator_traits<_ForwardIterator>::value_type _ValueType;
std::fill(__first, __last, _ValueType());

Mengubah ukuran vectorkonstruktor harus secara default menginisialisasi elemen, dan ini adalah bagaimana itu diterapkan. Jelas, _ValueType()sementara crash stack.

Pertanyaannya adalah apakah itu implementasi yang sesuai. Jika ya, itu sebenarnya berarti penggunaan vektor tipe besar sangat terbatas, bukan?

Igor R.
sumber
Seseorang seharusnya tidak menyimpan objek besar dalam tipe array. Melakukan hal itu berpotensi membutuhkan wilayah yang sangat besar dari memori kontroversial yang mungkin tidak ada. Sebaliknya, miliki vektor pointer (std :: unique_ptr biasanya) sehingga Anda tidak menempatkan permintaan yang begitu tinggi pada memori Anda.
NathanOliver
2
Hanya memori. Ada implementasi C ++ yang berjalan yang tidak menggunakan memori virtual.
NathanOliver
3
Kompiler mana, btw? Saya tidak dapat mereproduksi dengan VS 2019 (16.4.2)
ChrisMM
3
Dari melihat kode libstdc ++, implementasi ini hanya digunakan jika tipe elemennya sepele dan dapat ditugaskan untuk menyalin dan jika default std::allocatordigunakan.
walnut
1
@ Damon Seperti yang saya sebutkan di atas tampaknya hanya digunakan untuk jenis sepele dengan pengalokasi default, jadi seharusnya tidak ada perbedaan yang dapat diamati.
walnut

Jawaban:

19

Tidak ada batasan berapa banyak penyimpanan otomatis yang digunakan API std.

Mereka semua bisa membutuhkan ruang penyimpanan 12 terabyte.

Namun, API itu hanya membutuhkan Cpp17DefaultInsertable, dan implementasi Anda menciptakan contoh tambahan atas apa yang dibutuhkan oleh konstruktor. Kecuali jika terjaga keamanannya mendeteksi objek itu sepele dan dapat disalin, implementasi itu terlihat ilegal.

Yakk - Adam Nevraumont
sumber
8
Dari melihat kode libstdc ++, implementasi ini hanya digunakan jika tipe elemennya sepele dan dapat ditugaskan untuk menyalin dan jika default std::allocatordigunakan. Saya tidak yakin mengapa kasus khusus ini dibuat sejak awal.
walnut
3
@walnut Yang berarti kompiler bebas untuk as-jika tidak benar-benar membuat objek sementara; Saya menduga ada peluang yang layak untuk pembuatan yang dioptimalkan dan tidak dibuat?
Yakk - Adam Nevraumont
4
Ya, saya kira itu bisa, tetapi untuk elemen besar GCC sepertinya tidak. Dentang dengan libstdc ++ memang mengoptimalkan sementara, tetapi tampaknya hanya jika ukuran vektor yang diteruskan ke konstruktor adalah konstanta waktu kompilasi, lihat godbolt.org/z/-2ZDMm .
walnut
1
@walnut case khusus ada di sana sehingga kami mengirim ke std::filluntuk jenis sepele, yang kemudian digunakan memcpyuntuk meledakkan byte ke tempat-tempat, yang berpotensi jauh lebih cepat daripada membangun banyak objek individu dalam satu lingkaran. Saya percaya implementasi libstdc ++ sudah sesuai, tetapi menyebabkan stack overflow untuk objek besar adalah bug Kualitas Implementasi (QoI). Saya telah melaporkannya sebagai gcc.gnu.org/PR94540 dan akan memperbaikinya.
Jonathan Wakely
@ JonathanWakely Ya, itu masuk akal. Saya tidak ingat mengapa saya tidak memikirkan itu ketika saya menulis komentar saya. Saya kira saya akan berpikir bahwa elemen default-dibangun pertama akan dibangun langsung di tempat dan kemudian orang dapat menyalinnya, sehingga tidak ada objek tambahan dari tipe elemen yang akan dibangun. Tapi tentu saja saya belum benar-benar memikirkan hal ini secara rinci dan saya tidak tahu masuk dan keluarnya penerapan perpustakaan standar. (Saya terlambat menyadari bahwa ini juga saran Anda dalam laporan bug.)
walnut
9
huge_type t;

Jelas itu akan crash pada sebagian besar platform ...

Saya membantah anggapan "sebagian besar". Karena memori dari objek besar tidak pernah digunakan, kompiler dapat sepenuhnya mengabaikannya dan tidak pernah mengalokasikan memori dalam hal ini tidak akan ada crash.

Pertanyaannya adalah apakah itu implementasi yang sesuai.

Standar C ++ tidak membatasi penggunaan stack, atau bahkan mengakui keberadaan stack. Jadi, ya itu sesuai dengan standar. Tetapi orang dapat menganggap ini sebagai kualitas masalah implementasi.

itu sebenarnya berarti bahwa penggunaan vektor tipe besar sangat terbatas, bukan?

Itu tampaknya menjadi kasus dengan libstdc ++. Kecelakaan itu tidak direproduksi dengan libc ++ (menggunakan dentang), jadi sepertinya ini bukan batasan dalam bahasa, melainkan hanya dalam implementasi tertentu.

eerorika
sumber
6
"tidak akan selalu macet meskipun tumpukan yang berlebihan karena memori yang dialokasikan tidak pernah diakses oleh program" - jika stack digunakan dengan cara apa pun setelah ini (misalnya untuk memanggil fungsi), ini akan macet bahkan pada platform yang terlalu banyak melakukan .
Ruslan
Platform apa pun yang tidak mengalami crash (dengan asumsi objek tidak berhasil dialokasikan) rentan terhadap Stack Clash.
user253751
@ user253751 Akan optimis untuk berasumsi bahwa sebagian besar platform / program tidak rentan.
eerorika
Saya pikir overcommit hanya berlaku untuk heap, bukan stack. Tumpukan memiliki batas atas tetap pada ukurannya.
Jonathan Wakely
@JonathanWakely Kamu benar. Tampaknya alasan mengapa tidak macet adalah karena kompiler tidak pernah mengalokasikan objek yang tidak digunakan.
eerorika
5

Saya bukan pengacara bahasa atau pakar standar C ++, tetapi cppreference.com mengatakan:

explicit vector( size_type count, const Allocator& alloc = Allocator() );

Buat wadah dengan jumlah instance T. yang dimasukkan tidak ada salinan.

Mungkin saya salah paham "dimasukkan secara default," tetapi saya berharap:

std::vector<huge_type> v(1);

menjadi setara dengan

std::vector<huge_type> v;
v.emplace_back();

Versi terakhir seharusnya tidak membuat salinan tumpukan tetapi membangun besar_type langsung di memori dinamis vektor.

Saya tidak dapat secara otoritatif mengatakan bahwa apa yang Anda lihat tidak sesuai, tetapi tentu saja bukan itu yang saya harapkan dari implementasi yang berkualitas.

Adrian McCarthy
sumber
4
Seperti yang saya sebutkan dalam komentar pada pertanyaan, libstdc ++ hanya menggunakan implementasi ini untuk tipe sepele dengan tugas penyalinan dan std::allocator, jadi seharusnya tidak ada perbedaan yang dapat diamati antara memasukkan langsung ke memori vektor dan membuat salinan perantara.
walnut
@walnut: Benar, tetapi alokasi tumpukan yang besar dan dampak kinerja dari init dan copy masih hal-hal yang tidak saya harapkan dari implementasi berkualitas tinggi.
Adrian McCarthy
2
Ya saya setuju. Saya pikir ini adalah kekeliruan dalam implementasi. Maksud saya hanya bahwa itu tidak masalah dalam hal kepatuhan standar.
kenari
IIRC Anda juga membutuhkan copyability atau movability untuk emplace_backtetapi tidak hanya membuat vektor. Yang berarti Anda dapat memiliki vector<mutex> v(1)tetapi tidak vector<mutex> v; v.emplace_back();Untuk sesuatu seperti huge_typeAnda mungkin masih memiliki alokasi dan memindahkan operasi lebih banyak dengan versi kedua. Seharusnya tidak membuat objek sementara.
dyp
1
@IgorR. vector::vector(size_type, Allocator const&)membutuhkan (Cpp17) DefaultInsertable
dyp