পারফরম্যান্স আর CPU cache — মেপে দ্রুত করা

১ · একই algorithm, কয়েক গুণ পার্থক্য — সময় আসলে কোথায় যায়

চট্টগ্রামের একটি অনলাইন শপে কাজ করেন নাদিয়া। প্রতি রাতে তাঁর একটি C প্রোগ্রাম বিক্রির হিসাব করে। ডেটা থাকে একটি বড় টেবিলে — sales[শাখা][দিন], অর্থাৎ প্রতিটি সারি একটি শাখা, প্রতিটি কলাম একটি দিন। নাদিয়া লুপ লিখেছেন “প্রতিটি দিনের জন্য, সব শাখা ঘুরে যোগ করো”।

টেবিল বড় হতেই রিপোর্ট ধীর হয়ে গেল। AI-এর পরামর্শ (register, হাতে loop unrolling, গুণের বদলে shift) কাজে এলো না। তারপর একজন সিনিয়র শুধু লুপ দুটির ক্রম উল্টে দিলেন: “প্রতিটি শাখার জন্য, সব দিন ঘুরে যার যার দিনের ঘরে যোগ করো”। ফল হুবহু এক, কিন্তু প্রোগ্রাম কয়েক গুণ দ্রুত।

পর্ব ৩৯-এ শিখেছেন, Big-O গোনে কাজের ধাপ। দুটি সংস্করণেই ধাপ সমান — প্রতিটি ঘর একবার পড়া। পার্থক্য লুকিয়ে আছে Big-O যা বাদ দেয় তাতে: প্রতিটি ধাপের দাম। আর সেই দাম ঠিক করে মূলত ডেটা মেমরির কোন স্তর থেকে আসছে।

গত কয়েক দশকে প্রসেসরের গতি যত দ্রুত বেড়েছে, RAM থেকে ডেটা আনার সময় তত কমেনি। এই ক্রমবর্ধমান ফাঁককে বলে memory wall (ভাবনার প্রশ্ন ০১)। ফলে আজকের CPU-র বেশিরভাগ সময় হিসাবে নয়, ডেটার অপেক্ষায় কাটতে পারে। এই পর্বের পুরো কাহিনি তিনটি সরল নিয়মে বাঁধা:

২ · মেমরির সিঁড়ি — register থেকে SSD

দ্রুত মেমরি দামি আর ছোট; বড় মেমরি সস্তা কিন্তু ধীর। তাই কম্পিউটার একটি সিঁড়ির মতো কয়েক স্তরে মেমরি সাজায় — CPU-র একদম পাশে ছোট আর দ্রুত, দূরে বড় আর ধীর। এই ব্যবস্থার নাম memory hierarchy.

সংখ্যাগুলো আনুমানিক — CPU-র প্রজন্ম, নির্মাতা আর মেশিনভেদে বদলায়। মুখস্থ করার দরকার নেই; মনে রাখুন অনুপাত। L1 থেকে RAM প্রায় একশো গুণ দূরে। চাওয়া ডেটা cache-এ না পেলে হয় cache miss — RAM থেকে আনার সেই সময়ে core কয়েকশো সাধারণ হিসাব করে ফেলতে পারত। উল্টোদিকে, চাওয়া ডেটা cache-এ পেয়ে যাওয়াকে বলে cache hit.

একটি কাজ শুরু থেকে শেষ হতে যে সময় লাগে, তাকে বলে latency. RAM-এর latency বেশি হলেও একটানা পড়লে সে প্রতি সেকেন্ডে কয়েক দশ GB পাঠাতে পারে, কারণ একসাথে অনেক অনুরোধ চলে। তাই ক্রমানুসারে পড়া প্রায় সবসময় এলোমেলো পড়ার চেয়ে অনেক সস্তা।

৩ · Cache line আর locality — একবারে ৬৪ বাইট

CPU যখন RAM থেকে একটি int চায়, তখন শুধু সেই ৪ বাইট আসে না। আসে তার চারপাশের একটি নির্দিষ্ট মাপের টুকরো — cache line. x86-64 প্রসেসরে (Intel, AMD) এই মাপ সাধারণত ৬৪ বাইট; কিছু ARM চিপে, যেমন Apple-এর M-সিরিজে, ১২৮ বাইট। ৬৪ বাইটে ১৬টি int ধরে। অর্থাৎ a[0] পড়লে (array-টি line-এর শুরুতে থাকলে) a[0] থেকে a[15] পর্যন্ত সব একসাথে চলে আসে।

নিচের ডায়াগ্রামে একটি ৩২ ঘরের int array-এর যোগফল বের করা হচ্ছে। “পরে” চাপুন, আর দেখুন কোন পড়াগুলো সত্যিই RAM পর্যন্ত যায়:

