یک هک بزرگ برنامه نویسی بازی قدیمی (2013)

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

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

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

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

به روز رسانی 2013-12-16: نظرات بسیار خوبی درباره این داستان در Hacker News و Proggit و همچنین در اینجا در وبلاگ وجود دارد. با تشکر از اشتراک گذاری، همه!

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

تنها مشکل این بود که نسخه او از بازی غیر قابل بازی بود. خیلی آهسته بود و حرکت متلاطم غوطه ور شدن بازیکن را شکست. به هر حال این یک اسکرولر جانبی بود.

دوست من که روی بازی کار می کرد و در عین حال بار کاملی از دوره های کالج را گذرانده بود، کم کم به نظر می رسید. از ترس اینکه برخی بهینه سازی آسان را از دست داده باشد، از من خواست که نگاهی به کد بیندازم.

من انجام دادم. اما هیچ بهینه سازی آسانی وجود نداشت.

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

با این حال، قبل از اینکه به چیزهای احمقانه بپردازم، باید یک نسخه پشتیبان تهیه کنم و توضیح بدهم که سخت افزار گرافیکی در آن زمان چگونه کار می کرد.

این نسخه سریع است: سخت افزار گرافیکی جک اسکوات را انجام نداد.

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

بازی دوست من بیشتر وقت خود را صرف ترسیم مجدد پس‌زمینه می‌کرد. (دوباره: پیمایش جانبی.) برای هر فریم، باید کاشی‌های پس‌زمینه تقریبا به اندازه یک صفحه را ترسیم می‌کرد که برای موقعیت بازیکن جابجا می‌شد.

اگر حافظه ام در کار باشد، هر کاشی 28 در 28 پیکسل بود. هر پیکسل یکی از 16 رنگ بود که برای نمایش نیم بایت طول می کشید. بنابراین، کاشی‌ها در حافظه به‌عنوان 28 ردیف به‌هم پیوسته 14 بایتی نمایش داده می‌شوند. 14 بایت اول نشان دهنده ردیف اول، 14 بایت دوم ردیف دوم و غیره بود.

با این حال، صفحه نمایش 320 پیکسل عرض و 240 پیکسل ارتفاع داشت. پس در حافظه، یک بافر صفحه نمایش به صورت 240 ردیف به هم پیوسته از هر کدام 160 بایت گذاشته شد.

بنابراین هنگام کپی کردن یک کاشی در آدرس X در یک مکان بافر صفحه که از آدرس Y شروع می شود، باید 28 ردیف را کپی می کردید. برای کپی هر ردیف باید 14 بایت کپی می کردید. خوشبختانه، پردازنده این بازی یک 6809 بود که دارای چند رجیستر شاخص 16 بیتی و حالت های آدرس دهی لذت بخش «افزایش خودکار» بود (مثلا استفاده از عملگر postfix ++ برای اشاره گرها در C). این بدان معنی است که شما می توانید همزمان 4 پیکسل را کپی کنید و در عین حال هر دو رجیستر X و Y را به صورت گذرا پیش ببرید:

برای کپی کردن یک ردیف کامل، باید این کار را هفت بار انجام دهید، بنابراین ممکن است آن خطوط را در یک حلقه 7 شماری ساندویچ کنید:

وقتی کپی کردن سطر تمام شد، باید نشانگر مقصد Y را به سمتی پیش ببرید که به آدرس شروع ردیف بعدی که در بافر صفحه می کشید اشاره کند. از آنجایی که بافر صفحه نمایش 160 بایت و عرض یک کاشی فقط 14 بایت بود، به این معنی بود که باید تفاوت آنها را به Y اضافه کنید:

و دقیقا مانند آن، یک ردیف را روی صفحه کپی کرده اید.

اون یکی برای کپی کردن یک کاشی کامل، باید همان کار را 28 بار انجام دهید. بنابراین، به نوبه خود، آن کد را در یک حلقه 28 تعداد ساندویچ می کنید.

با کنار هم قرار دادن همه آن ها و نام بردن اعداد مهم، ممکن است به زیربرنامه ای مانند این دست پیدا کنید:

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

