jlg@lanl.gov (Jim Giles) (10/20/90)
> [ machine language simulation is faster with pointers ] >> Oh, I see. This is the oft cited and easily discredited claim that >> *(p+i) is more efficient than a(i). > > No, it is not. > > QUESTION 6: Can you see the difference between *p and *(p+i)? Do you > realize that the first is more efficient than the second? Do you > understand now why pointers can be more efficient than arrays? Very interesting. But the example called for simulating a machine with intense use of random (simulated) addresses. In this case, nearly every use of the simulated memory will require an add of the base of the simulated memory to the 'random' offset. There will be no opportunity to precompute a pointer/index combination. In this case, pointers are _identical_ in performance to arrays (unless some spurious other pointers are present in the code - in which case, the compiler will have to assume the simulated memory _might_ be aliased and will produce _less_ efficient code than the array version). Now, let us suppose that what you intended to give was an example in which the pointer _can_ be precomputed and the used directly. (This would seem to have been your intent.) If _your_ invocation of '*p' is to be semantically similar to _my_ invocation of 'a(i)', then you will have to do two separate things: 1) you need to precompute 'i' (the index expression - whatever it is); 2) you need to add the base address of the array. The first of these things may be very difficult. The index expression may appear to have nonlinear dependencies on loop variables or it may be _computationally_ identical to another expression without this fact being readily apparent to the compiler, etc.. You may often have to take a hand yourself if you want to precompute the index expression. The second part is rather easier. _IF_ you can precompute the index, the compiler can easily add the base address at the same place as part of common expression elimination, constant folding, or loop invariant migration, etc.. The compiler can easily find the index computation because it _must_ be an ancestor of the array reference in the data flow graph. In short, if you can precompute the index, the compiler can easily make an array reference as efficient as your precomputed pointer. All the production quality compilers I've used for 23 years have been able to do this. In fact, many compilers are clever enough to figure out how to precompute the index of most references as well. Only the more esoteric cases (like, admittedly, some of the ones you've posted in other articles) need hand optimization. But, bear in mind: it is the _index_ calculation that may need the hand optimization - not the addition of the array base. >> >> > 4. Data compression and decompression by dictionary methods like LZW. >> >> Again, you'll have to explain why this necessitates pointers. The >> >> codes I've seen do this never use pointers. >> > Read the subject line. You lose about 30% with arrays---though sometimes >> > you have to use 2-byte integers rather than pointers to save memory. >> I'm still not clear on this. > [ various confused questions ] > > I have taken several LZ-type compressors and decompressors and converted > them to use pointers rather than arrays with integers. This saves some > indexing inside the inner loop, for an average 30% gain on various > machines. Please reread the answer to the previous question. If you can precompute a pointer then a modern compiler can precompute the corresponding array reference. Period. Now, I don't doubt that many _C_ compilers can't do this. My experience is that most C compilers aren't modern (or even close - we _are_ talking about stuff that quality compilers have been able to do since before most programmers were born). With a _modern_ (maybe even futuristic) compiler, the 'gain' you are talking about is on the other foot. Our file compression expert just did the same type of experiment you did. The array version was Fortran (of all things), the pointer version was C, the target machine was the Cray. The Fortran version was 25 _times_ faster than the C version. I don't think this had anything to do with the compiler qualities. It's just that Fortran 'knows' that distinct arrays aren't aliased, C doesn't. > Unfortunately, pointers use 4 bytes on most machines, when the > application at hand only requires 2 bytes. You often have to use 2-byte > integers rather than pointers to save memory. So you lose that 30%. Last I heard, array indices in most languages were allowed to be any integer or enumerated type. Hence, 2-byte indices will save the same space or memory bandwidth that casting pointers to 2-byte integers will. > I hope you understand what I'm saying now, so that you can ask sensible > questions. The primary question I asked was for an example of some high-level data type which could not be as efficiently implemented with the structures I've expounded as it is with pointers. Your primary answer (TeX), after a long refusal on your part to post any sample of the code, turns out _not_ to use pointers at all! Your second answer (stack reversal) depends upon some misunderstanding on your part about what aliased variables do. Your other answers are efficiency issues based on compilers whose technology is as old as the use of transistors in computers (that's about right: the 1604 was 1958, some Fortran compilers could do things like loop-invariant migration by 1960). Which one of us isn't being sensible? End of chapter 4 J. Giles