owned this note   changed 7 years ago  
Linked with GitHub

llvm::SmallVector - Yun-Wei Lee

歡迎來到 https://hackmd.io/c/COSCUP2018 共筆

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

點擊本頁上方的 開始用 Markdown 一起寫筆記！
手機版請點選上方 按鈕展開議程列表。

Speaker

Yun-Wei Lee

  • Master student @ NCTU

Before reading code

  • What is SmallVector?

  • Why do we need it?

    • Performance
    • std::vector allocates memory dynamically, even for small size.
    • Solution –> Allocate on the stack statically.

  • First attempt

    • Fixed-size array
    • Cons: Can't grow.

  • Second attempt

    • Fixed-size array + pointer to next block.
    • Cons: Clde bloat

  • 3rd attempt

    ​​​​class SmallVectorImpl
​​​​{
​​​​    // ...    
​​​​};
​​​​class SmallVector: public SmallVectorImpl<T>
​​​​{
​​​​    // ...
​​​​};
    • Cons: Plain Old Data(POD)
      • A class without constructors, destructors and virtual member function.
      • No Virtual Table

  • 4th attempt

    ​​​​// TOO MUCH CODE!
    • Pros
      • Can use realloc for allocation
      • Can use memcpy for copy
    • More?
      • MORE!

  • 5th attempt

    • Move duplicate code into common base class.

Recap

  • SmallVectorBase:: size/capaciy/empty
  • SmallVectorTemplateCommon:: begin/end/[]/front/back/data…
  • SmallVectorTemplateBase:: push_back/pop_back
  • SmallVectorTemplateImpl:: clear/resize/append/erase/=/insert…

Clobbering

| BeginX   | 
| Size     | 
| Capacity | 
| 0        |
| ...      |
| N-1      |

Distinguish between stack/heap case

bool isSmall() const { return BeginX == getFirstBl(); }

Summary

  • What did SmallVector do?
    • Code Bloat
    • POD
    • Clobbering
tags: COSCUP2018 source
Select a repo