Tối ưu hóa Mã số

Question

Bạn được cung cấp một đống mã bằng ngôn ngữ yêu thích của bạn kết hợp để tạo thành một ứng dụng khá phức tạp. Nó chạy khá chậm, và sếp của bạn đã yêu cầu bạn tối ưu hóa nó. Các bước bạn làm theo để tối ưu hóa hiệu quả mã nhất là gì?

Bạn đã phát hiện ra những chiến lược nào là không thành công khi tối ưu hóa mã?

Viết lại: Tại thời điểm nào bạn quyết định ngừng tối ưu hóa và nói "Điều này nhanh như nó sẽ nhận được mà không cần viết lại hoàn toàn". Trong trường hợp nào bạn sẽ ủng hộ việc viết lại hoàn toàn đơn giản? Làm thế nào bạn sẽ đi về thiết kế nó?

Answer 1

Tiểu sử trước khi thử bất kỳ tối ưu hóa nào.

9 lần trong số 10 lần, thời gian sẽ không được tiêu thụ ở nơi bạn có thể đoán được.

Chiến lược không thành công thông thường là tối ưu hóa vi mô, khi những gì được yêu cầu thực sự là thuật toán thích hợp.

buộc Donald Knuth quote:

"Chúng ta nên quên đi hiệu quả nhỏ, nói rằng khoảng 97% thời gian: sớm tối ưu hóa là gốc rễ của mọi tội lỗi"

Answer 2

bước:

1. Đo
2. Phân tích
3. Quyết định
4. Thực hiện
5. Lặp lại

Đầu tiên có được một hồ sơ để đo mã. Đừng rơi vào cái bẫy giả định bạn biết nơi bị tắc nghẽn. Ngay cả sau đó, nếu giả định của bạn chứng minh là chính xác, đừng nghĩ rằng bạn có thể bỏ qua bước đo lường trong lần tiếp theo bạn có một nhiệm vụ tương tự.

Sau đó phân tích các phát hiện của bạn. Nhìn vào mã, xác định các tắc nghẽn bạn có thể làm một cái gì đó về điều đó sẽ có hiệu lực. Hãy thử ước tính mức độ cải thiện này sẽ là bao nhiêu.

Quyết định xem bạn có muốn đi xuống con đường này hay không, dựa trên phân tích của bạn. Liệu lợi ích có xứng đáng không? Là một viết lại bảo hành? Có lẽ bạn thấy rằng mặc dù nó chạy chậm, nó tốt như nó sẽ nhận được hoặc rằng bạn đang ở gần đầu của đường cong hiệu suất nơi công việc cần thiết để eek ra một cải tiến nhỏ không được bảo đảm.

Thực hiện các thay đổi của bạn, viết lại nếu cần, hoặc cấu trúc lại mã nếu đó là con đường bạn đã đi xuống. Thực hiện theo các bước nhỏ để dễ dàng đo lường xem thay đổi của bạn có cung cấp những gì bạn muốn hoặc nếu bạn cần quay lại một bước và thử một tuyến đường khác.

Sau đó, quay lại bắt đầu và đo lường, phân tích, quyết định, triển khai, v.v.

Ngoài ra, trên lưu ý mã tái cấu trúc. Những điều đầu tiên bạn nên thay đổi là các phương pháp tiếp cận cấp thuật toán lớn.Những thứ như thay thế thuật toán sắp xếp với thuật toán khác hoạt động tốt hơn, v.v. Không bắt đầu với tối ưu hóa cấp dòng, như cách để có được một dòng tăng giá trị để đi nhanh hơn một chút. Đó là những tối ưu hóa cấp độ cuối cùng và thường không đáng giá, trừ khi bạn đang chạy trong điều kiện hiệu suất cực đoan.

Answer 3

Thậm chí đừng bận tâm thử bất cứ điều gì mà không cần một số loại loại hồ sơ, tôi không thể nhấn mạnh điều này đủ! Thật không may, tất cả các profilers tôi biết hoặc là hút hoặc là tốn kém (Yay cho chi phí kinh doanh!) Vì vậy, tôi sẽ cho người khác làm cho các khuyến nghị có :).

Bạn biết bạn cần viết lại khi dữ liệu cho bạn biết rằng bạn cần viết lại, nghe có vẻ đệ quy, nhưng thực sự chỉ có nghĩa là chi phí của kiến ​​trúc hoặc phần mềm hiện tại của bạn đủ để đẩy bạn trên vách đá hiệu suất, vì vậy không có gì bạn làm trong các thay đổi cục bộ có thể khắc phục vấn đề chung. Tuy nhiên, trước khi bạn nhận ra lệnh File-> New ..., lập kế hoạch, xây dựng một mẫu thử nghiệm và thử nghiệm mẫu thử tốt hơn hệ thống hiện tại cho cùng một công việc: thật ngạc nhiên khi không có sự khác biệt đáng chú ý!

