Blog cộng đồng về Công nghệ thông tin

• Bạn ngây thơ không nhận ra mình đã gặp vấn đề với n³. Có lẽ bạn gặp rắc rối, bởi vì bạn không biết rằng đã có một cản trở ở đây.
• Theo cách hàn lâm, bạn nhận ra mình đã gặp vấn đề với n³, và cho rằng điều này thật tồi tệ, bạn viết lại thuật toán của mình.
• Theo lối kỹ thuật, bạn nhận ra mình đã gặp vấn đề với n³, nhưng sau đó bạn trang bị công cụ cho hệ thống để phát hiện ra điều gì thật sự ảnh hưởng tới hệ thống của bạn.

Các duy nhất để tối ưu hóa đúng chính là theo lối kỹ thuật. Tôi tính toán quá trình xử lí, và trong thử nghiệm lớn nhất của mình, tôi nhận ra rằng n luôn luôn bằng 1, đôi khi bằng 2, hiếm khi bằng 3, và bằng 4 một lần duy nhất. Điều này quá nhỏ để trở thành vấn đề. Độ phức tạp của thuật toán là n³, nhưng với n nhỏ như vậy, nên chúng ta không cần phải viết lại chương trình. Việc viết lại đoạn chương trình này hết sức phức tạp, có thể kéo dài cả dự án một vài tuần, và sử dụng hết nhiều con trỏ trong mỗi nốt của toàn bộ cây của một hệ thống địa chỉ đã tương đối bị bó hẹp.

So I wrote a little hook in the allocator that counted the number of times it was called. It turns out it was called over 4,000,000 times. No call took longer than the minimum measurement interval of 10µs (approximately ten instructions on our 1-MIPS machine), but 40,000,000 microseconds is 40 seconds. Actually, it was more than that because there were 4,000,000 free operations as well, which were even faster, but still the resulting time was more than 50% of the total execution time.

Why did this happen? Because, unknown to the programmers, a critical function they were calling in the inner loop of several algorithms would actually allocate a 5-to-10 byte working buffer, do its thing, and release it. When we changed this to be a 10-byte stack local, the time spent in the storage allocator dropped to about 3% of the total program time.

Without the data, we would not have known why the allocator accounted for so much time. PC-sampling performance tools are a very weak class of tools and their results are intrinsically suspect. See my article "Profiling for Performance", in Dr. Dobb's Journal (18,1) January, 1993, pp.80-87.

A classic blunder in optimization was committed some years ago by one of the major software vendors. We had their first interactive timesharing system, and it was a "learning experience" in a variety of ways. One such experience was that of the FORTRAN compiler group. Now any compiler writer knows that the larger the hash table you use for a symbol table, the better your performance on lookup will be. When you are writing a multipass compiler in a 32K mainframe, you end up using a relatively small symbol table, but you create a really, really good hash algorithm so that the probability of a hash collision is reduced (unlike a binary seach, which is log n, a good hash table has constant performance, up to a certain density, so as long as you keep the density below this threshold you might expect that you will typically have an order 1 or 2 cost to enter or lookup a symbol, on the average. A perfect hash table (which is usually precomputed for constant symbols), has a constant performance between 1.0 and 1.3 or thereabouts; if it gets to 1.5 you rework the hashing to get it lower).

So anyway, this compiler group discovers that they no longer have 32K, or 128K, or 512K. Instead, they now have a 4GB virtual address space. "Hey, let's use a really big hash table!" you can hear them saying, "Like, how about 1 MB table?" So they did. But they also had a very sophisticated compiler technology designed for small and relatively dense hash tables. So the result was that the symbols were fairly uniformly distributed over the 256 4K pages in that 1MB, which meant that every symbol access caused a page fault. The compiler was a dog. When they finally went back to a 64K symbol table, they found that although the algorithm had poorer "absolute" performance from a purely algorithmic viewpoint (taking many more instructions to look up a symbol), because it did not cause nearly as many page faults, it ran over an order of magnitude faster. So third-order effects do matter.

