পারফরম্যান্স — অনুমান নয়, মেপে দ্রুত করা

১ · অনুমান নয়, মাপুন — আর লক্ষ্য আগে ঠিক করুন

একটি দোকানের হিসাবের সফটওয়্যারের কথা ভাবুন। মাসের শেষে মালিক “বিক্রির রিপোর্ট” বোতাম চাপেন, আর রিপোর্ট আসতে লাগে ১০ সেকেন্ড। নতুন প্রোগ্রামার এসে বললেন, “ফাইল পড়াটা নিশ্চয়ই ধীর, ওটাকে দ্রুত করি।” দুই দিন খেটে তিনি ফাইল পড়া দ্বিগুণ দ্রুত করলেন। রিপোর্ট এখনো আসে প্রায় ১০ সেকেন্ডে। কারণ ফাইল পড়তে লাগত মাত্র ০.১ সেকেন্ড — বাকি সময় যাচ্ছিল অন্য কোথাও।

অভিজ্ঞ প্রোগ্রামাররাও আন্দাজে বলতে পারেন না, প্রোগ্রামের সময় ঠিক কোথায় যায়। তাই optimization-এর প্রথম নিয়ম কোনো কৌশল নয়, একটি অভ্যাস: আগে মাপুন।

Knuth-এর উক্তি — পুরোটা পড়ুন

“Premature optimization is the root of all evil” — এই লাইনটি আপনি হয়তো শুনেছেন। অনেকে এটিকে বলেন “পারফরম্যান্স নিয়ে ভাবার দরকারই নেই”। কিন্তু Donald Knuth ১৯৭৪ সালে আসলে যা লিখেছিলেন, তা পুরোটা পড়লে অর্থ বদলে যায়:

সহজ বাংলায়: প্রোগ্রামের বেশিরভাগ অংশ (প্রায় ৯৭%) গতির জন্য গুরুত্বপূর্ণ নয়, সেখানে ছোটখাটো কৌশলে সময় নষ্ট করলে কোড শুধু জটিল হয়। কিন্তু একটি ছোট অংশ (প্রায় ৩%) সত্যিই সংকটপূর্ণ — সেখানে সুযোগ ছাড়া যাবে না। আর সেই ৩% কোথায়, তা খুঁজে বের করতে হবে মেপে। premature optimization মানে “সেই ৩% খোঁজার আগেই” অনুমানে কোড জটিল করা। ভাবনার প্রশ্ন ০১-এ এই প্রবন্ধের পুরো গল্প আছে।

“দ্রুত” মানে কী — latency, throughput আর p99

মাপার আগে ঠিক করতে হবে, কী মাপবেন। দুটি আলাদা প্রশ্ন আছে।

দুটি সবসময় একসাথে বাড়ে না। মেট্রো রেলের কথা ভাবুন: বড় ট্রেন কম ঘন ঘন চালালে ঘণ্টায় বেশি যাত্রী যায় (throughput বাড়ে), কিন্তু প্ল্যাটফর্মে প্রত্যেকের অপেক্ষা বাড়ে (latency বাড়ে)। প্রোগ্রামেও কাজগুলো জমিয়ে একসাথে করলে (batching) throughput বাড়ে, কিন্তু প্রথম কাজটিকে অপেক্ষা করতে হয়।

আর latency-তে গড় দিয়ে বিচার করবেন না। ধরুন ১০০টি অনুরোধের ৯৯টি ১০ মিলিসেকেন্ডে শেষ হয়, আর একটি লাগে ২ সেকেন্ড। গড় প্রায় ৩০ মিলিসেকেন্ড — দেখতে ভালো। কিন্তু প্রতি ১০০ জন গ্রাহকের একজন দুই সেকেন্ড আটকে থাকছেন। তাই পেশাদাররা দেখেন percentile: p50 (মাঝের মান), p99 (১০০টির মধ্যে ৯৯টি এর চেয়ে দ্রুত)। এই খারাপ দিকের প্রান্তকে বলে tail latency. একটি পাতা খুলতে যদি সার্ভার ভেতরে ৫০টি ছোট অনুরোধ পাঠায়, তাহলে তাদের অন্তত একটি p99-এর মতো ধীর হওয়ার সম্ভাবনা প্রায় ৪০% — তাই বড় সিস্টেমে p99-ই আসল গতি ঠিক করে।

২ · মাপা — সহজ শোনায়, কিন্তু কঠিন

পর্ব ৪১-এ আপনি std::chrono দেখেছেন। সময় মাপার জন্য ঠিক ঘড়িটি হলো steady_clock — এটি কখনো পেছনে যায় না। (দেয়ালঘড়ির system_clock ইন্টারনেট থেকে সময় ঠিক করার সময় লাফ দিতে পারে, তাই মাপার কাজে অচল।) সবচেয়ে সরল মাপার কাঠামো এমন:

