‏چرا پارسر Yuku سه تا ده برابر سریع‌تره

Yuku یه پارسر JavaScript/TypeScript ـه که با زبان Zig نوشته شده و به گفته‌ی نویسنده‌اش ۳ تا ۱۰ برابر سریع‌تر از گزینه‌های موجود روی npm کار می‌کنه، در حالی که یه نفره نوشته شده. حرف اصلی مقاله اینه که گرامر هیچ‌وقت بخش سخت ماجرا نبوده؛ recursive descent مسئله‌ی حل‌شده‌ایه که تقریباً می‌شه از خود اسپک ECMAScript رونویسی‌ش کرد. چیزی که سرعت رو تعیین می‌کنه سؤالیه که اسپک دربارش ساکته: نود تو حافظه چه شکلیه؟

نویسنده دو واقعیت سخت‌افزاری رو مبنا می‌ذاره. اول اینکه یه load که تو کش نباشه و بره سراغ حافظه‌ی اصلی حدود ۱۰۰ نانوثانیه خرج برمی‌داره، در حالی که یه عملیات حسابی کسری از نانوثانیه‌ست؛ پس برنامه‌ای که دنبال پوینترها بین آبجکت‌های پراکنده می‌دوه، عمرش رو پشت load معطل می‌مونه. دوم اینکه هر صدا زدن آلوکیتور عمومی ده‌ها تا صدها نانوثانیه هزینه داره و آبجکت‌های مرتبط رو تو فضای آدرس پخش می‌کنه.

مقیاس مسئله رو هم مشخص می‌کنه: Yuku تقریباً یه نود AST به ازای هر دو بایت سورس درنظر می‌گیره، یعنی یه فایل ۱۰۰ کیلوبایتی حدود ۵۰٬۰۰۰ نود می‌شه. اگه کتابی بسازیش، این یعنی ۵۰٬۰۰۰ بار alloc، ۵۰٬۰۰۰ بار free و بعدش هر پیمایش تبدیل می‌شه به دنبال کردن پوینتر تو حافظه‌ی سرد. با آرایه‌های تخت، همون چیز می‌شه چند تا alloc، پیمایش خطی و یه free.

AST کتابی تو یه زبان نیتیو این شکلیه؛ درست و خواناست، ولی به گفته‌ی نویسنده همه‌چیزش با ماشین سر جنگ داره: هر *Node یه alloc جداست، هر یال ۸ بایت پوینتره (اغلب بزرگ‌تر از خود داده‌ای که بهش اشاره می‌کنه) و چون پر از آدرس مطلقه، به یه فضای آدرس جوش خورده — نه می‌شه ریختش رو دیسک، نه بین پروسه‌ها به اشتراک گذاشتش.

const Node = union(enum) {
    binary: struct { op: Op, left: *Node, right: *Node },
    call: struct { callee: *Node, args: []*Node },
    identifier: struct { name: []const u8 },
};

راه‌حل Yuku اینه که هر پوینتر با یه ایندکس عددی داخل یه آرایه‌ی تخت جایگزین بشه. NodeIndex یه u32 ـه: نصف اندازه‌ی پوینتر، مستقل از موقعیت حافظه، و با یه مقدار رزروشده برای «فرزند ندارم» تا فرزندهای اختیاری هزینه‌ی اضافه نداشته باشن. خود درخت هم چند تا آرایه‌ست به‌علاوه‌ی یه آرنا: nodes برای نودها، extras برای فرزندهای با طول متغیر، یه string pool، و آرنایی که با یه deinit کل درخت رو آزاد می‌کنه.

یه تصمیم مهم دیگه استفاده از std.MultiArrayList ـه که داده رو به‌شکل struct-of-arrays نگه می‌داره: یه ستون برای payload و یه ستون برای span، با ایندکس مشترک. نتیجه اینه که پیمایشی که فقط به نوع نود کار داره، span‌ها رو الکی وارد کش نمی‌کنه و برعکس. اندازه‌ها هم با comptime قفل شدن تا اضافه شدن یه فیلد به یه واریانت، بی‌سروصدا حجم هر ۵۰٬۰۰۰ نود رو باد نکنه.

آلوکیتور هم کامل از مسیر داغ بیرون می‌ره: پارسر از روی طول سورس تعداد نود رو تخمین می‌زنه و ظرفیت رو از اول رزرو می‌کنه، پس اضافه کردن نود عملاً فقط زیاد شدن یه شمارنده‌ست. آرایه فقط رشد می‌کنه و هیچ‌وقت فشرده نمی‌شه، برای همین یه ایندکس تا آخر عمر درخت معتبر می‌مونه. ساخت هم پایین‌به‌بالاست: هر روتین اول فرزندهاش رو می‌سازه، بعد خودش رو اضافه می‌کنه و ایندکسش رو به والد برمی‌گردونه.

نویسنده با یه مثال ملموس نشون می‌ده که let x = 1 + 2; هفت تا نود می‌سازه: فرزندها قبل از والد میان، ریشه آخرین نود اضافه‌شده‌ست، هر یال یه عدد کوچیکه نه آدرس، و اسم شناسه به‌جای کپی رشته فقط بازه‌ی بایتی 4..5 از خود سورسه. در آخر هم می‌گه اگه پارسر فقط یه فرانت‌اند داخلی باشه و مصرف‌کننده‌ی بیرونی نداشته باشه، می‌شه نود رو تا حدود ۱۳ بایت کوچیک کرد؛ اون‌وقت tag تعیین می‌کنه دو کلمه‌ی data چطور خونده بشن و هر دسترسی از یه switch رد می‌شه.

const Node = struct {
    tag: Tag,        // 1 byte: node kind, and the key to reading `data`
    main_token: u32, // the token this node hangs off
    data: [2]u32,    // two words whose meaning depends on `tag`
};

نکات کلیدی:

• ادعای مقاله: سرعت پارسر رو نمایش داده تو حافظه تعیین می‌کنه، نه گرامر
• هر cache miss حدود ۱۰۰ نانوثانیه‌ست؛ درخت پوینتری یعنی پیمایش پر از load غیرقابل‌پیش‌بینی
• ایندکس u32 به‌جای پوینتر: نصف حجم، مستقل از فضای آدرس، قابل ذخیره روی دیسک
• struct-of-arrays باعث می‌شه هر پاس فقط ستون موردنیازش رو بخونه
• تخمین تعداد نود از روی طول سورس، آلوکیتور رو از مسیر داغ بیرون می‌بره
• برای فرانت‌اندهای داخلی می‌شه نود رو تا حدود ۱۳ بایت فشرده کرد