怎么用向量指令计算多个元素尾部 0 的个数?

大家都知道 gcc 提供了__builtin_ctz 这种内建函数计算整数尾部 0 的个数,它在大部分情况下会转译成 CPU 的内建指令,比如 x86 平台上的 tzcnt 指令。

但如果你想同时计算多个元素尾部 0 的个数,就会发现有些指令集,比如 SSE/AVX,并没有提供类似的向量指令。而这种指令有时候在写向量化代码时又是需要的,我自己针对 8-bits 单字节整数做了一些粗糙的实现,如果你通过搜索引擎来到这里,希望对你能有所帮助。

函数功能

输入一个整数向量(16 或者 32 个 uint8),返回一个同类型整数向量,其中输出的每一个整数表示对应位置输入整数末尾 0 的个数。

SSE 版本

#include <smmintrin.h>
__m128i tzcnt_epi8(__m128i a) {
    __m128i ctz_table = _mm_setr_epi8(
        4, 0, 1, 0, 2, 0, 1, 0,
        3, 0, 1, 0, 2, 0, 1, 0
    );
    __m128i shuffle_mask = _mm_set1_epi8(0x0F);
    __m128i v_4 = _mm_set1_epi8(0x4);
    __m128i a_low = _mm_and_si128(a, shuffle_mask);
    __m128i ctz_low = _mm_shuffle_epi8(ctz_table, a_low);
    __m128i a_high = _mm_and_si128(_mm_srli_epi16(a, 4), shuffle_mask);
    __m128i ctz_high = _mm_shuffle_epi8(ctz_table, a_high);
    ctz_high = _mm_and_si128(ctz_high, _mm_cmpeq_epi8(ctz_low, v_4));
    return _mm_add_epi8(ctz_low, ctz_high);
}

AVX 版本

#include <immintrin.h>
__m256i tzcnt_epi8(__m256i a) {
    __m256i ctz_table = _mm256_setr_epi8(
        4, 0, 1, 0, 2, 0, 1, 0,
        3, 0, 1, 0, 2, 0, 1, 0,
        4, 0, 1, 0, 2, 0, 1, 0,
        3, 0, 1, 0, 2, 0, 1, 0
    );
    __m256i shuffle_mask = _mm256_set1_epi8(0x0F);
    __m256i v_4 = _mm256_set1_epi8(0x4);
    __m256i a_low = _mm256_and_si256(a, shuffle_mask);
    __m256i ctz_low = _mm256_shuffle_epi8(ctz_table, a_low);
    __m256i a_high = _mm256_and_si256(_mm256_srli_epi16(a, 4), shuffle_mask);
    __m256i ctz_high = _mm256_shuffle_epi8(ctz_table, a_high);
    ctz_high = _mm256_and_si256(ctz_high, _mm256_cmpeq_epi8(ctz_low, v_4));
    return _mm256_add_epi8(ctz_low, ctz_high);
}

NEON 版本

#include <arm_neon.h>
uint8x16_t vctzq_u8(uint8x16_t a) {
    return vclzq_u8(vrbitq_u8(a));
}

用 ARM NEON 实现 _mm_movemask_epi8 的几种方法

背景

上一篇文章中描述了一种使用 SIMD 指令进行并行查找的 B16 哈希表,我让它支持 ARM 时遇到了一些指令集兼容的问题,对这个问题小小地探索了一下。

SSE2 指令集提供了 _mm_movemask_epi8 (pmovmskb) 指令,作用是取所有 8 bit 操作数最高 bit,然后把它们存储到返回值里。对包含 16 个 8 bit 数的 128 bit 输入,取得高位 16 个 bit,存入 32 位的返回值里,并且将返回值的高位置 0。

但是在 ARM 的指令集中,没有这条指令,只能想其它办法替代。

已有实现

通过搜索,找到这个 StackOverflow 问题的回答,里面提到了四种实现方法,我整理了一下接口,分列如下:

// Yves Daoust 的回答 (7 votes): 与 _mm_movemask_epi8 略有不符,要求输入的每个 8 bits 全 0 或全 1
inline uint32_t vmovemask_u8_YvesDaoust(uint8x16_t a) {
    const uint8_t __attribute__ ((aligned (16))) _Powers[16]=
        { 1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128 };
    // Set the powers of 2 (do it once for all, if applicable)
    uint8x16_t Powers= vld1q_u8(_Powers);
    // Compute the mask from the input
    uint64x2_t Mask= vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(vandq_u8(a, Powers))));
    // Get the resulting bytes
    uint32_t Output;
    vst1q_lane_u8((uint8_t*)&Output + 0, (uint8x16_t)Mask, 0);
    vst1q_lane_u8((uint8_t*)&Output + 1, (uint8x16_t)Mask, 8);
    return Output;
}
​
// David 对 Yves Daoust 回答最后三行进行了一些改进
inline uint32_t vmovemask_u8_David(uint8x16_t a) {
    const uint8_t __attribute__ ((aligned (16))) _Powers[16]=
        { 1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128 };
    // Set the powers of 2 (do it once for all, if applicable)
    uint8x16_t Powers= vld1q_u8(_Powers);
    // Compute the mask from the input
    uint64x2_t Mask= vpaddlq_u32(vpaddlq_u16(vpaddlq_u8(vandq_u8(a, Powers))));
    // Get the resulting bytes
    uint32_t Output = vgetq_lane_u64(Mask, 0) + (vgetq_lane_u64(Mask, 1) << 8);
    return Output;
}
​
// EasyasPi 的回答(4 votes): 标准实现了 _mm_movemask_epi8,被 simde 库采纳,link:
// https://github.com/simd-everywhere/simde/blob/master/simde/x86/sse2.h
inline uint32_t vmovemask_u8_EasyasPi(uint8x16_t input)
{
    // Example input (half scale):
    // 0x89 FF 1D C0 00 10 99 33
    // Shift out everything but the sign bits
    // 0x01 01 00 01 00 00 01 00
    uint16x8_t high_bits = vreinterpretq_u16_u8(vshrq_n_u8(input, 7));
    // Merge the even lanes together with vsra. The '??' bytes are garbage.
    // vsri could also be used, but it is slightly slower on aarch64.
    // 0x??03 ??02 ??00 ??01
    uint32x4_t paired16 = vreinterpretq_u32_u16(vsraq_n_u16(high_bits, high_bits, 7));
    // Repeat with wider lanes.
    // 0x??????0B ??????04
    uint64x2_t paired32 = vreinterpretq_u64_u32(vsraq_n_u32(paired16, paired16, 14));
    // 0x??????????????4B
    uint8x16_t paired64 = vreinterpretq_u8_u64(vsraq_n_u64(paired32, paired32, 28));
    // Extract the low 8 bits from each lane and join.
    // 0x4B
    return vgetq_lane_u8(paired64, 0) | ((uint32_t)vgetq_lane_u8(paired64, 8) << 8);
}
​
// inspirit 的回答 (1 vote): 标准实现了 _mm_movemask_epi8,但分了上下半边,指令很多
inline uint32_t vmovemask_u8_inspirit(uint8x16_t input)
{
    const int8_t __attribute__ ((aligned (16))) xr[8] = {-7,-6,-5,-4,-3,-2,-1,0};
    uint8x8_t mask_and = vdup_n_u8(0x80);
    int8x8_t mask_shift = vld1_s8(xr);
​
    uint8x8_t lo = vget_low_u8(input);
    uint8x8_t hi = vget_high_u8(input);
​
    lo = vand_u8(lo, mask_and);
    lo = vshl_u8(lo, mask_shift);
​
    hi = vand_u8(hi, mask_and);
    hi = vshl_u8(hi, mask_shift);
​
    lo = vpadd_u8(lo,lo);
    lo = vpadd_u8(lo,lo);
    lo = vpadd_u8(lo,lo);
​
    hi = vpadd_u8(hi,hi);
    hi = vpadd_u8(hi,hi);
    hi = vpadd_u8(hi,hi);
​
    return ((hi[0] << 8) | (lo[0] & 0xFF));
}

我的实现

看到上面这几个方法,我就在想,有没有可能找到一种更高效的实现,用更少的 ARM 指令实现这个功能?经过一段时间的思考,我想到了下面这种方法,我感觉这(可能)是指令数最少的一种实现了。

但这个方法和 YvesDaoust 的方法一样,假设每个 8 bits 都是全 0 或者全 1,这在处理向量比较指令(vceq*, vcgt* 等)结果时是可用的,但在其它场景下未必可用。

 // (可能是)指令数最少的实现,要求输入的每个 8 bits 全 0 或全 1
inline uint32_t vmovemask_u8_solrex(uint8x16_t a) {
    // 先取出相邻两个 uint8 的中间 2 bits,1 bit 属于高 uint8,1 bit 属于低 uint8
    uint16x8_t MASK =  vdupq_n_u16(0x180);
    uint16x8_t a_masked = vandq_u16(vreinterpretq_u16_u8(a), MASK);
    // 再将这 8 个 2 bits 按照不同的偏移进行 SHIFT,使得它们加一起能表示最终的 mask
    const int16_t __attribute__ ((aligned (16))) SHIFT_ARR[8]= {-7, -5, -3, -1, 1, 3, 5, 7};
    int16x8_t SHIFT = vld1q_s16(SHIFT_ARR);
    uint16x8_t a_shifted = vshlq_u16(a_masked, SHIFT);
    // 最后把这 8 个数字加起来
    return vaddvq_u16(a_shifted);
}

性能测试

我非常好奇新方法性能如何,所以我对以上几种方法都进行了 benchmark,然后发现结果跟我想的有点不一样:

方法重复处理单变量按序处理数组
vmovemask_u8_YvesDaoust()536us531us
vmovemask_u8_David()189us208us
vmovemask_u8_EasyasPi()92us340us
vmovemask_u8_inspirit()286us389us
vmovemask_u8_solrex()137us166us
表1:内联函数调用,重复 10 万次

分析

重复处理单变量场景下,对一个固定的 uint8x16_t 变量重复计算 movemask,然后把结果累加起来(避免被优化)。这时候,vmovemask_u8_EasyasPi()胜出。这可能是因为 EasyasPi 的方法只有数值计算,没有寄存器 load,而往往 load/store 指令的耗时是比较长的。

按序处理数组场景下,对一个 10 万个元素数组的每个元素计算 movemask,然后把结果累加起来(避免被优化)。这时候,vmovemask_u8_solrex() 胜出。这可能是因为新方法里的 load 操作与数组元素的 load 操作形成了一定的流水线效果,load 的开销被抵消后,指令数少的性能优势就体现出来了。

从与 _mm_movemask_epi8 接口的一致性来说,还是 EasyasPi 给的实现更合适,所以 simde 库在替换 x86 intrinsics 时也用了这个实现。但探索一下不同的实现,还是能让人对向量指令设计和选择更多一些理解。

最后说回哈希表里 SIMD 并行比较的实现,其实 Facebook F14 里的实现更高效,并没有受 movemask 的思路限制,感兴趣的同学可以自己钻研一下。

2025年12月30日刷新

前两天在知乎上有同学评论了另一种实现,我又重新 benchmark 了一下。可能由于我之前的测试环境是 Mac 下的 ARM Docker,指令的执行效率太低,在新版 MBP 的 M3 芯片上执行时的结论和之前有显著不同。

WebAssembly 实现

 inline uint32_t vmovemask_u8_webasm(uint8x16_t a) {
    static const uint8x16_t mask = {1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16, 32, 64, 128};
    uint8x16_t masked = vandq_u8(mask, (uint8x16_t)vshrq_n_s8(a, 7));
    uint8x16_t maskedhi = vextq_u8(masked, masked, 8);
    return vaddvq_u16((uint16x8_t)vzip1q_u8(masked, maskedhi));
}

由于我以前的性能测试代码已不可考,所以我重写了一遍 benchmark 代码,并提交到 github:solrex/demo/cppdemo/arm_movemask_epi8.cpp,在我的 MacBook Pro M3 芯片下测试结果如下:

方法重复处理单变量按序处理数组
vmovemask_u8_YvesDaoust()0.76ns0.76ns
vmovemask_u8_David()0.78ns0.76ns
vmovemask_u8_EasyasPi()0.77ns0.76ns
vmovemask_u8_inspirit()1.03ns1.02ns
vmovemask_u8_solrex()0.77ns0.75ns
vmovemask_u8_webasm()0.75ns0.74ns
表2:内联函数调用 100万次

从这个性能测试结果来看,好像使用哪种实现区别已经不大了。那就别计较了,还是使用与 _mm_movemask_epi8 语义完全一致的实现吧,例如 vmovemask_u8_EasyasPi 或者 vmovemask_u8_webasm。

JS Bridge API - 安卓和iOS统一设计探讨

1 背景

APP 开发过程中,为了追求开发效率、更新成本、性能和交互体验的平衡,经常会采取 Hybrid 的 APP 端架构。用基于 HTML5 的 WEB APP 实现易变的业务部分,用原生代码实现对效率、权限、数据交换等有要求的功能部分,然后通过 JS Bridge 打通两者,实现 JS 与 原生代码的相互调用,完成整个产品功能。

但谈到 APP 开发,大家都知道至少存在两个平台,那就是 Android 和 iOS。这两个系统采取不同的原生开发语言,也有不同的 Webview 浏览器环境。但 WEB APP 是跨平台的,所以跨浏览器的调用总归需要在一个层面上得到统一,这样才不需要专门针对两个平台开发不同的 WEB APP。

下面先对在目前的技术框架下有哪些 JS - NA 相互调用方式做一下综合介绍,然后基于上述技术提出几种跨平台 JS Bridge API 统一设计思路,最后扩展讨论下 JS Bridge 设计中的一些值得注意的点。

2 在原生代码中调用 JS 代码

2.1 Android Platform

loadUrl 方法

Android Webview 的 loadUrl 接口,可以直接在 Java 代码中执行 Javascript 脚本。在 API 23(Android 6.0)及之前,这里的 Javascript 脚本能够获取当前加载页面的变量,甚至执行当前加载页面里定义好的函数。也就是说,传入的 JS 脚本是在当前加载页面的上下文中执行的。

    // Javascript: 在网页内定义一个函数,显示一个消息,返回一个内容
    function propose(msg) {
      alert(msg);
      return "Yes!";
    }

    // Java: 执行当前加载页面中定义好的一个函数 propose()
    webView.loadUrl("javascript:propose('Will you merry me?');");

