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.
Dude. You are fabulous.
Super rare to talk with someone who is committed to a position, but can still listen.
Rarer still is someone that will go off and try the experiment to see for themselves. Very, very admirable.
Part of our communication problem, (and probably your frustration w the convo) was that I wasn't clear initially in explaining why it would be faster. My bad there. I was responding piecemeal.
Very cool that you went off and tried it.
(I have used that technique professionally to resurrect large, non performing systems that have outgrown their platforms...it's super effective... Now u can do that too ;-) )
I checked out your sub for resurrecting Dissenter...also very admirable. I will look at it when I get some time; I'll message u if I come up with anything helpful.
I enjoyed the conversation!
Cheers!
Looking at your code now....super cool.
(post is archived)