Also, beware of C. No, not the speed of light. When we talk about performance, the algorithmic performance for n is expressed as a function C × f(n). Thus an n² algorithm is formally C × n², meaning that the performance is a constant multiple of the square of the number of elements being considered. We shorten this to O(n²), meaning "order of n²", and in common parlance just drop the "order of" designation. But never forget the C is there. Some years ago, I was doing a project that produced summary set of listings, sorted in a variety of ways. In the first attempt (this was in the days before C and qsort) I just did an ordinary bubble sort, an O(n²) algorithm. After initial testing, I fed it some live data. Ten minutes later, after it had printed the console message "Starting reports", it had not yet produced any reports. A series of probes showed that most of the time was in the sort routine. OK, I was done in by my laziness. So I pulled out my trusty heapsort (n log n) sort and spent an hour modifying it to work in my application (remember, I said qsort did not yet exist). Having solved the problem, I started running it again. Seven minutes into the report phase, nothing had yet appeared. Some probes revealed something significant: it was spending most of its time in the equivalent of strcmp, comparing the strings. While I'd fixed the O issue, I had serious neglected the C issue. So what I did was do one sort of the composite symbol table, all of the names, and then assigning an integer to each symbol structure. Thereafter, when I had to sort a substructure, I just did an integer sort on its ordinal position. This reduced C to the point where less than 30 seconds were required to do the entire report phase. A second-order effect, but a significant one.

So algorithmic performance, particularly paging performance, can matter. Unfortunately, we have neither the proper tools for measuring paging hits nor for reorganizing code to minimize paging of code pages.

Some performance tools measure the total time spent in user space, and treat kernel time as free. This can mask the impact the application has on the kernel time. For example, a few years ago we were measuring the performance of a program whose performance was exceptionally poor. No "hotspot" showed up in terms of program time wasted. However, at one point I was looking at the trace data and noticed that the input routine was called about a million times, which is not surprising when you are reading a megabyte of data, but something seemed odd to me. I looked. Each time it was called, it called the kernel to read a single byte of the file! I changed it to read 8K bytes and unpack the buffer itself, and got a factor of 30 performance improvement! Note the lesson here: kernel time matters, and kernel transitions matter. It is not accidental that the GDI in NT 4.0 is no longer a user-level process but integrated into the kernel. The kernel transitions dominated the performance.

So what to optimize is easy: those parts of the program that are consuming the time. But local optimizations that ignore global performance issues are meaningless. And first-order effects (total time spent in the allocator, for example), may not be the dominant effects. Measure, measure, measure.

.

Đừng thực hiện việc tối ưu mà không có ý nghĩa gì. Ví dụ, người ta cố gắng tối ưu giao diện GUI. Hard wired constants, distributed enabling, cute algorithms. Kết quả lại là một cái gì đó rất khó phát triển, khó debug, và tuyệt đối không thể bão dưỡng được.

Tại sao lại không có ý nghĩa về mặt hiệu quả khi bạn update menus hay controls? Hãy nhìn vào nhân tố con người. Con chuột của máy tính được giữ cách tai khoảng tầm 2 feet, tốc độ âm thanh thì đạt khoảng 1100 ft/sec. Nghĩa là âm thanh của việc nhấp chuột hay gõ phím mất khoảng 2ms để đến được tai. Dây thần kinh từ đầu ngón tay đến não bộ ở người lớn dài khoảng chừng 3 feet. Tốc độ truyền xung thần kinh xấp xỉ 300 ft/sec, Nghĩa là việc cảm nhận tiếng nhấp chuột hay gõ phím mất chừng 10ms để đến được não. Sự trì hoãn giác quan trong não bộ có thể thêm 50 đến 250ms hoặc hơn.

