第十三號艦隊
0%

Posted on Edited on In ,

Agner Fog最近更新了他的Software optimization resources。
之前在Corel的時候也有參考過這邊的文件。不過離開那邊之後就沒碰過Assembly了。

不過Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms這篇文件可以看看。
這年頭自己寫Assembly的人越來越少，除了是大師之外，沒有把握比Compiler做的更好。

Posted on Edited on In , , , ,

在StackOverflow看到的。
這段程式，在GCC和Clang會失敗，而在VC正常運作。

1
2
3
4
5
int main()
{
        int linux = 1;
        return 0;
}

用gcc -E下去看的結果如下

1
2
3
4
5
int main()
{
        int 1 = 1;
        return 0;
}

這是由於在未標準化的年代，像是unix，linux等字都會採到地雷。
不過可以用 gcc -std=c89強讓他走標準規範編譯。

可以看到

1
2
3
4
5
6
7
8
9
$ cpp --std=c89 -dM < /dev/null | grep linux
#define __linux 1
#define __linux__ 1
#define __gnu_linux__ 1
$ cpp --std=gnu89 -dM < /dev/null | grep linux
#define __linux 1
#define __linux__ 1
#define __gnu_linux__ 1
#define linux 1

在gnu89裡面GCC自己加了linux的定義下去了。注意這邊的cpp是The C Preprocessor，跟C++無關。
用-dM來印出所有被Preprocessor定義的值。
既然知道Preprocessor定一些什麼值之後，就可以順利避開陷阱了。

Posted on Edited on In

東西閱看越多姿後，才發覺自己的無知。 寫起來當筆記。

First-class citizen

Wiki上有其定義。另一個名稱叫First-class object，其特性有

  • 可以被存入變數或其他結構
  • 可以被作為參數傳遞給其他函數
  • 可以被作為函數的返回值
  • 可以在執行期創造，而無需完全在設計期全部寫出
  • 即使沒有被繫結至某一名稱，也可以存在
    其中最具討論性的是函數算不算First-class citizen，C/C++不支援在Runtime創造函數，所以不把函數視為First-class citizen。

Higher-order unction

[Wiki]（http://en.wikipedia.org/wiki/Higher-order_function）上同樣有定義。一個Higher-order unction至少滿足以下條件之一。

  • 接受一個或多個函數作為輸入

Closure

Wiki同樣有其定義。

用在一個函式與一組「私有」變數之間建立關聯關聯。在給定函式被多次呼叫的過程中，這些私有變數能夠保持其永續性。變數的作用域僅限於包含它們的函式，因此無法從其它程式代碼部分進行存取。不過，變數的生存期是可以很長，在一次函式呼叫期間所建立所生成的值在下次函式呼叫時仍然存在。正因為這一特點，閉包可以用來完成訊息隱藏，並進而應用於需要狀態表達的某些編程典範中。

用這種方式來使用閉包時，閉包不再具有參照透明性，因此也不再是純函式。

Posted on Edited on

Tailing Recursion是大部分Function Language的基本配備，在沒有迴圈的情況下，Recursive是唯一的方案。
而Tailing Recursion是Tail Call的一種特例。只是最後呼叫的函數是自己。
在不討綠用公式解跟迴圈解的情況下，要從1加到1000000000我們會這麼寫。

1
2
3
4
5
6
long long sum(int n)
{
	if (n == 0) return 0;
	return n + sum(n - 1);
}
cout << sum(1000000000) << endl;

這段程式在Visual C++會掛，而在GCC跟Clang可以正常運作。 (Visual C++的判別還真有點弱)。
不過我想說的是後面這個，Tailing Recursion Optimization。
跟上面很類似，不過會多帶一個參數，代表初始狀態。
上面的範例可以重新寫成

1
2
3
4
5
6
long long int sum(int n, long long int v)
{
	if (n == 0) return v;
	return sum(n - 1, n + v);
}
cout << sum(1000000000, 0) << endl;

這種寫法比上面好的點，在於當我們要做Recursive呼叫的時候，必須保留呼叫時每一層的狀態，存在Stack裡，當你遞迴深度過深時，超過OS給予的極限，就會造成Stackoverflow。而用下面這種寫法的話，則不需要保留遞迴中的堆疊。只需要修改當前堆疊的值，然後既需呼叫函式即可。

