第十三號艦隊
0%

Posted on Edited on In ,

有時候有其需要，知道Shared Library當中有哪些符號，這時候可以這樣做。
以下是我們的測試程式

1
2
3
4
5
6
7
8
int bar;
void foo() {}
class Foo {
        static int value;
        void Bar(int);
};
int Foo::value = 0;
void Foo::Bar(int) {}

Linux

在Linux底下可以用nm來指令

1
$ nm -gC test.so
  • g 列出所有External symbols
  • c 由於C++支援Function overload，要區別同名的函數名稱的話，需要在後方加上一些符號以供區別，而Demangle就是讓這些奇形怪狀的符號變成人可以看懂得版本。
    以上的結果如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    000000000020102c B bar
    0000000000201028 B __bss_start
                     w __cxa_finalize@@GLIBC_2.2.5
    0000000000201028 D _edata
    0000000000201038 B _end
    00000000000006e4 T _fini
                     w __gmon_start__
    00000000000005a0 T _init
                     w _ITM_deregisterTMCloneTable
                     w _ITM_registerTMCloneTable
                     w _Jv_RegisterClasses
    00000000000006d0 T foo()
    00000000000006d6 T Foo::Bar(int)
    0000000000201030 B Foo::value

Windows

需要額外一個步驟，用一個Exporting from a DLL Using DEF Files倒出foo這個函數。
Windows底下可以用DLL Export Viewer。
而我們只看到foo，而沒有clas被輸出。輸出一個class不能用Def那種方式，如果需要的話，可以用dllexport這種方式。

這邊可見Windows跟Unix設計上的不同，Unix是預設把所有Symbols列出，然後需要的在隱藏。而Windows是需要的在列出。
至於如何隱藏，Binary Hacks有介紹，日後在補上。

Posted on Edited on In , , ,

同樣來自VC Blog的靈感，來測試一下三大編譯器的能耐。
如果對這技術有興趣的話，可以操考Wiki跟Code Optimizations:
Partial Dead Code Elimination和Dead Code Elimination這兩份PDF。
測試程式如下

1
2
3
4
5
6
int main()
{
	long long s = 0;
	for (long long i = 1; i <= 1000000000; i++) s += i;
	return 0;
}

Visual C++的結果

未開最佳化，如同VC Blog列的那樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	mov	QWORD PTR i$1[rsp], 1
	jmp	SHORT $LN3@main
$LN2@main:
	mov	rax, QWORD PTR i$1[rsp]
	inc	rax
	mov	QWORD PTR i$1[rsp], rax
$LN3@main:
	cmp	QWORD PTR i$1[rsp], 1000000000		; 3b9aca00H
	jg	SHORT $LN1@main
	mov	rax, QWORD PTR i$1[rsp]
	mov	rcx, QWORD PTR s$[rsp]
	add	rcx, rax
	mov	rax, rcx
	mov	QWORD PTR s$[rsp], rax
	jmp	SHORT $LN2@main
$LN1@main:

最佳化版本，結果相同，什麼都沒有

1
// Nothing

GCC的結果

未開最佳化

1
2
3
4
5
6
7
8
9
10
11
	movq	$1, -8(%rbp)
	jmp	.L2
.L3:
	movq	-8(%rbp), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
.L2:
	cmpq	$1000000000, -8(%rbp)
	setle	%al
	testb	%al, %al
	jne	.L3

如同Visual C++的結果一樣，照實執行。
最佳化版

1
// Nothing

跟Visual C++的結果相同，完全沒有程式碼，證明了這段程式碼一樣被偵測到而被捨棄。根據這篇的說明，在-O2的設定終究有暗示Dead Code Elimination的使用。

Clang的結果

未開最佳化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	movq	$1, -24(%rbp)
.LBB0_1:                                # %for.cond
                                        # =>This Inner Loop Header: Depth=1
	cmpq	$1000000000, -24(%rbp)  # imm = 0x3B9ACA00
	jg	.LBB0_4
# BB#2:                                 # %for.body
                                        #   in Loop: Header=BB0_1 Depth=1
	movq	-24(%rbp), %rax
	movq	-16(%rbp), %rcx
	addq	%rax, %rcx
	movq	%rcx, -16(%rbp)
# BB#3:                                 # %for.inc
                                        #   in Loop: Header=BB0_1 Depth=1
	movq	-24(%rbp), %rax
	addq	$1, %rax
	movq	%rax, -24(%rbp)
	jmp	.LBB0_1
.LBB0_4:                                # %for.end

可以看出三大編譯器對做同一件事，產生的程式碼風格相差甚大。
最佳化版

