معمولا دیتاتایپ لیست از اولین دیتاتایپ‌هایی‌ست در آموزش‌های پایتون تدریس می‌شود و باتبع متد append جزو اولین متد‌کال‌هایی‌ست که توسط ما انجام می‌شود. اما اینجا لیست CPython هست و می‌خواهیم بررسی کنیم under the hood واقعا چه چیز‌هایی آبجکتی رو به یک لیست در پایتون اپند می‌کنند.
در این قسمت از مقاله به بررسی یک کانسپت به نام dynamic arrays و چگونگی پیاده‌سازی آنها می‌پردازیم!
Wikipedia:
In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages. Dynamic arrays overcome a limit of static arrays, which have a fixed capacity that needs to be specified at allocation.
A dynamic array is not the same thing as a dynamically allocated array or variable-length array, either of which is an array whose size is fixed when the array is allocated, although a dynamic array may use such a fixed-size array as a back end.[1]
خیلی ساده اگر بخواهیم به موضوع نگاه کنیم اینجوریه که ما یه مقدار حافظه رو اشغال می‌کنیم، فرضا داخل یه C Array و فرضا اندازه ۴ تا خونه، بعدش آبجکت‌هامون رو توش ذخیره می‌کنیم، و وقتی که ۴ تا خونه‌ش پر شد، میایم یه C Array دیگه می‌سازیم اما مثلا به اندازه‌ی ۸ تا خونه و سپس تمامی مقادیر رو میریزیم توش، و همین‌طور تا آخر.
و چیزی که ویکی‌پدیا میگه:
A simple dynamic array can be constructed by allocating an array of fixed-size, typically larger than the number of elements immediately required. The elements of the dynamic array are stored contiguously at the start of the underlying array, and the remaining positions towards the end of the underlying array are reserved, or unused. Elements can be added at the end of a dynamic array in constant time by using the reserved space, until this space is completely consumed. When all space is consumed, and an additional element is to be added, then the underlying fixed-size array needs to be increased in size. Typically resizing is expensive because it involves allocating a new underlying array and copying each element from the original array. Elements can be removed from the end of a dynamic array in constant time, as no resizing is required. The number of elements used by the dynamic array contents is its logical size or size, while the size of the underlying array is called the dynamic array's capacity or physical size, which is the maximum possible size without relocating data.[2]
A fixed-size array will suffice in applications where the maximum logical size is fixed (e.g. by specification), or can be calculated before the array is allocated. A dynamic array might be preferred if:
- the maximum logical size is unknown, or difficult to calculate, before the array is allocated
- it is considered that a maximum logical size given by a specification is likely to change
- the amortized cost of resizing a dynamic array does not significantly affect performance or responsiveness
مثل این تصویر
پس چنین چیزی هم باید یک‌جایی از آبجکت لیست پایتون پیاده‌سازی شده باشه که در این مقاله در دو ورژن از پایتون (۳.۸ و ۳.۱۱) کاملا با نگاه به کدهای مفسر بررسیش می‌کنیم.
اما یک موضوع دیگه که هست مسئله‌ی اینه که این زیاد شدن با چه نرخی انجام میشه؟! طبق جدولی که در ویکی‌پدیا هست در زبان‌‌های مختلف نرخ رشد این نوع از آرایه‌ها چنینه:
اول از همه بیاید یه نگاهی به خود آبجکت لیست بندازیم؛ با توجه به داکیومنتیشن پایتون:
و خب کد این تایپ در مفسر پایتون:
که البته این ماکرویی که در ابتدای این تایپ هست، اینه:
که اگه بخوایم کل آبجکت لیست رو یکجا ببینیم (این کد وجود نداره و صرفا برای ساده‌سازی و کنار هم آوردن همه فیلد‌ها نوشته شده):
در مطالعه کدهای فایل listobject.c اولین نشانه و تابعی که برای انجام عملیات append این پیدا میشه، اینه:
بسیار ساده، ابتدا آبجکت لیست و آبجکتی که باید بهش اضافه بشه رو میگیره و تابع app1 رو صدا میزنه، اگه خروجی app1 صفر باشه یعنی اپند انجام شده و مقدار None ریترن میشه، اگر نه، مقدار NULL به نشانه‌ی ارور و عدم انجام اپند (به هر دلیلی) ریترن میشه.
بریم تابع app1 رو نگاه کنیم:
کد بسیار ساده‌ی تابع app1 که مهم‌ترین قسمتش خط ۳۴۶ هست! که خب می‌دونیم باید برای اپند کردن یک resize انجام بدیم.
این هم کل تابع list_resize:
آقای ریموند هتینگر حدود ۲۰ سال پیش این تابع رو optimize کردن و روش ایشون تا پایتون ۳.۸ استفاده می‌شد:
حالا که تمامی توابع برای اپند کردن به یک لیست رو داریم بیاید تا این کد رو اجرا کنیم:
برای اینکه کامل و با شکل متوجه بشیم چه اتفاقی میوفته من از روی کدهای C بالا یه نسخه‌ی مینیمال پایتونی نوشتم که از یه Debugger خوب هم بتونیم استفاده کنیم.
کدهایی که قراره استفاده کنیم اینجان:
از تریک‌ها و روش‌های پایتونی استفاده نکردم تا دقیقا همون کدهای سی رو بنویسم، پس بریم که این اپند کردن رو یبار trace کنیم:
در ابتدا همه‌چیز طبق چیز‌هایی پیشفرضی هست که توی کلاس PyListObject نوشته شدن:
سپس متد append صدا زده میشه و این متد تابع list_append رو صدا میزنه:
تابع list_append:
و خب طبق کد این تابع، تابع app1 رو صدا میزنه:
اتفاقاتی که میوفته:
خط اول تابع مقدار len تابع رو با اون تابع بدست میاره! سپس چک میکنه که آیا به سر حد نهایت اندازه یه لیست که اون عدده (که فکر کنم بزرگ‌ترین عدد ۳۲ بیتی هست، ولی مطمئن نیستم) رسیده یا نه! که اگه رسیده یک اکسپشن raise کنه!
سپس روند execution ما میرسه به تابع list_resize:
اتفاقاتی که میوفته:
ابتدا مقدار allocated رو میگیره، سپس چک میکنه ببینه میتونه بدون resize کردن اون لیست میتونه ادامه بده یا نه، یعنی لیست هنوز جای خالی توش مونده یا خیر!
این هم به این شرط وابسته‌ست که allocated ما بیشتر از newsize که سایز جدید لیست ماست باشه (که اینجا len + 1 هست) و اینکه اون newsize بیشتر یا مساوی نصف مقدار خالی باشه! که البته اینجا توی کد ما رد میشه!
سپس مقدار new_allocated محاسبه میشه:
که طبق پنجره‌ی دیباگر مقدار ۴ هست. محاسبه‌ی این مقدار فرمول ساده‌ای داره که میگه:
اندازه جدید لیست (len اش) + جز صحیح یک هشتم مقدار جدید + (۳ اگر مقدار جدید کمتر از ۹ باشه و در غیر این صورت + ۶) (فرمولی که Raymond Hettinger داده دیگه چه کنیم D:)
می‌رسیم به شرط بعدی که چک میکنه آیا این مقدار new_allocated خییییلی بزرگ شده یا نه که اگه شده اکسپشن بده که در کد ما اینطور نیست! (البته اشاره کنم اون ۱ در کد سی این بود sizeof(PyObject *) که خب نمیدونستم چقدره و بجاش عدد یک رو گذاشتم)
سپس:
میاد باز چک میکنه که آیا اندازه جدید به اندازه کافی کوچک هست یا خیر و اگه بود کار مهمی رو انجام بده: کپی کردن مقادیر به مکانی با اندازه‌ی جدید. این کار توسط تابع PyMem_Realloc انجام میشه.
حالا مقداری جدید باید محاسبه بشه که مقدار بایت‌هایی هست که تابع بعدی باید از مموری بگیره، مقدار واقعی این در کد CPython همون new_allocated * sizeof(PyObject *) هست که ما اون رو برابر با یک گرفتیم:
درون تابع PyMem_Realloc:
که خب کاری که من کردم این بود که به تعداد مورد نیاز (new_allocted_byted - len(self)، که یعنی مثلا الان لیست من ۴ تا عضو داره و new_allocated میگه باید ۸ تا بشی، که خب ۴ تا خونه‌ی خالی باید بهش اضافه بشه) و برای نشون دادن خونه‌ی خالی از '*' استفاده کردم که:
یک سری چک‌های ساده دیگه انجام میشه و می‌رسیم به:
مشاهده می‌کنید که مقدار ob_item این لیست ما بروز شده و سپس:
حالا مقدار len که فیلد ob_size نشونش میده بروز شده و:
مقدار allocated هم بروز میشه و صفر به معنای انجام موفق عملیات ریترن میشه!
اما خب کی قراره آبجکت داخل لیست ریخته بشه؟ دقیقا اینجا:
این تابع میاد و:
مقدار "Py 3.8" رو داخل اولین ایندکس لیست میگذاره و در نهایت None ریترن میشه!
به همین سادگی و زیبایی عمل اپند کردن به یک لیست انجام شد :دی اما خب این به یک لیست خالی بود، معلومه که باید یه resize انجام بشه، لیست‌های پر‌تر چطور؟
این اتفاقیه که میوفته و اگه در تعداد خیلی بالاتر بخوایم بهش نگاه کنیم میزان رشد و نحوه‌ی رشدش به صورت خواهد بود:
این اعداد نشون میدن که وقتی سایز لیست ما، ۱۸۴ بایت هست، وقتی که یک resize می‌خواد صورت بگیره، اندازه‌ی ۸ خانه خالی resize انجام میشه، یا مثلا وقتی سایز لیست میرسه به ۵۲۰ بایت، list_resize اندازه‌ی ۱۲ خونه‌ی خالی میذاره روی ob_item یا توی ۷۶۰ بایت، ۱۴ خونه‌ی خالی به ob_item اضافه میشه و الی آخر...
این نمودار از روی داده‌های تولید شده توسط implementation پایتونی من از append و با این استفاده از این تابع کشیده شده:
حالا بیاید نتایج پیاده‌سازی خودمون رو با نتایج بدست اومده اجرا کردن این کد:
که با پایتون ۳.۸ ران شده ببینیم:
انگار واقعا شبیه به هم هستن، پس بیاید بندازیم‌شون روی هم:
بلی دقیقا روی هم افتادن :)) خودم هم باورم نمیشد دقیقا همین نتایج رو بگیریم D:
این از ورژن پایتون ۳.۸مون بریم ببینیم بعد از این نسخه، چه اتفاقاتی افتاده و این الگوریتم چقدر بهتر شده؟
در git blame فایل listobject.c برنچ main پایتون چنین چیزی مشاهده میشه:
یه کسی ۳ سال پیش، برای پایتون ورژن:
یه بحثی رو اینجا:
با کور دولوپرا داشته که نتیجه‌ی کلیش این شده که، استراتژی list_resize رو تغییر بدن به:
می‌بینید که هم pattern رشد و هم فرمول محاسبه‌ی new_allocated تغییر کرده، دلایلش در همون باگ‌ترکر بالا ذکر شده اما نتایجش قابل توجه هستن.
اول بیاید ببینیم رفتن اپند کردن به یک لیست در پایتون در ورژن ۳.۱۱ چه تغییراتی داشته:
چندین تابع جدید برای هندل کردن اپند کردن به پایتون اضافه شدن که ترتیب صدا زدن‌شون و خودشون (کدشون) به این صورته:
تابع list_append الان تابع
_PyList_AppendTakeRef
رو صدا میزنه. این تابع چنینه:
همین‌طور که مشخصه این تابع بعد از چک کردن چند تا چیز و گرفتن مقادیر len و allocated یه شرط داره! اونم اینه که اگه allocated بیشتر بود، len رو یکی بیشتر کن و مقدار رو بذار توی لیست و خلاص! اما اگر مقدار allocated بیشتر از len نبود، میریم سراغ صدا زدن تابع بعدی:
اول که مقدار len رو دریافت میکنه، سپس چک میکنه که یا allocated عدد ۱- باشه (که توی PyListObject نوشته بود وقتی مثلا list.sort رو صدا میزنیم این چنین میشه) یا اینکه allocated با len برابره؛ حالا میاد و list_resize رو صدا میزنه!
تا اینجا تغییری نداشتیم ولی طبق همون pr عی که اون فرد داده بود و فرمول رو عوض کرده بود:
باز هم مثل قبل بیاید یه مثال بزنیم و کدی رو ران کنیم تا بفهمیم این فرمول جدید چجوری کار میکنه.
من باز هم کد پایتون این لاجیک جدید رو نوشتم که توی همون ریپازیتوری هست.
دیگه بدون توضیح اضافه دیباگ کردنش رو ببینیم:
حالا بیاید ببینیم اگه allocation به اندازه کافی بزرگ باشه چه اتفاقی میوفته:
این هم از بررسی کدهایی که در ورژن ۳.۱۱ یک آبجکت رو به لیست اپند می‌کنند. اما خب سوالی که پیش میاد، این تغییر محاسبه‌ی new_allocation چه تاثیری داشته؟
بیاید تا دو نموداری که از اعداد پایتون ۳.۱۱ و ۳.۸ تولید شدن رو بندازیم روی هم دیگه و تفاوت رو واضح ببینیم:
خط نارنجی پایتون ۳.۱۱ هست :)
بازم یک توضیح کوچک: خط نارنجی رنگ میگه: وقتی که سایز لیست از ۷۶۰ بایت تا ۹۰۴ بایت تغییر میکنه، برای هر بار resize که صورت میگیره، تنها ۱۶ خونه به ob_item اضافه میشه.
اما خب این اعداد فقط برای ۱۲۸ تا عدد هست، بیاید تا مقدار تا ۴۶۰ تا آبجکت ببریم بالا
این هم مقایسه‌ای بین growth rateهای این دو الگوریتم.
توی این مقاله سعی کردم خیلی ساده و با کلی کد ساده‌تر و نتایج لحظه به لحظه بهتون نشون بدم در یک اپند واقعا چه رخ میده.
امیدوارم استفاده کرده باشید!
