iT邦幫忙

2024 iThome 鐵人賽

DAY 11
0
Python

為你自己讀 CPython 原始碼系列 第 11

Day 11 - 字串的秘密生活(下)

  • 分享至 

  • xImage
  •  

本文同步刊載於 「為你自己學 Python - 字串的秘密生活(下)

字串的秘密生活(下)

為你自己學 Python

字串操作

複製字串

在上個章節中我們介紹過這個寫法:

message = "Hello, world!"
message = message + "😊"

雖然感覺是 a = a + 1 簡單操作,但事實上這過程會產生新的字串物件。在函數的最後可以看到在做呼叫這個方法進行字串串接:

// 檔案:Objects/unicodeobject.c

PyObject *
PyUnicode_Concat(PyObject *left, PyObject *right)
{
    PyObject *result;

    // ... 略 ...

    result = PyUnicode_New(new_len, maxchar);
    if (result == NULL)
        return NULL;
    _PyUnicode_FastCopyCharacters(result, 0, left, 0, left_len);
    _PyUnicode_FastCopyCharacters(result, left_len, right, 0, right_len);
    assert(_PyUnicode_CheckConsistency(result, 1));
    return result;
}

可以看到這裡最後面做了兩次的複製動作,最終把結果給複製到 result 物件上,而且這個 _PyUnicode_FastCopyCharacters 函數的名字裡還有 Fast 字樣,我們來看看它是有多 Fast:

// 檔案:Objects/unicodeobject.c

static int
_copy_characters(PyObject *to, Py_ssize_t to_start,
                 PyObject *from, Py_ssize_t from_start,
                 Py_ssize_t how_many, int check_maxchar)
{
    // ... 略 ...
}

這個函數有幾個參數,其中 tofrom 比較好猜,就是要從 from 這顆物件複製內容到 to 物件,to_startfrom_start 也不難猜,就是要把 from 物件的某一段資料複製到 to 物件的指定位置,how_many 是要複製多少個字元,check_maxchar 是要不要檢查最大的字元值。

接著再往下看:

// 檔案:Objects/unicodeobject.c

from_kind = PyUnicode_KIND(from);
from_data = PyUnicode_DATA(from);
to_kind = PyUnicode_KIND(to);
to_data = PyUnicode_DATA(to);

if (from_kind == to_kind) {
    if (check_maxchar
        && !PyUnicode_IS_ASCII(from) && PyUnicode_IS_ASCII(to))
    {
        Py_UCS4 max_char;
        max_char = ucs1lib_find_max_char(from_data,
                                         (const Py_UCS1*)from_data + how_many);
        if (max_char >= 128)
            return -1;
    }
    memcpy((char*)to_data + to_kind * to_start,
              (const char*)from_data + from_kind * from_start,
              to_kind * how_many);
}
else if (from_kind == PyUnicode_1BYTE_KIND
         && to_kind == PyUnicode_2BYTE_KIND)
{
    // ... 略 ...
}

這個 PyUnicode_KIND 巨集其實就是檢查字串物件裡的 state 裡的 kind 屬性,如果兩個字串物件的 kind 屬性相同,就直接用 memcpy() 函數進行記憶體複製,這個 memcpy() 是直接操作記憶體,不會進行額外的檢查或處理,只是單純地將資料從一塊記憶體複製到另一塊記憶體,這比逐個字元的複製快很多。

相同編碼是進行記憶體複製,但如果是不同編碼的字串物件呢?接下來你就會看到一堆 else if 的判斷式:

// 檔案:Objects/unicodeobject.c

if (from_kind == to_kind) {
    // 快速複製
}
else if (from_kind == PyUnicode_1BYTE_KIND
         && to_kind == PyUnicode_2BYTE_KIND)
{
    // ... 略 ...
}
else if (from_kind == PyUnicode_1BYTE_KIND
         && to_kind == PyUnicode_4BYTE_KIND)
{
    // ... 略 ...
}
else if (from_kind == PyUnicode_2BYTE_KIND
         && to_kind == PyUnicode_4BYTE_KIND)
{
    // ... 略 ...
}
else
{
    // ... 略 ...
}

