C is Lower Level Than You Think(prog21.dadgum.com)
prog21.dadgum.com
C is Lower Level Than You Think
http://prog21.dadgum.com/185.html
12 comments
>No, C is lower level than you think.
Really? What made you think he doesn't think at the correct level? The fact that he tried to correct others that invoke the "sufficiently advanced compiler" thing?
If anything that would be proof that he thinks at the RIGHT level.
>And yes, the string could change mid iteration, in the loop or in another function that has access to the address, or even in another thread that's just made a guess at a valid memory address.
He already stated all that -- not to mention he knows it for over 3 decades.
>That's perfectly rational behaviour.
He didn't say it wasn't. He merely said that counter to some people who invoke the "sufficiently advance compiler" idea, that's what is actually happening.
Really? What made you think he doesn't think at the correct level? The fact that he tried to correct others that invoke the "sufficiently advanced compiler" thing?
If anything that would be proof that he thinks at the RIGHT level.
>And yes, the string could change mid iteration, in the loop or in another function that has access to the address, or even in another thread that's just made a guess at a valid memory address.
He already stated all that -- not to mention he knows it for over 3 decades.
>That's perfectly rational behaviour.
He didn't say it wasn't. He merely said that counter to some people who invoke the "sufficiently advance compiler" idea, that's what is actually happening.
> This is the beauty and power of C, everything is a piece of memory and nothing is guaranteed, and no we will not hold your hand or stop you doing something stupid. Someone else has a valid use case for that, even if they don't know it yet.
Just replace C with assembler and we know why we should all go back to it. Or rather not ..? Guarantees provide reliable environments. Reliablity is really helpful.
My nitpick aside ... I still want to (finally, really) learn C some time. Yeah, I can read it more or less, but that's not the same. Maybe on my next vacation.
Just replace C with assembler and we know why we should all go back to it. Or rather not ..? Guarantees provide reliable environments. Reliablity is really helpful.
My nitpick aside ... I still want to (finally, really) learn C some time. Yeah, I can read it more or less, but that's not the same. Maybe on my next vacation.
Going back to assembly has it's place, sometimes you want to do some gnarly/neat stuff with the call stack which is straightforward in assembly but which C doesn't lend itself to. Other times, you don't need to do that, and C has you covered. Yet other times, you really don't need to do anything that C enables and python will have you covered instead... it all depends on what you are doing.
Inline assembly in C, but still you don't need to jump to pure assembly (ie FASM/MASM/TASM,etc.). OP is just mouthing off about how if you go one level deep, you might as well strip off all your floorboards. Thats a logical fallacy.
C is basically readable, portable assembler. That's it. Don't treat it as a high level language; treat it as a nicer alternative to assembler. It definitely has its place, but it's not for everybody.
I really don't think you have a space to speak here if you don't know C. C is a behemoth, sure but there's no surprises. And assembler is platform specific, so you can't really make the 'bandwagon'/'slippery slope' logical fallacy. Stay in Python/Ruby/TLC world, and leave us hard-core coders alone. We'll continue making the performant libs that your dynamic language runtime requires. Thanks.
Much real world C code is platform specific too. As written: I can read C (more or less) and I can recognize things like code that will only work on your nice little endian platform and will explode in your face on big endian. Code like that is written all the time in C - especially by programmers that "continue making the performant libs" or whatever you think you do. So, the abstraction over assembler is often far smaller than you make it out to be. But that is a completely different point, which has nothing to do with my last post.
sgift, dealing with big vs small endian is a ways away from dealing with different opcodes and instruction sets like SSE and whatnot. It's not far smaller. It's huge. You aren't speaking from experience. As someone who used to do reverse engineering and knows assembly first-hand, I'm not going to argue with you about the different between writing code in assembly versus C. You're incorrect to say that ASM and C are so close. There's a reason why certain routines are implemented in CPU architecture specific asm, and that's for speed. Because C is still too high up to make many optimizations. The lack of fine-grained-ness is definitely there, in regard to the processor instructions used.
[deleted]
I never said we should all use C for everything, I certainly don't :)
But it is what it is, a thing of great power and beauty but highly dangerous in the wrong hands.
But it is what it is, a thing of great power and beauty but highly dangerous in the wrong hands.
> we will not hold your hand or stop you doing something stupid
Thanks for underlining exactly why I love C: no bullshit, get down in the dirt, eat your debugging, live with valgrind for that tiny bit that won't free itself,... Sometimes, I wish ruby could segfault a bit just so I have to debug my code for something else than a missing '='...
Thanks for underlining exactly why I love C: no bullshit, get down in the dirt, eat your debugging, live with valgrind for that tiny bit that won't free itself,... Sometimes, I wish ruby could segfault a bit just so I have to debug my code for something else than a missing '='...
I agree. The OP's examples are lame. Anyone who has written a memory allocator (I've written at least a couple) knows there's overhead for each allocation.
There are many ways you can shoot yourself in the foot with C that are much more obscure.
There are many ways you can shoot yourself in the foot with C that are much more obscure.
It's weird to me that a post like this even needs to be written. Isn't it kind of obvious that it's highly problematic for the compiler to do this optimization because the function, generally speaking, may have side effects?
For me, this kind of post means that C language is not any more core basic knowledge. The new generation has selected a new set of core basic knowledge: javascript, html5, python (for teaching of algorithm, not for production), scalability, replication, UX/UI ...
In this particular case it's not even the fact that strlen may have side effects. Suppose we had syntax to tell the compiler strlen is a pure function. It still could not optimize it out because it'd have to know that strlen argument (both itself and memory it points to) is not going to change inside the loop either. By the time you're done checking all the Vs that compiler needs to actually optimize it, it may be much easier to rewrite the loop. At least that way you'd know exactly what's going on and won't have to disassemble binaries to find it out.
It might be obvious to people with some experience. Many C programmers never read the standard or understand how the language works exactly, though. And to those people it might not immediately be obvious that for the strlen to be hoisted out of the loop the compiler would have to guarantee that the string's memory cannot change at all during the same loop. And that any function call can already lead to the compiler giving up trying to guarantee that.
Here's a gotcha I find more interesting than strlen: Right shifting integers instead of dividing by powers of two, e.g:
1337 / 8;
Becomes:
1337 >> 3;
Compilers ought to figure that one out, shouldn't they? Well if 1337 is a signed int, they can't. Shifting actually leads to different semantics for negative numbers, so this optimisation is only possible for unsigned ints. You can either do the bit shift or cast to unsigned, but it's a leaky abstraction either way.
1337 / 8;
Becomes:
1337 >> 3;
Compilers ought to figure that one out, shouldn't they? Well if 1337 is a signed int, they can't. Shifting actually leads to different semantics for negative numbers, so this optimisation is only possible for unsigned ints. You can either do the bit shift or cast to unsigned, but it's a leaky abstraction either way.
I'm pretty sure that the different semantics for negative signed ints (sign extension) are there to make sure it works as division. It's right-shifting for regular bit manipulation purposes that's unsafe with signed.
Whether right-shift is arithmetic or logical is implementation-defined in C. The compiler (for obvious reasons) knows what hardware is available, and generally optimizes a divide by a power of two to a right-shift if arithmetic is available (as it is in most architectures), plus a check to see if the number is odd and negative (and to add 1 to the numerator if so). All of which is still faster than using the divide hardware.
One more instance where I just assumed that what GCC does was in the standard. Very interesting.
For the curious who don't want to duplicate my look-up - right shift is by definition division by two except negative signed numbers, for which it's implementation defined. GCC on every architecture I've checked uses arithmetic shift for signed, probably because that extends the base definition to negatives.
For the curious who don't want to duplicate my look-up - right shift is by definition division by two except negative signed numbers, for which it's implementation defined. GCC on every architecture I've checked uses arithmetic shift for signed, probably because that extends the base definition to negatives.
This is a problem in most imperative-paradigm languages, unfortunately. The issue is in the semantics of the `for` loop, which make everything confusing both for the programmer and the compiler.
I think the issue is that you don't know what's going to happen when you call an arbitrary function.
There's no reason that the compiler should even optimize strlen out of the loop. Here's the proper way to iterate a string if order doesn't matter, take notice:
What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes. If you want to have fast access to strlen, and you find yourself being pained by the extra variable to cache the value, then use std::string.
This blog post needs a refactor.
for (int i = strlen(str); i--;)
...loopContents...
What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes. If you want to have fast access to strlen, and you find yourself being pained by the extra variable to cache the value, then use std::string.
This blog post needs a refactor.
My guess/intuition was that walking backwards might defeat any memory pre-caching at various layers (CPU, OS).
I wrote this quick-and-dirty code [http://codepad.org/d9ilykxA] to try and test the effect.
To me, it's a little interesting how it various with optimisation level, but I've not picked apart the assembly to see what's going on.
Under gcc 4.8.1, 64bit ubuntu):
Also - what is going on with clang -O2?
I wrote this quick-and-dirty code [http://codepad.org/d9ilykxA] to try and test the effect.
To me, it's a little interesting how it various with optimisation level, but I've not picked apart the assembly to see what's going on.
Under gcc 4.8.1, 64bit ubuntu):
-O0 forwards 4.37s, backwards 4.88s (fowards faster)
-O1 forwards 2.67s, backwards 2.66s (same/backwards faster)
-O2 forwards 2.67s, backwards 2.66s (same/backwards faster)
-Os forwards 3.33s, backwards 3.00s (backwards faster)
-O0 forwards 3.35s, backwards 4.11s
-O1 forwards 2.67s, backwards 2.67s
-O2 forwards 0.69s, backwards 0.77s
-Os forwards 2.67s, backwards 3.00s
Also - what is going on with clang -O2?
I don't believe these tests show much. You need to be doing something realistic inside the loop, and not repeating it using num_iterations, that will probably be optimized out into an unrolled memcpy. Too simplistic to be an accurate test. Modern CPUs will precache memory forwards as well as in reverse.
The author isn't saying that there's anything wrong with strlen; he's just saying that it's not trivially optimizable like it might seem to be.
Also, std::string is C++, not C.
Also, std::string is C++, not C.
Sorry, that was a slipup. What I meant is a string object library. std::string would be fine in the case of C++ or bstring for C
http://bstring.sourceforge.net/
http://bstring.sourceforge.net/
Did we read the same article? I read no rant against `strlen`, but rather against naive programmers incorrectly assuming that it could/should be hoisted out by an optimizing compiler. There was not one word about being pained by an extra variable, rather that it's a clunky-but-correct solution.
And other languages have nothing to do with it; this is strictly a post about C, not a dynamic language, and not C++.
And other languages have nothing to do with it; this is strictly a post about C, not a dynamic language, and not C++.
Just seems silly to rant against strings in C when they aren't really strings at all. char* is explicity a pointer to a sequence of chars. If a developer wants more things, like a cached length, invalidated by changes, then a lib should be used. A string lib like bstring[0]. I think we get to this precarious place by even considering that char* somehow brings what we could call 'common string functions' to the forefront in an easy way. And of course, assuming the compiler will optimize away code like strlen where it cannot possibly deduce constant memory conditions for the null byte, very silly indeed.
[0] http://bstring.sourceforge.net/
C is low level, but the same mistake could be said for any other language where a function is repeatedly called in a loop. The compiler can only do so much, garbage code is still garbage code. Cache your function calls less they const restricted, and extremely simple, and even then, the compiler might still fail to optimize.
[0] http://bstring.sourceforge.net/
C is low level, but the same mistake could be said for any other language where a function is repeatedly called in a loop. The compiler can only do so much, garbage code is still garbage code. Cache your function calls less they const restricted, and extremely simple, and even then, the compiler might still fail to optimize.
Where do you get the idea that the author is ranting against strings in C? I don't see it.
He's ranting against repeated function calls. Same could be said for any other language. The only interesting thing here is that strlen is the main way to get the length of a string in C, unlike OOP languages that will have a .length accessor that usually keeps the last validated length for o(1) access. That doesn't mean C is subterranean leveled.. it just means the language isn't OOP .. use a lib/struct/functions and the problem is solved. I see this as a baseless attack on C's lack of OOP through some clever bashing.
I'm reading it, and I'm rereading it, and I'm just not seeing that. In fact, I see the author going to great pains to point out that there really are times you want to depend on the non-hoisted conditional behavior of C. This is a heads up, not a "OMG C is teh worst language EVAR!" rant, not even a subtle one.
Storing length with pointer to array has nothing to do with OOP, strings can be defined as simple records (aka structs, product types) you don't need OOP for that:
struct string_t { const char * buffer; int lenght };
That still would not solve the issue as you'd manually be updating length when you modified your string. This is why instead of rolling your own lib, it's probably better to use the existing dynamically allocated C string libs out there to take care of it. Right, all the libs use a struct, as there are no first-class objects in C.
Actually I would prefer to write the length at creation time and don't mutate the string at all (and yes I'm aware that the line of code above is quite far from ensuring immutability); afaik most of those "OOP languages" use immutable strings. But yes, you are absolutely right in most cases using existing libraries is superior solution to any own, rolled-out-just-a-second-ago implementation of string; I used it only to demonstrate that storing length with a buffer address is hardly a OOP technique.
Here's how you'd do that mbel:
The array pointer can't change, the buffer size can't change, and the char components are const. Immutable but then again, you can violate that quite easily. And it's only compile-time immutability, which isn't all that great.
const char[] str = "This is a string";
int len = sizeof(str) / sizeof(str[0]);
The array pointer can't change, the buffer size can't change, and the char components are const. Immutable but then again, you can violate that quite easily. And it's only compile-time immutability, which isn't all that great.
Read some of the other stuff this guy has written - he's not the type to rant against low level stuff. He is the type to warn beginners about common pitfalls.
No beginner programmer (the premise of the article) will loop over a string backwards. No beginner programmer will put the decrement in the test slot like you did, in order to make i have valid values in the loop body.
I think it's somewhat scary to rely on post-decrement; I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string.
I still think the original article's suggestion to manually pre-compute the length (storing it in a const size_t variable, of course) is the better option, overall.
I think it's somewhat scary to rely on post-decrement; I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string.
I still think the original article's suggestion to manually pre-compute the length (storing it in a const size_t variable, of course) is the better option, overall.
> No beginner programmer (the premise of the article) will loop over a string backwards. No beginner programmer will put the decrement in the test slot like you did, in order to make i have valid values in the loop body.
So no beginner programmer will write proper code without further practice. I thought this was reasonably obvious. The reason why both those constructs work the same they do is likely to be found within a single paragraph of a properly-written book on the C programming language.
I'm definitely not claiming this is a nice feature to have in a language. I'm just trying to point out that the quality of the code a beginner programmer can write isn't a very good indicator of how high-level a language is. All beginning programmers will write shit code in any language, as low-level as Assembly and C or as high-level as Lisp or JavaScript.
So no beginner programmer will write proper code without further practice. I thought this was reasonably obvious. The reason why both those constructs work the same they do is likely to be found within a single paragraph of a properly-written book on the C programming language.
I'm definitely not claiming this is a nice feature to have in a language. I'm just trying to point out that the quality of the code a beginner programmer can write isn't a very good indicator of how high-level a language is. All beginning programmers will write shit code in any language, as low-level as Assembly and C or as high-level as Lisp or JavaScript.
This is the fastest way to write a loop in pretty much any language _if_ order is not imperative and is very well understood by any developer worth their salt.
> I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string.
That makes absolutely no sense. It's post-increment so it runs for i=0, could have easily been:
> I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string.
That makes absolutely no sense. It's post-increment so it runs for i=0, could have easily been:
for (int i = strlen(str); --i >= 0;)
Huh? I'm aware that there can be benefits to looping backwards. There can also be (cache-related) drawbacks.
"It's post-increment so it runs for i=0" is probably exactly what I meant, you needed to use post-decrement (not increment) since otherwise it would break. Of course it can be re-written like you did now, but then you added the >= 0 part which was implicit in your first comment. Its omission made it important to pick post-decrement or it would break on an empty string just as I said. My entire point was that it's beyond most beginners to rely on fairly subtle things like that.
Not sure why you're so condescending, I certainly didn't try to call you a beginner, it was the other way around: your code was not very beginner-esque, but the original article was about how a C beginner might write a simple loop and be surprised.
"It's post-increment so it runs for i=0" is probably exactly what I meant, you needed to use post-decrement (not increment) since otherwise it would break. Of course it can be re-written like you did now, but then you added the >= 0 part which was implicit in your first comment. Its omission made it important to pick post-decrement or it would break on an empty string just as I said. My entire point was that it's beyond most beginners to rely on fairly subtle things like that.
Not sure why you're so condescending, I certainly didn't try to call you a beginner, it was the other way around: your code was not very beginner-esque, but the original article was about how a C beginner might write a simple loop and be surprised.
I see what you mean now, I was quick to judge, wrongly albeit. Sorry about that.
It's not foolproof, though. Take a beginning C++ programmer who heard that type inference is all the rage now:
for (auto i = strlen(str); --i >= 0;)
"The proper way"? Not only is it less familiar than the usual "i = 0; i < n; i++" idiom, requiring the reader to examine exactly what it's doing, but now i goes from n to 1 instead of 0 to n-1. What's so bad about caching the strlen result in a variable beforehand?
You're wrong. Maybe I should hire my next team based on loop analysis ;-)
http://codepad.org/kd3oOBAb
http://codepad.org/kd3oOBAb
And I think this perfectly demonstrates why it is a stupid approach to take in the first place. In fact, personally I have a tendency to avoid for-loops in C because of the awful syntax; I much prefer using while-loops as I find them far clearer.
In 25+ years of C, I've seen plenty of people getting for-loops wrong (making broken assumptions about what's evaluated where, and countless off by one bugs), but everyone gets while-loops.
If you are going to do for-loops in C, stick with the most obvious, simplest variants possible - the moment you try to be smart, you've substantially increased the odds that a maintenance programmer will introduce a bug at one point or another.
In 25+ years of C, I've seen plenty of people getting for-loops wrong (making broken assumptions about what's evaluated where, and countless off by one bugs), but everyone gets while-loops.
If you are going to do for-loops in C, stick with the most obvious, simplest variants possible - the moment you try to be smart, you've substantially increased the odds that a maintenance programmer will introduce a bug at one point or another.
For the sake of job security, I propose using the comma operator to put the entire loop body within the for() parentheses, and replace the block with a semicolon:
// Pure C99 (prints an invalid character at the end)
for(
FILE *f = fopen("/etc/fstab", "r");
!feof(f) || (fclose(f), 0);
putchar(fgetc(f))
) ;
// C99+POSIX
for(
int fd = open("/etc/fstab", O_RDONLY), c = 0;
read(fd, &c, 1) || (close(fd), 0);
write(1, &c, 1)
) ;You have read his loop wrong. It has the same bounds.
i goes from n-1 to 0 in the example because for loops execute the condition before the first iteration.
[deleted]
>What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes.
No attack at strlen at all. Perhaps you didn't read it correctly? Not to mention the author already knows all of this (trivial) information.
The only attack is at the naive assumption of some newbie programmers (which the blog post targets) that "the compiler should take care of that".
No attack at strlen at all. Perhaps you didn't read it correctly? Not to mention the author already knows all of this (trivial) information.
The only attack is at the naive assumption of some newbie programmers (which the blog post targets) that "the compiler should take care of that".
Wow, this "for (int i = strlen(str); i--;) printf("%c", str[i]);" trick to reverse a string is really cool! Thanks!
I realise this is illustrating something, but just in case:
For the love of all that is good, please don't actually printf() for every character...
Depending on your platform that may or may not result in a ridiculous number of system calls, but no matter what, it will be slow if you do it a lot. If you insist on calling a function for every character (which is still silly), please at least putchar()/putc()/fputc() (putc()/putchar() can expand inline, but even they have substantial overhead to lock the stream)
I've seen systems spend the majority of their time in IO functions because of stuff like that. Always, always, always batch up IO unless you have real reasons not to (and almost always avoid syscalls when you can)
For the love of all that is good, please don't actually printf() for every character...
Depending on your platform that may or may not result in a ridiculous number of system calls, but no matter what, it will be slow if you do it a lot. If you insist on calling a function for every character (which is still silly), please at least putchar()/putc()/fputc() (putc()/putchar() can expand inline, but even they have substantial overhead to lock the stream)
I've seen systems spend the majority of their time in IO functions because of stuff like that. Always, always, always batch up IO unless you have real reasons not to (and almost always avoid syscalls when you can)
Is there a good resource or book on how to write high performance C code?
I just started learning programming, and I will need to write C for simulations (well, it will be CUDA version of C or C++).
I can't think of any good books of the top of my head - I've picked this up largely from starting out with assembly, and spending years picking apart compiler output (initially because the C compilers I had access to were junk, and I more than once would compile something, disassemble it and then hand-optimise the result...)
One approach is to learn to read assembly (being able to write it from scratch is optional), and understand what affects clock cycle count. On modern architectures that also means understanding cache effects, and particularly looking out for memory access patterns. Then look at lots of disassembly and learn to understand what kind of code typically gets generated from your C. Often it will be plain obvious why things are slow when you see the amount of generated code (though here be dragons - sometimes modern compilers will actually do a good job optimising, and as a result produce code that no sane human would ever write manually).
You can quickly get a good feel for patterns that are good and bad.
But in general:
- Profile. Profile some more, to make sure you're actually spending your time on the code that matters.
- A useful rule of thumb is that for any given algorithm, the fewer function calls and memory accesses, the better it is likely to to be. Functions calls are expensive, and often (not always) reduce locality of code, and so increase the amount of time spent accessing memory that is not in cache (== expensive). But don't start hand-unrolling/removing abstractions until you know by profiling that the code in question is performance critical, or you may just end up creating a maintenance nightmare.
- System calls are particularly nasty on any memory protected modern OS. The context switch overhead tends to be absolutely brutal. Which means it's very often worth quickly breaking out strace (on Linux) or equivalents to quickly eyeball the system call behaviour of applications before spending much time on other stuff. E.g. one particular pet peeve of mine is the amount of time you see read() or write() with small byte counts - if that occurs often, you can sometimes get truly massive speedups simply by changing the code to do non-blocking read/writes to/from a buffer and do smaller read/write's in user space from those buffers. (Always be suspicious of code that does read/write/recv/send or similar unless you can see it uses large-ish buffers... but profile). My experience is that odds are shockingly high that people will severely underestimate the cost of system calls.
- Keep data that is accessed together close in memory. E.g. cluster values by access patterns when you can, to avoid thrashing cache when you access the data. This can be tricky, and the solutions can be non-obvious because the actual access patterns may not be that easy to spot.
One approach is to learn to read assembly (being able to write it from scratch is optional), and understand what affects clock cycle count. On modern architectures that also means understanding cache effects, and particularly looking out for memory access patterns. Then look at lots of disassembly and learn to understand what kind of code typically gets generated from your C. Often it will be plain obvious why things are slow when you see the amount of generated code (though here be dragons - sometimes modern compilers will actually do a good job optimising, and as a result produce code that no sane human would ever write manually).
You can quickly get a good feel for patterns that are good and bad.
But in general:
- Profile. Profile some more, to make sure you're actually spending your time on the code that matters.
- A useful rule of thumb is that for any given algorithm, the fewer function calls and memory accesses, the better it is likely to to be. Functions calls are expensive, and often (not always) reduce locality of code, and so increase the amount of time spent accessing memory that is not in cache (== expensive). But don't start hand-unrolling/removing abstractions until you know by profiling that the code in question is performance critical, or you may just end up creating a maintenance nightmare.
- System calls are particularly nasty on any memory protected modern OS. The context switch overhead tends to be absolutely brutal. Which means it's very often worth quickly breaking out strace (on Linux) or equivalents to quickly eyeball the system call behaviour of applications before spending much time on other stuff. E.g. one particular pet peeve of mine is the amount of time you see read() or write() with small byte counts - if that occurs often, you can sometimes get truly massive speedups simply by changing the code to do non-blocking read/writes to/from a buffer and do smaller read/write's in user space from those buffers. (Always be suspicious of code that does read/write/recv/send or similar unless you can see it uses large-ish buffers... but profile). My experience is that odds are shockingly high that people will severely underestimate the cost of system calls.
- Keep data that is accessed together close in memory. E.g. cluster values by access patterns when you can, to avoid thrashing cache when you access the data. This can be tricky, and the solutions can be non-obvious because the actual access patterns may not be that easy to spot.
Thanks! Is there a good profiling tool you recommend?
Right now I'm using time command on Linux. How can I measure the execution time of a single loop inside my program?
To start, you can instrument the loop using a function like clock_gettime(CLOCK_MONOTONIC, ...)[0], or you can compile with the -pg flag and use gprof[1]. If you instrument, put your instrumentation outside the loop and divide by the number of iterations. From there you can start researching tools like valgrind (and its different internal modules like cachegrind, helgrind, etc.), OProfile, and others.
Your available tools will be different once you start using CUDA or OpenCL; you'll need to look for profiling methods designed for those environments at that point.
[0] http://man.cx/clock_gettime [1] https://duckduckgo.com/?q=gprof+tutorial
Your available tools will be different once you start using CUDA or OpenCL; you'll need to look for profiling methods designed for those environments at that point.
[0] http://man.cx/clock_gettime [1] https://duckduckgo.com/?q=gprof+tutorial
It seems that everyone's forgetting the whole genius thing about C-strings, which is that you can iterate through them without advance knowledge of their length:
char c;
while(c = *(str++))
...
Which is great if you're guaranteed to advance one character per loop iteration. Which may or may not hold.
True, this is even better in terms of complexity. I'd be curious to know if constantly changing the pointer causes certain cpus to execute this slower than doing a DWORD PTR [EAX + EDX] where EDX is the counter and EAX is the start of the str.
I actually prefer the variation:
char c;
for (int i = 0; (c = str[i]) != '\0'; i++)
...loopcontents using c...
If you're going to do that, why are you wasting instructions maintaining an offset and adding it to the string pointer on every iteration, instead of just iterating the pointer (or a copy of it) every iteration instead?
I was trying to provide a semantically equivalent construct (you might need the current index for some computation). Furthermore, the difference between the two really is negligible. The current solution involves an increment to i, an increment to the pointer, and a dereference whereas the solution you describe only involves an increment to the pointer and a dereference. The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA.
Providing a semantically equivalent construct is a fair enough reason.
> Furthermore, the difference between the two really is negligible. > ... > The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA.
Whether or not it matters will depend greatly on how often this loop is executed, and what else it does, and the ISA and available address modes, as well as whether or not the pointer and/or counter can fit in available registers.
If the pointer and counter is not in registers, and you don't have a suitable indirect indexed type load/test instruction, you can easily end up with 3+ extra memory reads. Memory access gets expensive if/when those kind of loops are run often enough.
I've seen speed improvements of 30%-50% from a couple of hours of work from production systems just from trivial rewrites to reduce memory accesses like these. Some fixes like that have paid my salary for months in reduction in server investments.
> Furthermore, the difference between the two really is negligible. > ... > The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA.
Whether or not it matters will depend greatly on how often this loop is executed, and what else it does, and the ISA and available address modes, as well as whether or not the pointer and/or counter can fit in available registers.
If the pointer and counter is not in registers, and you don't have a suitable indirect indexed type load/test instruction, you can easily end up with 3+ extra memory reads. Memory access gets expensive if/when those kind of loops are run often enough.
I've seen speed improvements of 30%-50% from a couple of hours of work from production systems just from trivial rewrites to reduce memory accesses like these. Some fixes like that have paid my salary for months in reduction in server investments.
This seems like surprising behavior because we expect compilers will make wise choices. Beginning programmers do the same: for example I've seen something like:
for x in stuff_list:
print other_list_of_stuff.count(x)
Nobody who tried to write some code compiling something (I'm not even talking about optimizing C compiler, but parsing or processing any sufficiently rich format that humans can touch) wouldn't expect compilers to make too much of the wise choices. Making code that behaves correctly, in a predictable manner according to what people expect and be "wise" too is very hard. It's easy to say "oh, it's clear I meant foo when I wrote bar" but try to make a code that identifies cases where "bar" means "foo" with 100% accuracy and you'll get why compilers aren't as wise as some think they could be.
The problem here is that the for loop in C is a direct generalization of the while loop. In a Pascal-like language like Oberon the bound is only calculated once, so
FOR i := 0 TO Strings.Length(s) - 1 DO
...
END
lim := Strings.Length(s) - 1;
WHILE i <= lim DO
...
INC(i)
ENDP.S. We have PVS-Studio rule for this issue: http://www.viva64.com/en/d/0309/
http://prog21.dadgum.com/179.html
This is my favourite article of him :)
This is my favourite article of him :)
[deleted]
I don't see how the compiler's smartness factors in a language's level.
tl;dr if you don't know what you're doing, you don't know what you're doing.
That's perfectly rational behaviour. And yes, the string could change mid iteration, in the loop or in another function that has access to the address, or even in another thread that's just made a guess at a valid memory address.
This is the beauty and power of C, everything is a piece of memory and nothing is guaranteed, and no we will not hold your hand or stop you doing something stupid. Someone else has a valid use case for that, even if they don't know it yet.