performance - 匹配整数文字集

Question

我正在寻找一种快速方法来检查 int 是否包含在常量稀疏集中。

考虑一个 unicode 空白函数:

let white_space x =  x = 0x0009 or x = 0x000A or x = 0x000B or x = 0x000C or x = 0x000D or x = 0x0020 or x = 0x0085 or x = 0x00A0 or x = 0x1680
             or x = 0x2000 or x = 0x2001 or x = 0x2002 or x = 0x2003 or x = 0x2004 or x = 0x2005 or x = 0x2006 or x = 0x2007 or x = 0x2008 
             or x = 0x2009 or x = 0x200A or x = 0x2028 or x = 0x2029 or x = 0x202F or x = 0x205F or x = 0x3000

ocamlopt 生成的内容如下所示:

.L162:
        cmpq    $19, %rax
        jne     .L161
        movq    $3, %rax
        ret
        .align  4
.L161:
        cmpq    $21, %rax
        jne     .L160
        movq    $3, %rax
        ret
        .align  4
.L160:
        cmpq    $23, %rax
        jne     .L159
        movq    $3, %rax
        ret
        .align  4
        ...

我使用以下基准对这段代码进行了微基准测试:

let white_space x =  x = 0x0009 || x = 0x000A || x = 0x000B || x = 0x000C || x = 0x000D || x = 0x0020 || x = 0x0085 || x = 0x00A0 || x = 0x1680
             || x = 0x2000 || x = 0x2001 || x = 0x2002 || x = 0x2003 || x = 0x2004 || x = 0x2005 || x = 0x2006 || x = 0x2007 || x = 0x2008 
             || x = 0x2009 || x = 0x200A || x = 0x2028 || x = 0x2029 || x = 0x202F || x = 0x205F || x = 0x3000

open Core.Std
open Core_bench.Std

let ws = [| 0x0009 ;0x000A ;0x000B ;0x000C ;0x000D ;0x0020 ;0x0085 ;0x00A0 ;0x1680
        ;0x2000 ;0x2001 ;0x2002 ;0x2003 ;0x2004 ;0x2005 ;0x2006 ;0x2007 ;0x2008 
        ;0x2009 ;0x200A ;0x2028 ;0x2029 ;0x202F ;0x205F ;0x3000 |]

let rec range a b =
  if a >= b then []
  else a :: range (a + 1) b

let bench_space n = 
  Bench.Test.create (fun() -> ignore ( white_space ws.(n) ) ) ~name:(Printf.sprintf "checking whitespace (%x)" (n))

let tests : Bench.Test.t list  = 
  List.map (range 0 (Array.length ws)) bench_space

let () = 
  tests
  |> Bench.make_command 
  |> Command.run

基准 yield :

Estimated testing time 2.5s (25 benchmarks x 100ms). Change using -quota SECS.
┌──────────────────────────┬──────────┬────────────┐
│ Name                     │ Time/Run │ Percentage │
├──────────────────────────┼──────────┼────────────┤
│ checking whitespace (0)  │   4.05ns │     18.79% │
│ checking whitespace (1)  │   4.32ns │     20.06% │
│ checking whitespace (2)  │   5.40ns │     25.07% │
│ checking whitespace (3)  │   6.63ns │     30.81% │
│ checking whitespace (4)  │   6.83ns │     31.71% │
│ checking whitespace (5)  │   8.13ns │     37.77% │
│ checking whitespace (6)  │   8.28ns │     38.46% │
│ checking whitespace (7)  │   8.98ns │     41.72% │
│ checking whitespace (8)  │  10.08ns │     46.81% │
│ checking whitespace (9)  │  10.43ns │     48.44% │
│ checking whitespace (a)  │  11.49ns │     53.38% │
│ checking whitespace (b)  │  12.71ns │     59.04% │
│ checking whitespace (c)  │  12.94ns │     60.08% │
│ checking whitespace (d)  │  14.03ns │     65.16% │
│ checking whitespace (e)  │  14.38ns │     66.77% │
│ checking whitespace (f)  │  15.09ns │     70.06% │
│ checking whitespace (10) │  16.15ns │     75.00% │
│ checking whitespace (11) │  16.67ns │     77.43% │
│ checking whitespace (12) │  17.59ns │     81.69% │
│ checking whitespace (13) │  18.66ns │     86.68% │
│ checking whitespace (14) │  19.02ns │     88.35% │
│ checking whitespace (15) │  20.10ns │     93.36% │
│ checking whitespace (16) │  20.49ns │     95.16% │
│ checking whitespace (17) │  21.42ns │     99.50% │
│ checking whitespace (18) │  21.53ns │    100.00% │
└──────────────────────────┴──────────┴────────────┘

所以我基本上限制在 100MB/s 左右，这还不错，但仍然比例如词法分析器慢一个数量级。海湾合作委员会。由于 OCaml 是一种“你要求什么就得到什么”的语言，我想我不能指望编译器对此进行优化，但是是否有一种通用技术可以改进这一点？

Answer 1

这更短并且看起来更恒定的时间:

let white_space2 = function
  | 0x0009 | 0x000A | 0x000B | 0x000C | 0x000D | 0x0020 | 0x0085 | 0x00A0 | 0x1680
  | 0x2000 | 0x2001 | 0x2002 | 0x2003 | 0x2004 | 0x2005 | 0x2006 | 0x2007 | 0x2008
  | 0x2009 | 0x200A | 0x2028 | 0x2029 | 0x202F | 0x205F | 0x3000 -> true
  | _ -> false

给予:

┌──────────────────────────┬──────────┬────────────┐
│ Name                     │ Time/Run │ Percentage │
├──────────────────────────┼──────────┼────────────┤
│ checking whitespace (0)  │   5.98ns │     99.76% │
│ checking whitespace (1)  │   5.98ns │     99.76% │
│ checking whitespace (2)  │   5.98ns │     99.77% │
│ checking whitespace (3)  │   5.98ns │     99.78% │
│ checking whitespace (4)  │   6.00ns │    100.00% │
│ checking whitespace (5)  │   5.44ns │     90.69% │
│ checking whitespace (6)  │   4.89ns │     81.62% │
│ checking whitespace (7)  │   4.89ns │     81.62% │
│ checking whitespace (8)  │   4.90ns │     81.63% │
│ checking whitespace (9)  │   5.44ns │     90.68% │
│ checking whitespace (a)  │   5.44ns │     90.70% │
│ checking whitespace (b)  │   5.44ns │     90.67% │
│ checking whitespace (c)  │   5.44ns │     90.67% │
│ checking whitespace (d)  │   5.44ns │     90.69% │
│ checking whitespace (e)  │   5.44ns │     90.69% │
│ checking whitespace (f)  │   5.44ns │     90.69% │
│ checking whitespace (10) │   5.44ns │     90.73% │
│ checking whitespace (11) │   5.44ns │     90.69% │
│ checking whitespace (12) │   5.44ns │     90.71% │
│ checking whitespace (13) │   5.44ns │     90.69% │
│ checking whitespace (14) │   4.90ns │     81.67% │
│ checking whitespace (15) │   4.89ns │     81.61% │
│ checking whitespace (16) │   4.62ns │     77.08% │
│ checking whitespace (17) │   5.17ns │     86.14% │
│ checking whitespace (18) │   4.62ns │     77.09% │
└──────────────────────────┴──────────┴────────────┘