7 ms·

I find it weird that the case is called a "bug" multiple times. Sure, if its o(n^2), that's a problem, but if the code works correctly at the end, it's not a b

by gkya 10y ago

I find it weird that the case is called a "bug" multiple times. Sure, if its o(n^2), that's a problem, but if the code works correctly at the end, it's not a bug.

ouid 10y ago
Yes it is? Asymptotic complexity is a well defined property of an algorithm. It is an output, and it doesn't match the expected output.
- jeffdavis 10y ago
  "reject!" is not an algorithm. It is a semantic element of the ruby language, which is implemented using an algorithm. That algorithm, in this case, is a quadratic one.
  - ouid 10y ago
    No, because a linear implementation of bsearch is clearly a bug.
- TheDong 10y ago
  It's ruby, so the expected complexity of any line of code is "it might complete sometime in my lifetime". No surprises for users here, which is why that bug lasted for about 4 years with noone caring. If the documentation stated it was O(n), or benchmarks tested it was fast, then it being slow would become a bug. As is, it's just what it is.
  - aetherson 10y ago
    Well, probably the reason it lasted for about 4 years with no one caring is because .reject! is a fairly rarely used function.
- flukus 10y ago
  Can you point out where in the function definition this was defined?
choward 10y ago
If it's n^2 it may never return in your lifetime. Does the code work? Nobody knows. It this situation you may consider it a bug.
- CanSpice 10y ago
  O() doesn't say anything about how long it'll take. O(n) may never return in your lifetime too.
  - hamandcheese 10y ago
    O(1) might not either :)
    - dr_win 10y ago
      Because you might be dead already. Which would be a weird edge case.
      - pmiller2 10y ago
        No. O(1) just means the algorithm always takes no more than some arbitrary, but fixed amount of time to complete, regardless of the size of the input. That fixed amount of time could be a billion years (or more).
    - astrodust 10y ago
      It consistently takes a billion years, it's O(1).
  - chrisdevereux 10y ago
    O(0) would though, right?
    - lvh 10y ago
      You mean O(1) (alternatively, O(k)) -- from the definition of Big O notation, O(0) is nonsensical. But even then; O(1) just means "constant time", it does not mean "soon."
perfmode 10y ago
Unfortunately, it's not that simple. It's really depends on context. There are cases where accidental quadratic complexity would definitively be considered a bug. If a fleet of GitHub servers were burning cycles due to a quadratic reject!, I'm pretty sure the engineers would classify the misbehavior as such.
pdw 10y ago
O(n^2) algorithms are insidious in that they will work fine on test data, but will ruin performance when there's an unusually large input in production. They're landmines in your code.
- eco 10y ago
  One of the more interesting approaches I've seen lately is in Andrei Alexandrescu's "An Algebra for Expressing Time Complexity of Generic Functions" article[1]. The gist is you (or more likely, the library writer) annotate functions with their complexity guarantees then you can make static assertions about your runtime performance expectations which result in a compile time error if the algorithms/data structures being used cannot meet them. In theory that would prevent the O(n^2) landmine. 1. http://erdani.com/d/bigo.html http://erdani.com/d/bigo.html
- throwaway1579 10y ago
  You do know that the most popular general-purpose, comparison-based sorting algorithm quicksort has a worst case complexity of O(n^2), right?
  - minitech 10y ago
    Good implementations tend to address this with introspection, randomization, etc..
- gkya 10y ago
  Certainly. But does it make it a bug?
- zerr 10y ago
  Alternatively, it will ruin performance on artificially large test data, but will work fine in production :)
parenthephobia 10y ago
It's not a bug in the method, but it should be. A peeve I have with Ruby is that methods in the standard library don't have defined big-O complexities. If they did, I don't think reject! would have been specified to be O(n²), and so it would be a bug.
- lotyrin 10y ago
  I'd love a type-system alike checking feature of a language that made you specify (and would verify) time complexity of functions Then in reviews its explicit when someone's doing something dumb (specifying high complexity for new algos) at compile time if a lower-complexity function calls a higher complexity one with the same sized input, or in CI when an algorithm isn't within the complexity it claims to be (experimentally)
  - al2o3cr 10y ago
    I suspect the "verify" part of that is going to slam head-first into the Halting Problem, given that some of the quadratic behavior only happens (see the blog) for particular patterns of use or input data. You'd also likely want to somehow encode space complexity as well, otherwise silly things like "precompute every possible result and put it in a giant lookup table" will register as "O(1)".
