With software, there's always a better way to do it

[bitbank]

My latest blog post on open source software and (lack of) optimization

http://bitbanksoftware.blogspot.com/201 ... r-way.html

[Heater]

bitbank,

It's not surprised that the OpenEXR code you talk about is not particularly optimized. It's a reference implementation and as such I would expect it to be written for maximum accuracy, understandability and portability.

Whist your optimized version sounds like a grate piece of work I presume it does not run on any non-Intel architecture. It would not serve as a reference. Arguably you have de-optimized it by making something that does not even run in the general case.

From the end of your article:

Stating the Obvious
If you use open source libraries in your products or daily work it's fair to assume that they're not optimized.

This is not at all obvious. This is not a logical conclusion one can draw from your story.

There is all kind of software in the Free and Open Source software world. Of all kind of quality. Finding an example of non-optimized open source software does not prove anything about all the rest of it.

When you release your program as open source you will immediately counter your own statement. You are going to do your bit to help the world's software quality by releasing your code, right?

The bigger picture - the software that runs the world falls in the same bucket.

As I say this does not logically follow from your example. There is a lot of Open Source software, from the Linux kernel to the Google Chrome Javascript engine that gets a lot of attention re: performance.

Anyway, we look forward to seeing your source code.

[DougieLawson]

The bigger picture - the software that runs the world falls in the same bucket.

What on earth is that supposed to mean?

The software that runs the world has been developed over that last 50 years and is now being optimised in hardware with every new processor (just wait for commercial scale quantum computers). The compilers (even good old COBOL) have been making code that's as good or better than any human can write for many years. The SQL engines are re-writing queries to optimise them. So your assertation is entirely meaningless.

[jamesh]

Once you've taken the x264 open source library and optimised that run even faster then I think I might believe you.

Until then I found your article lacking in any real statistical relevance. You've extrapolated from one open source library to say the same thing happens in tens of thousands of other libraries which is not a valid extrapolation. Not only that but the library you've been talking about is a reference implementation which almost by definition is not optimised!

[Heater]

One question might be, why does Apple use an un-optimised reference version of this library?
Is it so that not many people use or care about this thing?

[jamesh]

One question might be, why does Apple use an un-optimised reference version of this library?
Is it so that not many people use or care about this thing?

Because perfection is the enemy of good enough?

[bitbank]

Once you've taken the x264 open source library and optimised that run even faster then I think I might believe you.

Until then I found your article lacking in any real statistical relevance. You've extrapolated from one open source library to say the same thing happens in tens of thousands of other libraries which is not a valid extrapolation. Not only that but the library you've been talking about is a reference implementation which almost by definition is not optimised!

My day job is optimizing other people's software. I'm constantly optimizing open source libraries that are used by many companies. There are plenty of examples of open source libraries that are getting optimization attention (e.g. x264), but the vast majority don't get that much scrutiny.

You seem to have missed my point that most of the time, the reference implementation becomes the only implementation. Private companies may optimize the code for their internal use, but the public version stays abandoned.

[bitbank]

The bigger picture - the software that runs the world falls in the same bucket.

What on earth is that supposed to mean?

The software that runs the world has been developed over that last 50 years and is now being optimised in hardware with every new processor (just wait for commercial scale quantum computers). The compilers (even good old COBOL) have been making code that's as good or better than any human can write for many years. The SQL engines are re-writing queries to optimise them. So your assertation is entirely meaningless.

Beating the compiler is what I do every day. Compilers are not good enough to beat humans (me), especially when it comes to SIMD. My changes to both the algorithm and instruction choices have dramatic effects on the performance. Setting the "-O3" switch and hoping for the best is a guaranteed way to get sub-optimal results.

[bitbank]

bitbank,

It's not surprised that the OpenEXR code you talk about is not particularly optimized. It's a reference implementation and as such I would expect it to be written for maximum accuracy, understandability and portability.

Whist your optimized version sounds like a grate piece of work I presume it does not run on any non-Intel architecture. It would not serve as a reference. Arguably you have de-optimized it by making something that does not even run in the general case.

From the end of your article:

Stating the Obvious
If you use open source libraries in your products or daily work it's fair to assume that they're not optimized.