可惜的是,这种方法:

  • 只能执行 JS,无法获取返回结果,需要用其它的方式(下文介绍)获取返回结果;
  • 而且会触发一次页面的刷新,可能会导致焦点丢失,软键盘消失之类的问题;
  • 在 Android 7.0 以后,存在兼容性问题;

evaluateJavascript 方法

不过,如果 APP 适配的版本在 API 19(Android 4.4)以后,也可以使用 Webview 的 evaluateJavascript 接口 。这也是更为推荐的做法,因为避免了上面 loadUrl 的问题。

    // Java: 执行当前加载页面中定义好的一个函数 propose()
    webView.evaluateJavascript("propose('Will you merry me?')", new ValueCallback() {
      @Override
      public void onReceiveValue(String answer) {
        // 拿到 answer 是 "Yes!"
      }
    });

间接方法:Web Event 分发

这种方法很少有人提到,因为它是一种间接的调用方法。Web Event 接口提供了一种在 DOM 里进行广播的机制,那也就意味着原生代码可以不知晓 JS 的函数名,而只是广播一个事件,由页面内的 JS 决定是否处理这个 Event。这能够避免 JS 代码执行的异常,更常用于原生代码主动通知页面某些信息更新的场景。

    // Javascript: 在网页内定义一个函数,显示一个消息,返回一个内容
    function propose(e) {
      alert(e.msg);
      return "Yes!";
    }
    // 注册 WebDomEvent handler
    window.addEventListener("propose_event", propose);
    // Java: 
    webView.evaluateJavascript("var e=new Event('propose_event'); e.msg='Will you merry me?'; window.dispatchEvent(e);", new ValueCallback() {
      @Override
      public void onReceiveValue(String answer) {
        // nothing
      }
    });

这种方法也存在无法获取返回结果的问题,也需要用其它的方式(下文介绍)获取返回结果。不过在使用到 Event 通知的场景下,我们一般也不需要返回。

2.2 iOS Platform

讲到 iOS,必须提到两个不同的 WebView,一个是过时但广泛使用的 UIWebView,另一个是建议且逐渐流行的 WKWebView。

UIWebView: stringByEvaluatingJavaScriptFromString 方法

UIWebView 提供了 stringByEvaluatingJavaScriptFromString 接口 ,并且能够获得返回结果。

    // OC: 执行当前加载页面中定义好的一个函数 propose()
    [_webView stringByEvaluatingJavaScriptFromString:@"propose('Will you merry me?')"];

这个方法的主要问题在于,它是一个同步的方法。它可能会阻塞 UI 线程,不太适合执行复杂的调用。

UIWebView: JavaScriptCore

在 iOS 7 之后,苹果提供了一个获取 UIWebView 中 JSContext 的方法,直接将 JS 执行环境暴露给原生代码。这样就可以在原生代码中任意执行 JS 代码了。同时,这个接口也可以用于 JS 调用原生代码的能力,下文中会介绍。

    // OC: 获取 JSContext 
    JSContext *context = [_webView valueForKeyPath:@"documentView.webView.mainFrame.javaScriptContext"]
    [context evaluateScript:@"propose('Will you merry me?')"];

WKWebView: evaluateJavaScript 方法

可以看到,JavaScriptCore 使用起来极其方便,但在 WKWebView 中我们享受不到这种方便了。因为 WKWebView 的页面渲染是在独立的进程中,在当前进程无法直接拿到 JSContext。

不过 WKWebView 提供了一个更好的 evaluateJavaScript 接口 ,可以传入一个回调函数,实现了 JS 的异步调用。

    // OC: 执行当前加载页面中定义好的一个函数 propose() 
    [_webView evaluateJavaScript:@"propose('Will you merry me?')" completionHandler:^(id _Nullable result, NSError * _Nullable error) {
      // 拿到 result 是 "Yes!", error 是 nil
    }];

可以看到,evaluateJavaScript 接口与上文 Android evaluateJavaScript 接口极为类似。

间接方法:Web Event 分发

当然,由于 Event 接口是 WEB 标准,iOS 上也可以同样进行 Event 分发。场景和作用请看上文,不再赘述,简单代码如下:

    // Javascript: 在网页内定义一个函数,显示一个消息,返回一个内容
    function propose(e) {
      alert(e.msg);
      return "Yes!";
    }
    // 注册 WebDomEvent handler
    window.addEventListener("propose_event", propose);
    // OC: 执行当前加载页面中定义好的一个函数 propose() 
    [_webView evaluateJavaScript:@"var e=new Event('propose_event'); e.msg='Will you merry me?'; window.dispatchEvent(e);" completionHandler:^(id _Nullable result, NSError * _Nullable error) {
      // nothing
    }];

3 在 JS 代码中调用原生代码

3.1 Android Platform

addJavascriptInterface 方法

Android 从 API 1 就开始提供了 addJavascriptInterface 接口,用这个接口可以很方便地把原生的方法注入到 JS 上下文中,可以说比 iOS 做得好很多。

    // Java: 定义一个类,提供一个接口,返回一个内容
    class NativeApis {
      @JavascriptInterface
      public String propose(String msg) {
        return "Yes!";
      }
    }
    webView.addJavascriptInterface(new NativeApis(), "Bridge");
    // Javascript: 执行一个 native 的方法
    alert(window.Bridge.propose("Will you merry me?"));

但问题在于在 API 17 (Android 4.2) 之前这个方法存在安全漏洞,攻击者可以执行任意代码。在 API 17 及以后,通过显式地给出 @JavascriptInterface 限定暴露的接口,避免了安全漏洞。但在 API 17 以前,不建议使用此方法,可以考虑下面的 work around。

URL 拦截:shouldOverrideUrlLoading

这是一种曲线救国的方式,那就是通过加载非标准 Scheme( 非 http/s, 非 ftp)的 URL,用一个非法(或者叫自定义)的 URL 传递参数。当页面中的 Javascript 动态插入一个 iframe 元素时,iframe 的 url 会被 WebView 通过 shouldOverrideUrlLoading 方法传给 WebViewClient 判断是否需要加载该 URL。在这里可以拦截自定义的 URL Scheme,通过 encode 到 URL 中的信息传递参数。

    // Java: 解析要加载的 URL,如果是自定义 scheme,调用相关的函数
    class MyWebViewClient extends WebViewClient {
      @Override
      public boolean shouldOverrideUrlLoading(WebView view, String url) {
        if (url.startsWith("bridge://")) {
          // 解析 // 后面的 action 和参数,调用相关的函数
        }
        return true;
      }
    }
    webView.setWebViewClient(new MyWebViewClient());
    // Javascript: 用不可见 iframe 打开一个自定义 URL,参数需要 urlencode
    bridgeFrame = document.createElement('iframe');
    bridgeFrame.style.display = 'none';
    bridgeFrame.src = 'bridge://propose?msg=Will%20you%20merry%20me%3F';
    document.documentElement.appendChild(bridgeFrame);

URL 拦截的问题也是无法直接拿到原生代码的返回结果,需要用 URL 字符串参数传入一个回调函数,然后用上文讲到的原生代码调用 JS 的方式回调传回结果。

弹出框拦截

Android Webview 可以定义一些接口,重载 onJsAlert()、onJsConfirm()、onJsPrompt() 这些回调方法。当 JS 控制弹出框时,这些回调会被调用,进而可以通过约定的特殊内容格式判断是真正的弹出框,还是 JS 到 NA 的调用。由于 onJsPrompt 可以返回结果,所以更合适一些。

    // Java: 重载 onJsPrompt 方法,提取 prompt 内容判断是否需要拦截
    class MyWebViewClient extends WebChromeClient {
      @Override
      public boolean onJsPrompt(WebView view, String url, String message, String defaultValue, JsPromptResult result) {
        if (message.startsWith("bridge://")) {
          // 解析 // 后面的 action 和参数,调用相关的函数
          result.confirm("Yes!");
        }
        return true;
      }
    }
    webView.setWebViewClient(new MyWebViewClient());
    // Javascript: 调用 prompt 弹框,使用特定内容格式以利于拦截
    alert(window.prompt('bridge://propose?msg=Will%20you%20merry%20me%3F'));

Local Server

APP 可以在手机的本地地址 127.0.0.1 上启动一个 HTTP/WebSocket 服务,浏览器内的 JS 可以通过本地回环网络连接到这个服务,把 APP 视为一个服务端,进行正常的 B/S 通信,也可以实现在 JS 中调用原生代码。

使用这种方式时,额外注意一点是要进行有效地鉴权。因为除了 APP 内的 WebView,手机内其它的 APP 也可以访问这个服务,很可能会造成一些安全问题。所以可能需要 NA 在加载 Webview 的时候,通过 Cookie/URL参数/JS 上下文环境传入合法的 Token,才能保证其安全性。

还有一点是,如果不幸出现了端口冲突,需要有办法去解决。

3.2 iOS Platform

URL 拦截:shouldStartLoadWithRequest

UIWebView 原生并没有提供任何可以在 JS 代码中调用 NA 方法的 API,但 UIWebView 也可以通过与 Android 相同的方式进行 URL 拦截,进而间接实现 JS 到 NA 的传参。

    // UIWebView
    - (BOOL)webView:(UIWebView *)webView 
    shouldStartLoadWithRequest:(NSURLRequest *)request 
     navigationType:(UIWebViewNavigationType)navigationType;

这个方式在 WKWebView 上,依然有效,只是叫做 decidePolicyForNavigationAction

    - (void)webView:(WKWebView *)webView 
    decidePolicyForNavigationAction:(WKNavigationAction *)navigationAction 
    decisionHandler:(void (^)(WKNavigationActionPolicy))decisionHandler;

UIWebview: JavaScriptCore

大概苹果官方也觉得这种方式太 ugly,所以后来在 iOS 7 以后,提供了一个好一些的接口,就是 JavaScriptCore。在页面加载完后,可以获取当前加载页面的 JavaScript 上下文执行环境 JSContext。然后可以把一些原生方法注入到 JSConext 中,这样页面内的 JS 就可以直接调用到这些注入的方法了。

    // OC: 获取 JSContext,将原生方法注入进去
    JSContext *context = [webView valueForKeyPath:@"documentView.webView.mainFrame.javaScriptContext"];
    context[@"propose"] = ^(msg) {
      return @"Yes!";
    };
    // Javascript: 调用 prompt 弹框,使用特定内容格式以利于拦截
    alert(window.propose('Will you merry me?'));

WKWebView: WKScriptMessageHandler 方法

然后到了 WKWebView,JSContext 不好使了。不过 WKWebView 提供了另外一个方法,那就是 WKScriptMessageHandler。在创建一个 WKWebView 的时候,可以通过配置将一个 WKScriptMessageHandler 对象指针和 NAME 传进去。这样在加载页面中,通过 window.webkit.messageHandlers.NAME.postMessage 就可以将消息传给原生的 WKScriptMessageHandler 对象。

    // OC: 编写 Message 回调,并注册 Message Handler
    @interface Brige : NSObject 
    - (void)userContentController:(WKUserContentController *)userContentController
          didReceiveScriptMessage:(WKScriptMessage *)message {
      if ([message.name isEqualToString:@"Bridge"]) {
        // 处理 message
      }
    }
    ...
    _bridge = [[Brige alloc] init];
    [[_webView configuration].userContentController addScriptMessageHandler:_bridge name:@"Bridge"];
    // Javascript: 发消息给注入的 Message Handler
    window.webkit.messageHandlers.Bridge.postMessage("Will you merry me?");

WKScriptMessageHandler 同样也是无法直接返回结果。

WKWebView: 弹出框拦截

与 Android 类似,WKWebView 也提供了弹出框的回调函数,可以通过此类函数实现参数的传递。

    // WKUIDelegate
    - (void)webView:(WKWebView *)webView 
    runJavaScriptAlertPanelWithMessage:(NSString *)message 
    initiatedByFrame:(WKFrameInfo *)frame 
    completionHandler:(void (^)(void))completionHandler;
    
    - (void)webView:(WKWebView *)webView 
    runJavaScriptConfirmPanelWithMessage:(NSString *)message 
    initiatedByFrame:(WKFrameInfo *)frame 
    completionHandler:(void (^)(BOOL result))completionHandler;
    
    - (void)webView:(WKWebView *)webView 
    runJavaScriptTextInputPanelWithPrompt:(NSString *)prompt 
        defaultText:(NSString *)defaultText 
    initiatedByFrame:(WKFrameInfo *)frame 
    completionHandler:(void (^)(NSString *result))completionHandler;

Local Server

见上文中对 Android Local Server 调用方式的讨论。

4 notify-fetch-run 间接机制

上文中讲到的很多还是较为直接的 JS-NA 相互调用方法,其实还有一些更开脑洞的方法。比如 notify-fetch-run 机制,不需要直接传递参数或者代码,只需要传递一个信号,然后通过可以共同访问的第三方传递真正的参数,进行执行。

4.1 notify

如果仅仅把相互调用简化成一个 0/1 信号,那除了上面讲到的内容,还有太多东西可以做为信号。比如 event,比如通过远程服务器通知之类,下面讲一个比较奇葩的方法:

notify 中的奇葩:online/offline event

HTML5 中有一对标准的 event,叫做 online/offline,可以反应当前浏览器的联网状况。而 WebView 呢,可以通过 webView.setNetworkAvailable() 来控制联网状态。那也就意味着,原生代码只要控制 webView 的联网状态变化,就可以发送 0/1 信号给 JS。JS 收到 0/1 信号后,可以通过下文 JS 调用原生的方式获取原生代码要传入的内容,然后执行这些内容。

这种方式最大的问题在于,需要非常精巧地设计整个状态流转。因为传入的信号信息量非常少,而且正常情况下网络状况的变化也会触发这两个 event。

4.2 fetch

fetch 也可以有很多种,只要是 JS 和 NA 都能访问到的目标,都可以做第三方信息交换。比如本地 socket,远端网站,或者本地文件 file://,或者 cookie,localstorage。

5 安卓 & iOS 统一 API

