ردیابی کامپایل درجا

ردیابی کامپایل درجا (به انگلیسی: Tracing just-in-time compilation)، تکنیکی است که توسط ماشین‌های مجازی برای بهینه‌سازی اجرای یک برنامه در زمان اجرا استفاده می‌شود. این کار با ثبت یک دنباله خطی از عملیات‌هایی که اغلب انجام می‌شود، کامپایل آنها با کد ماشین محلی و اجرای آنها انجام می‌شود. این برخلاف کامپایلرهای سنتی درجا (JIT) است که به صورت مبتنی بر هر روش کار می‌کنند.

بررسی اجمالی

کامپایل درجا یک تکنیک برای افزایش سرعت اجرای برنامه‌ها توسط کامپایل قسمت‌هایی از برنامه به کد ماشین در زمان اجرا است. یکی از راه‌های طبقه‌بندی کامپایلرهای مختلف JIT با توجه به محدوده کامپایل آن‌ها است. در حالی که کامپایلرهای JIT مبتنی بر روش، یک روش را به‌طور همزمان به کد ماشین ترجمه می‌کنند، ردیابی JITها از حلقه‌هایی که اغلب اجرا می‌شوند به عنوان واحد کامپایل خود استفاده می‌کنند. ردیابی JIT بر اساس این فرضیات است که برنامه‌ها بیشتر وقت خود را در بعضی از حلقه‌های برنامه ("حلقه‌های گرم") می‌گذرانند و تکرارهای حلقه عدی اغلب مسیرهای مشابه را طی می‌کند. ماشین‌های مجازی که دارای یک JIT ردیابی هستند، اغلب محیط‌های اجرای حالت مختلط هستند، به این معنی که آن‌ها علاوه بر ردیابی JIT، یک مترجم یا کامپایلر روش نیز دارند.

جزییات فنی

کامپایلر JIT ردیابی در زمان اجرا مراحل مختلفی را طی می‌کند. ابتدا، اطلاعات پروفایل برای حلقه‌ها جمع‌آوری می‌شود. پس از شناسایی یک حلقه گرم، یک حالت ردیابی ویژه وارد می‌شود که همهٔ عملیات اجرا شده آن حلقه را ثبت می‌کند. به این دنباله عملیات، ردیابی (trace) گفته می‌شود. سپس اثر بهینه شده و با کد ماشین (ردیابی) کامپایل می‌شود. هنگامی که این حلقه دوباره اجرا شود، به جای همتای برنامه، ردیابی کامپایل شده نامیده می‌شود.

مرحله پروفایل

هدف از پروفایل شناسایی حلقه‌های گرم است. این کار اغلب با شمارش تعداد تکرارها برای هر حلقه انجام می‌شود. پس از شمارش یک حلقه از آستانه مشخصی فراتر می‌رود، حلقه گرم محسوب می‌شود، و حالت ردیابی وارد شده‌است.

مرحله ردیابی

در مرحله ردیابی، اجرای حلقه به‌طور عادی پیش می‌رود، اما علاوه بر این، هر عملیات اجرا شده در یک ردیابی ثبت می‌شود. عملیات ثبت شده معمولاً در قالب نمایندگی واسط ذخیره می‌شوند. ردیابی به دنبال تماس‌های عملکردی است که منجر به ورود آن‌ها به ردیابی می‌شود. ردیابی ادامه می‌یابد تا زمانی که حلقه به انتهای خود برسد و به سمت شروع پرش کند.

از آنجا که ردیابی با دنبال کردن یک مسیر اجرای بتونی حلقه ثبت می‌شود، اجراهای بعدی از آن ردیابی می‌تواند از آن مسیر منحرف شود. برای شناسایی مکان‌هایی که می‌تواند در آن اتفاق بیفتد، دستورالعمل‌های نگهبان ویژه در ردیابی قرار می‌گیرند. یک مثال برای چنین مکانی در صورت بیان است. نگهبان یک بررسی سریع است برای تعیین اینکه آیا شرط اصلی هنوز صحیح است یا خیر. اگر یک نگهبان نتواند، اجرای ردیابی قطع می‌شود.