還有如果把之後要做的事情當做參數傳進來，就變成Continuation-passing style了。

把程式碼改寫成這樣

1
2
3
4
5
6
void sum(int n, long long int v, function<void (long long)> contWith)
{
	if (n == 0) return contWith(v);
	return sum(n - 1, n + v, contWith);
}
sum(1000000000, 0, [] (long long v) { cout << v << endl; });

結果所有編譯器全掛了，同樣邏輯的程式碼用Haskell重寫一次

1
2
3
sum' n total cont  
    | n == 0 = cont(total)
    | otherwise = sum' (n - 1) (total + n) cont

整個計算資源被耗盡了，難道1000000000真的玩太大了。

Posted on Edited on

由於Asynchronous Programming大行其道之後，Continuation Passing Style就再度被人們注意到。
在介紹Continuation Passing Style(之後簡稱CPS)之前，先要介紹一下什麼是Continuation。指的是完成某件事情之後，接下來還需要做的情情。

而什麼是CPS，就是將Continuation當做參數傳入函數之中。

1
2
3
 
let add a b = a + b
printfn "%i" (add 3 5)

而CPS的寫法會是

1
2
3
 
let add a b cont = cont(a + b)
add 3 5 (printfn "%i")

兩者能夠得到一樣的結果，不過光看這麼簡單的範例，看不出CPS優勢和在。

Posted on Edited on In , ,

從C語言說起

在C語言的時候，const的用途很簡單，用來修飾變數的屬性。以下給個範例

1
2
3
4
5
6
void func(const int *v)
{
        int p;
        *v = 10;
        v = &p;
}

上面的*v = 10會被編譯器指出v是不能被修改的。 值得注意的是 const int *的寫法跟 int const *是一樣的，不過我比較偏好前者。

如果改寫成

1
2
3
4
5
6
void func(int * const v)
{
        int p;
        *v = 10;
        v = &p;
}

會告訴你v = &p這行錯了，由此可見int const *表示被指向的 內容 不可改，而指標是可以改變的，這邊的const是用來修飾int的。而int * const表示指向的 指標 不可改，而這邊的const是用來修飾int *的。
當然，如果要兩者間得，也可以寫成這樣

1
2
3
void func(const int * const v)
{
}

C++98

C++擴大const的使用範圍，允許const修飾Class的Member Function。表示這個函數是 Logic Constness，不影響外界看這物件的狀態。因此以下這段程式碼會出現問題。

1
2
3
4
5
6
7
class Test {
        int state;
public:
        void Func() const {
                state = 1;
        } 
};

由於C++支援Cast Overloading，支援Function Signature相同，但const屬性不同的Overload，因此這樣的是合法的，，

1
2
3
4
5
6
7
8
9
10
class Test {
        int state;
public:
        void NonConstFunc() {}
        void Func() {
                state = 0;
        }
        void Func() const {
        } 
};

寫個程式來測試一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
oid Test1(const Test &t)
{   
        t.NonConstFunc();  // Compile Error, 不能呼叫Non-const的Member Function
        t.Func(); 
}   
void Test2(Test &t)
{ 
        t.NonConstFunc();
        t.Func();
}
void Test3(Test &&t)
{
        t.NonConstFunc();
        t.Func();
}
Test t;
Test1(t);
Test2(t);
Test3(move(t));

除了Test1的Func是跑const版本之外，其他所有函數都是呼叫Non-const版本的Func
雖說const的Member function是不可修改 Logic Constness ，不過以下程式碼很難是合法的。

1
2
3
4
5
6
7
8
class Test {
        int *state;
public:
        void NonConstFunc() {}
        void Func() const {
            *state = 1;
        } 
};

Mutable

之前說過，從外界看到的類別狀態是 Logic Constness 的，這代表我們可以在 const函數裡面動手腳，只要外界看起來正常就好，因此就有了mutable的誕生。將上面的範例重新改寫。

1
2
3
4
5
6
7
class Test {
        mutable int state;
public:
        void Func() const {
                state = 1;
        } 
};

這樣就能正常使用了…初看之下好像很沒用，不過以這個範例來說