1int a[32];        /* 32 x 4 = 128 bytes = 2 lines */2long s = 0;3for (int i = 0; i < 32; i++)4    s += a[i];

দুই রকম locality

• Spatial locality (স্থানের নৈকট্য): একটি ঠিকানা পড়লে খুব শিগগিরই তার পাশের ঠিকানাও পড়বেন। Array ক্রমানুসারে পড়া এর সেরা উদাহরণ।
• Temporal locality (সময়ের নৈকট্য): যে ডেটা এইমাত্র পড়েছেন, শিগগিরই আবার পড়বেন। যেমন একটি ছোট lookup table বারবার ব্যবহার করা, বা একই ডেটার ওপর কয়েকটি কাজ একসাথে সেরে ফেলা — ডেটা cache থেকে বেরিয়ে যাওয়ার আগেই।

একটি সাধারণ ভুল: দশ লাখ গ্রাহকের তালিকায় মোট ব্যালান্স, সর্বোচ্চ ব্যালান্স আর সক্রিয় গ্রাহক — তিনটি কাজের জন্য তিনটি আলাদা লুপ। তালিকা cache-এর চেয়ে বড়, তাই পুরোটা তিনবার RAM থেকে আসে। এক লুপে তিনটি কাজ করলে (loop fusion) প্রতিটি গ্রাহক একবার এসেই তিনটি কাজে লাগে।

Linked list বনাম array — ঠিকানার পেছনে দৌড়

পর্ব ৩৩-এ linked list বানিয়েছেন। Array আর linked list — দুটিতেই সব উপাদান একবার করে দেখা O(n). কিন্তু মেমরির কাছে দুটি সম্পূর্ণ আলাদা কাজ:

• Array: সব উপাদান পাশাপাশি। প্রতি line-এ অনেকগুলো উপাদান, আর পরের ঠিকানা আগে থেকেই জানা — prefetcher খুশি।
• Linked list: প্রতিটি node malloc থেকে আলাদাভাবে এসেছে, মেমরিতে ছড়ানো থাকতে পারে। আর পরের node কোথায়, তা জানতে আগে এই node-এর next পড়তেই হবে — একে বলে pointer chasing. তাই CPU একসাথে কয়েকটি পড়া চালাতে পারে না, prefetcher-ও পরের ঠিকানা আন্দাজ করতে পারে না।

ফলে বড় তালিকায় linked list ঘুরে আসা array-র চেয়ে অনেক গুণ ধীর হতে পারে — Big-O সমান হলেও। node-গুলো একটি বড় block থেকে পাশাপাশি দিলে (অংশ ৮-এর arena) ক্ষতি অনেক কমে।

৪ · সারি ধরে না কলাম ধরে — cache গুনে দেখা

এবার নাদিয়ার রহস্যে ফিরি। পর্ব ২১-এ বহুমাত্রিক অ্যারে-তে দেখেছেন, C-তে 2D array মেমরিতে থাকে row-major ক্রমে: প্রথম সারির সব ঘর পাশাপাশি, তারপর দ্বিতীয় সারি, এভাবে। তাই sales[b][d]-এর ঠিক পরের ঘর হলো sales[b][d+1], আর sales[b+1][d] আছে পুরো একটি সারি দূরে।

Cache কীভাবে কাজ করে, তা বোঝাতে একটি খুব ছোট খেলনা ধরি: ৪ × ৪ grid, প্রতিটি line-এ ৪টি int (অর্থাৎ এক সারি = এক line), আর cache-এ জায়গা মাত্র ২টি line-এর। কোন line কোন জায়গায় বসবে, তার নিয়ম সরল — সারি নম্বর জোড় হলে জায়গা ০, বিজোড় হলে জায়গা ১। এমন cache-কে বলে direct-mapped cache: প্রতিটি line-এর জন্য cache-এ ঠিক একটিই নির্দিষ্ট জায়গা।

সারি 0: [ 0  1  2  3]  -> জায়গা 0
সারি 1: [ 4  5  6  7]  -> জায়গা 1
সারি 2: [ 8  9 10 11]  -> জায়গা 0
সারি 3: [12 13 14 15]  -> জায়গা 1
cache: জায়গা 0 = খালি, জায়গা 1 = খালি

g[0][0]  M   সারি 0 আনা -> জায়গা 0
g[0][1]  H
g[0][2]  H
g[0][3]  H
৪টি পড়ায় ১টি miss

সারি 0:  M H H H
সারি 1:  M H H H
সারি 2:  M H H H
সারি 3:  M H H H
মোট: miss 4, hit 12

