আন্দাজের আগে মাপো: কত সময়, কত memory, আর কোথায়

Kenji মিরপুরের একটা coaching centre-এ পড়ায়। প্রতি সন্ধ্যায় ওর script দিনের sign-in-গুলো পড়ে, আর যারা এসেছিল তাদের একটা report print করে। প্রথম সপ্তাহে চোখের পলকে হয়ে যেত। এখন centre বড় হয়েছে, আর report আসতে আসতে Kenji এক কাপ চা বানিয়ে ফেলতে পারে।

Kenji নিশ্চিত, কারণটা ও জানে। "String জোড়াটাই সমস্যা," ও বলে। "+= দিয়ে লাইন যোগ করলে প্রতিবার পুরো report copy হয়।" এক সন্ধ্যা খেটে ও পুরোটা array আর join দিয়ে আবার লেখে। Report ঠিক আগের মতোই ধীর।

Amara আন্দাজ করে না। Script-এর প্রতিটা অংশের চারপাশে ও একটা stopwatch বসায়, একবার চালায়। একটা অংশই প্রায় পুরো সময়টা খায়, আর সেটা string না। এই module Amara-র এই অভ্যাস নিয়ে: আগে মাপো, তারপর একটা জিনিস বদলাও, তারপর আবার মাপো। তিনটা প্রশ্ন এখানে আসবে। কত সময় লাগে? কতটা memory ধরে রাখে? আর ভাঙলে, কোথায়?

একটা ধীর program আর একটা ভুল আন্দাজ

এটা Kenji-র script-এর একটা ছোট copy। ও 6000 student-এর 30000 টা sign-in বানায়, প্রতিটা student-কে একবার রাখে, তারপর report বানায়। পুরো জিনিসটা একটাই stopwatch দিয়ে মাপা।

const signIns = [];
for (let i = 0; i < 30000; i++) signIns.push("s" + ((i * 7919) % 6000));

const start = performance.now();
const students = [];
for (const id of signIns) {
  if (!students.includes(id)) students.push(id);
}
let report = "";
for (const id of students) report += id + " present\n";
const ms = performance.now() - start;

console.log(students.length + " students, " + report.length + " characters");
console.log("whole script: " + ms.toFixed(1) + " ms");

6000 students, 82890 characters
whole script: 310.1 ms

প্রথম লাইনটা ফলাফল, আর সেটা ঠিক। দ্বিতীয় লাইনটা এই run-এর সময়, millisecond-এ। পুরো script-এর জন্য একটা সংখ্যা তোমাকে বলে যে ওটা ধীর। কোন অংশটা ধীর, সেটা বলে না। Kenji-র আন্দাজ ওই ফাঁকটা ভরেছিল, আর আন্দাজটা ভুল ছিল।

performance.now: millisecond-এর একটা stopwatch

performance.now() ফেরত দেয় program শুরুর পর থেকে কত millisecond গেছে, দশমিকসহ একটা সংখ্যা। দুবার পড়ো, তারপর বিয়োগ করো। পার্থক্যটাই হলো দুই reading-এর মাঝের code কতক্ষণ নিল।

const a = performance.now();
let sum = 0;
for (let i = 0; i < 1000000; i++) sum += i;
const b = performance.now();

console.log(typeof a, a < b);
console.log("sum " + sum);
console.log("the loop took " + (b - a).toFixed(2) + " ms");

number true
sum 499999500000
the loop took 5.53 ms

Reading-টা একটা সাধারণ number, আর দ্বিতীয় reading সবসময় বড়। এটা একটা monotonic ঘড়ি: শুধু সামনে এগোয়, কেউ computer-এর সময় বদলে দিলেও। Date.now() হলো দেয়ালের ঘড়ি, পূর্ণ millisecond-এ, আর সেটা লাফ দিতে পারে। Code মাপার জন্য performance.now() নাও।

শেষ লাইনটা প্রতিবার চালালে একটু একটু বদলায়। Machine-টা অন্য program-ও ভাগ করে নেয়, আর engine প্রথমবার কোনো code চালানোর সময় বাড়তি কাজ করে। তাই একটা সময় মানে সবসময় "এই run-এ"। Lesson 03 একটা ছোট helper বানায়, যেটা code কয়েকবার চালিয়ে মাঝের মানটা রাখে।

একবারে একটা অংশ মাপো