1
2
3
4
5
6
7
8
9
10
11
12
13
class Test {
        int state;
        mutable mutex obj_mutex;
public:
        void SetState() {
                unique_lock<mutex> lock(obj_mutex);
                state = 1;
        }
        int GetState() const {
                unique_lock<mutex> lock(obj_mutex);
                return state;
        }
};

在Multithread的情況之下，有人會呼叫SetState，而有人會想知道GetState的值，雖然state在GetState不會被改變，但是mutex會變。所以需要mutable的存在。
另外一種情形是當做Cache使用

1
2
3
4
5
6
7
8
9
10
11
12
class HashTable {
        mutable string lastKey, lastValue;
        ....
public:
        string lookup(string key) const {
                if (key == lastKey) return lastValue;
                string value = ookupInternal(key);
                lastKey = key;
                lastValue = value;
                return value;
        }
};

不過在C++11之後，又有新用法了 

1
2
3
4
int x = 30;
auto f1 = [=]() { x = 123; } // Compile error
auto f1 = [=]() mutable { x = 123; }
auto f2 = [&]() mutable { x = 123; }

f1在呼叫之後，x會變成123，不過離開f1之後，x又回到30，而f2呼叫之後就整個變成123了。
不過我看不懂第一個範例的用途是什麼。

constexpr

constexpr是C++11才有的觀念，原先就有Constant Expressions的觀念，不過還是有其不足之處。
假設我們要宣告個n*m的一維陣列，我們會這麼做。

1
2
3
const int n = 5;
const int m = 5;
int array[n * m];

假設我們已經有一個mul2的函數，試著編譯以下這段程式就會出現錯誤。

1
2
3
4
const int n = 5;
const int m = 5;
int mul2(int x, int y) { return x * y; }
int array[n * m];

結果我們只能藉由以下兩種方法解決，一是回到C語言的Preprocessor來做。

1
#define mul2(x, y) ((x) * (y))

這方式可行，不過缺乏型態資料。在Secure Coding的時候容易出錯。
另一種是在Runtime時算出一個常數。

1
2
3
4
5
int mul2(int x, int y) { return x * y; }
const int Mul2 = mul2(n, m);
void func() {
        int array[Mul2];
}

如果要把array儀到global scope，問題又出現了。導致不得不使用Preprocessor的解法。因此就有了constexpr的誕生。
有了constexpr之後，可以在編譯時期就算出答案，類似Template Metaprogramming，不過用途更廣。
上面的範例我們可以重新改寫

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
using namespace std;
const int n = 5;
const int m = 5;
constexpr int mul2(int x, int y) { return x * y; }
int array[mul2(n, m)];
int main() {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("arraySize = %lu\n", sizeof(array) / sizeof(array[0]));
        printf("mul2((x, y) = %d\n", mul2(x, y));
        return 0;
}

可以看到這邊的mul2不只可以用在compile-time，在runtime也可正常執行。
也可以在編譯時期使用物件，上面的範例我們可以用Functor在寫一次。

1
2
3
4
5
6
7
8
9
10
const int n = 5;
const int m = 5;
class Mul2 {
        int x, y;
public:
        constexpr Mul2(int x_, int y_) : x(x_), y(y_) {}
        constexpr int operator()() { return x * y; }    
};
constexpr Mul2 mul2(n, m);
int array[mul2()];

如果對constexpr有更多了解，可以參考Constexpr - Generalized Constant Expressions in C++11，目前支援constexpr的編譯器也不多。

結論

C++果然不愧是最難學的語言，每個環節都搞的特別複雜。我難過。

Posted on Edited on In , ,

看到了fasd之後發現真是相見恨晚啊。整天在那邊切換目錄真是麻煩。
安裝方法很簡單，下載之後只要

1
$ sudo make install

接著再自己的.bashrc之後加上這行

1
$ eval "$(fasd --init auto)"

然後就完成了…

如何使用

最簡單的情況，假設我們現在在home目錄下有foo跟bar兩個目錄，而foo目錄下有bar這個檔案。

1
2
3
4
5
~ $ cd foo
~/foo $ touch foo
~/foo $ touch bar
~/foo $ cd ~/bar
~/bar $

接著就可以用

1
2
~/bar $ z foo
~/foo $ z bar

跳到你想要的目錄，當然也支援 Tab complementation 。
也可以使用

1
$ zz