#include <chrono>
using clk = std::chrono::steady_clock;

auto t0 = clk::now();
auto total = build_report(sales);          // je kaj mapchi
auto t1 = clk::now();
auto us = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0);
std::println("report: {} us (total = {})", us.count(), total);

দেখতে সহজ। কিন্তু এভাবে একবার মাপা সংখ্যা প্রায়ই ভুল পথে নিয়ে যায়। চারটি ফাঁদ চিনে রাখুন।

• ১. প্রথমবার আলাদা। প্রথমবার চালালে ডেটা cache-এ নেই, মেমরির পাতা অপারেটিং সিস্টেম তখনো দেয়নি, CPU হয়তো কম গতিতে ঘুমিয়ে ছিল। তাই আগে কয়েকবার “গরম” করুন — warm-up — তারপর অনেকবার মেপে মাঝের মান (median) নিন।
• ২. optimizer কাজটাই মুছে দিতে পারে। পর্ব ৪৩-এর as-if rule মনে করুন: ফলাফল যদি কোথাও ব্যবহার না হয়, compiler পুরো হিসাবটাই বাদ দিতে পারে — dead code elimination. তখন আপনার “১০ লাখবার হিসাব” মাপে ০ ন্যানোসেকেন্ড আসে। উপরের কোডে তাই total ছাপানো হয়েছে, যাতে ফলটি “কাজে লাগে”।
• ৩. noise. পাশে ব্রাউজার চলছে, ল্যাপটপ চার্জে নেই, CPU গরম হয়ে গতি কমিয়েছে — একই কোড দুবার চালালে ১০–২০% পার্থক্য খুব স্বাভাবিক। ৫% উন্নতি “পেয়েছি” বলার আগে কয়েকবার চালিয়ে দেখুন পার্থক্যটা noise-এর চেয়ে বড় কি না।
• ৪. ভুল build. -O0 (optimization বন্ধ, g++-এর ডিফল্ট) দিয়ে মাপা সংখ্যা প্রায় অর্থহীন। সেখানে std::vector-এর প্রতিটি [] একটি আসল ফাংশন-ডাক, তাই C++-এর abstraction-গুলো কৃত্রিমভাবে ধীর দেখায়। সবসময় যে flag-এ প্রোগ্রাম আসলে চলবে (সাধারণত -O2), সেটা দিয়েই মাপুন।

Benchmark লাইব্রেরি — এই ফাঁদগুলো সামলানোর তৈরি হাতিয়ার

ছোট একটি ফাংশনের গতি আলাদা করে মাপাকে বলে microbenchmark. এর জন্য হাতে লুপ না লিখে তৈরি লাইব্রেরি ব্যবহার করুন। সবচেয়ে প্রচলিত Google Benchmark; হালকা একটি বিকল্প Martin Ankerl-এর nanobench (একটি header ফাইল)। এরা নিজে থেকেই warm-up করে, যথেষ্টবার চালায়, পরিসংখ্যান দেয়, আর ফল মুছে যাওয়া ঠেকানোর হাতিয়ার দেয়:

#include <benchmark/benchmark.h>

static void BM_Report(benchmark::State& state) {
    auto sales = make_sales(20000);            // prostuti: mapar baire
    for (auto _ : state) {                     // library nije koto bar chalabe thik kore
        auto total = build_report(sales);
        benchmark::DoNotOptimize(total);       // "eta byabohar hocche" - mucho na
    }
}
BENCHMARK(BM_Report);
BENCHMARK_MAIN();

DoNotOptimize-এর ধারণাটা মনে রাখুন: compiler-কে বলা “এই মানটি কেউ দেখবে, তাই হিসাবটা সত্যিই করো”, কিন্তু আর কোনো বাড়তি খরচ না যোগ করে। quick-bench.com সাইটে Google Benchmark অনলাইনেও চালানো যায়; নিজের কম্পিউটারে লাইব্রেরিটি ইনস্টল করে -lbenchmark দিয়ে link করতে হয় (পর্ব ৪৭-এর CMake দিয়ে সহজ)।

পুরো চক্র — মাপুন, খুঁজুন, ঠিক করুন, আবার মাপুন

দোকানের রিপোর্টের গল্পটি এবার ঠিক পথে চালিয়ে দেখি। নিচের stepper-এ প্রতিটি ধাপে কী করা হয় আর কী পাওয়া যায়, দেখুন।

মালিকের চাওয়া: রিপোর্ট ১ সেকেন্ডের মধ্যে
ডেটা: ২০০০ পণ্য, মাসে ২০,০০০ বিক্রি
লক্ষ্য না থাকলে optimization কখনো শেষ হয় না