Amara-র প্রথম চাল ছিল প্রতিটা অংশের চারপাশে আলাদা stopwatch বসানো। তাহলে একই run-এ সংখ্যাগুলো একে অপরের সাথে মেলানো যায়।

const signIns = [];
for (let i = 0; i < 30000; i++) signIns.push("s" + ((i * 7919) % 6000));

let t = performance.now();
const students = [];
for (const id of signIns) {
  if (!students.includes(id)) students.push(id);
}
const dedupeMs = performance.now() - t;

t = performance.now();
let report = "";
for (const id of students) report += id + " present\n";
const reportMs = performance.now() - t;

console.log("keep each student once: " + dedupeMs.toFixed(1) + " ms");
console.log("build the report:       " + reportMs.toFixed(1) + " ms");
console.log("dedupe is the slow part: " + (dedupeMs > reportMs * 10));

keep each student once: 282.3 ms
build the report:       0.4 ms
dedupe is the slow part: true

আগে তৃতীয় লাইনটা দেখো। ওটা দুটো অংশকে মেলায়, আর millisecond বদলালেও প্রতিটা run-এ ওটা সত্যি থাকে। +=-এর loop কখনোই সমস্যা ছিল না। সময়টা যায় students.includes(id)-এ। প্রতিটা call পুরো students array হাঁটে, তাই 30000 sign-in মানে কয়েক কোটি তুলনা।

ওই তুলনার লাইনটা একটা ভালো অভ্যাস। একা একটা সময় run থেকে run-এ বদলায়। একই run-এ দুটো অংশের তুলনা অনেক বেশি স্থির, আর সিদ্ধান্তটা তুমি আসলে ওটার ওপরেই নাও।

একটা জিনিস বদলাও, তারপর আবার মাপো

এবার Amara শুধু ধীর অংশটা বদলায়। Set (Module 16 পুরোটা শেখায়) এমন একটা collection, যেটা প্রতিটা value একবার রাখে, আর সব না হেঁটেই বলে দেয় "এটা আছে কি না"। ও array-টা বদলে Set বসায়, তারপর একইভাবে আবার মাপে।

const signIns = [];
for (let i = 0; i < 30000; i++) signIns.push("s" + ((i * 7919) % 6000));

let t = performance.now();
const seen = [];
for (const id of signIns) if (!seen.includes(id)) seen.push(id);
const withArray = performance.now() - t;

t = performance.now();
const set = new Set();
for (const id of signIns) set.add(id);
const withSet = performance.now() - t;

console.log("same students: " + (seen.length === set.size));
console.log("array and includes: " + withArray.toFixed(1) + " ms");
console.log("Set:                " + withSet.toFixed(1) + " ms");

same students: true
array and includes: 312.3 ms
Set:                4.8 ms

প্রথম লাইন যাচাই করে যে দুই উপায়েই উত্তর এক। এটা কখনো বাদ দিয়ো না: দ্রুত কিন্তু ভুল উত্তর কোনো উন্নতি না। বাকি দুই লাইন এই run-এর সময়। এই run-এ Set অনেক ব্যবধানে দ্রুত, আর কেন, সেটা খরচের ভাষায় বুঝিয়ে দেয় Lesson 04।

খেয়াল করো Amara কী করেনি। ও report, পড়ার অংশ, অন্য কিছুই আবার লেখেনি। একটা মাপা সমস্যা, একটা বদল, প্রমাণের জন্য একটা মাপ। Kenji-র সন্ধ্যার খাটুনি গিয়েছিল এমন একটা অংশে, যার খরচ প্রায় শূন্য।

কতটা memory: process.memoryUsage

সময় একটা প্রশ্ন। Memory দ্বিতীয়টা। process.memoryUsage() byte গোনা একটা object ফেরত দেয়। সবচেয়ে বেশি পড়বে heapUsed: JavaScript-এর heap এই মুহূর্তে কত byte ধরে আছে। Heap হলো সেই memory, যেখানে object, array আর string থাকে।

const mb = (bytes) => Math.round(bytes / 1024 / 1024);
const before = process.memoryUsage().heapUsed;

const marks = [];
for (let i = 0; i < 1000000; i++) marks.push({ roll: i, mark: i % 100 });

const after = process.memoryUsage().heapUsed;
console.log("objects kept: " + marks.length);
console.log("heap grew by about " + mb(after - before) + " MB");
console.log("more than 20 MB: " + (after - before > 20 * 1024 * 1024));

