7 ms·

This article has a strange take on algorithmic scaling. L1, L2, LL, MM, Disk, NetDisk ..., GalacticRAM. Wow, you actually expected traversing ‘system boundari

This article has a strange take on algorithmic scaling. L1, L2, LL, MM, Disk, NetDisk ..., GalacticRAM. Wow, you actually expected traversing ‘system boundaries’ with distinct access costs and maintain theoretical scaling? An algorithm that is O(n) will be O(n) in L1, O(n) in L2, ,..., and yes O(n) in GalacticRAM. Each (sub-)system traversal is due to exceeding capacity limits. There is likely a more interesting mathematical result buried in here, since we see that a series of sub-systems with relative constant order of magnitude increases in access costs in aggregate transforms f -> f’ with this interesting n^.5 term showing up instead of the logs.

karmakaze 3y ago
This is the 2nd post I've seen recently submitted to HN that plays fast and loose with big-O notation. It has a defined meaning. If someone wants to talk about something else, great use different notation. People already seem to have some trouble grokking big-O and we don't need to muddy it with 'ad-hack' usages.
- Dylan16807 3y ago
  According to the exact literal meaning, every algorithm you ever run on your computer is O(1), because your computer is finite. The same can be applied to the reachable universe. Context is inevitable.
  - karmakaze 3y ago
    ...which becomes meaningless and not useful. There is a whole area of mechanical sympathy and cache aware or cache oblivious algorithms that are well worth discussing and learning, but we don't need to use big-O notation to do so.
    - Dylan16807 3y ago
      It's useful notation even when we're not dealing with mathematical infinities. Unless you have a better alternative for the same purpose, "don't use it" is a pretty bad answer. It's being used for pretty much the same meaning. Not meaningless at all.
      - karmakaze 3y ago
        Ending up at sqrt(n) doing a visual linear regression on a log plot doesn't mean the same thing to me. It would be better to frame the discussion as an illustration of the limitations of big-O analysis in real world cases, than to say that the big-O of a linked-list is really O(sqrt(N))
        Dylan16807 3y ago
        There's certainly a difference between showing a plot such that it seems to be O(sqrt(N)) and proving that it's O(sqrt(N)). But you're still saying O(sqrt(N)) in both of those. I think it's useful to use the term O(sqrt(N)). It's the best notation for the job.
    - 38321003thrw 3y ago
      I have a video link to an MIT lecture that disproves your assertion. Cache aware, cache adaptive, and cache oblivious algorithms are definitively analyzed using big O. In fact it is big O notions that provide assurances about these approaches. Mechanical sympathy has little (if anything) to do with big-O, btw. LMAX, the poster child of mechanical sympathy, is really about minimizing the use of memory coherence machinery and not taking the substantial latency hits.
  - j16sdiz 3y ago
    Where is my tuning machines?
  - kaba0 3y ago
    That’s not true - an algorithm is a mathematical “entity”, it can and is infinite. The actual implementation on a real machine might not run forever, but there is no such kind of limit with math.
    - Dylan16807 3y ago
      You can't run the abstract infinite entity. The article was specifically talking about putting algorithms onto real machines and the speed consequences. This creates a new version of the algorithm with certain limits. And because of these limits, there is a maximum runtime for any halting code, and it is a constant number.
  - tjoff 3y ago
    No? I'm tired and it was way too long since I dealed with Big O so someone will surely correct me. Your computer being finite is irrelevant. Big O is about growth factor. Just because you are capped at value X (< infinity) does not mean that every value below X has the same characteristics. If it did, sure, you are O(1). But if it is N^2 it will still be N^2 even if your machine only has resources for N < 12.
    - kmill 3y ago
      Big O is about the eventual behavior for large enough N. An algorithm is O(N^2) is for sufficiently large inputs the running time is < c * N^2, for some fixed constant c. That's a really weak guarantee for practical purposes -- it allows an algorithm to take stupidly long amounts of time on all practical inputs, so long as eventually it's got a running time with the given bound. The colloquial use of big O as a general growth factor doesn't hold up to its definition, if you want to be sure it's valid for small inputs too. I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation.
      - Dylan16807 3y ago
        > I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation. The difference between "everything is O(1)" and "you're not allowed to use O" is pretty minor anyway. Either way it takes a lot of very useful analysis and throws it out the window because a particular branch of math was being too pedantic about needing infinity. Use big O anyway. It works fine. It's a good tool even within the limits of real machines. If you're not abusing it on purpose, it tells you useful information in the exact same way that the pure math version does.
        karmakaze 3y ago
  - lesuorac 3y ago
    This is typically why we don't pick N to mean all of the resources in the universe. I guess you're the kind of guy that chooses to uses not 8-bit bytes in an interview? Instead typically it's the amount of accesses into some array. Other times people get cute and it's `log2(input length)` so somebodies algorithm could be O(N) while if N was just `input length` then it'd be N^2.
    - Dylan16807 3y ago
      This isn't about picking N. This is saying "No matter what N you pick, your runtime will be smaller than roughly 2^[number of atoms in the reachable universe]" (Because if you hit the same state twice, you're stuck in a loop that will never halt.) So yes, your algorithm is bound by O(N^2), and that's the number that matters on practical computers... but it's also bound by O(1) with a stupidly large constant. So it's O(1). > I guess you're the kind of guy that chooses to uses not 8-bit bytes in an interview? Dude, I'm here specifically to argue against insisting on the exact literal meaning, and to choose the practical option.
