第十三號艦隊
0%

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學到更多。

Posted on Edited on In

趁著Android 4.3的出現，記錄一下如何編譯一個Android環境。

首先，建立一個Android目錄。

1
2
3
4
5
$ mkdir Android && cd Android
$ mkdir bin && cd bin
$ curl https://dl-ssl.google.com/dl/googlesource/git-repo/repo > /repo
$ chmod a+x repo
$ cd ..

建立一個source的目錄存放程式碼。

1
2
$ mkdir source && cd source 
$ ../bin/repo init -u https://android.googlesource.com/platform/manifest -bandroid-4.3_r2.1

開始下載，時間很久，請耐心等待

1
$ ../bin/repo sync

建置環境

1
2
3
$ source build/envsetup.sh
$ lunch full-eng
$ make -j 4

完成之後執行開啟模擬器

1
$ emulator

如果又更多問題，可以參考官網的說明，建議在64 bits的Linux底下操作。

Posted on Edited on In

接續上個範例

我們將add2這個函數從demo中題取出來，建立一個math library，讓其他人使用。
提供header file跟library，header file放在include目錄底下，source code放在lib底下>
我們的header file： MyMath.h

1
2
3
4
#ifndef _MyMath_H_
#define _MyMath_H_
int add2(int, int);
#endif

實作add2.c

1
2
#include "MyMath.h"
int add2(int a, int b) { return a + b; }

重點的CMakeLists.txt部分

1
ADD_LIBRARY(mymath STATIC add2.c)

重新改寫我們的demo

1
2
3
4
5
6
7
#include <stdio.h>
#include "MyMath.h"
int main()
{
        printf("%d\n", add2(1, 1));
        return 0;
}

以及CMakeLists.txt

1
2
ADD_EXECUTABLE(demo demo.c)
TARGET_LINK_LIBRARIES(demo mymath)

目錄下的CMakeLists.txt也要跟著更新

1
2
3
4
5
6
PROJECT(CMakeDemo C)
cmake_minimum_required(VERSION 2.8)
SET(EXECUTABLE_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)
SET(LIBRARY_OUTPUT_PATH ${PROJECT_SOURCE_DIR}/bin)
INCLUDE_DIRECTORIES(${PROJECT_SOURCE_DIR}/include)
SUBDIRS(src lib)

在城市規模小的時候，直接寫Makefile是個比較快的解決方案，不過當規模更大，以及要跨平台的時候，CMake的優勢就出現了。

如何使用編譯參數

上面這個範例，我們是使用static library，我們假設要在編譯的時候選擇是要用static library或是shared library，該怎麼進行。

重新改寫 lib/CMakeLists.txt

1
2
3
4
5
if (ENABLE_SHAREDLIB)
ADD_LIBRARY(mymath SHARED add2.c)
else()
ADD_LIBRARY(mymath STATIC add2.c)
endif()

之後我們在產生Makefile之前下以下參數就能選擇了

1
$ cmake .. -DENABLE_SHAREDLIB=TRUE

這樣就能選擇編譯成shared librarry了。