CODEWITHSUNDEEP
linuxperformanceassemblyx86-64
randomusername
randomusername

Reputation: 8097

Why does my Assembly code run in linear time when it should run in O(N*sqrt(N)) time?

So I was writing a prime number generator in assembly (to learn the language) and when I started benchmarking the program, I found that it was running in linear time rather than the expected O(N * sqrt(N)) time.

Why is this happening?

I went through and commented the code and put it up on github over here: https://github.com/kcolford/assembly_primes. It should be fairly readable, but if anyone wants me to comment it more thoroughly (like with explanations of each instruction) I'm happy to do that, I just didn't think that it would be necessary.

The assembler and linker that I'm using are the ones found in the GNU binutils and it is written for the x86_64 architecture running the linux kernel.

Upvotes: 1

Views: 236

Answers (1)

TypeIA
TypeIA

Reputation: 17248

Big-O complexity is tricky to measure experimentally. Like Phil Perry suggested, there are often linear terms (or other terms) that overwhelm the primary O() term for "small" runs. These extra terms, hidden in big-O notation, always exist in real code and are necessary when analyzing the actual run time of something.

When I measure your sample code on my test machine, I get a clearly nonlinear relationship. I can't post a plot because of low reputation, but here's a table:

N (= n^2)     Time
  1000000    0.386
  4000000    1.846
  9000000    4.673
 16000000    9.275
 25000000   15.850
 36000000   24.690
 49000000   35.850
 64000000   49.887
 81000000   66.509
100000000   86.855

Also, I didn't thoroughly look through your exact implementation of the algorithm, but the Sieve of Eratosthenes is O(n log log n), not O(n sqrt(n)).

Also note that I/O is usually very expensive compared to number crunching. In your case, on my test machine, at n = 5000, the I/O accounts for almost 30% of the total run time. This would be a significant linear term in the run time analysis. You'd have to thoroughly analyze everything else the code is doing to figure out what else is affecting the measurements.

Upvotes: 2

Related Questions