前因

在春節前了解到 Rust語言有一個叫 nom 的解析庫

它可以讓你創建安全的解析器，而不會占用內存或影響性能。

它依靠 Rust 強大的類型系統和內存安全來生成既正確又高效的解析器，并使用函數，宏和特征來抽象出容易出錯的管道。

nom 核心是解析器組合器，而解析器組合器是高階函數，可以接受多個解析器作為輸入，并返回一個新的解析器作為輸出。

這種方式讓你可以為簡單的任務(如：解析某個字符串或數字)構建解析器，并使用組合器函數將它們組合成一個遞歸下降(recursive descent)的解析器。

組合解析的好處包括可測試性，可維護性和可讀性。每個部件都非常小且具有自我隔離性，從而使整個解析器由模塊化組件構成。

由此萌生在其他非函數語言探究函數抽象代價的想法，如何優雅語義化代碼前提下追求極致的性能應該是一個非常復雜的問題

所以在春節期間選擇了熟悉的 c# 語言（避免對語言的不熟悉導致無法充分利用性能）進行了嘗試

調研

春節一開始，為了解除這個讓我寢食難安的想法，沒有片刻的休息，便開始了糾結反復長期的探究。

當然解析庫的頂流必然是ANTLR，其完全避免了大家在詞法語法解析這項費事費力極為復雜的事情上浪費時間

當然我研究ANTLR的話就完全偏離之前預定的函數抽象代價的想法

那么 c# 語言有沒有過其他人有過類似用函數思想進行解析器簡化抽象的想法呢？

一番查找，發現還真有人在多年前就做嘗試，代表者為Sprache

其不完全是典型函數組合思想，而是c#語言中Linq這數據處理函數庫以及其類sql表達結合形式

以HexColor解析舉例說明

HexColor 為16進制顏色值，其以 "#" 開頭, 接著6個16進制數(0-9和a-f,大小寫不敏感), 每2個值構成一組, 從左到右為 RGB 通道值, 可以簡寫為 #R(hex, hex)G(hex, hex)B(hex, hex).

所以解析器邏輯可以概括為：去掉開頭的 "#", 如果隨后的6個字符為16進制數, 則分為三組, 并將每組的值從16進制轉換為10進制.

手寫HexColor解析器

如果手寫代碼，該解析器代碼如下：

private static (byte red, byte green, byte blue) HexColorHande(string str)
{
    if (str.Length == 7 && str[0] is '#')
    {
        for (var i = 1; i < str.Length; i++)
        {
            if (!char.IsAsciiHexDigit(str[i]))
            {
                throw new FormatException("Must has 6 AsciiHexDigit");
            }
        }
        return (Convert.ToByte(str[1..3], 16), Convert.ToByte(str[3..5], 16), Convert.ToByte(str[5..7], 16));
    }
    throw new ArgumentException("No perfix with #");
}

除了Range運算符產生子串之外，沒有多余分配和判斷消耗，以此作為性能基線，應該可以明顯看出其他實現產生的代價

Sprache 的HexColor解析器

public static class SpracheHexColorTest
{
    /// 通過字段緩存函數，避免多次構建
    private static Sprache.Parser<(byte red, byte green, byte blue)> identifier;

    static SpracheHexColorTest()
    {
        identifier =
        from leading in Sprache.Parse.Char('#').Once()
        from s in Sprache.Parse.LetterOrDigit.Repeat(6).Text()
        select (Convert.ToByte(s[0..2], 16), Convert.ToByte(s[2..4], 16), Convert.ToByte(s[4..6], 16));
    }

    public static (byte red, byte green, byte blue) Parse(string content) => identifier.Parse(content);
}

可以看到代碼還是非常語義化，雖然個人覺得類sql形式還是有點不習慣，但其實也是對于Linq過長鏈條代碼語義復雜問題的比較好的解決形式

那么性能對比結果會是怎么樣呢？

ps： Superpower 號稱是 Sprache 的性能優化版本，兩者核心思路一致，只是一些實現細節有所差別，兩者使用形式一致，這里就不展示其代碼了

可以看到有著比較明顯的差別，當然在一般項目中，這點消耗完全沒必要考慮（但我的目的本身就是吹毛求疵，這些差異肯定是要探究的）

經過簡單查閱代碼，其主要有以下差異：

• 函數實際是以delegate作為基石

  所以對于手寫的解析器肯定有更多的delegate調用以及次數代價，不過這點由于語言特性，如果依舊要函數優化語義，多半沒有其他優化選擇了

• 函數不支持多返回值

  所以封裝了Result結構體，以此包含更多所需的結果，當然也帶來了更多的分配消耗

• IEnumerable<T>作為Sprache另外一個基石

  在這里實際導致無法使用原始的string，畢竟string的還是一個比較復雜的對象

優先嘗試減少多返回值

通過 out 避免Result結構體

public delegate int Is<T>(IPeeker<T> input, out T t);

