Tag Archives: pool

Sử dụng bộ nhớ hiệu quả với Memory Pool

Vấn đề cân bằng giữa tốc độ và sử dụng bộ nhớ luôn là vấn đề đau đầu đối với lập trình viên. Khi phải đối mặt với vấn đề này, người lập trình phải cân nhắc xem nên ưu tiên tốc độ hay bộ nhớ. Đối với những ứng dụng chạy theo thời gian thực thì bộ nhớ luôn là vấn đề hàng đầu, bởi trong suốt vòng đời của ứng dụng, các đối tượng liên tục được tạo và hủy gây phân mảnh vùng nhớ, do vậy nếu quản lý bộ nhớ không tốt sẽ gây lãng phí tài nguyên dẫn đến hệ thống nhanh chóng rơi vào tình trạng cạn bộ nhớ. Đối với việc lập trình cho các thiết bị hạn chế về tài nguyên thì cần phải xem trọng cả hai. Việc tìm ra điểm cân bằng giữa tốc độ thực thi và sử dụng bộ nhớ là một công việc không phải lúc nào cũng dễ dàng.

Bài viết này sẽ cung cấp cho các bạn một giải pháp để tham khảo trong việc quản lý bộ nhớ sử dụng Memory Pool. Memory Pool là một kỹ thuật giúp khai thác vùng nhớ một cách hiệu quả bằng cách khởi tạo một vùng nhớ cố định sau đó quản lý việc cấp phát và tái chế các đối tượng trong vùng nhớ này.

Để hiểu được cách mà Pool hoạt động, ta thử đặt một tình huống giả định sau đây: Một đạo diễn phim nhận được một kịch bản trong đó có hơn 100 nhân vật, nhưng thực tế ông chỉ có 10 diễn viên trong tay. Làm thế nào để hoàn thành bộ phim có hơn 100 nhân vật mà trong tay chỉ có 10 diễn viên? Câu trả lời trong trường hợp này đơn giản là: cho mỗi diễn viên đóng nhiều vai khác nhau.

Thử một tình hống khác: Làm thế nào để tiêu diệt 1000 máy bay địch mà trong tay bạn chỉ có 10 viên đạn? :D. Các bạn sẽ thắc mắc rằng thực tế làm sao mà làm được như vậy, nhưng nếu bạn đã từng chơi một game đi cảnh bắn súng kiểu như SkyForce thì điều này hoàn toàn là sự thật đứng dưới góc độ của lập trình viên, còn tất nhiên người chơi thì vẫn chỉ biết bắn và bắn mà không hề biết rằng mình chỉ có 10 viên đạn!!! Tình huống này so với tình huống trên là không khác gì nhau nếu nhìn nhận dưới góc độ của Pool.

Nếu các bạn vẫn cảm thấy chưa thuyết phục, ta hãy code một game đơn giản giúp minh họa cách hoạt động của memory pool như sau: Trò chơi với một khẩu súng máy có 1000 viên đạn, bắn liên tục vào một bia đích cách đó 10m. Trò chơi sẽ kết thúc khi không còn viên đạn nào được bắn ra.

Sau đây ta cùng nhau khảo sát mã nguồn của trò chơi này (tuy viết bằng Java, nhưng về mặt tư tưởng có thể áp dụng trên các ngôn ngữ và nền tảng khác):

– Mô tả lớp các viên đạn, với một thuộc tính cơ bản là vị trí của viên đạn theo thời gian (đơn vị m):

public class Bullet {
    private int position;

    public int getPosition() {
         return position;
    }

    public void setPosition(int position) {
         this.position = position;
    }

    public Bullet() {
    }

    public void move() {
         position++;
    }
}

– Lớp MemoryPool cho phép tạo pool cho một nhóm đối tượng cụ thể:

import java.util.LinkedList;