g[0][0]  M  জায়গা 0 = সারি 0
g[1][0]  M  জায়গা 1 = সারি 1
g[2][0]  M  জায়গা 0 = সারি 2  (সারি 0 বের হলো)
g[3][0]  M  জায়গা 1 = সারি 3  (সারি 1 বের হলো)

g[0][1]  M  সারি 0 দরকার, কিন্তু সেটা বের হয়ে গেছে!
g[1][1]  M
g[2][1]  M
g[3][1]  M
একই line বারবার আনা আর ফেলা

              miss   hit
সারি ধরে        4     12
কলাম ধরে       16      0
line-এ ১৬টি int হলে পার্থক্য ১৬ গুণ

এবার একটু বড় করে সত্যিকারের মাপে গুনি। নিচের প্রোগ্রাম একটি direct-mapped খেলনা cache বানায় — ৬৪ বাইটের ৮টি line, মোট ৫১২ বাইট। তারপর ৬৪ শাখা × ৬৪ দিনের int বিক্রির টেবিলের (১৬ KB) প্রতিটি ঘরের ঠিকানা দুই ক্রমে “ছুঁয়ে” গোনে, কতবার নতুন line আনতে হলো। কোনো সময় মাপা হচ্ছে না, তাই ফল প্রতিবার হুবহু এক:

#include <stdio.h>
#define N 64     /* sales[64][64] of int = 16 KB */
#define LINE 64  /* bytes per cache line */
#define SETS 8   /* toy direct-mapped cache: 8 lines = 512 bytes */

static long count_misses(int by_row) {
    long tag[SETS], misses = 0;
    for (int s = 0; s < SETS; s++) tag[s] = -1;          /* empty cache */
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            long idx = by_row ? (long)i * N + j : (long)j * N + i;
            long line = idx * (long)sizeof(int) / LINE;   /* which line? */
            if (tag[line % SETS] != line) { tag[line % SETS] = line; misses++; }
        }
    return misses;
}

int main(void) {
    printf("accesses: %d\n", N * N);
    printf("misses by row: %ld, by column: %ld\n", count_misses(1), count_misses(0));
    return 0;
}

আসল cache অনেক বড়, আর সাধারণত set-associative — একটি জায়গায় ৮ বা ১২টি line থাকতে পারে। কিন্তু টেবিলও তখন লাখ লাখ ঘরের, তাই বড় টেবিলে অনেক মেশিনে সারি-ক্রম কয়েক গুণ দ্রুত; নির্দিষ্ট সংখ্যা হার্ডওয়্যার আর মাপের ওপর নির্ভর করে।

নাদিয়ার সমাধান: লুপের ক্রম উল্টে সারি ধরে হাঁটা, আর দিনের যোগফল একটি ছোট day_total[দিন] array-তে জমানো, যা পুরো সময় cache-এ থাকে। মূল কথা: যে ক্রমে বেশি পড়বেন, সেই ক্রমে মেমরিতে সাজান।

৫ · ডেটার বিন্যাস — padding, field-এর ক্রম, AoS বনাম SoA

পর্ব ২২-এ struct পড়ার সময় দেখেছেন, compiler প্রতিটি member-কে তার alignment মেনে বসায় — double সাধারণত ৮-এর গুণিতক ঠিকানায়, int ৪-এর গুণিতকে। মাঝের ফাঁকা বাইটগুলোকে বলে padding. এক রেকর্ডে কয়েক বাইট নষ্ট হওয়া তুচ্ছ মনে হয়। কিন্তু দশ লাখ গ্রাহকের রেকর্ডে সেটাই কয়েক MB — আর প্রতিটি অকেজো বাইট cache-এ জায়গা খায়, RAM থেকে আনতে সময় খায়।

struct cust_bad {
    char   active;    /* 1 byte, align 1 */
    double balance;   /* 8 bytes, align 8 */
    char   tier;      /* 1 byte, align 1 */
    int    id;        /* 4 bytes, align 4 */
};                    /* আসল ডেটা: 14 bytes */

বাইট     0 1 2 3 4 5 6 7
সারি  0: A . . . . . . .   active + 7 ফাঁকা
সারি  8: B B B B B B B B   balance
সারি 16: T . . . I I I I   tier + 3 ফাঁকা + id
sizeof = 24, এর মধ্যে 10 বাইট ফাঁকা

বাইট     0 1 2 3 4 5 6 7
সারি  0: B B B B B B B B   balance
সারি  8: I I I I A T . .   id, active, tier
sizeof = 16, ফাঁকা মাত্র শেষের 2 বাইট

c[0]: B B B B B B B B | I I I I A T . .
c[1]: B B B B B B B B | ...
      ^ ঠিকানা 16 = 8-এর গুণিতক
ফাঁকা না রাখলে c[1].balance বসত 14-তে, alignment ভাঙত

             প্রতি রেকর্ড   মোট           এক line-এ
