[theora-dev] [OT] Just saying hi!

Christoph Lampert chl at math.uni-bonn.de
Fri Feb 28 00:14:23 PST 2003

Hi again, 

On Thu, 27 Feb 2003, Mike Melanson wrote:
> 	As for IDCT stuff, would it be reasonable to prefetch coeff. data
> for block n+1 before transforming block n? For the DC's SH-4:
>   get address of next block
>   prefetch addr+0   ; prefetching gets 32-byte blocks
>   prefetch addr+32  ; there are 8x8 coeffs * 2 bytes/coeff = 128 bytes
>   prefetch addr+64
>   prefetch addr+96
>   idct(current block)

Yes, I know the thread is "closed", but I just found this nice description
of a guy who tried to optmize his "simple" binary search to reduce memory
latency using prefetches. In this case it won't happen, but it shows how
careful you have to be: 

(quotation from http://folk.uio.no/jsundet/judy-notat.pdf)

5 But?! 

We're in for a surprise. Running prospect again we note that we have
equally many cache-misses as before! The program actually runs slower
because of the added complexity. We fiddle a bit with the prefetch
distance, to no avail. Have we completely misunderstood how prefetching
works? Did we compile the wrong file? Did we run the wrong program? Is it
just a very bad Thursday? 
Inserting debugging fprintf s of which addresses we prefetch shows that we
re prefetching the right ones. 
Examination of the assembly code reveals that our nice high-tech
optimizing compiler has figured out that it s faster to execute some loops
backwards. It does so because it doesn t understand the temporal
dependency between our prefetching and the rest of the loop body. The
compiled code counts i downwards. We 'prefetch' addresses which we
accessed two iterations ago! Effectively, we don t do prefetching at all,
we do, eh, postfetching. (Of course, with fprintf s present, the compiler
didn t reverse the loop. This is an excellent example of a Heisenbug; it
changes or disappears whenever you inspect it. And, by the way, it didn t
actually happen in this particular program, but it has happened to me in a
similar program.)


<p>--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'theora-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.

More information about the Theora-dev mailing list