Sadly, HN was not able to help you understand what premature optimization is.
What the SQLite team did was systematically measure the performance of their system, identify potential bottlenecks/inefficiencies, create and measure improvements to these bottlenecks and choose the better option.
This is what we call optimization. Premature optimization is when you have no idea how your system really performs, but spend time trying to make it "better" without having a way to determine whether your change made any difference.
Yeah. We had an in house report generator that was epicly slow (about 7 minutes to gen a single report)
We frequently have strange issue come in cause fucking vendors can’t stop making changes, then saying “nobody changed anything that would cause that”!
Anyway. I told my boss I’m going to spend a day optimizing this, and got back “we had people try, it’s not really a valuable use of time”.
Long story short, I know that processing 10,000 lines of data should absolutely not take 7 minutes and now it doesn’t. Now we can run our entire day in 30 seconds. No threads. No async. Half a day of optimization.
I think part of the problem with optimization today is that people are completely clueless about how fast computers are, and thus stay happy with being slow just as a matter of ignorance. The FP community pushing that all optimization is premature optimization doesn’t help either.
Urgh, reminds me of a production error that was caused by a job running on a timer, assuming that some other job would have finished by then. That lead to two obvious questions:
- Why is it on a timer, instead of being triggered when the first job was done?
- Why was that first job taking over an hour to process XML data?
Turns out the second one was accidentally-quadratic, since it was parsing a whole document to process its first record; then re-parsing the whole document to process its second record; etc. and this made it very slow when the XML was reaching several hundred MB.
Unfortunately, the solution we went with was to set the timer to run 20 minutes later...
I remember when I was in COMPSCI-101 or something like that and was introduced to sorting, and after coming up with a basic bubble sort algorithm, thinking that there was no way that could be improved because it looked self-evident that you needed to do all the work the algorithm was doing or you couldn't be sure the list was really sorted. Then, of course, I was introduced to multiple better algorithms like merge sort and quick sort which showed just how wrong I was...
Perhaps, for the "scientist" writing that initial code, their algorithm was also already the best that could be done because they just don't know much about algorithms and techniques to make them faster?! But once you learn about things like divide-and-conquer, work avoidance etc. it becomes pretty much self-evident when your algorithm sucks... it's really not that hard - definitely not for people whose job is stuff like climate science who have a very good understanding of maths.
Maybe by teaching scientists the basic "smart" algorithms and just a little about algorithm analysis (Big O notation), massive computation improvements could be had.
For you, me and James Hiebert, this sort of optimisation is exhilarating. Getting a half-hour job down to milliseconds? Awesome!
But for the scientists that wrote the original code, maybe not. Maybe they think of this sort of thing as drudge work, something that doesn't really hold their interest. Their fun is in designing the mathematical concept, and turning it into code is just a chore.
So yeah, we could teach scientists. But even better would be if we could provide scientists with tools that are just naturally fast when expressing problems on their own terms.
The irony is that his solution has an unnecessary log(n) term, because it's finding each point independently instead of taking advantage of the fact that the input points are also a dense grid. ;) so it can probably run 2-10x faster than the optimized version, assuming that the function call to bin search is probably a lot more expensive than filling in the grid, which R can do internally.
(You don't have to binary search each time, you have a known starting point from the previous point. So you binary search once to find the top-left point and the rest is just checking if you moved into the next global grid cell.)
> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. And there are many, many, many, ways to write a program which make it “slow” to execute. “Slow” being… like really slow.
Nitpick: there are some languages where you can tell whether your program will terminate without running it. There are even languages where you can tell whether your program will be slow.
And there are even more specialised languages where any program will be 'fast'.
Obviously, these languages aren't Turing complete. It's an interesting exercise to explore the design space to find languages that are both useful and avoid being Turing complete.
Agda is an example of a language that allows you to run approximately any practical computation, but it's not Turing complete. Oversimplified: in Agda a program is only considered valid by the compiler, if it comes with a computer-checkable proof of halting on all inputs.
> Obviously, these languages aren't Turing complete.
Interestingly, a Turing complete language without non-halting programs could exist conceptually (rather, many do); it's just impossible to know it has that property (hard to use in practice if you don't know it has the guarantees you'd like), and it can't be finitely describable (impossible to implement a compiler for it which doesn't sometimes "succeed" at compiling invalid programs).
You can also construct programs in Turing complete languages to always halt (e.g. by bounding the number of iterations of all loops, usually with the tradeoff of limited input size).
I once took some matlab code and got a 200x+ improvement for a couple of days work, the code was atrocious. So it really matters to understand your tool. I think the person I took it from was afraid to change anything that worked after it was prototyped.
People always seem to think "premature optimization" means "premature optimization for speed". But there are lots of otherwise-good things that you can prematurely optimize for:
We've all seen codebases that are over-abstracted in the name of code reuse, or to adhere to this or that software design philosophy, and are nightmares as a result. "You Ain't Gonna Need It" is a restatement of the premature-optimization adage, just for a different metric.
People deal with the cognitive dissonance by calling these optimizations other things, like “architecture”. But at the end of the day, if you’re changing your architecture for any reason other than correctness, then you’re optimizing. And if you’re having a hard time doing it, then you probably waited too long.
“The Last Responsible Moment” is subtle. You have to include user benefit (they may not care yet) versus snowballing consequences of delay, versus having more and better information later on.
One of the things that drew me to CI/CD was the notion that you’re not going to get better at handling your problems by avoiding them. You can’t learn to pick your optimization battles if you never fight them. You won’t learn something I’ve been saying for almost 25 years now and I still haven’t heard come out of anyone else’s mouth: there are code changes that improve readability and performance. Making those changes as refactors is hardly ever premature.
"Premature optimisation" refers to speed or size. Using the phrase to talk about those other things is a stretch. (Except maybe cost.)
You can design for modularity, readability etc., but optimising for them doesn't sound right. Something to do with them not having well-defined, agreed-upon definitions of where the optimum is.
Usually this criticism doesn't even hold water if you put performance aside, since a set will often have nicer ergonomics if you find yourself reaching for it. I see far too much code that is like items.remove((item) => item == value) and if you're using the proper datastructure you don't have to handroll your implementations each time, because they are provided by default.
Except in your example I’ve had numerous cases where bugs have been introduced because the developer’s primary thinking to pick a set was “fast” and “no duplicates”, only to later realize that order of items is important. And looking back at their choice, dealing with 5-20 items, using a list and checking contains() not only had no performance impact but better reflects the intent of “no duplicates”. Instead the set is left in place and the dev fixing it usually copies the results in a list to be sorted the same order prior to being in the set...
"In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering." - Also Knuth
I agree. But it is critical to ensure that what one is improving is something worthwhile. 12% improvement in compute costs for a project with lots of compute spend = massive win. 12% improvement in compute costs for a hobby project running on a single VM = probably negligible. 12% improvement in function runtime some arbitrary place in the stack = possibly net negative, taking into account developer opportunity costs.
It is almost always useful to talk in terms of outcomes, ie benefits to customer/users/team/company.
A 12% overall improvement might be worthwhile. But you have to look at the bigger picture: if part A of your project takes 99.9% of the time, and part B takes 0.1% of the time, even a 100% improvement in part B (ie making it take 0 time) might not be worthwhile.
Any improvement is significant!! I spent a week implementing an optimization for my language (pypy's storage strategies) and ended up significantly slowing it down instead. It's not guaranteed.
I have massive respect for anyone who can pull off steady improvements, no matter how small.
That's the sad side. The flipside is that for the employers that _do_ care, being able to use a profiler and repeatedly identify optimizations is considered some sort of superpower that very few of your coworkers possess. :-)
Am I misunderstanding this or is this an article about how Chars[].resize works in a library they wrote by themselves ? Or is it a misunderstanding of how resize works in general ?
I am not trying to take anything away from the author but digging into assembly instead of simply looking up the docs seems like a long road to go for calling it an optimization.
Another thing is that why does this even exist ? The tests are showing some sql executions but is that real production executions or simply to test a possible optimization in a different context.
I am not mentioning in as a premature optimization because I am not sure whether I am bright enough to tell what is going on.
The deeper truth is more that impact derives from leverage.
Leverage might reside in architectural changes, but one can also imagine other dimensions (not just altitude in application level) that also confer leverage.
Maybe it's because I am experimenting with improving my posture through small and gradual optimizations, but I expected the article to be about small optimizations in your life, rather than code.
Readit News
Don't underestimate accumulation of small improvements.
What the SQLite team did was systematically measure the performance of their system, identify potential bottlenecks/inefficiencies, create and measure improvements to these bottlenecks and choose the better option.
This is what we call optimization. Premature optimization is when you have no idea how your system really performs, but spend time trying to make it "better" without having a way to determine whether your change made any difference.
http://james.hiebert.name/blog/work/2015/09/14/CS-FTW.html
We frequently have strange issue come in cause fucking vendors can’t stop making changes, then saying “nobody changed anything that would cause that”!
Anyway. I told my boss I’m going to spend a day optimizing this, and got back “we had people try, it’s not really a valuable use of time”.
Long story short, I know that processing 10,000 lines of data should absolutely not take 7 minutes and now it doesn’t. Now we can run our entire day in 30 seconds. No threads. No async. Half a day of optimization.
I think part of the problem with optimization today is that people are completely clueless about how fast computers are, and thus stay happy with being slow just as a matter of ignorance. The FP community pushing that all optimization is premature optimization doesn’t help either.
- Why is it on a timer, instead of being triggered when the first job was done?
- Why was that first job taking over an hour to process XML data?
Turns out the second one was accidentally-quadratic, since it was parsing a whole document to process its first record; then re-parsing the whole document to process its second record; etc. and this made it very slow when the XML was reaching several hundred MB.
Unfortunately, the solution we went with was to set the timer to run 20 minutes later...
Perhaps, for the "scientist" writing that initial code, their algorithm was also already the best that could be done because they just don't know much about algorithms and techniques to make them faster?! But once you learn about things like divide-and-conquer, work avoidance etc. it becomes pretty much self-evident when your algorithm sucks... it's really not that hard - definitely not for people whose job is stuff like climate science who have a very good understanding of maths.
Maybe by teaching scientists the basic "smart" algorithms and just a little about algorithm analysis (Big O notation), massive computation improvements could be had.
But for the scientists that wrote the original code, maybe not. Maybe they think of this sort of thing as drudge work, something that doesn't really hold their interest. Their fun is in designing the mathematical concept, and turning it into code is just a chore.
So yeah, we could teach scientists. But even better would be if we could provide scientists with tools that are just naturally fast when expressing problems on their own terms.
(You don't have to binary search each time, you have a known starting point from the previous point. So you binary search once to find the top-left point and the rest is just checking if you moved into the next global grid cell.)
https://www.youtube.com/watch?v=c33AZBnRHks
> Furthermore, there is literally no way to tell whether your program will ever actually terminate without actually executing it. And there are many, many, many, ways to write a program which make it “slow” to execute. “Slow” being… like really slow.
Nitpick: there are some languages where you can tell whether your program will terminate without running it. There are even languages where you can tell whether your program will be slow.
And there are even more specialised languages where any program will be 'fast'.
Obviously, these languages aren't Turing complete. It's an interesting exercise to explore the design space to find languages that are both useful and avoid being Turing complete.
Agda is an example of a language that allows you to run approximately any practical computation, but it's not Turing complete. Oversimplified: in Agda a program is only considered valid by the compiler, if it comes with a computer-checkable proof of halting on all inputs.
Interestingly, a Turing complete language without non-halting programs could exist conceptually (rather, many do); it's just impossible to know it has that property (hard to use in practice if you don't know it has the guarantees you'd like), and it can't be finitely describable (impossible to implement a compiler for it which doesn't sometimes "succeed" at compiling invalid programs).
“The Last Responsible Moment” is subtle. You have to include user benefit (they may not care yet) versus snowballing consequences of delay, versus having more and better information later on.
One of the things that drew me to CI/CD was the notion that you’re not going to get better at handling your problems by avoiding them. You can’t learn to pick your optimization battles if you never fight them. You won’t learn something I’ve been saying for almost 25 years now and I still haven’t heard come out of anyone else’s mouth: there are code changes that improve readability and performance. Making those changes as refactors is hardly ever premature.
You can design for modularity, readability etc., but optimising for them doesn't sound right. Something to do with them not having well-defined, agreed-upon definitions of where the optimum is.
"Use a set instead of a list, it's faster". "that's premature optimization!"
I have massive respect for anyone who can pull off steady improvements, no matter how small.
Unfortunately not a lot of employers consider this a good use of time.
I am not trying to take anything away from the author but digging into assembly instead of simply looking up the docs seems like a long road to go for calling it an optimization.
Another thing is that why does this even exist ? The tests are showing some sql executions but is that real production executions or simply to test a possible optimization in a different context.
I am not mentioning in as a premature optimization because I am not sure whether I am bright enough to tell what is going on.
Please clarify
Leverage might reside in architectural changes, but one can also imagine other dimensions (not just altitude in application level) that also confer leverage.
Would appreciate it if you could share more.
(I am suffering from back pain from several years)