run 1: 10.31 s
run 2:  9.97 s
run 3: 10.02 s   median = 10.0 s
(সংখ্যাগুলো উদাহরণ; আপনার মেশিনে আলাদা হবে)

  98.0%  find_product
   0.9%  format_line
   0.9%  read_sales_file
   0.2%  [others]

for (const auto& p : catalog)   // 2000 ponno, shuru theke
    if (p.id == pid) return p;
২০,০০০ বিক্রি × গড়ে ১০০০ তুলনা = ২ কোটি তুলনা

std::ranges::lower_bound(catalog, pid, {}, &Product::id);
প্রতি বিক্রিতে ~১১টি তুলনা, মোট ~২.২ লাখ
(বিকল্প: std::unordered_map, গড়ে O(1))

median = 0.2 s     লক্ষ্য পূরণ — থামুন
find_product এখন  ~৫০% সময়
নতুন profile: বাকি অর্ধেক format_line আর ফাইল পড়ায়

৩ · Profiler — সময় আসলে কোথায় যায়

stopwatch বলে “পুরোটায় কত সময়”; profiler বলে “কোন ফাংশনে কত সময়”। যে ছোট অংশে সবচেয়ে বেশি সময় যায়, তাকে বলে hotspot. profiler সাধারণত দুইভাবে কাজ করে:

কোন প্ল্যাটফর্মে কী ব্যবহার করবেন:

Linux-এ একটি সাধারণ সেশন এমন দেখায়। -g দিলে profiler ফাংশনের নাম আর লাইন দেখাতে পারে; frame pointer রাখলে কে কাকে ডেকেছে, সেই শিকল নির্ভরযোগ্যভাবে পাওয়া যায়:

g++ -std=c++23 -O2 -g -fno-omit-frame-pointer report.cpp -o report
perf record -g ./report        # chalao, sample jomao
perf report                    # kon function-e koto %

Flame graph — এক ছবিতে পুরো প্রোগ্রাম

profiler-এর লম্বা টেক্সট তালিকা পড়া কঠিন। ২০১১ সালে Brendan Gregg MySQL-এর একটি পারফরম্যান্স সমস্যা খুঁজতে গিয়ে একটি ছবি আবিষ্কার করেন, যা এখন সবখানে ব্যবহার হয় — flame graph. প্রথমবার দেখলে বিভ্রান্ত লাগে, কারণ একটি অক্ষ সবাই ভুল পড়েন। ধাপে ধাপে পড়া শিখুন:

উপরে: যে ফাংশন নিজে চলছিল
[ str== 60%                     ][ hash ]
[ find_product  98%                     ][f]
[ build_report  99%                        ][l]
[ main  100%                                  ]
f = format_line 1%, l = load 1%
নিচে: শিকড় (প্রথম ডাক)

[ str  ]
[ find_product 50% ][ fmt 25%  ]
[ build_report  75%            ][ load 25%  ]
[ main  100%                                ]
মোট সময় ৫০ গুণ কম; এখন load আর fmt-ও চোখে পড়ে

৪ · আগে algorithm — O(n²) থেকে O(n log n)

profiler hotspot দেখানোর পরে প্রথম প্রশ্ন: “এখানে কাজের পরিমাণ কমানো যায়?” — কাজটা দ্রুত করার আগে। একটি পরিচিত সমস্যা দিয়ে দেখি: একটি তালিকায় কোনো সংখ্যা দুবার আছে কি না (যেমন একই মোবাইল নম্বরে দুটি অ্যাকাউন্ট খোলা হয়েছে কি না)। তিনটি উপায়:

// upay 1: protiti jora tulona - O(n^2)
bool has_dup_slow(const std::vector<long>& v) {
    for (std::size_t i = 0; i < v.size(); ++i)
        for (std::size_t j = i + 1; j < v.size(); ++j)
            if (v[i] == v[j]) return true;
    return false;
}
// upay 2: sajao, tarpor pashapashi dekho - O(n log n)
bool has_dup_sort(std::vector<long> v) {          // copy, karon sajabo
    std::ranges::sort(v);
    return std::ranges::adjacent_find(v) != v.end();
}
// upay 3: hash set - gore O(n)
bool has_dup_hash(const std::vector<long>& v) {
    std::unordered_set<long> seen;
    seen.reserve(v.size());
    for (long x : v)
        if (!seen.insert(x).second) return true;  // age theke chilo
    return false;
}

