نهان‌سازی درخط


نهان‌سازی در خط یک تکنیک بهینه سازی است که در زمان اجرا انجام می‌شود، و در ابتدا برای زبان اسمال‌تاک پیاده‌سازی شده است.[۱] هدف از نهان‌سازی در خط سرعت بخشیدن به یافتن تابع مورد نظر به وسیله ذخیره‌سازی نتایج جستجوی قبلی به طور مستقیم در نقطه فراخوانی است. نهان‌سازی در خط به طور خاص مورد استفاده زبان‌های گونه پویا است که بیشتر یا تمام جستجوی تابع‌های آن‌ها در زمان اجرا اتفاق می‌افتد. در این موارد جداول توابع مجازی معمولاً قابل استفاده نیست.

مثالی از نهان‌سازی در خط در زبان جاوا اسکریپت

شرح مشکل و راه‌حل ابتدایی

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

function dump(obj) {
    document.write(obj.toString());
}

از آنجایی که نوع شیء مشخص نشده است و احتمال استفاده از قابلیت method overloading وجود دارد، تصمیم‌گیری آن که در لحظه کدام تابع toString در اصل باید اجرا شود، غیر ممکن است. در عوض، یک جستجوی پویای تابع باید در زمان اجرا انجام شود. در زبان‌هایی که در زمان اجرا از نهان‌سازی استفاده نمی‌کنند، با هر بار رسیدن به نقطه فراخوانی، این جستجوی پویای تابع دوباره انجام می‌شود. از آنجا که ممکن است زنجیره وراثت وجود داشته باشد و توابع در کلاس پدرهای شیء پیاده‌سازی شده باشند، هر جستجوی پویای تابع می‌تواند یک عمل هزینه‌بر در زمان اجرا تلقی شود.

برای دستیابی به عملکرد بهتر، بسیاری از زبان‌ها در زمان اجرا از نوعی نهان‌سازی غیر در خط (none_online) استفاده می‌کنند به این صورت که نتایج تعداد محدود و مشخصی از جستجوهای پویای تابع در ساختار داده‌ای مناسب ذخیره می‌شوند. این کار می‌تواند عملکرد را مقدار خوبی بهبود ببخشد به شرطی که نهان‌سازی برای برنامه های اجرا شده به صرفه باشد (یعنی تعداد محدودی از توابع وجود داشته باشد که به طور مکرر مورد استفاده قرار بگیرد). این ساختار داده معمولاً به عنوان حافظه نهان جستجوی تابع سطح اول نامیده می‌شود.[۱]

تعریف نهان‌سازی در خط و پیاده‌سازی اولیه

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

پیاده‌سازی ابتدایی[۱] با استفاده از یک ثبات و یک دستورالعمل فراخوانی است. با رسیدن به نقطه فراخوانی، مقدار ثبات با آدرس شیءای که تابع را فراخوانده است بارگذاری می‌شود (در مثال بالا آدرس obj که تابع toString را فراخوانی کرده در ثبات قرار می‌گیرد) اگر نقطه فراخوانی در وضعیت ناشناخته باشد دستورالعملی اجرا می‌شود که با استفاده از حافظه نهان جستجوی تابع سطح اول که در بالا اشاره شد، تابع مقصد (پذیرنده) را پیدا می‌کند، سپس وضعیت نقطه فراخوانی به "تک‌ریخت" تغییر پیدا می‌کند.

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

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

انواع نهان‌سازی در خط

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

نهان‌سازی در خط تک‌ریخت

اگر انواع مختلفی از اشیاء از یک نقطه فراخوانی مشاهده شود، عملکرد نهان‌سازی در خط به دلیل تغییرات مکرر وضعیت نقطه فراخوانی تضعیف می‌شود، چرا که با دیدن اشیا از نوع مختلف هر بار باید عملیات تغییر وضعیت و جستجوی پویای تابع را انجام بدهد. مثال زیر یک سناریوی بدترین حالت برای نهان‌سازی در خط تک‌ریخت را نشان می‌دهد: (فرض کنید یافتن تابع toString برای متغیرهای int و string هزینه‌ای فراتر از فراخوانی مستقیم یک تابع دارد)

var values = [1, "a", 2, "b", 3, "c", 4, "d"];
for (var i in values) {
    document.write(values[i].toString());
}

