[C++] Branchless Singly Linked List

最近同事分享了一個一小段在新增 node 到 singly linked list 時不用判斷 head/tail 是否為 nullptr 的寫法，因為滿有趣的，所以分享一下

概念上來說其實滿簡單的，一般來說的 signly linked list 的寫法會像下面這樣 (極度簡化)

struct Node {
    void* data;
    Node* next;
};

class List
{
public:
    List() : head(nullptr), tail(nullptr) {}
    ~List() {
        while (this->head) {
            auto tmp = this->head;
            this->head = this->head->next;
            delete tmp;
        }
    }
    void addTail() {
        auto node = new Node{nullptr, nullptr};
        if (this->tail) {
            this->tail->next = node;
            this->tail = node;
        }
        else {
            this->head = this->tail = node;
        }
    }

private:
    Node* head;
    Node* tail;
};

我們需要判斷 head/tail 是否為 nullptr 來採取不同的處理方式。
當然，這可以藉由 dummy head 的作法來避開，只是如果 Node 太大，dummy head 就會占用多餘的記憶體；採用如上面範例的方式，把 data 放在別的空間，再用 pointer 指過去雖然可以避開這問題，但也會在每次要存取資料時多了一次的 memory reference 的時間。

brachless 的作法用了一個很巧妙的方式做到類似 dummy head 的效果，基本想法就是把 List 本身當成一個 dummy head。反正我們不會真的用到 dummy head 的資料欄位，只會用到 dummy head 的 next pointer，那就不如把 List 的 head 當成 dummy head 的 next pointer 就好。如下：

class List
{
public:
    List() : head(nullptr) {
        constexpr auto offset = sizeof(Node) - sizeof(Node::next);
        this->tail = reinterpret_cast<node>(&(this->head)) - offset;
    }
    ~List() {
        while (this->head) {
            auto tmp = this->head;
            this->head = this->head->next;
            delete tmp;
        }
    }
	void addTail() {
	    auto node = new Node{nullptr, nullptr};
		this->tail->next = node;
		this->tail = node;
	}

private:
    Node* head;
    Node* tail;
};

假設 List 的 head pointer 變成 dummy head 的 next pointer，那 List 的 dummy head 就是以 head 為基準，往前一段 offset，然後讓 tail 指向那邊，如此一來可以讓 tail->next 剛好就會是 List 的 head pointer 本身。

我們也可以利用 Compiler Explore 看 assembly 的差異：branchless v.s. traditional

雖然滿有趣的，不過現在 compiler 跟硬體的 branch prediction 都做得滿好的，實際使用上如果不是很常遇到 List 會變成空的，performance 應該會看不出明顯差異。

另一個值得考量的問題是 branchless 的寫法在 initialize/clear/delete 都要特殊處理，一有疏漏很容易造成 bug 造成後續維護上的困擾 (比方說 legacy code XD)。是以雖然有趣，但我覺得絕大多數情形況下不如照著常見的寫法走比較不會出問題。

完整的 code 如下

	#include <iostream>
	struct Node {
	void* data;
	Node* next;
	};
	class List
	{
	public:
	List() : head(nullptr), tail(nullptr) {}
	~List() {
	while (this->head) {
	auto tmp = this->head;
	this->head = this->head->next;
	delete tmp;
	}
	}
	protected:
	Node* head;
	Node* tail;
	};
	class BranchlessList : public List
	{
	public:
	BranchlessList();
	void addTail();
	};
	BranchlessList::BranchlessList()
	{
	constexpr auto offset = sizeof(Node) - sizeof(Node::next);
	this->tail = reinterpret_cast<Node*>(&(this->head)) - offset;
	}
	void BranchlessList::addTail()
	{
	auto node = new Node{nullptr, nullptr};
	this->tail->next = node;
	this->tail = node;
	}
	class TraditionList : public List
	{
	public:
	void addTail();
	};
	void TraditionList::addTail()
	{
	auto node = new Node{nullptr, nullptr};
	if (this->tail) {
	this->tail->next = node;
	this->tail = node;
	}
	else {
	this->head = this->tail = node;
	}
	}
	template <typename T, int ELEM_CNT>
	void perfList()
	{
	T list;
	for (int i = 0; i < ELEM_CNT; ++i) {
	list.addTail();
	}
	}
	int main()
	{
	constexpr auto ELEM_CNT = 100'000'000;
	perfList<BranchlessList, ELEM_CNT>();
	perfList<TraditionList, ELEM_CNT>();
	return 0;
	}

view raw brachless_list.cpp hosted with ❤ by GitHub