Bukankah penggunaan variabel pointer overhead memori?

Dalam bahasa seperti C dan C ++, saat menggunakan pointer ke variabel kita perlu satu lokasi memori lagi untuk menyimpan alamat itu. Jadi bukankah ini overhead memori? Bagaimana ini dikompensasi? Apakah pointer digunakan dalam aplikasi kritis memori rendah waktu?

Sebenarnya, overhead tidak benar-benar terletak pada tambahan 4 atau 8 byte yang dibutuhkan untuk menyimpan pointer. Pointer yang paling sering digunakan untuk alokasi memori dinamis , yang berarti bahwa kita memanggil fungsi untuk mengalokasikan blok memori, dan fungsi ini mengembalikan kepada kita pointer yang menunjuk ke blok memori itu. Blok baru ini dengan sendirinya mewakili overhead yang besar.

Sekarang, Anda tidak harus terlibat dalam alokasi memori untuk menggunakan pointer: Anda dapat memiliki array yang intdinyatakan secara statis atau di stack, dan Anda dapat menggunakan pointer alih-alih indeks untuk mengunjungi ints, dan itu adalah semua sangat bagus dan sederhana dan efisien. Tidak ada alokasi memori yang dibutuhkan, dan pointer biasanya akan menempati ruang yang persis sama dengan memori dalam indeks integer.

Juga, seperti yang diingatkan oleh Joshua Taylor dalam komentar, petunjuk digunakan untuk melewatkan sesuatu dengan referensi. Misalnya, struct foo f; init_foo(&f);akan mengalokasikan f pada stack dan kemudian memanggil init_foo()dengan pointer ke sana struct. Itu sangat umum. (Berhati-hatilah untuk tidak melewatkan pointer itu "ke atas".) Dalam C ++ Anda mungkin melihat ini dilakukan dengan "referensi" ( foo&) alih-alih sebuah pointer, tetapi referensi tidak lain adalah pointer yang tidak boleh Anda ubah, dan mereka menempati jumlah memori yang sama.

Tetapi alasan utama mengapa pointer digunakan adalah untuk alokasi memori dinamis, dan ini dilakukan untuk memecahkan masalah yang tidak dapat diselesaikan sebaliknya. Berikut adalah contoh sederhana: Bayangkan Anda ingin membaca seluruh isi file. Di mana Anda akan menyimpannya? Jika Anda mencoba dengan buffer ukuran tetap, maka Anda hanya akan bisa membaca file yang tidak lebih lama dari buffer itu. Tetapi dengan menggunakan alokasi memori, Anda dapat mengalokasikan memori sebanyak yang diperlukan untuk membaca file, dan kemudian melanjutkan untuk membacanya.

Juga, C ++ adalah bahasa berorientasi objek, dan ada beberapa aspek OOP seperti abstraksi yang hanya dapat dicapai dengan menggunakan pointer. Bahkan bahasa-bahasa seperti Java dan C # menggunakan pointer secara ekstensif , mereka hanya tidak memungkinkan Anda untuk memanipulasi pointer secara langsung, sehingga dapat mencegah Anda melakukan hal-hal berbahaya dengannya, tetapi tetap saja, bahasa-bahasa ini baru mulai masuk akal begitu Anda memiliki menyadari bahwa di balik layar semuanya dilakukan dengan menggunakan pointer.

Jadi, pointer tidak hanya digunakan dalam aplikasi waktu-kritis, memori rendah, mereka digunakan di mana-mana .

Jadi bukankah ini overhead memori?

Tentu, alamat tambahan (umumnya 4/8 byte tergantung pada prosesor).

Bagaimana ini dikompensasi?

Bukan itu. Jika Anda memerlukan tipuan yang diperlukan untuk pointer, maka Anda bisa membayarnya.

Apakah pointer digunakan dalam aplikasi kritis memori rendah waktu?

Saya belum melakukan banyak pekerjaan di sana, tetapi saya akan berasumsi begitu. Akses pointer adalah aspek dasar dari pemrograman perakitan. Dibutuhkan sejumlah kecil memori dan operasi penunjuk yang cepat - bahkan dalam konteks aplikasi semacam ini.

Saya tidak memiliki putaran yang sama dalam hal ini dengan Telastyn.

Sistem global dalam prosesor yang disematkan dapat dialamatkan dengan alamat yang spesifik dan dikodekan keras.

Globals dalam suatu program akan dialamatkan sebagai offset dari pointer khusus yang menunjuk ke tempat di memori tempat global dan statika disimpan.