1
// Nothing

大家都能偵測到Dead Code Elimination。

同場加映

在VC Blog的Option 2，在原來的程式碼後面，加上printf，使得Dead Code Elimination失效。
VC的結果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
       xor    edx, edx
       mov    eax, 1 
       mov    ecx, edx
       mov    r8d, edx
       mov    r9d, edx
       npad   13
$LL3@main:
       inc    r9
       add    r8, 2
       add    rcx, 3
       add    r9, rax                           ;; r9  = 2  8 18 32 50 ...
       add    r8, rax                           ;; r8  = 3 10 21 36 55 ...
       add    rcx, rax                          ;; rcx = 4 12 24 40 60 ...
       add    rdx, rax                          ;; rdx = 1  6 15 28 45 ...
       add    rax, 4                            ;; rax = 1  5  9 13 17 ...
       cmp    rax, 1000000000                   ;; i <= 1000000000 ?
       jle    SHORT $LL3@main                   ;; yes, so loop back

使用Loop unwinding的技巧加速。
不過GCC跟Clang更勝一籌，直接印答案了。

1
movabsq	$500000000500000000, %rsi # imm = 0x6F05B59F17F6500

如果把原先的程式碼改成這樣

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main()
{
	long long s = 0;
	long long count;
	scanf("%lld", &count);
	for (long long i = 1; i <= count; i++) s += i;
	printf("%llu\n", s);
	return 0;
}

Visual C++跟GCC的產生結果就比較像了，VC原先的Loop Unwinding被拿掉了。

1
2
3
4
5
6
7
8
9
	movl	$1, %eax
	testq	%rdx, %rdx
	jle	.L3
.L6:
	addq	%rax, %rsi
	addq	$1, %rax
	cmpq	%rdx, %rax
	jle	.L6
.L3:

而Clang會根據x64指令集作最佳化一

1
2
3
4
5
6
7
8
9
10
11
12
	movq	8(%rsp), %rax
	testq	%rax, %rax
	jle	.LBB0_2
# BB#1:                                 # %for.body.lr.ph
	movl	$1, %ecx
	cmovgq	%rax, %rcx
	leaq	-1(%rcx), %rax
	leaq	-2(%rcx), %rdx
	mulq	%rdx
	shldq	$63, %rax, %rdx
	leaq	-1(%rdx,%rcx,2), %rbx
.LBB0_2:                                # %for.end

Posted on Edited on In , , ,

看了VC Blog的Constant-Folding之後，測試一下VC2012，GCC和Clang對最佳化的演繹程度為何。
比較基準，未開最佳化(VC是/Od，而GCC/Clang是-O0)，跟第二級最佳化(/O2和-O2)
第一個範例

1
int main() { return 7 + 8; }

不果是VC2012，GCC或是Clang都會直接將eax填入15，無論有沒有開最佳化。這邊的最佳化不需要後端Codegen的幫忙。
第二個範例

1
2
int bump(int n) { return n + 1; }
int main() { return 3 + bump(6); }

在未開最佳化的情況，VC產生的Assembly Code像這樣

1
2
3
mov     ecx, 6
call    ?bump@@YAHH@Z
add     eax, 3

而最佳化的Assembly Code則是

1
mov     eax, 10

這邊需要後端Codegen的幫忙，才能在編譯的時刻得到常數值。
而GCC跟Clang的表現也差不多，最大的差別是Intel語法跟AT&T對組合語言的表示方式不同。
未最佳化版本

1
2
3
movl	$6, %edi
call	_Z4bumpi
addl	$3, %eax

最佳化版本

1
movl	$10, %eax

在這種最簡單的最佳化大家都有一樣的能力，接著可以看其他部分的差異。

Posted on Edited on In ,

把目前看到的資訊做個總結，分幾篇文章來寫

從同步開始

假設我們要抓取Web Response，可以這樣寫。

lang: c#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static int BUFFER_SIZE = 1024;
static void getContentFromURI(string uri)
{
    WebRequest request = WebRequest.Create(uri);
    WebResponse response = request.GetResponse();
    Stream stream = response.GetResponseStream();
    byte[] buffer = new byte[BUFFER_SIZE];
    using (stream)
    {
        while (true)
        {
            int actualRead = stream.Read(buffer, 0, BUFFER_SIZE);
            if (actualRead != 0)
            {
                string partialContent = Encoding.Default.GetString(buffer, 0, actualRead);
                Console.WriteLine(partialContent);
            }
            else
            {
                break;
            }
        }
    }
}