This is not at all obvious. This is not a logical conclusion one can draw from your story.

There is all kind of software in the Free and Open Source software world. Of all kind of quality. Finding an example of non-optimized open source software does not prove anything about all the rest of it.

When you release your program as open source you will immediately counter your own statement. You are going to do your bit to help the world's software quality by releasing your code, right?

The bigger picture - the software that runs the world falls in the same bucket.

As I say this does not logically follow from your example. There is a lot of Open Source software, from the Linux kernel to the Google Chrome Javascript engine that gets a lot of attention re: performance.

Anyway, we look forward to seeing your source code.

The way I write code, I leave the reference implementation (original C/C++) code untouched and #ifdef in SIMD optimized code for each target architecture (usually X86+ARM). This allows the code to compile on any system and make use of target features when possible.

Yes, there are plenty of open source libraries that have been optimized, but it's the exception, not the norm.

This particular project (my OpenEXR implementation) was work for hire paid for by Google. It's up to them if it gets released to the public. So far, they have not released any of my FOSS optimizations due to "legal reasons". I assume other private companies are doing a lot of the same thing.

[Heater]

Sounds like you are doing great work there bitbank.

Sad part is that apparently none of this kind of work my you and others makes it back out of the company into the upstream projects or other Open Source repositories.

As such it may as well not exist for most of us and hence is not really worth talking about.

[jamesh]

The bigger picture - the software that runs the world falls in the same bucket.

What on earth is that supposed to mean?

The software that runs the world has been developed over that last 50 years and is now being optimised in hardware with every new processor (just wait for commercial scale quantum computers). The compilers (even good old COBOL) have been making code that's as good or better than any human can write for many years. The SQL engines are re-writing queries to optimise them. So your assertation is entirely meaningless.

Beating the compiler is what I do every day. Compilers are not good enough to beat humans (me), especially when it comes to SIMD. My changes to both the algorithm and instruction choices have dramatic effects on the performance. Setting the "-O3" switch and hoping for the best is a guaranteed way to get sub-optimal results.

This is quite the claim. I believe your last statement is also wrong. Modern compilers are spectacularly good, and will beat almost any human coder at almost everything. So you are in effect claiming you are one of the very very best coders in the world. Is that correct? If so, you should be working for in excess of 500k per year at one of the big ones, Google, Microsoft etc. Or certainly in the area of high frequency trading where they are desparate for coders like this. $1m at least per year for those guys! Nice one if you on that level of salary.

I used to think I was pretty good at code optimization, but I have been overtaken by better compilers and caching processors.

[bitbank]

What on earth is that supposed to mean?

The software that runs the world has been developed over that last 50 years and is now being optimised in hardware with every new processor (just wait for commercial scale quantum computers). The compilers (even good old COBOL) have been making code that's as good or better than any human can write for many years. The SQL engines are re-writing queries to optimise them. So your assertation is entirely meaningless.

Beating the compiler is what I do every day. Compilers are not good enough to beat humans (me), especially when it comes to SIMD. My changes to both the algorithm and instruction choices have dramatic effects on the performance. Setting the "-O3" switch and hoping for the best is a guaranteed way to get sub-optimal results.

This is quite the claim. I believe your last statement is also wrong. Modern compilers are spectacularly good, and will beat almost any human coder at almost everything. So you are in effect claiming you are one of the very very best coders in the world. Is that correct? If so, you should be working for in excess of 500k per year at one of the big ones, Google, Microsoft etc. Or certainly in the area of high frequency trading where they are desparate for coders like this. $1m at least per year for those guys! Nice one if you on that level of salary.

I used to think I was pretty good at code optimization, but I have been overtaken by better compilers and caching processors.

I get paid well, but not that well. If you know some people in the financial services industry, please hook me up

Compilers have come a long way in the last 10 years, but they can't know your data better than you do. I'm able to beat the compiler consistently because I can see the bigger picture while the compiler has to analyze each little loop and make safe guesses. One good example is in another blog post I wrote about using non-temporal writes versus normal writes:

http://bitbanksoftware.blogspot.com/201 ... in-uk.html

