5 ms·

The random idiom I got was: > Idiom #137 Check if string contains only digits > Set boolean b to true if string s contains only characters in range '0'..'9',

The random idiom I got was: > Idiom #137 Check if string contains only digits > Set boolean b to true if string s contains only characters in range '0'..'9', false otherwise. char b = 0; for (int i = 0; i < strlen(s); i++) { if (! (b = (s[i] >= '0' && s[i] <= '9'))) break; } I appreciate the funny assignment-and-test-and-early-break in one (although I'd hardly say it's idiomatic), but I could do without the quadratic strlen().

Miiko 5y ago
Not to mention that proper idiom for this task would be: int n = strspn(s,"0123456789"); BOOL b = (s[n] == 0);
- Stratoscope 5y ago
  That is nice and simple, but it makes ten comparisons for each character in s, where only two are needed. Of course it would be a good approach if the set of characters you're testing against is not contiguous, unlike 0..9.
  - toxik 5y ago
    Good news then, it’s also linear time like the marginally faster but enormously grotesque for loop provided previously. I would take that clarity of intent a hundred times over squeezing a couple of comparisons out.
    - Stratoscope 5y ago
      > it’s also linear time You raise an interesting point. It got me thinking about how big-O notation has failed us in some ways: it teaches us to ignore constant factors. In big-O, an algorithm that makes 1000 comparisons per element is no different from one that makes a single comparison per element. They are both linear time. But you can't deny that one of these will likely take 1000 times as long as the other. Of course, like you, I favor simple and readable code over grotesque code that is hard to understand and mentally verify.
      - still_grokking 5y ago
        I think big-O makes sense as a kind of filter for the truly bad solutions. When you have some big constant factor that's not good. But when you have a big exponent that's not workable anymore, even for smallest input.
      - toxik 5y ago
        Sure, asymptotic time complexity only says anything about the asymptotic behavior. On the other hand, I have had far more cases of things blowing up due to cubic or even quadratic time complexities than I have for linear; linear is what you expect, if it takes a long time for a toy input, it'll take twice as long for a real input at double the size. Not so with the superlinear ones, your toy problem might work fine, but cubed? Ain't happening this millennium. This combined with the constant factor tending to also grow as the problem size grows really is a potent foot-gun.
  - Miiko 5y ago
    Correct, but we're talking about "idiomatic" not "most efficient" solution. Input validation is usually not time-critical, and for these cases the code clearly showing the intent is much better than optimal one.
foxfluff 5y ago
It's not unreasonable to assume the compiler will optimize it to a single call. Though I guess people who are capable of making that judgement won't need to look this idiom up on the internet.
- sokoloff 5y ago
  Is there something in the C spec that allows optimizing to a single strlen call?
  - foxfluff 5y ago
    Absolutely. The gist of it: "In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object)."
    - sokoloff 5y ago
      As I understand it, the strlen implementation ("calling a function") is typically going to come from another object file (at link time), so it’s not clear that when compiling this file that “calling strlen has no side effects” is information available to the compiler.
      - foxfluff 5y ago
        strlen is a standard function (in a hosted environment). So it must do exactly what the standard says it does, and the standard doesn't say it has side-effects. The compiler could very well use a built-in implementation of strlen, or even omit the call entirely if it had another way to deduce its would-be return value. Object files are an implementation detail not known by the C standard.
        sokoloff 5y ago
        > the standard doesn't say it has side-effects The relevant question is "does the standard say that it does not have side-effects?" (is a pure function). @skissane's sibling comment to yours provides the explanation of how the compiler can deduce that it's a pure function.
thethirdone 5y ago
I just checked godbolt [0]. gcc only calls strlen once even with -O0. [0]:https://godbolt.org/z/j4o1915vE https://godbolt.org/z/j4o1915vE
- josefx 5y ago
  For me the strlen call appears directly before loops backwards jump when set to -O0, resulting in a call every iteration as far as I can tell. However -O1 already seems to optimize it to a single call at the start of the function.
  - still_grokking 5y ago
    I find it every time funny that when using languages that want to give you "total control" over the execution of your code (mostly C/C++) you actually almost never know what code gets executed in the end. It depends on the compiler, it's version, it's flags, and likely "the position of the moon". Of course the compiler is only allowed to do transformations that the spec permits. But it's impossible for a human being to anticipate the exact outcome. It's more like: "Compiler, do something that has the same outcome as this code I show you here". The output can be than something that doesn't resemble the input even slightly! There's obviously nothing wrong when the compiler is so smart that it sees some patterns and transforms your code into something much more efficient. Only that there's not much difference to what happens when you use a high level language. In both cases you in fact don't control the exact code that gets executed, and in both cases you rely on the smartness of your compiler to produce some efficient code, "whatever" you've written. That's why I think it's mostly a function of the code-style how performant or efficient some language can be (to some extend of course). When you write low-level style code (even in a high level language) a smart compiler will (hopefully) create something like what you would get form writing your code in C/C++.
    - bombela 5y ago
      I think what matters is the intent. Here the intent is to compare against strlen at every turn of the loop. When the compiler is optimizing it might very well realize that the parameter to strlen doesn't change and the output can be saved first. If the intent is to compute the length only once, then we can save the length in a variable. Of course; as others have pointed out; there is no need to call strlen at all in this example.