我们讨论 Android & iOS API 的统一,主要是在 JS 里的统一,因为只有 JS 是跨平台的。统一 API 有两种实现方法:

  • 一种是通过封装的统一,就是说 JS 与原生代码的底层通信方式是不同的,但通过一个嵌入 WebView 的 JS 库实现 API 的统一。
  • 另一种是无需封装的统一,也就是在底层通信的接口就保持了统一,在两端的 JS 代码上是完全一致的。

5.1 JS 调用原生代码

URL 拦截(Android & iOS)

从上文介绍的方法就可以直接看出,通过 URL 拦截实现 JS 调用原生代码是统一适用于所有平台的方法,而且没有版本限制。所以很多 JSBridge 都使用了这种方法以做到最大的兼容性。

    // Android Java: 解析要加载的 URL,如果是自定义 scheme,调用相关的函数
    class MyWebViewClient extends WebViewClient {
      @Override
      public boolean shouldOverrideUrlLoading(WebView view, String url) {
        Uri uri = Uri.parse(url);
        // FIXME 异常处理
        if (uri.getScheme().contentEquals("bridge")) {
          if (uri.getAuthority().contentEquals("propose")) {
            view.evaluateJavascript(uri.getQueryParameter("callback") + "('Yes!')", null);
          }
        } else {
          view.loadUrl(url);
        }
        return true;
      }
    }
    webView.setWebViewClient(new MyWebViewClient());
    // iOS OC: 解析要加载的 URL,如果是自定义 scheme,调用相关的函数
    - (BOOL)webView:(UIWebView*)webView shouldStartLoadWithRequest:(NSURLRequest*)request navigationType:(UIWebViewNavigationType)navigationType {
      NSURL * url = [request URL];
      if ([[url scheme] isEqualToString:@"bridge"] && [[url host] isEqualToString:@"propose"]) {
        NSArray *params =[url.query componentsSeparatedByString:@"&"];
        for (NSString *paramStr in params) {
          if ([paramStr hasPrefix:@"callback"]) {
            NSArray *kv = [paramStr componentsSeparatedByString:@"="];
            [webView stringByEvaluatingJavaScriptFromString:[kv[1] stringByAppendingString: @"('Yes!')"]];
          }
        }
        return NO;
      }
      return YES;
    }
    // 统一的 Javascript: 用不可见 iframe 打开一个自定义 URL,参数需要 urlencode
    bridgeFrame = document.createElement('iframe');
    bridgeFrame.style.display = 'none';
    bridgeFrame.src = 'bridge://propose?msg=Will%20you%20merry%20me%3F&callback=showResult';
    document.documentElement.appendChild(bridgeFrame);

这种方法的问题:

  1. 对 URL 格式有 UrlEncode 的要求,对于要传递复杂参数的情况不友好。比如我们需要在参数中传递一个正常的 URL,就需要对这个参数进行两次 UrlEncode,才能保证解码不出问题。
  2. 通过 iframe 打开 URL 的方式不太直观,也缺少调用成功的返回确认,需要在 JS 端再封装一下。

对象植入(Android & iOS UIWebView)

放宽兼容性限制,Android 不再兼容 4.1 及以前版本,iOS 不再兼容 iOS 6 及以前版本。那就可以直接通过 Android 的 addJavascriptInterface 和 iOS 的 JSContext 实现将要调用的方法以对象的方式注入到 JS 上下文中,同时也可以直接获得返回结果。

    // Android Java: 定义一个类,提供一个接口,返回一个内容
    class NativeApis {
      @JavascriptInterface
      public String propose(String msg) {
        return "Yes!";
      }
    };
    webView.addJavascriptInterface(new NativeApis(), "Bridge");
    // iOS OC: 定义一个类,提供一个接口,返回一个内容
    // *.h 
    #import 
    @protocol BrigeProtocol 
    - (NSString *)propose:(NSString *)msg;
    @end
    
    @interface Bridge : NSObject
    @end
    // *.m
    // 永远返回 Yes
    @implementation Bridge
    - (NSString *)propose:(NSString *)msg {
      return @"Yes!";
    }
    @end
    ...
      // 注意生命周期
      bridge = [[Bridge alloc] init];
    ...
      JSContext *context = [webView valueForKeyPath:@"documentView.webView.mainFrame.javaScriptContext"];
      context[@"Bridge"] = bridge;
    // 统一的Javascript: 执行一个 native 的方法
    showResult(window.Bridge.propose("Will you merry me?"));

对象植入(Android & iOS WKWebView)

如果使用 WKWebView,那就意味着进一步放宽了兼容性限制,因为 WKWebView 不支持 iOS 7 及以前版本。上文说到,WKWebView 不支持 JavaScriptCore,但提供了一个 WKScriptMessageHandler 方法。这也意味着我们只能将调用方式尽量往 WKWebView 的方式上统一。

WKWebView 注入的对象,只能使用 postMessage 接口,而且是注入到 window.webkit.messageHandlers 。虽然 Android 的 addJavascriptInterface 不能实现属性的注入,也就是说我们无法在原生代码中在 JS 上下文中添加一个 window.webkit.messageHandlers.NAME 这样一个对象。但我们可以在 WKWebView 中通过 addUserScript 注册一个加载页面时就执行的脚本,将 window.webkit.messageHandlers.NAME 赋给 window.NAME,就实现在注入对象层面的统一。即 Android 和 iOS 里的 Brige 对象都注入到了 window 下。

然后 Android addJavascriptInterface 注入的对象也实现一个与 WKWebView 类似的 postMessage 接口,那么两端就实现了底层接口上的统一。

    // Android Java: 定义一个类似于 WKScriptMessageHandler 的类
    class NativeApis {
      private WebView mWebView;
      public NativeApis(WebView webview) {
        mWebView = webview;
      }
      @JavascriptInterface
      public void postMessage(String msg) {
        try {
          JSONObject json_obj = new JSONObject(msg);
          final String callback = json_obj.getString("callback");
          // JS 是异步线程,转到 UI 线程执行 JS
          mWebView.post(new Runnable() {
            @Override
            public void run() {
              mWebView.evaluateJavascript( callback + "('Yes!')", null);
            }
          });
        } catch (JSONException e) {
          Log.i("Bridge", "postMessage: " + e.getMessage());
        }
      }
    };
    // 初始化 NativeApis 时多一个 webView 句柄
    webView.addJavascriptInterface(new NativeApis(webView), "Bridge");
    // iOS OC: 定义 WKScriptMessageHandler 处理接口
    - (void)userContentController:(WKUserContentController *)userContentController didReceiveScriptMessage:(WKScriptMessage *)message {
      // 解析 JSON,调用 callback 返回数据
      NSData *jsonData = [message.body dataUsingEncoding:NSUTF8StringEncoding];
      NSDictionary * msgBody = [NSJSONSerialization JSONObjectWithData:jsonData options:kNilOptions error:nil];
      NSString *callback = [msgBody objectForKey:@"callback"];
      [message.webView evaluateJavaScript: [NSString stringWithFormat:@"%@('Yes!')",
                                              callback] completionHandler:^(id _Nullable result, NSError * _Nullable error) {
        // FIXME 出错处理
      }];
    }
    ...
    [[_webView configuration].userContentController addScriptMessageHandler:self name:@"Bridge"];
    // 将 window.webkit.messageHandlers.Bridge 改名成 window.Bridge 与 Android 统一
    WKUserScript* userScript = [[WKUserScript alloc]initWithSource:@"if (typeof window.webkit != 'undefined' && typeof window.webkit.messageHandlers.Bridge != 'undefined') { window.Bridge = window.webkit.messageHandlers.Bridge;}" injectionTime:WKUserScriptInjectionTimeAtDocumentStart forMainFrameOnly:YES];
    
    [[_webView configuration].userContentController addUserScript:userScript];
    // 统一的Javascript: 给 Native 发送一个消息,通过回调返回结果
    message = {
      func: "propose",
      options : {
        msg: "Will you merry me?"
      },
      callback: showResult.name
    };
    window.Bridge.postMessage(JSON.stringify(message));

5.2 原生代码调用 JS

JS 调用原生代码,主要目的是为了增强 JS 的能力。而原生代码调用 JS 大部分情况下主要是为了便捷 JS 的调用,这可以分为三种情况:

  1. 主动设置上下文。每次加载页面必须执行一些 setup,将一些 JS 环境设置好,不需要每次都从服务器端获取。比如上文中讲到的 addUserScript 添加一个加载页面时的上下文环境。
  2. 主动发起与 JS 交互。在某些比较少见的场合下,原生代码可能想要主动将一些信息通知给 JS,尤其是一些不在官方 HTML5 支持能力的事件,比如语音的输入、扫码的结果、调用失败等等。
  3. 最常见的,是被动的回调 JS。也就是 JS 发起了一个调用,由于调用方式的限制无法返回,或者需要较长时间才能拿到结果,这就需要原生代码在执行完调用后通过回调回传给 JS。

主动设置上下文不需要 API 的统一。

主动发起与 JS 的交互场景比较少,可以有两种方法实现:一种是页面加载过程中将回调注册给 NA;另一种是通过 Web Event 的方式由 NA 广播给 JS 上下文。我们更建议通过 Web Event 的方式广播,这样不受页面加载状态之类的限制,交互上更简单。当然,也可以两种方法结合,增加一个 Event 到 NA 的注册,保证有效广播。

被动的回调 JS,实现上比较直观,只要在 JS 调用 NA 的接口中增加一个 callback 参数,NA 在完成之后回调记录下来的接口即可。

6 JS Bridge 设计上的更多考虑

6.1 是否使用第三方 JS Bridge 库

使用第三方 JS Bridge 库,理论上能避免很多烦恼,按照它的 step by step 指引,很容易就能配出来一个可以工作的 JS Bridge 环境。

但第三方库也有一些缺点。前面讲到,第三方库为了易用,往往在 NA 层和 JS 层都会做一套新的 Adapter API 封装,但不好意思的是,它提供的仍然是一套通用 API 封装,往往应用方还得在上面再封装一层业务 API。这也就意味着,每次 JS-NA 的调用,需要走下面的一套流程:

Created with Raphaël 2.2.0业务函数: proposeJS Adapter: 比如序列化参数等前面讲到的某种 Bridge 方法:比如 URL 拦截NA Adapter:比如某种路由机制原生函数

中间的三层是由第三方库实现的。如果不熟悉第三方库的代码,或者说第三方库在这三层做了过重的封装,那调试问题就会非常困难。

我上文讲到无需二次封装的统一 API,就是希望通过选取合适的 Bridge 方法,把 JS Adapter 这一层去掉或者让它尽量地薄。这样整个调用过程能得到充分地简化,更便于问题的追查和整体的设计。

第三方库还有一个问题就是,它往往追求大而全。比如有些第三方库就是想非常完整地支持 Hybrid App 的设计,但很多时候我们往往仅需要有限个接口调用而已。为了实现有限地一些功能,还得去了解第三方库的整体设计,有时候代价也高了些。

6.2 参数约束

由于 Javascript 是弱类型的语言,而 Java 和 OC 都是强类型的,在参数的互相传递时,需要进行严格的检查。虽说 addJavascriptInterface 等方法可以动态地注入无数个对象或者方法,但仍然不建议这样做,因为维护成本太高。就像 URL 拦截一样,搭桥的路有一条就足够了。

JS Bridge 的接口,就像是一个 RPC 协议。这个 RPC 协议需要有一个版本,这样我们知道哪些版本有哪些 API,更利于有效地调用。这个 RPC 协议需要约定哪些固定的字段,这样我们可以用在入口统一校验字段是否完整,字段类型是否可用。

6.3 出错信息

跨平台的接口,很多时候 DEBUG 比较困难,尤其是上文讲到一些方式无法直接返回结果,自然也无法直接返回错误。所以在接口上,要尽量考虑出错时错误信息的回传通道,例如接口需要提供出错的 callback。

那么问题来了,如果 callback 参数也写错了怎么办?总不能让 FE 看 APP 的 log 吧?

所以建议在接口设计上,增加一个全局错误的 Web Event,就像 Linux 系统下的 errno。任何 JS 调用 NA 失败或者回调失败,都通过这个 Event 分发出去,这样前端就很容易知道错在哪里了。

6.4 API 安全性

虽然网页是在 APP 自己的 WebView 中打开的,但因为网页天然具有的超链接性质,也很难保证所有可以点开的页面都是可信的,比如有些时候活动的落地页可能会到第三方页面等。所以对一些影响 APP 运行逻辑的关键 API 接口,需要做站点的白名单控制,避免第三方站点调用此类 API。

7 总结

这篇文章列举了可用于 JS Bridge 的各平台技术实现,建议了几种无需二次封装的 Android & iOS 平台 JS Bridge 统一 API 的可选方案,讨论了设计一个简洁、规范、安全的 JS Bridge API 需要考虑的问题和解决思路。希望对读者能有所助益。

react-native-navigation 简单分析和跨页跳转

虽然 react-native-navigation 是 Facebook React Native 官方文档推荐的导航库之一 ,但我也不得不说使用它做 APP 导航主框架的体验简直糟糕透了。当然,这本身可能就是 React Native 自身的问题。

1 react-native-navigation 简单分析

使用 react-native-navigation 首先得理解下它的实现。它独立于 RN Component 的 componentWillMount/componentWillUnmount 接口实现了一套自己的事件机制,最重要的可能是 willAppear/willDisappear。它提供了一套页面堆栈操作和切换动画, push 可以将目标页面切换到最上方,pop 可以返回上一页。

可能是为了性能或者设计使然,push 的时候不会销毁当前页。也就是说,在 A 页面里 push 跳转到B 页面,不会 Unmount A 页面的Component。 不过在 B 页面 pop 回 A 页面时,的确会 Unmount B 页面的Component。这也意味着,整个导航路径是一个页面堆栈,只要在堆栈里页面的 Component,都不会被 Unmount。

2 页面堆栈的问题

这有时候会导致一些很严重的问题。有些情况下,特定的 Component 可能会占用唯一的系统资源,比如:麦克风、照相机等。这些 Component 在实现的时候往往只考虑了 React Native 的接口,在 componentWillUnmount 的时候释放占用的资源。它们不会预料到与 react-native-navigation 的结合,专门提供一个 willDisappear 时释放资源的接口,而且有些情况下也未必能这样做。

