Good algorithms, Good compilers
Good algorithms usually beat good compilers in space and time
Understand the Big-O notation: keep algorithmic complexity as low as possible
Be lateral: use probabilistic algorithms, hashes, etc
Keep your embedded code simple: shift complexity and preparation of data elsewhere
Notes:
EXAMPLE: finlib performance problem with curvelib at LB; identified problem area and converted from linear search (O(n2)) to hash (O(n)); replaced in situ as library patch and doubled app speed.
Note1: Understand why O(1) is better than O(log n) which is better than O(n) which is in turn better than O(nk).
Note2: Discuss what optimising compilers generally can and can’t do and why...
- Are you doing difficult tasks as efficiently and as few times as possible and on appropriate machine (use central servers for data prep)?
- Do you have the best algorithm for your problem size and type (lowest complexity is not always best)?
- Have you measured and tested and iterated?
- Have you considered aspects such as latency and cache misses?