以上都是同步動作，如果有個Thread呼叫此函數，外面的Thread必須等待這個函數執行結束，才能繼續往下走。如果是UI Thread的話，通常會出現漏斗符號，然後整個UI僵住的情形。

放到Thread

解決方案之一是把耗時的工作丟到Thread之後，外面呼叫的就能繼續向下執行。

lang: c#
1
2
3
4
5
6
7
static void ThreadStart()
{
    string uri = "http://www.facebook.com";
    getContentFromURI(uri);
}
Thread thd = new Thread(ThreadStart);
thd.Start();

更甚一點的是用ThreadPool來，減少Thread的開銷

lang: c#
1
ThreadPool.QueueUserWorkItem(state => ThreadStart());

不過這還是無法完全解決問題，這邊的行為是屬於IO Bounded Operation，不需要CPU計算能力，指需要完成之後，發個中斷通知CPU事件完成就好，使用Thread的解決方案還是不夠好。而.Net的IO Operation幾乎都有提供同步跟非同步的版本，就從這點開始。

.Net 1.0, BeginXXX / EndXXX

如同上面所說，幾乎所有IO operation都有非同步版本，而其命名都是BeginXXX / EndXXX開始，因此我們可以把程式改寫成這樣。

lang: c#
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
static void getContentFromURI(string uri)
{
    WebRequest myWebRequest = WebRequest.Create(uri);

    myWebRequest.BeginGetResponse(ar =>
    {
        WebResponse response = myWebRequest.EndGetResponse(ar);
        Stream stream = response.GetResponseStream();
        byte[] buffer = new byte[BUFFER_SIZE];
        using (stream)
        {
            while (true)
            {
                int actualRead = stream.Read(buffer, 0, BUFFER_SIZE);
                if (actualRead != 0)
                {
                    string partialContent = Encoding.Default.GetString(buffer, 0, actualRead);
                    Console.WriteLine(partialContent);
                }
                else
                {
                    break;
                }
            }
        }
    }, null);
}

程式碼被切成兩段，在GetResponse之前，跟GetResponse之後，相較於同步的版本，相差沒說很大。
談一下Exception部分，同步的版本指需要一個try-catch，而非同步的需要兩個，這邊變得很麻煩。
更進一步將Read的部份變成非同步的版本，程式碼會變成這樣。

lang: c#
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
static void ReadHelper(Stream stream)
{
	byte[] buffer = new byte[BUFFER_SIZE];
	stream.BeginRead(buffer, 0, BUFFER_SIZE, ar =>
	{
            int actualRead = stream.EndRead(ar);
            if (actualRead != 0)
            {
                string partialContent = Encoding.Default.GetString(buffer, 0, actualRead);
                Console.WriteLine(partialContent);
                ReadHelper(stream);
            }
            else
            {
                stream.Close();
            }
        }, null);
}
static void getContentFromURI(string uri)
{
	WebRequest myWebRequest = WebRequest.Create(uri);

	myWebRequest.BeginGetResponse(ar =>
	{
            WebResponse response = myWebRequest.EndGetResponse(ar);
            Stream stream = response.GetResponseStream();
            ReadHelper(stream);
	}, null);
}

這邊可以看到，用using釋放資源的方式已不可行，同樣的，用for/while的方式也不可行，必須使用Recursive的方式來持續讀取資料。而由於這樣，例外處理幾乎不可行。程式碼寫的支離破碎，難怪一堆人寧可寫同步版本。

Posted on Edited on In , ,

眾所週知，Java跟C#都是從C++演變而來。
既然C++有Template，Java在5.0，C#在2.0的時期分別引進了Generics，
雖然看起來很像，看其中差異還是不小，列出重要的幾點份來討論。

Generics不能接受Nontype Parameter

由於實作方式的不同，Generics拿掉了這個

lang: cpp
1
2
3
template <typename T, int MAXSIZE> class Stack {
	T stack[MAXSIZE];
};

Generic不支援Specialization

不管是Full Specialization或是 Partial Specialization，通通不行。所以也寫不出這樣的程式碼。

lang: cpp
1
2
template <typename T> class Foo {};
template <> class Foo<int> {};

Template不對Type作任何限制，而Generics能擁有Bound Type

這點才是最大的不同，假設我們要寫一個兩樹相加的Generic function。
在C++我們會這麼寫

lang: cpp
1
2
3
template <typename T> T sum2(T a, T b) { return a + b; }
sum2(100, 200);
sum2(string("Hello"), string("World"));

可以看到，只要有定義operator+，我們什麼東西都能相加。
同樣的Code，如果改寫成C#的話

