5 ms·

Creating a Fibonacci Generator in Assembly

50 points by willvk 8y ago

emilfihlman 8y ago
movl $1, %eax movl $1 %eax copy 0 into register eax movl $0, %ebx movl $0 %ebx copy 1 into register ebx Surely the explanations are flipped?
- willvk 8y ago
  Yep. It's a typo. Thanks for the feedback.
pq0ak2nnd 8y ago
every programmer needs to do this at some point in their life. it is too easy to take take modern languages for granted. but i'm a little disappointed that you dogged `make`. i think the programming landscape would be a lot more effective if people took the time to learn about what already exists (not just make but autoconf/automake/configure) instead of reinventing the wheel every three years.
- willvk 8y ago
  Thanks for reading and thanks for the feedback. It wasn't my intention to 'dog' make, I just felt that for an entry level post that introducing the make syntax may detract from the focus on assembly (although make is an integral part of gas asm) and add extra complexity and length to the (already very long) article. Anything more complex, such as multiple .s files would definitely warrant a description of make. Thanks again.
userbinator 8y ago
As someone with considerable experience in using x86 Asm (over a decade), it's always nice to see more articles on it, but there are a few things I found odd about this one. The basis of the algorithm to use was decided to be a space-optimised method using a dynamic programming approach. This effectively means using an array on the stack to hold our values while giving O(n) time and space complexity. That isn't "space-optimised" at all --- when I think of a Fibonacci example I think of O(1) space. Unless it was chosen specifically to demonstrate array indexing (in which case it would be better to use an algorithm that actually requires an array, like sorting), the choice of algorithm is unusual. The same applies to finding the length of argv[1] before doing the equivalent of an atoi() on it --- if you're going to read the bytes of the string through, might as well accumulate and convert, and oddly enough the length appears to be unused too. The unexplained and useless nop is also puzzling. Why is it there? What is it for? The same goes for the many other instructions which aren't actually contributing to the calculation, and initially made me think it was compiler output when I first glanced over the code. Writing a program that performs the given task is relatively straightforward even in Asm, but your solution is unnecessarily complex. Making things easier to understand using function calls I consider this a premature abstraction. A comment or even label will do just fine to delimit the blocks of functionality, as your "functions" are called only once. Your task has 3 parts [basically atoi(), fib(), itoa()+output] so you will have 3 blocks of code. It cannot be any simpler than that. Better is "making things easier to understand by avoiding unnecessary code". Here is how I would write the first 2 blocks; I wrote this without testing at all so it could have errors, but it is really quite simple: mov esi, [esp+8] ; get argv[1] xor eax, eax ; clear the upper bits xor ecx, ecx ; will hold converted value atoiloop: lodsb ; get a character cmp al, '0' jb fibinit cmp al, '9' ja fibinit imul ecx, ecx, 10 lea ecx, [ecx+eax-'0'] jmps atoiloop fibinit: jecxz invalid ; can't do fib(0) xor eax, eax inc eax ; eax = 1 cdq ; edx = 0 fibloop: xadd eax, edx loop fibloop ; now eax and edx will contain fib(n) and fib(n-1) Observe that I chose the specific registers for a reason: esi/al will be used by lodsb, ecx by the looping instructions, and edx for xadd. This is one of the things that compilers are not very good at, and also why carefully written Asm can easily beat them. If you want to learn more Asm I recommend any assembler besides GAS, and looking at some examples from advanced users: http://www.hugi.scene.org/compo/compoold.htm http://www.hugi.scene.org/compo/compoold.htm The demoscene in its smaller-size competitions has lots of particularly knowledgeable users too.
- willvk 8y ago
  That's some awesome feedback. Thanks so much. As I'm teaching myself asm I'm learning as I go. I'll incorporate it all into a revised version soon.
  - exikyut 8y ago
    I mentioned this elsewhere, but just to make sure you see it, I also stumbled on https://codegolf.stackexchange.com/a/135618/15675 https://codegolf.stackexchange.com/a/135618/15675, which may also be useful.
    - willvk 8y ago
      Thanks for that. Yep, I've seen that too.
  - pjc50 8y ago
    Your article is actually pretty handy in terms of setting up the "workflow" for compilation and debugging from scratch. It's the sort of thing genuine beginners need to avoid getting tripped up.
    - willvk 8y ago
      Thank-you for your kind words about the post. That was what I was trying to do with it - to break down some of the nebulous fear that beginners have with assembly. Cheers!
  - pkilgore 8y ago
    Quick suggestion to massively improve your writing for general consumption: strip out the passive voice where not absolutely necessary, e.g., "was decided". Not only is the active voice "I/we decided" generally much more interesting to read, it usually forces you to adopt a sentence structure with fewer words (easier to read). Your writing later in the article is much more engaging as you start to use the active voice. And thanks for the article, I love reading interesting excursions in low level programming!
