第十三號艦隊

Channel model for concurrency

Posted on 2014-01-23 Edited on 2025-02-21 In Cuncurrency , Go , Scala

解決Concurrency中shared infomation的方法不只一總，同樣是Message-based syste，Channel不過跟Actor model不同

Actor是直接跟其他Actor作溝通
Channel是兩端透過一個Channel連接，然後透過Channel傳輸到另一端，類似Unix的pipe

「Go](http://golang.org/)是最著名使用Channelmodel當做標準配備的程式語言。
看看Go網站上提供的範例

// A concurrent prime sieve

package main

import "fmt"

// Send the sequence 2, 3, 4, ... to channel 'ch'.
func Generate(ch chan<- int) {
	for i := 2; ; i++ {
		ch <- i // Send 'i' to channel 'ch'.
	}
}

// Copy the values from channel 'in' to channel 'out',
// removing those divisible by 'prime'.
func Filter(in <-chan int, out chan<- int, prime int) {
	for {
		i := <-in // Receive value from 'in'.
		if i%prime != 0 {
			out <- i // Send 'i' to 'out'.
		}
	}
}

// The prime sieve: Daisy-chain Filter processes.
func main() {
	ch := make(chan int) // Create a new channel.
	go Generate(ch)      // Launch Generate goroutine.
	for i := 0; i < 10; i++ {
		prime := <-ch
		fmt.Println(prime)
		ch1 := make(chan int)
		go Filter(ch, ch1, prime)
		ch = ch1
	}
}

原先的ch 是 [2, 3, 4, 5, 6, ….]的Channnel
在從for-loop中拿出2之後，變成[3, 4, 5, 6, …]
再度經過Filter函數，將2的倍數濾掉之後, ch1就是[3, 5, 7, 9, ….]的Channel
之後將ch1複製到ch，重複以上的動作。

這邊有Scala跟Go對Cuncurrency的比較
這邊是Go cunnerency的投影片

Actor model

Posted on 2014-01-20 Edited on 2025-02-21 In erlang , java , Scala , c++ , concurrency

About Actor Model

在Concurrency programming流行之後，Actor Model又重新熱門起來了。
一個Actor要做的就是以下幾件事情

建立其他 Actor
對其他Actor發送消息

接收並處理消息
因此，Erlang可以這樣寫

loop() ->
    receive
        {From, {store, Key, Value}} ->
            put(Key, {ok, Value}),
            From ! {kvs, true},
            loop();
        {From, {lookup, Key}} ->
            From ! {kvs, get(Key)},
            loop()
    end.

而沒有支援Tail Recursion的程式語言，如Scala等，用Loop來模擬Tail Recursion。

class Ping(count: int, pong: Actor) extends Actor {
  def act() {
    var pingsLeft = count - 1
    pong ! Ping
    while (true) {
      receive {
        case Pong =>
          if (pingsLeft % 1000 == 0)
            Console.println("Ping: pong")
          if (pingsLeft > 0) {
            pong ! Ping
            pingsLeft -= 1
          } else {
            Console.println("Ping: stop")
            pong ! Stop
            exit()
          }
      }
    }
  }
}

至於C++，有Theron這套Framework可以建構Actor，至於Event-based或是Thread-based就取決於用途了。

Why use Actor Model

根據網路上找到的資料，把它歸類為這幾個理由

No shared infomation，在多個Thread共享一段資料的時候，需要用Atomic operation或是Locks作保護。除了性能可能有所損失的話，不當的Lock sequence也會造成Dead lock。而Actor可以將information保存於單一個Actor當中。這樣就少去了錯誤同步的風險。當然，消除shared infomation的方案還有Functional programming。
Asynchronous，雖然Scala有提供同步版本的API。不過大部分的Actor implementation都是Asynchronous。不必耗費CPU Resource在等待完成的時刻。

valgrind resources

Posted on 2014-01-16 Edited on 2025-02-21

官方的The Valgrind Quick Start Guide
valgrind使用手册

new / delete in C++

Posted on 2014-01-01 Edited on 2025-02-21 In c++

在C++中，new / delete 總共有三種用法。new跟delete的用法類似，所以就以new來示範。

operator new

詳細細節可以參考operator new和operator new, operator new[]
可以透過function overload訂製自己的new和delete動作。
operater new/delete就相對於C語言的malloc/free。因此透過operator new分配到的記憶體就該用operator delete釋放。

struct Object {
	Object() {std::cout << '*' << std::endl; }  // print an asterisk for each construction
	void* operator new(size_t size)
	{
		return ::operator new(size);
	}
	void operator delete(void *ptr)
	{
		return ::operator delete(ptr);
	}
	void* operator new[](size_t size)
	{
		return ::operator new[](size);
	}
	void operator delete[](void *ptr)
	{
		return ::operator delete[](ptr);
	}
};
Object *obj = new Object;
delete obj;

這時就會使用Object裡面的new/delete的函式了。

Placement new

Placement new只是operator new的一種overload版本

inline void *operator new(size_t, void *_Where) 
{
	return (_Where);
}

詳細使用可以參考C++ FAQ中的介紹。
我們可以從任何記憶體位置(在Heap或是Stack都行)進行new constructor的動作。

void *pMemory = malloc(sizeof(Object));
Object *pObj1 = new (pMemory) Object;
pObj1->~Object();
free(pMemory);

char stackObj[sizeof(Object)];
Object *pObj2 = new (stackObj) Object;
pObj2->~Object();

Placement new的存在是有意義的，可以自由控制Memory的取得方式，可以從Stack/Heap/Memory Pool中取得記憶體，對於某些情景之下有更大的

new operator

這大概是最常見的動作，基本上就是以下兩個步驟構成

呼叫 operator new
呼叫 Constructor
這個順序是固定的，無法opverload，這是C++ Standard所規定的。

How to output Intel's assembly syntax for gcc

Posted on 2013-12-30 Edited on 2025-02-21 In GCC

看慣了x86的Intel Syntax，對於AT&T的語法還是不習慣。
使用以下方式可以將gcc編譯出來的Code變成Intel Syntax。

1	$ gcc test.c -S -masm=intel

這只支援gcc，clang不行。

Overloading postfix and prefix ++ in C++

Posted on 2013-12-30 Edited on 2025-02-21 In c++

突然想到，順手把他記下來吧。
在C++當中，如果要自己定義++和–這兩個operator，需要不同的Function signature。

class Date {
	//...
public:
	Date& operator++(); //prefix
	Date& operator--(); //prefix
	Date& operator++(int unused); //postfix
	Date& operator--(int unused); //postfix
};

最大的差別就在於Postfix裡面有個未使用的參數。至於為什麼要這麼設計，可以參考這裡。

Creating Variable-size structs in C/C++

Posted on 2013-12-26 Edited on 2025-02-21 In C , c++

這種技巧很常在Open Source的專案中看到，看了Arrays of Length Zero原本以為是GCC獨有Extensionm，後來發現Clang跟VC都能使用，記錄一下。

struct datapacket
{
    int size;
    int data[0];
];
void f()
{
struct datapacket *pkt =
    malloc( sizeof(struct datapacket) +
        sizeof(int)*9 );
/* further code . . . */
}

這邊的data[0]不佔記憶體空間，因此sizeof(struct datapacket)大小相當於sizeof(int)，而data就是一個記憶體指標，指向一塊連續的記憶體。

Write HelloWorld for LLVM IR

Posted on 2013-12-23 Edited on 2025-02-21

一直想寫一篇關於LLVM的文章，想了好久終於下筆了。同樣從Hello world開始下手

#include <stdio.h>
int main()
{
        puts("Hello world!\n");
        return 0;
}

編譯成 LLVM的IR中間形式，利用lli來執行IR Code。

1 2	$ clang hello.c -S -emit-llvm -o hello.lli $ lli hello.lli

刪除hello.lli的Meta data之後，一個Hello world的最小部分掌這個樣子

@.str = private unnamed_addr constant [14 x i8] c"Hello world!\0A\00", align 1
define i32 @main() #0 {
  %1 = alloca i32, align 4
  store i32 0, i32* %1
  %2 = call i32 @puts(i8* getelementptr inbounds ([14 x i8]* @.str, i32 0, i32 0))
  ret i32 0
}
declare i32 @puts(i8*) #1

Useful algorithms in real product

Posted on 2013-12-20 Edited on 2025-02-21 In DataStructure , Algorithm

在StackExchange有人問了一個問題。在實際產品中常用的資料結構跟演算法有哪些。

把這當做一個參考，有空的時候可以研究一下。

How to call C/C++ code from Python

Posted on 2013-12-09 Edited on 2025-02-21 In C , Python

這篇文章正好是上一篇的相反行為。為了加速某些特殊運算，有時需要呼叫C/C++的程式碼。使用Python內建的ctypes可以幫助完成這件事。

lang: cpp foo.cpp

#include <iostream>

class Foo {
public:
        void bar() {
            std::cout << "Hello" << std::endl;
        }
};

extern "C" {
    Foo* Foo_new(){ return new Foo(); }
    void Foo_bar(Foo* foo) { foo->bar(); }
}

將其編譯成Shared Library / DLL。

1 2	$ g++ -c -fPIC foo.cpp -o foo.o $ g++ -shared -Wl,-soname,libfoo.so -o libfoo.so foo.o

接著就是Python code上場了

from ctypes import cdll
lib = cdll.LoadLibrary('./libfoo.so')

class Foo(object):
    def __init__(self):
        self.obj = lib.Foo_new()

    def bar(self):
        lib.Foo_bar(self.obj)

f = Foo()
f.bar() #and you will see "Hello" on the screen

Windows版跟Linux版大同小異，最大的差別在於Windows可以寫 ./libfoo 而不用寫 ./libfoo.dll：而 Linux沒有附檔名的話會發生錯誤。

當然，swig跟Boost Python一樣可以幫忙完成這件事。