প্রথম উপায়ে nested loop প্রতিটি জোড়া তুলনা করে: কোনো ডুপ্লিকেট না থাকলে n(n−1)/২টি তুলনা। দ্বিতীয় উপায়ে sort (পর্ব ৩৩) মোটামুটি n log₂ n তুলনা করে, তারপর একবার সারি ধরে হাঁটে। তৃতীয় উপায়ে std::unordered_set (পর্ব ৩১) প্রতিটি সংখ্যার জন্য গড়ে ধ্রুবক সময়ের একটি খোঁজা করে। ছোট n-এ পার্থক্য চোখে পড়ে না — আর ঠিক এ কারণেই এমন কোড পরীক্ষার সময় পার হয়ে যায়, আর আসল ডেটায় এসে ভেঙে পড়ে। n বাড়লে কী হয়, দেখুন:

1// n ti shonkhya, kono duplicate nei2has_dup_slow(v); // n(n-1)/23has_dup_sort(v); // ~ n log2 n4// 1e9 sohoj kaj/sec dhore

এবার দোকানের রিপোর্টের আসল কোড। ২০০০ পণ্যের catalog id অনুযায়ী সাজানো, আর মাসে ২০,০০০ বিক্রি। দুই উপায়ে প্রতিটি বিক্রির দাম খুঁজে মোট বিক্রি যোগ করা হয়েছে, আর সময় না ছেপে তুলনার সংখ্যা গোনা হয়েছে — কারণ সময় মেশিনভেদে বদলায়, কিন্তু কাজের পরিমাণ বদলায় না:

#include <algorithm>
#include <print>
#include <vector>

struct Product { int id; int price; };
int main() {
    std::vector<Product> catalog;              // 2000 ponno, id onujayi sajano
    for (int id = 0; id < 2000; ++id) catalog.push_back({id, 10 + id % 90});
    std::vector<int> sales;                    // 20000 bikri: kon ponno
    for (int i = 0; i < 20000; ++i) sales.push_back(i * 7919 % 2000);
    long total = 0, steps = 0;                 // upay 1: protibar shuru theke khoja
    for (int pid : sales)
        for (const auto& p : catalog) {
            ++steps;
            if (p.id == pid) { total += p.price; break; }
        }
    std::println("linear: total = {}, steps = {}", total, steps);
    total = 0; steps = 0;                      // upay 2: binary search
    auto less = [&steps](int a, int b) { ++steps; return a < b; };
    for (int pid : sales)
        total += std::ranges::lower_bound(catalog, pid, less, &Product::id)->price;
    std::println("binary: total = {}, steps = {}", total, steps);
}

৫ · মেমরির সিঁড়ি আর cache-বান্ধব কোড

algorithm ঠিক করার পরে দ্বিতীয় বড় জয় লুকিয়ে থাকে ডেটা মেমরিতে কীভাবে সাজানো, তার মধ্যে। কারণ আধুনিক CPU হিসাব করতে যত দ্রুত, মেমরি থেকে ডেটা আনতে তার চেয়ে অনেক ধীর। তাই CPU আর RAM-এর মাঝে কয়েক স্তরের ছোট কিন্তু দ্রুত মেমরি থাকে — cache. পুরো ব্যবস্থাকে বলে memory hierarchy:

সংখ্যাগুলো আনুমানিক — CPU-র প্রজন্ম আর নির্মাতা অনুযায়ী বদলায়। এই ধরনের তালিকা জনপ্রিয় হয় Peter Norvig-এর একটি প্রবন্ধ আর Jeff Dean-এর বক্তৃতার “Latency numbers every programmer should know” থেকে (ভাবনার প্রশ্ন ০৪)। আসল শিক্ষা অনুপাতে: RAM থেকে একবার পড়ার সময়ে CPU কয়েকশো সাধারণ হিসাব করে ফেলতে পারত। একটি cache miss মানে CPU-র সেই সময়টা বসে থাকা।

পর্ব ৩০-এ দেখেছেন, CPU মেমরি আনে একটি-একটি বাইট করে নয়, ৬৪ বাইটের cache line ধরে। এর থেকে দুটি নিয়ম আসে। spatial locality: একটি ঠিকানা পড়লে তার পাশেরগুলো বিনা খরচে চলে আসে, তাই পাশাপাশি থাকা ডেটা পরপর পড়ুন। temporal locality: সম্প্রতি পড়া ডেটা cache-এ থাকে, তাই একই ডেটা নিয়ে কাজগুলো কাছাকাছি সময়ে সেরে ফেলুন।

2D grid — সারি ধরে হাঁটবেন, না কলাম ধরে?