cust_bad       24 বাইট    24,000,000    2টি রেকর্ড
cust_good      16 বাইট    16,000,000    4টি রেকর্ড
বাঁচল                      8,000,000 বাইট (প্রায় 7.6 MiB)

নিচের প্রোগ্রাম sizeof আর offsetof দিয়ে compiler-এর আসল সিদ্ধান্ত ছাপায়, তারপর দশ লাখ রেকর্ডের হিসাব করে:

#include <stdio.h>
#include <stddef.h>

struct cust_bad  { char active; double balance; char tier; int id; };
struct cust_good { double balance; int id; char active; char tier; };

int main(void) {
    printf("bad : size %zu, offsets %zu %zu %zu %zu\n", sizeof(struct cust_bad),
           offsetof(struct cust_bad, active), offsetof(struct cust_bad, balance),
           offsetof(struct cust_bad, tier), offsetof(struct cust_bad, id));
    printf("good: size %zu, offsets %zu %zu %zu %zu\n", sizeof(struct cust_good),
           offsetof(struct cust_good, balance), offsetof(struct cust_good, id),
           offsetof(struct cust_good, active), offsetof(struct cust_good, tier));
    size_t n = 1000000, a = sizeof(struct cust_bad), b = sizeof(struct cust_good);
    printf("1M records: %zu vs %zu bytes, saved %zu\n", n * a, n * b, n * (a - b));
    printf("records per 64-byte line: %zu vs %zu\n", 64 / a, 64 / b);
    return 0;
}

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

ধরুন দশ লাখ গ্রাহকের মোট ব্যালান্স দরকার। সাধারণ নকশায় একটি struct-এর array থাকে — Array of Structs (AoS). প্রতিটি রেকর্ডের ১৬ বাইটের মধ্যে কাজে লাগে শুধু ৮ বাইটের balance; বাকি অর্ধেক line অকারণে আসে। বিকল্প হলো Struct of Arrays (SoA) — প্রতিটি field-এর জন্য আলাদা array. এই দুই নকশার তুলনাকে একসাথে বলে AoS বনাম SoA:

/* AoS: one array of records - natural, good when you use whole records */
struct customer { double balance; int id; char active; char tier; };
struct customer cust[1000000];

/* SoA: one array per field - good when a loop uses only one or two fields */
struct customers {
    double balance[1000000];
    int    id[1000000];
    char   active[1000000];
    char   tier[1000000];
};

/* summing balances in SoA: every byte fetched is a balance */
double total = 0;
for (int i = 0; i < n; i++) total += all.balance[i];

SoA-তে ব্যালান্সের লুপ শুধু ব্যালান্সই আনে — প্রতিটি line-এ ৮টি double, অপচয় নেই, আর compiler সহজে SIMD করতে পারে (অংশ ৭)। কিন্তু একজন গ্রাহকের সব তথ্য একসাথে লাগলে SoA-তে চারটি line আনতে হয়, AoS-এ একটি। নিয়ম: সবচেয়ে ঘন ঘন চলা লুপ যে field-গুলো একসাথে ছোঁয়, সেগুলো পাশাপাশি রাখুন।

মাঝামাঝি একটি কৌশল হলো hot/cold splitting: রেকর্ডের ঘন ঘন ব্যবহৃত ছোট field (ব্যালান্স, স্ট্যাটাস) এক struct-এ, আর কালেভদ্রে লাগা বড় field (ঠিকানা, নোট, ছবির পথ) আরেকটি struct-এ রেখে pointer বা index দিয়ে জোড়া। গরম অংশ ছোট থাকে, বেশি সংখ্যায় cache-এ ধরে।

৬ · Branch prediction আর শাখাহীন কোড

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

long sum = 0;
for (int i = 0; i < n; i++)
    if (data[i] >= 128)        /* data: values 0..255 */
        sum += data[i];

এখন দুটি পরিস্থিতি ভাবুন, আর আন্দাজ কতবার ভুল হয় তা মনে মনে গুনুন:

এলোমেলো ডেটায় কোনো predictor-ই কয়েন টসের চেয়ে ভালো আন্দাজ করতে পারে না; সাজানো ডেটায় আন্দাজ প্রায় সবসময় মেলে। ২০১২ সালের বিখ্যাত Stack Overflow প্রশ্ন “Why is processing a sorted array faster than processing an unsorted array?” এই ঘটনা নিয়েই (ভাবনার প্রশ্ন ০৩)।

শাখাহীন (branchless) কোড

অনুমান করা কঠিন এমন if-কে হিসাবে বদলে ফেলা যায়, যাতে লাফ দেওয়ার প্রশ্নই না ওঠে। একে বলে branchless কোড:

