Big-O matters, but it's often memory that's killing your performance | Hacker News Reader

Big-O matters, but it's often memory that's killing your performance

cocoaphony.micro.blog

44 pointstodsacerdoti13 comments

Big O notation and analysis techniques can apply to both time and space and the same algorithm can have very different Big O approximations between time and space. For instance, a hash table (dictionary/map) algorithm may give you some nice O(log n) performance in time, but because you need to be able to retrieve the items you store is best case never going to be better than O(n) in space. It's possible to find such algorithms with worst cases nearly as bad as O(n^2) in space overhead (or Omega(n^2) if you prefer Omega-notation to mean "worst case approximation"). They may still be nice O(log n) in algorithm time, but the theoretical "speed" comes at the tradeoff of space utilization. Trade-offs in space of course have practical impacts on time in the real world (between locks, paging, bank switching, bank delays, bandwidth/light speed distance to specific banks, cache prefetch intelligence, and so many more variables, some ancient and some modern and/or language specific).

As with everything involving Big O notation: it's a first order approximation. (Literally so, as that's exactly what Big O means, summarize things to the first order in the presumed polynomial equation that describes it time or space [!] complexity.) The exact same analysis process is useful for more than just "number of algorithm steps" (time) and can be useful in examining algorithm space requirements ("number of memory units", say). Also, it's still an approximation to start an analysis and that's rarely where you should stop in your analysis in real life.

I spent about a decade doing app performance consulting. The basic three buckets I saw were:

1) Stupid human mistakes. IE: improper configuration, checked in the wrong file, no testing, etc.

2) Resource constraints, normally because someone was being cheap and thought they could get away with less memory / cpu / network / database / etc than was needed.

3) Architecture. Often the real root cause was that either a system had outgrown its original design, or there really wasn't much of a design in the first place. These were the worst, because they were not easy [fast | cheap] to solve.

To the article's point - I don't think I ever saw a single instance of "wrong algorithm" IE: a case where "Big O" was at fault. Did see interesting memory situations, but even those were relatively uncommon compared to "Why are you doing this in js rather than in your db?" or some variation on those other themes.

Over the years, working on performance on .Net applications, I've found among the best ways to improve a .Net application performance is to reduce the GC collection pressure. This is the least obvious way to improve performance for most people because the GC is treated like a magic black box. Recent versions of .Net have made it so straightforward things that used to wreck havoc on memory (like LINQ) no longer do so (yielding good performance gains).

I’ve work in games and simulations for over a decade and it’s almost always algorithm choice that affects performance. A very common issue is storing a bunch of values in a list and constantly searching that list when a dictionary would reduce the Big O and cut down of thousands of value checks that have to be loaded into cache.

I think both of your points 2 and 3 are heavily impacted by "Big O faults", it's just that you are seeing the practical repercussions from a distance ("postmortem" of the failure so to speak) rather than evaluating the potential problems up front before they occur. "Big O" is a "theoretical" tool for trying to avoid problems up front. When those problems do occur in practice they show up as hitting resource constraints (the algorithms don't scale in resource utilization in a once predicted way, or don't scale with input in ways that align with business needs, etc), or they show up as architectural faults (designs that don't last much beyond initial conditions/testing conditions).

In all those cases the "Big O" of the chosen algorithms is never directly "at fault", it's an approximation tool so of course it will rarely be a "smoking gun" in the real world, but it can be a very common hidden "root cause" that's easy to overlook in problem "post mortems", often: Had the developer at the time a thing was written been better aware of the "Big O" complexity of their chosen algorithms they might have found potentially better trade-offs for resource utilization given resource constraints or for architecture given expected long term design.

I know that's a lens I apply a lot when doing performance work and trying to find "true" root causes, thought exercises along the lines of: What was the intended "Big O" of this algorithm when originally written? What in practice violates that intention? Where are hidden "Big O" costs that a developer might have missed because it seemed ancillary to their core algorithm they were working?

(In .NET, for a concrete example of applying "Big O" to performance fixing, I can go to some length on "ToList Considered Harmful" and how it's a common accidental O(n)/O(n^2)/O(n^m) sink, in both time and especially space [memory usage], that is non-obvious because it is so easy to write .ToList() everywhere and so common in many codebases/code-styles to find it mindlessly everywhere and a lot of APIs wastefully use IList<T> or ICollection<T> rather than IEnumerable<T> or IQueryable<T> as their API boundary and a lot of developers use "ToList Debugging" as a crutch and yet ToList doesn't look like it intentionally means to be a part of the algorithmic complexity of the actual business logic it interferes with.)

>Heaviest remaining stack trace that I’m digging into now: swift_allocObject. It’s always memory…

Reminds me of Kirk Pepperdine's "The Trouble with Memory" talk: https://www.infoq.com/presentations/jvm-60-memory/

Quotes:

"Reduced allocation rates from 1.8 gigabytes per second to zero. (...) TPS jumped from 400,000 to 25 million."

"about 70% of all the applications I run into are bottlenecked by some sort of memory issue (...) not only are people bottlenecked on this issue, they don't actually realize it. They don't even see it. It's not even visible to them."

Then he goes on to enumerate some popular Java frameworks, and says: "If you use any of these, then you're very likely in the 70% of people that are suffering from memory issues."

From first look on article, seen something wrong, and now seen code and understand what is wrong.

Algorithm I see is very simple, nothing could brake there, but author don't share communication routines, and here is core of problem.

Few years ago I have worked on project, where one thread sends huge amounts of data to other, using standard CriticalSection routines to synchronize threads.

They are simple to use, but even with hardware support are extremely slow - on 3Hgz class cpu give about million transactions per second.

I was too lazy to finish that project, but it's very clear for me, that I just need to rewrite messaging part, to send not one string, but batch of strings, so million transactions per second will be for example, 100 millions strings, or billion strings.

Same thing I see here - accept inter-thread communication is laggy, and rewrite code, so it will send larger packets, so there will be less transactions, and you will get easy performance gain.

Yeah, I get into arguments with people all the time whenever I am "teaming" any kind of parallelism.

I assume at the beginning that the unit of work is almost certainly so small that you can do many units of work in the time it takes to move a unit of work from one thread to another. Usually the other people are obstinate and insist on implementing something that is slower than serial execution, but they do come around unless they give up entirely when their attempt at a parallel speedup really causes a slowdown.

People love to talk about smart things. But when asked question about real implementation, people disappear, because nobody want to take even abstract (ethical) responsibility of consequences :)

In the case of Xoshiro256 you can just make multiple instances of the generator with Xoshiro's jump function. No locking required and no overlapping sequences.

Don't you need to lock the primary generator to avoid producing identical jump-derived generators?

He makes some good points. Mutable states in multithreaded applications can quickly become the bottleneck and often requires a rewrite to solve.

I think people also forget another fact - O(f(N)) means O(N) + c and a lot of times the value of c overwhelms the gains from algorithm for one off uses. O(f(N)) might also be amortized cost and you need to evaluate your use carefully to see if you see the gain.

Reply on news.ycombinator.com