我們能利用machine learning去幫助compiler的optimization演算法變強嗎？

ML通常是拿來幫忙做predict和decisions

透過大量training data (input: feature,  output: predict a value or classification)

對於沒有看過的feature做predict和decisions

我對於ML經驗只有半年多

以下是我的一些看法

1. 

如果是對特定benchmark的話

用ML能幫忙找出不錯的heuristic值 (ex. --param, --regalloc=[basic|fast|greedy|pbqp] 等等)

google也滿多的

Automatic Feature Generation for Machine Learning Based Optimizing Compilation

但直到看到"MILEPOST GCC"  覺得圖很眼熟...

就是interactive compiler!

2. 

如果想把machine learning的training也做進compiler內

看來就只能做在JIT了

google了一下也有人做到VM

Using machines to learn method-specific compilation strategies (IBM)

Method-Specific Dynamic Compilation using Logistic Regression

也有人拿來做CPU/GPU decisions XD
Machine-Learning-based Performance Heuristics for Runtime CPU/GPU Selection

如果做在AOT compiler, 感覺就像PGO, 看起來也不需ML

3. 

如果要用machine learning去學出某隻benchmark/function最好的instruction sequence

感覺可以用reinforcement learning去做

但是用interactive compiler去挑heuristic就可能做的很好了.. 

也有google到

Basic-block Instruction Scheduling Using Reinforcement Learning and Rollouts

我認為ML強的地方是對於noise多的input或者沒見過的pattern

做的決策會比人類直接寫的演算法好

但是compiler optimizations其實就是一堆pattern matching

雖然register allocation和instruction scheduling可能不太一樣

這就比較像是如何用machine learning去幫忙加速解決NP problem (ex. tree coloring)

這是做的到的, 像是圍棋是np-hard problem

但已經可以用machine learning (deep learning)來找approximation解

The Speed Game: Automated Trading Systems in C++

https://meetingcpp.com/index.php/tv16/items/18.html



C++ low latency coding techniques：

● General considerations

C++11 Move semantics
Static assert
Data member layout, padding and alignment (盡量alignment access)
● False sharing
http://shuyufu.blogspot.tw/2013/01/false-sharing.html
● Cache locality

● Compile-time dispatch

std::sort(array, array + N, [](int a, int b) { return b < a; });
 71us, std deviation 1.5us

int comparer(const void* a, const void* b) { return *(int*)a - *(int*)b; } qsort(arr, N, sizeof(int), comparer); 223us, std deviation 7us

● Constexpr
C++14 feature
● Variadic templates
● Loop unrolling
Generally, don’t bother, the compiler will figure it out
● Expression short-circuiting

Rewrite:
if (expensiveCheck() && inexpensiveCheck()) {}
As:
if (inexpensiveCheck() && expensiveCheck()) {}

● Signed vs unsigned comparisons
用loop iteratort用signed就是了 （可看前篇

● Mixing float and doubles

Default type of a floating point literal in C++ is double, not float
Side note: If you are brave, consider -ffast-math

● Branch prediction/reduction
Compile-time branch prediction hints are a topic of much discussion (particularly within SG14)
○ I.e. gcc’s __builtin_expect

Avoid this:
 if (checkForErrorA()) handleErrorA();
 else if (checkForErrorB()) handleErrorB();
 else if (checkForErrorC()) handleErrorC();
 else executeHotpath();

Aim for this:
 uint32_t errorFlags; ...
 if (errorFlags) HandleError(errorFlags)
 else { ... hotpath }

● Exceptions
不要用

● Slowpath removal
Code is data - keep it minimal, and keep the slowpath code away from the hotpath

● Avoiding allocations
使用萬惡的replace new
Tip: don’t use swap. Memory is cheap. Buy more!

● Fast containers

● Lambda functions

If only at runtime you know what the target is, you have no choice but to use std::function

If you know at compile time which target is to be run, then prefer lambdas template
void SendMessage(T&& target) {
 // populate and send message 
 target(mBuffer);
 send(mBuffer);
 } 

 SendMessage([&](auto& message) { 
 message.field1 = x; 
 ... message.field3 = z;
 });


Surprises and side notes：
Older versions of gcc’s implementation had copy on write semantics (新版比較快)

#include <string> #include <iostream> int main() { std::string a(50, 'c'); std::string b = a; *const_cast<char*>(a.c_str()) = 'A'; std::cout << "a: " << a << "\nb: " << b << std::endl; }

GCC < 5:

$ g++ -std=c++11 main.cpp && ./a.out
a: Accccccccccccccccccccccccccccccccccccccccccccccccc
b: Accccccccccccccccccccccccccccccccccccccccccccccccc

Aha! Copy-on-write in action.

GCC >= 5:

$ g++-5 -std=c++11 main.cpp && ./a.out
a: Accccccccccccccccccccccccccccccccccccccccccccccccc
b: cccccccccccccccccccccccccccccccccccccccccccccccccc

clang:

$ clang++ -std=c++11 -stdlib=libc++ main.cpp && ./a.out
a: Accccccccccccccccccccccccccccccccccccccccccccccccc
b: cccccccccccccccccccccccccccccccccccccccccccccccccc

reference: http://shaharmike.com/cpp/std-string/