Performance của switch-case so với if-else

So sánh performance giữa switch-case so với if-else và các kĩ thuật tối ưu của compiler đối với việc định nghĩa switch-case.

switch-case so với if-else

switch-case sẽ được định nghĩa bằng các khối if, else-if liền nhau. Như vậy, performance của switch-case và if-else sẽ như nhau?
 Tuy nhiên:

• Compiler được phép làm mọi thứ để tối ưu hóa chương trình, miễn là vẫn tuân theo các đặc tả của ngôn ngữ lập trình đó và không gây ra side-effect. 
• Compiler ngày nay cực kì thông minh.

switch-case là một trường hợp đặc biệt của if-else (trong "mọi trường hợp" có thể dùng if-else, nhưng switch-case thì chỉ với một số trường hợp). 

Một số giải pháp tối ưu switch-case của compiler

Jump table

Một khối lệnh switch-case như sau:

switch(value)
{
	case 3:
		//Code
		break;
	case 4:
		//Code
		break;
	case 5:
		//Code
		break;
	case 6:
		//Code
		break;
	case 7:
		//Code
		break;
	case ...:
		...
	case n:
		//Code
		break;
}

Đây là một trường hợp cực kì đặc biệt, làm liên tưởng đến mảng.

Thay vì so sánh value với từng giá trị 3, 4, 5, ..., n rồi thực hiện đoạn code tương ứng. Có thể:

• Tạo ra một mảng (n - 3 + 1) phần tử (gọi mảng này là jump table), mảng này sẽ chứa địa chỉ đoạn code thực thi của case 3, 4, 5..., n.
• Thay vì phải so sánh value với từng giá trị từ 3->n đến khi tìm ra case tương ứng, chỉ cần dùng value như một index của jump table trên, và truy xuất trực tiếp jump table này để tìm ra địa chỉ của đoạn code thực thi tương ứng với case "value", và chỉ cần thực hiện jump đến địa chỉ đó.
• Độ phức tạp của phương pháp này là O(1), nhanh hơn rất nhiều so với O(n) nếu định nghĩa switch-case bằng if-else.

Ý tưởng implement switch-case bằng jump table

Đầu tiên, tạo 1 mảng (n - 3 + 1) phần tử, chứa địa chỉ của đoạn code trong case 3, 4, 5..., n vào phần tử tại index (3-3), (4-3), (5-3)... (n-3) của mảng.

Psuedo-code

if( value > n || value <3 )
    jmp <Địa chỉ đoạn code sau switch-case>;
jmp jump_table[value-3];

Mảng function pointer

Có thể sử dụng 1 mảng chứa các function pointer, các function pointer này sẽ trỏ đến function chứa đoạn code tương ứng với từng case, nhưng nó sẽ chậm hơn so với jump table vì nó tốn thêm chi phí cho một function call.

Nhưng giải pháp này chỉ tối ưu trong trường hợp:

• Số lượng case trong khối switch lớn
• Các case trong switch phải có giá trị gần nhau hoặc liên tiếp nhau.

Ngoài ra, có thể sử dụng 2 jump-table để tối ưu trong một số trường hợp mà 1 jump-table không hiệu quả như:

• Các case của switch có giá trị {1, 2, 3, 79, 80, 81, 103, 104, 105}

Binary search

Giải pháp này có ý tưởng tương tự thuật toán binary search: 

Giả sử có 1 mảng các giá trị {<Giá trị của case đầu tiên>, <Giá trị của case thứ 2>, ..., <Giá trị của case thứ n>}.

Bài toán trở thành: tìm index của phần tử có giá trị bằng value trong mảng trên. Thuật toán đầu tiên nghĩ đến sẽ là binary search. Để thực hiện binary search, mảng phải ở trạng thái đã sắp xếp. Nhưng việc sắp xếp này sẽ được thực hiện tại compile-time (trong khi compiler đang thực hiện optimize) nên nó sẽ không ảnh hưởng tới performance khi chương trình đang chạy (tại run-time). Nên không cần quan tâm đến chi phí sắp xếp của mảng trên. Như vậy, chỉ việc thực hiện binary search đối với mảng trên để tìm ra địa chỉ của đoạn code trong case tương ứng. Performance của giải pháp này so với việc định nghĩa bằng if-else cũng tương tự như performance của binary search so với linear search (O(log n) so với O(n)).

Thông thường giải pháp này sẽ được áp dụng trong trường hợp:

• Số lượng case trong khối switch không quá nhỏ.
• Các giá trị của case rời rạc chứ không liên tiếp nhau (Nếu liên tiếp nhau thì việc sử dụng jump table sẽ hiệu quả hơn).