Perl 的 Regular Expression 的強度:NP-complete

這篇稍微偏 CS 理論一些...

以前在學校學 Formal language 的時候會帶出 Grammer、Language、Automaton 三個項目,就像是維基百科上的條列:

裡面可以看到經典的 Regular expression 會被分到 RG/RL/FSM 這三塊。

前幾天看到 gugod 寫的「[Perl] 以正規表示式來定義文法規則」這篇,裡面試著用 Perlregular expression (perlre) 建構「遞歸下降解析器」 (Recursive descent parser)。

Recursive descent parser 可以當作是 CFG 的子集合,而 CFG 對應到的語言是 CFL,另外他對應到的自動機是 PDA

我們已經知道 perlre 因為支援一堆奇怪的東西 (像是 backreference 或是 recursive pattern),所以他能接受的 language 已經超過 RL,但我很好奇他能夠做到什麼程度。

用搜尋引擎翻了翻,查到對 PCRE 的分析 (這是一套與 Perl regular expression 語法相容的 library):「Which languages do Perl-compatible regular expressions recognize?」。

在裡面有人提到「The true power of regular expressions」這篇文章,裡面給了一個在 PTIME 演算法,將 3SAT 轉換到 PCRE 裡解,這證明了 PCRE 是 NP-hard;另外也很容易確認 PCRE 是 NP,所以就達成了 NP-complete 的條件了...

本來一直以為 PCRE 只是 CFG/CFL/PDA 而已,沒想到這麼強,NPC 表示大多數現有的演算法都可以轉成 PCRE 形式放進去跑... XD

AWS 也推出了 GitHub Copilot 的競爭對手 Amazon CodeWhisperer

AWS 推出了 Amazon CodeWhisperer,可以看做是 GitHub Copilot 的競爭產品:「Now in Preview – Amazon CodeWhisperer- ML-Powered Coding Companion」,在 Hacker News 上的討論還不多:「Copilot just got company: Amazon announced Codewhisperer (amazon.com)」。

目前還是 Preview 所以是免費的,但也還沒有提供價錢:

During the preview period, developers can use CodeWhisperer for free.

另外目前提供的程式語言只有 PythonJavaJavaScript

The preview supports code written in Python, Java, and JavaScript, using VS Code, IntelliJ IDEA, PyCharm, WebStorm, and AWS Cloud9. Support for the AWS Lambda Console is in the works and should be ready very soon.

至於 training 的資料集,這邊有提到的是 open source 專案與 Amazon 自家的東西:

CodeWhisperer code generation is powered by ML models trained on various data sources, including Amazon and open-source code.

開發應該需要一段時間,不知道是剛好,還是被 GitHub Copilot 轉 GA 的事件強迫推出 Preview 版...

Python 3.11 (目前還是 beta) 的效能大幅進步

Hacker News 上看到「Python 3.11 Performance Benchmarks Are Looking Fantastic」這篇,提到目前還在 beta 的 Python 3.11 效能已經比 Python 3.10 有大幅進步了:

Python 3.11 is 10~60% faster than Python 3.10 according to the official figures and a 1.22x speed-up with their standard benchmark suite.

HN 上對應的討論在「Python 3.11 Performance Benchmarks Are Looking Fantastic (phoronix.com)」。

從比較簡單的 PyBench 到 Python 官方的 pyperformance 都有大幅進步。

像是 PyBench:

然後 pyperformance 的部份挑個我自己用到比較多的,Django 相關的東西:

整體分數跑幾何平均的話會是:

When taking the geometric mean of all the Python benchmarks I carried out for this article on the AMD Ryzen 9 5950X, Python 3.11 Beta was about 41% faster overall than the current Python 3.10.4 stable release or 45% over the aging Python 3.8 series.

在官方文件上「Faster CPython」這邊有提到做了哪些事情,可以看到大家分頭去改善超多東西,累積起來就很驚人...

PHP 8.2 預計要將一些字串內指定變數的方法標為 Deprecated,在 9.0 移除

Twitter 上看到這個蠻大的改變:

裡面的連結是「PHP RFC: Deprecate ${} string interpolation」,在文件中提到了 PHP 語言支援的四種字串內指定變數的方式:

  1. Directly embedding variables (“$foo”)
  2. Braces outside the variable (“{$foo}”)
  3. Braces after the dollar sign (“${foo}”)
  4. Variable variables (“${expr}”, equivalent to (string) ${expr})

提案在 PHP 8.2 裡將 3 與 4 兩種方式標為 deprecated,並且在 PHP 9.0 移除,目前看起來是 31:1 通過了...

PHP: The Right Way

Hacker News 上面意外看到「PHP – The Right Way (phptherightway.com)」,官網在「PHP: The Right Way」這邊,另外我在 2012 年的時候也有提過這個站台:「PHP 康莊大道」。

看了一下,應該不完全是給初學者看的,反而對於回鍋的人比較有用,無論是很舊的歷史 (像是裡面提到的 PEAR),還是比較新的東西 (像是 test case 那邊的介紹),他都有花一些篇幅介紹,而且除了開發以外也包含了 deployment 與 hosting provider 的部份...

沒想到這個網站過了十年繼續維護啊,而且內容豐富不少...

DeepMind 的 Gopher

DeepMind 丟出新聞稿,提到了 Gopher 這個比 OpenAI 家的 GPT-3 更暴力的 language model:「Language modelling at scale: Gopher, ethical considerations, and retrieval」。