objects kept: 1000000
heap grew by about 55 MB
more than 20 MB: true

Program-টা দশ লাখ ছোট object রেখে দেয়, আর heap বাড়ে দ্বিতীয় লাইনের পরিমাণে। ওটা "প্রায়", দুই কারণে। Heap-এ এমন garbage-ও থাকে যা collector এখনো সাফ করেনি। আর engine memory নেয় বড় বড় টুকরোয়, object ধরে ধরে না। তাই heapUsed-কে একটা মোটামুটি স্তর হিসেবে পড়ো, আর স্তরগুলো মেলাও, যেমন তৃতীয় লাইন করে।

বাকি field-গুলোরও কাজ আছে। rss হলো operating system process-টাকে যত memory দিয়েছে তার সবটা, code আর buffer সহ। heapTotal হলো engine কতটা heap আগে থেকে নিয়ে রেখেছে। প্রতিটা field দেখায় Lesson 02, আর এর পেছনের garbage collector বোঝায় Lesson 05।

কোথায় ভাঙল: stack trace

তৃতীয় প্রশ্নটা আসে যখন একটা program error দিয়ে থেমে যায়। Module 10-এ তুমি err.stack দেখেছ, যে text stack frame-গুলোর list দেয়: error তৈরির মুহূর্তে যে call-গুলো চলছিল তাদের শিকল। প্রথম লাইনে error-এর নাম। তারপর at দিয়ে শুরু প্রতিটা লাইন একটা frame, সবচেয়ে ভেতরেরটা আগে।