با نگاهی به این تعداد در حلقه، احتمالا از این که 21 چرخه را برای کپی کردن فقط 4 پیکسل می سوزانید، غافل نشوید. بنابراین، برای کپی کردن یک ردیف کامل، 2 چرخه + (7 تکرار) * (21 چرخه/تکرار) + 8 چرخه = 157 چرخه انجام می شود. اوه

اما این اولین باری نیست که روی صفحه کلید می روید. شما می دانید چه کاری انجام دهید. باز کردن آن حلقه!

اکنون، با کاهش سربار حلقه به صفر - حتی تنظیم را حذف کرده اید - هر ردیف فقط 7 * (8 + 8) + 8 = 120 چرخه طول می کشد. این یک افزایش 30 درصدی است. خیلی خوبه

و این جایی است که اکثر برنامه نویسان احتمالا آن را ترک می کردند.

او می دانست که آن عملیات ++ پرهزینه است، هر بار 3 چرخه. و با باز شدن حلقه، او همچنین می‌دانست که هر کلمه‌ای که باید خوانده یا نوشته شود با توجه به X یا Y در کجا قرار دارد. بنابراین او هوشمندانه آن 3 چرخه پس از افزایش را با افست های دقیق جایگزین کرد. آنها فقط 1 چرخه قیمت دارند و افست 0 در واقع رایگان است:

با بهینه سازی های او، تعداد چرخه در هر ردیف به (5 + 5) + 6 * (6 + 6) + (8 + 8) = 98 چرخه کاهش یافت. در مقایسه با کد اصلی، 60 درصد سریعتر است:

همه را کنار هم بگذارم - و دوباره، من از حافظه استفاده می کنم، بنابراین ممکن است کد کمی متفاوت باشد - زیرروال کپی-کاشی چیزی شبیه به این بود، و یک کاشی کامل، همه 28 ردیف، را در 2893 چرخه ناب کپی کرد:

این کد در مجموع 60 درصد سریعتر از کد COPYTILE ساده لوحانه ای بود که ما با آن شروع کردیم.

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

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

بعدا نتوانستم مشکل را از سرم بیرون کنم. شاید چیزی را از دست داده بودم. من با رایانه های Apple II و پردازنده های 6502 آنها بزرگ شده بودم. کد دوست من، با این حال، برای 6809 بود. شاید بهینه‌سازی‌هایی را ارائه می‌کرد که من نمی‌دانستم.

با خوش بینی مجدد، برای دسترسی به فهرست کارت به کتابخانه دانشگاه مراجعه کردم. (این روزها قبل از شبکه جهانی وب بود.) از طریق شبیه ساز ترمینال VT220، کتاب هایی را در مورد 6809 جستجو کردم.

یکی بود. کتابچه راهنمای ریزپردازنده 6809. در کتابخانه مهندسی بود. خوشبختانه من دانشجوی مهندسی بودم و امتیازات ورود به سیستم را داشتم.

وقتی به کتابخانه مهندسی رسیدم، کتاب را دقیقا همان جایی که قرار بود باشد، پیدا کردم، به نظر کمی کتک خورده:

راهنمای برنامه نویسی ریزپردازنده MC6809-MC6809E.

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

سپس به PSHS رسیدم. «ثبت‌کننده‌ها را روی پشته سخت‌افزار فشار دهید».

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

اما در 6809 می توانید همه رجیسترها - یا هر زیر مجموعه ای از آنها را - با یک دستورالعمل ذخیره کنید. و به طرز شگفت انگیزی، فقط 5 سیکل هزینه داشت، به اضافه 1 چرخه بیشتر در هر بایت فشار داده شده.

از آنجایی که پردازنده سه رجیستر 16 بیتی همه منظوره داشت - D، X و Y - می‌توانستم آنها را بارگیری کنم و سپس از یک دستورالعمل PSHS برای نوشتن 6 بایت فقط در 11 چرخه استفاده کنم. دستورالعمل کشش مربوطه، PULS، همان هزینه کم را داشت.

علاوه بر این، 6809 دارای دو رجیستر پشته، S و U بود. می توانم از یکی به عنوان اشاره گر مبدا و دیگری به عنوان اشاره گر مقصد استفاده کنم. در تئوری، با یک جفت PULS / PSHU، می‌توانم 6 بایت را در 22 چرخه کپی کنم.

با هیجان سوار شدم، به سمت میز جلو رفتم و به شناسه دانشجویی ام رسیدم. من قصد داشتم آن کتاب کوچک فوق العاده را برای مطالعه بیشتر امضا کنم.

من رجیسترهای S و U را در جایی ذخیره می‌کردم و سپس S را روی کاشی پس‌زمینه و U را در بافر صفحه نمایش قرار می‌دادم. سپس از S می کشیدم و به U فشار می دادم، هر بار 6 بایت را کپی می کردم و از D، X و Y به عنوان واسطه استفاده می کردم. برای کپی کردن 14 بایت که یک ردیف را تشکیل می‌دهند، به سه تکرار نیاز است که باز کردن آن حدود 60 چرخه خواهد بود.

وقتی به اتاقم رسیدم، یک تکه کاغذ پیدا کردم و آن را ترسیم کردم:

فقط 66 چرخه، از جمله تنظیم بعد از ردیف به U که آن را برای ردیف بعدی آماده می کند. (توجه داشته باشید که تنظیم اکنون منفی است.) برای مقایسه، حلقه کپی ردیف ساده که قبلا به آن نگاه کردیم 157 چرخه طول کشید تا همین کار را انجام دهد. و کد بهینه شده دوست من 98 را گرفت. از قبل، این ایده دیوانه کننده مانند یک برد بزرگ به نظر می رسید.

با این حال، آخرین جفت PULS / PSHU! چه هولناکی برای رسیدگی به دو بایت نهایی در هر ردیف لازم بود، زیرا سطرها 28 پیکسل = 14 بایت عرض داشتند و 6 14 را به طور مساوی تقسیم نمی کند.

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

و بعد با تعجب طلا زدم! این یکی دیگر از موارد عجیب و غریب 6809 بود، ثبت DP.

در 6502 و اکثر پردازنده های 8 بیتی آن دوره، کمترین 256 بایت حافظه صفحه صفر نامیده می شد. صفحه صفر خاص بود زیرا مکان های حافظه آن آدرس های تک بایتی داشتند و با دستورالعمل های کوتاه تر و معمولا سریع تر قابل دسترسی بودند.

طراحان 6809 این ایده را یک قدم جلوتر بردند. آنها به شما اجازه می دهند از رجیستر DP برای تعیین هر صفحه به عنوان صفحه صفر استفاده کنید که آن را "صفحه مستقیم" نامیدند.

اما هیچ یک از دستورالعمل های بایت اسلینگ من برای استفاده از صفحه مستقیم نیازی نداشت. این بدان معناست که می‌توانم از رجیستر DP به‌عنوان یک میان‌بر یک بایت اضافی استفاده کنم. حالا می توانستم 7 بایت را در هر جفت کشش فشاری کپی کنم!

با این تغییر، می‌توانم یک ردیف کامل 28 پیکسلی را کپی کنم و فقط در 5 دستورالعمل به ردیف بعدی بروم:

آن بیت کد به من احساس فوق العاده ای داد. من موفق شده بودم از تک تک رجیسترهای موجود در دستگاه برای بایت اسلینگ استفاده کنم! D، X، Y، U، S، و حتی DP عجیب و غریب - همه آنها کاملا درگیر بودند.

اگر با پشته ها آشنا هستید، ممکن است متوجه یک نقص ظریف در طرح درخشان من شده باشید:

فشارها و کشش ها در جهت مخالف کار می کنند.

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

به یاد بیاورید که ردیف های کاشی به طور معقول در حافظه به صورت 14 بایت به هم پیوسته قرار گرفتند، مانند این:

بنابراین وقتی یک ردیف را در 7 بایت روی صفحه می کشید و فشار می دادید، به صورت افقی به این صورت تقسیم می شود:

سپت اول اکنون دوم بود و سپت دوم اکنون اول بود. با این حال، توجه داشته باشید که بایت های درون هر سپتت بدون تغییر بودند. آنها نظم اولیه خود را حفظ کردند.

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

برای تجسم خرابی‌هایی که این تغییر ردیف و تعویض سپت‌ت به بار می‌آورد، بیایید بگوییم که شما کاشی 28 در 28 زیر را داشتید که نشان‌دهنده یک کلید است:

اگر از 28 برنامه از کد row-copy من برای کشیدن آن روی صفحه استفاده کرده بودید، به این کلید نمی رسید:

اما این مشکل هم راه حل شیکی داشت!

پیشرفت این بود که «وارونه» و «مبادله» را به عنوان دو نمونه از یک چیز ببینیم. معکوس.

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

با کار کردن بر روی کاغذ، همچنین متوجه شدم که مرحله پیش پردازش می‌تواند ردیف‌ها را نادیده بگیرد و کاشی‌ها را به‌عنوان یک دنباله خطی و طولانی از سپتیت‌ها در نظر بگیرد. 1 برای اینکه بفهمیم چرا اینطور است، بیایید یک کاشی کوچک از 2 ردیف از هر کدام 2 سپتیت در نظر بگیریم:

در حافظه، به ترتیب ردیف اصلی، یعنی به صورت 4 سپتیت متوالی تنظیم می شود:

بنابراین، معکوس کردن ردیف‌ها و سپس تعویض سپت‌ت‌ها در هر ردیف مانند معکوس کردن ترتیب سپت‌ت‌ها در حافظه است:

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

با دانستن این که مشکل انحراف را می توان حل کرد، نسبت به ایده کلی خود احساس خوبی داشتم. من نتوانستم هیچ مشکل دیگری ببینم، بنابراین یک زیربرنامه جدید کپی کاشی طراحی کردم تا به دوستم ارائه کنم. از آنجایی که منطق row-copy اکنون فقط 5 دستورالعمل بود، من 4 بار از آن استفاده کردم و حلقه باقی مانده را کمی باز کردم. الان به جای کپی 28 ردیف تکی، 7 چهار ردیف کپی کردم.

با جمع کردن چرخه ها، کل فقط 1689 بود. من تقریبا 1200 چرخه از کد دوستم پاک کرده بودم. این یک افزایش 70 درصدی است!

وقتی با دوستم تماس گرفتم و گفتم که می‌دانم چگونه روال کپی کردن را ۷۰ درصد سریع‌تر کنم، چهره او روشن شد. با این حال، وقتی در مورد کل سپت‌ت‌ها و قلاب‌زنی توضیح دادم، چهره‌اش روشن نشده بود، شک و تردید بالا می‌رفت. اما وقتی کد را به او نشان دادم، آن را دریافت کرد. کلیک کرد.

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

بازی فوق العاده سریع به نظر می رسید. در حقیقت، احتمالا فقط یک سوم تا نیم سریعتر بود، اما همین کافی بود. برخی از آستانه ادراکی مهم عبور کرده بود. بازی اکنون نرم و طبیعی بود. شما می توانید تفاوت را احساس کنید.

ما فقط همانجا نشستیم، بازی کردیم و پوزخند زدیم. روز خوبی بود.

چند روز پس از پشت سر گذاشتن مشکل سرعت - یا ما فکر می کردیم - آخرین کارهای بازی اعمال شد. یکی از آن کارهای پایانی، نمونه جلوه های صوتی بود. این امر مستلزم تغذیه لقمه هایی به اندازه بایت به DAC خروجی صوتی چند هزار بار در هر ثانیه بود. برای برنامه ریزی تغذیه، دوست من یک وقفه با ساعت سخت افزاری را روشن کرده بود.

مثل یک طلسم کار کرد. صداها عالی بود و همه چیز عالی بود.

بعد از اینکه یک شب وارد بازی شدیم، متوجه شدیم که برخی از کاشی ها خراب شده اند. هر چه بیشتر بازی می کردیم، فساد بیشتر می دیدیم.

