[ time to re-share my Dr. Nicely story ]

Dr. Nicely caused quite a bit of excitement at Intel. I was on the p6 architecture team when he discovered the FDIV bug. Our FPU was formally verified and didn't have the same bug. To be nice to Dr Nicely we sent him a pre-release p6 development system to test with his program to demonstrate that his bug was fixed. He was working on a prime number sieve program and came back reporting that the p6 ran at 1/2 the speed of a Pentium for his code. Wow, another blackeye/firestorm caused by Dr. Nicely. He had too much of an audience for him to report to the world this new processor was slower.

So I got to spend a lot of time learning how to sieve works and what is happening. For the most part, it allocates a huge array in memory with each byte representing a number. You walk the array with a stride of known primes setting bytes and whatever is left must be prime. ie. every 3 is not prime, every 5 is not prime, every 7...

So in the steady state, you are writing a single byte to a cache line without reading anything. And every write hits a different cache line.

Now p6 had a write-allocate cache, but the Pentium would only allocate on read, so on the Pentium a write that misses the cache would become a write to memory. On the p6 that write would need to load the cache line from memory into the cache and then the line in the cache was modified. And since every line in the cache was also modified we had to flush some other cache line first to make room. So every 1-byte write would become a 32-byte write to memory followed by a 32-byte read from memory.

Normally write-allocate is a good thing, but in this case, it was a killer. We were stumped.

Then the magic observation: 99% of these writes were marking a space that was already marked. When you get up to walking by large strides most of those were already covered by one of the smaller factors.

So if you change the code from:

     array[N] = 1

to:

     if (!array[N]) array[N] = 1

Now suddenly we are doing a read first, and after that read we skip the write so the data in the cache doesn't become modified and can be discarded in the future. Also, the p6 was a super-scalar machine that ran multiple iterations of this loop in parallel and could have multiple reads going to memory at the same time. With that small tweak, the program got 4X faster and we went from being 1/2X the speed of a Pentium to being twice the speed. And this was at the same clock frequency. The test hardware ran 100Mhz, we released at 200Mhz and went up from there.