Variabel lokal muncul ketika suatu fungsi dimasukkan dan dialamatkan sebagai offset dari pointer khusus lain, sering disebut "frame pointer". Ini termasuk argumen ke fungsi. Jika Anda berhati-hati dengan push dan pops dengan penunjuk tumpukan, Anda bisa menghilangkan frame pointer dan mengakses variabel lokal langsung dari penumpukan tumpukan.

Jadi Anda membayar tidak langsung dari pointer apakah Anda melangkah melalui array atau hanya mengambil beberapa variabel lokal atau global yang biasa-biasa saja. Itu hanya berdasarkan pada pointer yang berbeda, tergantung pada variabel apa itu. Kode yang dikompilasi dengan baik akan menyimpan pointer itu dalam register CPU, daripada memuatnya kembali setiap kali digunakan.

Ya tentu saja. Tapi itu tindakan penyeimbangan.

Aplikasi dengan memori rendah biasanya dibangun dengan mempertimbangkan pertukaran antara overhead dari beberapa variabel pointer dibandingkan dengan overhead dari apa yang akan menjadi program besar (yang harus disimpan dalam memori, ingat!) Jika pointer tidak dapat digunakan .

Pertimbangan ini berlaku untuk semua program, karena tidak ada yang ingin membuat kekacauan yang mengerikan, tidak dapat dipelihara dengan kode duplikat kiri kanan dan tengah, itu dua puluh kali lebih besar dari yang seharusnya.

Dalam bahasa seperti C dan C ++, saat menggunakan pointer ke variabel kita perlu satu lokasi memori lagi untuk menyimpan alamat itu. Jadi bukankah ini overhead memori?

Anda menganggap bahwa pointer perlu disimpan. Tidak selalu demikian. Setiap variabel disimpan di beberapa alamat memori. Katakanlah Anda telah longmenyatakan sebagai long n = 5L;. Ini mengalokasikan penyimpanan untuk ndi beberapa alamat. Kita dapat menggunakan alamat itu untuk melakukan hal-hal mewah seperti *((char *) &n) = (char) 0xFF;memanipulasi bagian n. Alamat ntidak disimpan di mana pun sebagai overhead tambahan.

Bagaimana ini dikompensasi?

Bahkan jika pointer disimpan secara eksplisit (misalnya dalam struktur data seperti daftar), struktur data yang dihasilkan seringkali lebih elegan (lebih sederhana, lebih mudah dipahami, lebih mudah ditangani, dll) daripada struktur data yang setara tanpa pointer.

Apakah pointer digunakan dalam aplikasi kritis memori rendah waktu?

Iya nih. Perangkat yang menggunakan pengendali mikro sering mengandung sangat sedikit memori tetapi firmware mungkin menggunakan pointer untuk menangani vektor interupsi atau manajemen buffer, dll.

Memiliki pointer pasti menghabiskan beberapa overhead, tetapi Anda dapat melihat sisi atas juga. Pointer seperti indeks. Dalam C Anda dapat menggunakan struktur data yang kompleks seperti string dan struktur karena pointer saja.

Bahkan misalkan Anda ingin melewatkan variabel dengan referensi maka mudah untuk mempertahankan pointer daripada mereplikasi seluruh struktur dan menyinkronkan perubahan di antara mereka (bahkan untuk menyalinnya, Anda perlu pointer). Bagaimana Anda menangani alokasi memori yang tidak bersebelahan dan de-alokasi tanpa pointer?

Bahkan variabel normal Anda memiliki entri dalam tabel simbol yang menyimpan alamat tempat variabel Anda mengarah. Jadi, saya tidak berpikir itu menciptakan banyak overhead dalam hal memori (hanya 4 atau 8 byte). Bahkan bahasa seperti java menggunakan pointer secara internal (referensi), mereka hanya tidak membiarkan Anda memanipulasi mereka karena itu akan membuat JVM kurang aman.

Anda harus menggunakan pointer hanya ketika Anda tidak memiliki pilihan lain seperti tipe data yang hilang, struktur (dalam c) karena menggunakan pointer dapat menyebabkan kesalahan jika tidak ditangani dengan benar dan relatif lebih sulit untuk debug.

Jadi bukankah ini overhead memori?

Ya Tidak mungkin?

Ini adalah pertanyaan yang aneh karena bayangkan rentang pengalamatan memori pada mesin, dan perangkat lunak yang perlu terus melacak di mana segala sesuatu berada dalam memori dengan cara yang tidak dapat diikat ke tumpukan.

