Profilers fill in gaps in our mental model of code execution but they are not a substitute for it. Computer behavior is largely knowable from first principles, albeit requiring a considerable degree of expertise and detail. For some people in some contexts, the profiler adds little information to what they already understand. I know a few people that do almost all of their optimization work using pencil and paper with great effectiveness and precision. Not something I would recommend for most software engineers but not unreasonable at the limit either.

If you optimize infrequently, or haven't profiled code like this recently, or haven't profiled this specific codebase recently, then your mental model is probably due a refresh.

I've spent a lot of time optimizing video codecs and while it is maybe possible to reason about these without a profiler it's much faster to profile. The profiler isn't going to tell you what you need to do though.

Profiling to find suboptimal code is perfectly fine. Then you need to figure out how to fix it. Many people don't understand how performance optimization works, so they blindly add caching, improve constant time by invoking more low-level methods, etc. This obviously doesn't work, yet intuitively (to those people, anyway) it should produce good results.

That's why the mantra exists: don't trust your intuition, don't believe it when it says these changes improve performance, instead measure that performance and only apply changes that work. This is also perfectly fine, but this is a double-edged sword, and I've seen people go too far in this direction.

For example, they refuse to do any changes that don't immediately improve performance according to the profiler. If they modify one computation and performance decreases, they abandon this path altogether. They treat optimization as a game with a dense fog of war, and they refuse to apply deductive reasoning and, of course, intuition to apply changes that, according to the profiler at least, are not immediately rewarding.

Eg: indexing or partitioning a database table may appear to make things slower if you don't have both a representative amount of data and representative query patterns when you're measuring the change.

You should still measure your changes, but sometimes you need to be careful about measuring them in the right way, and possibly simulating a future context (eg: more scale) before drawing a conclusion.

Intuition about how the context will evolve and what effect that might have on the tradeoffs of different approaches is helpful

Adding caches or switching to lower-level calls is definitely something learned, and I wouldn't call it "intuitive".

What I think you are referring to is that sometimes, simply reading and understanding the code can tell you where the problem really is — still, my experience is that you want to measure the before and after to at least identify the general area you should be looking at, and more often than not, I could figure out what needs optimizing and how without having to get detailed profiles.

I did end up being surprised a few times, but it was mostly due to external code like buggy library implementations that didn't do the things they promised (eg. async library really synchronizing everything with a badly placed mutex).

At the same time, it's wrong to focus on a single case or a single profile (executing one code path in one set of circumstances), but what you are describing simply sounds like bad engineering — the fact that you can misuse the tool does not make the tool bad, it's still the engineer wielding it who's at fault.

Caching and lower level calls are generic solutions that work everywhere, but are also generally the last and worst way to optimise (thus why they need such careful analysis since they so often have the opposite effect).

Better is to optimise the algorithms, where actual profiling is a lesser factor. Not a zero factor of course, as a rule of thumb it’s probably still wise to test your improvements, but if you manage to delete an n^2 loop then you really don’t need a profiler to tell you that you’ve made things better.

Once you “find” a candidate change you measure it to see if what you did made things worse and you put it back if it did, or maybe you try it in combination with other changes to see if its value is complementary.

But people fuck up all the time reading the initial telemetry, which is often where I come in. I get tired of hearing people say, “we’ve done all we can, look how flat this chart is,” and hand someone my beer. You won’t find all of the good candidates in the percentage of run time list. That’s not all the data that’s there, and not every change that works needs to even be supported by the initial data. It only needs to be supported by the delta afterward.

Imagine: function F() { for (i = 0; i < 10; i++) { A(); B(); C(); } }

If we profile this code, we might find out, e.g. B takes the majority of the time--let's say 90%. So you spend hours, days, weeks, making B 2X faster. Great. Now you removed 45% of execution time. But the loop in the outer function F is just a few instructions, it is not "hot"--it won't show up in profiles except for ones that capture stacks.

If you're just stuck in the weeds optimizing hot functions that show up in profiles, it's possible to completely overlook F. That loop might be completely redundant, causing 10X the workload by repeatedly computing A, B, and C, which may don't need to be recomputed.

There are bazillions of examples like this. Say you find out that a function is super, super hot. But it's just a simple function. There are calls to it all over the code. You can't make it any faster. Instead you need to figure out how to not call it at all, e.g. by caching or rethinking the whole algorithm.

> How could measuring be a substitute for thinking/analyzing/predicting/forming a plan?

This happens more than you think. Understanding how the system works in enough detail and also at a high level to formulate a plan is in short supply. Jumping in and hacking in things, like a cache or something, is surprisingly common.

One of my best examples of this, I had a function reported as still taking 10% of cumulative run time, after I’d tweaked it as much as I could. But I’d set up a benchmark that called a code path a deterministic number of times and this function was getting called twice as much as it should. I found two sibling methods asking the same question and rearranged them so the answer came as an argument and nixed the duplicate call. I reran the benchmark and instead of getting a reduction of 5% (10/2), I got 20%. That was all memory pressure.