Answer 4

Hãy chắc chắn để có đủ bài kiểm tra đơn vị để đảm bảo bất kỳ tối ưu hóa, bạn sẽ thực hiện sẽ không phá vỡ bất cứ điều gì

Hãy chắc chắn để đủ điều kiện thi của bạn môi trường. Đôi khi, một sự thay đổi đơn giản trong các tùy chọn thực hiện có thể đi một chặng đường dài.

Sau đó, chỉ khi đó, hãy bắt đầu phân tích mã.

Quyết định viết lại (đối với mã số đang hoạt động) chỉ nên được xem xét nếu có đủ diễn biến trong tương lai có thể không được kiến ​​trúc hiện tại hỗ trợ.
Nếu các bản sửa lỗi đơn giản có thể tăng tốc mã không được phép phát triển nhiều, không cần viết lại hoàn toàn.

Tiêu chí dừng thường được xác định trong sự cộng tác với người dùng cuối (khách hàng), nhưng tôi sẽ đề xuất một tài liệu chính thức khắc phục các mục tiêu để đạt được với quy trình tối ưu hóa này.

Answer 5

Bên cạnh hồ sơ, như mọi người đề cập, hai giải pháp tôi luôn đi đầu tiên (sau khi profilling) là Ghi nhớ và tải Lười biếng, cả hai đều dễ thực hiện và thường tạo sự khác biệt lớn.

Answer 6

Trước tiên hãy quyết định mục tiêu tối ưu hóa của bạn là gì - hãy đặt mục tiêu cho thời gian của các hoạt động cụ thể trên nền tảng phần cứng đã cho. Đo hiệu suất chính xác (đảm bảo kết quả của bạn có thể lặp lại) và trong môi trường giống như sản xuất (không có máy ảo, trừ khi đó là những gì bạn sử dụng trong sản xuất!).

Sau đó, nếu bạn quyết định đã đủ nhanh, bạn có thể dừng ở đó.

Nếu nó vẫn chưa đủ tốt, thì cần thêm một số công việc nữa - đó là nơi có hồ sơ. Bạn không thể sử dụng profiler rất tốt (ví dụ, nếu nó tác động quá nhiều), trong trường hợp thiết bị này nên được sử dụng thay thế.

Answer 7

Trước hết đừng quên những:

• sớm tối ưu hóa là gốc rễ của tất cả các tệ nạn
• Performance đến từ thiết kế

Thứ hai;

Đừng cho rằng thử và xem

Tôi nghĩ rằng đây là nguyên tắc cốt yếu của tối ưu hóa, kiểm tra nó, trừ khi bạn kiểm tra nó và chứng minh rằng nó làm việc bạn sẽ không biết.

Trong trường hợp của bạn những gì tôi muốn làm là, trước hết là refactor mã, đã nắm bắt được nó.

Nếu bạn đã kiểm tra đơn vị bạn là may mắn chỉ cần đi chức năng của chức năng và đặc biệt là đi và kiểm tra thường xuyên nhất gọi mã (sử dụng profiling để quan sát cuộc gọi và nơi là những nút thắt cổ chai). Nếu bạn không có xét nghiệm, hãy viết một số xét nghiệm cơ bản xác nhận đầu ra tổng thể trong một số điều kiện để bạn có thể đảm bảo rằng bạn không vi phạm bất cứ điều gì và miễn phí để thử nghiệm.

Answer 8

Giả sử mã cần tối ưu hóa, sau đó tôi sẽ sử dụng: 1.) Tối ưu hóa cách bộ đệm được xử lý được sử dụng - Tối ưu hóa bộ nhớ cache. Độ trễ của bộ nhớ cache là một khu vực lớn làm cho các chu kỳ CPU như bị hỏng. khoảng trong phạm vi 5-10% trên không Vì vậy, hãy sử dụng bộ đệm dữ liệu theo cách hiệu quả của bộ nhớ cache.

2.) Vòng quan trọng và chức năng chuyên sâu MCPS có thể được mã hóa bằng ngôn ngữ lắp ráp hoặc sử dụng nội tại mức thấp do trình biên dịch cung cấp cho mục tiêu h/w đó.

3.) Đọc/ghi từ bộ nhớ ngoài là chu kỳ tốn kém. giảm thiểu khả năng truy cập bộ nhớ ngoài càng nhiều càng tốt. Hoặc nếu bạn phải truy cập dữ liệu đó theo cách hiệu quả (nạp trước dữ liệu, truy cập song song DMA, vv ..)