اگر یک وقفه در طول روال کپی کاشی خاموش شود، چه اتفاقی می‌افتد؟

پردازنده، برای آماده شدن برای فراخوانی کنترل کننده وقفه، وضعیت فعلی خود را به پشته سیستم فشار می دهد. اما، در طول روال کپی کاشی، هیچ پشته سیستم وجود نداشت. ثبت سیستم پشته S فرمان داده شده بود. و به کجا اشاره می کرد؟ درست در بافر حافظه که کاشی های مرجع را نگه می داشت!

ما سقوط کردیم. بعد از آن همه تلاش، فکر کنیم که سرعت بسیار مهم ما باعث تخریب حافظه شده است…

که نیاز به استراحت داشتیم، به سمت یک غذاخوری شبانه در نزدیکی دانشگاه رفتیم تا غذا بخوریم و فکر کنیم. در مورد پنکیک و بیکن، ضایعات و چسب های کبابی، ما در مورد مشکل صحبت کردیم.

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

پس از آن، به هر طریقی، وقفه ها ایجاد می شد. و وقتی آنها بودند، اگر copy-tile اجرا می شد، هر چیزی که S به آن اشاره می کرد، چکش می شد.

چگونه می توانیم از فساد جلوگیری کنیم؟ من پرسیدم.

ما آنجا نشستیم، بی توجه به غذایمان، سوال در هوا معلق بود.

ناگهان دوستم سیلی روی میز زد. او آن را داشت.

او توضیح داد: «از فساد جلوگیری نکنید. "اجازه دهید این اتفاق بیفتد. نه به کاشی های مرجع."

"فقط S و U را در روال کپی کاشی عوض کنید. U به کاشی های مرجع و S به بافر صفحه نمایش اشاره می کند. اگر یک وقفه خاموش شود، خرابی در جایی اتفاق می افتد که S نشان می دهد - روی صفحه. خرابی فقط تا زمانی که فریم بعدی را دوباره ترسیم کنیم ادامه خواهد داشت."

مشتاق امتحان کردن راه حل او، سریع غذایمان را تمام کردیم.

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

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

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

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

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

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

ما با یک زیرروال کپی کاشی شروع کردیم که هسته آن حلقه ای از دستورالعمل های ماشین بود که به صورت دستی تنظیم شده بود. سپس، برای خرید یک سرعت 70 درصدی:

به هر حال به دو دلیل می خواستم آن داستان را با شما در میان بگذارم.

اولین مورد این است که یک داستان سرگرم کننده است. این یکی از اولین خاطرات من از مبارزه با یک مشکل محاسباتی درهم و برهم است و با پشتکار زیاد، به راه حلی دست یافتم که هم مؤثر و هم ظریف بود. نتیجه به شدت رضایت بخش بود.

دلیل دوم تشویق شما به گفتن داستان هایتان است. می‌دانم که «در آن روزگار»، بیشتر بازی‌های ویدیویی احتمالا داستان‌های زیادی مانند این را به وجود آورده‌اند. من دوست دارم آنها را بشنوم. اما تعداد زیادی از آنها گم شده اند، و قبل از اینکه کسی فکر کند آنها را حفظ کند، حافظه آنها محو شده است.

اگر داستانی دارید، لطفا منتظر نمانید. بگو هر روز که صبر کنی، سخت تر می شود.

تمرین: ثابت کنید که برای تمام دنباله های متناهی دنباله های متناهی، اعمال ( معکوس ⋅ concat ) با اعمال (concat ⋅ معکوس ⋅ معکوس نقشه) یکسان است. ↩︎

همچنین باید مطمئن می‌شدیم که هیچ چیز ارزشمندی در مکان‌های حافظه درست قبل از بافر صفحه ذخیره نمی‌شود. در تئوری، اگر وقفه ای در حین قرار دادن سپت بالا سمت چپ کاشی گوشه بالا سمت چپ رخ دهد، ممکن است خراب شوند. آدرس این Septet با شروع بافر مطابقت دارد. ↩︎