Nhái Cốm Blog

I love you just the way you are

0R8A4000_

Quay lại tương lai – Tách rời

Leave a comment

Tác giả: Dmitriy Gakh
Bài gốc: Back to the Future – Decapsulation

Lược dịch

Giới thiệu

Khi các mô-đun lập trình phải xử lý một lượng dữ liệu khổng lồ lưu trữ trong RAM, cấu trúc dữ liệu ảnh hưởng đến lượng RAM sử dụng cũng như hiệu suất. Để tiết kiệm tài nguyên máy tính, bạn nên sử dụng các kiểu dữ liệu nguyên thủy, dùng cấu trúc (struct) thay vì lớp (class) hoặc tốt hơn dùng dữ liệu cơ bản thay vì cấu trúc. Hướng tiếp cận này đi ngược lại lập trình hướng đối tượng, quay lại việc áp dụng các phương pháp lập trình cũ. Tuy nhiên, trong một số trường hợp, cách tối ưu này có khả năng xử lý rất nhiều vấn đề. Một nghiên cứu đơn giản chứng minh rằng hoàn toàn có thể giảm lượng bộ nhớ cần dùng xuống 3 lần.

Những vấn đề dưới đây sẽ được đề cập đến trong bài viết:

  • Sự ảnh hưởng của kiến trúc phần mềm đối với lượng bộ nhớ sử dụng cũng như hiệu suất
  • Sự khác nhau trong việc chạy ứng dụng trong chế độ 32 bit và 64 bit
  • Sự khác nhau giữa các con trỏ và các chỉ số trong mảng
  • Ảnh hưởng của việc sắp xếp dữ liệu bên trong cấu trúc (struct) và lớp (class)
  • Ảnh hưởng của bộ nhớ đệm CPU đến hiệu suất
  • Đánh giá chi phí liên quan đến việc hỗ trợ lập trình hướng đối tượng trong các ngôn ngữ lập trình cấp cao
  • Nhận thức sự cần thiết của những tính năng cấp thấp trong một nền tảng, ngay cả khi bạn đang sử dụng các ngôn ngữ cấp cao

Khái quát

Chúng tôi bắt đầu áp dụng phương pháp này khi pháp triển giải pháp tìm đường tối ưu mới cho cổng thông tin http://www.GoMap.Az. Thuật toán mới tạo sử dụng nhiều RAM hơn thuật toán cũ, kết quả là ứng dụng bắt đầu có tình trạng tắc nghẽn sau khi được cài đặt lên máy chủ. Việc nâng cấp phần cứng trong trường hợp này cần nhiều ngày trong khi việc tối ưu lượng RAM sử dụng bằng phần mềm cho phép giải quyết vấn đề nhanh chóng hơn nhiều. Trong bài viết này, chúng tôi sẽ chia sẻ kinh nghiệm của mình và mô tả theo cách đơn giản nhất những việc chúng tôi đã thực hiện cũng như lợi ích những việc đó mang lại.

Việc bố trí không gian lưu trữ cho một lượng lớn cấu trúc dữ liệu và truy xuất đến những dữ liệu đó là một vấn đề thực sự quan trọng đối với những hệ thống thông tin làm việc với dữ liệu địa lý. Loại vấn đề này có xu hướng xảy ra khi pháp triển những hệ thống thông tin hiện đại khác nhau.

Chúng ta cùng đánh giá việc lưu trữ và truy xuất dữ liệu thông qua một ví dụ về các con đường – các cạnh của một đồ thị. Để tiện hình dung, con đường được thể hiện bởi class Road và các con đường được lưu giữ trong class RoadContainer. Bên cạnh đó, class Node thể hiện một điểm trên đồ thị. Đối với Node, chúng ta chỉ cần biết nó là một class. Chúng ta cũng giả sử rằng các cấu trúc dữ liệu không chứ các hàm cũng như quan hệ thừa kế; nói theo cách khác, chúng chỉ được sử dụng để lưu trữ và xử lý dữ liệu.

