Mark–compact algorithm
কম্পিউটার বিজ্ঞানে, মার্ক-কমপ্যাক্ট অ্যালগরিদম হল এক ধরনের আবর্জনা সংগ্রহের অ্যালগরিদম যা অপ্রাপ্য স্মৃতি পুনরুদ্ধার করতে ব্যবহৃত হয়। মার্ক-কমপ্যাক্ট অ্যালগরিদমকে মার্ক-সুইপ অ্যালগরিদম এবং চেনির অনুলিপি অ্যালগরিদমের সংমিশ্রণ হিসাবে বিবেচনা করা যেতে পারে। প্রথমে, পৌঁছনো যায় এমন বস্তু চিহ্নিত করা হয়, তারপর একটি কম্প্যাক্টিং ধাপ পৌঁছনো যায় এমন (চিহ্নিত) বস্তুগুলিকে স্তূপ এলাকার শুরুতে স্থানান্তরিত করে। কম্প্যাক্টিং আবর্জনা সংগ্রহ আধুনিক জেভিএম, মাইক্রোসফ্টের কমন ল্যাঙ্গুয়েজ রানটাইম এবং গ্লাসগো হাস্কেল কম্পাইলার দ্বারা ব্যবহৃত হয়। অ্যালগরিদম মার্ক-সুইপ অ্যালগরিদমের মতো একই পদ্ধতিতে জীবন্ত বস্তুগুলিকে চিহ্নিত করার পরে, স্তূপটি প্রায়শই খণ্ডিত হয়ে যায়। মার্ক-কমপ্যাক্ট অ্যালগরিদমের লক্ষ্য হল জীবন্ত বস্তুগুলিকে একসঙ্গে মেমরিতে স্থানান্তরিত করা যাতে বিভাজন দূর হয়। চ্যালেঞ্জটি হল সরানো বস্তুর সমস্ত পয়েন্টার সঠিকভাবে আপডেট করা, যার বেশিরভাগের সংক্ষেপণের পরে নতুন মেমরি ঠিকানা থাকবে। পয়েন্টার আপডেটগুলি পরিচালনা করার বিষয়টি বিভিন্ন উপায়ে পরিচালিত হয়। টেবিল-ভিত্তিক সংকোচন একটি টেবিল-ভিত্তিক অ্যালগরিদম প্রথম 1967 সালে হ্যাডন এবং ওয়েইট দ্বারা বর্ণনা করা হয়েছিল। এটি স্তূপের মধ্যে জীবন্ত বস্তুর আপেক্ষিক অবস্থান সংরক্ষণ করে এবং শুধুমাত্র একটি ধ্রুবক পরিমাণ ওভারহেডের প্রয়োজন হয়। সংকোচন হিপের নীচে (নিম্ন ঠিকানা) থেকে উপরে (উচ্চ ঠিকানা) পর্যন্ত অগ্রসর হয়। লাইভ (অর্থাৎ, চিহ্নিত) বস্তুর মুখোমুখি হওয়ার সাথে সাথে সেগুলি প্রথম উপলব্ধ নিম্ন ঠিকানায় স্থানান্তরিত হয় এবং স্থানান্তর তথ্যের একটি ব্রেক টেবিলে একটি রেকর্ড সংযুক্ত করা হয়। প্রতিটি জীবন্ত বস্তুর জন্য, ব্রেক টেবিলের একটি রেকর্ডে সংকোচনের আগে বস্তুর মূল ঠিকানা এবং সংকোচনের পরে মূল ঠিকানা এবং নতুন ঠিকানার মধ্যে পার্থক্য থাকে। ব্রেক টেবিলটি সংকুচিত করা হচ্ছে এমন স্তূপের মধ্যে সংরক্ষণ করা হয়, তবে এমন একটি এলাকায় যা অব্যবহৃত হিসাবে চিহ্নিত করা হয়। সংকোচন সর্বদা সফল হবে তা নিশ্চিত করার জন্য, স্তূপের সর্বনিম্ন বস্তুর আকার অবশ্যই ব্রেক টেবিল রেকর্ডের চেয়ে বড় বা একই আকারের হতে হবে। সংকোচন বাড়ার সাথে সাথে স্থানান্তরিত বস্তুগুলি স্তূপের নীচের দিকে অনুলিপি করা হয়। অবশেষে একটি বস্তুকে ব্রেক টেবিলের দখলে থাকা জায়গায় অনুলিপি করতে হবে, যা এখন অন্য কোথাও স্থানান্তরিত করতে হবে। ব্রেক টেবিলের এই নড়াচড়া, (লেখকদের দ্বারা টেবিল রোলিং বলা হয়) স্থানান্তর রেকর্ডগুলিকে বিশৃঙ্খল করে তোলে, যার জন্য সংকোচন সম্পূর্ণ হওয়ার পরে ব্রেক টেবিলটি সাজানো প্রয়োজন। ব্রেক টেবিল বাছাই করার খরচ হল ও (এন লগ এন), যেখানে এন হল অ্যালগরিদমের চিহ্নিত পর্যায়ে পাওয়া জীবন্ত বস্তুর সংখ্যা। অবশেষে, ব্রেক টেবিল স্থানান্তর রেকর্ডগুলি স্থানান্তরিত বস্তুর ভিতরে পয়েন্টার ক্ষেত্রগুলি সামঞ্জস্য করতে ব্যবহৃত হয়। জীবন্ত বস্তুগুলি পয়েন্টারের জন্য পরীক্ষা করা হয়, যা ও (এন লগ এন) সময়ে এন আকারের বাছাই করা ব্রেক টেবিলে দেখা যেতে পারে যদি ব্রেক টেবিলটি সাজানো হয়, ও (এন লগ এন) এর মোট চলমান সময়ের জন্য। তারপরে পয়েন্টগুলি স্থানান্তর টেবিলে নির্দিষ্ট পরিমাণ দ্বারা সামঞ্জস্য করা হয়। এল. আই. এস. পি 2 অ্যালগরিদম ও (এন লগ এন) জটিলতা এড়ানোর জন্য, অ্যালগরিদমটি স্তূপের উপর তিনটি ভিন্ন পাস ব্যবহার করে। উপরন্তু, স্তূপ বস্তুর অবশ্যই একটি পৃথক ফরওয়ার্ডিং পয়েন্টার স্লট থাকতে হবে যা আবর্জনা সংগ্রহের বাইরে ব্যবহার করা হয় না। স্ট্যান্ডার্ড মার্কিংয়ের পরে, অ্যালগরিদমটি নিম্নলিখিত তিনটি পাসে এগিয়ে যায়ঃ জীবন্ত বস্তুর জন্য ফরওয়ার্ডিং অবস্থান গণনা করুন। একটি বিনামূল্যে এবং লাইভ পয়েন্টারের উপর নজর রাখুন এবং স্তূপের শুরু পর্যন্ত উভয়ই শুরু করুন। যদি লাইভ পয়েন্টারটি কোনও লাইভ অবজেক্টের দিকে নির্দেশ করে, তবে সেই অবজেক্টের ফরওয়ার্ডিং পয়েন্টারটি বর্তমান ফ্রি পয়েন্টারে আপডেট করুন এবং অবজেক্টের আকার অনুযায়ী ফ্রি পয়েন্টারটি বৃদ্ধি করুন। লাইভ পয়েন্টারটি পরবর্তী বস্তুর প্রান্তে নিয়ে যান যখন লাইভ পয়েন্টারটি স্তূপের শেষে পৌঁছায়। সমস্ত পয়েন্টার আপডেট করুন প্রতিটি লাইভ অবজেক্টের জন্য, তারা যে বস্তুগুলিকে নির্দেশ করে তার ফরওয়ার্ডিং পয়েন্টার অনুসারে এর পয়েন্টারগুলি আপডেট করুন। বস্তু সরান প্রতিটি জীবন্ত বস্তুর জন্য, তার তথ্য তার ফরওয়ার্ডিং অবস্থানে সরান। এই অ্যালগরিদমটি হিপে আকারের উপর ও (এন); টেবিল-ভিত্তিক পদ্ধতির তুলনায় এটির একটি ভাল জটিলতা রয়েছে, তবে টেবিল-ভিত্তিক পদ্ধতির এন শুধুমাত্র ব্যবহৃত জায়গার আকার, এলআইএসপি 2 অ্যালগরিদমের মতো পুরো হিপে স্থান নয়। তবে, এল. আই. এস. পি2 অ্যালগরিদম বাস্তবায়ন করা সহজ। আরও দেখুন ডেড-কোড এলিমিনেশন ট্রেসিং আবর্জনা সংগ্রহের তথ্যসূত্র স্বয়ংক্রিয় মেমরি ম্যানেজমেন্ট মেমরি ম্যানেজমেন্ট অ্যালগরিদম