Obviously I do. You're completely missing the point.
Ask yourself this question:
How do I get a fibonacci number to load into a register?
i.e. list all the steps, at an assembler level, needed to calculate a fibonacci number before you can load it into the register.
Compare that list of steps to a lookup of a resident, indexed, hard coded table whicj already contains the number.
During initialization, you load 1 and 1 as immediates into two registers to represent the last two Fibonacci values.
Then, you'd just do an ADD, storing the result in the first register, then SUB to subtract the two, ADD to add that result to the index storing the memory location of the current word (also in a register). Then a check to see if index > end. Then when you do the next value, you just use the second register holding the Fibonacci values as the first and repeat.
Pulling data from memory, regardless if in a cache or not just to eliminate that one ADD operation is going to be slower. Or are you saying that pulling data from a cache in one SUB operation is the same speed or faster than two ops using registers? I
Yes.
Every instruction is a CPU cycle. On a single processor 1 GHz chip (for example) ea CPU instruction takes 1 nanosecond. 2 instructions takes 2 nanoseconds, 4 takes 4 nanoseconds , etc
(omit debate about your pseudocode and how many actual instructions, and registers u need to compute fibonacci #)
An L1 cache read takes ~1 nanoseconds
All of this goes out the window if the cache gets paged.....see previous comments explaining system level calls to prevent that.
I decided to try an test this, so I can up with a program. The result is that your right, your method seems about 2x quicker. I wrote your algorithm in c along with my algorithm in c and in asm. I couldn't get my asm code faster than the speed of c implementation, so I didn't bother writing your algorithm in asm. Also, yours was the fastest overall even when written only in c.
Here are the results:
$ gcc -o comp comp.c #gh $ ./comp compute_fib Time measured: 1.312 seconds. compute_fib_table Time measured: 1.450 seconds. compute_fib_asm Time measured: 1.704 seconds. $ gcc -O3 -o comp comp.c #gh $ ./comp compute_fib Time measured: 1.314 seconds. compute_fib_table Time measured: 0.696 seconds. compute_fib_asm Time measured: 1.723 seconds.
Here is the code if you want. Don't expect much, it's the first time I used gcc inline assembly: https://pastebin.com/1VEjESdG
Sorry about getting angry before, I was in a rush and in a bad mood due to other things.
(post is archived)