News for hackers. Stuff that matters.
Re:WTF Is Big O Notation? by gpm on Monday March 25, 2019 @09:54PM (#19488618)
This seems like a good time to bring up one of my pet peeves about big O notation.

Every theoretical model I've ever seen says that indexing into n bits of memory takes O(1) time. That's obviously impossible:

- The pointer you need to read is log(n) bits.

- The physical memory is at best O(n^(1/3)) distance away from the CPU, and thus takes that much time to get back to you. In reality it's probably O(n^(1/2)) because we build on flat planes (once you start talking about petabytes of data anyways).

Maybe this doesn't matter in practice, because the constants associated with these are small enough (but are they, how many memory/disk bound applications are there? How much extra performance could we squeeze out by using 16/32 bit pointers for small arrays?). It certainly doesn't matter in theory where things work like we say they do regardless of the physical reality. But it annoys me that it's so obviously wrong.

Re:WTF Is Big O Notation? by anon946 on Monday March 25, 2019 @10:10PM (#19488707)
Well, it's "wrong", but there's the saying that all models are wrong, but some are useful. If time complexity analysis had to include physical distance, then it would perhaps be less wrong, but also much less useful.

That said, "time complexity" is a bit of a misnomer anyway. It's often implied, but underneath, there is a specific operation. For example, when we say that merge sort is O(N lg N), we mean in number of comparison operations.

Re:WTF Is Big O Notation? by deathanatos on Monday March 25, 2019 @10:09PM (#19488699)
There was a decent article exploring the timing between memory accesses, and when they started taking longer b/c you hit L2 cache, L3 cache, main RAM, swap, etc., and eventually showed how if you really graphed the access times, the overarching "curve" they followed was square/cube root¹; that is, real world hardware obeys the laws of physics.

My googling dug up [1], but I'm not sure if that's it or not.

My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about.

> 16/32 bit pointers for small arrays?

It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out.

[1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

¹I'm a software engineer, not a physicist.

Re:WTF Is Big O Notation? by mwfunk on Monday March 25, 2019 @10:27PM (#19488791)
Part of it is that there's very casual, conversational usages of Big O vs. much more formal usages when trying to actually quantify performance.

Conversational Big O tends to include a lot of spherical cows (https://en.wikipedia.org/wiki/Spherical_cow), because when Big O comes up in conversation, people are more likely to be talking in generalities about high level designs. More detail could be counterproductive in that context.

When someone is actually trying to quantify and predict performance of an algorithm, then the other extreme becomes desirable- the more detailed and specific the function, the better.

Re:WTF Is Big O Notation? by gpm on Monday March 25, 2019 @10:34PM (#19488822)
Ya, I'm directly addressing non-conversational use of Big O notation here, including the areas of academia I'm familiar with and know people in.
Re:WTF Is Big O Notation? by jhanschoo on Tuesday March 26, 2019 @04:26AM (#19490054)
In industry there is indeed a hand-waving of the size of addressing. IMO for industry this is not too important since a lg n multiplicative factor is peanuts.

With respect to the space problem, for some problems researchers don't care about it so much because it only means that it is a polynomial factor slower. For problems where the degree of the polynomial is important, theorists typically work with variants of Turing machines and need to specify which variant they are using, which typically do not allow random access, so this does not become important. Of course, random-access Turing machines are also studied that violate the physical constraint you mentioned.

Re:WTF Is Big O Notation? by umanwizard on Tuesday March 26, 2019 @05:47PM (#19496336)
Actually the size of indices can be important in real life. For example, on Nvidia GPUs, a kernel that indexes data with 64-bit indices will usually be much slower than one that uses 32-bit indices.

(Hard to argue that this is related to big-O since there are only two data points, but I'm just pointing out that index size is in fact a real-world concern).

Re:WTF Is Big O Notation? by giucal on Wednesday March 27, 2019 @05:18AM (#19499174)
I think they don't matter because:

1. they are all fixed or bounded quantities;

2. all algorithms are subject to them.

On the other hand, in practice, the input size is also bounded. You deal not with arbitrarily long arrays, for example, since memory is not infinite.

So, I think, asymptotic time complexity is meaningful as long as the inputs we are considering can grow so much -- while remaining bounded -- that a linearithmic algorithm indeed outperforms, say, a quadratic one for a large and relevant class of inputs.

And that may be why computational models make those assumptions; but I'm not remotely sure.

Re:WTF Is Big O Notation? by briankelly on Monday March 25, 2019 @10:07PM (#19488694)
There's a nice series of articles on this here: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
Re:WTF Is Big O Notation? by gpm on Monday March 25, 2019 @10:08PM (#19488697)
Oh cool, hadn't seen that!
Re:WTF Is Big O Notation? by heinrich5991 on Monday March 25, 2019 @10:09PM (#19488702)
In academia, you usually see O(log n) for addressing. Since it doesn't really seem to matter for real-world performance, we just assume it's O(1) in practice.
Re:WTF Is Big O Notation? by gpm on Monday March 25, 2019 @10:19PM (#19488752)
You're probably seeing a different part of academia than I am. The portions of CS academia I'm familiar with don't do O(log n) addressing.