// 一些函數實現舉例
public static Is<char> Is(char c) => Parser.Is<char>(i => i == c, 1);

public static Is<T> Is<T>(Func<T, bool> predicate, int count) => (IPeeker<T> i, out T t) =>
{
    if (i.TryPeek(out t) && predicate(t))
    {
        return count;
    }
    return 0;
};

public static Func<IPeeker<T>, T> Once<T>(this Is<T> predicate, Func<IPeeker<T>, Exception> ex) => i =>
{
    var c = predicate(i, out var t);
    if (c <= 0)
    {
        throw ex(i);
    }
    i.Read(c);
    return t;
};

// HexColor解析器
public static class HexColorOnlyChar
{
    private static readonly Func<IPeeker<char>, char> tag_Start = Chars.Is('#').Once("# is Required.");

    private static Func<IPeeker<char>, char[]> HexDigit = Chars.IsAsciiHexDigit.Repeat(6, "Must has 6 AsciiHexDigit");

    public static (byte red, byte green, byte blue) Parse(string str)
    {
        var input = Input.From(str);
        tag_Start(input);
        var s = new string(HexDigit(input));
        var r = (Convert.ToByte(s[0..2], 16), Convert.ToByte(s[2..4], 16), Convert.ToByte(s[4..6], 16));
        if (input.TryPeek(out var c))
        {
            throw new FormatException(c.ToString());
        }
        return r;
    }
}

ps： 這里實際略掉了一些 錯誤信息 以及行列計算的信息，為了簡單，暫時不討論，忽略其影響，重心先看與基線的差異

可以看到，減少了非常多處理邏輯后，性能好了很多，我們再做更多嘗試

最終實現

public static class HexColor
{
    /// Take<char> 實際調用 TryPeek(int count, out IPeekSlice<char> data) ， 降低 
    private static readonly Func<IPeeker<char>, string> HexDigitString = Parser.Take<char>(6, "Must has 6 AsciiHexDigit").Map(ii =>
    {
        var s = ii.ToString();
        for (var i = 0; i < s.Length; i++)
        {
            if (!char.IsAsciiHexDigit(s[i]))
            {
                throw new FormatException("Must has 6 AsciiHexDigit");
            }
        }
        return s;
    });

    private static readonly Action<IPeeker<char>> NoMore = Chars.Any.NoMore("Only 7 chars");
    private static readonly Func<IPeeker<char>, char> TagStart = Chars.Is('#').Once("# is Required.");

    public static (byte red, byte green, byte blue) Parse(string str)
    {
        var input = Input.From(str);
        TagStart(input);
        var s = HexDigitString(input);
        NoMore(input);
        return (Convert.ToByte(s[0..2], 16), Convert.ToByte(s[2..4], 16), Convert.ToByte(s[4..6], 16));
    }
}

對比上一版核心降低了 IEnumerable<char> 與 new string 代價

/// TryPeek 通過Substring 減少遍歷次數
public bool TryPeek(int count, out IPeekSlice<char> data)
{
    var i = readed + count;
    if (i >= str.Length)
    {
        data = null;
        return false;
    }
    data = new PeekString(str.Substring(readed + 1, count));
    return true;
}

/// PeekString 減低了 toArray 和 new string 的消耗
public class PeekString : IPeekSlice<char>
{
    private string str;

    public PeekString(string str)
    {
        this.str = str;
    }

    public override string ToString()
    {
        return str;
    }
}

完整性能測試結果

BenchmarkDotNet v0.13.12, Windows 11 (10.0.22631.3085/23H2/2023Update/SunValley3)
Intel Core i7-9750H CPU 2.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 8.0.101
  [Host]     : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2
  DefaultJob : .NET 8.0.1 (8.0.123.58001), X64 RyuJIT AVX2

// * Legends *
  Mean      : Arithmetic mean of all measurements
  Error     : Half of 99.9% confidence interval
  StdDev    : Standard deviation of all measurements
  Gen0      : GC Generation 0 collects per 1000 operations
  Gen1      : GC Generation 1 collects per 1000 operations
  Allocated : Allocated memory per single operation (managed only, inclusive, 1KB = 1024B)
  1 ns      : 1 Nanosecond (0.000000001 sec)

可以看到性能比上一版減少了一半，非常接近手寫那版，如果后續不存在函數實現的限制，該方式將會是比較接近一行一行優化的手寫方式的嘗試方案

總結

• delegate 肯定會有調用消耗，不過單次非常小，只是函數抽象一般量大
• 抽象可以簡化問題，但也容易屏蔽特定場景優化，帶來多余消耗
• 編碼還是需要安靜環境，不然容易注意力分散而昏頭浪費時間，哈哈哈哈

雖然春節花費了不少時間，確定了一些認知，但性能與優雅語義化依然如太極陰陽平衡艱難

完整代碼參考 https://github.com/fs7744/ruqu

該代碼僅為早期研究，不代表最終成型，也缺乏完整功能，還有待持續開發

后續會以 ini 文件解析探究更多復雜語義函數實現