第十三號艦隊

Thought about macros

Posted on 2015-09-01 Edited on 2024-11-15

Macro這東西很早就有了，不過各有巧妙不同。
在Assembler的年代就已經有Macro了

COPY            macro   Dest, Source
                mov     ax, Source
                mov     Dest, ax
                endm

而在C語言的時候，Macro的被使用了更頻繁了

1	#define min(a, b) ((a < b) ? a : b)

C語言的Macro也很簡單，就只是作文字的代換而已。Side Effect除外，出錯的話也很難Debug，因此其他語言打算因此作改進。

Define group of functions

#define CK_PR_FENCE(T, I)                               \
        CK_CC_INLINE static void                        \
        ck_pr_fence_strict_##T(void)                    \
        {                                               \
                __asm__ __volatile__(I ::: "memory");   \
        }

CK_PR_FENCE(atomic, "sfence")
CK_PR_FENCE(atomic_store, "sfence")
CK_PR_FENCE(atomic_load, "mfence")
CK_PR_FENCE(store_atomic, "sfence")
CK_PR_FENCE(load_atomic, "mfence")
CK_PR_FENCE(load, "lfence")

在這情況下 Templateˊ無能為力.

Rust

Macro overload

macro_rules! sayHello {
    () => {
       println!("sayHello");
    };
    ($name:ident) => {
       println!("sayHello {:?}",  stringify!($name));
    };
}
fn main() {
    sayHello!();
    sayHello!(ABC);
    
}

Pattern Matching

macro_rules! min {
    // base case
    ($x:expr) => ($x);
    // `$x` followed by at least one `$y,`
    ($x:expr, $($y:expr),+) => (
        // call min! on the tail `$y`
        std::cmp::min($x, min!($($y),+))
    )
}

Recursive Macro

macro_rules! write_html {
    ($w:expr, ) => (());

    ($w:expr, $e:tt) => (write!($w, "{}", $e));

    ($w:expr, $tag:ident [ $($inner:tt)* ] $($rest:tt)*) => {{
        write!($w, "<{}>", stringify!($tag));
        write_html!($w, $($inner)*);
        write!($w, "</{}>", stringify!($tag));
        write_html!($w, $($rest)*);
    }};
}

fn main() {
    use std::fmt::Write;
    let mut out = String::new();

    write_html!(&mut out,
        html[
            head[title["Macros guide"]]
            body[h1["Macros are the best!"]]
        ]);

    assert_eq!(out,
        "<html><head><title>Macros guide</title></head>\
         <body><h1>Macros are the best!</h1></body></html>");
}

Nim

Reference

– Macros - Rust Documentation
– A Quick Intro to Rust Macros
– Module macros - Nim
– Nim Manual

Build freebsd kernel

Posted on 2015-08-15 Edited on 2024-11-15 In freebsd

雖然這些東西網路上都找得到，不過為了節省時間，把相關步驟一次記下來。

UsersFetchingSource

有些時刻/usr/src是空的，所以需要手動獲取程式碼

1 2	$ pkg install svnup $ svnup stable -h svn.freebsd.org

The Configuration File

修改自己需要的Configuration File

1 2	$ cd /usr/src/sys/amd64/conf $ cp GENERIC MYKERNEL

Building and Installing a Custom Kernel

1
2
3

$ cd /usr/src
$ make buildkernel KERNCONF=MYKERNEL
$ make installkernel KERNCONF=MYKERNEL

Reference:

Install Hadoop 2.7 on Ubuntu 14.04

Posted on 2015-06-10 Edited on 2024-11-15

Create Hadoop Account

1
2
3

$ sudo useradd -m hadoop -s /bin/bash
$ sudo passwd hadoop
$ sudo adduser hadoop sudo

Setup ssh environemtn

$ sudo apt-get install openssh-server
$ cd ~/.ssh/ 
$ ssh-keygen -t rsa
$ cat id_rsa.pub >> authorized_keys

Instal Java

1	$ sudo apt-get install openjdk-7-jre openjdk-7-jdk

修改~/.bashrc押入

export JAVA_HOME=/usr/lib/jvm/java-7-openjdk-amd64

1	$ source ~/.bashrc

Install Hadoop

1
2
3

$ sudo tar -zxvf ./hadoop-2.7.0.tar.gz -C /usr/local
$ sudo mv ./hadoop-2.7.0/ ./hadoop
$ sudo chown -R hadoop:hadoop ./hadoop

單機Hadoop建立