- deleted 3y ago
  [deleted]
Georgelemental 3y ago
O(n) describes limiting behavior as n → ∞. In the process of getting to infinity, you will necessarily cross capacity limits.
- 38321003thrw 3y ago
  We strongly & emphatically disagree. Analysis assumes a homogeneous computational regime for the said “infinite” store otherwise it is basically meaningless. If this assumption is known not to hold (for example in considering the role of caching in algorithms), this is specifically incorporated in the analysis. See “cache models” and cache-oblivious algorithms for examples. Cache-Oblivious Structures I, MIT, by Erik Demaine https://www.youtube.com/watch?v=bY8f4DSkQ6M https://www.youtube.com/watch?v=bY8f4DSkQ6M Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis https://www.youtube.com/watch?v=eB_UH7tLomw https://www.youtube.com/watch?v=eB_UH7tLomw Analysis of Recursive Cache-Adaptive Algorithms, Andrea Lincoln, 2015 (thesis) http://dspace.mit.edu/bitstream/handle/1721.1/100630/933227456-MIT.pdf http://dspace.mit.edu/bitstream/handle/1721.1/100630/9332274...
  - CyberDildonics 3y ago
    We strongly & emphatically disagree Why are you saying 'we' in your comment? computational regime I think you mean environment instead of regime. the said “infinite” store None of this is true for basic O notation, it's just what exponent the algorithm carries on the number of elements. Big-O notation doesn't even have to do with this article, it's just showing that memory access isn't strictly constant. This all seems like you're trying to argue something that isn't a part of this thread and I'm not sure what that is.
CyberDildonics 3y ago
First, there is no such thing as "galactic RAM". Second, there are three images of the same graph, each showing how access times aren't linear when they cross cache boundaries. There aren't any transforms and there aren't any aggregate transforms f -> f’. Third, algorithmic complexity is about abstract amounts of work relative to amount of elements. It isn't about "a series of sub-systems" or "galactic RAM". This article shouldn't use big O notation because it isn't really about algorithms, it is just about non constant access times.
- deleted 3y ago
  [deleted]
- 38321003thrw 3y ago
  > First, there is no such thing as “galactic RAM” And there goes my plans for floating a “secondary system wrapper” around openGRAM’s apis and VCing my way to the top of the unicorn charts. Oh well. “This is why I come to hn”.

karmakaze 3y ago

This is the 2nd post I've seen recently submitted to HN that plays fast and loose with big-O notation. It has a defined meaning. If someone wants to talk about something else, great use different notation. People already seem to have some trouble grokking big-O and we don't need to muddy it with 'ad-hack' usages.

Dylan16807 3y ago
According to the exact literal meaning, every algorithm you ever run on your computer is O(1), because your computer is finite. The same can be applied to the reachable universe. Context is inevitable.
- karmakaze 3y ago
  ...which becomes meaningless and not useful. There is a whole area of mechanical sympathy and cache aware or cache oblivious algorithms that are well worth discussing and learning, but we don't need to use big-O notation to do so.
  - Dylan16807 3y ago
    It's useful notation even when we're not dealing with mathematical infinities. Unless you have a better alternative for the same purpose, "don't use it" is a pretty bad answer. It's being used for pretty much the same meaning. Not meaningless at all.
    - karmakaze 3y ago
      Ending up at sqrt(n) doing a visual linear regression on a log plot doesn't mean the same thing to me. It would be better to frame the discussion as an illustration of the limitations of big-O analysis in real world cases, than to say that the big-O of a linked-list is really O(sqrt(N))
      - Dylan16807 3y ago
        There's certainly a difference between showing a plot such that it seems to be O(sqrt(N)) and proving that it's O(sqrt(N)). But you're still saying O(sqrt(N)) in both of those. I think it's useful to use the term O(sqrt(N)). It's the best notation for the job.
  - 38321003thrw 3y ago
    I have a video link to an MIT lecture that disproves your assertion. Cache aware, cache adaptive, and cache oblivious algorithms are definitively analyzed using big O. In fact it is big O notions that provide assurances about these approaches. Mechanical sympathy has little (if anything) to do with big-O, btw. LMAX, the poster child of mechanical sympathy, is really about minimizing the use of memory coherence machinery and not taking the substantial latency hits.
- j16sdiz 3y ago
  Where is my tuning machines?
- kaba0 3y ago
  That’s not true - an algorithm is a mathematical “entity”, it can and is infinite. The actual implementation on a real machine might not run forever, but there is no such kind of limit with math.
  - Dylan16807 3y ago
    You can't run the abstract infinite entity. The article was specifically talking about putting algorithms onto real machines and the speed consequences. This creates a new version of the algorithm with certain limits. And because of these limits, there is a maximum runtime for any halting code, and it is a constant number.