lang: c#
1
2
3
4
public static T sum2<T>(T a, T b)
{
    return a + b;
}

連編譯都邊不過。原因出在Template是在Compile-Time完成的，在編譯的時刻就能檢查出operator+是否存在，而Java跟C#的Generics是在Runtime則否，必須對Type有其一定的限制，在這個範例裡面，我們需要這個Type要有相加的能力，才能作相加的動作。

lang: java
1
2
3
4
public <T extends Number> T sum(T a, T b) {
  T newValue = a.sum(b);
  return newValue;
 }

所有從Number衍生出來的子類別，Integer，Double等都可以使用，不過String不行。
不過.Net 4.0之後有更好的解法，掠過編譯時期的型別檢查，不過Java沒有此特性。

lang: c#
1
2
3
4
5
6
public static T sum2<T>(T a, T b)
{
    dynamic a_ = a;
    dynamic b_ = b;
    return a_ + b_;
}

Template不支援Covariance和Contravariance

這是另一個大題目，同樣在.Net 4.0之後，支援了Covariance和Contravariance。Java的版本有無支援也需要確認。
以後有時間再仔細描述。在C#可以寫這樣的Code

Covariance Example lang: c#
1
2
3
4
5
6
7
8
9
10
11
class Base
{
}
class Derived : Base
{
}
public static void Run(IEnumerable<Base> bases)
{
}
IEnumerable<Derived> derivedBases = new Derived[] { new Derived(), new Derived() };
Run(derivedBases);

類似的程式碼在C++就失敗了…

Covariance Example lang: c#
1
2
3
4
5
6
7
8
9
10
11
12
class Animal
{
    public void Feed() {}
}
class Frog : Animal {
}
static void DoSomethingToAFrog(Action<Frog> action, Frog frog)
{
        action(frog);
}
Action<Animal> feed = animal => { animal.Feed(); };
DoSomethingToAFrog(feed, new Frog());

其他Template高級技巧

例如SFINAE，Template Template Parameter等，由於學習門檻相當高，所以Generics都把它拿掉了。

Posted on Edited on In , ,

程式計算中有個技巧，叫做Memoization，避免重複計算相同的工作。
以下分別用C/Python/Haskell來當範例

C Language

以Fibonacci Number來說，遞迴的表示式這樣。

lang: c
1
2
3
4
5
int fib(int n)
{
	if (n < 2) return n;
	return fib(n - 1) + fib(n - 2);
}

加上Memoization的程式碼會變這樣

lang: c
1
2
3
4
5
6
7
8
int _fib[100];
int fib(int n)
{
	if (n < 2) return n;
	if (_fib[n] != -1) return _fib[n];
	return (_fib[n] = fib(n - 1) + fib(n - 2));
}
memset(_fib, -1, sizeof(fib));

Python

至於Python版Recursive的程式碼也相當相似

lang: python
1
2
3
4
5
def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

不過由於Python將Function當First-Class Function，可以寫出像這樣的程式碼。

lang: python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def memoize(fn):
    stored = {}
    def memoized(*args):
        try:
            return stored[args]
        except:
            result = fn(*args)
            stored[args] = result
            return result
    return memoized

def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

fib = memoize(fib)

更甚者可以使用Python的Decorator來簡化程式碼

lang: python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def memoize(fn):
    stored = {}
    def memoized(*args):
        try:
            return stored[args]
        except:
            result = fn(*args)
            stored[args] = result
            return result
    return memoized

@memoize
def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Haskell

Haskell反而是裡面最麻煩的，因為他是個純Pure Functional Language。同樣的先來看Recursive版本。

lang: haskell
1
2
3
4
fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

而Memorize版的方法不少，不過比起上面兩種反而難以理解。

lang: haskell
1
2
3
4
5
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib(n - 2) + memoized_fib(n - 1)

果然各種程式語言個有所長，看情況決定該用些什麼語言解決問題才是。

Posted on Edited on In ,

網路上另一個練習Coding跟Algroithm的網站，不過跟TopCoder跟一般的ACM Online Site不同，不限制語言，用任何方式都能，只需要正確答案。

第一題要列出1-999之間，三或五倍數的總和。要用熟悉的C++/Java寫不是不行，不過正好最近在練習Haskell，就用Haskell當做開端。

1
2
3
4
5
6
check x
        | (x `mod` 3 == 0) = True
        | (x `mod` 5 == 0) = True
        | otherwise = False
--- ans [1...999]
ans numbers = sum (filter check numbers)

Functional language的表達能力還真是高。

Posted on Edited on In , ,