Pentium có thể thực hiện bao nhiêu lệnh trong 2ms, 10ms, hay 100ms? Trong 2ms, với một máy tính 500MHz tức là 1,000,000 xung đồng hồ, bạn có thể thực hiện được rất nhiều lệnh. Thậm chí với một máy Pentium 120MHz cũ kĩ cũng không có sự trì hoãn đáng kể nào trong việc quản lý các controls.

Điều này đã không ngăn cản Microsoft khỏi việc can thiệp hoàn toàn vào C++ object model trên trình điều khiển thông điệp; nếu bạn gọi CWnd::OnWhatever(...), thay vì phải gọi DefWindowProc với các tham số bạn đã cung cấp, chúng sử dụng lại các tham số của thông điệp cuối để gọi ::DefWindowProc. Mục tiêu là để "giảm kích thước của MFC runtime", như thể hơn trăm lệnh trong một DLL đồ sộ sẽ có ý nghĩa! Thậm chí tôi có thể đoán làm thế nào để get CWnd::OnAnything to inline-expand to a call on DefWindowProc.

Optimization is your enemy

Rất nhiều năm trước đây, như đã nói sơ trong phần giới thiệu, tôi làm việc với một hệ thống multiprocessor lớn (16-processor). Chúng tôi đã sử dụng minicomputers custom-modified PDP-11 khá là chậm. Chúng tôi đã lập trình trên đó bằng Bliss-11 – tôi có thể nói là vẫn giữ kỉ lục thế giới về trình biên dịch chặt chẽ nhất (mặc dù tôi cũng có thấy những sự tối ưu hóa khá ấn tượng trong Microsoft C/C++). Sau khi thực hiện vài phép đo thực thi, chúng tôi xác định rằng giải thuật phân trang đã gây ra “bottleneck”. Vì vậy giả thiết đầu tiên của chúng tôi là giải thuật phân trang đó bị sai. Chúng tôi đã kiểm tra mã và nhân viên phụ trách giải thuật phân trang đó đã viết lại nó, lấy dữ liệu thực thi của chúng tôi vào và đã có một giải thuật phân trang mới nhanh hơn nhiều, mọi việc tiến hành chỉ trong vòng 1 tuần.

Meanwhile, up at MIT, MULTICS was still running. Họ đã tìm ra một vấn đề nghiêm trọng đối với hệ thống phân trang. Bởi vì nó được viết bằng một ngôn ngữ giống như PL/1, là EPL, giả thiết rằng vì nó được viết bởi ngôn ngữ bậc cao nên mã gần như cực thuận, vì vậy họ đã cố gắng bỏ sức ra để viết lại giải thuật phân trang bằng hợp ngữ. Một năm sau, phần mã đó hoạt động và được đưa vào sử dụng. Hiệu suất giảm 5%. Qua kiểm tra, người ta phát hiện thuật toán cơ bản đã sai. Họ lấy mã EPL, viết lại và có được thuật toán hoạt động tốt hơn, mọi việc tiến hành trong vòng vài tuần. Bài học rút ra là đừng tối ưu hóa những gì không có trục trặc. Chỉ sau khi hiểu kĩ vấn đề có trục trặc thì mới tối ưu hóa. Nếu không sự tối ưu sẽ gây lãng phí thời gian và có thể còn làm cho hiệu suất giảm đi.

In the Bliss compiler, the 'register' attribute on a variable said to the compiler "You will assign this variable to a register". In C, it means "I'd like you to assign this variable to a register". Many programmers decided that they should put certain variables in registers to get better code. But the Bliss compiler was very good; it had a very sophisticated register allocation system, and in the absence of direction from the programmer felt free to assign a variable to a register if that produced the best code. Explicitly assigning a variable to a register meant that the register was not available for common subexpressions, particularly those subexpressions implicit in data structure access. After a fair amount of experiments, we determined that almost invariably adding 'register' attributes to declarations produced significantly worse code than letting the compiler do the assignment. For inner-loop code, many hours of effort would usually result in a small improvement in performance, but it was generally understood by the programmers that unless you studied the generated machine code and did a number of calibrated experiments, any attempts at optimization would make the code worse.