Trong bài viết này, chúng ta sẽ sử dụng ngôn ngữ C# mặc dù trên thực tế chúng tôi sử dụng C++. Thật ra vấn đề và giải pháp cho vấn đề nằm trong lĩnh vực lập trình hệ thống. Tuy nhiên, nghiên cứu cũng chỉ ra việc sử dụng lập trình hướng đối tượng có thể phải đánh đổi bằng một chi phí đáng kể. C# có thể là cách tốt nhất để chỉ ra những chi phí ngầm này, mặc dù nó không phải là một ngôn ngữ lập trình hệ thống.

// Main data structure – class Road
public class Road
{
	public float Length;
	public byte Lines ;
	
	// Class Node is described anywhere 
        // Road refers to two Node objects here
	public Node NodeFrom;
	public Node NodeTo;

	// Other members
}

// Container of roads
public class RoadsContainer
{
	// Other members

	// Returns roads located in specific region
	public Road[] getRoads(float X1, float Y1, float X1, float Y1)
	{
		// Implementation
	}

	// Other members
}

Bộ nhớ RAM và hiệu suất

Khi đánh giá hiệu suất và mức độ sử dụng bộ nhớ, các yếu tố của kiến trúc nền tảng dưới đây nên được cân nhắc đến:

  • Sắp xếp dữ liệu:
    Việc sắp xếp dữ liệu giúp tăng tốc độ truy xuất của CPU đến bộ nhớ. Vì vậy, phụ thuộc vào loại CPU mà địa chỉ của cấu trúc dữ liệu hay đối tượng trong bộ nhớ có thể bắt đầu từ những địa chỉ là bội số của 32 hay 64. Các trường dữ liệu bên trong cấu trúc hay đối tượng có thể được sắp xếp theo từng khối 32, 16 hoặc 8 byte (ví dụ, trường Lines trong class Road chiếm 4 byte thay vì 1 byte). Theo cách này, lượng bộ nhớ sử dụng tăng lên do những vùng nhớ không sử dụng đến.
  • Bộ nhớ đệm CPU:
    Như đã biết, mục đích chính của bộ nhớ đệm CPU là tăng tốc độ truy xuất đến những khối bộ nhớ được sử dụng thường xuyên. Kích thước của bộ nhớ đệm là rất nhỏ do đây là một trong những loại bộ nhớ đắt đỏ nhất. Khi làm việc với cấu trúc dữ liệu hay đối tượng, các vùng nhớ không sử dụng cũng được lấp đầy trong bộ nhớ đệm mà không mang bất kì thông tin hữu ích nào. Điều này làm giảm hiệu quả của việc sử dụng bộ nhớ đệm.
  • Kích thước con trỏ:
    Trên các hệ thống 32 bit, một con trỏ trỏ đến địa chỉ của đối tượng trong bộ nhớ có kích thước là 32 bit; qua đó giới hạn ứng dụng làm việc với kích thước RAM tối đa là 4GB. Các hệ thống 64 bit có thể làm việc với lượng bộ nhớ nhiều hơn nhờ sử dụng con trỏ có kích thước 64 bit. Các đối tượng luôn có một con trỏ trỏ đến nó (nếu không vùng bộ nhớ sẽ bị rỏ rỉ hoặc nằm trong danh sách sẽ bị loại bỏ bởi bộ dọn rác – Garbage Collector). Trong ví dụ của bài viết, trường NodeFrom và NoteTo của class Road sẽ chiếm 8 bytes tronng hệ thống 64 bit và 4 byte trong hệ thống 32 bit.

Như một nguyên tắc, trình biên dịch luôn tạo ra mã nguồn tốt nhất có thể, nhưng hiệu quả cao nhất chỉ có thể đạt được thông qua các giải pháp ứng dụng phần mềm.

Mảng các đối tượng

Dữ liệu có thể được lưu trữ bằng nhiều cấu trúc khác nhau: danh sách (list), bảng băm (hash table)… Việc lưu trữ dữ liệu trong một mảng (array) có lẽ là cách đơn giản và phổ biến nhất; đó là lý do chúng tôi quyết định lựa chọn cấu trúc này. Bạn có thể tìm hiểu những cấu trúc dữ liệu khác theo cách tương tự.

