facebook / facebook/folly

small_vector wasting space on GNU / Linux

Open
#1,926 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
30.5k
Forks
5.9k
PR merge metrics
No merged PRs in 30d

Description

When using a `small_vector` with two **4 byte values** and a **2 byte size type**, the small_vector is **12 instead of 10 bytes** under the GNU toolchain. This wastes space and leads to platform inconsistencies.

How to reproduce:
```c++
#include
#include
#include

using my_policy = folly::small_vector_policy::policy_size_type;
using my_vector_t = folly::small_vector;

auto main() -> int {
std::cout << sizeof(my_vector_t) << " bytes \n";
return 0;
}
```

This gives the following result (C++20):
```
Windows MSVC 17.4: 10 bytes
Windows Clang 16: 10 bytes

Ubuntu GCC 12.1: 12 bytes
Ubuntu Clang 14: 12 bytes
```

I expect both numbers to be 10 bytes.

## Source of the problem

While under MSVC the pack is implemented as push/pop around the whole implementation,
```c++
FOLLY_SV_PACK_PUSH
class small_vector {
...
};
FOLLY_SV_PACK_POP
```

With GNU backend it is done via the `FOLLY_SV_PACK_ATTR` only for the pointer type.
```
struct HeapPtrWithCapacity { ... } FOLLY_SV_PACK_ATTR;
struct HeapPtr { ... } FOLLY_SV_PACK_ATTR;
```

It is not applied to the inline storage or the final Union type of both the pointer and storage.
```
typedef InlineStorageType = ...; // probably cannot be packed
union Data { ... };
```

That's why the vector is 4 byte aligned, as the value type, resulting in the final size of 12 instead of 10 bytes.

The result is the worst with a 8 byte value type and 1 byte counter. Resulting in 16 bytes instead of 9 bytes.

## Possible Fix

Adding `FOLLY_SV_PACK_ATTR` to the [union Data](https://github.com/facebook/folly/blob/73f67d4200a6b79e51a98a95397bbb1d6f2c3874/folly/small_vector.h#L1371) and [IntegralSizePolicyBase](https://github.com/facebook/folly/blob/73f67d4200a6b79e51a98a95397bbb1d6f2c3874/folly/small_vector.h#L262) fixes the issue for GCC and Clang on Ubuntu. Making the vectors 10 bytes in the above example.

```c++
union FOLLY_SV_PACK_ATTR Data { // proposed change
PointerType pdata_;
InlineStorageType storage_;
...
} u ;
```
```c++
template
struct FOLLY_SV_PACK_ATTR IntegralSizePolicyBase { // proposed change
...
SizeType size_;
}
```
In addition we need to define our [own swap](https://github.com/facebook/folly/blob/73f67d4200a6b79e51a98a95397bbb1d6f2c3874/folly/small_vector.h#L315), as GCC doesn't allow references to packed fields.
```c++
void swapSizePolicy(IntegralSizePolicyBase& o) {
// std::swap(size_, o.size_);
SizeType tmp = size_;
size_ = o.size_;
o.size_ = tmp;
}
```

## Test Cases

Here are two more test cases that already work on Windows and then also work on Ubuntu x64 Clang, GCC:

```c++
using folly::small_vector_policy::policy_size_type;

using test_vector_1 = folly::small_vector>;
static_assert(sizeof(test_vector_1) == 9); // currently 16

using test_vector_2 = folly::small_vector>;
static_assert(sizeof(test_vector_2) == 11); // currently 12
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.