執行測試程, ˊ執行時記得不能有output`目錄存在

$ sudo mkdir input
$ sudo cp README.txt input
$ bin/hadoop jar share/hadoop/mapreduce/sources/hadoop-mapreduce-examples-2.7.0-sources.jar  org.apache.hadoop.examples.WordCount input output
$ cat output/*

偽分布式Hadoop建立

修改/usr/local/hadoop/etc/hadoop/core-site.xml

<configuration>
    <property>
        <name>hadoop.tmp.dir</name>
        <value>file:/usr/local/hadoop/tmp</value>
        <description>Abase for other temporary directories.</description>
    </property>
    <property>
        <name>fs.defaultFS</name>
        <value>hdfs://localhost:9000</value>
    </property>
</configuration>

修改/usr/local/hadoop/etc/hadoop/hdfs-site.xml

<configuration>
    <property>
        <name>dfs.replication</name>
        <value>1</value>
    </property>
    <property>
        <name>dfs.namenode.name.dir</name>
        <value>file:/usr/local/hadoop/tmp/dfs/name</value>
    </property>
    <property>
        <name>dfs.datanode.data.dir</name>
        <value>file:/usr/local/hadoop/tmp/dfs/data</value>
    </property>
</configuration>

###請動Hadoop
進行Namenode格式化

1	$ bin/hadoop namenode -format

啟動Guardian process

1	s bin/start-dfs.sh

可以連到 http://localhost:50070 來觀察adoop狀態

俄式偽分布式Hadoop

$ bin/hdfs dfs -mkdir -p /user/hadoop
$ bin/hdfs dfs -put README.txt input
$ bin/hadoop jar share/hadoop/mapreduce/sources/hadoop-mapreduce-examples-2.7.0-sources.jar  org.apache.hadoop.examples.WordCount input output
$  bin/hdfs dfs -cat output/*

Reference

How to pass exception between threads in C++11

Posted on 2015-05-21 Edited on 2024-11-15 In C++11

長知識了，直接看Code比較快

int calc(std::exception_ptr& eptr)
{
        try {
                std::string s;
                s.at(0);  // throw out of range exception
        } catch (...) {
                eptr = std::current_exception();
        }
        return 0;
}
int main()
{
        std::exception_ptr eptr;
        auto f = std::async(std::launch::async, std::bind(calc, std::ref(eptr))); 
        try {
                int i = f.get();
                if (eptr) {
                        std::rethrow_exception(eptr);
                }
                std::cout << i << std::endl;
        } catch (const std::exception& e) {
                std::cout << e.what() << std::endl;
        }
        return 0;
}ion_ptr eptr;
        auto f = std::async(std::launch::async, std::bind(calc, std::ref(eptr))); 
        try {
                int i = f.get();
                if (eptr) {
                        std::rethrow_exception(eptr);
                }
                std::cout << i << std::endl;
        } catch (const std::exception& e) {
                std::cout << e.what() << std::endl;
        }
        return 0;
}

如果要在Thread傳輸exception的食，記得紀錄一個exception_ptr，當exception發生食，用current_exception()捕捉在當今thread發生的excetipn。然後其他Thread發現這個eptr存在的話，透過rethrow_exception處理這個exception。
不過這樣作一點都不直覺啊

Better Solution

搭配同時加入C++11的thread和future，可以寫出更加優雅的Code，promise不僅解決了exception的問題，同時也提供了Thread return value的問題>

void calc(std::promise<int> && p)
{
        try {
                std::string s;
                s.at(0);  // throw out of range exception
                p.set_value(0);
        } catch (...) {
                p.set_exception(std::current_exception());
        }
}
int main()
{
        std::promise<int> p;
        std::future<int> f = p.get_future();
        std::thread thd(calc, std::move(p));
        try {
                int i = f.get();
                std::cout << i << std::endl;
        } catch (const std::exception& e) {
                std::cout << e.what() << std::endl;
        }
        thd.join();
        return 0;
}

‵``

The story about return value and error handling

Posted on 2015-05-20 Edited on 2024-11-15 In c++ , Rust

這故事說起來還真不簡單，在寫Code的時候，往往與這兩樣東西牽扯不清。
例如以下這段Code

1
2
3

FILE *fp = fopen( "input.txt", "r");
if (fp == NULL)
	printf ("  err %d \n", errno);

fp代表著回傳的正常值，errno表示萬一錯誤的時候，可以供判斷的錯誤依據。
不過就算是return value跟error code，也有很長故事可以說。
以 $ f(x)=\frac{100}{\frac{100}{x}+1} $ 當我們的範例，來討論各種處理return value跟error handleing

Global state

在設計API的時候，就完全沒考慮過Error這件事，如同上面的errno那樣，我們可以仿照使用一個global variable。
可能的作法如下

int _errno;
const int invalid_value = -1;
int g(int x) {
	if (x == 0) {
		_errno = -1;
		return invalid_value;
	}
	return 100 / x + 1;
}
int f(int x)
{
	int v1 = g(x);
	if (v1 == invalid_value)
		return v1;
	if (v1 == 0) {
		_errno = -2;
		return invalid_value;
	}
	return 100 / v1;
}

這作法不難懂，不過有幾個很重大的缺點
– 需要對Return Value定義一個特蘇的值，代表這個值是無效的，而這個Return Value有可能跟值域的某個數值碰撞。例如上例的f(-50)，你不知道他是錯誤還是有效值。
– global variable表示任何人都有機會更動到，因此在Code的Maintain跟Protect上難很多
– Error很容易被忽略，因為沒有強制性，可能在實做內部，或是外部使用，都有可能因為Code的修改而跳過Error Code處理

因此有了改良版的方法

Return Error and Value simultaneously

上面方法的改良版

int g(int x, int *retvalue) {
	if (x == 0)
		return -1;
	*retvalue = 100 / x + 1;
	return 0;
}
int f(int x, int *retvalue)
{
	int err = g(x, retvalue);
	if (err != 0)
		return err;
	if (*retvalue == 0) 
		return -2;
	*retvalue = 100 / (*retvalue);
	return 0;
}

這邊的寫法類似於COM的作法，把return value放在最後一個參數，而errorcode當作return值傳回。
也可以像golang那樣傳回多個回傳質的方法，大同小異

f, err := os.Open("filename.ext")
if err != nil {
    log.Fatal(err)
}

這方是解決了上述錢兩個問題，不過還是無法解決第三個問題

Exception-Based solution

越來越多程式語言都加入當標準配備了。

int g(int x) {
	if (x == 0)
		throw std::exception("cannot be zero in g");
	return 100 / x + 1;
}
int f(int x)
{
	int v1 = g(x);
	if (v1 == 0) 
		throw std::exception("cannot be zero in f");
	return 100 / v1;
}
	try {
		f(0);
	}
	catch (std::exception e) {
	}

比起上述兩種，exception的優點
– 不需要特異定義一堆內部的Error Code Value，並且Code的可讀性比上面兩者都強。可以專住在Logic上的Code。
而缺點是：
– 效能問題，雖然這問題越來越不重要，不過使用Exception的方案通常比Error code慢。
– Boundary issue，當跨越兩個Shared library的程式碼互動食，這方案完全派不上用場。還是要走回上面的老路。

Railway Oriented Programming

錢幾個作法都是遇到問題就往上拋，而ROP反其道而行，將錯誤往後傳，最後統一處理。

這例子改用ustㄉ做示範範例因為C++诶有ML系Language Pattern Matching和Abstract Data Type，要模擬這個不如直接換個語言寫寫看當練習。

enum Result {
        Value(i32),
        Error(&'static str)
}
fn div(x: Result, y: Result) -> Result {
        match y {
                Result::Value(0) => Result::Error("Cannot divide 0"),
                Result::Value(y_) => {
                        match x {
                                Result::Value(x_) => Result::Value(x_ / y_),
                                _ => x
                        }
                },
                _ => y
        }
}
fn add1(x: Result) -> Result {
        match x {
                Result::Value(v) => Result::Value(v + 1),
                _ => x
        }
}
fn f(x: i32) -> Result {
        return div(Result::Value(100), add1(div(Result::Value(100), Result::Value(x))));
}
fn main() {
        let value = f(25);
        match value {
                Result::Value(v) =>  println!("The result value is {}", v),
                Result::Error(str) => println!("Error happen, {}", str)
        }
}

座個事情很簡單，如果Result是有效的值就繼續往下做，不然就直接往後傳。

Enhance Monad solution for Railway Oriented Programming

網路上有很多Monad的介紹，於是東施校憑寫了一個山寨版的。關鍵在於所謂的bind函數，這裡就不多介紹了。

trait Monad {
        fn unit(x: i32) -> Self;
        fn bind(&self, f: fn(i32) -> Self) -> Self;
}
enum Result {
        Value(i32),
        Error(&'static str)
}
impl Monad for Result {
        fn unit(x: i32) -> Result {
                Result::Value(x)
        }
        fn bind(&self, f: fn(i32) -> Self) -> Self {
                match *self {
                        Result::Value(x) => f(x),
                        Result::Error(str) => Result::Error(str)
                }
        }
}
fn div100(x: i32) -> Result {
        match x {
                0 => Result::Error("Cannot divide 0"),
                _ => Result::Value(100 / x)
        }
}
fn add1(x: i32) -> Result {
        Result::Value(x + 1)
}
fn f(x: i32) -> Result {
        Result::unit(x).bind(div100).bind(add1).bind(div100)
}
~

Reference

– C++ Exceptions: Pros and Cons
– http://fsharpforfunandprofit.com/rop/

Type traits in C++11

Posted on 2015-05-07 Edited on 2024-11-15

std::decay

如名稱所說，將所獲取到的類型作退化的動作。
先移除類型T的Reference，得累類型U

如果 is_array::value 為 treu，修改類型type為remove_extent::type *

如果 is_function::value 為 true，修改類型type為add_pointer::type

否則，修改類型type為remove_cv::type
不過decay可以用來作些什麼？

將參數以值的方式傳回

N2609提了一種用法

template <class T1, class T2> 
inline pair<T1,T2> make_pair(T1 x, T2 y)
{ 
    return pair<T1,T2>(x, y); 
}

這段Code能動，不過會多出複製物件的成本

1	std::pair<std::string, int> p = make_pair("foo", 0);

如果我們改用Refernece的傳法重寫的話

template <class T1, class T2> 
inline pair<T1,T2> make_pair(T1&& x, T2&& y)
{ 
    return pair<T1,T2>(x, y); 
}

以上麵這個範例的話，T1會被推導成const char[4]，而不是const char *。因此我們需要Decay
正確的寫法類似這樣

template <class T1, class T2> 
inline pair< typename decay<T1>::type, typename decay<T2>::type > 
make_pair(T1&& x, T2&& y)
{ 
    return pair< typename decay<T1>::type, 
                 typename decay<T2>::type >(std::forward<T1>(x), 
                                            std::forward<T2>(y)); 
}

之前的make_resource範例

template<typename Creator, typename Destructor, typename... Arguments>
auto make_resource(Creator c, Destructor d, Arguments&&... args)
{
	auto r = c(std::forward<Arguments>(args)...);
	if (!r) { throw std::runtime_error{ "Unable to create resource" }; }
	typedef typename std::decay<decltype(*r)>::type ResourceType;
	return std::unique_ptr<ResourceType, void(*)(ResourceType*)>(r, d);
}

為了decay推導出primitive type，將變化包裝起來不讓外界知道。

std::result_of

看了Stackoverflow，覺得這東西可以完全用decltype去代。有興趣的話可以參考CppReference的用法。

std::enable_if

SFINAE

Some thought about C/C++

Posted on 2015-04-23 Edited on 2024-11-15 In C , c++

前一陣子在做C++轉C Code的動作，真是麻煩的苦工。在看到Modern C++ in embedded systems – Part 1: Myth and Reality還真是心有慼慼焉啊。C++能做的，C當然也可以，不過程式可讀性差很多，以下列出幾點。

Function overload

void Dosomething(int v);
void Dosomething(float v);
Dosomething(1);
Dosomething(3.14f);

這樣的Code在C++可行，在C會編譯失敗，因此要自行加上suffix錯開

void DosomethingWithInt(int v);
void DosomethingWithFloat(float v);
DosomethingWithInt(1);
DosomethingWithFloat(3.14f);

雖然效果是一樣的，不過人的記憶力是有限的，同時兩個淚名稱不同，功能相似的函式，有事沒事要分心注意，會殺死一堆腦細胞。
在C11之後，終於有了Generic Selections可用了。

define Dosomething(X) _Generic((X),  \
        int: DosomethingWithInt,  \
        float: DosomethingWithFloat)(X)
Dosomething(1);
Dosomething(3.14f);

這下看起來好多了，不過如果每增加一種寒士，就要修改一次Dosomething的定義。還是很麻煩啊。這也無法解決所有問題。

Constructor & Destructor

在C++當中是

struct Obj {
        Obj(int v);
        ~Obj();
};
int Doanotherthing(Obj *v);
nt Dosomething()
{
        Obj local(10);
        return Doanotherthing(&local);
}

同樣的Code在C與研究寫得支離破碎了

void init_Obj(Obj *this, int v) 
void uninit_Obj(Obj *this);
int Dosomething()
{
        Obj local;
        init_Obj(&local, 10);
        int result = Doanotherthing(&local);
        uninit_Obj(&local);
        return result;
}

由於C不會主動去呼叫Destructor，因此要將計算的值存起來，所以要主動呼叫Destructor。
由於我們不能簡單的把Constructor和Destructor定義成init和uninit就好，原因同上面的Function overload，只好加上自行的suffix避開這個問題。

Member function

雖然這兩樣寫差異無幾

1
2
3

Obj *obj;
obj->Dosomething(); // member function
Dosomething(obj); // pass object to function

萬一有個cstruct 也有Dosomething的函式怎麼辦

1
2
3

Obj2 *obj2;
obj2->Dosomething(); // member function
DosomethingWithObj2(obj2); // pass object to function

又回到老問題了，不能function overload就要手動繞過很多眉角。

Continuation, Calll/cc and CPS

Posted on 2015-04-10 Edited on 2024-11-15 In programming , javascript , c++

又是一個很雜的題目。

Continuation

看了很多定義之後，覺得這定義是最好的。

所謂continuation，其實本來是一個函數調用機制。

我們熟悉的函數調用方法都是使用堆棧，采用Activation record或者叫Stack frame來記錄從最頂層函數到當前函數的所有context。一個frame/record就是一個函數的局部上下文信息，包括所有的局部變量的值和SP, PC指針的值（通過靜態分析，某些局部變量的信息是不必保存的，特殊的如尾調用的情況則不需要任何stack frame。不過，邏輯上，我們認爲所有信息都被保存了）。函數
的調用前往往伴隨著一些push來保存context信息，函數退出時則是取消當前的record/frame，恢複上一個調用者的record/frame。

如果有用過C/C++/Java等開發過，對於Stack Frame隊上面這段話應該不陌生。

Continuation則是另一種函數調用方式。它不采用堆棧來保存上下文，而是把這些信息保存在continuation record中。這些continuation record和堆棧的activation record的區別在於，它不采用後入先出的線性方式，所有record被組成一棵樹（或者圖），從一個函數調用另一個函數就等於給當前節點生成一個子節點，然後把系統寄存器移動到這個子節點。一個函數的退出等於從當前節點退回到父節點。　

這些節點的刪除是由garbage collection來管理。如果沒有引用這個record，則它就是可以被刪除的。　

From callback to (Future -> Functor -> Monad)

Posted on 2015-04-07 Edited on 2024-11-15

From callback to (Future -> Functor -> Monad) 這篇寫得很好，雖然是用Javascript實做，不過還是值得一看。目前我的能力還不足以使用C++重寫一次，先用殘破的Javascipt來練習吧。

Callback

fs.readFile('...', function (err, data) {
  if (err) throw err;
    ....
});

這就是continuation-passing style。最大的問題就是nested callback之後，整個程式碼雜亂無章，難以維護。因此想了很多方法來改善流程。

Future

現在各大語言都有Future跟Promise了，Javascript的版本可以參考上面那篇文章的實做。

Introduction to JIT

Posted on 2015-03-22 Edited on 2024-11-15 In C , c++ , JIT

這邊是參考How to JIT - an introduction和Hello, JIT World: The Joy of Simple JITs 的感想。

Sample Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

// Allocates RWX memory of given size and returns a pointer to it. On failure,
// prints out the error and returns NULL.
void* alloc_executable_memory(size_t size) {
  void* ptr = mmap(0, size,
                   PROT_READ | PROT_WRITE | PROT_EXEC,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (ptr == (void*)-1) {
    perror("mmap");
    return NULL;
  }
  return ptr;
}

void emit_code_into_memory(unsigned char* m) {
  unsigned char code[] = {
    0x48, 0x89, 0xf8,                   // mov %rdi, %rax
    0x48, 0x83, 0xc0, 0x04,             // add $4, %rax
    0xc3                                // ret
  };
  memcpy(m, code, sizeof(code));
}

const size_t SIZE = 1024;
typedef long (*JittedFunc)(long);

// Allocates RWX memory directly.
void run_from_rwx() {
  void* m = alloc_executable_memory(SIZE);
  emit_code_into_memory(m);

  JittedFunc func = m;
  int result = func(2);
  printf("result = %d\n", result);
}