這一段就是做苦工啦,基本上只要是不同的編碼,就是先轉換成相同的編碼再進行逐字複製,這自然就沒有 memcpy() 來的快。也就是說,如果是相同編碼的字串物件進行串接,字串的複製是相當快的。

字串切片

在 Python 中,我們可以使用切片(Slice)操作來提取字串的一部分。例如:

text = "Hello, World!"
print(text[0:5])  # 印出: "Hello"

這是怎麼做到的?在前面曾經介紹過幾個 tp_as_xxx 的方法之一,其中透過 [] 來操作的時候,如果裡面只有一個數字,例如 [2],這樣會去找 tp_as_sequence 裡的 sq_item 方法。如果裡面有兩個數字,例如 [2:5],這樣會去找 tp_as_mapping 裡的 mp_subscript 成員。

// 檔案:Objects/unicodeobject.c

static PyObject*
unicode_subscript(PyObject* self, PyObject* item)
{
    if (_PyIndex_Check(item)) {
        Py_ssize_t i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        // ... 略 ...
        return unicode_getitem(self, i);
    } else if (PySlice_Check(item)) {
        Py_ssize_t start, stop, step, slicelength, i;
        // ... 略 ...
    }
}

從這裡可以看到,如果傳進來的 item 是個數字的話,會執行 unicode_getitem() 函數,這個函數就是用來處理單個字元的取值操作的。如果傳進來的 item 是個切片物件的話,就會準備進行切片操作。

什麼是切片物件?其實它也是個型別,名字叫做 PySlice_Type

// 檔案:Objects/sliceobject.c

PyTypeObject PySlice_Type = {
    PyVarObject_HEAD_INIT(&PyType_Type, 0)
    "slice",                    /* Name of this type */
    sizeof(PySliceObject),      /* Basic object size */
    0,                          /* Item size for varobject */
    // ... 略 ...
    (destructor)slice_dealloc,                  /* tp_dealloc */
    0,                                          /* tp_iternext */
    slice_methods,                              /* tp_methods */
    slice_members,                              /* tp_members */
    0,                                          /* tp_init */
    0,                                          /* tp_alloc */
    slice_new,                                  /* tp_new */
};

跟數字或字串相比,切片算是相對簡單的型別。而切片物件在 Python 用起來大概是像這樣:

reverse = slice(None, None, -1)
all = slice(None, None, None)
last_five = slice(-5, None)

message = "hellokitty"
print(message[reverse])    # 印出 yttikolleh
print(message[all])        # 印出 hellokitty
print(message[last_five])  # 印出 kitty

回到原本的 unicode_subscript() 繼續往下看,會看到這段:

// 檔案:Objects/sliceobject.c

slicelength = PySlice_AdjustIndices(PyUnicode_GET_LENGTH(self),
                                    &start, &stop, step);
if (slicelength <= 0) {
    _Py_RETURN_UNICODE_EMPTY();
} else if (start == 0 && step == 1 &&
           slicelength == PyUnicode_GET_LENGTH(self)) {
    return unicode_result_unchanged(self);
} else if (step == 1) {
    return PyUnicode_Substring(self,
                               start, start + slicelength);
}

這個 PySlice_AdjustIndices() 是用來計算切片的長度,如果計算出來的切片長度小於或等於 0,會回傳一個空的字串,如果切片長度等於整個字串,那就直接回傳直接回傳原本的字串。字串切片的用法跟索引值有點像,也都是使用中括號 [] 的寫法,在中括號裡有三個欄位並使用分號 : 分隔,這些欄位分別代表「起始位置(Start)」、「停止位置(Stop)以及「移動距離(Step)」,而且這三個欄位都可以視情況省略。在數字與文字章節中有更詳細的介紹,同時也可以看到如果省略部份欄位會又是怎麼回事。

其實切片的長度有一點小複雜,所以這個用來計算切片長度的 PySlice_AdjustIndices() 函數,裡面的註解也這樣寫著:

// 檔案:Objects/sliceobject.c

Py_ssize_t
PySlice_AdjustIndices(Py_ssize_t length,
                      Py_ssize_t *start, Py_ssize_t *stop, Py_ssize_t step)
{
    /* this is harder to get right than you might think */

    assert(step != 0);
    assert(step >= -PY_SSIZE_T_MAX);
    // ... 略 ...
}

現在的註解都講的這麼直白了嗎!