exikyut 8y ago
FWIW, the article mentions a possible followup "using ... MMX, XMM or SIMD". (To clarify, XMM is SSE.) SIMD is noted last as though it's the newest development, when that would arguably be is at least AVX, and AVX-512 to be specific.
- willvk 8y ago
  Thanks for that. I didn't intend for it to be a chronological list but will add AVX to it. Cheers.
  - exikyut 8y ago
    Oh, okay, my bad! And wow, fibonacci using hand-rolled AVX :) that would definitely be a sight to see. ...although, I should explicitly point out, AVX is a set of vector streaming/processing instructions. Fibonacci is inherently a single-step operation, with no lookahead. Okay, so I googled "fibonacci avx". The results were quite a mess but some careful wading found me http://www.insideloop.io/blog/2014/10/14/arrays-part-iii-vectorization/ http://www.insideloop.io/blog/2014/10/14/arrays-part-iii-vec..., which states: "A a consequence, the following code that computes the sequence of Fibonacci can’t get vectorized." So, forgive my own (bullish!) naivete. AVX, and _possibly_ SIMD, SSE, etc _may not_ be applicable to/usable for Fibonacci computation.
    - userbinator 8y ago
      Vector instructions are certainly usable for scalar computation, although it doesn't make much sense --- you basically just use one piece of one vector and throw away all the other results. Fibonacci is a toy example but illustrates where the vector instructions do become useful: if you want to compute the n'th term of various Fibonacci-like sequences with different starting conditions but the same recurrence, then you could do them in parallel using those instructions.
    - leghifla 8y ago
      Unrolling the computation of the series, it is possible to compute f(n) using only f(n-4) and f(n-8): f(n) = 7*f(n-4)-f(n-8) So, using 4-vector operations, you can compute 4 numbers in one step.
emersonrsantos 8y ago
In Forth language would be: : fib 2dup + ; 2dup word duplicates n and n-1 elements and put it on the top of the stack. + word takes n and n-1 elements from the stack and sum them. The result goes on top of the stack. Just start with 1 and 1 at the top of stack.
- willvk 8y ago
  That's some very concise code golf! It would be interesting in seeing how Forth compiles this under the hood.
  - pjc50 8y ago
    Normally Forth is interpreted. Compiled Forth code is unlikely to look particularly clean or elegant. (If you like languages with a very high density of functionality to symbol count, you should look at APL and its successor J)
saagarjha 8y ago
I think you might be missing the NULL that terminates argv in your stack diagram.
- willvk 8y ago
  Thanks for that. I've amended the diagram accordingly.
sdfsdfsdff 8y ago
It's also a problem in 7 Billion Humans or Human Resource Machine (I forgot which - they are both great anyway), fun programming games that also use a kind of assembly language.

50 points by willvk 8y ago

movl $1, %eax movl $1 %eax copy 0 into register eax movl $0, %ebx movl $0 %ebx copy 1 into register ebx Surely the explanations are flipped?

willvk 8y ago
Yep. It's a typo. Thanks for the feedback.

pq0ak2nnd 8y ago

every programmer needs to do this at some point in their life. it is too easy to take take modern languages for granted. but i'm a little disappointed that you dogged `make`. i think the programming landscape would be a lot more effective if people took the time to learn about what already exists (not just make but autoconf/automake/configure) instead of reinventing the wheel every three years.

willvk 8y ago
Thanks for reading and thanks for the feedback. It wasn't my intention to 'dog' make, I just felt that for an entry level post that introducing the make syntax may detract from the focus on assembly (although make is an integral part of gas asm) and add extra complexity and length to the (already very long) article. Anything more complex, such as multiple .s files would definitely warrant a description of make. Thanks again.

userbinator 8y ago

As someone with considerable experience in using x86 Asm (over a decade), it's always nice to see more articles on it, but there are a few things I found odd about this one. The basis of the algorithm to use was decided to be a space-optimised method using a dynamic programming approach. This effectively means using an array on the stack to hold our values while giving O(n) time and space complexity. That isn't "space-optimised" at all --- when I think of a Fibonacci example I think of O(1) space. Unless it was chosen specifically to demonstrate array indexing (in which case it would be better to use an algorithm that actually requires an array, like sorting), the choice of algorithm is unusual. The same applies to finding the length of argv[1] before doing the equivalent of an atoi() on it --- if you're going to read the bytes of the string through, might as well accumulate and convert, and oddly enough the length appears to be unused too. The unexplained and useless nop is also puzzling. Why is it there? What is it for? The same goes for the many other instructions which aren't actually contributing to the calculation, and initially made me think it was compiler output when I first glanced over the code. Writing a program that performs the given task is relatively straightforward even in Asm, but your solution is unnecessarily complex. Making things easier to understand using function calls I consider this a premature abstraction. A comment or even label will do just fine to delimit the blocks of functionality, as your "functions" are called only once. Your task has 3 parts [basically atoi(), fib(), itoa()+output] so you will have 3 blocks of code. It cannot be any simpler than that. Better is "making things easier to understand by avoiding unnecessary code". Here is how I would write the first 2 blocks; I wrote this without testing at all so it could have errors, but it is really quite simple: mov esi, [esp+8] ; get argv[1] xor eax, eax ; clear the upper bits xor ecx, ecx ; will hold converted value atoiloop: lodsb ; get a character cmp al, '0' jb fibinit cmp al, '9' ja fibinit imul ecx, ecx, 10 lea ecx, [ecx+eax-'0'] jmps atoiloop fibinit: jecxz invalid ; can't do fib(0) xor eax, eax inc eax ; eax = 1 cdq ; edx = 0 fibloop: xadd eax, edx loop fibloop ; now eax and edx will contain fib(n) and fib(n-1) Observe that I chose the specific registers for a reason: esi/al will be used by lodsb, ecx by the looping instructions, and edx for xadd. This is one of the things that compilers are not very good at, and also why carefully written Asm can easily beat them. If you want to learn more Asm I recommend any assembler besides GAS, and looking at some examples from advanced users: http://www.hugi.scene.org/compo/compoold.htm http://www.hugi.scene.org/compo/compoold.htm The demoscene in its smaller-size competitions has lots of particularly knowledgeable users too.

