Điều gì xảy ra khi chương trình thực thi 1 vòng lặp “đơn giản” trong C++?

3
2387

Có bao giờ bạn thắc mắc cách mà Google làm thế nào để trả về kết quả cực nhanh chỉ sau 0,xx giây hay cách 1 đoạn mã trong chương trình chạy sẽ thực thi những gì chưa?

Về vụ cách mà Google hoạt động thì các bạn có thể đọc repo sau trên Github:

Còn bài này sẽ nói điều gì sẽ xảy ra khi chương trình thực thi vòng lặp sau:

for (int I = 0; I < 1000000; I++) {
     cout << I;
}

Bạn có thấy vòng lặp này quá sức đơn giản? Yeah, nó thực sự đơn giản tuy nhiên nó có chút vấn đề khi chạy: “tốc độ thực thi”. Với những chiếc máy tính hiện đại, việc lặp 1.000.000 phần tử là điều hết sức bình thường. Tuy nhiên mọi sự không đơn giản với đoạn code trên.

Máy tính không phải là 1 con khủng long có sức mạnh vô song, bạn cần tối ưu mã sao cho nó nhanh nhất có thể

Trước khi tìm hiểu sâu hơn, thì mình đọc qua bài viết này trên Quora Việt Nam dịch bởi bạn Vũ Cường. Mới hôm qua đó thôi, mình cũng đăng 1 bài viết của Vũ Cường với câu hỏi: “Bằng cách nào để nén dữ liệu khi chúng là một lượng byte rất nhỏ?” – và mình bất ngờ vì số lượt xem cũng như thích thú với bài viết đó.

Cho nên mình quyết định chia sẻ thêm 1 bài viết chuyên sâu hơn, nhiều não hơn với mong muốn a/e có thể hiểu được sâu hơn bản chất vấn đề.

Nào, sẵn sàng để tìm hiểu chưa a/e?

Q: Nếu một máy tính thực hiện được một triệu phép tính mỗi giây thì tại sao đoạn code for (int I = 0; I < 1000000; I++) {cout <<I;} lại chạy mãi chẳng xong vậy?

A: Steve Baker, Blogger LetsRunWithIt.com (2013-nay)


(Ví dụ) nếu bạn viết đoạn code NÀY bằng ngôn ngữ C hoặc C++ nhé:

for ( int i = 0 ; i < 1000000 ; i++ ) x += i;

(Hãy lưu ý rằng tôi đã thay đổi đoạn mã để cộng tổng tất cả các số từ 0 tới 1000000 thay vì hiển thị các con số đó lên màn hình – RẤT quan trọng đấy!)

…và dịch đoạn đó thành mã máy thì máy tính sẽ phải làm những việc sau:

  • Kiểm tra xem liệu i có còn nhỏ hơn 1 triệu nữa không.
  • Cộng i vào x.
  • Tăng i lên một.
  • Quay ngược lại đoạn ban đầu và làm lại hết tất cả.

Có khoảng 4 đoạn lệnh mã máy (tương ứng với 4 gạch đầu dòng trên) – mỗi đoạn được thực thi một triệu lần – khoảng 4 triệu lệnh.

Và do máy tính của bạn có thể thực hiện hàng TỶ lệnh mỗi giây nên đoạn code này có thể chạy rất nhanh… Chậc, còn dưới một một phần ngàn giây đối với những chiếc máy tính hiện đại nữa kia.

Giờ thì… Tất cả những điều tôi đang nói đều được đặt ra với giả thiết rằng bạn đang dùng C hoặc C++ và dịch chương trình đó ra mã máy nhé.

Mọi việc khó từ đây:

Nhưng câu hỏi bạn đặt ra ấy là:

for ( int i = 0 ; i < 1000000 ; i++ ) cout << i;

Mới nhìn qua thì đối với máy tính, đoạn cout << i; không khác lắm so với x += i ; – nhưng lại “khoai” thật đấy!

Cứ thử nhìn xem máy tính sẽ phải làm gì để thực hiện một vòng lặp của đoạn mã ĐÓ nhé:

  • Kiểm tra xem liệu i có còn nhỏ hơn 1 triệu nữa không.
  • Tăng i lên một.