如果 A 页面在使用这些 Component 已经占用了麦克风或者相机,B 页面也要使用这些 Component,那么从 A push 跳转到 B 时,A 页面的资源不会被释放,B 页面就可能会遇到麦克风不可用,或者相机无法初始化等问题。

解决这个问题,最简单的办法是调整页面交互顺序,保证使用这些独占系统资源的页面永远在堆栈的最顶端,或者使用 Modal Stack,把独占资源的 Component 放到 Modal 里去 present 然后 dismiss。

3 跨页跳转实现

react-native-navigation 只能支持页面堆栈,而且看起来只能支持 push/pop 一个页面,也就是说整个切换过程是串行的,push 顺序是 A->B->A->D ,那么 pop 顺序也只能是 D->A->B->A。

但很可惜地是,在产品经理眼中,是不存在串行页面切换这种限制的。TA 们有时候要求跳转的过程中没 A,但返回的时候要有 A;或者要求跳转的过程中有 A,但返回的时候可以跳过 A,或者甚至直接返回到堆栈最底端。

直接返回栈底很容易,react-native-navigation 提供了 popToRoot 接口,但它没有提供一下子 push 多个页面,或者一下子 pop 多个页面的功能。它也没有类似于 HTML5 的 history API,我们直接对堆栈进行操作,是不太可能的。只能通过它现有的接口想办法。

3.1 跨页 push

跳转的过程没有 A,但返回的时候要有 A,这只是一个产品需求。在实现上,是可以变成跳转过程中有 A,但是 A 被快速跳过,返回的时候才会被真正渲染。这样从用户体验上来看,并没有看到 A。代码实现上,可以考虑两种方法:

willAppear 结合 didDisappear 做状态控制

在 A 的 state 里放一个 isFirstEntry 状态,默认是 truewillAppear 里判断 isFirstEntry 则直接跳转到下个页面,render 里判断 isFirstEntry 则只渲染一个背景 View ,否则才渲染正常页面。这样就实现了在页面切换过程中跳过 A。在 的 didDisappear 里将 isFirstEntry 置为 false 。这样在返回的时候 willAppearrender 表现就和正常返回一样了。

  willAppear = () => {
    if (this.state.isFirstEntry) {
      this.props.navigator.push(...);
      return;
    }
    ...
  };
  render() {
    if (this.state.isFirstEntry) {
      // 返回背景 View
    } else {
      // 返回正常 View
    }
  }
  didDisappear = () => {
    this.setState({isFirstEntry: false});
  };

willAppear 页面计数

在需要更复杂逻辑的地方,可以在 state 里放一个 appearTimes 计数器。在 willAppear 里给计数器加一,这样每次进入页面都会增加计数。通过判断计数器的值,来决定如何 render 或者跳转。

  willAppear = () => {
    this.setState({appearTimes: this.state.appearTimes + 1});
    if (this.state.appearTimes === 1) {
      this.props.navigator.push(...);
      return;
    }
    ...
  };
  render() {
    if (this.state.appearTimes === 1) {
      // 返回背景 View
    } else {
      // 返回正常 View
    }
  }

3.2 跨页 pop

跳转的过程中有 A,但返回的时候要跳过 A,相当于可以自己操作 pop 的步长。很遗憾,react-native-navigation 没有提供这样的接口。不过我们可以采用一个 trick 的手段,来实现这个逻辑。

假设从 Root->A->B,在 A 的 state 里放一个 relayPop ,默认是 false。 在 A 跳转到 B 时,通过 props 传入一个回调:setParentRelayPop,B 可以通过这个回调修改 A 的 state relayPoptrue; 在 A 的 willAppear 中,首先判断 relayPop 是否为真,如果是真的话,代表是从 B 返回且 B 要求接力返回,那么 A 就直接 pop 返回到 A 的上级。 B 在返回时,首先通过回调设置 relayPoptrue,然后再调用 pop 接口,就实现了跨页返回。

// Screen A
  willAppear = () => {
    if (this.state.relayPop) {
      this.props.navigator.pop();  // 接力返回
      return;
    }
    ...
  };
  ...
    // 跳转逻辑某处
    this.props.navigator.push({..., passProps: {
                                  setParentRelayPop: () => this.setState({relayPop: true}) 
                                }});
// Screen B
    // 返回逻辑某处
    this.props.setParentRelayPop();
    this.props.navigator.pop();

手机 APP 应该选用哪个加密算法 - 兼吐槽 TEA

很多 APP 产品都有通信加密的需求,一部分出于市场的要求,比如苹果对于“ATS”的强制性规定,一部分出于自身安全的考虑,比如对账号和密码的保护。这些需求大部分都可以用简单的 HTTP -> HTTPS 升级来搞定,而且几乎不用付出什么成本(除加解密的计算开支外),例如使用我之前文章介绍到的 Let's Encrypt 免费证书

但还有一类特殊的需求,HTTPS 解决不了,也就是防协议分析的需求。很多 APP 开发者应该知道,只要在手机里安装一个代理 CA 证书,就可以实现中间人攻击,通过代理软件抓到 HTTPS 包的明文内容。虽然这样的攻击很难在公开网络上进行,但对自己的手机进行抓包分析,作为 APP 和服务端通信的调试手段是被广泛使用的。

协议分析能做什么呢?可以猜想到一定的 APP 内部逻辑,可以对产品数据进行作弊攻击。举个例子:你的 APP 通过某个渠道进行推广,为了统计渠道安装、注册或者日活,你往往会在 APP 中埋一个点,当 APP 启动时,发送一些信息到服务器。如果这个协议被破解了,渠道商根本不需要真正进行推广,只需要构造一些假消息发送到你的服务器就行了。仅看数据你可能会以为这个渠道推广效果特别好,其实只是骗局而已。

这类情况下,就要求对敏感协议内容进行额外的数据保护。最常用的做法,就是对协议内容进行一次额外的加密,为了性能,往往选用对称加密算法。那么问题来了,手机 APP 开发时,应该选用哪个加密算法?

关于这个选型,国内互联网圈有个怪现状值得谈一下,那就是 TEA 算法。因为该算法在腾讯有着广泛的应用,因而被很多客户端开发人员推崇。典型推荐理由往往是:“TEA加密算法不但比较简单,而且有很强的抗差分分析能力,加密速度也比较快,还可以根据需求设置加密轮数来增加加密强度”。这是真的吗?算法安全性可以直接看维基百科上 TEA 算法的介绍,我的理解是不够安全。但其实大部分用户也不那么地在乎它的安全强度,那么性能呢?加密速度真的很快吗?

这就要从历史的角度去看了。作为曾经手撸过 “DES 差分密码攻击” 代码的程序员,表示 TEA 算法的确足够简单。在 QQ 诞生的那个年代,TEA 在计算上的确有着不小的优势。但 QQ 已经 18 岁了啊同学们,18 年来中国发生了多大的变化,世界发生了多大的变化啊!

2008 年,Intel 就发布了 x86 的 AES 指令集扩展,近几年的服务器 CPU 应该都支持,不相信你
grep aes /proc/cpuinfo 就能看到 ;2011 年 ARM 也在 ARMv8 架构下直接提供了 AES 和 SHA-1/SHA-256 指令 。这意味着什么?意味着服务端和客户端在硬件上直接支持 AES,意味着原来 N 条汇编指令只需要一条 AES 指令就完成了。其实也意味着,在绝大多数情况下 AES 才应该是你的首选

口说无凭,咱们可以看一下测试数据,x86 服务器 CPU 测试可以直接看 Crypto++ 的 benchmark 。可以看到 AES/CTR (128-bit key) 与 TEA/CTR (128-bit key) 的加密速度比是:4499 MB/s 比 72 MB/s,62 倍的差异!这就是硬件实现的威力。

ARM 手机 CPU 加密算法的 Benchmark,我没有找到。但为了更有说服力,我自己实现了两个测试 APP,一个 Android 版,一个 iOS 版。写技术文章多不容易啊,写博客之前先写三个晚上代码,泪目!!!代码在 https://github.com/solrex/cipher-speedAndroid 版可以直接在 Release 里扫码安装

首先介绍一下目前的旗舰 CPU,骁龙 835 (MSM8998) 的表现,测试机型是小米 6:

# Speed Test of 10MB Data Enc/Decryption #
# AES: 
* [AES/CBC/PKCS5Padding] ENC: 1146.9 KB/ms
* [AES/CBC/PKCS5Padding] DEC: 692.4 KB/ms
* [AES/CBC/NoPadding] ENC: 1118.8 KB/ms
* [AES/CBC/NoPadding] DEC: 1343.5 KB/ms
* [AES/ECB/PKCS5Padding] ENC: 990.4 KB/ms
* [AES/ECB/PKCS5Padding] DEC: 703.2 KB/ms
* [AES/ECB/NoPadding] ENC: 973.4 KB/ms
* [AES/ECB/NoPadding] DEC: 988.9 KB/ms
* [AES/GCM/NOPADDING] ENC: 13.9 KB/ms
* [AES/GCM/NOPADDING] DEC: 14.7 KB/ms
# DES: 
* [DES/CBC/PKCS5Padding] ENC: 20.1 KB/ms
* [DES/CBC/PKCS5Padding] DEC: 20.7 KB/ms
* [DES/CBC/NoPadding] ENC: 21.3 KB/ms
* [DES/CBC/NoPadding] DEC: 21.6 KB/ms
* [DES/ECB/PKCS5Padding] ENC: 26.3 KB/ms
* [DES/ECB/PKCS5Padding] DEC: 26.2 KB/ms
* [DES/ECB/NoPadding] ENC: 25.9 KB/ms
* [DES/ECB/NoPadding] DEC: 26.8 KB/ms
# 3DES: 
* [DESede/CBC/PKCS5Padding] ENC: 23.6 KB/ms
* [DESede/CBC/PKCS5Padding] DEC: 23.2 KB/ms
* [DESede/CBC/NoPadding] ENC: 23.6 KB/ms
* [DESede/CBC/NoPadding] DEC: 23.5 KB/ms
* [DESede/ECB/PKCS5Padding] ENC: 8.5 KB/ms
* [DESede/ECB/PKCS5Padding] DEC: 8.5 KB/ms
* [DESede/ECB/NoPadding] ENC: 8.5 KB/ms
* [DESede/ECB/NoPadding] DEC: 8.6 KB/ms
# TEA: 
* [TEA] ENC: 16.0 KB/ms
* [TEA] DEC: 18.1 KB/ms

可以看到,TEA:AES=16:990,这是多少倍?我都懒得算了。然后是 2 年前的中低端 CPU,联发科 Helio P10 (MT6755),测试机型是魅蓝 Note 3:

# Speed Test of 10MB Data Enc/Decryption #
# AES: 
* [AES/CBC/PKCS5Padding] ENC: 358.8 KB/ms
* [AES/CBC/PKCS5Padding] DEC: 267.9 KB/ms
* [AES/CBC/NoPadding] ENC: 438.8 KB/ms
* [AES/CBC/NoPadding] DEC: 515.0 KB/ms
* [AES/ECB/PKCS5Padding] ENC: 310.6 KB/ms
* [AES/ECB/PKCS5Padding] DEC: 222.1 KB/ms
* [AES/ECB/NoPadding] ENC: 312.4 KB/ms
* [AES/ECB/NoPadding] DEC: 319.5 KB/ms
* [AES/GCM/NOPADDING] ENC: 5.1 KB/ms
* [AES/GCM/NOPADDING] DEC: 5.7 KB/ms
# DES: 
* [DES/CBC/PKCS5Padding] ENC: 7.5 KB/ms
* [DES/CBC/PKCS5Padding] DEC: 7.7 KB/ms
* [DES/CBC/NoPadding] ENC: 7.7 KB/ms
* [DES/CBC/NoPadding] DEC: 7.8 KB/ms
* [DES/ECB/PKCS5Padding] ENC: 9.3 KB/ms
* [DES/ECB/PKCS5Padding] DEC: 9.2 KB/ms
* [DES/ECB/NoPadding] ENC: 9.3 KB/ms
* [DES/ECB/NoPadding] DEC: 9.5 KB/ms
# 3DES: 
* [DESede/CBC/PKCS5Padding] ENC: 12.5 KB/ms
* [DESede/CBC/PKCS5Padding] DEC: 12.3 KB/ms
* [DESede/CBC/NoPadding] ENC: 12.3 KB/ms
* [DESede/CBC/NoPadding] DEC: 12.5 KB/ms
* [DESede/ECB/PKCS5Padding] ENC: 3.1 KB/ms
* [DESede/ECB/PKCS5Padding] DEC: 3.1 KB/ms
* [DESede/ECB/NoPadding] ENC: 3.1 KB/ms
* [DESede/ECB/NoPadding] DEC: 3.1 KB/ms
# TEA: 
* [TEA] ENC: 6.2 KB/ms
* [TEA] DEC: 8.0 KB/ms

然后是 3 年前的旗舰 CPU,Apple A8,测试机型是 iPhone6。别问我为啥不用今年的苹果旗舰 CPU...

# Speed Test of 10MB Data Enc/Decryption #
# AES
* [AES/CBC/PKC7Padding] ENC: 76.0 KB/ms
* [AES/CBC/PKC7Padding] DEC: 111.3 KB/ms
* [AES/CBC/NoPadding] ENC: 138.2 KB/ms
* [AES/CBC/NoPadding] DEC: 450.7 KB/ms
* [AES/ECB/PKC7Padding] ENC: 305.6 KB/ms
* [AES/ECB/PKC7Padding] DEC: 735.9 KB/ms
* [AES/ECB/NoPadding] ENC: 330.0 KB/ms
* [AES/ECB/NoPadding] DEC: 673.6 KB/ms
# DES
* [DES/CBC/PKC7Padding] ENC: 23.1 KB/ms
* [DES/CBC/PKC7Padding] DEC: 24.5 KB/ms
* [DES/CBCPadding] ENC: 23.1 KB/ms
* [DES/CBCPadding] DEC: 22.8 KB/ms
* [DES/ECB/PKC7Padding] ENC: 19.4 KB/ms
* [DES/ECB/PKC7Padding] DEC: 20.8 KB/ms
* [DES/ECBPadding] ENC: 22.2 KB/ms
* [DES/ECBPadding] DEC: 22.2 KB/ms
# 3DES
* [3DES/CBC/PKC7Padding] ENC: 9.7 KB/ms
* [3DES/CBC/PKC7Padding] DEC: 9.8 KB/ms
* [3DES/CBC/NoPadding] ENC: 9.8 KB/ms
* [3DES/CBC/NoPadding] DEC: 9.8 KB/ms
* [3DES/ECB/PKC7Padding] ENC: 9.4 KB/ms
* [3DES/ECB/PKC7Padding] DEC: 9.1 KB/ms
* [3DES/ECB/NoPadding] ENC: 9.2 KB/ms
* [3DES/ECB/NoPadding] DEC: 9.4 KB/ms
# TEA
* [TEA] ENC: 10.9 KB/ms
* [TEA] DEC: 11.1 KB/ms

