Fast software is a discipline, not a purpose | Hacker News Reader

Fast software is a discipline, not a purpose

lemire.me

56 pointsfrostmatthew64 comments

“Avoid multiple passes over the data when one would do.”

Totally disagree. Unless performance is an issue (like I’m not dealing with a trivial number of elements), I would rather use functional programming approaches to sort data into shape (think map/filter/reduce). These approaches typically result in passing over the data multiple times, and often performing multiple copies, but it makes for readable and less error prone code. Doing the performant thing consists of writing a for loop (or multiple of them unless you unroll) and automatically result with a large custom body of code performing multiple transformations on the data. It’s just wasted mental effort when you write it and every time when you happen to read it again.

Most collections/array I process have trivial number of elements (<100) and you get virtually no benefit from writing optimized code.

I have also written a lot of performant code, and the lesson is always benchmark benchmark benchmark. The results do not always fit the mental model about what you think should be the fastest. In particuliar avoiding cache misses is far more important than you might think.

Readable and less error prone? As opposed as to proven to be correct for example? Recursive functional code is a pain to prove to be right and not blow up stack. Multiple passes (when interspersed with other accesses) can blow up cache.

Even calling through a lambda is a cost compilers cannot easily optimize away unless you help them. (Even in C++.)

You do get the benefit of optimizing all the "trivial data size" code when it is all the functions being written in such silly way. Difference of 10% in one function as opposed to across whole application.

Benchmarking is often even harder to do right than writing good tests. (In fact is tied to it.) Instead of benchmarking, be a real computer scientist and prove bounds and memory allocations.

How is it difficult to prove if a recursive call is tail-recursive or not? If it's tail-recursive and your language supports tail-call optimisation then you proved that there will be no stack blow-up.

For simple calls, not. For something more involved? (Dependent functions, corecursion, partially stateful code.) Very which is why compilers fail to optimize it in general.

> Recursive functional code is a pain to prove to be right and not blow up stack.

Much easier to prove recursion correct than to prove a loop always terminates, since the recursion makes the way the state changes between steps much more explicit. If you're really worried about this you can use Idris and require all your functions to be total.

Plus some functional languages can combine those steps at compile, giving you the best of both worlds. Rust for example elides away many lambda's in map operations. I don't have the link handy, but a post a few months back showed Rust and Haskell functional patterns could almost match their hard coded imperative style implementations and C/C++ cousins.

Here it is: https://www.fpcomplete.com/blog/2017/07/iterators-streams-ru...

The key word is "often". Which means not always, which means you cannot rely on it unless you check all your code in Godbolt or equivalent.

Which used to be a common complaint of C and Pascal compilers against manually written Assembly code.

Performance is always an issue.

That said, I fully grant it may be an issue that is worth solving later in the process.

The later you do it, the more expensive it gets. In this it is similar to testing.

Fully agreed, though optimization is something that should come later. Otherwise, folks will spend too much time making a really tight loop that isn't actually run in a loop. :)

I also agree that folks should try to avoid poor habits. However, I'll note that even Knuth uses brute force for some parts of his programs. Quoting, "Brute force is the rule in this part of the program."[1] Sometimes, it really isn't the bottleneck. :)

[1] http://www-cs-faculty.stanford.edu/~knuth/programs/dance.w

Performant code vs readable code is a false dichotomy.

Do you have any evidence to back that statement up?

I think the proof should be on those who say that readable code cannot be performant.

I've never heard anyone say that.

