Hacker News Reader

Comment by decasia | Hacker News Reader

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation.

Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption is incorrect.

There's no way to develop software without making assumptions, some of which inevitably turn out to be incorrect, so I don't think there is any great shame in having that happen, in itself. But better docs could help us make better assumptions with less effort, at least.

View on HN

Keeping track of algorithmic complexity would be nice as a language and/or static analysis feature. If you wanted to be exact or do it for a language with complex metaprogramming I assume it would be a nightmare to implement. Absent those complications and especially if you always reduced it to O(1), O(n), O(log(n)), etc it might not even be that difficult given the potential advantages.

The difficulty here is "define n". And I don't mean that facetiously. You have a string parsing lib. It is, for reasons, quadratic over the number of strings parsed, and linear per string.

This is overall n^3, but that's meaningless because there actually isn't just one n. So, more m^2 * n. That means you can't reduce it to anything, because you want to keep both components. (Because, say, you know it will only ever be called with a single string).

But then, in the next app, this gets called and reinitialized once per file. And the routine handling files, for reasons beyond our ken, is (n lg n). We're now at k * log(k) * m^2 * n.

And so, over any sufficiently long call chain, "what is n" is the overriding question - string length, number of strings, number of files? Not "how complex is the algorithm", because you want to optimize for what's relevant to your use case.

It would be a huge step to simply follow the call tree and report the depth of nested loops for each branch. You could then check what N is at each level.

The trick is knowing where the nested loops are since they can be spread across functions.

I had a function that scaled as N^2, but it was creating a list of that size as well. Then it called a function to remove duplicates from that list. That function was N^2, which meant the whole thing was actually N^4. And now that I think of it, those loops were not nested... I rewrote the first part to no create duplicates and deleted the quadratic deduplication. Now its N^2, but it has to be.

I guess you're right. Keeping track of it all is required for the information to be meaningful enough. Still seems doable to me, assuming the functions are pure.

Here's another crazy idea: keeping track of this while taking into consideration aggressive compiler optimizations.

There is no general solution to deciding whether a program is O(n^k).[1] So either your static analysis won't know the answer for some programs or report a wrong bound, or report a ridiculous overestimate.

[1] https://cstheory.stackexchange.com/questions/5004/are-runtim...

So? Static analysis doesn't need to always produce an answer, only produce an answer most of the time. The question isn't whether you can do it in general for all inputs (this is not possible for basically anything you would want to know), it's whether you can do it enough of the time on the kind of code which people actually write.

Can you point me towards some source code where a human can't find the algorithmic complexity?

Humans can't tell you whether this program will run forever on any particular (positive integer) input, or whether all inputs terminate.

  def collatz(n):
      while n != 1:
          print(n)
      if n % 2 == 0:
          n = n // 2 
      else:
          n = n * 3 + 1

      print(1)

I think your indentation needs to be adjusted? Like so:

  def collatz(n):
      while n != 1:
          print(n)
          if n % 2 == 0:
              n = n // 2 
          else:
              n = n * 3 + 1

      print(1)

Otherwise, n = 1 terminates, and n != 1 gets stuck looping at lines 2-3.

Thank you!

It's not hard to implement the construction in the proof. Generally you'll encounter problems in the wild in any interpreter. Similarly you can encode many open mathematical problems into simple programs where finding runtime bounds is equal to solving the problem. The Collatz Conjecture for example.

Once you leave primitive recursive functions[0], reasoning quickly becomes very non-trivial.

[0]: https://en.wikipedia.org/wiki/Primitive_recursive_function

personally, I think I wouldn't even bother to check the algorithmic complexity of every external function I call. I'd just use the logical choice (like sscanf) and only consider optimising if things started to slow down and profiling the application highlighted it as a bottleneck.