public abstract class MemoryPool<T> {
    private LinkedList<T> free_items = new LinkedList<T>();
    public void freeItem(T item) {
        free_items.add(item);
    }
    protected abstract T allocate();
    public T newItem() {
        T out = null;
        if ( free_items.size() == 0 ) {
             out = allocate();
        } else {
             out = free_items.getFirst();
             free_items.removeFirst();
        }
        return out;
    }
}

Ta thấy MemoryPool sử dụng cấu trúc dữ liệu FreeList, trong đó free_items là một danh sách liên kết cho phép lưu các đối tượng đã được giải phóng khi hết vai trò, chúng sẽ được tái sử dụng trong phương thức newItem(). MemoryPool có một phương thức allocate() dùng để tạo mới các đối tượng trên thực tế, thay vì tạo mới và tái sử dụng như phương thức newItem().

– Lớp BulletPool là một MemoryPool được triển khai như sau:

public class BulletPool extends MemoryPool<Bullet> {
    @Override
    protected Bullet allocate() {
        return new Bullet();
    }
}

– Lớp Gun, mô tả một khẩu súng máy với khả năng bắn tiết kiệm (dùng Pool) và bắn “xả láng” (không dùng Pool).

public class Gun {
    private int bulletCount=1000;
    public void fireInPool() {
         BulletPool pool=new BulletPool();
         List<Bullet> plist=new ArrayList<>();
         for(int i=0;i<bulletCount;i++) {
             Bullet p=pool.newItem();
             p.setPosition(0);
             plist.add(p);
             for(int j=0;j<plist.size();j++) {
                 Bullet pp=plist.get(j);
                 pp.move();
                 System.out.print("-"+pp.getPosition());
                 if(pp.getPosition()==10) {
                      pool.freeItem(pp);
                      plist.remove(pp);
                 }
             }
             System.out.println();
         }
    }

    public void fire() {
         List<Bullet> plist=new ArrayList<>();
         for(int i=0;i<bulletCount;i++) {
              Bullet p=new Bullet();
              p.setPosition(0);
              plist.add(p);
              for(int j=0;j<plist.size();j++) {
                  Bullet pp=plist.get(j);
                  pp.move();
                  System.out.print("-"+pp.getPosition());
                  if(pp.getPosition()==10) {
                      plist.remove(pp);
                  }
              }
              System.out.println();
        }
    }
}

Cuối cùng là gameplay:

public class DemoMemoryPool {
    /**
    * @param args the command line arguments
    */
    public static void main(String[] args) {
        // TODO code application logic here
        Gun gun=new Gun();
        System.out.println("Start");
        gun.fireInPool();
        gun.fire();
        System.out.println("Game over");
    }
}

Dùng Profiler đo việc sử dụng bộ nhớ đối với đối tượng Bullet ta thấy kết quả khá rõ ràng, khi không sử dụng pool để bắn được 1000 viên đạn bạn cần khởi tạo 1000 đối tượng Bullet, trong khi với pool ta chỉ cần khởi tạo 11 đối tượng :

Điều thú vị là con số 11 đối tượng được khởi tạo không phụ thuộc vào số lần lặp trong vòng lặp for ở trên mà chỉ phụ thuộc vào điều kiện giải phóng đối tượng (trong ví dụ này là thời điểm position=10).

Như vậy có thể thấy rằng, việc sử dụng pool một cách khéo léo sẽ giải quyết khá triệt để vấn đề hạn chế về bộ nhớ trong ứng dụng, đặc biệt là game hoặc các ứng dụng tương tác thời gian thực. Tất nhiên triển khai pool trên thực tế còn phải phụ thuộc nền tảng và bản thân bài toán cụ thể. Hy vọng rằng qua bài viết này các bạn lập trình viên sẽ rút ra được những giải pháp, những ý tưởng cho các bài toán thực tế hàng ngày.

Tham khảo:
http://en.wikipedia.org/wiki/Memory_pool
http://en.wikipedia.org/wiki/Free_list
http://box2d.org/forum/viewtopic.php?f=5&t=2794&start=10