3 ms·

Does anyone know what an "O(n) issue" is? I can think of a few possible meanings in the usage here, but I've never heard it before and they all seem wrong.

by cmrx64 11y ago

acveilleux 11y ago
Using a linked-list where the actual access pattern is random and an hash table is more suitable would be the most obvious, especially since this is C code. Similar things includes C-style string functions like strlen() and so on that require iterating over an unknown length array. Caching (or better avoiding!) this work can save a lot of computing time. Example from libgit2: https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f12a89c2518c1a07c0dc94c https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f... In fact C-style string is a rich source of O(n) performance issues. And git is full of strings like filenames.
- cmrx64 11y ago
  To me, I would have called that an "O(n^2)" (or whatever the proper non-linear order is) issue. The issue isn't that the algorithm is O(n), but that it's not O(n) when it could be! The other interpretations by andrewaylett and daveguy seem to be more accurate (and also agrees with my own thinking). But I could also see it being used for "the asymptotic complexity was hiding a huge constant". Have you heard your interpretation used in the wild?
andrewaylett 11y ago
It's an issue where processing something took O(n) time, when an algorithm to process it asymptotically more quickly (say O(log n)) would be more appropriate. The old code probably works properly for the average case, but will really blow up on pathological cases. My best personal example was an optimisation pass that turned out to be exponential in the worst case. On average `n` was small, so no-one cared, until a pathological case came up where compile time ballooned to over half-an-hour. Working out that the operation could be done in a linear way only shaved a fraction of a second off the average case, but brought the half-hour case down to a few seconds.
daveguy 11y ago
"O(n) issue" is generic for some asymptotic optimization issue. It doesn't literally mean it was running in O(n) and there was a better O(n log n) solution. It could be O(n^2) and there was an O(n) solution or O(n) when there was an O(log n) solution or O(n!) when there was an O(n^2) solution. It just means there was a poor algorithm choice / design decision for some part of the code when a more efficient option is available.
bado 11y ago
It's notation denoting the performance of an algorithm. See https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation

Does anyone know what an "O(n) issue" is? I can think of a few possible meanings in the usage here, but I've never heard it before and they all seem wrong.

by cmrx64 11y ago

Does anyone know what an "O(n) issue" is? I can think of a few possible meanings in the usage here, but I've never heard it before and they all seem wrong.

acveilleux 11y ago

Using a linked-list where the actual access pattern is random and an hash table is more suitable would be the most obvious, especially since this is C code. Similar things includes C-style string functions like strlen() and so on that require iterating over an unknown length array. Caching (or better avoiding!) this work can save a lot of computing time. Example from libgit2: https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f12a89c2518c1a07c0dc94c https://github.com/libgit2/libgit2/commit/7132150ddf7a883c1f... In fact C-style string is a rich source of O(n) performance issues. And git is full of strings like filenames.

cmrx64 11y ago
To me, I would have called that an "O(n^2)" (or whatever the proper non-linear order is) issue. The issue isn't that the algorithm is O(n), but that it's not O(n) when it could be! The other interpretations by andrewaylett and daveguy seem to be more accurate (and also agrees with my own thinking). But I could also see it being used for "the asymptotic complexity was hiding a huge constant". Have you heard your interpretation used in the wild?

andrewaylett 11y ago

It's an issue where processing something took O(n) time, when an algorithm to process it asymptotically more quickly (say O(log n)) would be more appropriate. The old code probably works properly for the average case, but will really blow up on pathological cases. My best personal example was an optimisation pass that turned out to be exponential in the worst case. On average `n` was small, so no-one cared, until a pathological case came up where compile time ballooned to over half-an-hour. Working out that the operation could be done in a linear way only shaved a fraction of a second off the average case, but brought the half-hour case down to a few seconds.

daveguy 11y ago

"O(n) issue" is generic for some asymptotic optimization issue. It doesn't literally mean it was running in O(n) and there was a better O(n log n) solution. It could be O(n^2) and there was an O(n) solution or O(n) when there was an O(log n) solution or O(n!) when there was an O(n^2) solution. It just means there was a poor algorithm choice / design decision for some part of the code when a more efficient option is available.

bado 11y ago

It's notation denoting the performance of an algorithm. See https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation