Why's my program slow?

Algorithmic Complexity and You

Hello

• Emily Dunham
• edunham on Freenode
• edunham@edunham.net
• No Twitter

These slides are online at:

http://talks.edunham.net/linuxfestnorthwest2015/complexity/

Why this talk?

https://www.flickr.com/photos/chefranden/3183416126/

Agenda

In Theory

• Motivations for complexity analysis
• Meaning of the notation
• Techniques for analyzing complexity
• Examples

In Practice

• What problem are you solving?
• Alternate Tools

In Theory

Coursera:

• Stanford
• Princeton

Syllabi:

• http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms

http://commons.wikimedia.org/wiki/File:Swiss_Jungfrau_mountains.jpg

What's complexity?

https://imgs.xkcd.com/comics/compiling.png

How Long it Takes

http://commons.wikimedia.org/wiki/File:Analog_clock_animation.gif

In terms of input size

https://projecteuler.net/

• Project Euler
• Solution fast on small input
• Very slow on large input

n is the size of the input.

N: /N/, quant.

1. A large and indeterminate number of objects: “There were N bugs in that

   crock!” Also used in its original sense of a variable name: “This crock has N bugs, as N goes to infinity.”

http://www.catb.org/jargon/html/N/N.html

Quantified in fancy notation

O(n)

(time in loop) * (times the loop runs) + (time outside of loop)

Graph of why it's "usually ok to omit the constant" (more on that later)

(Math Words)

http://upload.wikimedia.org/wikipedia/commons/thumb/8/89/Pure-mathematics-formul%C3%A6-blackboard.jpg/220px-Pure-mathematics-formul%C3%A6-blackboard.jpg

For any monotonic functions f(n) and g(n) from the positive integers to the positive integers, we say that f(n) = O(g(n)) when there exist constants c > 0 and n[0] > 0 such that:

f(n) ≤ c * g(n), for all n ≥ n[0]

P vs NP

http://www.public-domain-image.com/objects-public-domain-images-pictures/electronics-devices-public-domain-images-pictures/computer-components-pictures/computer-inside.jpg.html

How do you find how many times it runs?

https://www.flickr.com/photos/dalager/14110369/

Example: Linear Search

Disclaimer: If you use this implementation in an interview, you will not get the job.

needle = '4'
haystack = [2, 8, 23, 5, 4, 7, 42]

idx = 0
while haystack[idx] < len(haystack):
    if haystack[idx] == needle:
        print "Found it at index " + str(idx)
    idx += 1

Find n

needle = '4'
haystack = [2, 8, 23, 5, 4, 7, 42]

idx = 0
while haystack[idx] < len(haystack):
    if haystack[idx] == needle:
        print "Found it at index " + str(idx)
    idx += 1

Count the Loops

n is len(haystack)

needle = '4'
haystack = [2, 8, 23, 5, 4, 7, 42]

idx = 0
while haystack[idx] < len(haystack):
    if haystack[idx] == needle:
        print "Found it at index " + str(idx)
    idx += 1

There's the complexity!

• loop once over n items
• Contents is constant time
• Complexity is O(n)

Example: Finding Repeated Words

Same disclaimer as before.

words = ['linux', 'washington', 'linux', 'festival']
idx = 0
while idx < len(words):
    check = 0
    while check < len(words):
        if idx != check and words[check] == words[idx]:
            print "found a repeated word!"

First find n

words = ['linux', 'washington', 'linux', 'festival']
idx = 0
while idx < len(words):
    check = 0
    while check < len(words):
        if idx != check and words[check] == words[idx]:
            print "found a repeated word!"

Then count loops

n is len(words)

words = ['linux', 'washington', 'linux', 'festival']
idx = 0
while idx < len(words):
    check = 0
    while check < len(words):
        if idx != check and words[check] == words[idx]:
            print "found a repeated word!"

There's the complexity!

• Outer loop goes n times
• inner loop goes n times
• Inner loop runs every time the outer does
• Complexity is n*n, or n^2

Tangent: If that was an interview...

words = ['linux', 'washington', 'linux', 'festival']
idx = 0
while idx < len(words):
    check = 0
    while check < len(words):
        if idx != check and words[check] == words[idx]:
            print "found a repeated word!"

What's the Difference?

Without exponential

Now you Try It

def binary_search(l, value):
    low = 0
    high = len(l)-1
    while low <= high:
        mid = (low+high)//2
        if l[mid] > value: high = mid-1
        elif l[mid] < value: low = mid+1
        else: return mid
    return -1

First find n

def binary_search(l, value):
    low = 0
    high = len(l)-1
    while low <= high:
        mid = (low+high)//2
        if l[mid] > value: high = mid-1
        elif l[mid] < value: low = mid+1
        else: return mid
    return -1

Count the loops

def binary_search(l, value):
    low = 0
    high = len(l)-1
    while low <= high:
        mid = (low+high)//2
        if l[mid] > value: high = mid-1
        elif l[mid] < value: low = mid+1
        else: return mid
    return -1

There's the complexity

Binary search is log(n)

"In mathematics, the logarithm of a number is the exponent to which another fixed value, the base, must be raised to produce that number."

Some Details

big-oh is UPPER BOUND

big-omega is LOWER BOUND -- the program can never run faster than this

Big theta (not all programs will have this) is when upper and lower bounds match

Amortized Complexity

If a slow operation is done infrequently, we can spread its cost over all the times it didn't happen...

How about recursive?

def binary_search(l, value, low = 0, high = -1):
    if not l:
        return -1
    if(high == -1): high = len(l)-1
    if low == high:
        if l[low] == value: return low
        else:
            return -1
    mid = (low+high)//2
    if l[mid] > value:
        return binary_search(l, value, low, mid-1)
    elif l[mid] < value:
        return binary_search(l, value, mid+1, high)
    else: return mid

Space Complexity

how much memory does it take?

In-place sorting vs sorting by copying the array

• What if your array is > 1/2 your disk?
• Constant is the size of an item being sorted

Graphs of space complexity and show how they look quite a bit like time complexity

Reversing an Array

copy elements:

function reverse(a[0..n - 1])
    allocate b[0..n - 1]
    for i from 0 to n - 1
        b[n − 1 − i] := a[i]
        return b

vs in-place:

function reverse_in_place(a[0..n-1])
    for i from 0 to floor((n-2)/2)
        tmp := a[i]
        a[i] := a[n − 1 − i]
        a[n − 1 − i] := tmp

Feeling like a Real Computer Scientist yet?

http://en.wikipedia.org/wiki/File:Ada_lovelace.jpg

That Constant

Constant times differ by several orders of magnitude.

• Processor memory vs L1 cache
• Cache vs RAM
• RAM vs hitting the disk
• Local disk vs across the datacenter
• Across the datacenter vs over wifi or a cell network
• Wifi or cell vs another continent

In The Real World

Good Code

• Correct
• Efficient
• Simple
• Readable
• Maintainable

Is my program slow?

• Expected input size?

• How's it do in tests?

  • (you are testing it, right?)

• How much of test suite time is setup/teardown?

• What will real-world conditions look like?

  • and under heavy load? (CACHING CACHING CACHING)

Is my program too slow?

http://en.wikipedia.org/wiki/File:Ada_lovelace.jpg

Why is my program slow?

It's probably not how you structured your algorithm. Or you fix the obvious algorithmic stupidity and it's still bad.

Remember the orders of magnitude thing?

• Hard to see where an algorithm spends its time
• Working from a wrong guess about where the bottleneck is will waste yours

Algorithmic complexity in real code

• "the pros" can look at a section of code and tell you its best, worst, and average-case performance -- kind of like how we practiced earlier
• Recognizing patterns from having read a lot of other code

Expected Use Case

• Exponential time with a tiny constant vs. logarithmic with huge constant
• Input size?
• Space constraints?

Analysis Tools

Each language has its own

Python: Run Snake Run

C: GDB/gprof

Instrumentation

http://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29

http://commons.wikimedia.org/wiki/File:Pork_thermometer.jpg

Call Profilers

http://en.wikipedia.org/wiki/File:Alt_Telefon.jpg

Testing

• Language or shell timing utilities
• Test on different sizes of input
• Write a test suite to catch preformance changes

When to test?

• Always! (Continuous Integration)
• Deeper analysis for debugging, refactors

• How hard is it to introduce a complexity change?

accidentallyquadratic.tumblr.com

Recap

Learned about complexity

• Simplify the code
• Count how often it'll run for a given size of input
• Toss out the constants

Complexity isn't the entire picture

• That constant actually matters
• Premature optimization is bad for everyone
• Code that never gets finished was the slowest of all

Tools are great, in their place

• Instrumentation hooks into your code
• Profilers watch where it spends its time
• Test suite can check how long it takes on every change to find regressions

Thanks!

• Emily Dunham
• edunham on Freenode
• edunham@edunham.net
• No Twitter

These slides are online at:

http://talks.edunham.net/linuxfestnorthwest2015/complexity/