Calling Leader and other interested friends: GCC optimization !!

[andhrabalayya]

I was browsing through LLVM compiler doc's recently... and was comparing it against GCC... !!
gcc's recursion optimization is amazing... while LLVM cannot do that optimization "yet". Ok...well, here is a simple recursive function for searching a linked list:
void search(Node *node, int val) {
    if (node == NULL) {
      print("Did not find it!");
    } else if (node->val == val) {
      print("Did find it!");
    } else {
      search(node->next, val);
    }
}

Hopefully it makes sense... so if the list is long, then search() calls search() calls search() calls search()....
Naively, every call to search() creates a new stack frame. If your stack is small, then this could cause you to overflow the stack.. and even if it doesn't overflow the stack, it takes time to create all of those stack frames, and to tear them down. But you';ll notice that if teh function makes a recursive call, it's the last thing that it does there's no additional work after calling search. So by the time search() reaches the recursive call, it no longer needs its stack frame at all ... because its work is done ... so it might as well just re-use its own stack frame, for the recursive call.
....Hope that makes sense. The recursive call adopts the stack frame of the calling function and then if that recursive call makes another recursive call, it can adopt it too.
.. so in the end there's only one stack frame, and it's as fast as a loop. Another way to think about tail recursion is that the compiler rewrites a recursive call to be a loop..

Here's the same code, rewritten the same way the compiler would rewrite it:

void search(Node *node, int val) {
    if (node == NULL) {
      print("Did not find it!");
    } else if (node->val == val) {
      print("Did find it!");
    } else {
      search(node->next, val);
    }
}

void search_rewritten(Node *node, int val) {
  restart:
    if (node == NULL) {
      print("Did not find it!");
    } else if (node->val == val) {
      print("Did find it!");
    } else {
      node = node->next;
      goto restart;
    }
}

gcc's recursion optimization is pretty amazing(I don't know how they do it, honestly :) )

[andhrabalayya]

