I'm the senior dev on my team, and whenever a new dev joined my team they would look at the codebase and go "ew, python2? Just use python3."<p>That gave me a chance to explain the testing and refactoring cost that would come with changing python versions, and how the benefits to users would be almost zero. And then at some point one of the new juniors said, "hey, there's a lot of filesystem performance improvements and readability improvements (f-strings) in 3. I can get the test/refactor done in a month, and I think it's a net positive." They were right, and now we're on python3.<p>So, sometimes we all learn something.
I find that the biggest misunderstanding happens because "new grads" (and I happen to be one) confuse _asymptotic complexity_ with actual complexity.<p>I'm not sure sure why, but CS courses and interview questions mostly focus on _asymptotic complexity_ and usually forget to take into consideration the complexity for "little values of n". And funnily enough, in real life n never goes to infinity!<p>In a strict sense big O notation only cares about what happens when n goes to infinity. The algorithm could behave in any way up to numbers unimaginable (like TREE(3)) but still, its big O wouldn't change.<p>Maybe what is missing to those "new grad" is a felling of real world data, and how a computer behave in the real world (with caches, latencies, optimised instructions etc...) not just having an ideal computer model in their mind when they design algorithms.
In real life, you will always start with simple working implementation and go with it.
Then if things are slow, you profile your code with a good profiler while running for some kind of real life scenario and spot the slow parts (also keep in mind that profiling may affect the program's behaviour).
After that you may want to consider alternatives with less asymptotic complexity iff that's the part causing slowness.<p>Once I was asked to look for one project to see that if there is any room for improvement to speed up the program.
After I profiled the program with the test data, I saw that program was severely affected by a "size" method call on a lock-free concurrent list. Since the data structure is lock free, size method is not a constant time operation and calling it in a large list takes too much time. It was just there to print some kind of statistics, I changed the code so that it is called only necessary not every time some operation occurs. This immediately made program 2-3 times faster.<p>There were also some parts I changed with some algorithms with less algorithmic complexith to make it faster.
Overall, I made the program 6x faster. So sometimes you need to use fancy algorithms, sometimes you just need to change one line of code after profiling.
By the way, here’s an anecdote for the flip side: at one of my internships I was working on a tool to process large log files, and by careful application of Aho-Corasick I was able to make it about <i>50 times</i> faster on the dataset we were dealing with, which made using the tool change from “let’s go grab lunch while this finishes” to “let’s stream the logs through this live”. Sometimes you do know how to make things faster: just make sure to test them before you do, and asking why something is a certain way is always a good thing to do before proclaiming it’s broken.
Heh... reminds me of my first proper MS internship, when I too was responsible for speeding up some code, this time in the VS Code Go extension. This code was responsible for tokenization, so it affected pretty much every operation and ran on every edit. Important shit.<p>Day 1: do some basic hoisting. O(n^3) => O(n^2). Tokenization times for a 10k line file go from ~15s to 500ms. Sweet.<p>Days 2-30 [1]: ideate, develop, bug fix, iterate on, etc, a novel (to me) data-structure to speed up the program even more. O(n^2) => O(n x log(n)) (expected). Great! Runtime on 10k line file went from 500ms to <i>maybe</i> 300ms. Oooops.<p>But hey, all the people working in 500k line files must really love the couple seconds my month of toiling (more importantly, my month of not doing other, more impactful things) saved them.<p>Learned a lot from that experience, and writing this out now I can see how that impacted engineering decisions I make to this day. I suppose thats the <i>real</i> point of an internship, so time well spent, in a way.<p>[1] It probably wasn't actually a month, but certainly a significant chunk of the internship.
I see these senior vs non-senior engineer contrasts pop up a lot. I’m not a huge fan of them.<p>It seems that there is a spectrum of skills an engineer could excel at: programming, infrastructure, managing, planning, etc. I’ve known senior engineers who only excel at a particular skill. I’ve also known senior engineers who are moderately good at many but not particularly good at one.<p>In my experience the only difference between a senior and non-senior is that the senior’s distribution of skills makes them more effective.<p>I’ve also seen senior engineers change roles laterally and become more or less effective, yet still maintain the senior title.
Oh god. That meme.<p>I've seen it a day or two ago. Can't find the picture anywhere now (I've seen it in some group chat). Anyway, beyond the words quoted at the beginning of this article, the meme's "nested loops go brrr" had a picture of a triple-nested loop using Active Record to do some simple database operations.<p>To which the correct response is: "it's a 'senior developer' in an industry where you get called a 'senior' after a total of 3 years of experience doing programming; don't do stupid shit like this, <i>just use SQL like it's meant to</i>".
This is a great story. I feel like talented CS students are particularly prone to this sort of myopic thinking; their professors introduce them to functional programming, or the philosophy of UNIX, and they carry that approach everywhere, in a very blunt way. They also carry this little-examined conviction that the world consists of mediocrities and mediocre code and sometimes aren't charitable with the work of others.
I think it's really interesting how complexity theory sort of falls apart in the face of hardware-specifics and concrete use cases. The motto in computer architecture is to make the common case fast (it's in like every textbook), whereas the motto in computer science is to make the program scale/to solve generically. When push comes to shove (as this article shows), the computer architects seem to have the final word, at least when it comes to making things go <i>more brrrrrr</i>.<p>There's so much stress and attention given to complexity theory for software engineers, to the point that people will cram for hours to make it through FAANG interviews. I understand that it's important and it's just something that everyone has to go through... but data structure and algorithm performance is a Wikipedia search away, and then you choose the appropriate STL container and move on with your life. The same can't be said for gaining an understanding of modern processors.<p>I'm not saying that one is more important than the other or vice-versa, I'm just saying that it seems wrong to me that not knowing algorithms and data structures can break an interview, whereas not knowing hardware is virtually a non-factor.<p>The big take away for me is this: if you're not benchmarking, you're cargo culting.
Go's strings.Index/bytes.Index also often use the "find first byte" approach; now on amd64 it's a fancy vector instruction. If it finds the first byte too many times without a full match, it falls back to a Rabin-Karp match using a rolling multiplicative hash.<p>The strings.Index code is at <a href="https://golang.org/src/strings/strings.go?s=25956:25988#L1018" rel="nofollow">https://golang.org/src/strings/strings.go?s=25956:25988#L101...</a> and the internal bytealg package with all the CPU intrinsics is at <a href="https://golang.org/src/internal/bytealg/" rel="nofollow">https://golang.org/src/internal/bytealg/</a> with index_amd64.{go,s} as the relevant files for x64.<p>Battle-tested implementations of fundamental things like string searches, sorts, hashtables, allocators, graphics primitives, etc. are often interesting 'cause you find out a lot about what you need (and/or don't need) to work well in practice as well as protect from exploding worst-case scenarios.
As a senior dev, I wish that I could say I always knew more than my interns, and that all the code that's there is because it was carefully planned to be that way.<p>But more often than not, I don't, and it's not.<p>My take on it is that for the most part senior devs are a lot more paranoid on breaking things and don't want to make code changes unless enough people are asking for it and it'll make a notable difference. Even making things strictly faster can break users if they depend on the algorithm being slow (an extreme edge case that you'd usually say is the user's fault anyway, but could nonetheless be relevant in things like optimizing away a spin-wait).
Shockingly,<p><pre><code> InStr(<this page of 100+ comments>, "docum") = 0
</code></pre>
I'm a dev with some grey hair who feels it would have been useful for all that fantastic domain knowledge from Paterson to get documented in a code comment.<p>I'd love to hear if either of them ever went back and did that?
I always envy people who work on this level instead of cobbling systems together that integrate several systems all with their own set of flaws and you can be happy if you can make them work together somehow. The algorithm stuff seems pretty simple in comparison. A very local problem that can be profiled well and you can understand most of the factors at play.
This is also why C++ (and hopefully other languages by now) has the short string optimization. On a 64-bit machine, a pointer to a heap-allocated buffer is 8 bytes long. A stupidly large number of the strings used by actual programs are <= 7 bytes long (it's actually more like 20 in C++, because strings also include a length and capacity). Think about it: that's virtually every file extension, path separator, and field delimiter, and a good number of field names, labels, first & last names, usernames, identifiers, URL path components, parameter names, etc. If you can fit the whole string into an immediate value, then you can avoid the heap allocation and deallocation entirely, you can avoid chasing pointers and incurring a cache miss, and you can very significantly reduce the total amount of memory used.<p>This is also a good reason why, if you're designing a standard library, you really want to have length-prefixed strings instead of null-terminated ones. If you know the length of the strings you're dealing with, you can swap out the algorithm you use, such that you might use brute force for a very small needle, word comparisons if it's exactly 4 bytes long, SSE instructions if it's a word-length multiple, or Boyer-Moore for very long strings.
Imagine that the intern didn't dare to ask such questions.<p>a - he could've gone out thinking that performance doesn't matter. but it certainly does in a piece of code being used daily by thousands of devs.<p>b - he could've thought that the simple implementation is faster but missed the fact that skip is implemented in assembly.<p>c - he could've realized both but missed the why.<p>and these failure scenarios are likely to happen because this is an intern we're speaking about.<p>One or two tricks up your sleeve do not matter but repeat this a 100 times which one do you think would be a better programmer?<p>I think the willingness to challenge authority figures and to be (often) proven wrong and to learn from it is an essential part of becoming better.<p>Maybe Tim was understanding because he himself challenged people older than him and in-process learned form them.<p>Advice like "don't reinvent the wheel", "avoid premature optimization", "write boring code" promote exploitation.
which is the optimal strategy for older agents.<p>but for newer agents, a higher level of exploration is needed otherwise they would converge into a suboptimal strategy
I'd say that for widely used library code it makes sense to implement an efficient algorithm. By its very nature the context in which a library routine will be called is unknown and so it must be prepared for everything. Also for widely used code the amount of total saved machine time can be quite substantial.<p>In the story the senior dev makes a judgment call (that this routine will be used in LOB applications where the worst case is unlikely to appear so the implementation is OK) which is probably correct, especially considering other priorities. And of course senior devs are much better equipped to make this kind of calls than juniors, but they still can and will guess wrong.<p>> Moreover, Tim explained to me, any solution that involves allocating a table, preprocessing strings, and so on, is going to take longer to do all that stuff than the blazingly-fast-99.9999%-of-the-time brute force algorithm takes to just give you the answer.<p>That's why a good implementation will dispatch to the best algorithm at runtime!
Of course, if this code were running in a server, or if it were part of a library that was widely used, then suddenly you have the potential for a DoS vulnerability.<p>The narrative would then be that the microseconds you saved all those devs over the years were wiped out when hackers took down your system.
The senior dev knows the system, knows what they can get away with, and has choices to use those knowledge powers. A newbie will always follow the programming rules, like never going over the limit on a hwy. as they can’t take much calculated risks
> NO! YOU CAN’T JUST USE BRUTE FORCE HERE! WE NEED TO USE SEGMENT TREES TO GET UPDATE TIME COMPLEXITY DOWN TO O(LOG N)! BREAK THE DATA INTO CHUNKS AT LEAST! OH THE INEFFICIENCY!!!<p>I'm the opposite of this stereotype, and I think there are more like me. Two reasons as to why:<p>(1) Psychological:<p>I never had this. As a junior dev, I don't like to optimize because I feel a bit of pain when I need to moderately focus. I can do it, and I've done it quite a lot. In that sense, I've experienced quite a bit of pain in my life. It's something I've learned to live with. And when I have to focus, I prefer to focus all the way, because whether I focus on 50% or 100%, the pain is roughly similar. This leaves me in a state of either being lazy(ish) and wanting to program in a simple and understandable way versus being willing to go as deep into a topic as I would need to and focus on all the details step by step.<p>When I'm intense, I also am still sympathetic towards simple code because I know that I understand that in both states. I only understand complicated code when I'm focused.<p>(2) There are enough CS grads that know better:<p>Also, on another note. Efficiency analysis is simply not taught at university. Parts of it are taught, but they're never connected to real world cases.<p>For efficiency analysis (note I haven't done any but I've read a thing or two and talk with a friend who is a performance engineer quite regurlarly about it) I think there need to be a few perspectives in check:<p>1. What is the user's actual behavior.<p>2. What is the behavior for malicious attackers (if applicable, Intel should do this more, to my knowledge they are doing it more now).<p>3. How does the compiler translate it to assembly?<p>4. How does it theoretically look? Specifically: worst-case, best-case, average-case in both theoretical and empirical sense.<p>Concluding:<p>I only have one year of experience in software development, where no one cared about performance yet I know better than to look only at the theoretical speed. So I guess I'm a counter example to the stereotype. I'm not alone. Any CS student who reads HN has a high chance of stumbling upon articles like this and will know that performance analysis is not only about calculating the space-time complexity.
This is the meme referenced by the blog post:<p><a href="https://i.redd.it/lmrf72ko0ro41.png" rel="nofollow">https://i.redd.it/lmrf72ko0ro41.png</a>
Admittedly clueless question: what does 'brrr' mean? (I'm not a software dev and idioms that may be obvious to others are unfamiliar to me.)
One of my job tasks was improving our custom string library. In VB!
Sure InStr was slow: but we were trying to do "starts with" across very long strings.
Sure, it worked, but a slightly smarter solution was 100 times faster.
Upon finding it I went on a search, I found it written nearly identical 10 years before me, in a different version of a string library (hint, that one was faster).<p>The trick to knowing we needed to improve it: profiling!
This isn't always the case that simplistic algorithms don't cause issues Bruce Dawson keeps on finding O(n^2) algorithms in windows that keep on biting him. I'm always impressed with his work.<p><a href="https://randomascii.wordpress.com/2019/12/08/on2-again-now-in-wmi/" rel="nofollow">https://randomascii.wordpress.com/2019/12/08/on2-again-now-i...</a>
I dislike the mentality that one must "struggle" to be patient with new devs and that it's "more than they deserve."<p>Is it really so hard to help other people learn, and to accept that the only advantage you have on them is starting earlier?
I've noticed there's a similar form of this at the sr. dev/grizzled veteran divide.<p>The sr. dev will look at "old" code in horror and be sure the only way to make it perform is to port it to a newer language/framework/architecture.<p>The grizzled veteran will profile the code, think, and tweak a few lines. No fancy new things or big re-writes needed.
Sometimes it’s not just coding tools/techniques where new grads can benefit from a bit of oldster wisdom, like that one time I convinced a new grad it was wiser to slog through the bureaucratic approval process for a new api than attempt to hack into our company’s Oracle Financials db.
This reminds me of how insertion sort is the most efficient sorting algorithm for small values of n. I remember new-grad me always dismissing insertion sort in every situation because of asymptotic complexity. Engineers are supposed to find the most pragmatic solution without biases.
To be fair, there have also been plenty of times in this situation where the senior dev was wrong. You were right to question things and we should make sure to continue to encourage questions. The difference between a new grad and a senior dev is that the senior dev has the real-life experience to make the "yes/no" decision as to whether the new grad's input actually makes things better (e.g. it could be true that it doesn't matter if it is asymptotically faster if we are always working with small data). It's also a trait of a senior dev to be able to stay level-headed in these situations
Edit: I thought I was responding to someone, but I can't find the comment now.<p>I find that being open to new ideas, and allowing some time to prove them out rather than deciding beforehand, is the best way to find ideas that move the needle.<p>Senior comes to you with an idea? Great, prototype it, prove it out. Junior comes to you with an idea? Great, prototype it, prove it out.<p>Of course, you need to allow some time for prototyping.<p>When I ran teams, I told them part of their job was to spend the last half of Friday (unless emergency) prototyping their ideas and presenting their favorites at some point.<p>No one works the last half of Friday anyway, unless it's on this.
Well, this is a nice example of lack of knowledge flow. The senior developer spent his time explaining things that should have been put in the procedure's comment. Yes, that's what comments are for.
The real lesson here should be: don’t make assumptions about performance. Take real world use cases and measure!<p>That’s what my professors drilled into me (I specialized in high performance computing) and it’s served me well.
On a larger architectural scale, see: Use Boring Technology<p><a href="http://boringtechnology.club/" rel="nofollow">http://boringtechnology.club/</a><p>Also described as: "how to be old, for young people"
As a new grad myself, I completely agree with the author’s freak out when seeing “inefficient” looking code. But I feel like this applies to basically all aspects of a company life as a new grad software engineer. For me at least, there seems to be a lot of inefficient things going on in every aspect of the company. Maybe the author is right in that there is a reason behind those seemingly “inefficient” things. However, the inefficiencies are there because sometimes, people who have been working there for years just have become used to it.
Seems like the original developer should have left a comment about why their nested for loop was the right implementation (if they knew it was). Would have saved everyone a lot of time.
With the world of developers becoming "senior" at faster and faster rates, we're asymptomatically approaching the demise of these questions, no?
I would use the standard ISO C strstr instead of writing the function they are calling find.<p>Yes, we had strstr in 1994; it was in the 1989 ANSI C standard.<p>On a very small system, strstr will probably just be naively coded, to save space. On a big system, it might use Knuth-Morrison-Pratt or Boyer-Moore. I don't have to care; by using strstr, that decision is taken care of.
I think it is good when new grads have the knowledge to see that those things don't look right and can articulate how and why it should look different.<p>After all, when you come across a problem, that does not contain just 100 chars, it is very helpful to know what you can use to create something that still works with reasonable resources.
The only nested loop implementation I've ever changed for performance was due to the fact that there was a freakin' database call in the inner loop. All I did was refactor the data structure so that the db call was done outside the outer loop. Instant 20x improvement in performance.
Were the x86 string instructions much faster in 94? That was 486/Pentium era, right? IIRC this has varied over the years with sometimes slow microcoded string instructions and then faster improved instructions again.
But Boyer-Moore is so pretty!<p><pre><code> abcdefghijklmnopqrstuvwxyz
</code></pre>
If the 26th char isn't <i>z</i>, jump along 26 chars! (More complex, and more cache misses, if <i>z</i> is repeated in the search string).
The explanation behind the code is exactly the kind of thing that belongs in a comment. The why, not the what. So even if it wasn't a failure of programming, it was a failure of documentation.
> The skipto method is a single x86 machine instruction.<p>That’s not always a good thing, especially on modern hardware. And obviously, the “single instruction” doesn’t mean it’ll take bounded time to execute…
The way I read this, TIM FREAKIN' PATERSON, the man who wrote the most hated "operating system" in history, put an algorithm with a nasty performance bug into the standard library of VB, and conveniently forgot to document that this function is no good for large and/or repetitive inputs. Confronted with his blunder, he not only doesn't correct his blunder, but instead condescendingly proclaims that those inferior VB coders would never need long strings, just like 640kb ought to be enough for everybody, and if they did anyway, they'd surely use a library written for the purpose by a real programmer.<p>The arrogant prick should have listened to the new grad.
There's some good wisdom in this story. It reminds me of that article posted here about a more page cache efficient b-trees vs. Knuth's theoretically ideal version
There is another type/layer of new grad - the kind without CS background and not being able to make a right solution (let alone balancing different concerns)
New Grad: I'd use a linked list here because insertion into the middle is O(1) rather than O(n).<p>Senior Dev: Linked lists have very many more cache misses than do vectors, and the difference between hitting cache and hitting main memory is such a huge constant factor that for most reasonable list sizes it never makes sense to use a linked list. Use a vector. Checkmate, smug Lisp weenies.
Everyone who has done profiling knows that (almost always) the performance problem is in the part that you least expect it. But also that sometimes you wrestle to improve the performance of an algorithm hitting a hard wall and than someone comes up with an idea, often resulting from a fresh look on the problem, that results in an improvement of several orders. I guess that performance is at least as counter intuitive as statistics. The same is true for some other things like scalability and reliability.<p>Actually, I think that it scares the hell out of most of the developers that it is so difficult to get a grip on these things. It is so easy to think that there is a simple solution, a grand idea that will fix the problem. I still find myself falling in the trap and this after having developed software for over 30 year. It is the Dunning–Kruger effect over and over again. I guess it more that as a more senior engineer, you have experienced a little more often.
I understand this as phenomenon as the new grad and the senior developer are optimizing for different things. The new grad is focused solely on the asymptotic complexity of the code. It doesn't matter how slow or how complicated it is in practice, they are solely focused on using the fastest data structure asymptotically.<p>The senior developer optimizes a different set of criteria:<p><pre><code> 1) How hard is it to understand the code and make sure it's correct.
2) How fast the algorithm in practice.
</code></pre>
There are several different reasons why the performance of the algorithm in practice is different than the performance in theory. The most obvious reason is big-O notation does not capture lots of details that matter in practice. An L1 cache read and a disk IOP are both treated the same in theory.<p>A second reason is the implementation of a complex algorithm is more likely to be incorrect. In some cases this leads to bugs which you can find with good testing. In other cases, it leads to a performance degradation that you'll only find if you run a profiler.<p>I one time saw a case where a function for finding the right shard for a given id was too slow. The code needed to find from a list of id ranges, which one a given id fell into. The implementation would sort the id ranges once ahead of time and then run a binary search of the ranges to find the right shard for the id. One engineer took a look at this, realized that we were doing the shard lookups sequentially, and decided to perform the shard lookups in parallel. This made the code faster, but we still would have needed to double the size of our servers in order to provide enough additional CPU to make the code fast enough.<p>Another engineer hooked the code up into a profiler and made a surprising discovery. It turns out the implementation of the function was subtlety incorrect and it was sorting the id ranges <i>on every call</i>. This happened because the code sorted the id ranges inside of a Scala mapValues function. It turns out that mapValues does not actually map a function over the values of a hash table. It instead returns an object that when you look up a key, it will look up the value in the original hash table, then apply the function[0]. This results in the function being called on every read.<p>The solution was to replace mapValues with map. This dramatically improved the performance of the system and basically brought the CPU usage of the system down to zero. Notably, it would have been impossible to discover this issue without either knowing the difference between map and mapValues, or by using a profiler.<p>[0] <a href="https://blog.bruchez.name/2013/02/mapmap-vs-mapmapvalues.html" rel="nofollow">https://blog.bruchez.name/2013/02/mapmap-vs-mapmapvalues.htm...</a>
This Dilbert went around the office a lot when I was a new employee. The numbing is real...<p><a href="https://dilbert.com/strip/2003-02-16" rel="nofollow">https://dilbert.com/strip/2003-02-16</a>
I have no CS degree or STEM degree.<p>Recently I worked on the same type of project as someone with 10 yrs of experience & a CS degree from Stanford.<p>A few months later, I created a project, and had a manager with a CS degree. However, when I left, that manager was unable to pickup where I left off, and he ended up leaving soon after.<p>I have less years of experience, but to me, what matters more is the time within that experience which was put into a relevant business model, product built, or past projects. I.e. a Senior Dev with a CS degree, vs. a New Grad with a Business Background & SWE Experience. It's apples to oranges in many cases.<p>Also, I'd echo another comment here:<p>>"daxfohl 1 hour ago [-]<p>> As a senior dev, I wish that I could say I always knew more than my interns, and that all the code that's there is because it was carefully planned to be that way.<p>>But more often than not, I don't, and it's not. "