Memory, Cache line ও NUMA

সমস্যাটা কী?

বেশিরভাগ প্রোগ্রামার ভাবে memory access "free" — একটা variable পড়া মানে instant। বাস্তবে এটা ভয়াবহ ভুল ধারণা। আধুনিক CPU প্রতি সেকেন্ডে বিলিয়ন instruction চালাতে পারে, কিন্তু main memory (RAM) থেকে একটা data আনতে লাগে প্রায় ১০০ ন্যানোসেকেন্ড — যে সময়ে CPU কয়েকশো instruction চালাতে পারত। অর্থাৎ CPU প্রায়ই বসে থেকে data-র জন্য অপেক্ষা করে, যাকে বলে stall।

Low-latency সিস্টেমে অ্যালগরিদমের Big-O যত গুরুত্বপূর্ণ, তার চেয়ে বেশি গুরুত্বপূর্ণ হয়ে দাঁড়ায় — তোমার data মেমরিতে কীভাবে সাজানো এবং CPU তা কত দ্রুত cache থেকে পেতে পারে। দুটি O(n) অ্যালগরিদমের মধ্যে একটি অন্যটির চেয়ে ১০ গুণ দ্রুত হতে পারে শুধু memory layout-এর কারণে।

মূল ধারণা

Cache line হলো সেই ক্ষুদ্রতম একক (সাধারণত ৬৪ বাইট) যা CPU একবারে main memory থেকে cache-এ নিয়ে আসে। তুমি ১ বাইট চাইলেও CPU পুরো ৬৪ বাইট আনে।

CPU-তে memory একটি hierarchy-তে সাজানো — যত কাছে, তত দ্রুত, কিন্তু তত ছোট:

• Register: সবচেয়ে দ্রুত, ০ cycle।
• L1 cache: ~১ ns, কয়েক KB।
• L2 cache: ~৪ ns, কয়েকশো KB।
• L3 cache: ~১০-৪০ ns, কয়েক MB (cores শেয়ার করে)।
• Main memory (RAM): ~১০০ ns, GB-scale।

যখন CPU যে data চায় তা cache-এ থাকে, সেটা cache hit। না থাকলে cache miss — তখন নিচের ধীর স্তর থেকে আনতে হয়। প্রতিটি miss মানে অনেকগুলো হারানো cycle। তাই খেলাটা হলো — cache hit rate যতটা সম্ভব বাড়ানো।

কীভাবে কাজ করে

Locality — দুই ধরনের

CPU cache দুই ধরনের locality-র উপর নির্ভর করে দ্রুত কাজ করে:

• Temporal locality: এইমাত্র ব্যবহৃত data শিগগিরই আবার লাগবে — তাই cache-এ রাখা হয়।
• Spatial locality: একটি data-র পাশের data-ও শিগগিরই লাগবে — তাই পুরো cache line আনা হয়।

এজন্যই array (contiguous memory) প্রায়ই linked list (scattered memory)-এর চেয়ে অনেক দ্রুত traverse হয়, যদিও দুটোরই Big-O সমান। Array-তে একটি cache line load করলে পরের কয়েকটি উপাদানও বিনামূল্যে চলে আসে, আর CPU-র prefetcher আগেভাগে পরের line এনে রাখে।

False sharing — নীরব ঘাতক

ধরো দুটি thread, দুটি আলাদা variable a ও b লেখে। মনে হবে কোনো conflict নেই। কিন্তু যদি a ও b একই ৬৪-বাইট cache line-এ থাকে, তাহলে একটি core a লিখলে cache coherence protocol অন্য core-এর সেই line-এর copy invalidate করে দেয় — যদিও সে শুধু b নিয়ে কাজ করছে। ফলে cache line দুই core-এর মধ্যে বারবার "bounce" করে, যাকে বলে cache line ping-pong। এতে performance ১০ গুণ পর্যন্ত কমে যেতে পারে।

সমাধান হলো padding — variable-গুলোকে আলাদা cache line-এ ঠেলে দেওয়া:

struct Counters {
    long a;
    char pad[56];   // a-কে নিজের cache line-এ আলাদা করে রাখে (8 + 56 = 64)
    long b;
};

(Java-তে @Contended annotation এ কাজটি করে।)

NUMA — মেমরিরও দূরত্ব আছে

বড় সার্ভারে একাধিক CPU socket থাকে। NUMA (Non-Uniform Memory Access) মানে — প্রতিটি socket-এর নিজস্ব "local" memory আছে, যা দ্রুত। কিন্তু এক socket-এর thread যদি অন্য socket-এর memory পড়তে চায় (remote access), তাকে inter-socket interconnect (যেমন Intel UPI বা AMD Infinity Fabric) পেরোতে হয় — যা উল্লেখযোগ্যভাবে ধীর।

Access ধরন	আনুমানিক latency	মন্তব্য
L1 hit	~১ ns	দ্রুততম
L3 hit	~১০-৪০ ns	shared
Local RAM	~১০০ ns	নিজ NUMA node
Remote RAM (NUMA)	~১৫০-৩০০ ns	interconnect পেরিয়ে

তাই NUMA সিস্টেমে কৌশল হলো — thread-কে যে core-এ চালাবে, তার data সেই core-এর local memory-তে রাখো (NUMA pinning / numactl)।

কৌশল

• Struct-of-Arrays (SoA) ব্যবহার করো Array-of-Structs (AoS)-এর বদলে যখন তুমি একটা field-ই বারবার scan করো — এতে cache-এ শুধু দরকারি data আসে।
• Hot/cold data আলাদা করো — ঘনঘন ব্যবহৃত field একসাথে রাখো, যাতে cache line-এ অপ্রয়োজনীয় data না ঢোকে।
• False sharing এড়াতে padding/alignment ব্যবহার করো concurrent counter-এ।
• NUMA-aware allocation — thread আর তার data একই node-এ pin করো।
• Sequential access pattern পছন্দ করো random access-এর চেয়ে।

কখন ব্যবহার করবে / করবে না

এই micro-optimization-গুলো করো শুধু সেই hot path-এ যেখানে latency সত্যিই critical এবং profiling দেখিয়েছে memory-bound bottleneck আছে। সাধারণ application কোডে এসব করতে গেলে কোড দুর্বোধ্য হবে এবং সময়ের অপচয় হবে।

বাস্তব উদাহরণ

LMAX Disruptor তাদের ring buffer-এ সচেতনভাবে cache-line padding ব্যবহার করে false sharing এড়ায় — এটাই তাদের অবিশ্বাস্য throughput-এর একটা বড় কারণ।

গেম ইঞ্জিন (Entity-Component-System আর্কিটেকচার) data-oriented design ব্যবহার করে component-গুলোকে contiguous array-তে রাখে, যাতে প্রতি frame-এ লাখ লাখ entity দ্রুত process হয়।

Database ও in-memory store (যেমন Redis, ScyllaDB) NUMA-aware — ScyllaDB তো প্রতিটি core-কে আলাদা shard দিয়ে shared-nothing architecture বানিয়ে cross-core ও cross-NUMA traffic প্রায় শূন্যে নামিয়েছে।