moscow vi ninna ne ayipoyayi videos... eeroju nuclear secrets 2nd episode ( na daggara complete video set undi download chesukuna rapidshare nundi 2.5 gig )
[quote author=sandhya link=topic=126733.msg1402302#msg1402302 date=1290998258]
ok...will read...(btw,any moscow videos links today...or only yday ones..)
[/quote]

[bulava]

[quote author=andhrabalayya link=topic=126733.msg1402242#msg1402242 date=1290997074]
ennalluga Embedded systems expertise ni vethukutunna... this post is not about it.. But since you are familiar with embedded stuff.. I am planning to buy an ARM dev board .. can you suggest an inexpensive board ? ( I wanna use it for learning, can spend upto 200$$ ) I have seen some ARM dev boards on ebay.. will ping you
[/quote]

If you are living in the US then you could get a damn good board for that budget. There are couple of companies which I would recommend but in terms of Tools and Support for the price you are going to pay nothing could beat an ARM-SBC from Technologic Systems. Check them out:

[url=http://www.embeddedarm.com/products/arm-sbc.php]http://www.embeddedarm.com/products/arm-sbc.php[/url]

Allocate some time and go through them patiently. I hope you would like it. Am using couple of them, say TS-7300 SBC with FPGA.

Good luck!

[andhrabalayya]

I have had one of the Xilinx Virtex FPGA(4 M gates I guess ) .... wire wrapped pretty much everything LCD , mem , CPLD's .. The reason I don't want to experiment with FPGA boards -> Expensive and a bit difficult to program using Verilog/VHDL.. There might be ways to program FPGA using C, but I want to try out Embedded Dev board
I would like to get this one [url=http://www.digilentinc.com/Products/Detail.cfm?NavPath=2,400,795&Prod=XUPV5]http://www.digilentinc.com/Products/Detail.cfm?NavPath=2,400,795&Prod=XUPV5[/url] but its expensive
[quote author=bulava link=topic=126733.msg1403807#msg1403807 date=1291037927]
If you are living in the US then you could get a damn good board for that budget. There are couple of companies which I would recommend but in terms of Tools and Support for the price you are going to pay nothing could beat an ARM-SBC from Technologic Systems. Check them out:

[url=http://www.embeddedarm.com/products/arm-sbc.php]http://www.embeddedarm.com/products/arm-sbc.php[/url]

Allocate some time and go through them patiently. I hope you would like it. Am using couple of them, say TS-7300 SBC with FPGA.

Good luck!
[/quote]

[bulava]

[quote author=andhrabalayya link=topic=126733.msg1403846#msg1403846 date=1291039819]
I have had one of the Xilinx Virtex FPGA(4 M gates I guess ) .... wire wrapped pretty much everything LCD , mem , CPLD's .. The reason I don't want to experiment with FPGA boards -> Expensive and a bit difficult to program using Verilog/VHDL.. There might be ways to program FPGA using C, but I want to try out Embedded Dev board
I would like to get this one [url=http://www.digilentinc.com/Products/Detail.cfm?NavPath=2,400,795&Prod=XUPV5]http://www.digilentinc.com/Products/Detail.cfm?NavPath=2,400,795&Prod=XUPV5[/url] but its expensive
[/quote]

I know but I didn't mean that you should buy a FPGA board too. There are couple of non-FPGA embedded boards in the URL I've referred, have you gone through them?

Importantly, what is your requirement/application/industry like? Let me know about it. I could recommend couple of other boards once you focus on what I just asked. Well, I hope you have a good flair in ARM/C on Linux else you need to start from the beginning. Hope this helps:

[url=http://www.ee.ic.ac.uk/pcheung/teaching/ee2_computing]http://www.ee.ic.ac.uk/pcheung/teaching/ee2_computing[/url]

If you intend to straight away dive into the development 'curve' with boards such as Virtex-5 you need to be quite specific with what you plan to do before investing in them else it would be waste of everything. As I mentioned earlier, what are you looking at down the line? How much experience do you have in Embedded Linux/C?

[bulava]

If you are comfortable you may discuss here with me as I don't use any Chat programs except IRCs on Private Torrents else you may always PM me. But think twice before you invest, don't be hasty.

[krldr871]

[quote author=andhrabalayya link=topic=126733.msg1402307#msg1402307 date=1290998356]
I was browsing through LLVM compiler doc's recently... and was comparing it against GCC... !!
gcc's recursion optimization is amazing... while LLVM cannot do that optimization "yet". Ok...well, here is a simple recursive function for searching a linked list:
void search(Node *node, int val) {
    if (node == NULL) {
      print("Did not find it!");
    } else if (node->val == val) {
      print("Did find it!");
    } else {
      search(node->next, val);
    }
}

Hopefully it makes sense... so if the list is long, then search() calls search() calls search() calls search()....
Naively, every call to search() creates a new stack frame. If your stack is small, then this could cause you to overflow the stack.. and even if it doesn't overflow the stack, it takes time to create all of those stack frames, and to tear them down. But you';ll notice that if teh function makes a recursive call, it's the last thing that it does there's no additional work after calling search. So by the time search() reaches the recursive call, it no longer needs its stack frame at all ... because its work is done ... so it might as well just re-use its own stack frame, for the recursive call.
....Hope that makes sense. The recursive call adopts the stack frame of the calling function and then if that recursive call makes another recursive call, it can adopt it too.
.. so in the end there's only one stack frame, and it's as fast as a loop. Another way to think about tail recursion is that the compiler rewrites a recursive call to be a loop..

Here's the same code, rewritten the same way the compiler would rewrite it:

void search(Node *node, int val) {
    if (node == NULL) {
      print("Did not find it!");
    } else if (node->val == val) {
      print("Did find it!");
    } else {
      search(node->next, val);
    }
}

void search_rewritten(Node *node, int val) {
  restart:
    if (node == NULL) {
      print("Did not find it!");
    } else if (node->val == val) {
      print("Did find it!");
    } else {
      node = node->next;
      goto restart;
    }
}

gcc's recursion optimization is pretty amazing(I don't know how they do it, honestly :) )
[/quote]
*=: *=: *=: oka question bhayyaa..
assume there is a counter thats incremented each time the function is called..lets say counter++; is the last statement..and it comes after the recursive call..you could probably have it above the recursive call as well..the call and the statement dont affect each other..so the compiler might as well place the statement above the call..sequence ni alter chesi execute chestada optimization kosam.. sCo_hmmthink sCo_hmmthink sCo_hmmthink

[andhrabalayya]

It can do that sort of reordering, if iti can prove that the calls really can't affect each other.Let's think about what counter is.If it's a local variable, then incrementing it as the last operation is pointless, because it's about to be destroyed anyways.  So in that case, the entire expression would probably be optimized out.If it's a global variable, the analysis is more difficult, and gcc may not be able to do it. And let's say its a global variable that keeps track of how many times the function has been called, gcc may or may not optimize it. The answer to that depends on what else the function does.For example, if the function accepts a pointer to an int as a parameter...It's possible that the function is passed the address of the global variable and in that case, the order that the variable is incremented matters a lot. If the recursive function makes any other function calls, those function calls may read or write the global variable too. So in that case, the order in which that the global variable is incremented matters a lot too.

[quote author=Leader871 link=topic=126733.msg1405153#msg1405153 date=1291059528]
*=: *=: *=: oka question bhayyaa..
assume there is a counter thats incremented each time the function is called..lets say counter++; is the last statement..and it comes after the recursive call..you could probably have it above the recursive call as well..the call and the statement dont affect each other..so the compiler might as well place the statement above the call..sequence ni alter chesi execute chestada optimization kosam.. sCo_hmmthink sCo_hmmthink sCo_hmmthink
[/quote]

[consignor]

*=: *=: *=: you rock

[krldr871]

yaa cheppu baa  sCh_elmodance2 sCh_elmodance2 sCh_elmodance2

[andhrabalayya]

"counter thats incremented each time the function is called..lets say counter++; "  ???
[quote author=Leader871 link=topic=126733.msg1406596#msg1406596 date=1291083415]
yaa cheppu baa  sCh_elmodance2 sCh_elmodance2 sCh_elmodance2
[/quote]

[krldr871]

[quote author=andhrabalayya link=topic=126733.msg1406605#msg1406605 date=1291083472]
"counter thats incremented each time the function is called..lets say counter++; "  ???
[/quote]
actually na ques enti ante..bad code valla optimization dobbachu..are the compilers intelligent to check these ani..tht ws jus an example..u cud consider the counter as a global variable..whether its the last statement or the statement before the recursive function call..it makes no diff..assuming such scenario, if the variable increment is executed first, it would be much more efficient kadha..idi realistic scenario kakapovachu..dont ask me why i would want to have a counter at tht position..jus a thought..

[krldr871]

mama ne initiative bavundi..deenne koncham extend chestu..oka video post cheddam daily..for example a stanford univ lecture oo ala edaina..and then disco cheddam..if possible, chinna examples tho practical ga emaina cheyyachantava  sSc_hiding2 sSc_hiding2 naku chala nerchukovalani undi..ne lanti vallu koncham guidance iste bavuntadii

[andhrabalayya]

Lets move these topics to Jobs and IT !!
nenu Guidance iste baundademo mama... nenu field ki kotha  sSc_hiding2 apudapudu timepass kosam chaduvutu vuntanu!! naku personal blog unte blog chesevadini ledu kada anduke ikada threads lo vestuna.. emanna tappulunte experienced fellas vachi correct chestarani...
Did you read SICP ?
[quote author=Leader871 link=topic=126733.msg1406678#msg1406678 date=1291084042]
mama ne initiative bavundi..deenne koncham extend chestu..oka video post cheddam daily..for example a stanford univ lecture oo ala edaina..and then disco cheddam..if possible, chinna examples tho practical ga emaina cheyyachantava  sSc_hiding2 sSc_hiding2 naku chala nerchukovalani undi..[b]ne lanti vallu koncham guidance iste bavuntadii[/b]
[/quote]

[krldr871]

[quote author=andhrabalayya link=topic=126733.msg1406762#msg1406762 date=1291085339]
Lets move these topics to Jobs and IT !!
nenu Guidance iste baundademo mama... nenu field ki kotha  sSc_hiding2 apudapudu timepass kosam chaduvutu vuntanu!! naku personal blog unte blog chesevadini ledu kada anduke ikada threads lo vestuna.. emanna tappulunte experienced fellas vachi correct chestarani...
Did you read SICP ?
[/quote]
neeku manchi knowledge undi baa..nenu beginner ni le..inka kontha mandi unnaru DB lo manchi knwledge unna vaallu..chitti naidu okadu..inka kontha mandi..lets see if more people join in..
sicp start chesa baa monna nuvvu cheppinappudu..manchi C problems kosam vethukutha baa..roju okati solve chesi ala emaina cheste bavuntademo..emantav.. sCo_hmmthink sCo_hmmthink