از آنجا که ردیابی در حین اجرا انجام می‌شود، می‌توان ردیابی را دربرداشت که شامل اطلاعات زمان اجرا (به عنوان مثال اطلاعات نوع) باشد. این اطلاعات بعداً می‌تواند در مرحله بهینه‌سازی برای افزایش راندمان کد مورد استفاده قرار گیرد.

مرحله بهینه‌سازی و تولید کد

بهینه‌سازی ردیابی‌ها آسان است، زیرا آنها تنها یک مسیر اجرا را نشان می‌دهند، این بدان معنی است که هیچ جریان کنترلی وجود ندارد و نیازی به رسیدگی ندارد. بهینه‌سازی‌های معمولی عبارتند از: حذف زیر بیان ثابت، حذف کد مرده، تخصیص ثبات، حرکت کد بدون تغییر، تاشو ثابت و تجزیه و تحلیل فرار.^[۱]

پس از بهینه‌سازی، ردیابی به کد ماشین تبدیل می‌شود. به‌طور مشابه با بهینه‌سازی، این به دلیل ماهیت خطی ردیابی آسان است.

اجرا

بعد از اینکه ردیابی به کد ماشین کامپایل شد، می‌تواند در تکرارهای بعدی حلقه اجرا شود. اجرای ردیابی تا زمانی که نگهبان نتواند ادامه یابد ادامه دارد.

تاریخ

اگرچه ایده JIT به دهه ۱۹۶۰ بازمی‌گردد، ردیابی JITها اخیراً بیشتر مورد استفاده قرار می‌گیرند. اولین ذکر ایده ای که مشابه ایده امروز برای ردیابی JITها است در سال ۱۹۷۰ بود.^[۲] مشاهده شد که کد کامپایل شده توسط مترجم در زمان اجرا با صرفاً ذخیره کردن اقدامات انجام شده در هنگام تفسیر، می‌تواند منتقل شود.

اولین اجرای ردیابی Dynamo است، «یک سیستم بهینه سازی پویا نرم افزاری که قادر است عملکرد پردازنده محلی را به صورت شفاف بهبود بخشد زیرا این پردازنده بر روی پردازنده اجرا می‌کند».^[۳] برای این کار، جریان دستورالعمل محلی تا زمانی که دنباله دستورالعمل «گرم» پیدا شود تفسیر می‌شود. برای این دنباله نسخه بهینه‌سازی شده تولید، ذخیره و ذخیره می‌شود.

داینامو بعداً به DynamoRIO گسترش یافت. یکی از پروژه‌های مبتنی بر DynamoRIO چارچوبی برای ساخت مترجم بود که ترکیبی از ردیابی و ارزیابی جزئی بود. برای «حذف پویا مترجم از اجرای زبان» استفاده شده‌است.^[۴]

در سال ۲۰۰۶، VM مسیر گرم، اولین کامپایلر ردیابی JIT برای یک زبان سطح بالا ^{[نیازمند منبع]} شد. این VM قادر بود به صورت پویا دستورالعمل‌های بایت کد را اجرا کند، که ردیابی می‌شوند و با استفاده از ساخت تک تک استاتیک (SSA) به کد ماشین وارد می‌شوند. انگیزه VM مسیر گرم داشتن JVM کارآمد برای منابع تلفن همراه محدود شده بود.

نمونه دیگر JIT در حال ردیابی TraceMonkey است که یکی از پیاده‌سازی‌های جاوا اسکریپت موزیلا برای Firefox است (2009).^[۵] TraceMonkey در زمان اجرا، ردپاهای حلقه ای را که اغلب به زبان JavaScript پویا اجرا می‌شوند، وارد می‌کند و کد تولید شده را برای انواع پویای واقعی که در هر مسیر اتفاق می‌افتد، تخصص می‌دهد.