Nói chung nếu bạn nhận được tối ưu hóa 20% (trường hợp tốt nhất) bằng cách làm theo các kỹ thuật tối ưu hóa, tôi sẽ nói điều đó đủ tốt và đủ tốt nhất mà không cần bất kỳ cấu trúc lại mã chính nào, thiết kế lại thuật toán. Sau đó nó trở thành lừa, phức tạp và tẻ nhạt.

-AD

Answer 9

Ngôn ngữ tôi đã thực hiện tối ưu hóa nhất để tính toán số trong C và C++ trên Linux. Tôi thấy rằng hồ sơ, trong khi hữu ích, có thể nghiêng kết quả thời gian chạy của bạn để giá rẻ, thường được gọi là hoạt động (như gia số lặp + C++). Vì vậy, lấy những người có một hạt muối. Về các chiến lược thực tế đã tăng tốc tốt là:

1. Sử dụng mảng số chứ không phải là mảng đối tượng. Ví dụ, C++ có kiểu dữ liệu "phức tạp". Các hoạt động trên một mảng này chậm hơn rất nhiều so với một hoạt động tương tự trên hai mảng phao. Điều này có thể được khái quát hóa để "sử dụng các loại máy" cho bất kỳ mã quan trọng nào về hiệu năng.
2. Viết mã để cho phép trình biên dịch hiệu quả hơn khi tối ưu hóa. Ví dụ, nếu bạn có một mảng kích thước cố định, hãy sử dụng các chỉ mục mảng để tự động hóa vector (một tính năng của trình biên dịch của Intel) có thể hoạt động.
3. Hướng dẫn SIMD có thể cung cấp tăng tốc tốt nếu sự cố của bạn phù hợp với loại miền mà chúng được thiết kế (nhân/chia phao hoặc tất cả cùng một lúc). Đây là các nội dung như MMX, SSE, SSE2, v.v.
4. Sử dụng bảng tra cứu có nội suy cho các hàm đắt tiền trong đó giá trị chính xác không quan trọng. Điều này không phải lúc nào cũng tốt, khi tra cứu dữ liệu trong bộ nhớ có thể tốn kém theo cách riêng của nó.

Tôi hy vọng sẽ mang lại cho bạn một số nguồn cảm hứng!

Answer 10

Tất cả câu trả lời hay.

Tôi sẽ tinh chỉnh phần "đo lường" của lời khuyên. Tôi thực hiện đo lường với mục đích định lượng bất kỳ cải tiến nào tôi có thể thực hiện. Tuy nhiên, để tìm kiếm những gì cần được khắc phục (và đó là một mục đích khác), tôi nhận được một số mẫu của ngăn xếp cuộc gọi, theo cách thủ công.

Giả sử, để đơn giản, chương trình cần 20 chu kỳ giga để chạy, khi cần. 10. Nếu tôi tạm dừng 10 lần ngẫu nhiên, thì trong 5 lần đó, nhiều hay ít, nó sẽ ở một trong những chu kỳ không cần thiết đó. Tôi có thể xem chu trình là cần thiết hay không bằng cách nhìn vào từng lớp của ngăn xếp cuộc gọi. Nếu bất kỳ lệnh gọi nào ở bất kỳ mức nào của ngăn xếp có thể được loại bỏ, thì chu kỳ là không cần thiết. Nếu một lệnh như vậy xuất hiện trên nhiều ngăn xếp, việc loại bỏ nó sẽ tăng tốc chương trình, bằng một lượng xấp xỉ tỷ lệ phần trăm của mẫu ngăn xếp mà nó đang bật.

Bất kỳ hướng dẫn nào xuất hiện trên nhiều ngăn xếp đều bị nghi ngờ - càng nhiều ngăn xếp thì càng nghi ngờ. Bây giờ, call _main có lẽ không phải là một tôi có thể xóa, nhưng
foo.cpp:96 call std::vector::iterator:++
nếu nó xuất hiện trên nhiều ngăn xếp, chắc chắn là trọng tâm của sự chú ý.

Có thể vì lý do kiểu dáng, không phải muốn để thay thế, nhưng người ta sẽ biết mức giá nào về hiệu suất đang được thanh toán cho lựa chọn đó.

Vì vậy, tối ưu hóa bao gồm xác định các nghi phạm và tìm cách thay thế hoặc loại bỏ chúng.