Stratoscope 5y ago
That is one of the most confusing pieces of C code I have seen lately. And it fails on an empty string: I would expect it to set b to 1 for an empty string, but it sets it to 0. Of course that could easily be fixed by setting b to 1 at the top. Also, code like this should always be put inside a function that returns a value, not just written inline. Making it a function allows simpler and more understandable code too. The funniest part is that it is not necessary to call strlen() at all! The whole thing can be written in a single pass over the string. Here is how I would code it in C: int OnlyDigits( char str[] ) { for( int i = 0; str[i] != '\0'; ++i ) { if( str[i] < '0' || str[i] > '9' ) return 0; } return 1; } Try it here: https://replit.com/@geary/OnlyDigitsC https://replit.com/@geary/OnlyDigitsC
- pvtmert 5y ago
  You do realize it returns 1 for an empty string right? I mean it doesn't have any digits in it... What about adding a check of str[0] == 0 -> return 0 Also, giving char str[] will make it char* str. Which can be null. This may cause reading a random memory location (possibly segfault or use-after-free) edit: I get the comments but empty string still contains no digits. Given the regex would be ^[0-9]+ (+ instead of *) What I want to say is string has a numerical value or not. Empty string is NaN.
  - zeven7 5y ago
    Empty string contains no non-digits. Therefore it is only digits.
  - Someone 5y ago
    “contains only digits” isn’t synonymous with “not (doesn’t have any digits)” It is synonymous with “none of the characters is a non-digit”, which is true for the empty string.
  - Stratoscope 5y ago
    > You do realize it returns 1 for an empty string right? I mean it doesn't have any digits in it... Yes, and that was deliberate on my part, as it meets my expectation of what such a function should do in this edge case. The problem statement was "Set boolean b to true if string s contains only characters in range '0'..'9', false otherwise." To my mind, the question "is every character in the string a digit" should be equivalent to "are there any non-digits in the string" (with the answer inverted, of course). Returning 0 (false) for the empty string makes those questions not equivalent. It makes the empty string a special case. Of course the real problem is that the problem is under-specified. It should call out specifically what should happen for an empty string, because as illustrated here, this is something where reasonable people may disagree. > Also giving char str[] will make it char* str. Which can be null. This may cause reading a random memory location (possibly segfault or use-after-free) Well yes, of course. The point of my comment wasn't to write bullet-proof library-ready code, it was only to illustrate two things: code like this should always go in a function, and the entire task can be accomplished in a single pass through the string. Thanks for keeping me on my toes!
val_deleplace 5y ago
Indeed! I updated the implementation to hoist the quadratic strlen.

Miiko 5y ago

Not to mention that proper idiom for this task would be: int n = strspn(s,"0123456789"); BOOL b = (s[n] == 0);

Stratoscope 5y ago
That is nice and simple, but it makes ten comparisons for each character in s, where only two are needed. Of course it would be a good approach if the set of characters you're testing against is not contiguous, unlike 0..9.
- toxik 5y ago
  Good news then, it’s also linear time like the marginally faster but enormously grotesque for loop provided previously. I would take that clarity of intent a hundred times over squeezing a couple of comparisons out.
  - Stratoscope 5y ago
    > it’s also linear time You raise an interesting point. It got me thinking about how big-O notation has failed us in some ways: it teaches us to ignore constant factors. In big-O, an algorithm that makes 1000 comparisons per element is no different from one that makes a single comparison per element. They are both linear time. But you can't deny that one of these will likely take 1000 times as long as the other. Of course, like you, I favor simple and readable code over grotesque code that is hard to understand and mentally verify.
    - still_grokking 5y ago
      I think big-O makes sense as a kind of filter for the truly bad solutions. When you have some big constant factor that's not good. But when you have a big exponent that's not workable anymore, even for smallest input.
    - toxik 5y ago
      Sure, asymptotic time complexity only says anything about the asymptotic behavior. On the other hand, I have had far more cases of things blowing up due to cubic or even quadratic time complexities than I have for linear; linear is what you expect, if it takes a long time for a toy input, it'll take twice as long for a real input at double the size. Not so with the superlinear ones, your toy problem might work fine, but cubed? Ain't happening this millennium. This combined with the constant factor tending to also grow as the problem size grows really is a potent foot-gun.
- Miiko 5y ago
  Correct, but we're talking about "idiomatic" not "most efficient" solution. Input validation is usually not time-critical, and for these cases the code clearly showing the intent is much better than optimal one.

foxfluff 5y ago

It's not unreasonable to assume the compiler will optimize it to a single call. Though I guess people who are capable of making that judgement won't need to look this idiom up on the internet.

