2017年1月7日 星期六

三個願望一次滿足的 libdispatch (Grand Central Dispatch) (revised ver)

這篇也是先前在臉書網誌上發表的, 今年再修正一下相關的 issue
====
不可否認, 儘管 POSIX thread 存在已久, 但是其 Programming Model 並不容易讓一般 coder 能夠輕鬆駕馭, 而中間衍生的 data structure 與 interface 也讓許多人頭疼, 然而享有多核平台的好處, 使用 thread 又是必要的.
而綜觀 thread 的用途大致有三:
  1. 利用 thread 來利用多核加速 (這也是多數其他 framework 專注的地方)
  2. timer background worker 實作
  3. event multiplexing (用以透過 handler 處理各式 event, 像是 blocked I/O )
Apple 於 2009 年以 Apache License 釋出了 Grand Central Dispatch (GCD) 的原始碼, 透過其 framework 搭配 blocks 的使用, 能一致性地處理上述三個面向的問題。時至今日, 儘管數年過去了, 個人認為 GCD/libdispatch 依然是設計上最出眾的 multi-thread framework.
在 Apple 釋出後不久, 在開放社群的努力下有了 FreeBSD port, 而 Linux 平台上也因Mark Heily的 OpenGCD 專案, 使得 Linux 平台也能夠使用 libdispatch, 在一般 Linux 上, 像是 ubuntu 已有現成包好的 package, 可以透過下列指令安裝
sudo apt-get install libdispatch-dev
然而對於 Linux 平台上的 package, 多數較為老舊 svn197, 若需要比較新的版本可以去官方的 github 抓取最新的 svn685 版本編譯使用

但對於Android 平台上, 若想要使用, 我們可以透過 PSPDFKit-labs 的移植搭配 NDK
以下列步驟來編譯 svn197 版

1. 請於確認與設定好環境具有 NDK, git 
2. 建立 libdispatch 工作目錄與 子目錄 jni
$ mkdir -p libdispatch/jni; cd libdispatch/jni
libdispatch

3. 於 jni 目錄下自 PSPDFKit-labs 抓取 blocksruntime, libkqueue 與 libdispatch
$ git clone https://github.com/PSPDFKit-labs/blocksruntime.git
$ git clone https://github.com/PSPDFKit-labs/libkqueue.git
$ git clone https://github.com/PSPDFKit-labs/libdispatch.git
 4. 於 jni 下建立 Android.mk 與 Application.mk 內容如下

Application.mk
#APP_ABI := armeabi-v7a
APP_ABI := arm64-v8a

Android.mk:
LOCAL_PATH := $(call my-dir)
include $(CLEAR_VARS)
LOCAL_MODULE := blocksruntime
LOCAL_C_INCLUDES := $(LOCAL_PATH)/blocksruntime
LOCAL_SRC_FILES     := \
    blocksruntime/BlocksRuntime/data.c \
    blocksruntime/BlocksRuntime/runtime.c