Misalnya, bayangkan pemutar musik di mana file musik dimuat pada tombol yang ditekan oleh pengguna dan dibongkar dari memori yang tidak stabil ketika pengguna mencoba memuat file musik lain.

Bagaimana kita melacak di mana data audio disimpan? Kami membutuhkan alamat memori untuk itu. Program ini tidak hanya perlu melacak potongan data audio dalam memori tetapi juga di mana itu berada dalam memori. Jadi kita perlu menyimpan alamat memori (yaitu, pointer). Dan ukuran penyimpanan yang diperlukan untuk alamat memori akan cocok dengan rentang pengalamatan mesin (mis: pointer 64-bit untuk rentang pengalamatan 64-bit).

Jadi itu semacam "ya", itu memang membutuhkan penyimpanan untuk melacak alamat memori, tetapi tidak seperti kita dapat menghindarinya untuk memori yang dialokasikan secara dinamis semacam ini.

Bagaimana ini dikompensasi?

Berbicara tentang ukuran pointer itu sendiri, Anda dapat menghindari biaya dalam beberapa kasus dengan menggunakan stack, misalnya Dalam kasus itu, kompiler dapat menghasilkan instruksi yang secara efektif meng-hard-code alamat memori relatif, menghindari biaya pointer. Namun ini membuat Anda rentan untuk menumpuk luapan jika Anda melakukan ini untuk alokasi yang besar dan berukuran variabel, dan juga cenderung tidak praktis (jika bukan tidak mungkin dilakukan) untuk serangkaian cabang kompleks yang digerakkan oleh input pengguna (seperti dalam contoh audio) atas).

Cara lain adalah dengan menggunakan struktur data yang lebih berdekatan. Misalnya, urutan berbasis array dapat digunakan sebagai pengganti daftar dua kali lipat yang membutuhkan dua pointer per node. Kita juga dapat menggunakan gabungan keduanya seperti daftar yang tidak terbuka yang menyimpan hanya pointer di antara setiap kelompok elemen N yang berdekatan.

Apakah pointer digunakan dalam aplikasi kritis memori rendah waktu?

Ya, sangat umum demikian, karena banyak aplikasi kinerja kritis ditulis dalam C atau C ++ yang didominasi oleh penggunaan pointer (mereka mungkin berada di belakang smart pointer atau wadah seperti std::vectoratau std::string, tetapi mekanika yang mendasarinya mendidih menjadi sebuah pointer yang digunakan untuk melacak alamat ke blok memori dinamis).

Sekarang kembali ke pertanyaan ini:

Bagaimana ini dikompensasi? (Bagian kedua)

Pointer biasanya sangat murah kecuali Anda menyimpan jutaan seperti itu (yang masih sangat kecil * 8 megabita pada mesin 64-bit).

_{* Perhatikan ketika Ben menunjukkan bahwa "sangat" 8 MB masih seukuran L3 cache. Di sini saya menggunakan "sangat" dalam arti penggunaan DRAM total dan ukuran relatif tipikal pada memori, penggunaan pointer yang sehat.}

Di mana pointer menjadi mahal bukanlah pointer itu sendiri tetapi:

1. Alokasi memori dinamis. Alokasi memori dinamis cenderung mahal karena harus melalui struktur data yang mendasarinya (mis: buddy atau pengalokasi slab). Meskipun ini sering dioptimalkan sampai mati, mereka bertujuan umum dan dirancang untuk menangani blok berukuran variabel yang mengharuskan mereka melakukan setidaknya sedikit pekerjaan yang menyerupai "pencarian" (walaupun ringan dan mungkin bahkan waktu konstan) untuk temukan set bebas halaman yang berdekatan di memori.

2. Akses memori. Ini cenderung menjadi masalah besar yang perlu dikhawatirkan. Setiap kali kita mengakses memori yang dialokasikan secara dinamis untuk pertama kalinya, ada kesalahan halaman wajib serta cache kehilangan memindahkan memori ke bawah hierarki memori dan turun ke register.

Akses Memori

Akses memori adalah salah satu aspek kinerja yang paling penting di luar algoritma. Banyak bidang yang sangat kritis terhadap kinerja seperti mesin game AAA memusatkan banyak energi mereka ke optimisasi berorientasi data yang bermuara pada pola dan tata letak akses memori yang lebih efisien.