C++-এ একটি 2D array (বা vector-এর ভেতরে r * cols + c সূচকে রাখা grid) মেমরিতে থাকে row-major ক্রমে: প্রথম সারির সব ঘর, তারপর দ্বিতীয় সারির সব ঘর। পুরো grid-এর যোগফল বের করতে লুপের ক্রম দুই রকম হতে পারে — ফল একই, কিন্তু মেমরির কাছে দুটি সম্পূর্ণ আলাদা কাজ। একটি ছোট grid দিয়ে দেখুন, যার প্রতিটি সারিতে ১৬টি int = ঠিক ৬৪ বাইট = একটি cache line:

সারি 0: [ 0  1  2 ... 15 ]  <- cache line A
সারি 1: [16 17 18 ... 31 ]  <- cache line B
সারি 2: [32 33 34 ... 47 ]  <- cache line C
সারি 3: [48 49 50 ... 63 ]  <- cache line D
মেমরিতে: A এর ঠিক পরেই B, তারপর C, D

g[0][0]  A আনো (miss)
g[0][1]  A তে আছে (hit)
 ...     hit, hit, hit ...
g[0][15] hit
g[1][0]  B আনো  prefetcher আগেই এনে রাখতে পারে
৬৪টি ঘর, মোট ৪টি line আনা

g[0][0]  A আনো
g[1][0]  B আনো   ৬৪ বাইট দূরে লাফ
g[2][0]  C আনো
g[3][0]  D আনো
g[0][1]  A তে আছে? grid ছোট হলে হ্যাঁ

কলাম 0: সারি 0..255 -> 256টি আলাদা line
         cache-এ জায়গা মাত্র ৩২টির
         সারি 0-এর line ততক্ষণে বের হয়ে গেছে
কলাম 1: সারি 0 -> আবার আনো!
প্রতিটি ঘরেই নতুন line আনা

              line আনা    প্রতি line-এ কাজে লাগল
সারি ধরে        4,096      16টি int
কলাম ধরে  65,536       1টি int
একই যোগফল, ১৬ গুণ বেশি মেমরি-যাতায়াত

নিচের প্রোগ্রাম একটি খেলনা cache বানায়: ৩২টি line ধরে, আর জায়গা ফুরোলে সবচেয়ে পুরোনো ব্যবহৃত line বের করে দেয় (LRU নিয়ম)। তারপর ২৫৬ × ২৫৬ int grid-এর প্রতিটি ঘরের ঠিকানা দুই ক্রমে “ছুঁয়ে” গোনে, কয়বার নতুন line আনতে হলো:

#include <algorithm>
#include <deque>
#include <print>

constexpr long N = 256;              // 256 x 256 int grid
long loads = 0;
std::deque<long> cache;              // khelna cache: 32 line, LRU
void touch(long addr) {
    long line = addr / 64;           // 64-byte cache line
    auto it = std::ranges::find(cache, line);
    if (it != cache.end()) cache.erase(it);                 // hit
    else { ++loads; if (cache.size() == 32) cache.pop_front(); }
    cache.push_back(line);           // shobcheye notun byabohar
}
int main() {
    for (long r = 0; r < N; ++r) for (long c = 0; c < N; ++c) touch((r * N + c) * 4);
    std::println("row-major:    {} line loads", loads);
    loads = 0; cache.clear();
    for (long c = 0; c < N; ++c) for (long r = 0; r < N; ++r) touch((r * N + c) * 4);
    std::println("column-major: {} line loads", loads);
}

AoS বনাম SoA — কোন ঘরগুলো পাশাপাশি রাখবেন

একটি বোর্ডের পরীক্ষার ফলাফলের সফটওয়্যারে প্রতিটি ছাত্রের তথ্য একটি struct-এ রাখা আছে, আর সবার একটি vector. এই সাধারণ বিন্যাসকে বলে array of structs (AoS):

struct Student {                    // AoS: protiti chhatro ekta 64-byte struct
    int roll;
    float gpa;
    char name[56];
};
std::vector<Student> students;      // shudhu gpa-r gor chaile?

struct Students {                   // SoA: protiti field alada sari-te
    std::vector<int> roll;
    std::vector<float> gpa;          // shob gpa pashapashi
    std::vector<std::string> name;
};

এখন দশ লাখ ছাত্রের গড় GPA চাই। AoS-এ প্রতিটি ছাত্রের জন্য CPU পুরো ৬৪ বাইটের line আনে, অথচ কাজে লাগে মাত্র ৪ বাইটের gpa — বাকি ৬০ বাইট (নাম, roll) অকারণে মেমরি থেকে আসে। struct of arrays (SoA)-এ সব gpa একটি আলাদা ফাঁকহীন সারিতে, তাই প্রতিটি line-এ ১৬টি GPA — মেমরি-যাতায়াত ১৬ ভাগের এক ভাগ। তার ওপর পাশাপাশি থাকা একই টাইপের সংখ্যা compiler একসাথে কয়েকটি করে যোগ করতে পারে (SIMD).