- tjoff 3y ago
  No? I'm tired and it was way too long since I dealed with Big O so someone will surely correct me. Your computer being finite is irrelevant. Big O is about growth factor. Just because you are capped at value X (< infinity) does not mean that every value below X has the same characteristics. If it did, sure, you are O(1). But if it is N^2 it will still be N^2 even if your machine only has resources for N < 12.
  - kmill 3y ago
    Big O is about the eventual behavior for large enough N. An algorithm is O(N^2) is for sufficiently large inputs the running time is < c * N^2, for some fixed constant c. That's a really weak guarantee for practical purposes -- it allows an algorithm to take stupidly long amounts of time on all practical inputs, so long as eventually it's got a running time with the given bound. The colloquial use of big O as a general growth factor doesn't hold up to its definition, if you want to be sure it's valid for small inputs too. I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation.
    - Dylan16807 3y ago
      > I'm in agreement that saying algorithms on computers are all O(1) doesn't make much sense. In a finite memory model, it's impossible to solve big problems, so the running time function becomes undefined for big enough inputs, so big O becomes completely inappropriate in this situation. The difference between "everything is O(1)" and "you're not allowed to use O" is pretty minor anyway. Either way it takes a lot of very useful analysis and throws it out the window because a particular branch of math was being too pedantic about needing infinity. Use big O anyway. It works fine. It's a good tool even within the limits of real machines. If you're not abusing it on purpose, it tells you useful information in the exact same way that the pure math version does.
      - karmakaze 3y ago
- lesuorac 3y ago
  This is typically why we don't pick N to mean all of the resources in the universe. I guess you're the kind of guy that chooses to uses not 8-bit bytes in an interview? Instead typically it's the amount of accesses into some array. Other times people get cute and it's `log2(input length)` so somebodies algorithm could be O(N) while if N was just `input length` then it'd be N^2.
  - Dylan16807 3y ago
    This isn't about picking N. This is saying "No matter what N you pick, your runtime will be smaller than roughly 2^[number of atoms in the reachable universe]" (Because if you hit the same state twice, you're stuck in a loop that will never halt.) So yes, your algorithm is bound by O(N^2), and that's the number that matters on practical computers... but it's also bound by O(1) with a stupidly large constant. So it's O(1). > I guess you're the kind of guy that chooses to uses not 8-bit bytes in an interview? Dude, I'm here specifically to argue against insisting on the exact literal meaning, and to choose the practical option.
deleted 3y ago
[deleted]

Georgelemental 3y ago

O(n) describes limiting behavior as n → ∞. In the process of getting to infinity, you will necessarily cross capacity limits.

38321003thrw 3y ago
We strongly & emphatically disagree. Analysis assumes a homogeneous computational regime for the said “infinite” store otherwise it is basically meaningless. If this assumption is known not to hold (for example in considering the role of caching in algorithms), this is specifically incorporated in the analysis. See “cache models” and cache-oblivious algorithms for examples. Cache-Oblivious Structures I, MIT, by Erik Demaine https://www.youtube.com/watch?v=bY8f4DSkQ6M https://www.youtube.com/watch?v=bY8f4DSkQ6M Closing the Gap Between Cache-oblivious and Cache-adaptive Analysis https://www.youtube.com/watch?v=eB_UH7tLomw https://www.youtube.com/watch?v=eB_UH7tLomw Analysis of Recursive Cache-Adaptive Algorithms, Andrea Lincoln, 2015 (thesis) http://dspace.mit.edu/bitstream/handle/1721.1/100630/933227456-MIT.pdf http://dspace.mit.edu/bitstream/handle/1721.1/100630/9332274...
- CyberDildonics 3y ago
  We strongly & emphatically disagree Why are you saying 'we' in your comment? computational regime I think you mean environment instead of regime. the said “infinite” store None of this is true for basic O notation, it's just what exponent the algorithm carries on the number of elements. Big-O notation doesn't even have to do with this article, it's just showing that memory access isn't strictly constant. This all seems like you're trying to argue something that isn't a part of this thread and I'm not sure what that is.

CyberDildonics 3y ago

First, there is no such thing as "galactic RAM". Second, there are three images of the same graph, each showing how access times aren't linear when they cross cache boundaries. There aren't any transforms and there aren't any aggregate transforms f -> f’. Third, algorithmic complexity is about abstract amounts of work relative to amount of elements. It isn't about "a series of sub-systems" or "galactic RAM". This article shouldn't use big O notation because it isn't really about algorithms, it is just about non constant access times.

deleted 3y ago
[deleted]
38321003thrw 3y ago
> First, there is no such thing as “galactic RAM” And there goes my plans for floating a “secondary system wrapper” around openGRAM’s apis and VCing my way to the top of the unicorn charts. Oh well. “This is why I come to hn”.