I personally would, if it was listed in documentation. Doing stuff and profiling later is the right general approach to performance optimization. But what's better is not doing stupid mistakes in the first place, if they are trivial to avoid. To achieve that, you need to know the complexity guarantees of functions and data structures - or at least their ballpark (like, "this could be O(n) or perhaps O(n logn), definitely not worse").

This is where setting the guarantees and documenting them is useful - it allows people to trivially avoid making these performance mistakes. Prevention is better than cure, in that - as GTA Online case demonstrates - in the latter stage of product development, people may not bother fixing performance anymore.

It might still not help in he case of sscanf. The documentation would specify that it’s O(N) in the size of the input string, just what one would expect without deeper thought. The problem is not O(N), the problem is that N is the complete input string, not just the part being parsed. The documentation would have to include a big fat warning about that.

Part of the issue in my mind is that big O complexity values don't (can't?) tell you the point of inflection, if they are nonlinear. Sscanf could be O(N^10) (does the rule about ignoring the coefficient also apply to the exponent?) but if it only starts to hurt your application at the point of 10tb string reads then it's still unimportant.

I do agree that people often take "don't optimise early" as licence to not make optimisations up front that will clearly be needed (for example, implementing the buffer as a rope in a text editor), but I don't think this is the case here unless you test the function with reasonable future file sizes (something you should be doing anyway) and Sscanf profiles as a bottleneck.

I agree. And I'd personally probably trip over it too, if I used C functions much (I use C++ standard library equivalents, and I'm going to recheck string parsing code in our project now, because we may have that same problem, just with different API!). strlen() in a loop is something that can sneak up on you by virtue of having too many layers of abstraction - scanf() family being one of them.

But what I'm saying is, documenting big O complexity is useful, even if imperfect (and if the function has "tricky" complexity, the conditions where it gets bad should be documented too!).

> Sscanf could be O(N^10) (does the rule about ignoring the coefficient also apply to the exponent?) but if it only starts to hurt your application at the point of 10tb string reads then it's still unimportant.

Sure, but then applications grow, functions get reused. Iff it's trivial to spot and replace O(N^10) Sscanf with a O(n) alternative, I'd want to know the complexity and do the replacement immediately - otherwise, you may discover two years later that the company is investing employee-years into horizontally scaling your application as it's slow under workload, where fixing that one thing would let it run that same workload on a laptop, on a single core.

(This is not a joke, there are "big data" stories like this.)

> But what I'm saying is, documenting big O complexity is useful, even if imperfect (and if the function has "tricky" complexity, the conditions where it gets bad should be documented too!).

Ah yes I totally agree on this point, it should be documented for those who are more cautious/mathematical in their engineering efforts. I'm just not one of those people! I prefer to focus on the structural behaviour of a team (if it's my responsibility) to ensure that cases like:

> two years later that the company is investing employee-years into horizontally scaling your application as it's slow under workload

Resolve correctly - if a team is set up to respond healthily to production slowdowns (of course the equation is different for software with a slow/nonexistent update loop) then IMO you don't need to invest as heavily into up-front optimisation and can instead invest into features, allowing (sample-based for busy paths) profiling in production to notify you when optimisation is warranted.

At the end of the day, up front optimisation is an exchange of time with your future self/colleagues. It's worth it in some cases, not in others - but knowing where the balance in a tradeoff lies in your circumstance is a good chunk of all engineering decisions!

The important part of the documentation would be that N is the length of the entire string, not just the subset of data that needs to be processed. The actual complexity isn't relevant in this case.

Yes, I absolutely think profiling and then only optimizing the actual problems is always a sound choice.

I don't check the docs for every library function I use. I'm just saying, it wouldn't hurt if, when you do read the docs for standard library functions, the algorithmic complexity was mentioned in passing.

In principle, that sounds good. But then it can happen that you profiled when N=1000 and it seems fine. Then a few years later (like in GTA), N has grown to 63,000 and it's no longer fine. It seems unlikely the developer will go back and profile it again. Also, I think the original Windows Update algorithm for figuring out which updates you needed to download started out fine, but 20 years later it turns out it's quadratic and now there are tens of thousands of updates, so it becomes almost impossible to install XP SP2 from a CD and have it update itself.

