快速布爾表達式求值器

我有一個應用程序，其中包含一個3運算符（& |！）布爾表達式求值程序，包含變量和常量。一般來說，表達式不會太長（最多可能是50個詞，但通常會少很多）。可以有很多表達方式 - 我預計上限約爲一百萬。目前我有一個用一個非常簡單的評估器編寫的解析器，只需遞歸遍歷解析樹。一個限制是它必須從C++中調用。表達式之間沒有共享。我想調查這個速度。快速布爾表達式求值器

我看到了兩條研究途徑。

添加共享並存儲指示表達式節點是否已被評估的狀態。
提取常見子表達式。

另外我希望代碼生成方法比解析樹或類似結構上的解釋方法更快。生成一些C++代碼可能相當簡單，但考慮到函數的長度，我不知道像GCC這樣的編譯器是否能夠優化CSE。

我已經看到有幾個庫可用於表達式評估，但在我的工作環境中添加第三方庫並不簡單，再加上它們都與我的需求相比看起來非常複雜。

最後，我最近一直在看Antlr4，所以這可能適合我。在過去，我從事C代碼生成工作，但是我沒有使用LLVM之類的東西來進行優化和代碼生成。

任何建議走哪條路？

來源

2017-05-25 Paul Floyd

儘管我想建議ANTLR4，但我擔心它不會滿足您的性能需求。儘管有一些常見的技巧可以提高其性能，但在運行時簡單地跟蹤一個ANTLR4解釋器就會發現，除非當前的表達式求值器效率很低，否則很可能比ANTLR4更快，ANTLR4是一種工業應用引擎，旨在支持語法比你的複雜得多。當LALR（1）DFA shift-reduce引擎不支持我的語法時，我使用ANTLR，並以ANTLR4的額外解析能力作爲回報而獲得性能。

來源

2017-05-25 21:00:51 TomServo

解析和lex的運行時間不應該是一個問題。這是一個獨立於評估的階段，可能會有幾天的運行時間。所以即使幾個小時的解析lex階段也不成問題。評估速度是關鍵。 –

啊我明白了。然後誤解你的問題。 ANTLR中的評估可能非常有效。有一種稱爲Mu的語法，我用它作爲運行時表達式解釋器的基礎。 [鏈接]（https://github.com/bkiers/Mu/tree/master/src/main/antlr4/mu）。 – TomServo

據我所知，你的問題更多的是關於更快的表達評估比它更快的表達式解析。所以我的回答將集中在前者。畢竟，解析不應該成爲瓶頸，因爲您的表達語言看起來很簡單，足以爲其實施手動調整的解析器。

因此，爲了加速您的評估，您可以考慮使用LLVM對公式進行JIT執行。也就是說，根據公式F，您可以（相對）輕鬆生成相應的LLVM IR並直接對其進行評估。這SMT solver就是這樣做的。 IR代碼生成是在單個C++類here中實現的。請注意，您提到的布爾表達式是該解算器支持的SMT語言的子集。此外，您可以輕鬆調整LLVM優化器需要的積極性。

但是，IR生成和優化有其開銷。因此，如果給定的公式不足以分攤初始費用，那麼我會建議直接解釋。你可以在這種情況下尋找機會找到結構相似性和常見的子表達。

來源

2017-05-26 10:59:17 Codoka

快速布爾表達式求值器

回答

相關問題