Efficiency with Algorithms, Performance with Data Structures – Chandler Carruth

"Software is getting slower more rapidly than hardware becomes faster. -Niklaus Wirth: A Plea for Lean Software"

  • Niklaus Wirth – Algorithms + Data Structures = Programs

There are two sides to the performance coin:

Efficiency through Algorithms – How much work is required by a task.

  • Improving efficiency involves doing less work.
  • An efficient program is one that does the minimum (that we’re aware of) amount of work to accomplish a given task.

Performance through Data Structures – How quickly a program does it work.

  • Improving performance involves doing work faster
  • But there is no such thing as a "performant", not even work in the English language.
  • There is essentially no point at which a program cannot do work any faster… until you hit Bremermann’s limit…
  • What does it mean to improve the performance of software?
    • The software is going to run on a specific, real machine
    • There is some theoretical limit on how quickly it can do work
  • Try to light up all the transistors, get the most work done as fast as possible.

All Comes back to Watts

  • Every circuit not used on a processor is wasting power
  • Don’t reduce this to the absurd — it clearly doesn’t make sense to use more parts of the CPU without improving performance!

Algorithms

  • Complexity theory and analysis
  • Common across higher-level languages, etc.
  • Very well understood by most (I hope)
  • Improving algorithmic efficiency requires finding a different way of solving the problem.
  • Algorithmic complexity is a common mathematical concept that spans languages and processors. Don’t get lazy, you have to pay attention to your algorithms.
  • Example: – "it’s about doing less work", analyze the current approach and find ways to do it more efficiency
    • Initially, you might have a basic O(n^2) algorithm
    • Next, we have a Knuth-Morris-Pratt (a table to skip)
    • Finally, we have a Boyer-Moore (use the end of the needle)

Do Less Work by Not Wasting Effort, Example 1

std::vector<X> f(int n) {
 std::vector<X> result;
	for(int i = 0; i < n; ++i)
		result.push_back(X(...));
    return result;	
}

Initialize the collection size

std::vector<X> f(int n) {
 std::vector<X> result;
 result.reserve(n);
	for(int i = 0; i < n; ++i)
		result.push_back(X(...));
    return result;	
}

Do Less Work by Not Wasting Effort, Example 2

X *getX(std::string key,
        std::unordered_map<std::string, std::unique_ptr<X>> &cache) {   
    
    if(cache[key])
       return cache[key].get();
    
    cache[key] = std::make_unique<X>(...);
    return cache[key].get();    
}

Retain the reference to the cache entry

X *getX(std::string key,
        std::unordered_map<std::string, std::unique_ptr<X>> &cache) {   

	std::unique_ptr<X> &entry = cache[key];

    if(entry)
       return entry.get();

    entry = std::make_unique<X>(...);
    return entry.get();
}

Always do less work!

Design API’s to Help

Performance and Data Structures = "Discontiguous Data Structures are the root of all (performance) evil"

  • Just say "no" to linked lists

CPUs Have Hierarchical Cache System

Data Structures and Algorithms

  • They’re tightly coupled, see Wirth’s books
    • You have to keep both factors in mind to balance between them
  • Algorithms can also influence the data access pattern regardless of the data structure used.
  • Worse is better: bubble sort and cuckoo hashing

Leave a Comment