I think the idea is: think about what you are doing. Choose the correct level of simplicity vs performance What I find is that it's rarely massive amounts of data that kills you, it's the polynomial effects that do. For example, if you have 3 collections of <100 and you do for-each-class of students, then for each class check which rooms are available, and for each room available see if the course can be in the room, you may have 100^3 tests though your data was trivially small. People benchmark and it looks fine (because they took 10 items each for their O(MNK) algorithm, and perhaps even tried (1001010) but when things later hit 100^3 in production everything grinds to a halt. This is why benchmarking is not always helpful in the early phase. Estimate the relations between the data sizes just slightly wrong and your estimate of performance might be 1000% off.

I work on a program with dozens of parts being fundamentally quadratic and several even NP, and I'm perpetually angry at my fellow developers for tackling O(N^k) things as O(N^(k+1)). Typically this is by the use of "subtly polynomial" things such as things.First(x => otherThings.Contains(...)) etc.

I'm all for the nice high level constructs, I just think tthat it needs to be carefully considered. And I don't agree with the "make the simple one first, and only optimize after benchmarking" because that just keeps proving useless (Pick too small dataset and benchmark is OK, and unless the algorithm is linear or better, it's trivial to choose N such that the performance is unacceptable in the benchmark. And whatever N you choose, customers will demand 2N tomorrow). I prefer a simpler solution, e.g. "in parts X and Y of the application we write the fastest things possible from the start, while in the remaining 80% of the app we write the clearest thing possible and don't optimize until we are certain it's needed".

Generally, performance is something you worry about when it becomes an issue. Otherwise you spend waaaay too much time on "performance" that have 0 benefit.

That said “Avoid multiple passes over the data when one would do", while true, often profound performance gains comes from insight into the domain, where the first pass is structuring it such that the subsequent queries and transformations are simple and quick.

Luckily for haskellers, GHC does a thing called fusion, which is an optimization that pipes together different operations on data, and avoids allocating intermediate results.

(https://www.stackbuilders.com/tutorials/haskell/ghc-optimiza...)

The vast majority of programming languages return an iterator when you use map, filter, etc. There is usually only one eager evaluation pass at the end that conerts the iterator to a list.

Most languages are capabale of inlining the "next" function of the iterator to generate almost the same code as a regular for loop.

The advice you quoted is the most valuable of all, in my opinion.

You give "map/filter/reduce" as an example and claim that theses approaches "typically result in passing over the data multiple times". No, since reduce can behave like map and filter, with a proper reduction function you only have to pass over the data once.

> Most collections/array I process have trivial number of elements (<100) and you get virtually no benefit from writing optimized code.

That is true for all other advice given in the original article, but not for this: A reduction function only needs one input element and the aggregate/result so far. This function then does not care whether it is called in the context of list or vector iteration, it will happily work with elements read from a stream or any other potentially destructive iterator. The benefit is obvious: Write & debug once, document and never touch the code again until the actual algorithm implemented there changes.

> No, since reduce can behave like map and filter, with a proper reduction function you only have to pass over the data once.

You can indeed - which is why reduce is relatively opaque and unmaintainable, and should be a last resort. Any given map/filter pipeline could be rewritten to reduce, and it quite possibly would perform better - but at the cost of not being able to test individual pipeline stages, nor inspect the intermediate results in a debugger. Most of the time that's a bad tradeoff.

I disagree. I does not have to be unmaintainable. The difference between chaining map/filter and a single reduce is mostly a syntax transformation plus a little bit of thinking upfront:

   ;; N.B.: Code was written here in a comment and never tested. 
   ;; It might need some of those: ')))))'
   (flet ((filter-element (element bucket)
            ;; all (filter...)s of your chain here
           )
          (mutate-element (element bucket)
            ;; apply all your (map...)s here
           ))
     (defun distill-magic (essence element)
        (if (not (filter-element element essence))
            essence
            (cons (mutate-element element essence) 
                   essence))))

The hard part is sometimes to reformulate the chain in a way that you only filter on either pre- or post-mutation data. If you can't, your most probably using the wrong algorithm. But fixing that, if it requires serious thinking, is something I defer to the moment it actually matters. I now can, because it is neatly encapsulated in a single, local function definition.

And yes, of course I can inspect intermediate results in a debugger: Just trace distill-magic or set a break point.

Ever heard of streams/iterators? Where data from the collection pass as a stream through all transformations only once. Code is readable and functional, and it only passes once through your collection.

> Totally disagree.

Hmm, I see....

> Most collections/array I process have trivial number of elements (<100)

Ah! ok that explains it.

> I would rather use functional programming approaches to sort data into shape (think map/filter/reduce). These approaches typically result in passing over the data multiple times, and often performing multiple copies,

That's a good recommendation. If you tend to write in a deforestable style (whether deforested automatically by the compiler or, by you manually) you can mitigate some gratuitous copying and multiple passes.

"When people train, they usually don’t try to actually run faster or lift heavier weights. As a relatively healthy computer science professor, how fast I run or how much I can lift is of no practical relevance. "

This is really strange. If you don`t try to lift heavier weights you will not have progress. It is called progressive loading. I don`t wan`t to go into the details of the training, but if you do not track and improve your training (with whatever goal you have in mind, there are different kinds of progressions) you are the same as the programmer who write bad code, and knows it is bad, but does not care.

> If you don`t try to lift heavier weights you will not have progress.

That depends on what you're aiming for - if you're aiming for tone rather than bulk, you'd go for more reps of the same weight rather than stepping up the weight with the same reps, wouldn't you?

(Although I guess, technically, that does count as "heavier" since you're still moving more weight in your sets.)

The general consensus is there's not really such thing as 'tone' - usually that's just a matter of low bodyfat % which shows your muscles more promimently.

What you're talking about somewhat though is balancing hypertrophy and strength goals - where someone may wish to increase their reps to say 8-20 which is demonstrated with studies to increase muscle size, but is poorer for progressing with strength (where 3-8 reps is more effective)

I interpreted that as "When people train, their goal in of itself is not usually to run faster or lift heavier weights". (the following might diverge from the actual content of the article, the author's english doesn't seem to be that great and I don't think we'll gain anything by taking the article literally)The goal might be overall health, attractiveness, etc. However, that doesn't mean they won't take the training seriously if they think it will help their larger goal. If you saw someone at the gym dilly dallying and doing a seriously half-assed rotation you might think they don't really care about their end goal.

In the same vein if you saw a programmer coding something extremely slow just because they couldn't be bothered to put in the tiny bit of extra effort to get to a baseline of performance you might think they don't take their job or future skillset very seriously. Always thinking about the performance of your implementation is a form of training just like lifting weights is. Even if you don't care about making this particular section of code fast, or you don't care whether this particular dumbbell is lifted up and down 10 times in a row, you do those things in service of a greater goal.

Regarding the point "Don’t use floating-point operations when integers will do." I agree that using integer arithmetic can result in cleaner, easier to reason about code when applicable. It then follows that because of these traits the software will faster.

But integer arithmetic is not necessarily faster than floating point arithmetic in general; see for example: https://youtu.be/3K2LmnaLLF8?t=31m10s.

Only if you either have to pay the extra cost of handling overflows, underflows, saturation or normalization. (First three involve conditionals which may be mispredicted, last a division or multiplication.) Likewise correct rounding. (Multiple math ops and sometimes a conditional too.)

Or when the platform has no integer vector math for your type of choice. Which is still somewhat common.

> But integer arithmetic is not necessarily faster than floating point arithmetic in general;

GPUs was the first place I feel like floats got a much better pathway than any other data type - graphical pixel manipulations also can get away with much higher arithmetic errors, because it's all going to get rounded down to a pixel eventually.

On the other hand, the only place where I've really worked heavily with fixed point was on a graphical interface toolkit (MIDP on ARM I was working with would've had to use softfp for floats, so fixed point was hugely superior).

Come on, all reasonable ARM have NEON and VFPv3 (including cortex M) about the only place I saw something that didn't was an old internet router. Hardware completely unsuited to maths.

Softfp does not preclude the use of floating point math at all. It means you pay an extra cost when passing floats as arguments. (Which means you should rather use a hardfp math library if possible.)

> Come on, all reasonable ARM have NEON and VFPv3 (including cortex M) about the only place I saw something that didn't was an old internet router

ARM MIDP UI code in 2003-2004 - very interesting chip (ARM926EJ-S [1]) ... not that I ever invented anything new to do all this, all of what I did was learn & repeat tricks from 1980s arcade consoles.

[1] - https://en.wikipedia.org/wiki/Jazelle#BXJ:_Branch_to_Java

There is indeed a point where being fit and clean turns into an obsession. There is such a thing as premature optimization.

Commonly the mistakes costing performance are caused in part by bad design though, typically arrived at by either not caring or not fixing a quick and dirty prototype with something reasonable. Or "brute force" bug fixing in concurrent code.

If I got paid for every unnecessary or replaceable synchronized statement in Java, I'd be rich. Or a fat data copy made using a queue.

> There is indeed a point where being fit and clean turns into an obsession. There is such a thing as premature optimization.

There is also something as no optimization (at any point), and I see far more often in the wild. I think more devs should run their app on a cheap Android phone or cheap consumer entry laptop to see what is happening when it's not running on 32 gb i7 octa cores. I recently got some entry level machine from a friend to play around with; it has 4gb and flash drive; it is eerie how slow the thing is; this is what is sold in walmart etc at the entry price level, so fair to say, if you are B2C software dev, this is your audience.

For fun, I tried to do some development on it; Atom/Vscode started both snappy, but when devving on it a bit, they became rapidly unusable (cpu 100% always and typing appearing seconds after you typed it); emacs was ok; vim did well. You cannot run Electron on that and yet, that's what many people deliver. And my suspicion is that most don't optimize when using that (if you are fast software minded, you wouldn't use it in the first place, not because it's inherently bad, but because there are too many moving parts you cannot influence). Please try it on these machines to know what you are doing to your users :)

1. Make it work

2. Make it right

3. Make it fast

"Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%." - Donald Knuth

The problem is that these rules should apply in sequence to a given feature or flow, but they're instead applied in sequence to the whole product. So what happens is: they make everything "work", then they spend the next two decades pecking at making it right, and making it fast takes a back seat.

Corollary: interaction latency, power consumption, and other performance characteristics should probably be part of "make it right", and "make it fast" might not even be a value at all.

The challenge there is that a lot of developers are pushed by their managers to go to the next feature after #1, postponing 2 and 3 for when there's time. Time to market is considered the most important thing. Of course, it accumulates after a year.

> pushed by their managers to go to the next feature

Understandable, though, since features are what get customers to pay - 99% of customers will not care about efficient code as long as they can achieve what they're after without screaming.

Things that are full of bugs and are sluggishly slow are what makes customers scream their lounges out 99% of the time.

This quote is so misunderstood and so abused all the time.

The point of the statement is to not micro-optimize this and that corner of the program without having any data to guide you on what you should optimize and how.

It's not a rallying call to forgo all concerns about application performance and efficiency.

The mis-application of this quote is the root of all evil in modern software IMO.

It's why a chat program takes 500MB of RAM and why many programs take 10 seconds to load even though there's no technical reason they cannot startup instantly.

You should make it right and fast from the very start. You should not make something that "works" but is full of bugs and slow as hell. Like, that makes no sense at all. If it's full of bugs then it doesn't work. If it's slow as hell then it doesn't work.

1. Make it work correctly and efficiently (to a reasonable degree)

2. Make it even faster

3. Make it better

> 1. Make it work correctly and efficiently (to a reasonable degree)

Unfortunately, this took your team 6 months and the people that launched their app 4 months ago (having opted for "make it work") now have 90% of your market and you've all just been made redundant because the customers do not care whether your app is "more correct" and "more efficient" because they just plain damn couldn't use it.

There's a reason "worse is better" applies to software.

There's no evidence than any of this is true.

First market is not often the winner. Facebook came very late to the social media scene but it dominated.

Google came very late to the search engine scene, and people don't even remember this but there was a time when there were a ton of search engines and anyone at the time would probably think that the search engine market is saturated and there's no space for a new product.

All evidence actually points to better products dominating the market even if they come late.

If your competitors released their app 4 months ahead of you but it was full of bugs and always hangs up, and then you release your product which actually works and performs well, people will see your product as a breath of fresh air.

Another example is the Chrome browser, which came at a time when Firefox and IE were competing fiercely for market share, and Chrome completely dominated them on the simple basis that it was _really fast_.

For most products it doesn't even cost 6 months to make it fast. If you have that as a goal from the very start, there will never be a stage of "omg it's really slow let's try to make it a bit faster". It will always just be fast.

> but it was full of bugs and always hangs up,

That doesn't really fit in the "make it work" that I specifically mentioned. If you change the scenario, sure, things could be different!

> Chrome completely dominated them on the simple basis that it was _really fast_.

It isn't that simple - a lot of Chrome's success came because they "made it work" in ways that Firefox (horribly wasteful of CPU, memory, battery life) and IE (shambles in every department) didn't. Also helped in large part by having an enormous web monopoly pushing it and favouring it for their properties.

But you're definitely right that it came after them.

"Worse is better" refers to interface complexity vs. implementation complexity, not to software quality.

The quoted example in https://www.jwz.org/doc/worse-is-better.html does make reference to software quality.

1. Make it work

2. Make it ... err actually fuck it, let's build a hairball on top of it.

That's how it really rolls.

You have to think it fast, think it right, then make it work because if you do it the other way round, it never happens.

You're conflating management and priority issues with programming issues.

The two are intertwined and inseparable.

> But then, I dress cleanly every single day even if I stay at home. And you should too.

Nope.

It's good to know how to produce fast software, but also good to know when to do so. Lemire sounds like he has some psychological issues to work out.

I’ve spent the last 20 years not caring about performance. Not once has performance ever been a real issue on any project I’ve been on. Imagine how much time I could have wasted prematurely optimising.

You've never written any code to run in parallel? Or used a data structure or algorithm with O(logN) time instead of O(N) time?

I probably have, without particularly prioritising it. Ok, perhaps I should have said "overly caring about performance". Of course I have used built in functions in languages that take advantage of this when searching or sorting - but no, I can't remember a time when I had to get into the nitty gritty of low level performance enhancement, unless it was in a coding challenge of course.

For most people, "seeing inefficient code" is basically hallucinating. There's real truth to the mantra about premature optimization. I've seen people so many times worry about the performance of something, thinking that some code looks slow, when in actual reality it's a complete nonissue.

Software development is all about compromises, just like any kind of real world engineering. Building a stage for a weekend festival is different from building a bridge over a river. We're always on a budget, so if I can work much faster and safer and lose some marginal efficiency, I'll do it—unless marginal efficiency is what I'm competing on, which it usually isn't.

There is a reason we don’t tend to hire people who show up to work in dirty t-shirts. It is not that we particularly care about dirty t-shirts, it is that we want people who care about their work.

I don't quite agree the cleanliness of clothing is a good proxy of one's craftsmanship or personality, even if t-shirts are acceptable garment at a particular workplace.

It maybe different in US. But in some Asian countries, most people care about the money at the end of the day.

So yea, they don't care. But does it matter ? People are happy as long as they get paid at the end of the day. They don't care about the quality of code written.

Not saying its a good thing or bad thing. Just the way it is.

I think of myself as a software craftsman. Just like a master carpenter, the things I make should be not only functional but beautiful as well. Of course we should "care" about our work.

However there are other metrics besides performance that are worth caring about, e.g. readability, maintainability, etc...

Meeting deadlines, getting paid, whether anyone will ever care about the code, again, etc.

I also try to be a 'craftsman', and I try to pick work where that's an option, but I find that in practice, more often than not I have to care about various 'other metrics' at the detriment of craftsmanship.

Although I suppose being skilled at managing these various metrics could in itself be considered craftsmanship. And perhaps that mindset helps a bit with not getting utterly depressed at some of the shit I'm forced to deliver...

Code bloat could easily be sorted out by forcing people to read the generated assembly of their creations.

This is easy and convenient in Common Lisp with the DISASSEMBLE built-in function.

Blah. You get a lot of performance "for free" by getting the overall architecture of a system right. By starting with optimizations, you usually hit the "limit of your brainpower" very soon, like before you know enough to architect things right, so you mess up the architecture (think like "shit, we ended up with this location dependent time conversion logic in the backend instead of on the clients, so now is un-cacheable, but it's too late to refactor across multiple teams now... shit").

Just avoid building un-optimizable systems (nowadays it's harder than ever to avoid this... all the tools and services lay traps for us), and then you can safely leave the optimizations for later...

If you can't avoid building an un-optimizable system, all your clever early optimizations are worthless anyway. If you can, they can be postponed anyway.

Now, what I'd really want to read would be an article/book about avoiding the traps that lead people to get stuck with un-optimizable systems! (Though I imagine it's in general an unsolvable problem if natural evolution didn't solve it either: at some point your body accumulated enough de-optimizations that it basically stops working or being fixable/optimizable, so you die, and some of your memes and genes carry on in "rewritten forks" aka "other newly born people".)

Reply on news.ycombinator.com