nikic 10y ago
If the function was implemented as an infinite loop, would you consider the code working correctly as well? After all, the result after execution of the function is always correct (ex falso quodlibet).
- gkya 10y ago
  An infinite loop is a loop that never ends, it'd not be possible to implement a function that's expected to return in terms of an infinite loop. Here the algorithm is quadratic but will, theoretically, always complete. Thus there is no bug, but a performance problem. I think that a bug is a mistake in a programme that causes erroneous behaviour. Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed? I'd rather call this a mistake as long as the output from the function is as expected. I'm not saying that it's a negligible mistake to use a quadratic algo where there is a linear one though. Just that I doubt it is fundamentally a bug.
  - dbaupp 10y ago
    > Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed? This only makes sense if you completely ignore context, which doesn't make any sense at all. The point/"bug"/mistake here is using a quadratic algorithm when it isn't necessary, not just the fact that the algorithm is quadratic. If something can be solved in O(1) time, it's a mistake to use an O(n) algorithm, and similarly, if something can be solved in O(2^(n!)) time, it's a mistake to use a O(9999^(n!)) algorithm (assuming constant factors are of similar orders of magnitude etc, as they are in the OP).
baddox 10y ago
Would a sleep(100000) at the top of the method implementation not count as a bug either?
- gkya 10y ago
  I don't see how this is relevant. That certainly is a bug if such a call is not a part of the algorithm. Here the function is correct in the sense that it returns as expected.
  - baddox 10y ago
    The function with a long sleep also returns as expected, and is just as much a part of that particular algorithm as the quadratic implementation.
  - astrodust 10y ago
    Quadratic performance is not part of the algorithm. End of story.
    - gkya 10y ago
      I am not your student and this is not a classroom. I really dislike that tone.
- nilved 10y ago
  How is that a bug? Unless sleep was a typo or something. A bug isn't related to performance, a bug is just a mistake.
  - baddox 10y ago
    This quadratic implementation was a mistake.
    - nilved 10y ago
      No it wasn't, the developer probably knew exactly what they were doing.
mkonecny 10y ago
If it can take down your webserver due to unexpected CPU overload, then I would consider it bug
wuch 10y ago
Programs without specification have only surprising behaviour no bugs. As far as I can see "reject!" does not specify complexity, so in this sense it would be completely fine. Additionally it claims to change the array instantly every time the block is called, which doesn't seem to give any other options than making it at least quadratic (presuming flat representation for arrays). This feels quite overspecified as accessing the array from within the block seems quite unusual case to cater for. Though, this behaviour was changed after all which leaves me wondering how much Ruby people care about backward compatibility.

by gkya 10y ago

I find it weird that the case is called a "bug" multiple times. Sure, if its o(n^2), that's a problem, but if the code works correctly at the end, it's not a bug.

ouid 10y ago

Yes it is? Asymptotic complexity is a well defined property of an algorithm. It is an output, and it doesn't match the expected output.

jeffdavis 10y ago
"reject!" is not an algorithm. It is a semantic element of the ruby language, which is implemented using an algorithm. That algorithm, in this case, is a quadratic one.
- ouid 10y ago
  No, because a linear implementation of bsearch is clearly a bug.
TheDong 10y ago
It's ruby, so the expected complexity of any line of code is "it might complete sometime in my lifetime". No surprises for users here, which is why that bug lasted for about 4 years with noone caring. If the documentation stated it was O(n), or benchmarks tested it was fast, then it being slow would become a bug. As is, it's just what it is.
- aetherson 10y ago
  Well, probably the reason it lasted for about 4 years with no one caring is because .reject! is a fairly rarely used function.
flukus 10y ago
Can you point out where in the function definition this was defined?

choward 10y ago

If it's n^2 it may never return in your lifetime. Does the code work? Nobody knows. It this situation you may consider it a bug.

CanSpice 10y ago
O() doesn't say anything about how long it'll take. O(n) may never return in your lifetime too.
- hamandcheese 10y ago
  O(1) might not either :)
  - dr_win 10y ago
    Because you might be dead already. Which would be a weird edge case.
    - pmiller2 10y ago
      No. O(1) just means the algorithm always takes no more than some arbitrary, but fixed amount of time to complete, regardless of the size of the input. That fixed amount of time could be a billion years (or more).
  - astrodust 10y ago
    It consistently takes a billion years, it's O(1).
- chrisdevereux 10y ago
  O(0) would though, right?
  - lvh 10y ago
    You mean O(1) (alternatively, O(k)) -- from the definition of Big O notation, O(0) is nonsensical. But even then; O(1) just means "constant time", it does not mean "soon."

perfmode 10y ago

Unfortunately, it's not that simple. It's really depends on context. There are cases where accidental quadratic complexity would definitively be considered a bug. If a fleet of GitHub servers were burning cycles due to a quadratic reject!, I'm pretty sure the engineers would classify the misbehavior as such.