Salah satu kesulitan kinerja terbesar dari bahasa tingkat tinggi yang ingin mengalokasikan setiap jenis yang ditentukan pengguna secara terpisah melalui pengumpul sampah, misalnya, adalah mereka dapat memecah-mecah memori sedikit. Ini bisa benar terutama jika tidak semua objek dialokasikan sekaligus.

Dalam kasus tersebut, jika Anda menyimpan daftar sejuta contoh tipe objek yang ditentukan pengguna, mengakses instans-instans tersebut secara berurutan dalam satu loop mungkin cukup lambat karena dianalogikan dengan daftar sejuta petunjuk yang menunjuk ke wilayah memori yang berbeda. Dalam kasus tersebut, arsitektur ingin mengambil memori dari tingkat atas, lebih lambat, tingkat hierarki yang lebih besar pada bongkahan besar yang disejajarkan dengan harapan bahwa data di sekitar bongkahan tersebut akan diakses sebelum penggusuran. Ketika setiap objek dalam daftar tersebut dialokasikan secara terpisah, maka seringkali kita berakhir membayarnya dengan cache misses ketika setiap iterasi berikutnya mungkin harus memuat dari area yang sama sekali berbeda dalam memori tanpa objek yang berdekatan diakses sebelum penggusuran.

Banyak kompiler untuk bahasa-bahasa seperti ini melakukan pekerjaan yang sangat bagus akhir-akhir ini dalam pemilihan instruksi dan alokasi register, tetapi kurangnya lebih banyak kontrol langsung terhadap manajemen memori di sini dapat menjadi pembunuh (walaupun sering lebih sedikit rawan kesalahan) dan masih membuat bahasa seperti C dan C ++ cukup populer.

Secara tidak langsung Mengoptimalkan Akses Pointer

Dalam skenario yang paling kritis terhadap kinerja, aplikasi sering menggunakan kumpulan memori yang menyatukan memori dari potongan yang berdekatan untuk meningkatkan lokalitas referensi. Dalam kasus seperti itu, bahkan struktur yang ditautkan seperti pohon atau daftar tertaut dapat dibuat ramah-cache asalkan tata letak memori dari node-node tersebut berdekatan. Ini secara efektif membuat pointer dereferencing lebih murah, meskipun secara tidak langsung dengan meningkatkan lokalitas referensi yang terlibat ketika mendereferensi mereka.

Mengejar Pointers Sekitar

Asumsikan kita memiliki daftar yang terhubung sendiri seperti:

Foo->Bar->Baz->null

Masalahnya adalah bahwa jika kita mengalokasikan semua node secara terpisah terhadap pengalokasi tujuan umum (dan mungkin tidak semuanya sekaligus), memori sebenarnya mungkin agak tersebar seperti ini (diagram yang disederhanakan):

Ketika kita mulai mengejar pointer di sekitar dan mengakses Foonode, kita mulai dengan kehilangan wajib (dan mungkin kesalahan halaman) memindahkan potongan dari wilayah memorinya dari daerah memori yang lebih lambat ke daerah memori yang lebih cepat, seperti:

Hal ini menyebabkan kami untuk men-cache (mungkin juga halaman) wilayah memori hanya untuk mengakses sebagian darinya dan mengusir sisanya saat kami mengejar petunjuk di sekitar daftar ini. Namun, dengan mengambil kendali atas pengalokasi memori, kami dapat mengalokasikan daftar seperti itu secara bersebelahan seperti:

... dan dengan demikian secara signifikan meningkatkan kecepatan di mana kita dapat mengubah referensi ini dan memproses poinee mereka. Jadi, meskipun sangat tidak langsung, kita dapat mempercepat akses pointer dengan cara ini. Tentu saja jika kita hanya menyimpannya secara berdekatan dalam array, kita tidak akan memiliki masalah ini di tempat pertama, tetapi pengalokasi memori di sini memberi kita kontrol eksplisit atas tata letak memori dapat menghemat hari ketika struktur terkait diperlukan.

_{* Catatan: ini adalah diagram dan diskusi yang sangat disederhanakan tentang hierarki memori dan lokalitas referensi, tetapi mudah-mudahan ini sesuai untuk tingkat pertanyaan.}

Jadi bukankah ini overhead memori?

Ini memang overhead memori, tetapi yang sangat kecil (sampai-sampai tidak penting).

Bagaimana ini dikompensasi?

