Got myself a few months ago into the optimization rabbit hole as I had a slow quant finance library to take care of, and for now my most successful optimizations are using local memory allocators (see my C++ post, I also played with mimalloc which helped but custom local memory allocators are even better) and rethinking class layouts in a more “data-oriented” way (mostly going from array-of-structs to struct-of-arrays layouts whenever it’s more advantageous to do so, see for example this talk).
What are some of your preferred optimizations that yielded sizeable gains in speed and/or memory usage? I realize that many optimizations aren’t necessarily specific to any given language so I’m asking in !programming@programming.dev.
Unrolled a loop for a microcontroller and improved performance by like 300x. You can achieve amazing optimizations doing basics when you’re at low enough levels. The compiler was not smart enough on its own. Then again this was like 20 years ago. But anyway, will likely never hit that level of optimization ever again lol.
Lemmy is probably a good live example of how sometimes going for a “faster language” like Rust isn’t going to magically make a bad SQL database design better or slow queries faster: https://github.com/LemmyNet/lemmy/issues/2877
So yeah, SQL optimization stories are definitely welcome too!
I patched someone else’s program which was known for being slower when it’s used for a longer time. It was iterating over items in its window just to reach the last element, the more items the slower, it became snappy when i taught it to keep a pointer to the last element.
Not mind blowing, I know, but it was a popular program and this made life better for many people.
Was working on a game where we drew a fake audio graph to a black texture. The code originally cleared this texture every frame by drawing each pixel black before drawing the audio wave again. I cached the pixels we drew the audio wave to and only changed those back to black saving a huge amount of time.
I just recently updated a database call to return the last 7 days of data instead of all data from all time. It went from taking 30+seconds to around 2-4 seconds. Still a long way to go to make it “good” but at least it’s not timing out now.
I was working on a pretty well known game, porting it to consoles.
On PS4 we started getting OOM crashes after you’ve played a few levels, because PS4 doesn’t have that much memory. I was mostly new on the project and didn’t know it very well, so I started profiling.
It turned out that all the levels are saved in a pretty descriptive JSON files. And all of them are in Unity’s Scriptable Objects, so even if you are not playing that level, they all get loaded into memory, since once something references a SO, it gets loaded immediately. It was 1.7Gb of JSON strings loaded into memory once the game started, that stays there for the whole gameplay.
I wrote a build script that compresses the JSON strings using gzip, and then uncompresses it when loading the actual level.
It reduced the memory of all the levels to 46Mb down from 1.7Gb, while also reduced the game load by around 5 seconds.
I’ve got so many more stories about bad optimizations. I guess I’ll pick one of those.
There was an infamous (and critical) internal application somewhere I used to work. It took in a ton of data, putting it in the database, and then running a ton of updates to populate various fields and states. It was something like,
Put all data in x table with batch y.
Update rows in batch y with condition a, set as type a. (just using letters as placeholders for real states)
Update rows in batch y that haven’t been updated and have condition b, set as type b.
Update rows in batch y that haven’t been updated and have condition c, set as type c.
Update rows in batch y that have condition b and c and condition d, set as type d.
(Repeat many, many times)
It was an unreadable mess. Trying to debug it was awful. Business rules encoded as a chain of sql updates are incredibly hard to reason about. Like, how did this row end up with that data??
Me and a coworker eventually inherited the mess. Once we deciphered exactly what the rules were and realized they weren’t actually that complicated, we changed the architecture to:
Pull data row by row (instead of immediately into a database)
Hydrate the data into a model
Set up and work with the model based on the business rules we painstakingly reverse engineered (i.e. this row is type b because conditions x,y,z)
Insert models to database in batches
I don’t remember the exact performance impact, but it wasn’t markedly faster or slower than the previous “fast” SQL-based approach. We found and fixed numerous bugs, and when new issues came up, issues could be fixed in hours rather than days/weeks.
A few words of caution: Don’t assume that building things with a certain tech or architecture will absolutely be “too slow”. Always favor building things in a way that can be understood. Jumping to the wrong tool “because it’s fast” is a terrible idea.
If you think it’s slow, first prove it with a benchmark
So many crimes against maintainability are committed in the name of performance. Optimisation tears down abstractions, exposes internals, and couples tightly. If you’re choosing to shoulder that cost, ensure it is done for good reason.
In another project, I had some throwaway code, where I used a naive approach that was easy to understand/validate. I assumed I would need to replace it once we made sure it was right because it would be too slow.
Turns out it wasn’t a bottleneck at all. It was my first time using Java streams with relatively large volumes of data (~10k items) and it turned out they were damn fast in this case. I probably could have optimized it to be faster, but for their simplicity and speed, I ended up using them everywhere in that project.
Noticed that Hibernate session (DB ORM session) was leaking to Jackson (JSON marshalling), potentially causing infinite n+1 problem. Changing a few lines of code to lazy loading and fixing the session leak reduced our daily data transfer from DB from 5.6Gb to 170Mb.
Not sure if this was the biggest optimisation, but definitely the dumbest issue.
I was playing bloons td back when it was flash, in firefox. It was sometimes too slow. So i fired up perf and found out what horrors flash player was doing with memcpy. One byte memcpy, completely unaligned memcpy.
So i wrote an ssse3 memcpy that could do one byte unaligned with xmm registers. It was 30% faster then whatever glibc was doing and made the game playable. Was planing to submit it to glibc, but they came up with something different that was just as fast.
ok maybe not my biggest or cleanest optimization, but an interesting one
I made the WCS Predictor for StarCraft 2 eSports, which would simulate the whole year of tournaments to figure out the chances for each player qualifying for the world championship (the top 16 players by WCS Points), and it would also show the events that would help/hurt the players. It was a big monte carlo simulation that would run millions of iterations. (My memory is fuzzy here because this was 2013 to 2014)
Originally I did a data-based approach where each Tournament object had a vector of Round objects (like round of 32, or semifinals, etc) which had a vector of Match objects (like Soulkey vs Innovation, or a 4 player group). The Round class had a property for best_of (best of 3, best of 5, etc). This was really inflexible cause I couldn’t properly simulate complex tournament formats that didn’t fit my data, and it required a lot of if statements that could cause branch prediction misses.
A tournament definition looked something like this:
When I rewrote it for the following year, I ditched the data-driven approach to try to get more efficiency and flexibility, but I definitely didn’t want virtual functions either, so I decided to use templates instead and a custom class for each tournament. Now creating a tournament looked like this:
All data had very good locality using arrays instead of vectors, everything could be inlined and branch predicted and prefecthed, complex tournament formats could be built even properly handling high placements from one tournament granting you seeding into a different tournament. I think I gained like 3x to 5x speedboost from this alone, I also made it multithreaded and work in batches which improved performance further, which allowed me to get updated results more quickly and with a higher number of samples. I also made it so it could output the results and then keep processing more batches of samples to refine the numbers from there. I wouldn’t normally suggest these kinds of optimizations but it’s a very unusual program to have such a wide hotloop
The website is gone, but here’s a working archive of it (which I didn’t know existed until writing this post, I thought there were only broken archives)
archive links, me reminiscing on old times, get ready for stats and graphs overload
A database optimization I made was changing a tables id generation from a manual generation scheme (some other table had an entry with the next usable id, it was updated with every entry written) to a uuid generation scheme. The table stores data from a daily import, on a fresh import all previous data is deleted. On some systems, there are more than 10 000 000 entries to be imported on a daily basis, which took 8 hours. Now, with batched inserts and the mentioned improvement in the db scheme, it’s at about 20 minutes.
TLDR: Reducing the amount of queries sent is good, because although network is usually fast (ms), db requests are still slow compared to the speed of an application (clock cycles).
And yeah, there is an option to only import changes daily, but sadly that isn’t supported in every environment.
As a more fun or absurd anecdote, I reviewed a change in a SQL server stored procedure that merely copied the parameter value into a variable, solving a significant performance issue.
The query optimizer on first invocation determines the optimal query execution and resolution approach. For a stored procedure with parameters, parameter values can change what the best approach is.
In this case, the parameter could hold a record ID or null for all records. Because it included sub queries, whether it’s one or the other makes a huge difference on the query execution approach.
Using an intermediate variable prevents it of taking and remembering the optimization path for the other case.
You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !programming@programming.dev
Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!
Cross posting is strongly encouraged in the instance. If you feel your post or another person’s post makes sense in another community cross post into it.
Hope you enjoy the instance!
Rules
Rules
Follow the programming.dev instance rules
Keep content related to programming in some way
If you’re posting long videos try to add in some form of tldr for those who don’t want to watch videos
Unrolled a loop for a microcontroller and improved performance by like 300x. You can achieve amazing optimizations doing basics when you’re at low enough levels. The compiler was not smart enough on its own. Then again this was like 20 years ago. But anyway, will likely never hit that level of optimization ever again lol.
I don’t know if this counts, but making sure not a single query in my app results in a full table scan in MySQL made a huge difference.
Lemmy is probably a good live example of how sometimes going for a “faster language” like Rust isn’t going to magically make a bad SQL database design better or slow queries faster: https://github.com/LemmyNet/lemmy/issues/2877
So yeah, SQL optimization stories are definitely welcome too!
That was a good read. Thanks for the link.
I read through most of this and it was very informative. Thank you very much.
I patched someone else’s program which was known for being slower when it’s used for a longer time. It was iterating over items in its window just to reach the last element, the more items the slower, it became snappy when i taught it to keep a pointer to the last element.
Not mind blowing, I know, but it was a popular program and this made life better for many people.
Was working on a game where we drew a fake audio graph to a black texture. The code originally cleared this texture every frame by drawing each pixel black before drawing the audio wave again. I cached the pixels we drew the audio wave to and only changed those back to black saving a huge amount of time.
I remember getting 9x improvement on a set of Shell scripts at work, piping the results instead of writing and reading from files at each step.
I just recently updated a database call to return the last 7 days of data instead of all data from all time. It went from taking 30+seconds to around 2-4 seconds. Still a long way to go to make it “good” but at least it’s not timing out now.
Meme answer: Changed a manual wait from 20 seconds to 18 seconds. Boom, 10% performance improvement. I can only do it so often though.
I was working on a pretty well known game, porting it to consoles.
On PS4 we started getting OOM crashes after you’ve played a few levels, because PS4 doesn’t have that much memory. I was mostly new on the project and didn’t know it very well, so I started profiling.
It turned out that all the levels are saved in a pretty descriptive JSON files. And all of them are in Unity’s Scriptable Objects, so even if you are not playing that level, they all get loaded into memory, since once something references a SO, it gets loaded immediately. It was 1.7Gb of JSON strings loaded into memory once the game started, that stays there for the whole gameplay.
I wrote a build script that compresses the JSON strings using gzip, and then uncompresses it when loading the actual level.
It reduced the memory of all the levels to 46Mb down from 1.7Gb, while also reduced the game load by around 5 seconds.
I don’t want to know how many rushed games so stuff like this
See now we want to know what game it was…
Memorization of pure functions can make a WORLD of difference. It’s just not as easy as it should be.
I’ve got so many more stories about bad optimizations. I guess I’ll pick one of those.
There was an infamous (and critical) internal application somewhere I used to work. It took in a ton of data, putting it in the database, and then running a ton of updates to populate various fields and states. It was something like,
It was an unreadable mess. Trying to debug it was awful. Business rules encoded as a chain of sql updates are incredibly hard to reason about. Like, how did this row end up with that data??
Me and a coworker eventually inherited the mess. Once we deciphered exactly what the rules were and realized they weren’t actually that complicated, we changed the architecture to:
I don’t remember the exact performance impact, but it wasn’t markedly faster or slower than the previous “fast” SQL-based approach. We found and fixed numerous bugs, and when new issues came up, issues could be fixed in hours rather than days/weeks.
A few words of caution: Don’t assume that building things with a certain tech or architecture will absolutely be “too slow”. Always favor building things in a way that can be understood. Jumping to the wrong tool “because it’s fast” is a terrible idea.
Edit: fixed formatting on Sync
If you think it’s slow, first prove it with a benchmark
So many crimes against maintainability are committed in the name of performance. Optimisation tears down abstractions, exposes internals, and couples tightly. If you’re choosing to shoulder that cost, ensure it is done for good reason.
Yep, absolutely.
In another project, I had some throwaway code, where I used a naive approach that was easy to understand/validate. I assumed I would need to replace it once we made sure it was right because it would be too slow.
Turns out it wasn’t a bottleneck at all. It was my first time using Java streams with relatively large volumes of data (~10k items) and it turned out they were damn fast in this case. I probably could have optimized it to be faster, but for their simplicity and speed, I ended up using them everywhere in that project.
Noticed that Hibernate session (DB ORM session) was leaking to Jackson (JSON marshalling), potentially causing infinite n+1 problem. Changing a few lines of code to lazy loading and fixing the session leak reduced our daily data transfer from DB from 5.6Gb to 170Mb.
Not sure if this was the biggest optimisation, but definitely the dumbest issue.
I was playing bloons td back when it was flash, in firefox. It was sometimes too slow. So i fired up perf and found out what horrors flash player was doing with memcpy. One byte memcpy, completely unaligned memcpy.
So i wrote an ssse3 memcpy that could do one byte unaligned with xmm registers. It was 30% faster then whatever glibc was doing and made the game playable. Was planing to submit it to glibc, but they came up with something different that was just as fast.
ok maybe not my biggest or cleanest optimization, but an interesting one
I made the WCS Predictor for StarCraft 2 eSports, which would simulate the whole year of tournaments to figure out the chances for each player qualifying for the world championship (the top 16 players by WCS Points), and it would also show the events that would help/hurt the players. It was a big monte carlo simulation that would run millions of iterations. (My memory is fuzzy here because this was 2013 to 2014)
Originally I did a data-based approach where each Tournament object had a vector of Round objects (like round of 32, or semifinals, etc) which had a vector of Match objects (like Soulkey vs Innovation, or a 4 player group). The Round class had a property for best_of (best of 3, best of 5, etc). This was really inflexible cause I couldn’t properly simulate complex tournament formats that didn’t fit my data, and it required a lot of if statements that could cause branch prediction misses.
A tournament definition looked something like this:
older code example
When I rewrote it for the following year, I ditched the data-driven approach to try to get more efficiency and flexibility, but I definitely didn’t want virtual functions either, so I decided to use templates instead and a custom class for each tournament. Now creating a tournament looked like this:
newer code example
All data had very good locality using arrays instead of vectors, everything could be inlined and branch predicted and prefecthed, complex tournament formats could be built even properly handling high placements from one tournament granting you seeding into a different tournament. I think I gained like 3x to 5x speedboost from this alone, I also made it multithreaded and work in batches which improved performance further, which allowed me to get updated results more quickly and with a higher number of samples. I also made it so it could output the results and then keep processing more batches of samples to refine the numbers from there. I wouldn’t normally suggest these kinds of optimizations but it’s a very unusual program to have such a wide hotloop
The website is gone, but here’s a working archive of it (which I didn’t know existed until writing this post, I thought there were only broken archives)
archive links, me reminiscing on old times, get ready for stats and graphs overload
home page: https://web.archive.org/web/20150822091605/http://sc2.4ever.tv:80/
a tournament page: https://web.archive.org/web/20160323082041/http://sc2.4ever.tv/?page=tournament&tid=27
a player’s page: https://web.archive.org/web/20161129233856/http://sc2.4ever.tv/?pid=73
a general checkup page: https://web.archive.org/web/20161130055346/http://sc2.4ever.tv/?page=checkup
a page for players who must win tournaments to qualify: https://web.archive.org/web/20161129235740/http://sc2.4ever.tv/?page=must_wins
page showing the simulations history: https://web.archive.org/web/20161130055230/http://sc2.4ever.tv/?page=simulations
FAQ page: https://web.archive.org/web/20160323073344/http://sc2.4ever.tv/?page=faq
the fantasy league WCS Wars: https://web.archive.org/web/20161130055233/http://sc2.4ever.tv/?page=gamehome
my WCS Wars user page https://web.archive.org/web/20160704040152/http://sc2.4ever.tv/?page=user&uid=1
A database optimization I made was changing a tables id generation from a manual generation scheme (some other table had an entry with the next usable id, it was updated with every entry written) to a uuid generation scheme. The table stores data from a daily import, on a fresh import all previous data is deleted. On some systems, there are more than 10 000 000 entries to be imported on a daily basis, which took 8 hours. Now, with batched inserts and the mentioned improvement in the db scheme, it’s at about 20 minutes.
TLDR: Reducing the amount of queries sent is good, because although network is usually fast (ms), db requests are still slow compared to the speed of an application (clock cycles).
And yeah, there is an option to only import changes daily, but sadly that isn’t supported in every environment.
As a more fun or absurd anecdote, I reviewed a change in a SQL server stored procedure that merely copied the parameter value into a variable, solving a significant performance issue.
The query optimizer on first invocation determines the optimal query execution and resolution approach. For a stored procedure with parameters, parameter values can change what the best approach is.
In this case, the parameter could hold a record ID or null for all records. Because it included sub queries, whether it’s one or the other makes a huge difference on the query execution approach.
Using an intermediate variable prevents it of taking and remembering the optimization path for the other case.