pdw 10y ago

O(n^2) algorithms are insidious in that they will work fine on test data, but will ruin performance when there's an unusually large input in production. They're landmines in your code.

eco 10y ago
One of the more interesting approaches I've seen lately is in Andrei Alexandrescu's "An Algebra for Expressing Time Complexity of Generic Functions" article[1]. The gist is you (or more likely, the library writer) annotate functions with their complexity guarantees then you can make static assertions about your runtime performance expectations which result in a compile time error if the algorithms/data structures being used cannot meet them. In theory that would prevent the O(n^2) landmine. 1. http://erdani.com/d/bigo.html http://erdani.com/d/bigo.html
throwaway1579 10y ago
You do know that the most popular general-purpose, comparison-based sorting algorithm quicksort has a worst case complexity of O(n^2), right?
- minitech 10y ago
  Good implementations tend to address this with introspection, randomization, etc..
gkya 10y ago
Certainly. But does it make it a bug?
zerr 10y ago
Alternatively, it will ruin performance on artificially large test data, but will work fine in production :)

parenthephobia 10y ago

It's not a bug in the method, but it should be. A peeve I have with Ruby is that methods in the standard library don't have defined big-O complexities. If they did, I don't think reject! would have been specified to be O(n²), and so it would be a bug.

lotyrin 10y ago
I'd love a type-system alike checking feature of a language that made you specify (and would verify) time complexity of functions Then in reviews its explicit when someone's doing something dumb (specifying high complexity for new algos) at compile time if a lower-complexity function calls a higher complexity one with the same sized input, or in CI when an algorithm isn't within the complexity it claims to be (experimentally)
- al2o3cr 10y ago
  I suspect the "verify" part of that is going to slam head-first into the Halting Problem, given that some of the quadratic behavior only happens (see the blog) for particular patterns of use or input data. You'd also likely want to somehow encode space complexity as well, otherwise silly things like "precompute every possible result and put it in a giant lookup table" will register as "O(1)".

nikic 10y ago

If the function was implemented as an infinite loop, would you consider the code working correctly as well? After all, the result after execution of the function is always correct (ex falso quodlibet).

gkya 10y ago
An infinite loop is a loop that never ends, it'd not be possible to implement a function that's expected to return in terms of an infinite loop. Here the algorithm is quadratic but will, theoretically, always complete. Thus there is no bug, but a performance problem. I think that a bug is a mistake in a programme that causes erroneous behaviour. Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed? I'd rather call this a mistake as long as the output from the function is as expected. I'm not saying that it's a negligible mistake to use a quadratic algo where there is a linear one though. Just that I doubt it is fundamentally a bug.
- dbaupp 10y ago
  > Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed? This only makes sense if you completely ignore context, which doesn't make any sense at all. The point/"bug"/mistake here is using a quadratic algorithm when it isn't necessary, not just the fact that the algorithm is quadratic. If something can be solved in O(1) time, it's a mistake to use an O(n) algorithm, and similarly, if something can be solved in O(2^(n!)) time, it's a mistake to use a O(9999^(n!)) algorithm (assuming constant factors are of similar orders of magnitude etc, as they are in the OP).

baddox 10y ago

Would a sleep(100000) at the top of the method implementation not count as a bug either?

gkya 10y ago
I don't see how this is relevant. That certainly is a bug if such a call is not a part of the algorithm. Here the function is correct in the sense that it returns as expected.
- baddox 10y ago
  The function with a long sleep also returns as expected, and is just as much a part of that particular algorithm as the quadratic implementation.
- astrodust 10y ago
  Quadratic performance is not part of the algorithm. End of story.
  - gkya 10y ago
    I am not your student and this is not a classroom. I really dislike that tone.
nilved 10y ago
How is that a bug? Unless sleep was a typo or something. A bug isn't related to performance, a bug is just a mistake.
- baddox 10y ago
  This quadratic implementation was a mistake.
  - nilved 10y ago
    No it wasn't, the developer probably knew exactly what they were doing.

mkonecny 10y ago

If it can take down your webserver due to unexpected CPU overload, then I would consider it bug

wuch 10y ago

Programs without specification have only surprising behaviour no bugs. As far as I can see "reject!" does not specify complexity, so in this sense it would be completely fine. Additionally it claims to change the array instantly every time the block is called, which doesn't seem to give any other options than making it at least quadratic (presuming flat representation for arrays). This feels quite overspecified as accessing the array from within the block seems quite unusual case to cater for. Though, this behaviour was changed after all which leaves me wondering how much Ruby people care about backward compatibility.