/* branchless sum: mask is all 1 bits (-1) or all 0 bits */
for (int i = 0; i < n; i++) {
    int mask = -(data[i] >= 128);
    sum += data[i] & mask;
}

/* max and clamp: compilers usually turn ?: into a conditional move */
static inline int max_int(int a, int b) { return a > b ? a : b; }
static inline int clamp(int x, int lo, int hi) {
    x = x < lo ? lo : x;
    return x > hi ? hi : x;
}

প্রথম লুপে তুলনার ফল (০ বা ১) থেকে mask: -(1) মানে সব বিট ১, -(0) মানে সব বিট ০; & করলে মান হয় পুরোটা থাকে, নয় শূন্য — কোনো লাফ নেই। max আর clamp-এর ?:-কে -O2-এ GCC ও Clang সাধারণত conditional move (x86-এর cmov) নির্দেশে বদলায়। বাস্তব উদাহরণ: সেন্সরের মান সীমার ভেতরে আটকানো, বা পিক্সেলকে ০–২৫৫-এ রাখা।

৭ · Compiler-কে কাজে লাগানো — -O2, inlining, restrict, loop রূপান্তর, SIMD

হাতে কৌশল লেখার আগে মনে রাখুন: সবচেয়ে দক্ষ সহকারী compiler নিজেই। Optimization ছাড়া (-O0, GCC-র ডিফল্ট) compiler প্রায় প্রতিটি লাইন আক্ষরিক অনুবাদ করে; পর্ব ৪৬-এ assembly-তে এই পার্থক্য দেখেছেন। তাই -O0-তে মাপা গতির কোনো অর্থ নেই।

Inlining আর restrict

Inlining মানে ছোট ফাংশন ডাকার বদলে তার কোড সরাসরি ডাকার জায়গায় বসানো। লাভ শুধু ডাকার খরচ বাঁচানো নয় — ভেতরের কোড চোখের সামনে এলে compiler আরও অনেক optimization করতে পারে। একই ফাইলের static ছোট ফাংশন -O2-এ সাধারণত আপনিই inline হয়। ভিন্ন .c ফাইলের ফাংশন inline করতে লাগে link-time optimization (-flto).

পর্ব ৪৫-এ উন্নত পয়েন্টার-এ restrict দেখেছেন। এটি পারফরম্যান্সে কেন জরুরি, দেখুন:

void add_arrays(int n, float *restrict dst,
                const float *restrict x, const float *restrict y) {
    for (int i = 0; i < n; i++)
        dst[i] = x[i] + y[i];
}

restrict ছাড়া compiler-কে ধরে নিতে হয় যে dst হয়তো x-এর ভেতরেই কোথাও (aliasing), তাই একসাথে আটটি যোগ করা নিরাপদ নয়। restrict লিখে আপনি প্রতিশ্রুতি দেন যে এরা একই মেমরি ছোঁবে না; তখন compiler নিশ্চিন্তে vectorize করে। প্রতিশ্রুতি ভাঙলে undefined behavior.

Loop রূপান্তর — hoisting, interchange আর tiling

• Hoisting: লুপের ভেতরের যে হিসাব প্রতিবার একই ফল দেয়, তা বাইরে এনে একবার করা। Compiler প্রায়ই নিজেই করে, কিন্তু ফাংশন-ডাকের পার্শ্বপ্রতিক্রিয়া নিয়ে নিশ্চিত না হলে পারে না — for (i = 0; i < strlen(s); i++) তাই O(n²) হয়ে যেতে পারে।
• Loop interchange: nested loop-এর ক্রম বদলে ভেতরের লুপকে সারি ধরে হাঁটানো — নাদিয়ার সমাধান।
• Loop tiling (blocking): বড় ডেটাকে ছোট ছোট টুকরোয় (tile) ভাগ করে প্রতিটি টুকরোর কাজ শেষ করা, যাতে টুকরোটি cache-এ থাকতে থাকতেই বারবার ব্যবহৃত হয়।

Matrix গুণ এর সেরা উদাহরণ। পর্ব ২১-এর সরল i-j-k ক্রমে ভেতরের লুপ b[k][j] পড়ে কলাম ধরে — প্রতিটি ধাপে নতুন line. ক্রম i-k-j করলে ভেতরের লুপে b আর c দুটিই সারি ধরে হাঁটে। আর tiling আরও এক ধাপ এগোয়:

/* 1) loop interchange: i-k-j, inner loop walks rows of b and c */
for (int i = 0; i < n; i++)
    for (int k = 0; k < n; k++) {
        double aik = a[i][k];                 /* hoisted out of the j loop */
        for (int j = 0; j < n; j++)
            c[i][j] += aik * b[k][j];
    }

