HackMD
2020q1 Homework3 (quiz4)
contributed by < KYG-yaya573142 >
測驗 1
解題思路
首先觀察函式參數及開頭宣告的變數
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t _count)
{
uint8_t data, original, mask;
size_t bitsize;
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
const uint8_t *source = _src + (_read / 8);
size_t write_lhs = _write & KK1;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = _dest + (_write / 8);
...
}
bitcpy 允許開發者對指定的記憶體區域，逐 bit 進行資料複製，而從註解可以知道 _read 是寫入地址以 bit 為單位的 offset，觀察第 9~11 行
_read & 7會將read_lhs的數值侷限在 0~7read_rhs = 8 - read_lhs代表read_lhs與read_rhs的總和一定是 8*source = _src + (_read / 8)代表當 offset 超過 8 bits 時，會先以 byte 為單位移動*source來讓 offset 的數字維持在 8 以內- 綜合上述三點，在
*source指向的 byte 中read_lhs為 offset 的大小read_rhs為此 byte 資料中扣除 offset 部分後剩餘的大小
- 第 12~14 行
_write相關的部分邏輯同上，對應寫入的位置與 offset，因此 KK1 應填入 7
觀察主 while 迴圈的上半部
while (_count > 0) {
data = *source++;
bitsize = (_count > 8) ? 8 : _count;
if (read_lhs > 0) {
data <<= read_lhs;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
if (bitsize < 8)
data &= read_mask[bitsize];
...
_count -= KK2;
}
...
- 這段程式碼的作用是將資料從
*source讀進data這個 buffer data和*source的資料型態是uint8_t，代表一次讀取的資料為 1 bytebitsize代表最後需要寫入的 bit 總量，而一次迴圈我們只處理 1 byte- 因此 KK2 應填入
bitsize
- 因此 KK2 應填入
read_lhs代表讀取的 offset，因此亦可理解為從*source讀取的 byte 中read_lhs代表不需要的 bit 數量read_rhs代表需要的 bit 數量
data <<= read_lhs將不需要的 bit 移除，並將需要的資料移動到data的開頭，即只留下長度共read_rhs的資料- 因此
bitsize > read_rhs代表現有的資料不足需求，需再從下個 byte 讀取資料並接在data已有資料的後面
- 因此
- 以
_read = 5_count = 6為例，根據上述程式碼可知此時read_lhs = 5
- 由於總共需要讀取
bitsize = 6個 bit 的內容，需再從下個 byte 讀取資料並接在已有資料的後面，最終data內容如下
- 最後只會寫入
bitsize個 bit，這代表data中開頭bitsize個 bit 以外的資料是 dummy data，須使用read_mask[bitsize]遮罩掉 dummy data，以上例來說 dummy data 就是 b4 與 b5 這兩 bit 的資料 write_mask則是用於寫入時，寫入的 bit 數量以外的資料是需要保存的原始資料，因此用write_mask
...
static const uint8_t read_mask[] = {
0x00, /* == 0 00000000b */
0x80, /* == 1 10000000b */
0xC0, /* == 2 11000000b */
0xE0, /* == 3 11100000b */
0xF0, /* == 4 11110000b */
0xF8, /* == 5 11111000b */
0xFC, /* == 6 11111100b */
0xFE, /* == 7 11111110b */
0xFF /* == 8 11111111b */
};
static const uint8_t write_mask[] = {
0xFF, /* == 0 11111111b */
0x7F, /* == 1 01111111b */
0x3F, /* == 2 00111111b */
0x1F, /* == 3 00011111b */
0x0F, /* == 4 00001111b */
0x07, /* == 5 00000111b */
0x03, /* == 6 00000011b */
0x01, /* == 7 00000001b */
0x00 /* == 8 00000000b */
};
...
接著觀察主 while 迴圈的下半部
...
original = *dest;
if (write_lhs > 0) {
mask = read_mask[write_lhs];
if (bitsize > write_rhs) {
*dest++ = (original & mask) | (data >> write_lhs);
original = *dest & write_mask[bitsize - write_rhs];
*dest = original | (data << write_rhs);
} else {
if ((bitsize - write_lhs) > 0)
mask = mask | write_mask[8 - (bitsize - write_lhs)];
*dest++ = (original & mask) | (data >> write_lhs);
}
} else {
if (bitsize < 8)
data = data | (original & write_mask[bitsize]);
*dest++ = data;
}
...
- 這個部分程式碼的目的是將資料從
data寫入至目的地*dest write_lhs為寫入的 offset，因此write_rhs代表*dest指向的那個 byte 中可以被寫入的 bit 數量- 整體的邏輯和讀取資料至
data類似，但需要特別處理被寫入處*dest的原始資料，使寫入範圍外的資料不變write_lhs的部分永遠是原始資料- 若
bitsize > write_rhs，代表需要繼續寫入資料至下一個 byte - 若
bitsize < write_rhs，代表寫入的資料後面還會接著共8 - write_lhs - bitsize個 bit 的原始資料write_mask主要是用在這個部分，只要使用original & write_mask[write_lhs + bitsize]就可以保留接在尾端的原始資料- 原本的寫法應該有錯，
write_mask[8 - (bitsize - write_lhs)]應該要寫成write_mask[write_lhs + bitsize]才對
改寫為更精簡且等效的程式碼
原本的寫法有幾個可以改善的部分，如
- 使用太多
if進行判斷，例如原本read_mask和write_mask的宣告就有包含當參數為 0 的 mask，無須再用if進行判斷是否為 0 - 部分程式行數具有相同的邏輯但寫法不一致，導致較難理解
- 針對複製的 bit 數量很大時進行優化，此時會先不斷以
bitsize = 8執行迴圈的內容，最後再處理尾段不足 8 bits 的資料，因此可以去除大部分的if判斷 read_mask和write_mask互為 bitwise NOT 的關係，可用write_mask[n] = ~read_mask[n]代替
...
//write_mask[n] = ~read_mask[n]
for (size_t count = _count >> 3; count > 0; count--) {
/* read data from source in to buffer */
data = *source++;
data = data << read_lhs | (*source >> read_rhs);
/* write data into dest */
original = *dest & (read_mask[write_lhs]);
*dest++ = original | (data >> write_lhs);
*dest = (*dest >> write_lhs) | (data << write_rhs);
}
_count &= 7;
data = *source++;
data = (data << read_lhs | (*source >> read_rhs)) & read_mask[_count];
original = *dest & (read_mask[write_lhs] | ~read_mask[write_lhs + _count]);
*dest++ = original | (data >> write_lhs);
if (_count > write_rhs)
*dest = (*dest & ~read_mask[_count - write_rhs]) | (data << write_rhs);
...
最後使用原本題目中的程式碼驗證，輸出結果無誤
效能差異
實驗的程式碼如下
static uint8_t output[800], input[800];
int main(int _argc, char **_argv)
{
memset(&input[0], 0xFF, sizeof(input));
for (int bit = 1; bit < 6000; bit++) {
struct timespec t_start, t_end;
memset(&output[0], 0x00, sizeof(output));
clock_gettime(CLOCK_MONOTONIC, &t_start);
bitcpy(&output[0], 5, &input[0], 3, bit); /* original method */
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t1 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
memset(&output[0], 0x00, sizeof(output));
clock_gettime(CLOCK_MONOTONIC, &t_start);
bitcpy_rewrite(&output[0], 5, &input[0], 3, bit); /* mymethod */
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t2 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
printf("%d %lld %lld\n", bit, t1, t2);
}
}
- 複製的 bit 長度為 0~6000
- 使用與 fibdrv 作業一樣的方法降低干擾
實驗結果如下
- 相較於題目中的寫法，我改寫後的方法可以節省約 33% 的時間
由於更動的部分主要是去除大量的 if，我嘗試使用 perf 來分析 branch 的差異
sudo perf stat --repeat 5 -e branch-instructions:u,branch-misses:u ./test
- 原本的寫法
Performance counter stats for './test' (5 runs):
15,934,530 branch-instructions:u ( +- 0.00% )
9,913 branch-misses:u # 0.06% of all branches ( +- 0.12% )
0.025568 +- 0.000629 seconds time elapsed ( +- 2.46% )
- 我改寫的方法
Performance counter stats for './test' (5 runs):
2,417,277 branch-instructions:u ( +- 0.00% )
8,614 branch-misses:u # 0.36% of all branches ( +- 0.21% )
0.018744 +- 0.000560 seconds time elapsed ( +- 2.99% )
可以清楚的看到，無論在 branch-instructions:u 還是 branch-misses:u 都有明顯的改善
在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境 (待補)
測驗 2
解題思路
#define NEXT_POWER_OF_2(s) \
VV1 \
? s \
: (size_t) 1 << (64 - __builtin_clzl(s)) /* next power of 2 */
- 從註解可以知道目的是找出最接近且大於等於 s 的
- 以 2 進位思考，
(s & (s - 1)) == 0 - 因此 VV1 應填入
(s & (s - 1)) == 0
static inline int ilog2(size_t n)
{
return 64 - __builtin_clzl(n) - ((n & (n - 1)) == 0);
}
- 用來計算
64 - __builtin_clzl(n)代表代入的數字如果不是((n & (n - 1)) == 0)來扣回去
接著從使用示範觀察 vector 的使用方式
v(float, 3, vec1);
v(int, 2, vec2, 13, 42);
查看相關的定義來了解 vector 實作的資料結構
#define STRUCT_BODY(type) \
struct { \
size_t size : 54, on_heap : 1, capacity : 6, flag1 : 1, flag2 : 1, \
flag3 : 1; \
type *ptr; \
}
#define v(t, s, name, ...) \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof((__typeof__(name.buf[0])[]){0, __VA_ARGS__}) / \
sizeof(name.buf[0]) - 1; \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
#define STRUCT_BODY(type)實現了讓 vector 可以在宣告時使用不同資料型態的功能#define v(t, s, name, ...)是實現 vector 宣告的核心，vector 本質上是union，定義內容的方式和第二周測驗題中以 C 語言重寫 folly::fbstring 的程式碼非常相似- 前 8 bytes 會用來記錄
sizecapacityflag，所以後面的size_t filler是用來避免此區域內容遭到複寫 - 初始記憶體空間使用 stack，最大的可用空間為
NEXT_POWER_OF_2(s) name是這個 vector 物件的名稱，同時結尾用{.buf = {__VA_ARGS__}}來根據輸入的參數初始化物件的內容__VA_ARGS__是 Variadic Macros，對應到v(t, s, name, ...)中的...，用來實現讓參數數量可以變動的功能__attribute__是 Attribute Syntax，在這裡用來於宣告物件時加上特定的屬性- 從 Common Variable Attributes 可以知道
cleanup(vec_free)的作用為當 vector 變數超出 scope 時會自動呼叫vec_free name.size是 vector 中已有資料的數量__typeof__的用法可參閱 Referring to a Type with typeof(__typeof__(name.buf[0])[]宣告一個資料型態跟name.buf[0]一樣的陣列，並且用後面的數值{0, __VA_ARGS__}進行初始化- 當宣告 vector 時沒有輸入任何參數，這個陣列會變成 Arrays of Length Zero，
{0, __VA_ARGS__}的 0 就是為了避免這個情況發生
name.capacity是 vector 中可容納的資料數量上限sizeof(name.buf[0])是 buf 中一個內容的大小sizeof(name.buf)是整個 buf 的大小
- 前 8 bytes 會用來記錄
#define vec_size(v) v.size
#define vec_capacity(v) \
(v.on_heap ? (size_t) 1 << v.capacity : sizeof(v.buf) / sizeof(v.buf[0]))
#define vec_data(v) (v.on_heap ? v.ptr : v.buf) /* always contiguous buffer */
#define vec_elemsize(v) sizeof(v.buf[0])
#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
#define vec_push_back(v, e) \
__vec_push_back(&v, &(__typeof__(v.buf[0])[]){e}, vec_elemsize(v), \
vec_capacity(v))
#define vec_pop_back(v) (void) (VV2)
/* This function attribute specifies function parameters that are not supposed
* to be null pointers. This enables the compiler to generate a warning on
* encountering such a parameter.
*/
#define NON_NULL __attribute__((nonnull))
vec_sizevec_capacityvec_datavec_elemsizevec_pos這幾個 macro 都是用來取用對應的資料vec_reserve和vec_push_back是為了讓相關的函式使用起來更直覺的 wrapper，相對應的函式實作後面會討論__attribute__((nonnull))會讓函式追加代入的參數不能是 null pointer 的屬性，詳見 Declaring Attributes of Functionsvec_pop_back的意義是將 vector 中最後的元素去除，size代表的是 vector 內含有的資料數量，因此 VV2 應填入v.size -= 1
static NON_NULL void vec_free(void *p)
{
STRUCT_BODY(void) *s = p;
if (s->on_heap)
free(s->ptr);
}
- 如果 vector 有使用 heap，需
free掉使用的部分
#define vec_reserve(v, n) __vec_reserve(&v, n, vec_elemsize(v), vec_capacity(v))
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
v->ptr = realloc(v->ptr,
elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
} else {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
- 變更指定的 vector 讓其至少具有能涵蓋 n 筆資料的 capacity，如果索求量沒有超過原本 capacity，就不進行變動
- 須注意此函式內用的區域變數
*v內定義的資料型態是char，所以在malloc與realloc空間時需再乘elemsize- 這種做法是為了讓 vector 的資料能使用任意資料型態
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
- 將資料存在 vector 末端
- 如果空間不夠，就先擴張空間
- 原本在 heap 上就使用
realloc改變空間 - 原本在 stack 上就
malloc空間然後把資料複製過去
- 原本在 heap 上就使用
另外，在測試的程式碼中有一個這樣的用法
#define display(v) \
do { \
for (size_t i = 0; i < vec_size(v); i++) \
printf("%.2f ", vec_pos(v, i)); \
puts(v.on_heap ? "heap" : "stack"); \
} while (0)
- 如果要在 macro 中使用多個 statement，單純用
{}框起來在 macro 展開後會造成語法錯誤，因此可用do {} while (0)來滿足這個需求
上述實作的限制並提出改進方案
vec_pop_back
-#define vec_pop_back(v) (void) (v.size -= 1)
+#define vec_pop_back(v) (void) (v.size -= !!v.size)
- 原本的寫法如果在
v.size = 0時會引發 Segmentation fault (core dumped)，改寫後可避免此狀況發生
vec_pos(v, n)
-#define vec_pos(v, n) vec_data(v)[n] /* lvalue */
+#define vec_pos(v, n) *(__typeof__(v.buf[0]) *) _vec_pos(&v, n, vec_elemsize(v))
static NON_NULL void *_vec_pos(void *vec,
size_t n,
size_t elemsize)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
assert(v->size > n);
return (void *)
((v->on_heap ? v->ptr : v->buf) + n * elemsize);
}
- 一樣是原本的寫法沒有檢查邊界，但比較麻煩的地方是 vector 的資料型態不固定，如果直接在 macro 中使用
assert檢查邊界，又會導致vec_pos沒辦法直接當成printf的參數使用 - 最後想到可以先回傳
void *然後再於 macro 中使用__typeof__來轉換到對應的型態 - 整體寫法類似
vec_reserve中 wrapper 的寫法
v(t, s, name, ...)
#define v(t, s, name, ...) \
+ _Static_assert(strncmp(#t, "void", 4), "error type"); \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
t buf[NEXT_POWER_OF_2(s)]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof( (__typeof__(name.buf[0])[]){__VA_ARGS__} ) / \
sizeof(name.buf[0]); \
name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
- 原本的寫法可以允許
t是void*，而且會成功編譯 void不用特別處理，因為t buf[NEXT_POWER_OF_2(s)]的部分就會導致編譯錯誤error: declaration of ‘buf’ as array of voids- 參考第 2 周測驗題使用 _Static_assert
_Static_assert中要求只能使用 constant expression 來進行判斷，但一開始想不到如何使用 constant expression 來判斷字串，查詢後發現可以用strncmp- 原因是 gcc 有將它列入 Built-in Functions，所以可以在 compile time 的時候 evaluate
strncmp只比對前 4 字元是為了同時檢查void *和void*這兩種型態
Memory Handling
folly::fbvector 一開始就提到配置動態記憶體大小使用的 growth factor 會影響效能，其中 2 是一個不建議的數值，因為任何新配置的記憶體大小一定會大於之前配置過的記憶體的總和，造成 vector 無法重新利用曾經配置的空間。這點可以由下式驗證，例如欲配置的空間大小是
最理想的方案是使用與 allocator 相同的策略，如此一來可以有最佳的使用效率，但單純使用 realloc 沒辦法達成，所以 folly::fbvector 才會使用 jemalloc。
很重要的發現！在後續的作業 (如 kcalc 及 kecho) 可運用客製化的 memory allocator
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
使用 1.5 作為 growth factor 的輔助函式
嘗試使用 1.5 作為 growth factor，這裡以資料筆數做為計算的依據，而不是使用實際配置的記憶體大小，會這麼決定有幾個原因
- 不是每個數字都適合成為記憶體大小，例如說 91 bytes
- 可以用一套一樣的邏輯管理不同資料型態的 vector
- 程式碼的更動比較少
在實做更動以前，須先完成相關的輔助函式
#define FACTOR 1.5
#define CHUNK_SIZE 4
static inline float ilog_factor(float n) /* log1.5(n) = log2(n)/log2(1.5)*/
{
return ceilf(log2f(n)/log2f(FACTOR));
}
- 根據容量計算最接近的 capacity 比較麻煩，無法像以 2 為底進行計算時單純使用 bitwise shift
- 根據
- 最大可用資料數量為
#define vec_capacity(v) __vec_capacity(&v)
static size_t inline __vec_capacity(void *vec)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
return (size_t) (pow(1.5, v->capacity) * CHUNK_SIZE);
}
return CHUNK_SIZE;
}
- 原本的
vec_capacity沒辦法直接以 macro 的方式寫，改以函式寫 - 單純只是要算得數字沒問題，但要兼顧速度就非常困難，牽涉到浮點數的運算，運算成本一定會增加
以 CHUNK_SIZE = 4 FACTOR = 1.5 為例，修改後的資料筆數會以如下方式成長
4 6 9 13 20 30 45 ...
驗證數值正確性
用以下程式碼驗證，結果無誤
int main(int _argc, char **_argv)
{
for (int i = 4; i < 4097; i++) {
int capacity = ilog_factor((float)i/CHUNK_SIZE);
int full_size = (size_t) (pow(1.5, capacity) * CHUNK_SIZE);
assert(i <= full_size);
//printf("input: %d capacity: %d full size: %d\n", i, capacity, full_size);
}
}
計算數字的速度差異
實際比對以 1.5 與 2 做為 growth factor 時，計算 capacity 以及最大可用容量時的時間
#define FACTOR 1.5
#define CHUNK_SIZE 8.0
int main(int _argc, char **_argv)
{
struct timespec t_start, t_end;
int result = 0;
for (int i = 4; i < 4097; i++) {
clock_gettime(CLOCK_MONOTONIC, &t_start);
result = ilog2(i); /* original method */
//result = 1 << result;
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t1 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
clock_gettime(CLOCK_MONOTONIC, &t_start);
result = ilog_factor((float)i/CHUNK_SIZE); /* mymethod */
//result = (size_t) (pow(1.5, result) * CHUNK_SIZE);
clock_gettime(CLOCK_MONOTONIC, &t_end);
long long t2 = (long long)(t_end.tv_sec * 1e9 + t_end.tv_nsec)
- (long long)(t_start.tv_sec * 1e9 + t_start.tv_nsec);
printf("%d %lld %lld\n", i, t1, t2);
}
return 0;
}
ilog_facor的計算時間約為ilog2的 2 倍
pow(1.5, capacity)的時間約為1 << capacity的 3~4 倍- 以
pow計算次方值為常數時間，比用遞迴的方式好
修改 growth factor 為 1.5 (待補)
原本宣告 vector 的 macro 中是使用 t buf[NEXT_POWER_OF_2(s)] 來設置最初在 stack 占用的空間，我改為固定以 CHUNK_SIZE = 4 作為起始大小，主要是現階段以固定 chunk size 的實作比較簡單
#define v(t, s, name, ...) \
_Static_assert(strncmp(#t, "void", 4), "error type"); \
union { \
STRUCT_BODY(t); \
struct { \
size_t filler; \
- t buf[NEXT_POWER_OF_2(s)]; \
+ t buf[CHUNK_SIZE]; \
}; \
} name __attribute__((cleanup(vec_free))) = {.buf = {__VA_ARGS__}}; \
name.size = sizeof( (__typeof__(name.buf[0])[]){0, __VA_ARGS__} ) / \
sizeof(name.buf[0]) - 1; \
- name.capacity = sizeof(name.buf) / sizeof(name.buf[0])
+ name.capacity = 0
會動到記憶體配置的 __vec_push_back 與 __vec_push_back 也須做相對應的更動
static NON_NULL void __vec_reserve(void *vec,
size_t n,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(void);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (n > capacity) {
if (v->on_heap) {
- v->ptr = realloc(v->ptr,
- elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
+ v->ptr = realloc(v->ptr, elemsize * (size_t)
+ (pow(1.5, (v->capacity = ilog_factor((float) n / CHUNK_SIZE))) * CHUNK_SIZE));
} else {
void *tmp =
- malloc(elemsize * (size_t) 1 << (v->capacity = ilog2(n)));
+ malloc(elemsize * (size_t)
+ (pow(1.5, (v->capacity = ilog_factor((float) n / CHUNK_SIZE))) * CHUNK_SIZE));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
}
}
}
static NON_NULL void __vec_push_back(void *restrict vec,
void *restrict e,
size_t elemsize,
size_t capacity)
{
union {
STRUCT_BODY(char);
struct {
size_t filler;
char buf[];
};
} *v = vec;
if (v->on_heap) {
if (v->size == capacity)
- v->ptr = realloc(v->ptr, elemsize * (size_t) 1 << ++v->capacity);
+ v->ptr = realloc(v->ptr, elemsize * (size_t)
+ (pow(1.5, ++v->capacity) * CHUNK_SIZE));
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else {
if (v->size == capacity) {
void *tmp =
- malloc(elemsize * (size_t) 1 << (v->capacity = capacity + 1));
+ malloc(elemsize * (size_t) (pow(1.5, ++v->capacity) * CHUNK_SIZE));
memcpy(tmp, v->buf, elemsize * v->size);
v->ptr = tmp;
v->on_heap = 1;
memcpy(&v->ptr[v->size++ * elemsize], e, elemsize);
} else
memcpy(&v->buf[v->size++ * elemsize], e, elemsize);
}
}