پروژه دیگر که از ردیابی JITها استفاده می‌کند، PyPy است. این امکان استفاده از ردیابی JITها را برای پیاده‌سازی‌های زبانی که با ابزار ترجمه، ترجمه PyPy نوشته شده‌اند را فراهم می‌کند، بنابراین عملکرد هر برنامه ای را که با استفاده از آن مترجم اجرا می‌شود، بهبود می‌بخشد. این کار با ردیابی خود مفسر، به جای برنامه ای که توسط مترجم اجرا می‌شود، امکان‌پذیر است.^[۶]

ردیابی JITها نیز توسط مایکروسافت در پروژه SPUR برای زبان مشترک متوسط (CIL) مورد کاوش قرار گرفته‌است. SPUR یک ردیاب عمومی برای CIL است، که می‌تواند برای ردیابی از طریق اجرای JavaScript نیز استفاده شود.^[۷]

نمونه ردیابی

برنامه Python زیر را در نظر بگیرید که جمع مربعات تعداد کل متوالی را محاسبه می‌کند تا زمانی که این تعداد بیش از ۱۰۰۰۰۰ باشد:

def square(x):
    return x * x

i = 0
y = 0
while True:
    y += square(i)
    if y > 100000:
        break
    i = i + 1

ردیابی برای این برنامه می‌تواند چیزی شبیه به این باشد:

 loopstart(i1, y1)
 i2 = int_mul(i1, i1)  # x*x
 y2 = int_add(y1, i2)  # y += i*i
 b1 = int_gt(y2, 100000)
 guard_false(b1)
 i3 = int_add(i1, 1)  # i = i+1
 jump(i3, y2)

توجه داشته باشید که چطور فراخوانی تابع به square به ردیابی درج شده‌است و چگونگی تبدیل عبارت if به guard_false .

جستارهای وابسته

• کامپایلر
• Dalvik (نرم‌افزار)
• HotSpot
• مترجم
• تدوین فقط در زمان
• بهینه‌سازی با راهنمایی پروفایل
• PyPy

منابع

1. "Allocation removal by partial evaluation in a tracing JIT" بایگانی‌شده در ۱۸ فوریه ۲۰۱۸ توسط Wayback Machine Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, Michael Leuschel, Samuele Pedroni, Armin Rigo - PEPM '11 Proceedings of the 20th ACM SIGPLAN workshop on Partial evaluation and program manipulation - doi:10.1145/1929501.1929508. Retrieved April 24, 2012.
2. MITCHELL, J. G. 1970. The design and construction of flexible and efficient interactive programming systems. Ph.D. dissertation. Carnegie-Mellon University, Pittsburgh, PA.
3. "Dynamo: A Transparent Dynamic Optimization System" Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia - PLDI '00 Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation - pages 1 to 12 - doi:10.1145/349299.349303. Retrieved March 28, 2012
4. "Dynamic native optimization of interpreters" Gregory T. Sullivan, Derek L. Bruening, Iris Baron, Timothy Garnett, Saman Amarasinghe - Proceeding IVME '03 Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators doi:10.1145/858570.858576. Retrieved March 21, 2012
5. "Trace-based Just-in-Time Type Specialization for Dynamic Languages" A. Gal, M. Franz, B. Eich, M. Shaver, and D. Anderson - Proceedings of the ACM SIGPLAN 2009 conference on Programming language design and implementation, 2009 doi:10.1145/1542476.1542528.
6. "Tracing the Meta-Level: PyPy’s Tracing JIT Compiler" Carl Friedrich Bolz, Antonio Cuni, Maciej Fijałkowski, Armin Rigo - ICOOOLPS '09 Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems - pages 18 to 25 - doi:10.1145/1565824.1565827. Retrieved March 21, 2012
7. "SPUR: A Trace-Based JIT Compiler for CIL" M. Bebenita et al. - Proceedings of the ACM international conference on Object oriented programming systems languages and applications doi:10.1145/1869459.1869517.

پیوند به بیرون

• وب سایت رسمی LuaJIT