X86 and ARM compilers are pretty good because there are millions of users and they're a "squeaky" enough wheel to get the attention they need. Compilers for embedded systems (e.g. AVR/PIC/etc) are not close. Worse still are VLIW architectures like the Movidius. Their compiler (even several years after Intel bought them) generates sub-optimal code for every case. I can easily beat that compiler by a minimum of 2X for all possible situations (SIMD and regular C code). A recent contract I did at Google ATAP was rewriting Myriad2 code for a mobile device.

LLVM is way ahead of GCC, but even GCC has made some good improvements lately.

[ShiftPlusOne]

What on earth is that supposed to mean?

The software that runs the world has been developed over that last 50 years and is now being optimised in hardware with every new processor (just wait for commercial scale quantum computers). The compilers (even good old COBOL) have been making code that's as good or better than any human can write for many years. The SQL engines are re-writing queries to optimise them. So your assertation is entirely meaningless.

Beating the compiler is what I do every day. Compilers are not good enough to beat humans (me), especially when it comes to SIMD. My changes to both the algorithm and instruction choices have dramatic effects on the performance. Setting the "-O3" switch and hoping for the best is a guaranteed way to get sub-optimal results.

This is quite the claim. I believe your last statement is also wrong. Modern compilers are spectacularly good, and will beat almost any human coder at almost everything. So you are in effect claiming you are one of the very very best coders in the world. Is that correct? If so, you should be working for in excess of 500k per year at one of the big ones, Google, Microsoft etc. Or certainly in the area of high frequency trading where they are desparate for coders like this. $1m at least per year for those guys! Nice one if you on that level of salary.

I used to think I was pretty good at code optimization, but I have been overtaken by better compilers and caching processors.

I don't know how smart GCC is now, but not too long ago, people were getting very good results with hand written NEON instructions.

For example:
https://github.com/FFmpeg/FFmpeg/tree/m ... wscale/arm

Many emulators have to do this sort of thing to even be usable on ARM too.

[W. H. Heydt]

"Optimization" to programming is rather like "efficiency" to engineering. It depends on what you want to "effish".

Pure optimization may or may not be good, depending on context. Can the resultant code be maintained, and--especially--maintained by mere mortals, rather than requiring your god-like self to do so? (Remember...you could be hit by a truck at any time...or, given that you're in Florida, a passing hurricane or a falling bridge.) If not, the first time it breaks, there won't be anyone to fix it. Read up on how ditroff came to be as a good example. How much time does a system spend running the code? If it's only run sparingly, then the programmer's time to optimize it is being wasted. He should be working on some piece of code that is chewing up lot of machine cycles.

In addition to all that...if your company is using your optimized code in actual products that they sell to other people, by modifying GPL'd code, you are *required* by the GPL to give those customers access to the source code. The company you work for *is* doing that, aren't they? Because if they aren't, they no longer have a valid license to use that code.

[bitbank]

"Optimization" to programming is rather like "efficiency" to engineering. It depends on what you want to "effish".

Pure optimization may or may not be good, depending on context. Can the resultant code be maintained, and--especially--maintained by mere mortals, rather than requiring your god-like self to do so? (Remember...you could be hit by a truck at any time...or, given that you're in Florida, a passing hurricane or a falling bridge.) If not, the first time it breaks, there won't be anyone to fix it. Read up on how ditroff came to be as a good example. How much time does a system spend running the code? If it's only run sparingly, then the programmer's time to optimize it is being wasted. He should be working on some piece of code that is chewing up lot of machine cycles.

In addition to all that...if your company is using your optimized code in actual products that they sell to other people, by modifying GPL'd code, you are *required* by the GPL to give those customers access to the source code. The company you work for *is* doing that, aren't they? Because if they aren't, they no longer have a valid license to use that code.

You bring up a couple of good points:
1) I document everything with tons of comments and leave the original code in place, so that aids in understanding/maintenance. Much of my work is on productivity tools that help save time for the artists/developers and never ships. Some of it does ship in products and once I'm gone it may never get touched again. Then again, most software doesn't have a very long shelf life anyway and will be replaced in the near future.

2) Most of the optimization work I've done on open source code is not modifying the original code, but tossing it out and starting from a clean slate to replace it. I have made changes to FOSS code that ships in products and the project management team understands the GPL implications. I asked about the upstreaming process, but I hit a wall with the legal department. I'm not even an employee, so I have no voice in those decisions.