/* 2) tiling: work on T x T blocks that fit in cache (n multiple of T) */
for (int ii = 0; ii < n; ii += T)
    for (int kk = 0; kk < n; kk += T)
        for (int jj = 0; jj < n; jj += T)
            for (int i = ii; i < ii + T; i++)
                for (int k = kk; k < kk + T; k++) {
                    double aik = a[i][k];
                    for (int j = jj; j < jj + T; j++)
                        c[i][j] += aik * b[k][j];
                }

দুটি সংস্করণই একই গুণফল দেয়, দুটিই O(n³) — পার্থক্য শুধু ঘর ছোঁয়ার ক্রমে। tiling-এ T × T মাপের টুকরোগুলো (T = ৩২ হলে প্রতিটি ৮ KB) একসাথে cache-এ ধরে, তাই b-এর একটি টুকরো একবার এনে অনেকবার ব্যবহার হয়। বড় matrix-এ এতে অনেক মেশিনে কয়েক গুণ গতি আসে। তবে বাস্তবে বড় matrix গুণের জন্য OpenBLAS-এর মতো লাইব্রেরি ব্যবহার করুন — সেখানে প্রতিটি CPU-র জন্য আলাদা tuning করা।

Auto-vectorization — এক নির্দেশে অনেক সংখ্যা

আধুনিক CPU-র একটি নির্দেশ একসাথে ৪, ৮ বা ১৬টি সংখ্যার ওপর কাজ করতে পারে — SIMD. সাধারণ লুপকেও compiler নিজে SIMD-এ বদলাতে পারে (auto-vectorization), যদি লুপ সরল হয়: ডেটা পাশাপাশি, aliasing-এর ভয় নেই, ভেতরে জটিল branch বা অজানা ফাংশন-ডাক নেই। কোন লুপ vectorize হলো, জিজ্ঞেস করা যায়:

gcc -O3 -fopt-info-vec-optimized add.c -o add
# add.c:3:23: optimized: loop vectorized using 16 byte vectors   (sample)

Assembly নিজের চোখে দেখতে Compiler Explorer (godbolt.org) সবচেয়ে সহজ — বাঁ পাশে C, ডান পাশে assembly. ymm register বা addps-এর মতো নির্দেশ দেখলে বুঝবেন SIMD হয়েছে।

৮ · Thread আর allocation-এর লুকানো খরচ — false sharing, malloc

পর্ব ৫২-এ মাল্টিথ্রেডিং শিখেছেন। এখানে cache আরেকটি অদ্ভুত সমস্যা তৈরি করে। প্রতিটি core-এর নিজস্ব L1 আর L2 cache আছে। একটি core কোনো line-এ লিখলে অন্য সব core-এর কাছে থাকা সেই line-এর কপি বাতিল করতে হয়, নইলে তারা পুরোনো মান পড়বে। এই হিসাব রাখার ব্যবস্থাকে বলে cache coherence. সমস্যা হলো, এই হিসাব চলে পুরো line ধরে, আলাদা ভ্যারিয়েবল ধরে নয়।

cache line (64 বাইট): [ a | b | ........ ]
thread 1 (core 0):  cnt.a++  বারবার
thread 2 (core 1):  cnt.b++  বারবার
দুজন আলাদা ভ্যারিয়েবলে লেখে — কোনো data race নেই

core 0 L1: [ a=1 | b=0 ]  মালিক (লেখার অধিকার)
core 1 L1: [ বাতিল ]
লিখতে হলে line-এর একমাত্র মালিক হতে হয়

core 0 L1: [ বাতিল ]
core 1 L1: [ a=1 | b=1 ]  মালিক
b লিখতে পুরো line core 0 থেকে আনতে হলো

core 0: a++ -> line টানো
core 1: b++ -> line টানো
core 0: a++ -> line টানো
 ...
প্রতিটি ++ এখন L1-এর কয়েক cycle নয়, core-থেকে-core যাতায়াত

struct padded { alignas(64) long v; };   /* sizeof = 64 */
struct padded cnt[2];   /* cnt[0] আর cnt[1] আলাদা line-এ */

আরও ভালো: প্রতিটি thread নিজের local ভ্যারিয়েবলে
গোনে, শেষে একবার মোটে যোগ করে।

False sharing ধরা কঠিন: কোডে ভুল নেই, ThreadSanitizer-ও কিছু বলে না। লক্ষণ একটাই — thread বাড়ালে গতি বাড়ে না। Linux-এর perf c2c টুল ঠিক এই টানাটানি খুঁজে বের করতে তৈরি।

malloc-এর দাম — arena আর pool

