MILL:在 C 裡面實作 Go-style 的 concurrency

看到「Go-style concurrency in C」這個專案,在 C 上實作 Go-style 的 concurrency,包括了 channel 的設計。原始程式碼可以在 GitHub 上的「sustrik/mill」看到。

在「mill.c」可以看到實作細節,另外也可以看到 yield() 的設計。

不過目前還很早期,請小心服用:

This is a proof of concept project that seems to work with x86-64, gcc and Linux. I have no idea about different environments. Also, the project is in very early stage of development and not suitable for actual usage.

Google 將之前買下 Skybox 公司的工具放出來 (MapReduce for C)

Zite 上看到的,Google 把之前買下的 Skybox 所開發的工具 MapReduce for C (MR4C) 放出來:「Google open sources a MapReduce framework for C/C++」。

MR4C 的程式碼放在 GitHub 上,以 Apache License Version 2.0 授權放出來:「google/mr4c」。

C 對 Go Channel 的實做

在「Pure C implementation of Go channels.」這邊看到有人在 C 語言裡面實做 Go 的 Channel,包括了 Unbuffered 與 Buffered 版本。

看起來是支援 multithreading 的:「Add missing pthread_cond_destroy in chan init cleanup」、「Add -lpthread to CFLAGS」。

Go 的 self-boot 計畫

Go 的 self-boot 計畫,也就是用 Go compiler 編 Go compiler:「Russ Cox – porting the Go compiler from C to Go」。

其中提到:

The goal is to convert *their* C code (not all C code). They want generated code to be human-readable and maintainable. They want automatic conversion to handle 99+% of code.

第一波想要用機器轉換過去,而且要轉出可維護的程式碼。可以馬上想到的事情是,如果這件事情成功,代表現有軟體的 C code 也有機會轉移?

接下來了幾個版本會開始發展整套機制,有得瞧了 :p

C 語言的 extern 與 static...

把十年多的 BBS source code porting 到 Ubuntu 上,被迫要用 GCC 4.6 而一路找出來的...

在 BBS 內有這樣的資料結構要處理:

typedef struct p {
    struct p *pointer;
} P;

static P p1 = { &p2 };
static P p2 = { &p1 };

兩個要互指,但在指定 p1 時 p2 還沒有被定義,所以要用 extern 先宣告:

typedef struct p {
    struct p *pointer;
} P;

extern P p2;

static P p1 = { &p2 };
static P p2 = { &p1 };

這個語法在舊版的 GCC 沒問題 (3.4),但在新版的 GCC 4.6 上不接受這個寫法,會抱怨後面的 p2 實際在宣告是 static,與前面的 extern non-static 不符。

後來在 Stack Overflow 上找到「static extern vs extern static」這篇說明,要先定義 static 再定義 extern:

static P p2;
extern P p2;

這樣寫的原因在原文的下方有說明,所以是 C99 定義的關係?

ESR 解釋 C 的 Compiler 對 Structure Packing 的處理...

ESR (Eric S. Raymond) 寫了一篇 C Compiler 對 struct 實際如何佔用記憶體空間的說明:「The Lost Art of C Structure Packing」,全文在「The Lost Art of C Structure Packing」。

以前都學過也都還記得,但沒用就不容易想起來...

以文章裡的例子用這個 struct 說明:

struct {
    char *p;
    char c;
    int x;
};

(下面就不列出 struct 的部份了)

實際上在記憶體裡面會因為 alignment requirement 的關係,多了一個 padding (pad):

char *p;      /* 4 or 8 bytes */char c;       /* 1 byte */char pad[3];  /* 3 bytes */int x;        /* 4 bytes */

而如果 x 是 8 bytes 的 long 時:

char *p;
char c;
long x;

padding 會變成:

char *p;     /* 8 bytes */char c;      /* 1 byte
char pad[7]; /* 7 bytes */long x;      /* 8 bytes */

這是因為硬體架構的關係。有些是因為硬體只支援切齊 alignment 的存取指令,有些是因為效率的差異而預設會增加 padding。

在處理 protocol 這類必須依照原始的 struct 設計時,需要指定

#pragma pack

強迫 compiler 關掉,不然 compiler 還是會補上 padding。

而在一般的情況下,調整 struct 裡元素的位置就能夠在不影像存取效能的前提下節省空間,如果是大量的 struct 時效果就會變得很明顯...

用 C Macro 實作的紅黑樹...

用 C Macro 實作的紅黑樹 (Red-black tree) 很經典,不過每次都忘記怎麼用... XD

紅黑樹是平衡二元搜尋樹的一種,除了二元搜尋樹有的結構外,節點的資訊多了顏色。然後利用顏色達到平衡的特性。

先定義單一節點的資料結構:

struct element {
    char *key;

    int value1;
    char *value2;

    RB_ENTRY(element) meta;
};

紅黑樹的每個節點都需要紀錄母、左、右節點的指標,以及顏色,其中 RB_ENTRY() 所代表的資料結構會負責紀錄這些值。