Gửi i tới bộ đầu ra chuẩn. Và điều đó đồng nghĩa với việc:

  • Việc chuyển đổi số i đó thành một xâu theo chuẩn ký tự ASCII cơ số 10 và thêm cả một ký tự rỗng (null terminator)… đòi hỏi một hàm khá phức tạp, kiểm tra xem số đó có âm hay không (trường hợp này thì là không) và rồi lại phải thực hiện một vòng lặp làm vài thứ kiểu chia liên tiếp i cho 10 và cộng mã ASCII của 0 vào mỗi chữ số. Có lẽ điều này tương đương với khoảng một vài trăm phép xử lý máy tính – số càng lớn càng phải thực hiện nhiều lần hơn.
  • Gửi xâu chứa các chữ số đó tới “standard output” stream – giờ lại cần thêm một vài vòng lặp để sao chép mỗi ký tự ASCII đó vào một bộ đệm (buffer) trong object cout stream. Thêm vài chục câu lệnh nữa nhé.
  • Kiểm tra xem bộ đệm đó đã đầy chưa – chắc cứ vài trăm vòng lặp là phải làm một lần và nếu đầy thì sao…
  • Gửi bộ đệm đó tới hệ thống phân chia cửa sổ…lại HÀNG TRĂM câu lệnh nữa.
  • Hệ thống phân chia cửa sổ sẽ xác nhận xem bộ đệm đó sẽ được gửi tới cửa sổ hiện hành nào.
  • Tìm xem loại font đang được sử dụng là gì.
  • Kiểm tra xem xâu đó có chứa những ký tự như tab, dấu backspace hay newline hay không – hoặc xem nó có in đậm, nghiêng gì không.
  • Có thể nó sẽ cho rằng cửa sổ cần được cuộn lên và sẽ phải update lại thanh cuộn và chuyển mọi thứ khác lên trên. Vì bạn có thể tự mình dùng chuột cuộn cửa sổ đó lên nên máy cũng phải lưu lại những ký tự đó ở nơi nào đó để bạn có thể cuộn xem lại về sau. (Hàng triệu câu lệnh luôn!)
  • Sau đó nó phải gọi tới driver đồ họa để sử dụng card đồ họa.
  • Từ đó máy phải gọi kernel hệ điều hành, và kernel đấy phải lưu lại trạng thái chương trình để sau có thể sử dụng lại (hàng trăm câu lệnh nhé)…
  • Việc này đồng nghĩa với việc nó phải kiểm tra xem có chương trình nào khác cần chạy hay không. – và có thể phải chạy những chương trình đó một lúc đấy (hàng chục triệu câu lệnh nữa!).
  • Cuối cùng là câu lệnh vẽ các điểm ảnh tạo nên ký hiệu cho giá trị thập phân của i và được gửi vào hàng chờ để gửi tới chip GPU (lại vài trăm câu lệnh nữa nhé).
  • Khi GPU xong việc (có thể tốn thời gian một chút nếu có chương trình nào khác muốn hiển thị cái gì đó) – thì dữ liệu để cập nhật lại cửa sổ của bạn sẽ được gửi tới GPU thông qua cơ chế “DMA” (direct memory acess) khi có thời gian.
  • Thoát tất cả những câu lệnh đó và chờ hệ điều hành quyết định xem lúc nào có thể chạy chương trình đó một lần nữa…

Đây là những bước con khi câu lệnh cout << i; được thực hiện.


Và CUỐI CÙNG… Quay ngược lại đoạn ban đầu và làm lại hết tất cả những thứ trên đây.

=> ôi, dm. Thế có chết tôi không. Máy tính said.

Vì thế vấn đề là – chính vòng lặp đó chỉ tốn khoảng một phần tỷ giây mỗi lần lặp thôi – song những gì bạn làm trong vòng lặp đó là thứ gây nên một loạt phản ứng dây chuyền, những thứ thực sự phức tạp đó!

Một trong những bài học mà bạn phải học được khi lập trình ấy là Input/Output là thứ ngốn tài nguyên nhất mà một chương trình có thể thực hiện.

Đây không phải là khả năng duy nhất có thể xảy ra đâu – bạn có thể sẽ phải điều hướng standard output stream tới một file nào đó trên đĩa cứng… Từ đó dẫn tới việc điều hướng một mớ hổ lốn các process và driver khác nữa.

Thực tế thì, đối với những thứ như video game – toàn bộ process phải được rút ngắn bất cứ khi nào có thể bằng việc để chương trình kết nối trực tiếp với chip graphic – loại trừ tất cả những bước trung gian và chỉ để lại một vài thao tác nhỏ vậy thôi.

Máy tính nhanh vãi lúa – song chúng cũng phải thực hiện những công việc điên khùng vãi lúa luôn đấy!!

P/s: đoạn code trên là cố ý đưa ra để chúng ta có cái để phân tích, thông thường khi code bạn sẽ có kinh nghiệm tránh những lỗi cơ bản như thế này.

Nguồn: Quora

4.9/5 - (8 bình chọn)
Bài trướcBằng cách nào để nén dữ liệu khi chúng là một lượng byte rất nhỏ?
Bài tiếp theoNhận tạo acc Spotify Premium giá rẻ chỉ 86k / slot dùng lâu dài
Tui là 1 con người cả ngố đó mấy bạn, thật may tui được thằng Tín tà tưa (bạn cùng phòng) nhờ làm cái web mà nó không viết gì, tui cũng không biết viết nhưng mà bỏ phí domain tốn xiền. Share Ngay ra đời lãng xẹt z đó. Blog này tui viết hồi cuối tháng 3/2018, có thể thấy độ trẻ trâu qua từng năm của tui không hề giảm. Nói thiệt nha, tui quý mấy bạn đọc cái blog này dù cho nó có mang lại giá trị cho mấy bạn không, nhưng mà tui thực sự cảm ơn mấy bạn. Hông giống Youtube, đăng lên phát là có vài chục ngàn view, tui đăng lên 1 phát có chục view là: "Ơ, dm, sao bữa này nhiều ng đọc dị. Tui dzui. Mấy bạn comment, tui đọc. Tui dzui. Đơn giản dậy thôi". Tui quỡn lắm, lâu lâu đọc lại những gì mình viết rồi thấy trẻ trâu mà không dám sửa. Thôi cứ để nó là 1 kỷ niệm. Ờ, nói nhiều là dậy, vì tui muốn mấy bạn thoải mái nhất khi đọc những dòng này nên viết có hơi dài dòng. Đoạn giới thiệu dễ thương này dành tặng tất cả những ai yêu mến Share Ngay. Sharahero!!!
Theo dõi
Thông báo về
guest
3 người bình luận
mới nhất
cũ nhất like nhiều nhất