Itu tidak dikompensasi. Anda perlu menyadari bahwa akses data melalui pointer (dereferencing pointer) sangat cepat (jika saya ingat dengan benar, hanya menggunakan satu instruksi perakitan per dereferensi). Cukup cepat sehingga dalam banyak kasus akan menjadi alternatif tercepat yang Anda miliki.

Apakah pointer digunakan dalam aplikasi kritis memori rendah waktu?

Iya nih.

Anda hanya membutuhkan penggunaan memori tambahan (biasanya 4-8 byte per pointer) saat Anda membutuhkan pointer itu. Ada banyak teknik yang membuat ini lebih terjangkau.

Teknik yang paling mendasar yang membuat pointer kuat adalah Anda tidak perlu menjaga setiap pointer. Terkadang Anda dapat menggunakan algoritme untuk membuat pointer dari pointer ke sesuatu yang lain. Contoh paling sepele dari ini adalah aritmatika array. Jika Anda mengalokasikan array 50 integer, Anda tidak perlu menyimpan 50 pointer, satu untuk setiap integer. Anda biasanya melacak satu penunjuk (yang pertama), dan menggunakan aritmatika penunjuk untuk menghasilkan yang lainnya dengan cepat. Kadang-kadang Anda dapat menyimpan salah satu dari pointer tersebut ke elemen spesifik array sementara, tetapi hanya saat Anda membutuhkannya. Setelah selesai, Anda dapat membuangnya, selama Anda menyimpan informasi yang cukup untuk memperbaruinya nanti, jika Anda membutuhkannya. Ini mungkin terdengar sepele, tetapi itu persis seperti alat konservasi Anda

Dalam situasi memori yang sangat ketat, ini dapat digunakan untuk meminimalkan biaya. Jika Anda bekerja di ruang memori yang sangat sempit, Anda biasanya memiliki kepekaan yang baik tentang berapa banyak objek yang perlu Anda manipulasi. Alih-alih mengalokasikan sekelompok bilangan bulat satu per satu dan menyimpan pointer penuh untuk mereka, Anda dapat mengambil keuntungan dari pengetahuan pengembang Anda bahwa Anda tidak akan pernah memiliki lebih dari 256 bilangan bulat dalam algoritma khusus ini. Dalam hal ini, Anda mungkin menyimpan pointer ke integer pertama, dan melacak indeks menggunakan char (1 byte) daripada menggunakan pointer penuh (4/8 byte). Anda juga dapat menggunakan trik algoritmik untuk membuat beberapa indeks ini dengan cepat.

Jenis kesadaran ingatan semacam ini sangat populer di masa lalu. Misalnya, game NES akan mengandalkan kemampuan mereka untuk menjejalkan data dan menghasilkan pointer secara algoritmik daripada harus menyimpan semuanya secara grosir.

Situasi memori ekstrem juga dapat menyebabkan seseorang melakukan hal-hal seperti mengalokasikan semua ruang yang Anda operasikan pada waktu kompilasi. Kemudian pointer yang harus Anda simpan ke memori disimpan dalam program daripada data. Dalam banyak situasi dengan keterbatasan memori, Anda memiliki program dan memori data yang terpisah (seringkali ROM vs RAM), sehingga Anda mungkin dapat menyesuaikan cara Anda menggunakan algoritme untuk mendorong pointer ke dalam memori program.

Pada dasarnya, Anda tidak bisa menghilangkan semua biaya overhead. Namun, Anda bisa mengendalikannya. Dengan menggunakan teknik algoritmik, Anda dapat meminimalkan jumlah pointer yang dapat Anda simpan. Jika Anda menggunakan pointer ke memori dinamis, Anda tidak akan pernah mendapatkan di bawah biaya menjaga 1 pointer ke tempat memori dinamis itu, karena itulah jumlah minimum informasi yang diperlukan untuk mengakses apa pun di blok memori itu. Namun, dalam skenario kendala memori ultra-ketat, ini cenderung menjadi kasus khusus (memori dinamis dan kendala memori ultra-ketat cenderung tidak muncul dalam situasi yang sama).

Dalam banyak situasi pointer sebenarnya menghemat memori. Alternatif umum untuk menggunakan pointer adalah membuat salinan struktur data. Salinan lengkap dari struktur data akan lebih besar dari sebuah pointer.

Salah satu contoh aplikasi kritis waktu adalah tumpukan jaringan. Tumpukan jaringan yang baik akan dirancang untuk menjadi "salinan nol" - dan untuk melakukan ini memerlukan penggunaan pointer yang cerdas.