关于 Apple A8 的测试多说两句。我上面的 AES 性能,离 GeekBench 发布的 A8 AES Single Core 还有不少差距,不知道是不是测试方法差异导致。但总的来说,不影响结论,那就是 TEA 跟 AES 差距巨大

看到这里,可能大部分人心里已经做出选择了。即使还没做出选择的读者,我想你也可以考虑看看我的代码实现是否存在问题。不过最后还是回答一下开头提出的问题吧:

  • 如果你使用平台语言来实现对称加密,也就是 Android 上用 Java,iOS 上用 OC 或者 Swift,AES 是不二选择。这样能充分利用硬件提供的能力,安全性+性能肯定是最优,不要再想其他选项了。
  • 如果你使用 Native 语言来实现对称加密,在 Android 上使用 JNI 调用 C 编译的代码,的确不少人认为原生指令更难逆向。可能要在 ARM 架构上做个取舍,是取悦 v8 用户,还是取悦 v7 以下的用户,这可能影响到选型。不过我认为 AES 依然是一个好的选项,起码在服务器端,你肯定会节省成本。

C++ 多线程调用 Lua 的正确姿势

上一篇文章《轻量级的 C++ Lua 传参方法 - Protobuf 反射》提到我正在 C++ 项目中使用简单的 Lua 脚本做一些灵活的程序逻辑,这样可以把多个 Lua 脚本放在数据库或者缓存里,根据不同的条件选择执行不同的脚本,而且可以在线更新这些脚本。

但在 C++ 项目中集成 Lua,遇到的第一个问题就是多线程问题。Lua 本身是不知晓宿主程序线程环境的,所以 lua_State 的多线程访问是不安全的。而多线程又是服务端程序的天然特性,我暂时还不想把所有逻辑都托管给 Lua,用它自己的多线程机制。所以看起来有下面几个选择:

一是把 Lua 脚本也看成是一个独立服务,通过 RPC 或者消息队列的方式去调用它,在 Lua 脚本内部处理性能问题。这样做相当于用 Lua 写了个服务,脚本复杂度比较高,偏离了我的本意。

二是在每个 C++ 线程里,都创建一个独立的 Lua VM。每个线程有自己的上下文,也自然就互不干扰了。这样做会浪费一些内存,但考虑到 Lua VM 几十 K 级别的大小,对服务端来说根本不算什么开销。但创建线程级的 Lua VM,内存管理上又有不同的方法。

__thread 修饰符只能约束 POD 变量,的确可以存 lua_State 指针,可是它不支持指针的销毁,必须自己额外管理 lua_State 对象,然后再把指针传给线程变量。thread_local 的确能支持复杂类型,可以在析构里销毁 lua_State,可又要求 C++11。思来想去,用pthread_key_create/delete + pthread_get/setspecific 是一个相对稳妥又较为简单的方法,即不用额外自动管理内存,又能实现在线程结束后自动析构线程自己的 Lua VM。

三是将 C++ 的线程与 Lua 的线程对应起来,使用同一个 Lua VM,但在每个 C++ 线程中都用lua_newthread 创建一个 Lua 线程 State 指针。不过在创建线程那一刻,仍然需要对主 lua_State 加锁。这其实相当于给每个 C++ 线程都创建了一个独立的 Lua 堆栈,这样在传参和执行脚本的时候就不担心有数据冲突。理论上来讲效果应该与二是类似的。

四是使用一个线程安全的对象池。将 lua_State 指针放到对象池里,需要的时候拿出来,用完再放回去,由对象池来管理创建和销毁。这就需要一个额外的内存管理容器,代码量大一些,只是对很多成熟的产品来说,可能本身就有这样的轮子。

考虑到代码量,复杂度等问题,我实际在项目中采取了二方案。不过我对 Lua 的了解还不深入,不知道是否还有更好的办法?

一种轻量级 C++ Lua 传参方法 - Protobuf 反射

虽然很多动态语言(例如 PHP)的性能在近些年有了大幅度的提升,也得到了更广泛的应用,但是在一些对性能要求比较严苛的场合,C/C++ 还是有着难以替代的优势。可 C/C++ 最大的缺点就是它的不够灵活,很小一点修改都必须得重新编译,部署,重启上线。为了增强 C/C++ 的灵活性,很多项目都选择嵌入 Lua 解析器来处理程序逻辑中的动态部分,我们也不例外。

目前我们对 Lua 的使用还是比较保守,主要是封装了一些基于特定条件的排序或者过滤规则。它的特点就是传入参数较多,但返回值特别少,基本上就是一个数字或者布尔值。最开始是使用的原始方法,手工去拼 Lua Table 作为传入参数,每加一个参数,就要手写几行添加元素的代码。最近我看到 brpc 里的 pb2json ,忽然想到完全可以用 Protobuf 的反射机制,自动拼 Lua Table。下面是基本类型的转换方法,当然,也可以用类似的方法对 Protobuf 的 map, message 等高级数据结构进行进一步封装。

void ProtoMessageToLuaTable(const google::protobuf::Message &message, lua_State *L) {
    lua_newtable(L);
    const Descriptor* descriptor = message.GetDescriptor();
    const Reflection* reflection = message.GetReflection();
    int field_count = descriptor->field_count();
    for (int i = 0; i < field_count; ++i) {
        const FieldDescriptor* field = descriptor->field(i);
        switch (field->type()) {
        case FieldDescriptor::TYPE_BOOL:
            lua_pushboolean(L, reflection->GetBool(message, field));
            break;
        case FieldDescriptor::TYPE_UINT32:
            lua_pushinteger(L, reflection->GetUInt32(message, field));
            break;
        case FieldDescriptor::TYPE_UINT64:
            lua_pushinteger(L, reflection->GetUInt64(message, field));
            break;
        case FieldDescriptor::TYPE_INT32:
        case FieldDescriptor::TYPE_SINT32:
            lua_pushinteger(L, reflection->GetInt32(message, field));
            break;
        case FieldDescriptor::TYPE_INT64:
        case FieldDescriptor::TYPE_SINT64:
            lua_pushinteger(L, reflection->GetInt64(message, field));
            break;
        case FieldDescriptor::TYPE_FLOAT:
            lua_pushnumber(L, static_cast<double>(reflection->GetFloat(message, field)));
            break;
        case FieldDescriptor::TYPE_DOUBLE:
            lua_pushnumber(L, reflection->GetDouble(message, field));
            break;
        case FieldDescriptor::TYPE_STRING:
            lua_pushstring(L, reflection->GetString(message, field).c_str());
            break;
        default:
            lua_pushnil(L);
            break;
        }
        lua_setfield(L, -2, field->name().c_str());
    }
}

其实调研了一下,发现还有一些其它的方法,比如 luabind, sol2一堆库。但这些工具更适合 C++ Lua 交互比较复杂的场合,而且也引入了额外的依赖和额外的要求(比如 C++11)。对于像我们这样的简单场景,在不引入更多依赖的情况下使用 Protobuf 反射机制,不失为一个好的选择。

合并 Debian 补丁的 OpenBSD netcat Linux 源码

前几天在我的 CentOS 4.3 古董服务器上想使用 ProxyCommand 给 ssh 配置 socks 代理,ssh -o "ProxyCommand nc -X 5 -x 127.0.0.1:1080 %h %p" 选项在我的 OSX/Ubuntu 上挺好用的,但是在 CentOS 4.3 却发现 " invalid option -- x",没有这个参数。

本来我以为是 netcat 没有更新到最新,特地去下载了 GNU netcat 最新的源码包,结果源码编译后还是没有 “-x” 这个参数。后来仔细看 man page,看起来根本就不是一个版本。调研了下,才发现 netcat 居然有好多的版本:

你们城里人可真会玩儿啊!

因为 OSX/Ubuntu 都是用的 OpenBSD netcat(移植或修改版),所以 -x/X 参数是存在的,能够实现代理功能;但是 CentOS 4 因为版本太老,用的还是 GNU netcat。本来找个移植后的源码包,直接编译安装就好了呗。但可是,我 Google 了半天 (打脸,谁让你还用 CentOS 4),还是没找到能直接编译的 OpenBSD netcat Linux 源码包,最后还是在 Arch 的某个网站上找到使用 Debian 源码进行 Patch 然后再编译的脚本,才搞明白怎么能在 Linux 编出来 OpenBSD netcat 。

可能是出于易维护的考虑吧,Debian 把源码分成了两个包,一个是原始的 OpenBSD netcat,一个是 Debian 的 N 个 Patch 源码。编译时要先把 Patch 打到 OpenBSD 源码上,然后再编译。可这样的过程不是维护者很难理解,为什么不多发布个打完 Patch 的源码呢?而且这种补丁包形式也没个官方网站介绍下,真的好难懂。

为了避免其它古董 Linux 发行版用户再有我这样的苦恼,我把 patch 后的代码上传到了 Github: https://github.com/solrex/netcat ,有需要的朋友可以自取。

700行代码帮你迈出打造专属Jarvis的第一步

前几天,Mark Zuckerberg 写了一篇博客《Building Jarvis》 ,立即风靡科技圈。智能家庭,Bill Gates 弄了一个,Zuckerberg 也搞了一个,科技圈的大佬们纷纷动手,让小民们看着很眼馋。

在《Building Jarvis》这篇文章中,Zuckerberg 写到:

These challenges always lead me to learn more than I expected, and this one also gave me a better sense of all the internal technology Facebook engineers get to use, as well as a thorough overview of home automation.

注意到这些酷炫的技术,都是 internal technology Facebook engineers get to use。那么到底有没有可能,使用公开领域的服务,构建一个类似于 Jarvis 的系统呢?

正好这段时间,我也在做一个基于人工智能技术的简单 APP:WhatIsWhat。这个 APP 目前很简单,甚至可以称得上简陋,但可能对你构建自己的 Jarvis 会有所帮助或启发。

什么是什么
什么是什么

背景

某天闲聊的时候,有个妈妈同事说,她家宝宝问她很多东西不懂,只好去搜索,发现百度百科的不少词条有个“秒懂百科”,用视频讲解百科词条,宝宝很爱看。只是可惜宝宝不认字,不会自己搜索。然后我就想,要是有个工具,能用语音问问题,语音或者视频回答问题,那挺不错啊,就有了这个 APP。

随着近几年语音识别准确率的大幅度提升,语音交互技术已经步入到非常成熟的阶段了。公开领域也有讯飞、百度等好几家免费服务可用,只是关注和使用这些的一般都是企业,个人开发者并不多。其实从我工作上的背景出发,语音交互背后的技术都是非常熟悉的。下面我就以我使用的百度语音开放平台为例,解释下能有哪些免费的语音交互服务可用。

语音识别

要想宝宝能使用语音问问题,首先需要有一个语音转文字的技术,我们一般称之为“语音识别”。从 20 世纪 70 年代 IBM 把 HMM 应用到语音识别技术上来以后,语音识别准确率一直在稳步提升。但到了 2000 年以后,语音识别的效果改进停滞了,而且一停就是 10 年。直到 2010年,Geoffrey Hinton、邓力和俞栋在微软研究院将深度学习引入语音识别技术后,平地一声惊雷,语音识别的准确率才又开始一次大跃进。

可以这样说,20 年前的语音识别和六七年前的语音识别,没有太大区别。但现在的语音识别技术,和六七年前的语音识别技术,是有革命性改进的。如果你还根据几年前的经验,认为语音识别是个 Tech Toy,识别结果充满了错漏。不妨试试最新的语音识别产品,比如讯飞语音输入法、百度语音搜索,结果会让你很吃惊的。

值得高兴的是,讯飞和百度都将最新的语音识别技术免费开放给所有人使用。比如百度的语音识别服务,单个应用每天可以免费调用 5 万次,而且可以通过申请提升这个免费上限。只需要到它的平台上注册成为开发者(不需要任何费用),申请新建一个应用,下载最新版的 SDK,参考文档集成到 APP 里就行了。

语音合成

如果想让手机使用语音回答问题,还需要一个文字转语音的技术,我们一般称之为“语音合成”或者“TTS”。语音合成在准确率方面的问题上,没有语音识别那么显著,但更大的困难来自于“怎么让机器发出的声音更像人声?”有很多个方面的考量,比如情绪、重音、停顿、语速、清晰度等等。现代的语音合成产品,一般都支持选择发声人(男声、女声、童声)和调整语速的功能。很多小说阅读器都配备的“语音朗读”,就是语音合成技术的典型应用。

讯飞和百度也都免费开放了自家的语音合成技术,也是类似于语音识别的SDK集成即可。值得一说的是,Google 在今年 9 月发表了自家的 WaveNets 语音合成模型,号称将 TTS 发声和人声的差距缩短了 50%(可以到这个页面体验一下),所以我们可以期待公开的语音合成服务效果有更进一步的改进。

WaveNets 效果
WaveNets 效果

语音唤醒

就像两个人交谈时你必须得称呼对方名字,他才知道你是在对他说话,机器也是一样。对着手机屏幕的时候,可以通过点击麦克风按钮来实现唤醒语音输入,但在远处或者不方便点击时(比如开车),需要用特定的指令唤醒它接收并处理你的输入。就像我们熟悉的“Hey,Siri”和“OK,Google”,我们一般称之为“语音唤醒”。

一般情况下,唤醒指令不依赖语音识别,也就是说,它纯粹是使用声学模型匹配你的声音。这样做也有好处,就是不依赖网络,待机功耗也更低。

讯飞的语音唤醒功能是收费的,但是百度的语音唤醒功能是免费的,可以定制自己的唤醒词,然后下载对应唤醒词的声学模型包,集成到语音识别 SDK 中即可。

如果希望打造一个专属的 Jarvis 的话,这个唤醒词声学模型最好是使用自己的语音训练出来的,这样召准率才能更高。但很遗憾,百度的免费语音唤醒还不支持这点,只能用百度语料库训练出来的模型。

自然语言理解

关于自然语言理解,Zuckerberg 的 《Building Jarvis》已经解释得非常充分了,这是一个非常复杂和困难的技术领域。讯飞和百度也都在自身语音识别能力基础上,开放了自然语言理解的能力。用户甚至可以在云端自定义自己的语义,这样识别后不仅能拿到一个纯文本识别结果,还可以获取结构化的分析后结果。

百度语义理解
百度语义理解

我对 WhatIsWhat 这个 APP 的要求很简单,只需要理解“什么是什么?”这个问题即可。我没有用到百度的语义理解能力,而是简单地写了一个正则表达式匹配,主要是希望后续能充分利用语音识别的 Partial Result 对性能进行优化。

问题回答

目前很多搜索引擎(比如谷歌、百度)对语音发起的搜索,在给出搜索结果的同时,往往附带着一句或者几句语音的回答。但搜索引擎针对的往往是开放领域的搜索词,所以语音回答的覆盖比例并不高。限定到“什么是什么”这个特定的领域,百度百科的满足比例就高了。尤其是秒懂百科,使用视频的方式讲解百科词条,样式非常新颖。

在这个最初的版本中,我只采取了秒懂百科的结果。也就是先抓取百科结果页,提取秒懂百科链接,然后打开秒懂百科结果页。为了让播放视频更方便,我用 WebView 执行了一个自动的点击事件,这样第一条视频结果在打开页面后会直接播放,不需要再点击。

演示视频

下面是“WhatIsWhat”这个 APP 的演示视频,请点击查看,因为录音设备的冲突,视频的后半部分没有声音,敬请谅解。

演示视频,点击查看

源代码地址

你可以到 https://github.com/solrex/WhatIsWhat 这个链接查看“WhatIsWhat”的全部源代码。代码总共 700 多行,不多,需要有一点儿 Android 和 Java 基础来理解。

总结

WhatIsWhat 是从一个朴素 idea 出发的非常简单的 APP,这个产品集成了“语音识别、语音合成、语音唤醒、自然语言理解”几类人工智能服务。想要实现 Jarvis,可能还需要人脸识别、智能对话、开放硬件 API 等几项能力,并且需要一定的工程能力将这些功能整合起来。

虽然 WhatIsWhat 与 Jarvis 的复杂度不可比,但它演示了如何使用公共领域已有的人工智能服务,构造一个落地可用的产品。更重要的是,它便宜到不需花一分钱,简单到只有 700 行代码。

就像 Zuckerberg 所说“In a way, AI is both closer and farther off than we imagine. ”虽然很多人并没有意识到语音交互这类 AI 技术能够那么地触手可及,但技术的开放对 AI 应用普及的影响是巨大的。在这一点上,国内的人工智能产业巨头们做得并不差。这篇文章,WhatIsWhat 这个 APP,只能帮你迈出第一步,希望不远的将来,我们能够有更多的开放 AI 服务,使得搭建自己的专属 Jarvis 变成一件轻而易举的事情。

Android HTTPUrlConnection EOFException 历史 BUG

这是一个影响 Android 4.1-4.3 版本的 HTTPUrlConnection 库 BUG,但只会在特定条件下触发。

我们有一个 Android App,通过多个并发 POST 连接上传数据到服务器,没有加入单个请求重试机制。在某些 Android 机型上发现一个诡异的 bug,在使用中频繁出现上传失败的情况,但是在其它机型上并不能复现。

经过较长时间的排查,我们找到了上传失败出现的规律,并认为它跟 HTTP Keepalive 持久化连接机制有关。具体的规律是:当 App 上传一轮数据后,等待超过服务端 Nginx keepalive_timeout 时间后,再次尝试上传数据,就会出现上传失败,抛出 EOFException 异常。

更准确的特征可以通过连上手机的 adb shell 观察 netstat:当 App 上传一轮数据后,可以观察到有 N 个到服务器的连接处于 ESTABLISHED 状态;当等待超过服务端 Nginx keepalive_timeout 时间后,可以观察到这 N 个到服务器的连接处于 CLOSE_WAIT 状态;当上传失败后,发现部分 CLOSE_WAIT 状态的连接消失。

Java 的 HTTP Keepalive 机制,一直是由底层实现的,理论上来讲,不需要应用层关心。但从上面的 BUG 来看,对于 stale connection 的复用,在部分 Android 机型上是有问题的。为此我稍微研究了一下 Android 的源代码,的确发现了一些问题。

在 2011年12月15日,Android 开发者提交了这样一个 Commit,Commit Message 这样写到:

Change the way we cope with stale pooled connections.

Previously we'd attempt to detect if a connection was stale by
probing it. This was expensive (it relied on catching a 1-millisecond
read timing out with a SocketTimeoutException), and racy. If the
recycled connection was stale, the application would have to catch
the failure and retry.

The new approach is to try the stale connection directly and to recover
if that connection fails. This is simpler and avoids the isStale
heuristics.

This fixes some flakiness in URLConnectionTest tests like
testServerShutdownOutput and testServerClosesOutput.

Bug: http://b/2974888
Change-Id: I1f1711c0a6855f99e6ff9c348790740117c7ffb9

简单来说,这次 commit 做了一件事:在修改前,是在 TCP 连接池获取连接时,做 connection isStale 的探测。Android 开发者认为这样会在获取每个 connection 时都有 1ms 的 overhead,所以改成了在应用层发生异常时,再重试请求。 但是这个重试有个前提,就是用户的请求不能是 ChunkedStreamingMode,不能是 FixedLengthStreamingMode,这两种模式下,底层无法重试。很不幸地是,我们正好使用到了 FixedLengthStreamingMode 带来的特性。