include $(BUILD_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libkqueue
LOCAL_C_INCLUDES := \
    $(LOCAL_PATH)/libkqueue/src/common \
    $(LOCAL_PATH)/libkqueue/android \
    $(LOCAL_PATH)/libkqueue/include
LOCAL_CFLAGS := -std=c99 -D_XOPEN_SOURCE=600 -fvisibility=hidden -DCLANG_TLS_WORKAROUND
LOCAL_SRC_FILES    := \
    libkqueue/src/common/filter.c \
    libkqueue/src/common/knote.c \
    libkqueue/src/common/map.c \
    libkqueue/src/common/kevent.c \
    libkqueue/src/common/kqueue.c \
    libkqueue/src/posix/platform.c \
    libkqueue/src/linux/platform.c \
    libkqueue/src/linux/read.c \
    libkqueue/src/linux/write.c \
    libkqueue/src/linux/user.c \
    libkqueue/src/linux/vnode.c \
    libkqueue/src/linux/timer.c \
    libkqueue/src/posix/signal.c
include $(BUILD_STATIC_LIBRARY)

include $(CLEAR_VARS)
LOCAL_MODULE := libdispatch
LOCAL_C_INCLUDES := $(LOCAL_PATH)/libdispatch/android \
LOCAL_C_INCLUDES += $(LOCAL_PATH)/libdispatch/android/config \
    $(LOCAL_PATH)/libdispatch/ \
    $(LOCAL_PATH)/libdispatch/os \
    $(LOCAL_PATH)/libdispatch/private \
    $(LOCAL_PATH)/libkqueue/include \
    $(LOCAL_PATH)/libpwq/include \
    $(LOCAL_PATH)/blocksruntime/BlocksRuntime
LOCAL_CFLAGS := -fvisibility=hidden -momit-leaf-frame-pointer -fblocks -DHAVE_CONFIG_H
LOCAL_SRC_FILES    := \
    libdispatch/src/apply.c \
    libdispatch/src/benchmark.c \
    libdispatch/src/data.c \
    libdispatch/src/init.c \
    libdispatch/src/io.c \
    libdispatch/src/object.c \
    libdispatch/src/once.c \
    libdispatch/src/queue.c \
    libdispatch/src/semaphore.c \
    libdispatch/src/source.c \
    libdispatch/src/time.c \
    libdispatch/src/transform.c

ifeq ($(TARGET_ARCH_ABI),x86_64)
LOCAL_CFLAGS += -DHAVE_GETPROGNAME
endif
ifeq ($(TARGET_ARCH_ABI),arm64-v8a)
LOCAL_CFLAGS += -DHAVE_GETPROGNAME
endif
ifeq ($(TARGET_ARCH_ABI),armeabi-v7a)
LOCAL_CFLAGS += -DHAVE_VALLOC
endif
LOCAL_STATIC_LIBRARIES  := blocksruntime libkqueue
include $(BUILD_SHARED_LIBRARY)
最後於 libdispatch 目錄下透過 ndk-build 指令即可編譯出 libdispatch.so

最後可以測試一下, 這裡我們小修改了, "你也可以寫 SIMD 比寫網頁快"的範例
以 8x8 為轉置單位
void transpose8x8(int *src, int *dst, int w, int h)
{
   
    int8 row0 = *((int8*)(src)); src+=w;
    int8 row1 = *((int8*)(src)); src+=w;
    int8 row2 = *((int8*)(src)); src+=w;
    int8 row3 = *((int8*)(src)); src+=w;
    int8 row4 = *((int8*)(src)); src+=w;
    int8 row5 = *((int8*)(src)); src+=w;
    int8 row6 = *((int8*)(src)); src+=w;
    int8 row7 = *((int8*)(src));
   
    int8 tmp0, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7;
    tmp0 = (int8){row0.s0, row1.s0, row2.s0, row3.s0, row4.s0, row5.s0, row6.s0, row7.s0};
    tmp1 = (int8){row0.s1, row1.s1, row2.s1, row3.s1, row4.s1, row5.s1, row6.s1, row7.s1};
    tmp2 = (int8){row0.s2, row1.s2, row2.s2, row3.s2, row4.s2, row5.s2, row6.s2, row7.s2};
    tmp3 = (int8){row0.s3, row1.s3, row2.s3, row3.s3, row4.s3, row5.s3, row6.s3, row7.s3};
    tmp4 = (int8){row0.s4, row1.s4, row2.s4, row3.s4, row4.s4, row5.s4, row6.s4, row7.s4};
    tmp5 = (int8){row0.s5, row1.s5, row2.s5, row3.s5, row4.s5, row5.s5, row6.s5, row7.s5};
    tmp6 = (int8){row0.s6, row1.s6, row2.s6, row3.s6, row4.s6, row5.s6, row6.s6, row7.s6};
    tmp7 = (int8){row0.s7, row1.s7, row2.s7, row3.s7, row4.s7, row5.s7, row6.s7, row7.s7};
   
    *((int8*)(dst)) = tmp0; dst+=h;
    *((int8*)(dst)) = tmp1; dst+=h;
    *((int8*)(dst)) = tmp2; dst+=h;
    *((int8*)(dst)) = tmp3; dst+=h;
    *((int8*)(dst)) = tmp4; dst+=h;
    *((int8*)(dst)) = tmp5; dst+=h;
    *((int8*)(dst)) = tmp6; dst+=h;
    *((int8*)(dst)) = tmp7;
}

void gcd_transpose(dispatch_queue_t queue, dispatch_group_t group, int *src, int *dst, int w, int h)
{
    for(int x = 0; x < w; x+=8){
        dispatch_group_async(
            group,
            queue,
            ^{

                for(int y = 0; y < h; y+=8){
                    transpose8x8(src+y*w+x, dst+x*h+y, w, h);
                }
            }
        );

    }
    dispatch_group_wait(group, DISPATCH_TIME_FOREVER);
}
而 gcd_transpose 的使用方式如下
        dispatch_group_t group = dispatch_group_create();
        dispatch_queue_t queue = dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH,NULL);
        gcd_transpose(queue, group, src, out1, TEST_W, TEST_H);
        dispatch_release(group);
        dispatch_release(queue);
編譯的方式
* Ubuntu
clang -O3 -fblocks -mavx -mfma -o test test.c -ldispatch -lBlockRuntime
* Android 請使用以上產生的 libdispatch.so 置於 test 的 jni 下, 並於 Android.mk 加入
LOCAL_LDLIBS := -L$(LOCAL_PATH) -ldispatch
個人在 i7-3612QM 上, 速度為單核 1.5X.
Android 上曾以此於 Nexus 9 (四核平台)上做過 memory copy 的測試,  為單核 2.7X.

儘管對 multi-threading programming 熟稔的人使用 libdispatch 與直接使用 pthread 差異落差會感覺其實還好, 但可以觀察到藉由使用 Blocks 的方式, 能夠省去建構用以傳遞各 thread 執行所需資訊的資料結構之必要, 而由於 loop 中的變數值更可以直接取值使用, Blocks 這樣的特性使得執行流程簡潔又同時具有效能的延伸性. 另外在 Android N 之後預設使用 clang 編譯, 即能同夠使用 libdispatch 與 Blocks 來寫出更簡潔好讀兼顧效率的程式碼。
延伸閱讀:
 1. Grand Central Dispatch Reference (PDF, Apple Website
2. libdispatch tutorial (timer usage) 
3. Grand Central Dispatch In-Depth PartI, PartII 
4. Directory Monitoring and GCD (event handle) 

沒有留言:

Lookup Table 在 NEON 中的處理

在 SIMD Programming 中由於希望能夠每個 lane 有一致的行為, 因此有一些事情是不容易達到的 而 Lookup Table (LUT) 即是其中之一 但若是特定條件之下, 還是有可能透過 NEON 加速 而這個 直接前提是 8bit LUT (當然...