malloc বিনামূল্যে নয়: allocator-কে খালি জায়গা খুঁজতে হয়, হিসাব রাখতে হয়, মাঝে মাঝে OS-এর কাছে মেমরি চাইতে হয়। একটি ছোট allocation-এ সাধারণত কয়েক দশ ns — লুপে লাখো বার হলে মোট সময়ের বড় অংশ। তার ওপর আলাদা আলাদা টুকরো মেমরিতে ছড়িয়ে থাকে, locality নষ্ট হয়।

পর্ব ৪৭-এ নিজের allocator বানানোর সময় এর দুটি জনপ্রিয় সমাধান দেখেছেন:

• Arena allocator: শুরুতে একটি বড় block নিন, তারপর প্রতিটি চাওয়ায় শুধু একটি pointer সামনে সরান (bump allocation) — কয়েকটি নির্দেশের কাজ। আলাদা free নেই; কাজ শেষে পুরো arena একবারে ছেড়ে দিন। একটি HTTP request বা একটি ফাইল parse করার সব অস্থায়ী ডেটার জন্য আদর্শ। বোনাস: পরপর নেওয়া জিনিস মেমরিতেও পাশাপাশি থাকে।
• Memory pool: একই মাপের অনেক বস্তুর (যেমন linked list-এর node) জন্য আগে থেকে সারি সারি খোপ রাখা; খালি খোপগুলো একটি free list-এ। নেওয়া আর ফেরত দেওয়া দুটিই O(1), আর node-গুলো কাছাকাছি থাকে।

তবে প্রথম কাজ অপ্রয়োজনীয় allocation বাদ দেওয়া — লুপের ভেতরে প্রতিবার নতুন buffer না নিয়ে বাইরে একবার নেওয়া। profiler-এ malloc/free বড় অংশ নিলে তবেই allocator বদলানোর কথা ভাবুন।

৯ · মাপার বিজ্ঞান — benchmark, profiler আর Amdahl's law

সব কৌশলের আগে একটি শর্ত: আগে জানুন সময় কোথায় যাচ্ছে। প্রক্রিয়াটি একটি চক্র: সঠিক কোড আর টেস্ট → লক্ষ্য ঠিক করা ও বর্তমান অবস্থা মাপা → profiler দিয়ে সবচেয়ে গরম জায়গা (hot spot) খোঁজা → একটি পরিবর্তন → আবার মাপা ও টেস্ট চালানো। একবারে একটি পরিবর্তন, যাতে বোঝা যায় কোনটি কাজ করল।

নিজে মাপা — clock_gettime দিয়ে ছোট benchmark

Benchmark লিখতে clock() নয় (সেটি CPU সময় মাপে, পর্ব ৩৯), বরং POSIX-এর clock_gettime ব্যবহার করুন CLOCK_MONOTONIC ঘড়ি দিয়ে — এই ঘড়ি কখনো পেছনে যায় না, কেউ সিস্টেমের সময় বদলালেও না। নিচের কাঠামোটি শুধু দেখার জন্য (এখানে চালানোর বোতাম নেই, কারণ সময় প্রতিবার আলাদা আসে):

#define _POSIX_C_SOURCE 199309L
#include <stdio.h>
#include <time.h>

static double now_sec(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec / 1e9;
}

/* inside main, after building the table t: */
long checksum = 0;
for (int w = 0; w < 3; w++) checksum += sum_table(t);   /* warm-up runs */
double best = 1e9;
for (int r = 0; r < 10; r++) {                           /* repeat */
    double t0 = now_sec();
    checksum += sum_table(t);
    double dt = now_sec() - t0;
    if (dt < best) best = dt;
}
printf("best %.3f ms, checksum %ld\n", best * 1e3, checksum); /* use the result */

এই ছোট কাঠামোয় benchmark-এর পাঁচটি নিয়ম লুকিয়ে আছে:

1. Optimization চালু করে build করুন (-O2) — যেভাবে আসল প্রোগ্রাম চলবে।
2. Warm-up: প্রথম দৌড়ে cache খালি, পেজ প্রথমবার আসে, CPU-র ঘড়ি গতি তোলে — হিসাবে ধরবেন না।
3. বারবার চালান: একবারের মাপে অন্য প্রোগ্রাম আর interrupt মিশে থাকে; কয়েকবার চালিয়ে সবচেয়ে কম বা median নিন।
4. ফলাফল ব্যবহার করুন: হিসাবের ফল কোথাও ব্যবহার না হলে -O2-এ compiler পুরো হিসাবটাই মুছে দিতে পারে (dead code elimination) — আর আপনি দেখবেন “০ ns”! এজন্যই checksum জমিয়ে শেষে ছাপানো।
5. বাস্তবের মাপের ইনপুট: ১০০ ঘরের টেবিল পুরোটা L1-এ ধরে, সেখানে সারি-কলামের পার্থক্য দেখাই যাবে না। আসল ডেটার মাপে মাপুন।