Trong C#, mảng các đối tượng lưu trữ địa chỉ tham chiếu của các đối tượng; bản thân các đối tượng này được lưu trữ ở nơi khác trong bộ nhớ heap. Cách tổ chức này cho phép thao tác dễ dàng hơn với một tập hợp các đối tượng vì bạn chỉ phải làm việc với các con trỏ thay vì bản thân đối tượng. Trong ví dụ của chúng tôi, hàm getRoads của class RoadsContainer trả về một tập hợp các đối tượng thông qua địa chỉ tham chiếu của chúng thay vì sao chép dữ liệu bên trong các đối tượng. Điều này có thể thực hiện được do kiểu của đối tượng trong C# là kiểu dữ liệu tham chiếu.

Điểm bất lợi trong việc lưu trữ các đối tượng như một mảng chính là việc phải thêm không gian lưu trữ cho các con trỏ cũng như việc sắp xếp lại các đối tượng trong bộ nhớ heap. Trên các hệ thống 64 bit, mỗi con trỏ chiếm 8 byte bộ nhớ và mỗi đối tượng được sắp xếp sao cho địa chỉ của nó có thể chia hết cho 8.

Mảng các cấu trúc

Các lớp (class) được thiết kế để lưu trữ Road và Node có thể được chuyển sang cấu trúc (struct). Các chỉ số kiểu số nguyên sẽ được sử dụng thay vì con trỏ đến đối tượng. Kết quả của việc chuyển đổi như sau:

public struct Road
{
	public float Length;
	byte Lines ;
	Int32 NodeFrom;
	Int32 NodeTo;

	// Other members
}

public class RoadsContainer
{
	// Other members

	// Roads are in an array now, not in the heap
	Road[] Roads;

	// Returns roads located in specific region
	public Int32[] getRoads(float X1, float Y1, float X1, float Y1)
	{
		// Implementation
	}

	// Returns road by index
	public Road getRoad(Int32 Index)
	{
		return Roads[Index];
	}

	// Other members
}

// Container of nodes is similar by structure
// to the container of roades
public class NodesContainer
{
	// Other members

	Node []Nodes;

	// Returns node by index
	public Node getNode (Int32 Index)
	{
		return Nodes[Index];
	}

	// Other members
}

Việc thay đổi này có lợi gì?

Road được lưu trữ theo kiểu cấu trúc thay vì đối tượng. RoadsContainer sử dụng một mảng để lưu trữ chúng. Hàm getRoad sẽ trả về những cấu trúc riêng biệt thông qua các số nguyên 32 bit được sử dụng như một con trỏ đến dữ liệu trong mảng. Các node trong class NodesContainer cũng hoạt động hoàn toàn tương tự.

Sử dụng các chỉ số 32 bit thay vì con trỏ 64 bit giúp giảm bộ nhớ và đơn giản hóa tác vụ truy xuất. Việc sử dụng chỉ số để tham chiếu đến các trường NodeFrom và NodeTo trong cấu trúc Road sẽ làm giảm bộ nhớ cần dùng đi 8 bytes (nếu các trường được sắp xếp theo vùng địa chỉ 32, 16 hoặc 8 bit).

Việc cấp phát bộ nhớ sẽ được thực hiện một lần khi mảng được tạo ra. Trong trường hợp lưu trữ địa chỉ tham chiếu các đối tượng, mỗi đối tượng cần được tạo ra độc lập. Việc tạo ra các đối tượng độc lập không chỉ cần thời gian mà còn cần thêm bộ nhớ để sắp xếp các trường dữ liệu cũng như đăng ký đối tượng bên trong bộ nhớ heap cũng như hệ thống dọn rác – GC.

Điểm bất lợi khi sử dụng cấu trúc thay vì đối tượng, như đã nói, là bạn không thể sử dụng con trỏ đến các cấu trúc (do cấu trúc là kiểu giá trị chứ không phải kiểu tham chiếu). Điều này ngăn cản việc thao tác với tập hợp các đối tượng. Vì vậy, hàm getRoads sẽ phải trả về chỉ số của các cấu trúc trong mảng. Trong khi đó hàm getRoad trả về cấu trúc; tuy nhiên, hàm này sẽ sao chép toàn bộ dữ liệu của cấu trúc để trả về hàm gọi, quá trình này làm tăng băng thông cũng như thời gian xử lý của CPU.