If you've heard of the SPECmark performance, you may also be aware of how they are gamed. In particular, IBM wrote a program that took a FORTRAN program as input, such as the SPEC matrix-multiply benchmark, and produced another FORTRAN program as output, but one which was optimized for the cache architecture of the machine it would run on. A small number of parameters described all the cache strategies of each of the models of the RISC 6000 product line. The "optimized" original FORTRAN program performed on one machine at 45 SPECmarks. After being transformed, it performed on the same machine at over 900 SPECmarks. That's a factor of 20 performance improvement based solely on fourth-order effects, cache line hits. If you're doing image processing, particularly of large images, an awareness of cache issues (even relatively machine-independent) can buy you an order of magnitude performance.

A naive approach, optimizing at the code-line level, is not nearly as effective as higher-order optimizations. Paging optimizations, cache line optimizations, and memory allocation optimizations can often have vastly more significant effects than code-line optimization. Algorithmic optimizations are the next best bet, particularly if your problem is not amenable to paging/cache optimizations. Only after all these have been done, and, of course, you have measured everything in sight, does it make sense to start doing line-level optimizations. And if your problem domain demands it, it can even make sense to recode the inner loops, particularly of such algorithms as convolution algorithms and DSP algorithms, in assembly code, most often to take advantage of the instructions such as for MMX and streaming media.

Perhaps the best example of pure programmer stupidity in "optimizing" code occurred when I was porting a large library we used for our research project. Think of it as a 16-bit-to-32-bit port (it was an 18-bit-to-36-bit port, and the language wasn't C, but the details don't matter--you can write ghastly code in any language, and I've seen C programmers do things just as badly). The port mostly worked, but we had a really strange problem that showed up only under some rare conditions, but which crashed the program using the library. I started looking. The heap was damaged. When I found how the heap was being damaged, it was being damaged via a bad pointer which allowed a store into a random place in the heap. OK, how did that pointer get bad? Four levels of storage damage down, and after 12 solid hours of debugging, I found the real culprit. By why did it fail? Another 5 hours, and I found that the programmer who wrote the constructor code for the data structure had a struct-equivalent something like {char * p1; char * p2;} where the pointers had been 16-bit, and we now used 32-bit pointers. In looking at the initialization code, instead of seeing something like something->p1 = NULL; something->p2= NULL;, I found the moral equivalent of (*(DWORD*)&something.p1) = 0! When I confronted the programmer, he justified it by explaining that he was now able to zero out two pointers with only a single doubleword store instruction (it wasn't an x86 computer, but a mainframe), and wasn't that a clever optimization? Of course, when the pointers became 32-bit pointers, this optimization only zeroed one of the two pointers, leaving the other either NULL (most of the time), or, occasionally, pointing into the heap in an eventually destructive manner. I pointed out that this optimization happened once, at object creation time; the average application that used our library created perhaps six of these objects, and that according to the CPU data of the day before I'd spent not only 17 hours of my time but 6 hours of CPU time, and that if we fixed the bug and ran the formerly-failing program continuously, starting it up instantly after it finished, for fourteen years, the time saved by his clever hack would just about break even with the CPU time required to find and fix this piece of gratuitous nonsense. Several years later he was still doing tricks like this; some people never learn.

Summary

Optimization matters only when it matters. When it matters, it matters a lot, but until you know that it matters, don't waste a lot of time doing it. Even if you know it matters, you need to know where it matters. Without performance data, you won't know what to optimize, and you'll probably optimize the wrong thing.

The result will be obscure, hard to write, hard to debug, and hard to maintain code that doesn't solve your problem. Thus it has the dual disadvantage of (a) increasing software development and software maintenance costs, and (b) having no performance effect at all.

Hard to beat that combination! Now do you understand what I meant in the title?