這篇講的不是什麼技術面，而是每種物件導向程式語言都會碰到的情況。如何存取物件裡面的屬性。把屬性設成公開固然是一種解法，不過這就違反了Information Hiding的原則。各種程式語言作法都不同，這邊講我比較熟悉的部份(C++/C#/Java)。

從Java開始

這次從Java開始談，是因為最單純，沒有任何取巧的空間。

1
2
3
4
5
6
7
8
class Person {
	private String name;
	private int age;
	public String getName() { return name; }
	public void setName(String name) { this.name = name; }
	public int getAge() { return age; }
	public void setAge(int age) { this.age = age; }
};

每個getter/setter都要手刻，雖然可以藉由IDE的幫助，不過還是很麻煩。同樣在JVM上的城市語言，Scala就有在這點著墨。

C++的作法

藉由原本就有的Macro幫助，可以少打幾個字。

1
2
3
4
5
6
7
8
9
10
11
#define get_set_prop(type, Name) \
public: \
        type get##Name() { return Name; } \
        void set##Name(const type& v) { Name = v; }
class Person {
        string Name;
        int Age;
public:
        get_set_prop(int, Age)
        get_set_prop(string, Name)
};

不過也只是少打幾個字而已，IDE對於的Macro的支援度不同，Code completion可能會有問題。
加上Macro天生就很難除錯，Google C++ Coding Style建議能不用Macro就不用。

C#的Property

C#的Property算是一種語法糖，不過由於編譯器的支援，簡化了遇到的問題。以下以C# 4.0的示範

1
2
3
4
5
class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
}

雖然是語法糖，不過這樣表示新蜥易懂，也有很多人試著把這個特性家入到C++中，就知道這特性沒有無所謂，卻很實用。

Posted on Edited on

在Imperative programming下待久了，對於Functional language的一切都是覺得很新鮮。
Learn You a Haskell for Great Good!看到中途，筆記一下一些新觀念。

List comprehension

跟數學裡面Set comprehension的表達方法很像，假設我們想要找出直角三角形中，周長小於50的三元組的數量。 (假設 a <= b <= c 且 a ^ 2 + b ^ 2 = c ^ 2)。

如果是以往的作法，大概會像這樣

1
2
3
4
5
6
7
8
9
for (int a = 1; a <= 10; a++)
#define sqr(x) (x * x)
typedef tuple<int, int, int> tuple3;
std::vector<tuple3> ans;
for (int a = 1; a <= 50; a++)   
        for (int b = a; b <= 50; b++)           
                for (int c = b; c <= 50; c++)                   
                        if ((sqr(a) + sqr(b) == sqr(c))  && ((a + b + c) < 50))
                                ans.push_back(make_tuple(a, b, c));

如果是Haskell會是這樣，不同的語言寫法會不一樣，不過這上面列的C++11實作方式還不如上面來的直覺。

1
let xs = [(a, b, c) | a <- [1..50], b <- [a..50], c <- [b..50], a ^ 2 + b ^ 2 == c ^ 2, a + b + c < 50]

Pattern Matching

這邊跟我們常知的Pattern Matching不太相同，

Posted on Edited on In ,

在C99之後，新增了一種初始化方法。可以方便的設定structure/arry的初始值。帶來了極大的靈活

在之前的時期，要初始化一個structure，只能用以下的方式。

lang: c
1
2
3
4
5
typedef struct MyData {
    char *p;
    int v;
} MyData;
MyData a = { "name" , 10};

這種方式稱作Aggregate Initialization。
需要按照Type定義的方式來初始化，一旦我們修改MyData資料結構，所有用到MyData的初始化都需修改。
在C99之後，我們可以這樣做

lang: c
1
MyData a = { .v = 10, .p = "name"};

這樣就可以用任何順序指定初始值了。
另一個常用的應用場合是Array，拿以下這段程式碼當範例。

lang: c
1
2
3
4
5
6
7
8
9
10
enum {
    YAHOO = 0,
    GOOGLE,
    FACEBOOK
};
char *old_style_weburl[] = {
    "www.yahoo.com",        
    "www.google.com",       
    "www.facebook.com"  
};

當我們將 FACEBOOK跟YAHOO的順序對換之後，old_style_weburl的對應關係也要跟著改變。

lang: c
1
2
3
4
5
char *new_style_weburl[] = {
    [FACEBOOK] = "www.facebook.com",
    [YAHOO] = "www.yahoo.com",
    [GOOGLE] = "www.google.com"
};

這樣子不管enum裡的順序怎麼改變，new_style_weburl對應關係都能維持正確。
有興趣的可以參考Designated Initializers學到更多。