I mostly code in C# & VB, but I think this question is pretty universal. I try to limit loops to increase performance. For instance, string functions that split the string into an array, or do a lookup or replace.

I think if I were to write some string functions with those kinds of capabilities, I would need to include a loop.

Any insights about how what a compiler is doing with, say, a string replace function? Or any examples of how they're written in the programming language?

  • 2
    What constitutes a 'built in function'? – user40980 Mar 7 '16 at 14:37
  • 6
    Do you know about the opcode set of your target machine? Everything that isn't doable with a fixed string of opcodes from that set will require a loop no matter how great a programmer does it. It makes no sense to be worried about "using loops" because they might be slow. – Kilian Foth Mar 7 '16 at 14:39
  • If I'm writing something in .NET, there are functions that are available to me for string manipulation, data type conversion, etc. – JMcD Mar 7 '16 at 14:39
  • @JMcD those would be part of the standard library (not so much 'built in'). I would encourage you to read through, say... the String class on Java (part of its standard library) and count the loops. – user40980 Mar 7 '16 at 14:46
  • 1
    .NET framework source code can be inspected here. – Robbie Dee Mar 7 '16 at 16:09

Very probably, most builtin or primitives functions of C# involves some loop (at the machine code level) when executed.

BTW, even the object allocation indirectly involves a loop. At some times, an object allocation could trigger the garbage collector, which is looping.

Notice that a program without any loops is a finite state automaton, and will surely terminate (in less than a second, typically - intuitively the CPU is processing more than one instruction per nano-second, and in a few gigabytes you can encode about a billion machine instructions; without loops the processor would interpret then quickly!)

Of course, function calls, in particular recursive function calls, are a way of looping. And tail-recursive calls are exactly a looping construct (which does not consume any call stack space).

Read also the SICP, and about lambda calculus, Turing completeness (notably accidental Turing completeness is very funny), primitive recursive functions, random-access machine, ...

BTW, you'll learn a lot by studying the source code of free software, and Microsoft has even made the source code of C# open source. With a Linux system on your laptop you'll have even more free software...

| improve this answer | |
  • 1
    Wow, you're going to keep me busy here for a while :-) Thanks! – JMcD Mar 7 '16 at 14:52

I guess any decent opimizer for almost any (compiled) mainstream programming language includes the well-known technique of loop unrolling. So it is unneccessary in most cases to do this kind of low-level optimization manually, the result of what compilers produce are often better than any "hand coded" solution.

Said that, if you can replace an O(n) algorithm with a loop like

 for(int i=1; i<=n; ++i)

by an O(1) solution without a loop, like

 sum+= n*(n+1)/2

then I would not expect a typical optimizer to be so smart that to do this automatically.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.