مکرراً تابع toString بر روی یک شیء که نوع آن از قبل مشخص نیست فراخوانی می‌شود، زیرا نوع شیء با هر تکرار حلقه تغییر می‌کند. بنابراین وضعیت نقطه فراخوانی در هر تکرار از وضعیت "ناشناخته" به "تک‌ریخت" و برعکس تغییر می‌کند. به منظور جلوگیری از وقوع این امر ، اکثر پیاده سازی‌های نهان‌سازی در خط تک‌ریخت یک وضعیت سوم نیز در نظر می‌گیرند که اغلب به آن "بس‌ریخت (megamorphic)" گفته می‌شود. این حالت زمانی رخ می‌دهد که تعویض وضعیت یک نقطه فراخوانی از تعداد تعیین‌شده‌ای بیشتر شود. هنگامی که یک نقطه فراخوانی وارد وضعیت "بس‌ریخت" شود، مانند حالت "ناشناخته" عمل می‌کند با این تفاوت که دیگر وارد حالت "تک‌ریخت" نخواهد شد. (برخی از پیاده‌سازی‌ها وضعیت را دوباره به حالت "ناشناخته" برمی‌گردانند. این عمل پس از گذشت مدت زمان مشخص یا یک بار چرخه کامل بازیافت حافظه رخ می‌دهد)

نهان‌سازی در خط چندریخت

برای تعامل بهتر با نقاط فراخوانی که تعداد محدودی از انواع مختلف اشیاء را مشاهده می‌کنند، برخی از زبان‌ها از تکنیکی به نام نهان‌سازی در خط چندریخت استفاده می‌کنند.[۲] با نهان‌سازی در خط چندریخت، وضعیت سومی به نام "چندریخت" برای نقطه فراخوانی به وجود می‌آید. هنگامی که نقطه فراخوانی نوع جدیدی از شیء را مشاهده می‌کند به جای تغییر وضعیت از "تک‌ریخت" به "ناشناخته"، به حالت جدیدی به نام "چندریخت" تعویض می‌شود. یک نقطه فراخوانی "چندریخت" مجموعه محدودی از توابع شناخته شده را ذخیره می‌کند، و با توجه به نوع شیء تصمیم می‌گیرد که کدام‌یک را به عنوان تابع هدف معرفی کند. به عبارت دیگر، با نهان‌سازی در خط چندریخت، نتایج جستجوی چند تابع را می‌توان در همان نقطه فراخوانی ذخیره کرد. از آنجا که هر نقطه فراخوانی در یک برنامه می‌تواند انواع مختلفی از اشیاء را ببیند، معمولاً یک حد بالا برای تعداد انواع ذخیره شده وجود دارد که پس از رسیدن به این حد بالا، وضعیت نقطه فراخوانی به یک حالت جدید به نام "بس‌ریخت" تغییر پیدا می‌کند و نهان‌سازی بیشتری انجام نمی‌شود.

اجرای ابتدایی[۲] به صورت یک جدول پرش متشکل از یک مقدمه است که نوع شیء مورد نظر را دریافت کرده و پس از انجام چندین مقایسه تعیین می‌کند کدام پرش باید انجام شود. جدول پرش به طور معمول به یک نقطه فراخوانی اختصاص می‌یابد که با انواع مختلفی از اشیاء روبرو می‌شود. اندازه جدول پرش ثابت است و با افزودن مقادیر جدید قادر به رشد می‌باشد، حداکثر اندازه این جدول عدد کوچکی مانند ۴ یا ۶ یا ۸ می‌باشد. با دریافت یک نوع شیء جدید در حالتی که جدول به حداکثر اندازه خود رسیده است، برنامه به صورت عادی اجرا می‌شود و "حافظه‌نهان جستجوی تابع سطح اول" مجدداً فراخوانی می‌شود.

نهان‌سازی در خط بس‌ریخت

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

پراکندگی وضعیت‌های نهان‌سازی

بررسی‌ها و اندازه‌گیری‌های تجربی[۳] نشان می‌دهد پس از اعمال نهان‌سازی در خط در برنامه‌های بزرگ اسمال‌تاک حدود یک سوم از نقاط فراخوانی در حالت ناشناخته باقی می‌مانند و از دو سوم باقی مانده، ۹۰٪ در وضعیت تک‌ریخت، ۹٪ در وضعیت چندریخت و ۱٪ در وضعیت بس‌ریخت هستند.

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

منابع

  1. ۱٫۰ ۱٫۱ ۱٫۲ L. Peter Deutsch, Allan M. Schiffman, "Efficient implementation of the smalltalk-80 system", POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, January 1984
  2. ۲٫۰ ۲٫۱ Hölzle, U., Chambers, C., AND Ungar, D. 1991. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the ECOOP ’91 Conference. Lecture Notes in Computer Science, vol. 512. Springer-Verlag, Berlin.
  3. PICs [was v8 first impressions] on the Strongtalk mailing list

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