標籤：

用c++寫正則引擎構造nfa的時候到底該用智能指針嗎?

01-11

之前用C寫過, 現在剛看了一部分的`C++ primer`, 準備改成c++版本練練手. 因為書上大力倡導使用智能指針, 所以我就用智能指針實現了一波, 結果碰到了幾個的問題 :

1. 我目前用的是`shared_ptr`搭配`weak_ptr`的方式, 這種方式的話, 因為實現 `*` 和 `|` 都要用一個node外聯兩個node的情況本來是相同的結構, 但是對於`*`來講, 其中有一條線是是往回連接的, 也就是連接到之前的某個Node, 而對於`|`來說, 兩條線都是向前連接的. 如果我兩根指針都用`shared_ptr`, 那麼這裡對於`*`會出現循環引用, 到時候肯定會內存泄漏, 但是如果我讓一根指針使用`weak_ptr`的話, 對於`|`來講, 被使用虛指針連接的那個node剛連接完就要被釋放, 所以都不行. 那麼這裡只有將這這裡這兩個結構分離, 但是實際上這本來就是同一種結構分離了又覺得不合情理. 想想看也沒什麼好辦法, 所以想看看各位前輩的想法...

2. 我在實現正則的時候自己實現了一個棧結構, 我的實現是在創建棧的時候先用malloc一口氣分配size(T) * 30的空間(如果沒指定大小的話), 然後如果用戶添加元素進來我再給它初始化, 然後pop()出去的元素, 調用析構函數但是不釋放內存, 之後還接著用, 等到這個棧結束的時候在棧的析構函數裡面釋放內存. 但是這裡當棧的大小不夠的話, 我覺得擴容使用`realloc`好像是不行的, 因為`realloc` 一旦選擇換個地址分配空間的話, 那麼我那些存進去的元素好像都沒有正確地被釋放, 所以我選擇的方式是手動`malloc`出一塊更大的內存之後, 先手動拷貝到新地址, 再在原位置析構掉那些元素. 我大概看了下C++ allocator的做法, 好像也沒有可以替代`realloc`的方式, 那麼難道C++ 在這一塊就沒有更好的實現嗎?

最好不要。因為構造nfa的時候，基本上是只new不delete的，所以你應該給這些細小的結構寫一個池。這個池只管new，等到你整個nfa用完不要了，直接一起扔掉，也省去了運行析構函數的一大堆無謂的CPU指令。

而且share_ptr的語義不滿足nfa的要求。實際上正確的做法是，整個nfa去own所有的shared_ptr&，而Node之間使用裸指針去聯繫。這才是正確的所有權結構。然後你把nfa裡面的vector&&>給優化成一個池，就跟我上面說的一樣了。

問題1如果你執意要用智能指針只能這麼辦了, |和*分開兩種處理, *的回訪邊用weak_ptr. 其實更好的方法是使用對象池, 一同釋放, 節點內部的邊使用裸指針.

問題2不應該使用realloc, 應該使用鏈表將block連起來. 初始只分配一個block, 內存不夠了再分配一個新的block然後連接在鏈表尾部. 歸還空間的時候只調用解構函數, 並把地址存入臨時棧里, 下次分配請求時先在臨時棧上查找可用位置, 無則在block上新分配空間. 池的生命周期結束後一同歸還所有block.

最後附上一個我當時寫正則引擎用的一個非常簡單的池, 應該能滿足你的需求.

//memory pool:
//fast link allocator
template&
class memory_pool_impl
{
protected:

typedef _Ty* _pTy;

memory_pool_impl(const memory_pool_impl) = delete;
memory_pool_impl(const memory_pool_impl) = delete;
const memory_pool_impl operator =(const memory_pool_impl) = delete;
const memory_pool_impl operator =(const memory_pool_impl) = delete;

memory_pool_impl()
:begin(new memory_block_list),
end(begin),
size(0)
{
end-&>block = malloc(BLOCK_SIZE*sizeof(_Ty)); //reserve
end-&>next = nullptr;
}

~memory_pool_impl()
{
__clear();
free(begin-&>block);
delete(begin);
}

inline
void __clear()
{
memory_block_list* temp = begin-&>next;
while (temp)
{
memory_block_list* _next = temp-&>next;
free(temp-&>block);
delete(temp);
temp = _next;
}
end = begin;
end-&>next = nullptr;
size = 0;
}

forceinline
_pTy __allocate()
{
if (size &< BLOCK_SIZE) { _pTy _temp = (_pTy)((size_t)end-&>block + size*sizeof(_Ty));
++size;
return _temp;
}
else
{
size = 1;
end-&>next = new memory_block_list;
end = end-&>next;
end-&>block = malloc(BLOCK_SIZE*sizeof(_Ty));
end-&>next = nullptr;
return (_pTy)end-&>block;
}
}

forceinline
void __deallocate()
{
//empty
}

private:
struct memory_block_list
{
memory_block_list* next;
void* block;
};
memory_block_list *begin, *end;
size_t size;
};

template&
class memory_pool
:protected memory_pool_impl &< _Ty, BLOCK_SIZE &>
{
public:
typedef _Ty* _pTy;
typedef _Ty type;
typedef _Ty* pType;

memory_pool(const memory_pool) = delete;
memory_pool(const memory_pool) = delete;
const memory_pool operator =(const memory_pool) = delete;
const memory_pool operator =(const memory_pool) = delete;

memory_pool()
{
list.reserve(BLOCK_SIZE);
}

inline
void clear()
{
this-&>__clear();
list.clear();
}

forceinline
_Ty* allocate()
{
#ifdef ENABLE_MEMORY_POOL_LOCK
std::lock_guard& lock(sync_lock);
#endif
if (list.empty())
{
return this-&>__allocate();
}
else
{
_pTy ret = list.back();
list.pop_back();
return ret;
}
}

forceinline
void deallocate(_pTy _ptr)
{
#ifdef ENABLE_MEMORY_POOL_LOCK
std::lock_guard& lock(sync_lock);
#endif
list.push_back(_ptr);
}

private:
std::vector&<_pTy&> list; //cache list
#ifdef ENABLE_MEMORY_POOL_LOCK
SpinLock sync_lock;
#endif
};

如果不考慮線程安全可以完全忽略掉代碼中的自旋鎖.

當然你也可以用上面這個池來裝NFA節點.

推薦閱讀：

※編譯器後端優化有哪些經典的必讀論文？
※繼續學習編譯原理的意義是什麼？
※設計應用的二進位存儲格式有什麼要點？
※各個編程語言的發明者是否能夠隨便反編譯各自的已編譯的二進位文件？
※編譯原理學了有什麼用？

TAG:正則表達式 | C | 編譯原理 | 智能指針 |