[ShiftPlusOne]

2) Most of the optimization work I've done on open source code is not modifying the original code, but tossing it out and starting from a clean slate to replace it. I have made changes to FOSS code that ships in products and the project management team understands the GPL implications. I asked about the upstreaming process, but I hit a wall with the legal department. I'm not even an employee, so I have no voice in those decisions.

If they understand the implications of GPL, what's the problem with you just sending the patch upstream?

[bitbank]

2) Most of the optimization work I've done on open source code is not modifying the original code, but tossing it out and starting from a clean slate to replace it. I have made changes to FOSS code that ships in products and the project management team understands the GPL implications. I asked about the upstreaming process, but I hit a wall with the legal department. I'm not even an employee, so I have no voice in those decisions.

If they understand the implications of GPL, what's the problem with you just sending the patch upstream?

I like working for them and don't want to step on toes. They paid for the changes, so it's really up to them what happens next.

[ShiftPlusOne]

2) Most of the optimization work I've done on open source code is not modifying the original code, but tossing it out and starting from a clean slate to replace it. I have made changes to FOSS code that ships in products and the project management team understands the GPL implications. I asked about the upstreaming process, but I hit a wall with the legal department. I'm not even an employee, so I have no voice in those decisions.

If they understand the implications of GPL, what's the problem with you just sending the patch upstream?

I like working for them and don't want to step on toes. They paid for the changes, so it's really up to them what happens next.

Ah ok, understandable.

[W. H. Heydt]

2) Most of the optimization work I've done on open source code is not modifying the original code, but tossing it out and starting from a clean slate to replace it. I have made changes to FOSS code that ships in products and the project management team understands the GPL implications. I asked about the upstreaming process, but I hit a wall with the legal department. I'm not even an employee, so I have no voice in those decisions.

If they understand the implications of GPL, what's the problem with you just sending the patch upstream?

I like working for them and don't want to step on toes. They paid for the changes, so it's really up to them what happens next.

Sounds like the company lawyers either don't really understand the GPL, or are living in a fool's paradise thinking they can ignore it. Someone should point out to them what happened to Cisco.

[W. H. Heydt]

Some of it does ship in products and once I'm gone it may never get touched again. Then again, most software doesn't have a very long shelf life anyway and will be replaced in the near future.

Sounds like famous last words. As for that last point...that varies all over the map. One program I wrote I heard back about over a decade later because in that time there was *one* application system abend attributed to it, this in spite of there being 11K lines of COBOL procedure code in that program.

[jamesh]

I really do think we're talking about refactoring or completely rewriting rather than optimisation. if you are throwing away the existing code and rewriting from scratch perhaps using Neon instructions that's not optimisation, that is a complete rewrite. You now have the opportunity to parallelize algorithms, or to completely rewrite them. It's like saying you've optimised a bubble sort by rewriting it as a quick sort.

None of these are things your compilers can actually do to any great extent, but what it can do is take your code as it stands and make it much more efficient than almost any human coder can do.

In effect you cannot polish a turd. A compiler can do a fantastic job of making your code efficient. Choosing the right data structures and algorithms in the first place gives the compiler a chance.

[jahboater]

Today I saw this comment on SO :

It is worth mentioning that in early 2018 the glibc devs spent a bunch of time replacing hand-written assembly implementations of math.h functions with C, because the compilers have caught up on those, and C is ever so much more maintainable.

I knew they had improved speed of some of the math functions in libc (for version 2.27) but I didn't know it was done simply by rewriting them in C ....

[Heater]

bitbank,

With software, there's always a better way to do it

True enough. The question might be: What do you mean by "better"?

Is maximum performance the main criteria? Or perhaps quick and cheap development time. Or a simple clear expression of an algorithm (As is the case with the reference example sited in the OP). Or perhaps maximum portability. And so on. Engineering is always a trade off between all the desirable features on wants.

Modern C/C++ compilers are hard to beat. But in my limited experience and judging by what others say, compilers are still not very good at adopting vector instructions to boost performance. So there is still scope for manual tweaking of programs to accelerate such things.