來使用交互式的方式來跳躍。
假設我們要修改~/foo/bar這個檔案，我們只需要

1
~/bar $ vim `f bar`

如果我們要把bar這個檔案複製到bar這個目錄，也只要

1
~/bar $ cp `d foo`/bar .

現在有兩個bar在兩個不同的目錄底下，如果要編輯的話，必須指定更多資訊供批配。

1
~/bar $ vim `f foo/bar`

其他更複雜的使用方法就參照網站上的範例使用。

Posted on Edited on In ,

看到C#的yield之後，上網查了一下，發現這是Generator的概念。根據Wiki上的寫法

A generator is a special routine that can be used to control the iteration behaviour of a loop

以C#為程式語言示範，假設沒有控制Iterator的話，印出一到一百間所有質數，我們會這麼寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static IList<int> GeneratorPrimes()
{
        var result = new List<int>();
        for (int i = 2; i <= 100; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i && flag; j++)
                if (i % j == 0) flag = false;
            if (flag) result.Add(i);
        }
        return result;
 }
 
 IList<int> ans = GeneratorPrimes();
 foreach (var item in ans)
 {
        Console.WriteLine(" {0} ", item);
 }

假設我們想產生無限的質數列表，這方法就不適用，因此我們需要改變一個思緒，每次從中取得一個數，需要的時候在取下一個，因此，我們需要儲存狀態。

1
2
3
4
foreach (var item in GeneratorPrime())
{
        Console.WriteLine(" {0} ", item);
}

至於GeneratorPrime的作法就是我們要討論的部份

沒有語言支援的作法

沒有語言支援，只好再內部維護一個狀態機，記住當今狀態，以及如何移動狀態。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class PrimesGenerator : IEnumerator<int>
{
    int current, next;
    public PrimesGenerator()
    {
        Reset();
    }
    private void calcNext()
    {
        for (next++; ; next++)
        {
            bool flag = true;
            for (int i = 2; flag && i * i <= next; i++)
                if (next % i == 0) flag = false;
            if (flag) break;
        }
    }
    public bool MoveNext()
    {
        return current < 100;
    }
    public void Dispose()
    {
    }
    public int Current 
    { 
        get {
            int ret = current;
            current = next;
            calcNext();
            return ret;
        }  
    }
    object System.Collections.IEnumerator.Current
    {
        get {
            int ret = current;
            current = next;
            calcNext();
            return ret;
        }  
    }
    public void Reset()
    {
        current = 2;
        next = 3;
    }
}
public class IEnumerablePrimes : IEnumerable<int> 
{
    public IEnumerator<int> GetEnumerator()
    {
        return new PrimesGenerator();
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}
public static IEnumerable<int> GeneratorPrime()
{
    return new IEnumerablePrimes();
}

C++和Java的作法略有不同，不過重點是放在PrimesGenerator中各種狀態的保存及移轉。如果簡單的話還好，像是Tree Traversal這種複雜的情況就一個頭兩個大。

語言支援的作法

由於C#提供yield，yield表示江控制權教還給呼叫者，而Iterator保持在回傳時的那個狀態，當再一度被呼叫時，可以重剛剛那個狀態繼續運行下去，於是我們程式碼可以寫成這樣。

1
2
3
4
5
6
7
8
9
10
public static IEnumerable<int> GeneratorPrime()
{
        for (int i = 2; i <= 100; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i && flag; j++)
                if (i % j == 0) flag = false;
            if (flag) yield return i;
        }
}

這邊的yield就是一個syntax sugar，透過編譯器的幫忙，將上面這段code改寫成類似上面的State Machine，有興趣的人可以透過Resharper來看看邊義氣幫你處理掉多少東西。

Haskell的解法

由於Haskell有Lazy evaluation，所有東西都是Generator，所以可以寫成這樣。

1
2
3
4
5
6
primes = 2 : 3 : nextprime 5  where
  nextprime n | b = n : nextprime (n+2)
              | otherwise = nextprime (n+2)
    where b = all ((/= 0).(rem n)) $ takeWhile ((<= n).(^2)) $ tail primes

printPrimes = mapM_ print $ takeWhile (<= 100) primes

前面的primes產生一個無限質數數列，而printPrimes印出這個數列中滿足條件的部份，