Profiler — অনুমান নয়, গণনা

বড় প্রোগ্রামে কোন ফাংশন বা কোন লাইন সময় খাচ্ছে, তা বলে profiler. Linux-এ সবচেয়ে শক্তিশালী হাতিয়ার perf, যা CPU-র ভেতরের হার্ডওয়্যার counter পড়ে — কতগুলো cycle গেল, কতগুলো নির্দেশ চলল, কতবার cache miss আর branch-এর ভুল আন্দাজ হলো:

gcc -O2 -g sales.c -o sales
perf stat -e cycles,instructions,cache-misses,branch-misses ./sales
perf record -g ./sales      # sample where time goes
perf report                 # browse hottest functions and lines

নিচের আউটপুটটি উদাহরণ হিসেবে বানানো নমুনা — আপনার মেশিনে সংখ্যা আলাদা হবে, কিন্তু কোন লাইনে কী খুঁজবেন তা একই:

# sample output (illustrative) — column-order version
 Performance counter stats for './sales':

     3,912,455,120      cycles
     1,204,881,307      instructions        #  0.31  insn per cycle
        98,345,210      cache-misses
           412,906      branch-misses

সবচেয়ে কাজের সংখ্যা insn per cycle (IPC) — প্রতি cycle-এ কয়টি নির্দেশ শেষ হলো। IPC ১-এর অনেক নিচে আর cache-misses বিশাল মানে CPU বেশিরভাগ সময় মেমরির অপেক্ষায়। সারি-ক্রমে বদলানোর পর cache-misses কমবে, IPC বাড়বে — তখন জানবেন উন্নতি কেন হলো।

Cachegrind আমাদের খেলনা simulator-এরই বড় ভাই: সিমুলেট করা cache-এ প্রতিটি লাইনের miss গোনে। ধীর চলে, কিন্তু ফল প্রতিবার এক। (নতুন Valgrind-এ cache সিমুলেশন ডিফল্টভাবে বন্ধ, তাই --cache-sim=yes লাগে।) পর্ব ৩১-এ দেখা Valgrind-এরই আরেকটি টুল।

Amdahl's law — কতটা লাভ সম্ভব, আগেই হিসাব

ধরুন রিপোর্ট প্রোগ্রামের মোট সময়ের ২০% যায় একটি সর্টিং ফাংশনে। আপনি দুই দিন খেটে সেটিকে ১০ গুণ দ্রুত করলেন। পুরো প্রোগ্রাম কত দ্রুত হবে? Amdahl's law বলে:

এখানে p = ০.২, s = ১০: 1 ÷ (০.৮ + ০.০২) ≈ ১.২২ — দুই দিনের পরিশ্রমে মাত্র প্রায় ২২% লাভ; ফাংশনটি অসীম দ্রুত হলেও সর্বোচ্চ ১.২৫ গুণ। অথচ ৮০% সময় নেওয়া অংশকে মাত্র ২ গুণ দ্রুত করলেই 1 ÷ (০.২ + ০.৪) ≈ ১.৬৭ গুণ। শিক্ষা: বড় অংশে ছোট উন্নতি প্রায়ই ছোট অংশে বড় উন্নতিকে হারায় — আর কোন অংশ বড়, তা বলে profiler.

১০ · AI-এর যুগে — মাপা ছাড়া “optimization”

AI-কে “কোড দ্রুত করে দাও” বললে সে কিছু বদলে আত্মবিশ্বাসে বলে “এখন অনেক দ্রুত” — অথচ আপনার মেশিনে কোড চালায়নি, মাপেনি, ডেটার মাপও জানে না।

AI সাধারণত পারফরম্যান্সে যেসব ভুল করে

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

• পরিবর্তনের আগে ও পরে একই ইনপুটে, -O2-এ, warm-up আর কয়েকবার চালিয়ে মেপেছি
• পুরোনো আর নতুন সংস্করণের ফল হুবহু মিলিয়েছি (টেস্ট বা checksum দিয়ে)
• বদলানো অংশটি সত্যিই profiler-এর hot spot — ঠান্ডা কোডে সময় নষ্ট করিনি
• perf stat বা cachegrind দিয়ে দেখেছি উন্নতির কারণ (কম miss, কম branch-miss, বেশি IPC)
• -Ofast, -march=native, restrict, packed struct — প্রতিটির ঝুঁকি বুঝে তবেই রেখেছি
• জটিলতা বাড়লে সেই দাম লাভের তুলনায় যুক্তিসংগত কি না ভেবেছি, আর কোডে মন্তব্য রেখেছি কেন এমন লেখা