// Code snippet of: libcore.net.http.HttpURLConnectionImpl.java
while (true) {
  try {
    httpEngine.sendRequest();
    httpEngine.readResponse();
  } catch (IOException e) {
    /*
     * If the connection was recycled, its staleness may have caused
     * the failure. Silently retry with a different connection.
     */
    OutputStream requestBody = httpEngine.getRequestBody();
    // NOTE: FixedLengthOutputStream 和 ChunkedOutputStream
    // 不是 instance of RetryableOutputStream
    if (httpEngine.hasRecycledConnection()
        && (requestBody == null || requestBody instanceof RetryableOutputStream)) {
      httpEngine.release(false);
      httpEngine = newHttpEngine(method, rawRequestHeaders, null,
          (RetryableOutputStream) requestBody);
      continue;
    }
    httpEngineFailure = e;
    throw e;
}

由于 BUG 的根源在 Android 的核心库 libcore 中。这次改动影响了从 4.1 到 4.3 的所有 Android 版本, Android 4.4 网络库的 HTTP/HTTPS 从 libcore 切换到 okhttp,所以4.4以后的 Android 版本不受影响。

既然底层不重试,那么只有在应用层重试,所以我们在应用层增加了最多『http.maxConnections+1』次重试机制,以修复此问题。在重试的时候,尝试使用一个 stale connection 会导致 EOFException,底层也会自动关闭这个连接。『http.maxConnections+1』次重试保证即使连接池中全都是 stale connection,我们也能获得一个可用的连接。

网上应该也有人遇到过这个 BUG,所以我也在这个 StackOverflow 问题下做了回答

std::inner_product的简单性能测试

最近团队产品中用到了一些机器学习方面的算法,涉及到求向量内积,采取的是最朴素的实现方式(元素乘积循环相加)。有一天路上想到 STL 提供了一个模板函数 std::inner_product ,就好奇 libstdc++ 实现上是否对该算法做了什么优化呢?

于是做了个简单的实验:1000 维 double 类型向量乘积,用 std::inner_product 和朴素方法分别计算10000次,g++ -O2优化。第一轮使用原生 double 类型数组,第二轮使用 vector<double> 容器,分别在三个机器环境下进行了计算。

// Processors | physical = 2, cores = 32, virtual = 12, hyperthreading = no
//     Speeds | 12x2400.186
//     Models | 12xIntel(R) Xeon(R) CPU E5645 @ 2.40GHz
//     Caches | 12x256 KB
//        GCC | version 3.4.5 20051201 (Red Hat 3.4.5-2)
	   
a*b     : std::inner_product(27.934ms), for loop(40.061ms)
a_v*b_v : std::inner_product(27.878ms), for loop(40.04ms)

// Processors | physical = 2, cores = 12, virtual = 12, hyperthreading = no
//     Speeds | 12x2100.173
//     Models | 12xAMD Opteron(tm) Processor 4170 HE
//     Caches | 12x512 KB
//        GCC | version 3.4.5 20051201 (Red Hat 3.4.5-2)

a*b     : std::inner_product(31.242ms), for loop(47.853ms)
a_v*b_v : std::inner_product(31.301ms), for loop(47.815ms)

// Processors | physical = 1, cores = 0, virtual = 1, hyperthreading = no
//     Speeds | 1x2572.652
//     Models | 1xIntel(R) Core(TM) i5-3320M CPU @ 2.60GHz
//     Caches | 1x6144 KB
//        GCC | version 4.7.2 (Ubuntu/Linaro 4.7.2-2ubuntu1)

a*b     : std::inner_product(41.76ms), for loop(33.165ms)
a_v*b_v : std::inner_product(35.913ms), for loop(32.881ms)

可以看出不同环境下 std::inner_product 的表现不尽相同,与朴素的方式相比有优有劣。瞄了一眼 gcc 4.8 的 libstdc++ 的代码,没有注意到 std::inner_product 对基本类型做什么 SSE 指令的优化。不过倒是有个并行计算的版本,可能对超大的向量计算有帮助。

虽然从性能上没有看到明显的优势,但毕竟 std::inner_product 可以简化一个循环的编码,至少可以少测一个分支嘛。而且配合重载函数的后两个 functor 参数,可以做一些有趣的事情,比如算一组数的平方和,比较两个字符串相同字符的数量等。以后呢可以多尝试一下用标准库的算法而不是自己写循环。

寻找最快的Python字符串插入方式

在 MapReduce 分布式计算时有这样一种场景:mapper 输入来自多个不同的数据源,共同点是每行记录第一列是作为 key 的 id 列,reducer 需要根据数据源的不同,进行相应的处理。由于数据到 reducer 阶段已经无法区分来自什么文件,所以一般采取的方法是 mapper 为数据记录打一个 TAG。为了便于使用,我习惯于把这个 TAG 打到数据的第二列(第一列为 id 列,作为 reduce/join 的 key),所以有这样的 mapper 函数:

def mapper1(line):
    l = line.split('\t', 1)
    return "%s\t%s\t%s" % (l[0], 'TAG', l[1])

这样给定输入:

s = "3001	VALUE"

mapper1(s) 的结果就是:

s = "3001	TAG	VALUE"

这是一个潜意识就想到的很直白的函数,但是我今天忽然脑子转筋,陷入了“这是最快的吗”思维怪圈里。于是我就想,还有什么其它方法呢?哦,格式化的表达式可以用 string 的 + 运算来表示:

def mapper2(line):
    l = line.split('\t', 1)
    return l[0] + '\t' + 'TAG' + '\t' + l[1]

上面是故意将 '\t' 分开写,因为一般 TAG 是以变量方式传入的。还有,都说 join 比 + 快,那么也可以这样:

def mapper3(line):
    l = line.split('\t', 1)
    l.insert(1, 'TAG')
    return '\t'.join(l)

split 可能要消耗额外的空间,那就换 find:

def mapper4(line):
    pos = line.find('\t')
    return "%s\t%s\t%s" % (line[0:pos], 'TAG', line[pos+1:])

变态一点儿,第一个数是整数嘛,换成整型输出:

def mapper5(line):
    pos = line.find('\t')
    pid = long(line[0:pos])
    return "%d\t%s\t%s" % (pid, 'TAG', line[pos+1:])

再换个思路,split 可以换成 partition:

def mapper6(line):
    (h,s,t) = line.partition('\t')
    return "%s\t%s\t%s" % (h, 'TAG', t)

或者干脆 ticky 一点儿,用 replace 替换第一个找到的制表符:

def mapper7(line):
    return line.replace('\t', '\t'+'TAG'+'\t', 1)

哇,看一下,原来可选的方法还真不少,而且我相信这肯定没有列举到所有的方法。看到这里,就这几个有限的算法,你猜一下哪个最快?最快的比最慢的快多少?

先把计时方法贴一下:

for i in range(1,8):
    f = 'mapper%d(s)' % i
    su = "from __main__ import mapper%d,s" % i
    print f, ':', timeit.Timer(f, setup=su).timeit()

下面是答案:

mapper1(s) : 1.32489800453
mapper2(s) : 1.2933549881
mapper3(s) : 1.65229916573
mapper4(s) : 1.22059297562
mapper5(s) : 2.60358095169
mapper6(s) : 0.956777095795
mapper7(s) : 0.726199865341

最后胜出的是 mapper7 (tricky 的 replace 方法),最慢的是 mapper5 (蛋疼的 id 转数字方法),最慢的耗时是最慢的约 3.6 倍。最早想到的 mapper1 方法在 7 种方法中排名——第 5!耗时是最快方法的 1.8 倍。考虑到 mapper 足够简单,这个将近一倍的开销还是有一点点意义的。

最后,欢迎回复给出更快的方法!

那些害人的编码“神谕”

同其它领域一样,计算机科学和工程领域也是群星璀璨,有些耀眼的星光甚至刺得我们无法直视,只能匍匐在地上聆听神谕。也正如其它领域一样,虽然大家听到的是同样的话,却有各式各样不同的理解。我这里想讲的,就是我观察到的不同理解引发的现象。

“过早优化是万恶之源。” 这是 Donald Knuth 的一句名言。虽然大部分人都不知道,或者会忘掉前面半句:“We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” Knuth 说出这句话时,可能想不到这句话会多么地流行,多么根植在很多人心中,以至于成为程序员偷懒的借口,阻碍进步的动力。因为有了这句话,在你指出别人代码中可以优化的问题时,还必须浪费口舌来解释这样的优化是必要的,不是过早优化或者过度优化。

就我的观察而言,对很多程序员来说,其能力还远远达不到过早优化的地步。但他感觉自己受到了 Knuth 的神启,仿佛具有了某种魔力,不优化代码反而成了一种优越感!关于大多数人是否具备过早优化代码的能力,我可以举几个至今我还觉得神奇的例子。

我供职的公司内部有这样一个模块,隔一两个星期总会挂掉几台服务器,现象是内存占满导致服务器假死或者宕机,但事实上根据请求推算根本不会同时使用那么多内存。最后的排查结果发现,每个线程都有这样一个数据结构,它的内存是只增不减的。当你调用它的 clear 接口,它只会把所有的内存还回自己的内存池里,而不是还给系统。这就导致可供分配的内存越来越少、越来越少...

还是这个模块里,仅仅加载一个几 K 的配置文件,就能够占用超过 1G 的内存。为什么呢?因为它用 char str[MAX_CONF_LEN] 保存配置字符串,用 struct xx_t xx[MAX_XX_NUM] 读取配置,而且这个 struct 中还有嵌套的 struct yy_t y[MAX_YY_NUM] 数组。

该模块是个个例吗?还是这家公司,一个全公司使用的公共日志库,LOGGING 宏定义中直接传一个需要系统调用的函数作为参数,导致无论关不关该级别日志都要进行一次系统调用

这家公司好歹也位列国内顶尖的互联网公司之一,工程师的招聘要求也是极其高的,还会普遍出现这种肆意浪费资源的情况。那么我想对于大部分工程师来说,谈避免“过早优化”、“过度优化”,还为时尚早。

还有一句名言“好代码本身就是最好的文档。当你需要添加一个注释时,你应该考虑如何修改代码才能不需要注释。” 这是 Steve McConnell 说的。同样,大部分人都不知道,或者忘掉后面半句:Good code is its own best documentation. As you're about to add a comment, ask yourself, "How can I improve the code so that this comment isn't needed?" Improve the code and then document it to make it even clearer. 如果你是程序员,回想一下多少次跟别人讨论代码是不是必须要注释时,这句话被引用到;有很多次在写代码时喜爱这句话,又多少次改别人的代码时痛恨这句话。

还是从我个人的观察来看,对很多程序员来说,其编码能力还不足以达到“代码本身就是最好的文档”的地步,包括我自己。敝司招聘过很多顶尖的工程师,有传说中的各种杰出前辈,可能在各种学校、公司内部事迹广为流传。但若是你哪天继承了他的代码遗产,就会发现很多传说中的明星跌落凡尘。成百上千行没有注释,使用一个公共库函数时要么接口就根本没注释只能基本靠猜,要么即使注释也语焉不详让你踩到未注明的大坑。每到这个时候你心里总会暗暗骂娘,后面别人再谈到他的光辉事迹时,你跟随讪笑时心中暗自腹诽:“牛逼个锤子!”

但我想很多人争论的焦点是:“注释是不是不可省略的、要强制执行的?”即使个别人能力真能达到“代码本身就是最好的文档”的地步(我还没见过),我也不建议在团队中传播“注释可以省略”这一想法。因为如果你说“注释可以省略”,可能你会发现大家都理解和实践成“终于可以不写注释了”。如果一个刚刚大学毕业、脑袋里从来没有过 documentation 概念、从来没写过注释的新人进入公司,就“终于可以不写注释了”,那么我想他的代码会很难达到“代码本身就是最好的文档”这个级别。因为他根本没有机会懂得什么叫做 documentation。

在公司里,代码注释深远地影响着团队合作的每个人,以及软件生存期里所有的维护者,甚至会影响自己的职业声誉。所以无论别人怎么想,我对注释这个问题的答案始终是:“注释是不可省略的,越完善越好的,甚至强制执行矫枉过正也没关系的!”

用词典查找代替VLOOKUP

从上一篇《PYTHON操作EXCEL》可以看到,Python 操作 Excel 已非常自如方便。但是 Python 和相关库毕竟是一个额外的依赖,若能从 Excel 自身解决此类问题,自然是更为易用。

1. VBA 中的哈希表

用 Python 的着眼点主要是 VLOOKUP 公式太慢了,所以关键是要找到一种更高效的算法或数据结构定位数据。VLOOKUP 要求对列进行排序,内部应该是对列内数据进行二分查找,算法上不好再优化了,那就只好更换一种数据结构。搜索了一下,VBA 提供了 Scripting.Dictionary 这一词典结构,而且有文章说内部是哈希表实现,那就正是我要的东西了。

这样,VLOOKUP(lookup_value,table_array,col_index_num,range_lookup) 这一公式就转为下面的词典查找方式来实现:

  • 使用要从中进行查找的 table_array 内容构建词典。用 table_array 第一列作为 key,table_array 第 col_index_num 列作为 value,插入 Dictionary 中:Dictionary.Add key, value;
  • 查找时只需直接取 Dictionary 内的值 Dictionary.Item(lookup_value),即可完成查找;

若是仅仅 VLOOKUP 一次,倒也不必费劲先建立起一个词典。但当使用同样 VLOOKUP 公式的单元格很多时(比如几万个),就显得其必要了。因为 Dictionary 只需要建立一次,就可以用 O(1) 的复杂度进行多次查找了。

2. VLOOKUP 慢,主要问题不在算法上

从算法角度,词典查找的确快于二分查找,但优势并不是那么明显。所以在具体执行时,我发现使用词典查找的 VBA 宏运行速度并不比 VLOOKUP 快多少,运行时 Excel 仍然会导致系统假死几个小时。按说如此简单的程序不应该那么慢,问题究竟在哪里呢?

经过一段摸索,我才发现问题的根源所在:

  • VBA 往 Excel 表格中填内容时,会引发表格中已有公式的自动计算,非常耗时;
  • Excel 表格内容更新时,会触发屏幕显示内容的自动刷新,代价也很高;

所以提高 VBA 脚本执行性能的关键点,在于计算时关掉公式自动计算和屏幕刷新,这也是我始料未及的。在 VBA 中实现这两点很容易,但由于 VLOOKUP 本身即是公式,我没能想通直接调用 VLOOKUP 时如何避免这两点带来的性能损失。

3. 示例 VBA 代码

在做了上面提到的两次优化之后,原来 VLOOKUP N 个小时才能完成的任务,只用了 7 秒钟就执行结束了。

下面是我写的一段示例代码。我不熟悉 VBA 语言,只是照葫芦画瓢。代码规范程度相差甚远,但题意应是体现其中了。有心的朋友可以用作参考。

Sub 在机器表上生成一级分中心()
'
' 在机器表上生成一级分中心 Macro
'
Application.Calculation = xlCalculationManual
Application.ScreenUpdating = False

t0 = Timer
' 词典
Set map_dict = CreateObject("Scripting.Dictionary")

' 打开分中心映射表
Set map_sheet = Worksheets("分中心映射表")
map_nrows = map_sheet.Range("A300").End(xlUp).Row
Set my_rows = map_sheet.Range("A2:B" & map_nrows).Rows

' 遍历分中心映射表,获得 分中心 对应的一级分中心,插入词典
For Each my_row In my_rows
   center = my_row.Cells(1, 1).Value
   city = my_row.Cells(1, 2).Value
   If Not map_dict.Exists(center) Then
       map_dict.Add center, city
   End If
Next my_row

' 打开机器表
Set dispatch_sheet = Worksheets("机器表")
dispatch_nrows = dispatch_sheet.Range("G99999").End(xlUp).Row
Set my_rows = dispatch_sheet.Range("K2:L" & dispatch_nrows).Rows

' 遍历开通表,通过词典获得 machine_id 对应的一级分中心,插入开通表
For Each o_row In my_rows
   center = o_row.Cells(1, 1).Value
   o_row.Cells(1, 2).Value = map_dict.Item(center)
Next o_row

MsgBox "在机器表上生成一级分中心。共处理 " & dispatch_nrows & " 条记录,总耗时" & Timer - t0 & "秒。"

' 销毁建立的词典
Set map_dict = Nothing

' 打开自动计算和屏幕刷新
Application.Calculation = xlCalculationAutomatic
Application.ScreenUpdating = True
'
End Sub

最后补充一点:我先实现的词典查找,后发现性能问题根源,所以未能去比较 VLOOKUP 与词典查找两种方式的具体性能差异。我想如果差异可以忍受,那么直接在 VBA 中调用 VLOOKUP 公式或许是一种更为简单的实现。

Python操作Excel

老婆单位有时候有一些很大的 Excel 统计报表需要处理,其中最恶心的是跨表的 JOIN 查询。他们通常采取的做法是,把多个 Excel 工作簿合成一个工作簿的多个表格,然后再跑函数(VLOOKUP之类)去查。因为用的函数效率很低,在 CPU 打满的情况下还要跑几个小时。

然后我就看不过去了,我也不懂 Excel,不知道如何优化,但我想用 Python+SQLite 总归是能够实现的。于是就尝试了一把,效果还不错,一分钟以内完成统计很轻松,其中大部分时间主要花在读 Excel 内容上。

1. Python 操作 Excel 的函数库

我主要尝试了 3 种读写 Excel 的方法:

1> xlrd, xlwt, xlutils: 这三个库的好处是不需要其它支持,在任何操作系统上都可以使用。xlrd 可以读取 .xls, .xlsx 文件,非常好用;但因为 xlwt 不能直接修改 Excel 文档,必须得复制一份然后另存为其它文件,而且据说写复杂格式的 Excel 文件会出现问题,所以我没有选它来写 Excel 文件。

2> openpyxl: 这个库也是不需要其它支持的,而且据说对 Office 2007 格式支持得更好。遗憾地是,我经过测试,发现它加载 Excel 文件的效率比 xlrd 慢 3 倍以上,内存使用在 10 倍以上,于是就放弃了。

3> win32com: Python Win32 扩展,这个库需要运行环境为 Windows+Office 对应版本。由于 Python Win32 扩展只是把 COM 接口包装了一下,可以视为与 VBA 完全相同,不会有读写格式上的问题。尝试了一下用 win32com 读取 Excel 文件,效率还是比 xlrd 慢一些。

由于读取效率上 xlrd > win32com > openpyxl,所以我自然选择了 xlrd 用来读取统计报表;而最终输出的报表格式较复杂,所以选择了 win32com 直接操作 Excel 文件。

2. Python 里的关系型数据库

SQLite 是一个非常轻量级的关系型数据库,很多语言和平台都内置 SQLite 支持,也是 iOS 和 Android 上的默认数据库。Python 的标准库里也包含了 sqlite3 库,用起来非常方便。

3. 用 xlrd 读取 Excel 并插入数据库样例

如果数据量不大,直接用 Python 内部数据结构如 dict, list 就够了。但如果读取的几张表数据量都较大,增加个将数据插入数据库的预处理过程就有很大好处。一是避免每次调试都要进行耗时较长的 Excel 文件载入过程;二是能充分利用数据库的索引和 SQL 语句强大功能进行快速数据分析。

#!/usr/bin/python
# -*- coding: gbk -*-

import xlrd
import sqlite3

# 打开数据库文件
device_city_db = sqlite3.connect('device_city.db')
cursor = device_city_db.cursor()

# 建表
cursor.execute('DROP TABLE IF EXISTS device_city')
cursor.execute('CREATE TABLE device_city (device_id char(16) PRIMARY KEY, city varchar(16))')
 
# 打开 device 相关输入 Excel 文件
device_workbook = xlrd.open_workbook('输入.xlsx')
device_sheet = device_workbook.sheet_by_name('设备表')

# 逐行读取 device-城市 映射文件,并将指定的列插入数据库
for row in range(1, device_sheet.nrows):
   device_id = device_sheet.cell(row, 6).value
   if len(device_id) > 16:
       device_id = device_id[0:16]
   if len(device_id) == 0:
       continue
   city = device_sheet.cell(row, 10).value
   # 避免插入重复记录
   cursor.execute('SELECT * FROM device_city WHERE device_id=?', (device_id,))
   res = cursor.fetchone()
   if res == None:
       cursor.execute('INSERT INTO device_city (device_id, city) VALUES (?, ?)',
                      (device_id, city))
   else:
       if res[1] != city:
           print '%s, %s, %s, %s' % (device_id, city, res[0], res[1])
device_city_db.commit()

4. 将结果写入 Excel 文件样例

使用 win32com 写入 Excel 的时候要注意,一定要记得退出 Excel,否则下次运行会出错。这需要增加异常处理语句,我这里偷了个懒,出了异常后要手动杀死任务管理器中的 excel 进程。至于 win32com 中类的接口,可以从 MSDN 网站查阅。

import win32com.client as win32
import os
excel = win32.gencache.EnsureDispatch('Excel.Application')
excel.Visible = False
# 貌似这里只能接受全路径
workbook = excel.Workbooks.Open(os.path.join(os.getcwd(), '输出.xlsx'))
month_sheet = workbook.Worksheets(1)
# 计算文件中实际有内容的行数
nrows = month_sheet.Range('A65536').End(win32.constants.xlUp).Row
# 操作 Excel 单元格的值
for row in range(5, nrows-4):
   month_sheet.Cells(row, 1).Value += something
# 保存工作簿
workbook.Save()
# 退出 Excel
excel.Application.Quit()

Python JSON模块解码中文的BUG

很多语言或协议选择使用 ASCII 字符 “\”(backslash,0x5c) 作为字符串的转义符,包括 JSON 中的字符串。一般来说,使用 Python 中的 JSON 模块编码英文,不会存在转义符的问题。但如果使用 JSON 模块编解码中文,就可能面临着中文字符包含转义符带来的 bug。本篇文章给出了一个 badcase。

中文解码错误

测试用例文件里面包含繁体的“運動”二字,使用 GB18030 编码。使用 json 解码的错误如下:

$ cat decode.dat
{"a":"運動"}
$ python
>>> import json
>>> fp=open('decode.dat', 'r')
>>> json.load(fp, encoding='gb18030')
Traceback (most recent call last):
  File "", line 1, in 
  File "/home/yangwb/local/lib/python2.7/json/__init__.py", line 278, in load
    **kw)
  File "/home/yangwb/local/lib/python2.7/json/__init__.py", line 339, in loads
    return cls(encoding=encoding, **kw).decode(s)
  File "/home/yangwb/local/lib/python2.7/json/decoder.py", line 360, in decode
    obj, end = self.raw_decode(s, idx=_w(s, 0).end())
  File "/home/yangwb/local/lib/python2.7/json/decoder.py", line 376, in raw_decode
    obj, end = self.scan_once(s, idx)