Mảng các giá trị nguyên thủy

Mảng các cấu trúc có thể được chuyển thành các mảng tương ứng với từng trường của cấu trúc đó. Nói cách khác, cấu trúc có thể được tách rời rồi loại bỏ. Ví dụ, sau khi tách rời và loại bỏ cấu trúc Road, chúng ta sẽ có mã lệnh sau:

public class RoadsContainer
{
	// Other members
	// Fields of structure Road
	float[] Lengths;
	byte[] Lines;
	Int32[] NodesFrom;
	Int32[] NodesTo;

	// Other members

	// Returns roads located in specific region
	public Int32[] getRoads(float X1, float Y1, float X1, float Y1)
	{
		// Implementation
	}

	// Returns length of road by the index
	public float getRoadLengt(Int32 Index)
	{
		return Lengths[Index];
	}

	// Returns number of lines of road by the index
	public byte getRoadLines(Int32 Index)
	{
		return Lines[Index];
	}

	// Returns starting node of road by the index
	public Int32 getRoadNodeFrom(Int32 Index)
	{
		return NodesFrom[Index];
	}

	// Returns ending node of road by the index
	public Int32 getRoadNodeTo(Int32 Index)
	{
		return NodesTo[Index];
	}

	// Other members
}

Việc thay đổi này có lợi gì?

Thay vì lưu trữ toàn bộ cấu trúc trong một mảng riêng lẻ, các trường của cấu trúc đó được lưu trữ trong các mảng khác nhau. Việc truy xuất đến các trường được thực hiện riêng biệt thông qua chỉ số.

Bộ nhớ lãng phí do việc sắp xếp các trường dữ liệu bên trong cấu trúc được loại bỏ khi mà dữ liệu các kiểu nguyên thủy được lưu trữ liền nhau. Bộ nhớ để lưu trữ không còn là một khối duy nhất mà là nhiều khối, lưu trữ mảng của các trường. Ở một mức độ nào đó, việc phân chia đó có ích cho hệ thống; sẽ dễ dàng hơn nhiều khi phải chuyển các phần nhỏ của một vùng nhớ liên tục thay vì một đoạn bộ nhớ liên tục lớn.

Giờ đây, việc truy cập đến từng trường yêu cầu sử dụng chỉ số mọi thời điểm trong khi với mảng cấu trúc, chỉ số chỉ phải sử dụng 1 lần duy nhất. Trong thực tế, việc này được coi vừa là điểm bất lợi cũng vừa là điểm lợi. Nếu chỉ phải sử dụng một phần nhỏ các trường, bạn sẽ tối ưu việc sử dụng bộ nhớ đệm CPU nếu chúng được lưu trữ trong các mảng độc lập. Để tận dụng tất cả lợi thế của bộ nhớ đệm còn phụ thuộc vào thuật toán, tuy nhiên trong bất kì trường hợp nào lợi thế mang lại là rất rõ ràng.

Dọn rác và quản lý bộ nhớ

Vấn đề đưa ra liên quan đến việc quản lý bộ nhớ. Dù sao đi nữa, địa chỉ các đối tượng trong bộ nhớ vẫn ảnh hưởng đến thời gian truy xuất. Cho đến thời điểm hiện tại, có rất nhiều cách quản lý bộ nhớ khác nhau, bao gồm cả hệ thống dọn rác tự động. Những hệ thống tự động này không chỉ theo dõi quá trình thu dọn bộ nhớ mà còn khắc phục hiện tượng phân mảnh bộ nhớ.

Các hệ thống quản lý bộ nhớ chủ yếu hoạt động với con trỏ của các đối tượng được cấp phát trong bộ nhớ heap. Đối với trường hợp của mảng cấu trúc hay mảng các trường, nó không thể làm việc trực tiếp với các phần tử trong mảng; toàn bộ công việc liên quan đến việc tạo và giải phóng các phần tử được đặt lên đôi vai của lập trình viên. Có thể thấy rõ ràng việc sử dụng mảng các cấu trúc hay các trường đã vô hiệu hóa chức năng của bộ dọn rác. Tùy thuộc vào ứng dụng, giới hạn này vừa có thể coi là điểm lợi, vừa có thể coi là điểm bất lợi.