GPT-3 是 175 billion 個參數,Gopher 則是拉到 280 billion,加上 tune 了不少東西,在成績上面可以看出來好不少:

另外是主打反歧視與倫理道德標準 (在「Ethical and social risks from Large Language Models」這邊提到)。

看起來主要是推出對應的產品,跟 OpenAI 家對打...

Fork 自微軟的 Pyjion 專案的 Python 3.10 + JIT 方案

Hacker News 上看到「Pyjion – A Python JIT Compiler (trypyjion.com)」這個專案,也是一個想要透過 JIT 加速 Python 的專案:

Pyjion is a drop-in JIT Compiler for Python 3.10. It can be pip installed into a CPython 3.10 installation on Linux, Mac OS X, or Windows.

看了一下是從微軟的 Pyjion 專案 fork 出來的,原來的專案最後一次 commit 是一年前,而且專案也已經標示為 archived (read-only mode),但有留下轉移的說明,也就是上面提到的專案:

Development has moved to https://github.com/tonybaloney/Pyjion

可以看到大部分的效能都已經進入改善階段 (很多導入 JIT 的專案在初期時會先變慢):

跟其他的 JIT 方案相比,Pyjion 的目標是高度相容現有 Python 的程式,包括各種 extension,這點的確是在用 PyPy 這些軟體時的痛點沒錯...

看起來透過 pip 裝好後就可以直接 import 進來用,後續就會生效:

import pyjion; pyjion.enable()

另外提一下,翻 Hacker News 留言的時候翻到這個害我笑出來,有夠新 XD

zatarc 3 days ago | unvote | prev | next [–]

Pyjion requires: CPython 3.10 and .NET 6

.NET 6 Release: 19 hours ago (https://github.com/dotnet/core/blob/main/release-notes/6.0/6...)

... ok.

Java 17 (JDK 17),新的 Java LTS 版本 (然後來看 GC)

Java 17 (JDK 17) 釋出,這是 Oracle 本家新的 LTS 版本,引用的是 jdk-dev 的 mailing list:「Java 17 / JDK 17: General Availability」。另外在 Hacker News 上的討論可以翻一下:「Java 17 / JDK 17: General Availability (java.net)」。

上一個 LTS 版本是 Java 11,所以很自然的也會有從 Java 11 之後的新功能說明:「JEPs in JDK 17 integrated since JDK 11」。

對於只是拿來用,而不是拿來開發的人來說,我的重點都放在 JVM 的 GC 效能以及特性。

從 Java 11 預設的 G1GC 來看,可以看到一些改善,從「JEP 345: NUMA-Aware Memory Allocation for G1」(Java 14) 這個看起來會改善 G1GC 在多實體 CPU 的情況下效能,不過看起來有 -XX:+UseNUMA 這個參數要加。

再來是「JEP 346: Promptly Return Unused Committed Memory from G1」(Java 12) 可以在閒閒的時候跑個 GC 把記憶體給 OS。

接下來是兩個新的 GC (相較於 11 版),一個是 ZGC,另外一個是 Shenandoah,都沒有取代 G1GC,但兩個都有對應使用的場景。

ZGC 有列兩個 JEP:「JEP 376: ZGC: Concurrent Thread-Stack Processing」、「JEP 377: ZGC: A Scalable Low-Latency Garbage Collector (Production)」,目標是讓 GC pause time 盡可能的低,另外在 wiki 上面的說明則是有提到目標在 1ms 以下:

The ZGC garbage collector (GC) aims to make GC pauses and scalability issues in HotSpot a thing of the past.

Sub-millisecond max pause times

Shenandoah 列出了「JEP 379: Shenandoah: A Low-Pause-Time Garbage Collector (Production)」,不過先前的「JEP 189: Shenandoah: A Low-Pause-Time Garbage Collector (Experimental)」講的比較詳細,目標是希望 GC 不影響目前正在執行的程式:

Add a new garbage collection (GC) algorithm named Shenandoah which reduces GC pause times by doing evacuation work concurrently with the running Java threads. Pause times with Shenandoah are independent of heap size, meaning you will have the same consistent pause times whether your heap is 200 MB or 200 GB.

可以看出來兩個新的 GC 都是希望降低 pause time,對於 latency 敏感的應用應該都可以測試看看,可以預期整體的 throughput 會低一些。

回頭來看 G1GC,有人跑了 benchmark 測試了 Java 11 與 Java 17 的 G1GC 差異:「How much faster is Java 17?」。

可以看到 G1GC 的改善 (藍色的部份) 看起來還是不少,不過有些情況下是會變慢的。文章裡面還有提到 Parallel GC,這邊就不提了,可以自己看...

等各家 build 出來後來測看看 Cassandra 的效能影響如何...

Amazon Transcribe 可以自動偵測語言了

Amazon Transcribe 可以將聲音轉成文字,先前都需要自己指定語言,而這幾天發表新的功能,可以自動偵測語言:「Amazon Transcribe Now Supports Automatic Language Identification」。

不過系統要求最少要有 30 秒的資料,跟人類比起來還是有點差距,但比起之前好用不少:

With a minimum of 30 seconds of audio, Amazon Transcribe can efficiently generate transcripts in the spoken language without wasting time and resources on manual tagging.

沒有額外的費用,主要就是照著本來的價錢在走:

There is no additional charge on top of the existing pricing.

翻了一下價錢,好像可以來測一些東西...