6 রকম layout, মাপের 2 রকম প্রশ্ন

Alice একই library record 6 রকম বাক্সে রেখেছে। গুনে সবখানে সমান record পাও। তবু জায়গা আর নতুন record ঢোকানোর খরচ এক না। Maria জানতে চায়, একই value রাখতে এত আলাদা ব্যবস্থা কেন লাগছে।

Object আর নিজের রাখা জায়গা

Object হলো type আর আয়ু আছে এমন একটা value। container object প্রায়ই অন্য জায়গায় রাখা element সামলায়। নিজের রাখা জায়গা বলতে সেই memory বোঝাচ্ছি, যেটা শেষে তাকে ছাড়তে হবে। sizeof শুধু object-এর নিজের মাপ দেয়। pointer ধরে ধরে তার বাইরের memory যোগ করে না।

অনেক record-এর vector আর খালি vector-এর object-এর মাপ সমান হতে পারে। বড় হয় বাইরের element block। খালি deque-ও আগে থেকে কিছু জায়গা নিতে পারে। node-ভিত্তিক container-এ নতুন value এলে আলাদা allocation যোগ হয়। তাই sizeof(container)-কে element সংখ্যা দিয়ে গুণ করে মোট memory ধরো না।

Implementation detail মানে library-র নিজের বেছে নেওয়া রীতি। অন্য library সেটা বদলাতে পারে। Guarantee হলো C++ standard যে আচরণ চায়। এখানে GCC 12-এর libstdc++ ধরে Module 2 থেকে 10-এর ছবিগুলো একসাথে পড়ব। আগের module-এর বাড়ার পরীক্ষাগুলো আবার করার দরকার নেই। মিল আর পার্থক্যটাই এবার কাজের।

পাশাপাশি রেখে layout পড়ো

vector-এর 3-টা সীমানা: শুরু, জীবিত element-এর শেষ, আর বরাদ্দ জায়গার শেষ। প্রথম দুই সীমানা থেকে size বোঝা যায়। শেষ সীমানা বলে আর কতটা বাড়লে জায়গা বদলাবে। GCC-র এই রূপে এগুলো 3-টা pointer। standard element পাশাপাশি রাখার কথা বলে, এই field-গুলো রাখতেই হবে বলে না।

string-এর বেছে নেওয়া সুবিধাটা আলাদা। ছোট লেখা object-এর ভেতরের buffer-এই থাকতে পারে। বড় হলে বাইরের জায়গা লাগে। Module 3-তে এই small-string রীতি দেখেছ। vector-এর সাথে মিলিয়ে দেখো: ছোট string বাইরের allocation এড়াতে পারে, সাধারণ vector-এর element-এর জায়গা বাইরে থাকে।

deque block-এর pointer-এর একটা map রাখে। এখানে map মানে index-এর array, std::map না। এক block-এ কয়েকটা element থাকে। index দিয়ে আগে block, তারপর ঘর পাও। মাথায় বাড়াতে map বদলালেও আগের element সরতে হয় না। পরে দেখবে, এ কারণেই deque-এর iterator-এর নিয়ম আলাদা।

list-এ value আলাদা linked node-এ ছড়ানো। node-এ value আর পাশের node-এর link থাকে। object-এ সীমানা আর হিসাবের অংশ থাকে। নতুন value এলে একটা node যোগ হয়, পুরো element block লম্বা করতে হয় না। কিন্তু নম্বর ধরে মাঝখানে যেতে link বেয়ে হাঁটতে হয়। ঠিকানা স্থির মানেই index সস্তা না।

এই library-তে ordered set আর map tree node ব্যবহার করে। node-এ parent, left, right link আর colour থাকে। গাছের ভারসাম্য ঠিক করতে link বদলায়, value তার node-এই থাকে। তাই ordered খোঁজা আর স্থির element handle একসাথে পাও। standard খরচের সীমা চায়, এই colour-ওয়ালা গাছটাই চাই এমন না।

unordered container-এ bucket-এর array আর linked node দুটোই থাকে। hash দিয়ে bucket বাছা হয়। GCC-তে node-গুলো এক shared chain-এ যুক্ত; bucket entry দিয়ে তার অংশ খুঁজে পাও। Module 10-তে এটা খুলে দেখেছ। rehash-এ bucket-এর ব্যবস্থা বদলায়, element বেঁচে থাকে। তাই element-এর ঠিকানা ঠিক থেকেও হাঁটার iterator বাতিল হতে পারে।

এই layout-গুলো মূলত পাশাপাশি জায়গা, link আর বাড়তি ঘরের মধ্যে খরচ ভাগ করে। vector আগে থেকে কিছু ঘর রেখে একসাথে বড় হয়। list link-এর খরচ দিয়ে node আলাদা রাখে। hash table-এ node আর bucket দুটোই লাগে। string নিজের object একটু বড় রেখে ছোট allocation বাঁচায়। একটা sizeof দিয়ে সবগুলোর দাম বোঝা যাবে না।

record নিজেও বাইরের memory রাখতে পারে। vector<string>-এ string object পাশাপাশি থাকে, কিন্তু বড় লেখার buffer অন্যখানে হতে পারে। পাশাপাশি থাকার কথা element object-এর, তার সব মালিকানার জায়গার না। অনেক লেখা রাখলে দুই স্তরের খরচ ধরো।

allocation-এ চাওয়া byte আর process-এর ধরে রাখা memory-ও এক না। memory manager মাপ গোল করতে পারে, হিসাবের অংশ রাখতে পারে, ছাড়া block জমিয়ে রাখতে পারে। sizeof এগুলো মাপে না। এখানে node-এর type-এর মাপ, process-এর পুরো memory না।

একটা value এলে কী হয় মিলিয়ে দেখো। vector খালি ঘর নেয় বা block সরায়। deque নতুন block নিতে পারে। list node যোগ করে। tree-তে link-ও ঠিক হয়। hash-এ bucket-এর ব্যবস্থা বদলাতে পারে। এই update-গুলো দিয়ে handle-এর আলাদা নিয়ম বোঝা যায়।

Module 2-তে vector বাড়ার হিসাব হয়েছে। Module 4-এ deque-এর block-এর অঙ্ক দেখেছ। আবার একই প্রমাণ লাগবে না। এবার দুইটার ফল মেলাও: দুই layout-এই random access constant, তবু ঠিকানার স্থিরতা আর মাঝের pointer পড়ার কাজ আলাদা। খরচের O চিহ্ন মিললেই গঠন এক না।

array-এর element count type-এর অংশ। move-এ দিয়ে দেওয়ার মতো বাড়তে থাকা বাইরের block নেই। adaptor-এ আবার ভেতরের container-এর storage-এর নিয়ম লাগে। sizeof দেখে সিদ্ধান্তের আগে কোন স্তর element-এর মালিক বোঝো।

শেষে ছবি আর প্রমাণ আলাদা রাখো। ছবি field আর value-এর সম্পর্ক বোঝায়। program এই compiler-এর সত্যিকারের type মাপে। public API-এর নিয়ম বলে app কী ভরসায় করবে। একটা দিয়ে সব বোঝাতে না গিয়ে তিনটা মিলাও।

sizeof(vector<int>)  // The manager object, not its element block.
sizeof(int)          // One payload object.
v.capacity()         // Element slots owned by this vector.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
struct Boundaries { int *start,*finish,*limit; };
    vector<int> v(100); string shortText="book",longText(100,'x');
    cout<<"vector-object "<<sizeof(v)<<'\n';
    cout<<"three-pointer-model "<<sizeof(Boundaries)<<'\n';
    cout<<"string-object "<<sizeof(shortText)<<'\n';
    cout<<"long-string-object "<<sizeof(longText)<<'\n';
    cout<<"live-vector-payload "<<v.size()*sizeof(int)<<'\n';
}

vector-object 24
three-pointer-model 24
string-object 32
long-string-object 32
live-vector-payload 400

#include <deque>
#include <iostream>
#include <list>
using namespace std;
int main() {
deque<int> blocks; list<int> nodes;
    cout<<"deque-object "<<sizeof(blocks)<<'\n';
    cout<<"list-object "<<sizeof(nodes)<<'\n';
    cout<<"list-node-gcc-only "<<sizeof(std::_List_node<int>)<<'\n';
    cout<<"deque-iterator "<<sizeof(deque<int>::iterator)<<'\n';
    cout<<"int-payload "<<sizeof(int)<<'\n';
}

deque-object 80
list-object 24
list-node-gcc-only 24
deque-iterator 32
int-payload 4

#include <iostream>
#include <map>
#include <set>
#include <unordered_set>
using namespace std;
int main() {
cout<<"set-object "<<sizeof(set<int>)<<'\n';
    cout<<"map-object "<<sizeof(map<int,int>)<<'\n';
    cout<<"tree-node-gcc-only "<<sizeof(std::_Rb_tree_node<int>)<<'\n';
    cout<<"unordered-object "<<sizeof(unordered_set<int>)<<'\n';
    cout<<"hash-node-gcc-only "<<sizeof(std::__detail::_Hash_node<int,false>)<<'\n';
}

set-object 48
map-object 48
tree-node-gcc-only 40
unordered-object 56
hash-node-gcc-only 16

তীর দিয়ে সম্পর্ক দেখানো, ঠিকানা বা byte-এর অবস্থান না। deque-এর map-এর entry নিচের নিজের block-টা দেখায়। tree-তে node থেকে child-এর দিকে link যায়। hash-এ bucket shared chain-এর অংশে ঢোকার রাস্তা দেয়। প্রতিটা ছবির সাথে তার মাপার program-টা মিলিয়ে পড়ো।

প্রতিটা ধাপে capacity vector থেকেই পড়া। moved-এ জায়গা বদলালে আগের কয়টা int সরাতে হলো সেটা আছে। processor-এর instruction গোনা হয়নি। এই ধাপগুলো এই library-তে চালানোর ছবি। অন্য library-তে একই গুণে বাড়বে ধরে code লিখো না।

#include <list>
using namespace std;
int main() {
list<int> a{2,5}; auto p=a.data(); (void)p;
}

#include <vector>
using namespace std;
int main() {
vector<bool> flags(3); bool& first=flags[0]; (void)first;
}

4 3 0
2581

32

#include <iostream>
#include <string>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
int n,q; long long seed; string digits; cin>>n>>q>>seed>>digits;
    // Follow the inspection schedule and accumulate its weighted digits.
}

3 8 12

#include <iostream>
using namespace std;
int main() {
long long s,c,b; cin>>s>>c>>b;
    // Print the two payload budgets.
}

36 96

5 8 4 8

#include <iostream>
using namespace std;
int main() {
long long n,c,b,p; cin>>n>>c>>b>>p;
    // Compare the two stated memory models.
}

VECTOR

এরপর কাজের খরচের নিয়ম আর average-এর আড়ালের বড় খরচ দেখবে।