The worst memory pressure I ever fixed I saw a 10x improvement by removing one duplicate call. Now, there was a quadratic part of that call but it was a small enough n that I expected 3x and hoped for 4x, and was as shocked as anyone when it went from 30s to 3s with one refactor.

I don't think I've ever used a profiler that couldn't report you were in F() here. One that only captures your innermost functions really doesn't seem that useful, for exactly the reasons you give.

IMO, those are (generally) nowhere near as useful as a flame/icicle graph.

Not saying they are never useful; Sometimes people do really dumb things in 1 function. However, the actual performance bottleneck often lives at least a few levels up the stack.

I think I've only been able to get good call stacks when I build everything myself with the right compilation options. This is a big contrast with what I remember working with similar tools under MSFT environments (MS Profiler or vTune).

You can get it to work though but it's a pain.

But, in the real world. Code bases are massive. And it is hard to predict when worlds collide. Most things does not matter until they do. So measuring is the way to go I believe.

There’s so much noise at that point that even people who would usually catch problems start to miss them.

There’s usual response to this is, “well you can turn caching off to do profiling” but that’s incorrect because once people know they can get a value from the cache they stop passing it on the stack. So your function that calls A() three times that should have called it 2? You find now that it’s being called ten times.

And the usual response to that is, “well it’s free now so who cares?” Except it’s not free. Every cache miss now either costs you multiple, or much more complex cache bookkeeping which is more overhead, and every hit resets the MRU data on that entry making it more likely that other elements get evicted.

For instance in NodeJS concurrent fetches for the same resource often go into a promise cache, but now the context of the closure for the promise is captured in the cache, and it doesn’t take much to confuse v8 into keeping a bunch of data in scope that’s not actually reachable. I’ve had to fix that a few times. Hundreds of megabytes in one case because it kept an entire request handler in scope.

You make still run into problems where you expect A and B to have a relationship between them that doesn’t hold if there’s a gap between looking them up, but it’s often less likely or severe than if for instance half a page has the data in state S and half of it is in state T.

You do profiling because it's WAY too easy to get obsessed about theoretical problems when a simple measurement will show you the actual problems.

You do the math on the actual problem location, not a method with O(n!) which only gets called with n=3.

You still have to look at the entire call stack when profiling (which means thinking about the overarching algorithm).

The fact remains most projects that do small trivial modular prototypes first will ultimately know which paths are viable before painting themselves into a corner algorithmically.

Best of luck =3

If a problem area is so intuitively obvious, why would you introduce the problem in the first place? In reality, performance optimizations are usually needed where you least expect them. Which means that you can't get there intuitively. Hence, the suggestion of using profiling to help track down where the problem is instead.

Bring in a performance expert and their intuition can quickly identify many performance improvements. The tough part for the business is when and where do you pay for the experience of performant code, and when is good enough to leave alone?

Pretty much everyone I know will throw down an O(n^2) algorithm or whatever in their first pass and replace it with something more thought out once they have the time to think deeply about it.

If you're fretting about optimization at every stage of development, you're really doing it wrong. This is precisely the type of early optimization that everyone and their dog will tell you is bad. You should focus first on making your program work and laying out the logic and data flows. Optimization does not matter until the program is almost finished.

Most of the times I've seen this, the faster algorithm is literally just a dictionary with a well-defined key.

I honestly do not understand why that's not the first solution most devs think of and why n^2 seems to dominate.

As an example, I've seen code like this quiet a bit

    result = []
    for (item: items) {
        for (item2: items) {
        if (item != item2 && item.foo == item2.foo) {
          result.add(item)
        }
      }
    }

    result = []
    itemFoo = HashSet()
    
    for (item: items) {
      if (itemFoo.contains(item.foo))
        result.add(item)
      else
        itemFoo.add(item.foo)
    }

Disagree

> faster for small n (which is the common case)

How can you know that? And for smaller n, the choice hardly matters.

> can not run out of memory due to the hash table

If n gets large enough that hash table size becomes a problem, n is large enough that you need the hash table or some other structure that reduces the complexity down from O(n^2).

> compiles to less code

This is just nonsense. Any codebase of significant size already has a hashtable setup and unless you are using a language like C++, the code size of using a hash table anywhere is constant. The cost is already paid.

The actual amount of compiled code from the switch is identical.

> does not need item to be hashable

True.

There would be reasons not to choose option 2, but it should be default until it's been proven to be a problem. And even then, the next step is almost certainly not going to be option 1.

But then this could also be language and application specific. I deal primarily with backend services/Java where memory is plentiful, and allocation is fast. Algorithmic complexity is for my applications very often the better indicator of what good code should be.