UnicodeDecodeError: 'gb18030' codec can't decode byte 0xdf in position 0: incomplete
multibyte sequence

发生这个问题的原因,就存在于“運”字的编码之中。“運”的 GB18030 编码是 0xdf5c,由于第二个字符与转义符 “\” 编码相同,所以剩下的这个 0xdf 就被认为是一个 incomplete multibyte sequence。

我本来认为,既然已经提供了编码,json 模块就能够区分汉字与转义符(所以我觉得这应该是 json 的一个 bug)。但从实验来看,并非如此。对于一些不需提供字符编码的 JSON 解码器来说,我们倒可以用一种比较 tricky 的方法绕过上面这个问题,即在“運”字后面加一个额外的转义符:

{"a":"運\動"}

遗憾的是,这种方法对 Python 的 json 模块不适用。我仍不知道该如何解决这个解码问题。

中文编码——没错误!

对于相同的 case,Python 倒是能够编码成功:

$ cat in.dat
運動
$ python
>>> import json
>>> in_str = open('in.dat', 'r').read()
>>> out_f = open('out.dat', 'w', 0)
>>> dump_str = json.dumps({'a': in_str}, ensure_ascii=False, encoding='gb18030')
>>> out_f.write(dump_str.encode('gb18030'))
$ cat out.dat
{"a": "運動"}

所以这件事情就把我给搞糊涂了,Python 的 json 模块不能解码自己编码的 json 串。所以我觉得这可能是一个 bug,或者至少是 2.7.1 版本的 bug。

PS: 要仔细看文档

20120516:经网友 TreapDB 提醒,加载字符串时自己做 Unicode 转换,貌似能够解决这个问题。

$ cat decode.dat
{"a":"運動"}
$ python
>>> import json
>>> in_str = open('decode.dat', 'r').read().decode('gb18030')
>>> json.loads(in_str)

回头仔细看了一下 json 的文档,其中有这么一段:

Encodings that are not ASCII based (such as UCS-2) are not allowed, and should be wrapped with codecs.getreader(encoding)(fp), or simply decoded to a unicode object and passed to loads().

已经注明了 encoding 不支持非 ASCII-based 编码的参数,所以应该使用 getreader 进行转码,而不是让 json 模块去转码。看来是我没读懂文档,大惊小怪了,回家面壁去!

>>> json.load(codecs.getreader('gb18030')(fp))

警惕程序日志对性能的影响

做后台系统比做客户端软件的辛苦的地方,就是不能让程序轻易地挂掉。因为在生产环境中无法容易地复现或调试 bug,很多时候需要程序日志提供足够的信息,所以一个后台系统的程序员必须要明白该如何打日志(logging)。

很多语言都有自己现成的 logging 库,比如 Python 标准库中的 logging 模块,Apache 的 log4cxx(C++), log4j(Java)。如果你愿意找,很容易能找到基本满足自己需求的日志程序库。当然,自己实现一个也不是很困难。难点不在于写这些库,而是如何去使用它们。

大部分情况下,我们关注的都是日志的级别和内容。即哪些情况下,该打哪个级别的日志,日志语句中,该怎么写。

在程序开发的过程中,我们需要很多的日志协助分析程序问题;但在生产环境中,我们没有那么多的空间存储丰富的日志,而且日志量太大对于问题排查反而是累赘。有些人使用预处理解决这个问题,在 debug 版本和 release 版本中编译进不同的日志语句。这样能够解决一些问题,但却使得在生产环境中无法轻易地打印更多的日志。大部分人更接受的做法是,使用配置(参数)控制日志的打印级别,在需要更多日志的时候,可以随时打开它们。为了实现日志“少但是足够”的目标,开发人员必须明白日志信息的价值,即哪些日志应该属于哪个级别。

日志的作用是提供信息,但不同的日志语句,提供的信息量却是不一样的。有的日志里会写“Failed to get sth..”,但却忘记加上失败调用的返回值。同程序一样,日志语句中有的是变量(某个变量内容),有的是常量(提示信息)。常量你总能从程序源代码中获得,但变量不行。所以在一条日志中,信息量最大的是变量,是函数返回值/字符串内容/错误码,因而变量应该尽量放在靠前的位置。常量也不是一点价值没有,写得好的提示语句,会使问题一目了然,可以免去你到代码中 grep,然后重读代码的麻烦。

上面这两点,几乎所有知道 logging 重要性的同学都会了解。但关于 logging 对性能的影响,很多人没有足够的警惕心。例如有人会在一个按行解析文件的函数中写下这样的日志:

int parseline(...)
{
log_trace("Enter parseline with ...");
DO_SOMETHING;
log_trace("Exit parseline with ...");
return 0;
}

乍一看,由于 log_trace 级别不高,在生产环境中肯定会关闭,那么这样做看起来对性能没太大影响。但实际上 log_trace 可能是这样实现的:

#define log_trace(fmt, arg...) \
    xx_log(LVL_TRACE, "[%s:%d][time:%uus]" fmt, __FILE__, __LINE__,\
           log_getussecond(), ## arg)
#endif

可以看到 log_trace 宏中自动添加了很多信息,值得注意的是时间参数 log_getussecond()。大家都知道统计时间需要系统调用,那么无论 log_getussecond() 函数是如何实现的,它的代价肯定是高于一般的简单函数。

我们本以为 log_trace 在 LVL_TRACE 级别被关闭的情况下,消耗的代价仅仅是一个函数调用和分支判断,却没有发现宏参数中还隐藏着一个需要调用系统调用的函数。当文件不大是还算能够忍受,但当这个文件是一个数据库,扫描每一行都要执行两次 log_trace() 时,它对系统性能的影响就绝不可忽视了。

所以,最佳的做法还是,在性能攸关的代码中,使用可被预处理掉的 logging 语句,仅仅在 debug 发布中才能见到这些日志,release 版本中不把它们编译进来。

此外,上面这个 log_trace,是一个糟糕的设计。logging 模块只应该干 logging 的事情,开发人员需要时间统计时会自己完成。

修改exvim目录过滤逻辑为匹配拒绝

exVim 是一个非常优秀的 Vim 环境,通过它能够省去很多 Vim 插件的配置工作。自从使用上 exVim 后,我基本没有再自定义 Vim 插件,完全依赖 exVim 打包的辅助功能。

最近让我略有不爽的使用问题是:exVim 默认的 file filter 和 dir filter 都是匹配通过的,即“匹配 filter 过滤条件的目录和文件被通过,列入项目目录、文件列表中”。

exVim 的 dir filter

对于文件来说,设置匹配通过毫无问题。因为我也想要项目中仅包含 “.cpp,.c,.h,.py” 这样的源代码文件,选出来匹配这些模式的文件就是我希望的结果。

但是对于目录来说,设置匹配通过就与我通常的需求相悖了。一般情况下,项目目录下的所有目录都是程序需要的。但是一些专门存放测试程序、测试框架、输出文件的目录,我其实不希望显示在我的项目中。而且 exVim 中的目录过滤貌似仅限在项目顶层目录中,过滤的意义不大。

所以我修改了一下 exVim 的代码,将默认的 dir filter 含义修改为匹配拒绝,即:“匹配 dir filter 的目录被拒绝(被过滤掉),无论它在哪一级。"例如,我将 dir filter 设置为 “test,output”,那么我项目目录下所有叫做 test 或者 output 的子目录都不会显示到项目目录列表中,而不妨碍其它名称目录的通过。

可以想见两个 filter 采用不同的通过逻辑并不是 exVim 开发者希望看到的,所以我想这个修改也没必要提交给开发者。不过我仍然觉得这是很有用的一个修改,所以拿出来分享一下。修改的补丁文件见:http://share.solrex.org/ibuild/exvim-dir_filter-8.05_b2.patch

PS: patch 文件中还有一个改动是将 quick_gen_project_PROJECT_autogen.sh 文件从项目目录下,移动到项目目录下的 .vimfiles.PROJECT/ 目录中,原因是看起来碍眼 :)

std::sort 的仿函数参数

因为习惯了 qsort 的函数指针参数,以前用 std::sort 的时候一般也是传函数指针而不是仿函数(functor)。从很多示例程序来看,貌似没有什么大的不同。但是直到今天我才醒悟,原来是示例太简单了啊!

具体来说,我今天遇到了一个问题:要对一个表进行排序,每个字段可能是升序,可能是降序,也有不同的类型,所以排序的时候需要根据这些信息进行比较。比较函数不能是类成员函数,但我又的确要用到类成员的信息,函数接口又不能变,着实发愁。愁了就只能 Google,发现原来仿函数可以轻松地搞定这件事情。

// 来自 http://stackoverflow.com/a/1902360
class MyClass{

   // ...
   struct doCompare
   {
       doCompare( const MyClass& info ) : m_info(info) { } // only if you really need the object state
       const MyClass& m_info;

       bool operator()( const int & i1, const int & i2  )
       {
            // comparison code using m_info
       }
   };

    doSort()
    { std::sort( arr, arr+someSize, doCompare(*this) ); }
};

简单点儿说,因为仿函数是个类,也可以有成员变量,构造的时候可以传参进去初始化,这样就能实现更灵活的比较方法。这么简单的道理,为什么之前我就是想不到呢?

此外值得一提的是,std::sort 要求比较的结果是 strict weak order,就是说要严格小于才返回 true。这就意味着,仅仅对比较结果取反,是无法实现逆序的。因为小于的取反不是大于,而是大于等于。

我们有过经验,如果相等的时候也返回 true,可能会导致某些标准库实现的 sort 函数指针越界,导致程序出错。所以要千万避免犯这个错误。

Leveldb 编译错误背后的C++标准变化

在编译 Levedb 时,我遇到了这个错误:

g++ -c -I. -I./include -fno-builtin-memcmp -DLEVELDB_PLATFORM_POSIX -pthread -DOS_LINUX -O2 -DNDEBUG db/version_set.cc -o db/version_set.o
db/version_set.cc: In member function `void leveldb::VersionSet::Builder::Apply(leveldb::VersionEdit*)':
./db/version_edit.h:100: error: `std::vector, std::allocator > > leveldb::VersionEdit::compact_pointers_' is private
db/version_set.cc:461: error: within this context
...

在网上容易搜到解决方案,由于归根结底是访问控制问题,方法是把所有涉及到的的 private 变量或类型修改为 public。由于不是所有的编译器都会报错,我就很好奇产生这个错误的根本原因。

BTW: 一种不修改代码的 work around 方法是,在编译这个文件时加上 -fno-access-control 参数,这样 g++ 就不会进行访问控制检查,自然也就没问题了。这个参数同样可以用于对 private 成员函数进行单元测试。

简单地分析一下这个错误。发生错误的地方是在 VersionSet::Builder 这个类的成员函数中,而错误则是其成员函数无法访问 VersionEdit 和 Version 类的私有成员变量。VersionSet 是 VersionEdit 和 Version 类的友元类,Builder 是 VersionSet 的嵌套类。简化一下,代码如下所示:

class VersionSet;

class VersionEdit {
    friend class VersionSet;
    static int compact_pointers_;
};

class VersionSet {
    class Builder {
        int foo()
        {  
            return VersionEdit::compact_pointers_;
        }  
    }; 
};

把这段代码拿给编译器去编译,g++ 3.4.4/5 会报类似的 `int VersionEdit::compact_pointers_' is private 错误,但是 g++ 4.5.3 则能够编译通过。

由于 VersionSet 是 VersionEdit 的友元类,那么 VersionSet 是能够访问 VersionEdit 私有成员的,这样问题就集中在 Builder 是否能够获得与 VersionEdit 的友元关系。如果语法规定嵌套类 Builder 能够从 VersionSet “获得”友元关系,那么 Builder就能够访问 VersionEdit::compact_pointers_,反之就不能访问。

在 C++98 标准中,关于嵌套类的权限有如下描述:

$11.8/1 [class.access.nest],

The members of a nested class have no special access to members of an enclosing class, nor to classes or functions that have granted friendship to an enclosing class; the usual access rules (clause 11) shall be obeyed. The members of an enclosing class have no special access to members of a nested class; the usual access rules (clause 11) shall be obeyed.

Example:

class E {
    int x;
    class B { };
    class I {
        B b;                 // error: E::B is private
        int y;
        void f(E* p, int i) {
           p->x = i;         // error: E::x is private
        }
   };
   int g(I* p)
   {
       return p->y;          // error: I::y is private
   }
};

但是在 C++11 中,这段描述变更为:

$11.7/1 Nested classes [class.access.nest]

A nested class is a member and as such has the same access rights as any other member. The members of an enclosing class have no special access to members of a nested class; the usual access rules (Clause 11) shall be obeyed.

Example:

class E {
    int x;
    class B { };
    class I {
        B b;                  // OK: E::I can access E::B
        int y;
        void f(E* p, int i) {
            p->x = i;         // OK: E::I can access E::x
        }  
    }; 
    int g(I* p) {
        return p->y;          // error: I::y is private
    }  
};

从上面的描述和示例代码对比中我们可以明显看出,在旧标准中嵌套类和“被嵌套类”没有什么特殊的关系,就像两个普通类一样;但是在新标准中嵌套类已经完全视为“被嵌套类”的成员,那么自然也获得了“被嵌套类”成员应该有的访问控制权限。这也就意味着“被嵌套类”的普通成员拥有的访问“被友元类”私有成员变量的权限,嵌套类也能够获得,那么 Leveldb 在新版本的编译器下能够编译通过也不足为奇了。

不过 gcc3.4 的编译错误问题还不能单单归究于标准的变化。因为 gcc3.4 已经能够支持嵌套类访问“被嵌套类”的私有成员(因为在很早以前这就被确认为一个缺陷),只是不能够支持友元关系到嵌套类的传递。友元关系的传递可能是在 4.1 或者 4.2 版本中实现的,应该属于上述标准变化的衍生特性。