cache miss و ساختار unrolled linked list

Question

بعد از جست و جو هایی که داشتم متوجه شدم که ساختار هایی مثل  unrolled linkedlist  وجود دارن که از نظر cache hit وضعیت بهتری نسبت به list معمولی  دارند .

حالا سوال من اینه که آیا کامپایلر نمی تونه بصورت خودکار لینک لیست معمولی رو با این ساختار جابه جا کنه ؟

بعد این که std::list از لینک لیست معمولی استفاده می کنه یا از unrolled linkedlist ؟!

Comments

کامپایلر چیزی از لیست-پیوندی نمیدونه . اصلا نمیدونه چی هست ! :)
برای همین شما باید چند شی رو توی یک گره ی بزارید تا این شکل از لیست-پیوندی رو بدست بیارید .
در مورد std::list مطمئن نیستم ، ولی فکر میکنم از همون لیست-پیوندی معمولی استفاده میکنه .

Answer 1

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

شاید کامپایلر های ۳۰ سال دیگه این کاری که گفتید رو هم موفق بشن انجام بدن :)

 

در مورد STL هم داخل استاندارد ++C ذکر نشده که دقیقا چطور باید list یا container های دیگه پیاده سازی بشن 

داخل استاندارد این که  هر container چه توابعی باید داشته باشه به همراه پیچیدگی زمانی بعضی از توابع و  ویژگی های کلی ذکر شده .

پس اگر بتونن unrolled list رو طوری پیاده سازی کنن که تمام مشخصاتی که استاندارد ++C تعیین کرده رو رعایت کنن میتونن برای std::list هم ازش استفاده کنن

چیزی که در مورد std::list هست اینه که هدف از پیاده سازیش بیشتر باید روی جاهایی باشه که قرار از وسط داده ها یک مقدار حذف بشه یا اضافه بشه که این مورد با گرفتن بلاک توسط unrolled list جور در نمیاد (چون حذف از وسط این بلاک ها یا اضافه کردن به وسط هم مثل وکتور باعث شیفت دادن عناصر میشه )

وهم این که شماوقتی که داخل list عنصراضافه می کنید باید تضمین بشه که iterator های دیگه نامعتبر نمیشن که با unrolled linked list این کار قابل انجام  نیست.

 

ویرایش : 

در اکثر پیاده سازی های ++C ساختار std::deque بوسیله unrolled linkedlist  پیاده سازی شده .