3 ms·

I am sorry... but no, the article is interesting and well written, but it has nothing to do with big O notation. Random access in memory is still in O(1), it do

I am sorry... but no, the article is interesting and well written, but it has nothing to do with big O notation. Random access in memory is still in O(1), it doesn't depend on the size of the data structure (I am assuming that is the "n" the author talk about by pretending that a memory access is O(sqrt(n)). Even if you have a very complex memory architecture with 15 caching levels, spread all over the world, if you have a maximum of 5 day delay for accessing your memory through the mail, it will still be O(1), because 5 day is constant, it does not depend on the size of the data structure. The "n" the author is really talking about may be the depth of the cache hierarchy.

deleted 10y ago
[deleted]
stdbrouw 10y ago
It's just a fun way to frame a conversation about cache/ram latency, relax.
- justAlittleCom 10y ago
  I see the point and it is interesting, it's just not big O ^^ If I replace in my head all O(thing) by MyCustomComplexityMeasureYetToBeDefinedProperly(thing) then it makes perfect sens.
  - exelius 10y ago
    Big O is basically that. Big O notation predates computers (late 19th/early 20th century) -- it's simply a notation to signify how a problem scales in complexity in relation to the size of the data set. I would argue that multi-level memory access is itself a problem that scales complexity in the same way.
xrstf 10y ago
Are your questions maybe answered in part IV of the series, the FAQ[1]? [1] http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-part-iv http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-pa...
ricardobeat 10y ago
What he tried to show is precisely that in practice it does depend on the size of the data structure.
- deleted 10y ago
  [deleted]
fisherjeff 10y ago
...but if you have a significantly smaller dataset, you don't need such a complex caching architecture, which brings faster access times at the margins. So even in your example, worst-case access time scales with dataset size.
DanWaterworth 10y ago
There are models like the Transdichotomous model [1], where the properties of the machine vary based on the problem. That seems to be what is happening here. [1] https://en.wikipedia.org/wiki/Transdichotomous_model https://en.wikipedia.org/wiki/Transdichotomous_model
arielb1 10y ago
You can say everything is O(1) because nothing would ever take more than `2^128` seconds. In practice, O-notation means "with a reasonably small constant".
xenadu02 10y ago
> but it has nothing to do with big O notation If this has nothing to do with Big-O then Big-O is a useless concept and should be abandoned. You may be interested in measuring the number of CPU instructions it takes to traverse a linked list in which case O(N) is accurate. Personally I care about how much wall-clock time it takes in which case a linked list is very much not O(N) and the larger the list the further away from O(N) it becomes. There is a rather large delta between a 10K and a 100MB linked list. You can go test this for yourself right now. > Random access in memory is still in O(1) No it isn't. Random access only looks like O(1) at certain plateaus, like size of L1, size of L2, size of L3, size of RAM on the local NUMA node, size of RAM on neighboring NUMA nodes, size of RAM on distant NUMA nodes, size of SSD, size of HDD, size of NAS locally connected, size of NAS distantly connected, size of cloud storage. Constants can matter in Big-O, especially if they are very large. Compared to the number of instructions 3Ghz CPU must execute to do a hash lookup, accessing RAM has a relatively large constant factor and execution time can be massively impacted by sub-optimal RAM access patterns.
- krinchan 10y ago
  Except Big-O was never intended to describe wall clock time. As soon as you try to use Big-O to describe a number of concrete units you'll fail. Big-O is purely a comparative measure, this algorithm vs. that algorithm. As it stands, it is fairly meaningless outside of purely academic exercises. EDIT: I mean, consider that the entire basis for Big-O notation assumes that every "operation" are always equal. Adding is always constant. Big-O is very hand wavey and claiming the constants matter is to invent an entirely new notation.
  - Jweb_Guru 10y ago
    Big-O isn't handwavey, it was absolutely intended to describe (among other things!) wall-clock time, and the article isn't just talking about constants. Also, many operations (like adding) are constant-time on modern computers, outside of memory hierarchy effects, ALU stalls, etc., since they're bound to finish within exactly one clock-cycle.
    - 10y ago

deleted 10y ago

[deleted]

stdbrouw 10y ago

It's just a fun way to frame a conversation about cache/ram latency, relax.

justAlittleCom 10y ago
I see the point and it is interesting, it's just not big O ^^ If I replace in my head all O(thing) by MyCustomComplexityMeasureYetToBeDefinedProperly(thing) then it makes perfect sens.
- exelius 10y ago
  Big O is basically that. Big O notation predates computers (late 19th/early 20th century) -- it's simply a notation to signify how a problem scales in complexity in relation to the size of the data set. I would argue that multi-level memory access is itself a problem that scales complexity in the same way.

xrstf 10y ago

Are your questions maybe answered in part IV of the series, the FAQ[1]? [1] http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-part-iv http://www.ilikebigbits.com/blog/2015/2/9/the-myth-of-ram-pa...

ricardobeat 10y ago

What he tried to show is precisely that in practice it does depend on the size of the data structure.

deleted 10y ago
[deleted]

fisherjeff 10y ago

...but if you have a significantly smaller dataset, you don't need such a complex caching architecture, which brings faster access times at the margins. So even in your example, worst-case access time scales with dataset size.

DanWaterworth 10y ago

There are models like the Transdichotomous model [1], where the properties of the machine vary based on the problem. That seems to be what is happening here. [1] https://en.wikipedia.org/wiki/Transdichotomous_model https://en.wikipedia.org/wiki/Transdichotomous_model

arielb1 10y ago

You can say everything is O(1) because nothing would ever take more than `2^128` seconds. In practice, O-notation means "with a reasonably small constant".

xenadu02 10y ago

> but it has nothing to do with big O notation If this has nothing to do with Big-O then Big-O is a useless concept and should be abandoned. You may be interested in measuring the number of CPU instructions it takes to traverse a linked list in which case O(N) is accurate. Personally I care about how much wall-clock time it takes in which case a linked list is very much not O(N) and the larger the list the further away from O(N) it becomes. There is a rather large delta between a 10K and a 100MB linked list. You can go test this for yourself right now. > Random access in memory is still in O(1) No it isn't. Random access only looks like O(1) at certain plateaus, like size of L1, size of L2, size of L3, size of RAM on the local NUMA node, size of RAM on neighboring NUMA nodes, size of RAM on distant NUMA nodes, size of SSD, size of HDD, size of NAS locally connected, size of NAS distantly connected, size of cloud storage. Constants can matter in Big-O, especially if they are very large. Compared to the number of instructions 3Ghz CPU must execute to do a hash lookup, accessing RAM has a relatively large constant factor and execution time can be massively impacted by sub-optimal RAM access patterns.

krinchan 10y ago
Except Big-O was never intended to describe wall clock time. As soon as you try to use Big-O to describe a number of concrete units you'll fail. Big-O is purely a comparative measure, this algorithm vs. that algorithm. As it stands, it is fairly meaningless outside of purely academic exercises. EDIT: I mean, consider that the entire basis for Big-O notation assumes that every "operation" are always equal. Adding is always constant. Big-O is very hand wavey and claiming the constants matter is to invent an entirely new notation.
- Jweb_Guru 10y ago
  Big-O isn't handwavey, it was absolutely intended to describe (among other things!) wall-clock time, and the article isn't just talking about constants. Also, many operations (like adding) are constant-time on modern computers, outside of memory hierarchy effects, ALU stalls, etc., since they're bound to finish within exactly one clock-cycle.
  - 10y ago