তবে একজন ছাত্রের সব তথ্য একসাথে লাগলে (মার্কশিট ছাপানো) AoS-ই ভালো। নিয়মটি হলো: যে field-গুলো একসাথে পড়া হয়, সেগুলো পাশাপাশি রাখুন। এই চিন্তাকেই বলে data-oriented design — আগে ভাবুন ডেটা কীভাবে ব্যবহার হবে, তারপর বিন্যাস।

৬ · অকারণ কপি আর অকারণ allocation

C++-এর value semantics একটি বড় শক্তি — আবার লুকানো খরচের উৎসও। C-তে একটি বড় array কপি করতে হলে আপনাকে নিজে memcpy লিখতে হতো; C++-এ একটি = বা একটি ভুল parameter টাইপই এক লাখ উপাদানের vector চুপচাপ কপি করে ফেলে। profiler-এ এগুলো প্রায়ই দেখা যায় memcpy, operator new আর free নামে চওড়া বাক্স হিসেবে।

ফাংশন থেকে বড় vector বা string মান হিসেবে ফেরত দেওয়া কিন্তু ঠিক আছে — copy elision আর move-এর কারণে সেখানে কপি হয় না (পর্ব ৩৬)। আর ছোট string-এর কথা মনে রাখুন: বেশিরভাগ লাইব্রেরিতে small string optimization থাকে — ছোট লেখা (লাইব্রেরি ভেদে মোটামুটি ১৫ থেকে ২২ অক্ষর পর্যন্ত) string object-এর ভেতরেই থাকে, heap-এ যায় না। তাই ছোট নামের কপি সস্তা, বড় লেখার কপি দামি।

বড় string বানানো — reserve আর +=

রিপোর্টের প্রতিটি লাইন একটি বড় string-এ জুড়ছেন। দুটি লেখার ধরন দেখতে প্রায় এক, খরচে আকাশ-পাতাল:

// dhire: protibar notun string toiri, purono shob copy - mot O(n^2)
std::string slow;
for (const auto& s : sales) slow = slow + s.name + "," + std::to_string(s.amount) + "\n";

// druto: ekbar jayga, tarpor shudhu shesh-e jog - mot O(n)
std::string fast;
fast.reserve(sales.size() * 32);            // anumanik size
for (const auto& s : sales) {
    fast += s.name;
    fast += ',';
    fast += std::to_string(s.amount);
    fast += '\n';
}

প্রথম লাইনে slow + s.name একটি সম্পূর্ণ নতুন string বানায়, যাতে এ পর্যন্ত জমা সব লেখা কপি হয় — প্রতিটি লাইনে। দশ হাজার লাইনের রিপোর্টে সেটা কোটি কোটি অক্ষর কপি। দ্বিতীয়টিতে += শুধু শেষে যোগ করে, আর reserve শুরুতেই যথেষ্ট জায়গা নিয়ে রাখে, তাই বারবার বড় ব্লকে সরানোও লাগে না। (C++20-এর std::format_to দিয়ে একটি back_inserter-এ লেখা আরেকটি পরিচ্ছন্ন উপায়।)

Allocation-এর দাম — pool, arena আর std::pmr

heap allocation (new, বা vector/string-এর ভেতরের allocation) একটি বিনামূল্যের কাজ নয়: allocator-কে খালি জায়গা খুঁজতে হয়, হিসাব রাখতে হয়, অনেক thread থাকলে সমন্বয় করতে হয়, আর নতুন জায়গা প্রায়ই cache-এ থাকে না। একটি গরম লুপের ভেতরে প্রতিবার একটি অস্থায়ী vector বানানো খুব সাধারণ hotspot:

for (const auto& order : orders) {
    std::vector<int> items;             // protibar notun allocation...
    collect(order, items);
}
std::vector<int> items;                 // ...bodle bairer ekta, protibar clear()
for (const auto& order : orders) {
    items.clear();                      // size 0, kintu capacity thake
    collect(order, items);
}

এর চেয়ে বড় পরিসরে দুটি ধারণা আছে। object pool: একই মাপের অনেক বস্তু আগেই বানিয়ে রাখা, আর “মুছে ফেলা” বস্তু আবার ব্যবহার করা — যেমন গেমের গুলি বা নেটওয়ার্কের প্যাকেট। arena allocator: একটি বড় ব্লক নেওয়া, সেখান থেকে শুধু pointer এগিয়ে এগিয়ে ছোট ছোট জায়গা দেওয়া (খুব দ্রুত), আর কাজ শেষে পুরো ব্লক একবারে ফেরত দেওয়া — যেমন একটি HTTP অনুরোধ সামলানোর সব অস্থায়ী ডেটা। C++17 থেকে standard library-তে এর জন্য std::pmr (polymorphic memory resource) আছে, যাতে container-কে বলা যায় কোন জায়গা থেকে মেমরি নেবে:

#include <memory_resource>
std::array<std::byte, 64 * 1024> buf;                 // stack-e 64 KB
std::pmr::monotonic_buffer_resource arena{buf.data(), buf.size()};
std::pmr::vector<int> v{&arena};                      // heap noy, arena theke
// arena dhongsho hole shob ekbare ferot - alada free nei

এগুলো কোড জটিল করে — profiler allocation-কে বড় অংশ দেখালে তবেই। বেশিরভাগ ক্ষেত্রে reserve আর লুপের বাইরে container রাখাই যথেষ্ট।

৭ · CPU আর compiler-এর ভেতরের কাজ

Branch prediction — সাজানো ডেটা কেন দ্রুত

আধুনিক CPU একটি নির্দেশ শেষ হওয়ার অপেক্ষা না করে পরের অনেকগুলো নির্দেশ একসাথে এগিয়ে রাখে — কারখানার assembly line-এর মতো (pipeline). কিন্তু একটি if-এ এসে সে জানে না কোন দিকে যেতে হবে। অপেক্ষা না করে সে আন্দাজ করে এগিয়ে যায় — branch prediction. আন্দাজ ঠিক হলে কোনো খরচ নেই; ভুল হলে এগিয়ে রাখা কাজ ফেলে দিয়ে আবার শুরু — মোটামুটি ১০–২০ cycle নষ্ট, যাকে বলে branch misprediction.

long sum = 0;
for (int x : data)           // data: 0..255-er elomelo shonkhya
    if (x >= 128) sum += x;  // ei if-er dik CPU anda-je ki dhorte pare?

এলোমেলো ডেটায় এই if কোনো নিয়ম মানে না — আন্দাজ প্রায় অর্ধেক সময় ভুল। একই ডেটা আগে সাজিয়ে নিলে প্রথম অর্ধেক সব “না”, পরের অর্ধেক সব “হ্যাঁ” — আন্দাজ প্রায় সবসময় ঠিক। ২০১২ সালে Stack Overflow-এ “Why is processing a sorted array faster than processing an unsorted array?” প্রশ্নটি এই কারণেই বিখ্যাত হয়: প্রশ্নকর্তার মাপে সাজানো ডেটায় একই লুপ কয়েক গুণ দ্রুত চলেছিল। কিন্তু সেই আলোচনার একটি অংশ প্রায়ই ভুলে যাওয়া হয়: নতুন compiler উঁচু optimization-এ এই if-কে শাখাহীন নির্দেশ (যেমন conditional move) বা SIMD-এ বদলে দিতে পারে, আর তখন পার্থক্য প্রায় মুছে যায়। অর্থাৎ — আবার — মাপুন।

পর্ব ৪২-এ দেখা [[likely]] / [[unlikely]] (C++20 থেকে) compiler-কে বলে কোন শাখা বেশি ঘটে, যাতে সে সেই পথের কোড সোজা সাজায়। এটি ইঙ্গিত মাত্র, ভুল হলে উল্টো ক্ষতি; নিচের PGO আসল চলার তথ্য থেকে একই কাজ আরও নির্ভরযোগ্যভাবে করে।

Compiler আপনার সবচেয়ে বড় সহকারী

বেশিরভাগ “ছোট কৌশল” — গুণের বদলে shift, ছোট ফাংশন জুড়ে দেওয়া, লুপের ভেতরের স্থির হিসাব বাইরে আনা — compiler -O2-এ নিজেই করে। এর সবচেয়ে গুরুত্বপূর্ণটি হলো inlining: ছোট ফাংশনের ডাকের জায়গায় তার শরীরটাই বসিয়ে দেওয়া। এতে শুধু ডাকার খরচ বাঁচে না, আশপাশের কোডের সাথে মিলিয়ে আরও optimization-এর সুযোগ খোলে। এ কারণেই std::sort একটি lambda নিয়ে C-এর qsort-এর চেয়ে প্রায়ই দ্রুত — qsort প্রতিটি তুলনায় একটি function pointer ডাকে, sort-এর তুলনা inline হয়ে যায়।

compiler আসলে কী বানাল, তা দেখার সবচেয়ে সহজ উপায় Compiler Explorer — godbolt.org (Matt Godbolt-এর বানানো)। বাঁ দিকে C++ লিখুন, ডান দিকে সাথে সাথে assembly দেখুন, বিভিন্ন compiler আর flag পাশাপাশি তুলনা করুন। একটি পরীক্ষা করে দেখুন: x / 2 (unsigned) আর x >> 1 লিখে -O2-এ দুটির assembly — হুবহু এক। হাতে bit hack লিখে আপনি কিছুই পাননি, শুধু কোড পড়া কঠিন করেছেন।