A pretty common attitude that I've ran into. People take the "premature optimization" quote to mean "Never think about big oh when writing code".

If n is usually less than 100 then sure maybe it does make sense to do the more brute force approach. However, what's the impact of using the hash table first? If n is usually less than 100, now this method is slower usually, but is that a problem? Well, you should use a profiler to find out if it is or isn't. However, that may be entirely tolerable performance wise.

On the other hand, if your assumption that "n < 100" doesn't hold up and, indeed you start seeing n > 100, or 1000, or 10000. Now all the sudden this method becomes a fault in the application you developed that needs to be rewritten.

What's devious about the "n > 100" problem is when you first write the code, you may have very well been correct that "n < 100". But time and inputs change the way code is executed.

A lot of the code I've fixed has been due to this. I've seen the counter where really searching a list/array was the better option only a handful of times.

To me, premature optimization is using a known algorithmically inferior approach, of the same complexity as the superior approach, because you know that for small n, it is faster without knowing whether or not that will be the case.

Not really. You're just exploring an unknown frontier. Once the frontier is known and you actually understand what you are trying to solve you're still going to put in the right algorithm.

I mean, you might not if you're vibe coding, which I guess is apparently a thing somehow, but I'm assuming we're talking about actual engineering here, not speaking the sordid tales of cowboys. The "premature optimization" line was definitely not directed at those who think code is a feeling.

When the frontier is unknown, whatever algorithm gets something operating as soon as possible is the right one. The given example may be so contrived that the hash map would be what you see as the quickest and dirtiest solution anyway, but with a little more complexity loops do tend to be easier to reason about on a first-pass basis.

> Now all the sudden this method becomes a fault in the application you developed that needs to be rewritten.

In the same way that finding out that a blue button doesn't resonate with users, requiring you to rewrite your application to make the button green. Such is the life of building software. But that's why engineers get paid the big bucks – nobody else is stupid enough to do it.

> A lot of the code I've fixed has been due to this.

You're not really fixing it, you're updating it to reflect the information you gleaned during the exploratory phase. I mean, unless you're coding on vibes or something, but, again, assuming actual engineering is taking place here. Nobody should be coding non-prototypes by the guide of their feelings.

Good code should follow something along these lines:

- A reasonable understanding of what needs to happen. What are the requirements. Including data set sizes. Including how "hot" this code path is.

- A reasonable pick of the algorithm to perform what needs to happen.

Sure. O(N^2) for very small data sets could outperform an O(NlogN) or O(N). The conflation of big oh notation with actual performance is just another form of sloppiness as is picking a bad algorithm. In both cases it reflects a lack of understanding of how computers work and how to do things efficiently.

Let's look at what we're trying to do here. We want to find all values that occur more than once in a vector. Using a hash map means you have to:

- Create this data structure on the fly.

- Hash the values.

- Do the insertions/lookup.

You should consider the size of your dataset, you should consider locality/caches etc.

100 entries squared is 10k though. If this is part of a critical code path, let's say your frontend code does this for every DOM element or every notification it needs to process this can end up the bulk of CPU usage. This sort of stuff is why I've seen applications cause the fans to go on or the browser to crash. I would say bad O(N^2) algorithms for large Ns are pretty common.

I would be surprised if e.g. a C++ implementation of the hash version doesn't win over the double loop for data sets of 100. But maybe that's borderline. For a dataset of 1000 there's no way the double loop is winning.

Other alternatives might be something like an efficient small bloom filter that can be stored in a register, sorting the array. I mean at least cut the iterations in half by not iterating over the entire range in the inner loop!

Then you won't have the trouble with:

  if (item != item2 && item.foo == item2.foo) {

The reason I wrote it that way is because the actual common way I find this is in Java where the team wants to use the `stream` api.

IE

    items.stream()
      .filter((item)->items.stream()
        .filter((item2)->item2 != item)
        .findAny((item2)->Object.equals(item.foo, item2.foo)).isPresent())
      .toList();

Even more commonly, instead of doing the `findAny` I often see the trip up being someone doing a `contains` or other O(n) operations on `List` objects inside iterations of that list.

It's this sort of fluent/functional style of programming that often seems to get tripped up on doing n^2 (or more) algorithms.

Measuring doesn't mean don't think. Measuring and thinking are two different things. You need to do them both to optimize effectively.

> This seems like a nonsensical statement to me. How could measuring be a substitute for thinking/analyzing/predicting/forming a plan?

I believe the mantra “intuition doesn’t work, profile your code” is understood to mean “don't rely on your intuition alone; profile your work.” It's a warning that when it comes to performance optimization, intuition is often unreliable, so you need to supplement your mental model with actual data if you want to avoid big mistakes.

I don't know why the author of the blog post is interpreting the mantra literally, as if it claims intuition is obsoleted by profiling.