also dont forget the quadratic time desktop icon arrangement: https://news.ycombinator.com/item?id=26152335

Do you have a link for the Windows Update algorithm being quadratic?

I believe this is what the parent was referring to: https://arstechnica.com/information-technology/2013/12/expon...

Thank you, I had a vague memory of this but this article sums it up perfectly and states that it's worse than quadratic, it's exponential.

Luckily, this happens to be one of the places where learning computer science can help!

But you'll lose so much time doing that! Realizing there's a bug and investigating it is a huge amount of work compared to never writing it in the first place.

No, spending time optimising areas of the code that will never become bottlenecks is the waste of time.

But if you know the performance of an algorithm up front, you don't have to spend any time optimizing it in the first place. You just know what to do, because you know the performance.

For instance: suppose you are building a CRUD app on a SQL database. Do you (a) add indexes for important queries as you go? or (b) ignore indexes and later profile and see what queries are slow. No, of course you just make the indexes in the first place. Having to do the latter would mean that instead of having a fast app out of the gate, you have an app that gets slower over time and requires additional dev time to debug and improve. Profiling and fixing performance problems is a massive waste of everyone's time if the problem could have been dodged when the code was being written.

It's different if the optimization is significant engineering effort. Then, yes, put them off till it's needed. But most aren't, in my experience: most optimizations are totally simple, in hindsight, and the code should have been written that way in the first place.

Of course you index hot columns up front in that case, but I think where we disagree is that you want to generalise "optimise up front" into a rule, do or don't; I consider whether it's applicable in the circumstance. C programs tend to use a lot of system calls, and are also usually easily rapidly testable with large data. So rather than profile every individual std function I call, I'll just profile the very resource intensive paths with different scales of data and see if anything pops off. If R* had profiled their JSON parser with a 1gb file, they would've found this bug.

I don't disagree unilaterally with "optimise up front"; I disagree with unilateralism.

> I disagree with unilateralism

I mean, that's my point too. There's a camp of people who will say "don't prematurely optimize! profile and tune the hotspots later" as a blanket rule and I think that's dumb. And I thought you were espousing that.

No no that's not my angle at all, but I'm glad we're in agreement. Clear communication is hard!

This is how you get software where everything is just fast enough to be tolerable but still annoyingly slow.

No, not paying attention to performance at all is how that happens. Optimising all your code in advance is just being frivolous with your time.

Bugfixing isn't optimisation

The line between bug fixing and faffing around is context based, and there are efficient and inefficient ways to both fix bugs, and faff around. Profiling every stdlib function is probably both inefficient and faffing around unless your circumstances dictate its a worthwhile and effective (there aren't better alternatives to reach the goal) effort.

There are many implementations of the C standard library and thy may not have the same complexity. In this case the code has the right complexity(linear) but to the wrong n (string length instead of parse length)

> It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation.

Isn’t the point of standard library functions to define the contract and not implementation constraints? In other words, if algorithmic complexity is a significant concern, perhaps a standard library function is not a suitable choice.

Algorithmic complexity is not an implementation detail, it's part of the constraints on how you can use the function.

This is a cool idea..I'm sure it's been done before automatically in code, but I'd love to see this in my editor. It sounds similar to the bundle-size extension that you can use that will annotate how big a package that you're importing is in node.

> standard library functions to include algorithmic complexity as part of the standard documentation.

it would be acceptable to have a graph of the input size vs time, and this graph could be autogenerated using a testbed that is also used by unit testing! two birds one stone!

I don't think we could come up with a standard x axis bounds for such a graph, since n=1000, or 1,000,000 may not be zoomed out enough to showcase the behavior approaching infinity.

Reply on news.ycombinator.com