效能

字串內部化

字串內部化是 Python 裡處理字串的技巧之一,透過把符合特定規則的字串存放在「字串池(String Pool)」裡,可以讓相同內容的字串在記憶體裡只存儲一份,需要的時候可以從池子裡拿,這樣不只節省記憶體空間,也提高效能。

我們在 PyASCIIObjectstate 結構裡曾經看過一個 interned 的屬性,這個屬性是用來標記字串是否已經被內部化的:

// 檔案:Include/cpython/unicodeobject.h

typedef struct {
    PyObject_HEAD
    Py_ssize_t length;          /* Number of code points in the string */
    Py_hash_t hash;             /* Hash value; -1 if not set */
    struct {
        unsigned int interned:2;
        unsigned int kind:3;
        unsigned int compact:1;
        unsigned int ascii:1;
        unsigned int statically_allocated:1;
        unsigned int :24;
    } state;
} PyASCIIObject;

interned 有幾種種狀態,分別是:

// 檔案:Include/cpython/unicodeobject.h

#define SSTATE_NOT_INTERNED 0
#define SSTATE_INTERNED_MORTAL 1
#define SSTATE_INTERNED_IMMORTAL 2
#define SSTATE_INTERNED_IMMORTAL_STATIC 3

說明如下:

  • SSTATE_NOT_INTERNED 表示字串還沒有被內部化,這是大部份動態建立的字串的預設狀態。
  • SSTATE_INTERNED_MORTAL 表示字串已經被內部化,但是如果沒有其它物件需要它的話,也就是身上的 Reference Count 變成 0,就會被垃圾車載走回收掉。像是我們在 Python 程式裡透過 sys.intern() 手動內部化的字串就是這類的。
  • SSTATE_INTERNED_IMMORTAL 表示字串已經被內部化,而且不會被回收,只要 Python 活著,它們就會一直活著。Python 中的關鍵字如 "def"、"class"、"if" 這種就是這類的。
  • SSTATE_INTERNED_IMMORTAL_STATIC 表示字串已經被內部化,不只不會被 GC 回收,還是靜態的,這種字串是 Python 啟動時就建立好的,不會再被建立或回收。這通常是用在非常常用的字串上,例如空字串 "",或是單個字元的 ASCII 字串 "a""A" 就是這類的。
# 檔案:Tools/build/generate_global_objects.py

def main() -> None:
    identifiers, strings = get_identifiers_and_strings()

    generate_global_strings(identifiers, strings)
    generated_immortal_objects = generate_runtime_init(identifiers, strings)
    generate_static_strings_initializer(identifiers, strings)
    generate_global_object_finalizers(generated_immortal_objects)

if __name__ == '__main__':
    main()

在這個 Python 程式裡,從函數的名字猜的出來會產生全域字串或是識別字串,包括一些我們前面介紹過的「不死身(Immortal)」物件,執行這個程式會把寫入 Include/internal/pycore_unicodeobject_generated.h 以及 Include/internal/pycore_runtime_init_generated.h 這些檔案裡,並且在執行 Make 編譯它這些直接被編譯進 Python 的直譯器裡。有興趣可以打開這幾個檔案看看:

// 檔案:Include/internal/pycore_runtime_init_generated.h

#define _Py_small_ints_INIT { \
    _PyLong_DIGIT_INIT(-5), \
    _PyLong_DIGIT_INIT(-4), \
    _PyLong_DIGIT_INIT(-3), \
    // ... 略 ...
    _PyLong_DIGIT_INIT(255), \
    _PyLong_DIGIT_INIT(256), \
}

#define _Py_str_ascii_INIT { \
    _PyASCIIObject_INIT("\x00"), \
    _PyASCIIObject_INIT("\x01"), \
    // ... 略 ...
    _PyASCIIObject_INIT("\x04"), \
    _PyASCIIObject_INIT("\x7f"), \
}

會發現不只 ASCII 字元都被編進去,連我們前面介紹過的「小數字」(-5 ~ 256)也在這裡。

本文同步刊載於 「為你自己學 Python - 字串的秘密生活(下)


上一篇
Day 10 - 字串的秘密生活(上)
下一篇
Day 12 - 從準備到起飛!
系列文
為你自己讀 CPython 原始碼12
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言