Phần khó khăn (và tôi đã làm điều này nhiều lần) là sự hiểu biết những gì là cần thiết và những gì không. Để làm được điều đó, bạn sẽ hiểu được cách thức và lý do tại sao mọi thứ được thực hiện trong chương trình đó, vì vậy nếu một số hoạt động là chu kỳ, bạn có thể biết cách thay thế nó một cách an toàn.

Một số chu kỳ lợn có thể đơn giản để sửa chữa, nhưng bạn sẽ nhanh chóng chạy với những cái mà bạn không biết cách thay thế an toàn. Để làm được điều đó, bạn cần phải quen thuộc hơn với mã.

Sẽ giúp ích nếu bạn có thể chọn bộ não của người đã làm việc trong chương trình.

Nếu không (giả sử mã là ~ 10^6 dòng, như tôi đã làm việc), bạn có thể tăng tốc khá dễ dàng, nhưng để vượt xa điều đó, có thể mất vài tháng để đến nơi bạn cảm thấy thoải mái thay đổi đáng kể.

Answer 11

Như nhiều người khác đã nêu, hồ sơ là bước đầu tiên của bạn.

Tôi sẽ thêm rằng tập trung vào cấu trúc dữ liệu và thuật toán là bước đầu tiên thường mang lại nhiều lợi nhuận hơn so với lặn thẳng vào tối ưu hóa vi mô.

Đối với một điều, trình biên dịch thường sẽ thực hiện rất nhiều thủ thuật tối ưu hóa cổ điển cho bạn dù sao (và thường tốt hơn bạn). Điều này đặc biệt đúng trong các ngôn ngữ hiện đại hơn như C# hơn là trong các ngôn ngữ C cũ hơn, ít ràng buộc hơn, C, vì trình biên dịch có nhiều kiến ​​thức về cấu trúc chương trình; tồi tệ hơn, gây nhầm lẫn mã của bạn bằng cách "tối ưu hóa" nó thực sự có thể làm cho nó khó hơn cho trình biên dịch để áp dụng riêng của nó, hiệu quả hơn, tối ưu hóa.

Chủ yếu là mặc dù, chỉ có nhiều phạm vi hơn để cải thiện mọi thứ khi bạn bắt đầu cải thiện hoạt động lớn của mình. Ví dụ, tìm kiếm một danh sách liên kết là O (n); có nghĩa là thời gian thực hiện để tìm kiếm nó tăng ở cùng tốc độ với kích thước của dữ liệu được lưu trữ trong đó. Tìm kiếm hashtable chỉ là O (1), vì vậy bạn có thể thêm nhiều dữ liệu hơn mà không tăng thời gian tìm kiếm (có những yếu tố khác khi chúng ta rời khỏi thế giới lý thuyết để điều này không hoàn toàn đúng, nhưng nó là đủ) thời gian).

Lộn xộn với vòng lặp của bạn để chúng chạy từ cao xuống thấp để mã được tạo có thể tiết kiệm một vài chu kỳ đồng hồ với JumpIfZero thay vì JumpIfLessThan có lẽ sẽ không có mức độ tác động tương tự!

Answer 12

Tốt chiến lược

Bên cạnh những luật cơ bản đề cập tối ưu hóa (đo lường, không tối ưu hóa nếu không cần thiết), và mặc dù là câu hỏi một cách rõ ràng cho hiệu quả, tôi luôn luôn Refactor mã như vậy trong suốt kiểm tra của tôi.

Thông thường, mã có hiệu suất kém cũng bị ghi nhận sai. Vì vậy, với việc tái cấu trúc, tôi đảm bảo rằng mã được tài liệu tốt hơn và dễ hiểu hơn. Đó là cơ sở để chắc chắn rằng tôi biết những gì tôi đang tối ưu hóa (như trong hầu hết các trường hợp, các yêu cầu cho đoạn mã đó cũng sẽ không hoàn toàn có sẵn).

Khi ngừng

Với một ứng dụng biểu diễn thực sự tồi tệ, bạn thường sẽ có một cành trong thời gian chạy được hiển thị cho một phương pháp duy nhất (hay tập hợp các phương pháp liên quan) trong hồ sơ của bạn, cho thấy một lỗi lập trình hay lỗ hổng thiết kế. Vì vậy, tôi thường dừng nếu thời gian chạy các phương thức lược tả được phân phối chủ yếu bằng nhau (hoặc nếu phần lớn các phương thức nút cổ chai được hiển thị là mã nền tảng, như các phương thức Sun Java). Nếu khách hàng của bạn yêu cầu tối ưu hóa thêm, bạn sẽ phải thiết kế lại các phần lớn hơn của ứng dụng thay vì tối ưu hóa mã hiện có.