再來是定義母節點的資料結構,這樣之後就可以使用 struct tree tree1;struct tree tree2;struct tree tree3; 產生許多 tree 了:

RB_HEAD(tree, element);

這樣就會產生 struct tree 這個資料結構。如果只用一次可以偷懶寫成:

RB_HEAD(tree, element) tree1;

定義完資料結構後,接著比較函數 (要如何在兩個元素之間挑出大的那個):

int element_cmp(struct element *a, struct element *b)
{
    return strcmp(a->key, b->key);
}

接著就可以產生 C 語言的 function prototype,以及實際的 function:

RB_PROTOTYPE(tree, element, meta, element_cmp);
RB_GENERATE(tree, element, meta, element_cmp);

然後程式裡面就可以這樣初始化:

struct tree tree1;
RB_INIT(&tree1);

其中 tree1 就變成之後所有操作的基礎。

增加元素:

struct element *el;
el = malloc(sizeof(struct element));
el->key = strdup("key1");
el->value1 = 1;
el->value2 = strdup("value2");
RB_INSERT(tree, &tree1, el);

如果要尋找的話可以用 RB_FIND()

el->key = "key2";
pointer = RB_FIND(tree, &tree1, el);

其他的就翻 tree.h 檔裡面類推...

了解 C 語言的數字資料型態...

在「Deep C: Understanding the Design of C Integer Types」這篇文章裡面以 C99 為參考文件,說明 C 語言的資料型態 (尤其是數字的部份)。

裡面引用了規個書的文件,說明「為什麼」數字資料型態會長這樣:

To help ensure that no code explosion occurs for what appears to be a very simple operation, many operations are defined to be how the target machine’s hardware does it rather than by a general abstract rule.

以 target machine 為主要考量的特性與 C 語言被認為是 portable assembly language 的想法還蠻同調的... (What is a portable assembly language?)

所以寫 Portable C code 的人會比較辛苦,需要查規格書的資料,確保各平台都能夠正確被編譯... 而到最後演變成沒什麼人在管 "portable" 這件事情,反正 Autotools 開下去針對不能跑的平台用不同的 code XD

FreeBSD 將在 10.0 時將預設編譯器從 GCC 換成 clang

FreeBSD 預定在今年十一月將 amd64 與 i386 版本的 C 與 C++ 預設編譯器從 GCC 4.2.1 換成 clang,也就是下一個 major release (10.0) 就會是預設編譯器:「Clang as default compiler November 4th」。

自從 GCC 決定要換成 GPLv3 後整個計畫才活起來,到現在走了三年,看起來明年應該有機會看到預設是使用 clang 的 FreeBSD?

接下來的工作是解決 Ports 裡面一堆用 clang 編不過的軟體,以目前「Ports and Clang」這邊列出來的數量,看起來把幾個大的傢伙解決掉就差不多了?(不過應該是不怎麼好解,不然這種大目標物應該早就解決了...)

推薦《An Introduction to Programming in Go》這本書...

書的資料:

An Introduction to Programming in Go.
Copyright © 2012 by Caleb Doxsey
ISBN: 978-1478355823

以及網站:「An Introduction to Programming in Go」。有平裝實體書版本,也有電子 Kindle 版,網站上有 PDF 可以下載,或是直接 HTML 觀看。我是看完 HTML 版後買了一本 Kindle 版來翻...

這是一本講程式語言 Go 的入門書。看完後,我覺得這不是寫給第一次接觸程式語言而需要自己學習的人。這本書的編排,以及 Go 程式語言的特性,是寫給想要用 C++ 解決 C 問題卻弄的滿頭包的人另外一個方案。語言的特性很明顯可以感覺到 Go 想要找出更自然 (以及「優雅」) 的方式解決問題。

第三章講資料型態提到內建了 uint8uint16uint32uint64int8int16int32 以及 int64,以及 byte == uint8rune == int32。以前需要透過 autotools 的類的程式處理,現在是程式語言直接定義好。

然後支援 float32float64,以及 complex64complex128 直接避免 sqrt(-1) 的問題!內建 boolean (truefalse),把以前的壞習慣 (直接拿數字型態判斷) 處理掉...

第六章講內建 Arrays、Slices、Maps,這時候就可以發現 fmt.Println 可以直接輸出 (以前 C 就沒辦法用 printf 大絕直接對 array 輸出!) !然後很嚴格的不讓你在整數與小數之間亂轉...

而內建 Maps 這件事情超重要,已經是現在程式語言的基本資料型態 XD

第七章描述 Functions,把以前只能傳單變數的問題解決,並且介紹 Closure,然後介紹 Defer!是 Defer 啊!(該死的 fd leak...)

第十章 Concurrency 把以前用 POSIX threading library 的痛給解掉,多個 thread 要怎麼有效的互相傳資料一直都是痛 (超痛),引入 channel 的觀念內建進 Go...

很推薦購買的一本書,天瓏如果有進的話應該會再去拿一本實體...