3 ms·

And just like that, a micro-optimisation has introduced a bug. If the last number generated is even, it will still appear in the result set in the new code, an

by XJ6 7y ago

And just like that, a micro-optimisation has introduced a bug. If the last number generated is even, it will still appear in the result set in the new code, and not in the old code.

lifthrasiir 7y ago
The code assumes that, once the loop finishes, out[0] through out[index-1] contains the desired output. out[index] is not a part of that output.
- XJ6 7y ago
  Then you've got a bug which crashes if all your results were even and index is left zero.
  - kstenerud 7y ago
    The original code can end with index = 0 as well. The only difference is that in the optimized code, it will write to index 0, whereas in the original it will not.
    - XJ6 7y ago
      In the original code, an index = 0 would not be a problem. Here, trying to access out[index-1] would error. Yes, you could then guard against that of course, but then that's even more code to maintain. If this code is a critical hot-path then sure, micro-optimizations can make sense but doing so without over-commenting and a rigorous test suite to catch introduced bugs is a recipe for disaster.
      - kstenerud 7y ago
        I think you may have misread the code: while (howmany != 0) { val = random(); if( val is odd) { out[index] = val; index += 1; } howmany--; } vs while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; } Both of these store a list of odd numbers in out[], with "index" containing the resulting count of how many numbers are in out[]. Both will have an "index" (count) value of 0 if all inputs were even, and neither attempts to access out[index-1].
        XJ6 7y ago
        You were right I misinterpreted "out[0] to out[index-1]" but your next statement: > count of how many numbers are in out[] is not true, in the latter case it's a count of how many numbers you want to be in out[]. Consider what happens if howmany is 1 and it generates a single even number. In the original you have an empty array and index 0, in the newer one you have an array e.g. [2] and an index 0. Yes, you can solve this by 'manually' only returning the first "index" elements but it's just asking for trouble and a source of bugs as seen in your attempt to describe it have a difference between the reality and your description. You might not consider that to matter, but the point I'm trying to make isn't just nitpicking, it's that there are certain expected behaviours from code, and an array which is "all odd numbers, except maybe all odd but one last even number" is bound to lead to broken expectations.
        couchand 7y ago
        Granted, the examples lack enough detail to know precisely how `out` is allocated. However, it seems safe to assume from the context that `out` is allocated by the client and `index` is returned to indicate the total number. There is no case where `out` is an "empty array", it always must have enough space for `howmany` integers.
        gpderetta 7y ago
        You are reading too much in a minimalistic example to show some specific detail.
        kstenerud 7y ago
        > > count of how many numbers are in out[] > is not true, in the latter case it's a count of how many numbers you want to be in out[]. I'm failing to see how "index" is the count of how many numbers you want to be in out[] rather than the count of how many numbers actually ARE in out[], or why this would be different between code examples. > Consider what happens if howmany is 1 and it generates a single even number. In the original you have an empty array and index 0, in the newer one you have an array e.g. [2] and an index 0. Yes, that's the point, as was explicitly stated in the article. > Yes, you can solve this by 'manually' only returning the first "index" elements but it's just asking for trouble and a source of bugs as seen in your attempt to describe it have a difference between the reality and your description. What is there to solve? The end result in both cases is that variable "index" is 0, because 0 of the values in out[] are valid. > You might not consider that to matter, but the point I'm trying to make isn't just nitpicking, it's that there are certain expected behaviours from code, and an array which is "all odd numbers, except maybe all odd but one last even number" is bound to lead to broken expectations. Yes, and the expectation is that "index" tells you where the first garbage element is in the array (in both examples). You're either going to have an array with all garbage (index = 0), all garbage except the first element (index = 1), all garbage except the first and second elements (index = 2), and so on. What actual values are in a garbage index (even or odd or 0 or 1 or 2 or Martin Luther's birth year), are irrelevant because you're not going to read from those indices.
SloopJon 7y ago
It strikes me that the example is a bit contrived: why is howmany decremented unconditionally? The first loop populates out with howmany numbers. The second loop may set none (other than the ignored value that you point out). I suppose you can use the same trick: howmany -= (val bitand 1); But that might complicate the benchmark. Coincidentally, this was the subject of the first Stack Overflow question Bjarne addressed in an interview the other day: https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...
inetknght 7y ago
> And just like that, a micro-optimisation has introduced a bug. If only the function had a unit test to catch such bugs

by XJ6 7y ago

And just like that, a micro-optimisation has introduced a bug. If the last number generated is even, it will still appear in the result set in the new code, and not in the old code.

lifthrasiir 7y ago

The code assumes that, once the loop finishes, out[0] through out[index-1] contains the desired output. out[index] is not a part of that output.

XJ6 7y ago
Then you've got a bug which crashes if all your results were even and index is left zero.
- kstenerud 7y ago
  The original code can end with index = 0 as well. The only difference is that in the optimized code, it will write to index 0, whereas in the original it will not.
  - XJ6 7y ago
    In the original code, an index = 0 would not be a problem. Here, trying to access out[index-1] would error. Yes, you could then guard against that of course, but then that's even more code to maintain. If this code is a critical hot-path then sure, micro-optimizations can make sense but doing so without over-commenting and a rigorous test suite to catch introduced bugs is a recipe for disaster.
    - kstenerud 7y ago
      I think you may have misread the code: while (howmany != 0) { val = random(); if( val is odd) { out[index] = val; index += 1; } howmany--; } vs while (howmany != 0) { val = random(); out[index] = val; index += (val bitand 1); howmany--; } Both of these store a list of odd numbers in out[], with "index" containing the resulting count of how many numbers are in out[]. Both will have an "index" (count) value of 0 if all inputs were even, and neither attempts to access out[index-1].
      - XJ6 7y ago
        You were right I misinterpreted "out[0] to out[index-1]" but your next statement: > count of how many numbers are in out[] is not true, in the latter case it's a count of how many numbers you want to be in out[]. Consider what happens if howmany is 1 and it generates a single even number. In the original you have an empty array and index 0, in the newer one you have an array e.g. [2] and an index 0. Yes, you can solve this by 'manually' only returning the first "index" elements but it's just asking for trouble and a source of bugs as seen in your attempt to describe it have a difference between the reality and your description. You might not consider that to matter, but the point I'm trying to make isn't just nitpicking, it's that there are certain expected behaviours from code, and an array which is "all odd numbers, except maybe all odd but one last even number" is bound to lead to broken expectations.
        couchand 7y ago
        Granted, the examples lack enough detail to know precisely how `out` is allocated. However, it seems safe to assume from the context that `out` is allocated by the client and `index` is returned to indicate the total number. There is no case where `out` is an "empty array", it always must have enough space for `howmany` integers.
        gpderetta 7y ago
        You are reading too much in a minimalistic example to show some specific detail.
        kstenerud 7y ago
        > > count of how many numbers are in out[] > is not true, in the latter case it's a count of how many numbers you want to be in out[]. I'm failing to see how "index" is the count of how many numbers you want to be in out[] rather than the count of how many numbers actually ARE in out[], or why this would be different between code examples. > Consider what happens if howmany is 1 and it generates a single even number. In the original you have an empty array and index 0, in the newer one you have an array e.g. [2] and an index 0. Yes, that's the point, as was explicitly stated in the article. > Yes, you can solve this by 'manually' only returning the first "index" elements but it's just asking for trouble and a source of bugs as seen in your attempt to describe it have a difference between the reality and your description. What is there to solve? The end result in both cases is that variable "index" is 0, because 0 of the values in out[] are valid. > You might not consider that to matter, but the point I'm trying to make isn't just nitpicking, it's that there are certain expected behaviours from code, and an array which is "all odd numbers, except maybe all odd but one last even number" is bound to lead to broken expectations. Yes, and the expectation is that "index" tells you where the first garbage element is in the array (in both examples). You're either going to have an array with all garbage (index = 0), all garbage except the first element (index = 1), all garbage except the first and second elements (index = 2), and so on. What actual values are in a garbage index (even or odd or 0 or 1 or 2 or Martin Luther's birth year), are irrelevant because you're not going to read from those indices.

SloopJon 7y ago

It strikes me that the example is a bit contrived: why is howmany decremented unconditionally? The first loop populates out with howmany numbers. The second loop may set none (other than the ignored value that you point out). I suppose you can use the same trick: howmany -= (val bitand 1); But that might complicate the benchmark. Coincidentally, this was the subject of the first Stack Overflow question Bjarne addressed in an interview the other day: https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...

inetknght 7y ago

> And just like that, a micro-optimisation has introduced a bug. If only the function had a unit test to catch such bugs