Đánh giá

Lợi ích của việc tách rời được ước lượng thông qua một bài kiểm thử nhỏ. Mã nguồn của bài kiểm thử này có thể được tải về tại địa chỉ https://github.com/dgakh/Studies/tree/master/CSharp/Decapsulation. Trong bài kiểm thử, các mảng chứa 10 triệu phần tử được tạo ra, đọc và ghi dữ liệu. Bài kiểm thử chạy trên cả 2 chế độ 32 bit và 64 bit. Có một vấn đề nên được đề cập đến là trong chế độ 32 bit, sẽ rất dễ xảy ra tình huống tràn bộ nhớ khi phải làm việc với một lượng dữ liệu lớn. Mặc dù hiện nay chế độ 32 bit cho các hệ thống máy chủ và máy để bàn ngày càng ít được sử dụng, các hệ thống di động chủ yếu với dùng chế độ 32 bit. Vì vậy, việc đánh giá vẫn được thực hiện trong cả 2 chế độ.

Bộ nhớ

Bộ nhớ sử dụng trong chế độ 32 bit

Bộ nhớ sử dụng trong chế độ 64 bit

Như bạn có thể thấy, phần lớn bộ nhớ lãng phí nằm ở mảng các đối tượng. Với các hệ thống 64 bit, dung lượng lưu trữ tăng lên nhanh chóng. Mảng các cấu trúc hay các trường có độ lớn tương đương trong cả 2 chế độ. Mặc dù lưu trữ trong mảng các trường có lợi về lượng bộ nhớ hơn nhưng mức giảm này không thực sự quan trọng; bộ nhớ sử dụng giảm đi là do mất mát bộ nhớ khi sắp xếp các trường của kiểu cấu trúc.

Thời gian truy xuất


* – thời gian truy xuất quá nhỏ để có thể đo đạc chính xác

Thời gian truy xuất đến dữ liệu khi lưu trữ trong mảng các đối tượng là lớn nhất trong khi có thể truy xuất nhanh hơn nhiều nếu dữ liệu được lưu trữ trong mảng các trường một cách độc lập. Sự tăng tốc này là kết quả của việc sử dụng bộ nhớ đệm CPU một cách hiệu quả. Cũng phải lưu ý rằng bài kiểm thử được thực hiện với việc đọc/ghi liên tiếp các phần tử, do đó việc sử dụng bộ nhớ đệm được tối ưu hơn.

Kết luận

  • Tránh sử dụng lập trình hướng đối tượng (OOP) khi làm việc với lượng dữ liệu lớn có thể giúp sử dụng bộ nhớ RAM hiệu quả hơn 3 lần trên các hệ thống 64 bit, 2 lần trên các hệ thống 32 bit. Điều này xảy ra do kiến trúc phần cứng; và như hệ quả, nó ảnh hưởng đến tất cả các ngôn ngữ lập trình.
  • Trong C#, thời gian truy xuất thông qua chỉ số mảng nhỏ hơn nhiều so với truy xuất thông qua con trỏ đối tượng.
  • Công nghệ lập trình ở mức độ càng cao thì càng tốn tài nguyên. Làm việc ở mức độ thấp (mức độ hệ thống), với dữ liệu nguyên thủy (có thể đạt được thống qua tách rời các lớp hay cấu trúc) sử dụng ít tài nguyên nhất nhưng yêu cầu bạn phải viết nhiều mã lệnh cũng như công sức hơn.
  • Làm việc với các kiểu dữ liệu nguyên thủy là một cách tối ưu mã lệnh. Vì vậy, kiến trúc này không được sử dụng trong thiết kế kế ban đầu mà được sử dụng khi cần giảm lượng tài nguyên sử dụng.
  • Trong C++, nhiều vấn đề đưa có thể được giải quyết một cách minh bạch, nhưng với C#, cách thực hiện bên dưới được che đi. Thêm vào đó, thông thường khi học C#, ảnh hưởng của nền tảng không được cân nhắc đến.
  • Trong C#, cấu trúc (struct) nên được cân nhắc sử dụng thay vì lớp (class) khi có thể.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s