Stefan Genov

Performance

2 min read

description
How to write performant code
parent
Software Engineering Index
state
  • evergreen
date
2024-10-10
relates
links
title
Performance

Map Of Content

When and what to optimise

Every piece of optimisation comes with downsides. Cognitive load, code complexity, development time are some of these downsides.

Consider if the piece of code you are trying to optimise is really worth it.

Low-hanging fruits

Inspect your specific use case and go for the Low Hanging Fruits first. The big optimisations are more effective than the little ones.

The Three Optimization Questions:

  • Do we have to do this at all? The fastest code is the code that’s never run.
  • If yes, is this the best algorithm.
  • If yes, is this the best implementation of this algorithm.

Data Changes

These sorts of changes are useful when the data you need is cheap to store and easy to keep up-to-date.

  • Extra fields
    • You can for example store the value of length of a linked list instead of getting it every time.
  • Extra Search Indexes
    • For queries, you may want to have not only a primary key but a secondary key to index the data by it if searching is needed
  • Extra information about elements
    • Keeping a Bloom Filter can let you quickly return a no-match for lookups.
  • Add Caching if queries are expensive.

These are all clear examples of “do less work” at the data structure level. They all cost space. Most of the time if you’re optimizing for CPU, your program will use more memory. This is the classic Space-time Tradeoff.

Algorithmic Changes

The biggest improvement is likely to come from an algorithmic change. This is the equivalent of replacing bubble sort (O(n^2)) with quicksort (O(n log n)) or replacing a linear scan through an array (O(n)) with a binary search (O(log n)) or a map lookup (O(1)).

This is how software becomes slow. Structures originally designed for one use is repurposed for something it wasn’t designed for. This happens gradually.

It’s important to have an intuitive grasp of the different big-O levels. Choose the right data structure for your problem. You don’t have to always shave cycles, but this just prevents dumb performance issues that might not be noticed until much later.

  • Big O Notation

    The basic classes of complexity are:

    • O(1): a field access, array or map lookup Advice: don’t worry about it (but keep in mind the constant factor.)
    • O(log n): binary search Advice: only a problem if it’s in a loop
    • O(n): simple loop Advice: you’re doing this all the time
    • O(n log n): divide-and-conquer, sorting Advice: still fairly fast
    • O(nm): nested loop / quadratic Advice: be careful and constrain your set sizes
    • Anything else between quadratic and sub-exponential Advice: don’t run this on a million rows
    • O(b ^ n), O(n!): exponential and up Advice: good luck if you have more than a dozen or two data points
    Link to original

Garbage Collection

  • Garbage Collection

    Map Of Content

    Notes

    You pay for memory allocation more than once. The first is obviously when you allocate it. But you also pay every time the garbage collection runs.

    Reduce/Reuse/Recycle. — @bboreham

    • Stack vs. heap allocations
    • What causes heap allocations?
    • Understanding Escape Analysis (and the current limitation)
    • /debug/pprof/heap , and -base
    • API design to limit allocations:
      • allow passing in buffers so caller can reuse rather than forcing an allocation
      • you can even modify a slice in place carefully while you scan over it
      • passing in a struct could allow caller to stack allocate it
    • reducing pointers to reduce gc scan times
      • pointer-free slices
      • maps with both pointer-free keys and values
    • GOGC
    • buffer reuse (sync.Pool vs or custom via go-slab, etc)
    • slicing vs. offset: pointer writes while GC is running need writebarrier: https://github.com/golang/go/commit/b85433975aedc2be2971093b6bbb0a7dc264c8fd
    • use error variables instead of errors.New() / fmt.Errorf() at call site (performance or style? interface requires pointer, so it escapes to heap anyway)
    • use structured errors to reduce allocation (pass struct value), create string at error printing time
    • size classes
    • beware pinning larger allocation with smaller substrings or slices
    Link to original

Graph View

Backlinks