willvk 8y ago
That's some awesome feedback. Thanks so much. As I'm teaching myself asm I'm learning as I go. I'll incorporate it all into a revised version soon.
- exikyut 8y ago
  I mentioned this elsewhere, but just to make sure you see it, I also stumbled on https://codegolf.stackexchange.com/a/135618/15675 https://codegolf.stackexchange.com/a/135618/15675, which may also be useful.
  - willvk 8y ago
    Thanks for that. Yep, I've seen that too.
- pjc50 8y ago
  Your article is actually pretty handy in terms of setting up the "workflow" for compilation and debugging from scratch. It's the sort of thing genuine beginners need to avoid getting tripped up.
  - willvk 8y ago
    Thank-you for your kind words about the post. That was what I was trying to do with it - to break down some of the nebulous fear that beginners have with assembly. Cheers!
- pkilgore 8y ago
  Quick suggestion to massively improve your writing for general consumption: strip out the passive voice where not absolutely necessary, e.g., "was decided". Not only is the active voice "I/we decided" generally much more interesting to read, it usually forces you to adopt a sentence structure with fewer words (easier to read). Your writing later in the article is much more engaging as you start to use the active voice. And thanks for the article, I love reading interesting excursions in low level programming!

exikyut 8y ago

FWIW, the article mentions a possible followup "using ... MMX, XMM or SIMD". (To clarify, XMM is SSE.) SIMD is noted last as though it's the newest development, when that would arguably be is at least AVX, and AVX-512 to be specific.

willvk 8y ago
Thanks for that. I didn't intend for it to be a chronological list but will add AVX to it. Cheers.
- exikyut 8y ago
  Oh, okay, my bad! And wow, fibonacci using hand-rolled AVX :) that would definitely be a sight to see. ...although, I should explicitly point out, AVX is a set of vector streaming/processing instructions. Fibonacci is inherently a single-step operation, with no lookahead. Okay, so I googled "fibonacci avx". The results were quite a mess but some careful wading found me http://www.insideloop.io/blog/2014/10/14/arrays-part-iii-vectorization/ http://www.insideloop.io/blog/2014/10/14/arrays-part-iii-vec..., which states: "A a consequence, the following code that computes the sequence of Fibonacci can’t get vectorized." So, forgive my own (bullish!) naivete. AVX, and _possibly_ SIMD, SSE, etc _may not_ be applicable to/usable for Fibonacci computation.
  - userbinator 8y ago
    Vector instructions are certainly usable for scalar computation, although it doesn't make much sense --- you basically just use one piece of one vector and throw away all the other results. Fibonacci is a toy example but illustrates where the vector instructions do become useful: if you want to compute the n'th term of various Fibonacci-like sequences with different starting conditions but the same recurrence, then you could do them in parallel using those instructions.
  - leghifla 8y ago
    Unrolling the computation of the series, it is possible to compute f(n) using only f(n-4) and f(n-8): f(n) = 7*f(n-4)-f(n-8) So, using 4-vector operations, you can compute 4 numbers in one step.

emersonrsantos 8y ago

In Forth language would be: : fib 2dup + ; 2dup word duplicates n and n-1 elements and put it on the top of the stack. + word takes n and n-1 elements from the stack and sum them. The result goes on top of the stack. Just start with 1 and 1 at the top of stack.

willvk 8y ago
That's some very concise code golf! It would be interesting in seeing how Forth compiles this under the hood.
- pjc50 8y ago
  Normally Forth is interpreted. Compiled Forth code is unlikely to look particularly clean or elegant. (If you like languages with a very high density of functionality to symbol count, you should look at APL and its successor J)

saagarjha 8y ago

I think you might be missing the NULL that terminates argv in your stack diagram.

willvk 8y ago
Thanks for that. I've amended the diagram accordingly.

sdfsdfsdff 8y ago

It's also a problem in 7 Billion Humans or Human Resource Machine (I forgot which - they are both great anyway), fun programming games that also use a kind of assembly language.