৮ · শেষ অস্ত্র thread — আর কখন optimize করবেন না

একটি CPU-তে আজ ৮, ১৬ বা তারও বেশি core. তাহলে কাজটি ৮টি thread-এ ভাগ করলেই কি ৮ গুণ দ্রুত? পর্ব ৪৫-এ thread লিখতে শিখেছেন; এখানে প্রশ্নটা কখন। CPU-নির্ভর কাজে thread হলো শেষ অস্ত্র, প্রথম নয়, তিনটি কারণে।

• ভাগ না করা অংশ সীমা টানে। Amdahl's law: প্রোগ্রামের যে অংশ ভাগ করা যায় না, সেটিই সর্বোচ্চ গতি ঠিক করে। কাজের ২০% যদি এক thread-এই চলতে বাধ্য হয়, তাহলে অসীম core দিলেও ৫ গুণের বেশি দ্রুত হবে না (ভাবনার প্রশ্ন ০৫)।
• সমন্বয়ের খরচ। thread বানানো, mutex, কাজ ভাগ আর ফল জোড়া — সবকিছুর দাম আছে। আর দুটি thread যদি একই cache line-এর দুটি আলাদা ভ্যারিয়েবলে লেখে, CPU সেই line দুই core-এর মাঝে ক্রমাগত ঠেলাঠেলি করে — false sharing — আর multithread কোড single-thread-এর চেয়েও ধীর হতে পারে।
• বাগের নতুন জগৎ। data race (পর্ব ৪৩) আর deadlock খুঁজে পাওয়া কঠিন, কখনো কখনো শুধু গ্রাহকের মেশিনে দেখা দেয়।

তাই ক্রমটা মনে রাখুন: আগে algorithm, তারপর ডেটা-বিন্যাস আর কপি, তারপর compiler flag — সব শেষে, profiler দেখালে যে একটি বড়, স্বাধীনভাবে ভাগ করা যায় এমন কাজ এখনো সময় নিচ্ছে, তখন thread. সাধারণত std::sort-এর মতো algorithm-এ execution policy (std::execution::par) দিয়ে শুরু করা সবচেয়ে নিরাপদ।

কখন optimize করবেন না

খেয়াল করুন, দুটি বিপরীত ভুল আছে। একটি হলো আন্দাজে কোড দুর্বোধ্য করা। অন্যটি হলো “premature optimization খারাপ” বলে শুরু থেকেই স্পষ্টভাবে বাজে নকশা বেছে নেওয়া — যেমন প্রতিটি অনুরোধে পুরো ডেটাবেস টেবিল মেমরিতে আনা। প্রথমটির নাম premature optimization; দ্বিতীয়টির নাম অবহেলা। ভালো নকশা আর পরিষ্কার কোড কখনো premature নয়।

৯ · AI-এর যুগে — মাপা ছাড়া “দ্রুত” দাবি

AI-কে “এই কোড optimize করো” বললে সে প্রায়ই আত্মবিশ্বাসী উত্তর দেয়: “এখন ৩ গুণ দ্রুত!” — অথচ সে কোডটি একবারও চালায়নি, মাপেনি। তার পরিবর্তনগুলো প্রায়ই পুরোনো দিনের ছোট কৌশল, যা compiler নিজেই করে। অন্যদিকে AI একটি কাজে সত্যিই ভালো: কোড পড়ে জটিলতা বিশ্লেষণ করা আর ভালো data structure প্রস্তাব করা — যা মাপার পরে আপনি যাচাই করতে পারেন।

AI-এর “optimized” কোড যাচাইয়ের চেকলিস্ট

• বদলের আগে আর পরে একই ডেটায়, একই -O2 build-এ, কয়েকবার চালিয়ে median মেপেছি
• বদলটি profiler-এর দেখানো hotspot-এ — অন্য কোথাও নয়
• আগে complexity কমানোর চেষ্টা হয়েছে (O(n²) আছে কি না দেখেছি), ছোট কৌশল পরে
• হাতে unrolling, bit hack বা inline-এর ছড়াছড়ি নেই; থাকলে assembly আর মাপ দিয়ে প্রমাণিত
• নতুন কোড পুরোনোর মতোই সঠিক উত্তর দেয় — test চালিয়ে দেখেছি, edge case সহ
• নতুন flag (-march=native, -ffast-math) থাকলে তার ঝুঁকি বুঝে সিদ্ধান্ত নিয়েছি