function toCents(price) {
  return Math.round(price.amount * 100);
}
function total(rows) {
  return rows.reduce((sum, row) => sum + toCents(row.price), 0);
}
function report(rows) {
  return "total " + total(rows);
}
try {
  console.log(report([{ price: { amount: 120.5 } }, { cost: 30 }]));
} catch (err) {
  console.log(err.message);
  for (const line of err.stack.split("\n").filter((l) => l.includes("main.js"))) {
    console.log(line.trim().replace(/[^\s(]*main\.js/, "main.js"));
  }
}

Cannot read properties of undefined (reading 'amount')
at toCents (main.js:2:27)
at main.js:5:42
at total (main.js:5:15)
at report (main.js:8:21)
at Object.<anonymous> (main.js:11:15)

ওপর থেকে frame-গুলো পড়ো। toCents ভেঙেছে লাইন 2-এ: দ্বিতীয় row-তে price নেই, তাই price হলো undefined, আর ওর amount পড়তে গিয়ে আটকে যায়। পরের frame-টার কোনো নাম নেই। ওটা লাইন 5-এর arrow function, যেটাকে reduce প্রতিটা row-এর জন্য ডাকে। তারপর আসে total, report, আর Object.<anonymous>, file-এর top-কে Node এই নামেই ডাকে।

প্রতিটা frame শেষ হয় file, লাইন আর column দিয়ে। Program-টা শুধু main.js-এর frame রাখে আর folder-টা ফেলে দেয়, যাতে তুমি শুধু নিজের code দেখো।

একবার পড়লেই stack trace "কোথায়"-এর উত্তর দেয়। এটা না থাকলে তুমি প্রতিটা function-এ print বসাতে, খারাপটা না পাওয়া পর্যন্ত। এটা থাকলে সোজা লাইন 2-এ যাও, আর জিজ্ঞেস করো row.price নেই কেন।

কিছু না ভাঙলেও stack থাকে। নিচের widget একই function-গুলোর একটা run আবার চালায়, এবার ভালো data দিয়ে। সবচেয়ে ভেতরের call, toCents, new Error().stack ধরে রাখে, throw না করেই, আর frame-গুলো আসে সেই আসল text থেকে। দেখো, function শুরু হলে ওর frame push হয়, আর value return করলে pop হয়।

সবচেয়ে গভীর frame-টাই stack trace সবার আগে print করে। এজন্যই trace পড়তে হয় "ভেতর থেকে বাইরে": সবচেয়ে ভেতরের call ওপরে, তোমার top-level code নিচে। await-এর ওপারে একই ছবি দেখায় Lesson 02, যেখানে stack-টা তোমার জন্য আবার জোড়া লাগানো হয়।

তিনটা প্রশ্ন, তিনটা tool

প্রতিটা ধীর বা ভাঙা program এই তিন প্রশ্নের একটা তোলে। প্রতিটার একটা প্রথম tool আছে।

এই module-এর বাকিটা প্রতিটা column-কে বড় করে। Lesson 02 বাকি tool-গুলো আনে: console.time, console.table, console.assert, debugger। Lesson 03 আর 04 মাপকে structure আর algorithm-এর সিদ্ধান্তে বদলায়। Lesson 05 engine-এর ভেতরটা খোলে। Lesson 06 জড়ো করে interview-এর প্রিয় প্রশ্ন: "এটা কী print করবে?"

const t0 = performance.now();          // milliseconds since start, a decimal
work();
const ms = performance.now() - t0;     // how long work() took, on this run

const m = process.memoryUsage();       // { rss, heapTotal, heapUsed, external, arrayBuffers }
m.heapUsed;                            // bytes the JavaScript heap holds now

try { work(); } catch (err) {
  err.stack;                           // "Error: why" + one "at ..." line per frame
}

function timeIt(label, fn) {
  const t0 = performance.now();
  const result = fn();
  console.log(label + ": " + (performance.now() - t0).toFixed(2) + " ms");
  return result;
}

const words = timeIt("make words", () => Array.from({ length: 200000 }, (_, i) => "w" + (i % 500)));
const lengths = timeIt("measure them", () => words.map((w) => w.length));
const longest = timeIt("find the longest", () => Math.max(...lengths.slice(0, 50000)));
console.log("longest word: " + longest + " characters");

make words: 34.35 ms
measure them: 3.73 ms
find the longest: 0.59 ms
longest word: 4 characters

const level = () => process.memoryUsage().heapUsed;
const remembered = [];
function squareKeep(n) {
  const answer = { n, square: n * n };
  remembered.push(answer);
  return answer.square;
}
function squareForget(n) {
  return n * n;
}

let before = level();
for (let i = 0; i < 300000; i++) squareForget(i);
const forgetGrowth = level() - before;

before = level();
for (let i = 0; i < 300000; i++) squareKeep(i);
const keepGrowth = level() - before;

console.log("kept answers: " + remembered.length);
console.log("keeping grew the heap more: " + (keepGrowth > forgetGrowth));
console.log("keeping grew it by over 5 MB: " + (keepGrowth > 5 * 1024 * 1024));

kept answers: 300000
keeping grew the heap more: true
keeping grew it by over 5 MB: true

const values = [5, 3, 9, 1];
for (let round = 1; round <= 3; round++) {
  const t0 = performance.now();
  const sorted = [...values].sort((a, b) => a - b);
  const ms = performance.now() - t0;
  console.log("round " + round + ": " + sorted.join(",") + " in " + ms.toFixed(4) + " ms");
}

round 1: 1,3,5,9 in 0.0232 ms
round 2: 1,3,5,9 in 0.0074 ms
round 3: 1,3,5,9 in 0.0059 ms

const lines = [];
let t0 = performance.now();
for (let i = 0; i < 2000; i++) lines.push("row " + i);
const quiet = performance.now() - t0;

t0 = performance.now();
let printed = 0;
for (let i = 0; i < 2000; i++) {
  if (i % 1000 === 0) console.log("row " + i);
  printed++;
}
const noisy = performance.now() - t0;
console.log("printing cost more than the work: " + (noisy > quiet));

row 0
row 1000
printing cost more than the work: true

let big = new Array(2000000).fill(7);
const holding = process.memoryUsage().heapUsed;
big = null;
const after = process.memoryUsage().heapUsed;
console.log("dropped right away: " + (after < holding - 1024 * 1024));

dropped right away: false

5
start 0
read 12
parse 47
sort 51
print 60

parse 35
total 60

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

6
4 7 4 9 7 7

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

includes 8
set 6

8
enter main
enter load
exit load
enter render
enter row
enter cell
exit cell
exit row

const input = require("fs").readFileSync(0, "utf8");
const tokens = input.split(/\s+/).filter(Boolean);
let at = 0;
const next = () => tokens[at++];
const nextInt = () => Number(next());
const out = [];

// your code: read with next() and nextInt(), push every line of output to out

console.log(out.join("\n"));

depth 4
main > render > row > cell

এরপর: মাপজোখ আর debugging-এর প্রতিটা tool, একটা একটা করে, console.time থেকে debugger পর্যন্ত।