It seems similar to the way that compilers don't yet know how to spread a workload over many cores to gain performance. They can be helped with things like OpenMP though.

My beef with the linked article is that it is of no use to anyone. We don't get to see or use the code. Nothing to learn from. Working on closed source code whilst casting Open Source code in a bad light.

[bitbank]

bitbank,

With software, there's always a better way to do it

True enough. The question might be: What do you mean by "better"?

Is maximum performance the main criteria? Or perhaps quick and cheap development time. Or a simple clear expression of an algorithm (As is the case with the reference example sited in the OP). Or perhaps maximum portability. And so on. Engineering is always a trade off between all the desirable features on wants.

Modern C/C++ compilers are hard to beat. But in my limited experience and judging by what others say, compilers are still not very good at adopting vector instructions to boost performance. So there is still scope for manual tweaking of programs to accelerate such things.

It seems similar to the way that compilers don't yet know how to spread a workload over many cores to gain performance. They can be helped with things like OpenMP though.

My beef with the linked article is that it is of no use to anyone. We don't get to see or use the code. Nothing to learn from. Working on closed source code whilst casting Open Source code in a bad light.

Better in this case means that your time and energy are not wasted on inefficient software. If you're waiting for your machine to finish a task, that's lost productivity and probably wasted electricity too.

The point of the article is not to teach you how to do my job, but to raise awareness that just turning on the optimization flag is not sufficient. I keep being reminded that many of today's CS majors are good at an abstract understanding of programming, but don't really know how a computer works. They write terribly inefficient code; this hurts everyone. I'll give you another example. Out of curiosity, I bought a Leap Motion sensor to take a peek at (profile) their software. When running their simple demo app, my laptop CPU is somewhat stressed and I can see that 75% of the time is spent in malloc() and free(). Obviously the developers don't have a good understanding of efficient memory management and need to be taught the concept of memory pools and not allocating/freeing objects in inner loops.

[W. H. Heydt]

Better in this case means that your time and energy are not wasted on inefficient software. If you're waiting for your machine to finish a task, that's lost productivity and probably wasted electricity too.

While there are some specific--and not particularly common--exceptions, machine time in cheap and people time is expensive. A program has to be run a *lot* in order to be worth the time of a programmer to improve the speed, plus the improvement needs to be significant to be worth that effort.

The point of the article is not to teach you how to do my job, but to raise awareness that just turning on the optimization flag is not sufficient. I keep being reminded that many of today's CS majors are good at an abstract understanding of programming, but don't really know how a computer works. They write terribly inefficient code; this hurts everyone. I'll give you another example. Out of curiosity, I bought a Leap Motion sensor to take a peek at (profile) their software. When running their simple demo app, my laptop CPU is somewhat stressed and I can see that 75% of the time is spent in malloc() and free(). Obviously the developers don't have a good understanding of efficient memory management and need to be taught the concept of memory pools and not allocating/freeing objects in inner loops.

Newly minted members of any profession are going to be theory heavy and experience light. As for not really understanding computers...you've come to the right place. That's the whole point of the Raspberry Pi. Dr. Upton (and friends) noted that problem in incoming CS students so the whole point fo the project was to fix that problem while trying to generate more applicants to the Cambridge program.

It used to be--50+ years ago--that machine time was expensive and people time was (relatively) cheap. At that time, programmers spent a lot of time finding ways to make code run faster. This resulted--in part--in a lot of code that was very cleverly written and--therefore--couldn't be maintained or upgraded. Since the balance of cost shifted, and companies realized that being able to support the existing code base was necessary and often costly--especially if written for speed by very clever programmers--they opted insted for code that runs slower but can be worked on someone other than the one genius that wrote it.

As for your specific example...why do I suspect that it is written in an OO language and all the malloc/free activity is driven by the language and compiler design and isn't really in the hands of the actual programmers? This is not to say that a good programmer couldn't improve--or, at least--influence that behavior, but it might require doing things in ways that are obscure and warp the language design.

(FYI...I used to read psuedo-assembler listings from COBOL compiles to be sure the compiler was generating code that did what I intended. If he pseudo-assembler was correct, then I knew my COBOL source was correct.)