sokoloff 5y ago
Is there something in the C spec that allows optimizing to a single strlen call?
- foxfluff 5y ago
  Absolutely. The gist of it: "In the abstract machine, all expressions are evaluated as specified by the semantics. An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object)."
  - sokoloff 5y ago
    As I understand it, the strlen implementation ("calling a function") is typically going to come from another object file (at link time), so it’s not clear that when compiling this file that “calling strlen has no side effects” is information available to the compiler.
    - foxfluff 5y ago
      strlen is a standard function (in a hosted environment). So it must do exactly what the standard says it does, and the standard doesn't say it has side-effects. The compiler could very well use a built-in implementation of strlen, or even omit the call entirely if it had another way to deduce its would-be return value. Object files are an implementation detail not known by the C standard.
      - sokoloff 5y ago
        > the standard doesn't say it has side-effects The relevant question is "does the standard say that it does not have side-effects?" (is a pure function). @skissane's sibling comment to yours provides the explanation of how the compiler can deduce that it's a pure function.

thethirdone 5y ago

I just checked godbolt [0]. gcc only calls strlen once even with -O0. [0]:https://godbolt.org/z/j4o1915vE https://godbolt.org/z/j4o1915vE

josefx 5y ago
For me the strlen call appears directly before loops backwards jump when set to -O0, resulting in a call every iteration as far as I can tell. However -O1 already seems to optimize it to a single call at the start of the function.
- still_grokking 5y ago
  I find it every time funny that when using languages that want to give you "total control" over the execution of your code (mostly C/C++) you actually almost never know what code gets executed in the end. It depends on the compiler, it's version, it's flags, and likely "the position of the moon". Of course the compiler is only allowed to do transformations that the spec permits. But it's impossible for a human being to anticipate the exact outcome. It's more like: "Compiler, do something that has the same outcome as this code I show you here". The output can be than something that doesn't resemble the input even slightly! There's obviously nothing wrong when the compiler is so smart that it sees some patterns and transforms your code into something much more efficient. Only that there's not much difference to what happens when you use a high level language. In both cases you in fact don't control the exact code that gets executed, and in both cases you rely on the smartness of your compiler to produce some efficient code, "whatever" you've written. That's why I think it's mostly a function of the code-style how performant or efficient some language can be (to some extend of course). When you write low-level style code (even in a high level language) a smart compiler will (hopefully) create something like what you would get form writing your code in C/C++.
  - bombela 5y ago
    I think what matters is the intent. Here the intent is to compare against strlen at every turn of the loop. When the compiler is optimizing it might very well realize that the parameter to strlen doesn't change and the output can be saved first. If the intent is to compute the length only once, then we can save the length in a variable. Of course; as others have pointed out; there is no need to call strlen at all in this example.

Stratoscope 5y ago

That is one of the most confusing pieces of C code I have seen lately. And it fails on an empty string: I would expect it to set b to 1 for an empty string, but it sets it to 0. Of course that could easily be fixed by setting b to 1 at the top. Also, code like this should always be put inside a function that returns a value, not just written inline. Making it a function allows simpler and more understandable code too. The funniest part is that it is not necessary to call strlen() at all! The whole thing can be written in a single pass over the string. Here is how I would code it in C: int OnlyDigits( char str[] ) { for( int i = 0; str[i] != '\0'; ++i ) { if( str[i] < '0' || str[i] > '9' ) return 0; } return 1; } Try it here: https://replit.com/@geary/OnlyDigitsC https://replit.com/@geary/OnlyDigitsC

pvtmert 5y ago
You do realize it returns 1 for an empty string right? I mean it doesn't have any digits in it... What about adding a check of str[0] == 0 -> return 0 Also, giving char str[] will make it char* str. Which can be null. This may cause reading a random memory location (possibly segfault or use-after-free) edit: I get the comments but empty string still contains no digits. Given the regex would be ^[0-9]+ (+ instead of *) What I want to say is string has a numerical value or not. Empty string is NaN.
- zeven7 5y ago
  Empty string contains no non-digits. Therefore it is only digits.
- Someone 5y ago
  “contains only digits” isn’t synonymous with “not (doesn’t have any digits)” It is synonymous with “none of the characters is a non-digit”, which is true for the empty string.
- Stratoscope 5y ago
  > You do realize it returns 1 for an empty string right? I mean it doesn't have any digits in it... Yes, and that was deliberate on my part, as it meets my expectation of what such a function should do in this edge case. The problem statement was "Set boolean b to true if string s contains only characters in range '0'..'9', false otherwise." To my mind, the question "is every character in the string a digit" should be equivalent to "are there any non-digits in the string" (with the answer inverted, of course). Returning 0 (false) for the empty string makes those questions not equivalent. It makes the empty string a special case. Of course the real problem is that the problem is under-specified. It should call out specifically what should happen for an empty string, because as illustrated here, this is something where reasonable people may disagree. > Also giving char str[] will make it char* str. Which can be null. This may cause reading a random memory location (possibly segfault or use-after-free) Well yes, of course. The point of my comment wasn't to write bullet-proof library-ready code, it was only to illustrate two things: code like this should always go in a function, and the entire task can be accomplished in a single pass through the string. Thanks for keeping me on my toes!

val_deleplace 5y ago

Indeed! I updated the implementation to hoist the quadratic strlen.