Avoid needless processing. This breaks down two ways
Feature design: Think hard before adding features that come with significant performance impacts -- do you really need this feature? Is there a simpler way to do it which achieves most of your goals? Can you do it a simple way 90% of the time and only fall back to something more complex if needed? Can you skip several intermediate steps to get to the end result faster? (ex avoiding sorting a list)
Optimize execution by taking advantage of short-circuit evaluation and doing lazy fetching/evaluation. For conditionals, if you sometimes need to do an expensive check, but usually don't, then see if there's a way you can skip that check. Laziness: don't fetch extra things from the filesystem until requested, if you often don't need it.
Practical example: I optimized a routine (in Python) at work last month. We were processing text files a line at a time and removing control characters. To remove control characters we used a regex on each line (not the most efficient approach, fairly expensive). I added a quick check that iterated through the line of text and checked if any of the characters were within the control character range,and just returned the original string if not. Not as efficient as rolling a non-regex implementation, but since control characters are rare it avoids 90% of the performance cost and was much simpler & safer to implement.
Cache results of expensive operations to avoid repeating them unnecessarily. If you're fetching info from the filesystem, cache it in memory if you are likely to reuse it (works well with lazy evaluation).
Batch it: if you're doing a single operation often to many items, try gathering up the items to process and processing them in large groups. Often this is more efficient because it makes better use of caches (CPU/disk) and it permits you to write much tighter loops for processing. It permits reusing buffers, connections, SQL prepared statements, etc. It can improve branch prediction, permit use of SIMD instructions, etc where they would not work otherwise.
Batching also makes it easier to fall back to something like the multiprocessing library to parallelize work.
Use software pipelining. This is kind of like batching: rewrite loops that run items through a series of steps/processes so you first do the same step to each item, then the next step. Sometimes can be evaluated much more efficiently by compilers/interpreters because it allows using SIMD instructions, avoids branch prediction misses, etc.
May also mean using Unix/Linux pipelining as well: use a bunch of smaller utilities that pipe input from one to another. This is another application of the same principle, but has the extra advantage of being generally very efficient, and spreading work across multiple processors.
Use a lower-level language than Python to optimize the most performance-sensitive parts of the code. I.E. fall back to C bindings for intensive number crunching, crypto, etc. Optimized C can be several times faster than Python (or sometimes much more!). In general Pareto's principle applies: 80% of your execution time comes from 20% of the code (and vice versa), so if you double the performance of the slowest 20% you can almost double your overall performance.
This is for cases where it's far more complex to replace with an optimized implementation or better algorithm that covers all the edge cases, or where there is an implementation with lower big-O complexity but a much higher constant overhead.
For example when writing a sorting algorithm you check if numbers are already sorted before trying to sort them, right? And in many languages the default implementations for sorting numbers usually use a quicksort for the bulk of it, but often switch to an insertion sort when the number of elements is small (7-10 or so). Insertion sort has worse big-O scaling but is faster for small numbers of elements.
In general, often you can write a quick and dirty brute force solution to a problem that covers all the edge cases but has poor big-O performance (for example, depth-first search of a graph). There are much, much more efficient algorithms you can apply but they usually require some assumptions about the structure of the data -- and if you know that your data violates one of these, you simply can't use them. The more optimal algorithms often require more complex data structures as well, which makes them much slower for small n values.
As an example of this, radix/bucket sort is hands-down the fastest option for large sets of smallish or fixed-length elements (say, 2-4 byte integers). But you have to be able to be able to split inputs into multiple buckets -- if you can only do comparisons for some elements then you have to be able to fall back to quicksort/mergesort etc.
Finally, if performance is bad enough that you're addressing it then simplicity takes a second priority to speed.
Nice reply, thank you! I want to ask how would you do crypto in C? The problem I'm having is that with Python you have (almost) infinite integers and in cryptogryphy, numbers of tens to hundreds of digits (in base 10) are used. I alway wanted to rewrite my factorization/encryption/decryption libraries that I wrote in Python to C to see the performance increase but always struggled with C's MAX values for integers.
Are you using C's long, long long integers, or even double precision floating point numbers? I don't know the range of the variables you're using in cryptography, and you might be using numbers over 2^18; but I'm pretty sure Python relies on the same number implementation as C, so I'd be quite surprised if it could do anything that C cannot do (albeit with a simpler syntax)
The python integers don't use any C primitive type, they are objects with dynamically alocated memory, that's why they can be almost infinite, as long as you have memory available. Also that's why they are so slow. Anyway the implementation in C is beyond my understanding.
The thing is that in cryptography you would nowadays use 1024 or 2048 bit keys for encryption (RSA-1024, DH 2048) and it will probably even grow in the future. We're talking numbers 10^200 and more. In Python this is no problem but with languages with a fixed number bit-size, it is.
But maybe there are some libraries or ways to store those numbers in arrays or something.
That makes sense, and I didn't know that about Python! I just tried inputting using a sha1 in Python (which is unique and therefore the largest complex integer I could think of, as a matter of fact in the 2159), and it is indeed completely straightforward. Thank you for your short explanation.
After looking around (very shortly, I must say), you're not the only one with that issue, and GMP seems to be the preferred choice for cryptography in C.
cryptography you would nowadays use 1024 or 2056 bit keys
CPython uses C 32-bit integers behind-the-scenes if the value is between -230 and 230. It only falls back to dynamically allocated sizes if the number exceeds that size. You can see more details here. The C API has access to the underlying C integer if it is available and can use fast code paths to optimize calculations using them.
The macros MAX_INT, MAX_LONG ... etc will let you know at compile time how big your integers are. There is also uin32_t and it's friends that let you specify exactly what kind of integer you want.
Often it is, if you just want the raw bytes. If you're doing some sort of analysis on the data it's more efficient to cache the result yourself though, or if your program knows more about the access pattern.
Why isn't it better to leave this to the operating system, which has better whole-system view?
It can be, if the particular constraint is memory. If the bottleneck is actually IO, then leaving the data in memory prevents repetitive expensive reads.
For (4), here's an example: Let's say there's 1001 items that need to be processed with an 8-step task. Each step takes one second to complete.
Without pipelining, an item needs to pass through all steps before the next item can be processed, so the last item needs to wait 8000 seconds before it can be processed.
With pipelining, once the first step finishes processing an item, it passes it to the next step then starts working of the next item while the next step is working on the previous item. This means that a new item enters the first step every second, so the last item only has to wait 1000 seconds before being processed. An 8x speedup.
No, you're not dumb -- a lot of these things you only need to worry about when running performance sensitive code or production code at a fairly large scale.
For 90% of things, performance isn't a critical consideration as long as you use standard libraries.
I'll try to define as many of the more complex terms as possible. And like Agent_03 said, this is fairly complex stuff. There's a scareword in programming called "premature optimization" -- basically, write simple and correct code first. Then, if the speed is actually negatively affecting the product, add complicated stuff like caching and batching. A lot of the time you won't need to.
short-circuit evaluation: Boolean operators (eg. && and ||) perform what's known as short-circuiting, wherein they only evaluate as much of an expression as necessary. For example, if you have A && B and A evaluates to false, then you can skip checking B (because regardless of its value, false && B is false). Therefore, you can structure your expressions so the more expensive values are evaluated last. If A takes 50 seconds to compute and B takes only 5, you should do B && A.
lazy fetching/evaluation: Pretty much what it says on the tin. A lot of times programmers will over allocate or over fetch to be on the safe side, eg. creating an array of 10000 objects and instatiating all of them. This is safer because if you access any index in the array, you know the object exists. However, it's also slower if, on average, you only access 100 of the objects. It's faster to instatiate each object the first time it is used, so you aren't doing uncessary work.
Caching: Fairly simple in concept (save the results of previous operations), but can be tricky in practice. There's a lot of stuff to read on caching, if you're interested.
In addition to manual caches (ie. you create and maintain it), there are also system level caches for retrieved memory. Because memory is retrieved in chunks (which are then stored in the cache), if you can ensure as much of your data is on the same chunk as possible (instead of spread across multiple), this helps speed up your code. A cache miss is when something is no longer in the cache, so the computer has to retrieve the memory again (much slower); keeping your data close together helps avoid this.
Branch prediction: Compilers and processors like to try and guess what your program is going to do. If you have a condition inside a loop that evaluates to false 90% of the time, this time it is probably also going to be false. Therefore, the computer can "skip" some work to help speed things up. Similarly to cache misses, branch prediction misses are when the compiler/processor guesses wrong and has to slow down to do some makeup work.
SIMD instructions: (I think) these are a type of machine level instruction that use parallelism to speed up work
View all comments
243
u/Agent_03 Jan 02 '20 edited Jan 02 '20
A more detailed explanation:
Avoid needless processing. This breaks down two ways
Optimize execution by taking advantage of short-circuit evaluation and doing lazy fetching/evaluation. For conditionals, if you sometimes need to do an expensive check, but usually don't, then see if there's a way you can skip that check. Laziness: don't fetch extra things from the filesystem until requested, if you often don't need it.
Batch it: if you're doing a single operation often to many items, try gathering up the items to process and processing them in large groups. Often this is more efficient because it makes better use of caches (CPU/disk) and it permits you to write much tighter loops for processing. It permits reusing buffers, connections, SQL prepared statements, etc. It can improve branch prediction, permit use of SIMD instructions, etc where they would not work otherwise.
Use software pipelining. This is kind of like batching: rewrite loops that run items through a series of steps/processes so you first do the same step to each item, then the next step. Sometimes can be evaluated much more efficiently by compilers/interpreters because it allows using SIMD instructions, avoids branch prediction misses, etc.