diff options
| -rw-r--r-- | builtins/array.c | 109 | ||||
| -rw-r--r-- | builtins/array.h | 5 | ||||
| -rw-r--r-- | builtins/datatypes.h | 24 | ||||
| -rw-r--r-- | compile.c | 7 | ||||
| -rw-r--r-- | typecheck.c | 3 |
5 files changed, 106 insertions, 42 deletions
diff --git a/builtins/array.c b/builtins/array.c index 9b0e4206..cd326405 100644 --- a/builtins/array.c +++ b/builtins/array.c @@ -58,8 +58,8 @@ public void Array$insert(array_t *arr, const void *item, int64_t index, int64_t arr->free = 4; arr->data = arr->atomic ? GC_MALLOC_ATOMIC(arr->free * padded_item_size) : GC_MALLOC(arr->free * padded_item_size); arr->stride = padded_item_size; - } else if (arr->free < 1 || arr->data_refcount || (int64_t)arr->stride != padded_item_size) { - arr->free = MAX(15, MIN(1, arr->length/4)); + } else if (arr->free < 1 || arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) { + arr->free = MAX(ARRAY_MAX_FREE_ENTRIES, MIN(1, arr->length/4)); void *copy = arr->atomic ? GC_MALLOC_ATOMIC((arr->length + arr->free) * padded_item_size) : GC_MALLOC((arr->length + arr->free) * padded_item_size); for (int64_t i = 0; i < index-1; i++) memcpy(copy + i*padded_item_size, arr->data + arr->stride*i, padded_item_size); @@ -80,31 +80,73 @@ public void Array$insert(array_t *arr, const void *item, int64_t index, int64_t public void Array$insert_all(array_t *arr, array_t to_insert, int64_t index, int64_t padded_item_size) { + if (to_insert.length == 0) + return; + + if (!arr->data) { + *arr = to_insert; + ARRAY_INCREF(*arr); + return; + } + if (index < 1) index = arr->length + index + 1; if (index < 1) index = 1; else if (index > (int64_t)arr->length + 1) index = (int64_t)arr->length + 1; - if (!arr->data) { - arr->free = to_insert.length; - arr->data = arr->atomic ? GC_MALLOC_ATOMIC(padded_item_size*arr->free) : GC_MALLOC(padded_item_size*arr->free); - } else if ((int64_t)arr->free < (int64_t)to_insert.length || arr->data_refcount || (int64_t)arr->stride != padded_item_size) { - arr->free = to_insert.length; - void *copy = arr->atomic ? GC_MALLOC_ATOMIC((arr->length + arr->free) * padded_item_size) : GC_MALLOC((arr->length + arr->free) * padded_item_size); - for (int64_t i = 0; i < index-1; i++) - memcpy(copy + i*padded_item_size, arr->data + arr->stride*i, padded_item_size); - for (int64_t i = index-1; i < (int64_t)arr->length; i++) - memcpy(copy + (i+to_insert.length)*padded_item_size, arr->data + arr->stride*i, padded_item_size); - arr->data = copy; - arr->data_refcount = 0; - } else { + if ((int64_t)arr->free >= (int64_t)to_insert.length // Adequate free space + && arr->data_refcount == 0 // Not aliased memory + && (int64_t)arr->stride == padded_item_size) { // Contiguous array + // If we can fit this within the array's preallocated free space, do that: + arr->free -= to_insert.length; + arr->length += to_insert.length; if (index != arr->length+1) - memmove((void*)arr->data + index*padded_item_size, arr->data + (index-1)*padded_item_size, (arr->length - index + to_insert.length-1)*padded_item_size); + memmove((void*)arr->data + index*padded_item_size, + arr->data + (index-1)*padded_item_size, + (arr->length - index + to_insert.length-1)*padded_item_size); + for (int64_t i = 0; i < to_insert.length; i++) + memcpy((void*)arr->data + (index-1 + i)*padded_item_size, + to_insert.data + i*to_insert.stride, padded_item_size); + } else { + // Otherwise, allocate a new chunk of memory for the array and populate it: + int64_t new_len = arr->length + to_insert.length; + arr->free = MAX(ARRAY_MAX_FREE_ENTRIES, MIN(1, new_len/4)); + void *data = arr->atomic ? GC_MALLOC_ATOMIC((new_len + arr->free) * padded_item_size) + : GC_MALLOC((new_len + arr->free) * padded_item_size); + void *p = data; + + // Copy first chunk of `arr` if needed: + if (index > 1) { + if (arr->stride == padded_item_size) { + p = mempcpy(p, arr->data, (index-1)*padded_item_size); + } else { + for (int64_t i = 0; i < index-1; i++) + p = mempcpy(p, arr->data + arr->stride*i, padded_item_size); + } + } + + // Copy `to_insert` + if (to_insert.stride == padded_item_size) { + p = mempcpy(p, to_insert.data, to_insert.length*padded_item_size); + } else { + for (int64_t i = 0; i < index-1; i++) + p = mempcpy(p, to_insert.data + to_insert.stride*i, padded_item_size); + } + + // Copy last chunk of `arr` if needed: + if (index < arr->length + 1) { + if (arr->stride == padded_item_size) { + p = mempcpy(p, arr->data + padded_item_size*(index-1), (arr->length - index + 1)*padded_item_size); + } else { + for (int64_t i = index-1; i < arr->length-1; i++) + p = mempcpy(p, arr->data + arr->stride*i, padded_item_size); + } + } + arr->length = new_len; + arr->stride = padded_item_size; + arr->data = data; + arr->data_refcount = 0; } - arr->free -= to_insert.length; - arr->length += to_insert.length; - for (int64_t i = 0; i < to_insert.length; i++) - memcpy((void*)arr->data + (index-1 + i)*padded_item_size, to_insert.data + i*to_insert.stride, padded_item_size); } public void Array$remove(array_t *arr, int64_t index, int64_t count, int64_t padded_item_size) @@ -116,12 +158,12 @@ public void Array$remove(array_t *arr, int64_t index, int64_t count, int64_t pad if (count > arr->length - index + 1) count = (arr->length - index) + 1; - // TODO: optimize arr.remove(1) by just updating the .data and .length values - - if (index + count > arr->length) { + if (index == 1) { + arr->data += arr->stride * count; + } else if (index + count > arr->length) { if (arr->free >= 0) arr->free += count; - } else if (arr->data_refcount || (int64_t)arr->stride != padded_item_size) { + } else if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) { void *copy = arr->atomic ? GC_MALLOC_ATOMIC((arr->length-1) * padded_item_size) : GC_MALLOC((arr->length-1) * padded_item_size); for (int64_t src = 1, dest = 1; src <= (int64_t)arr->length; src++) { if (src < index || src >= index + count) { @@ -137,11 +179,12 @@ public void Array$remove(array_t *arr, int64_t index, int64_t count, int64_t pad arr->free += count; } arr->length -= count; + if (arr->length == 0) arr->data = NULL; } public void Array$sort(array_t *arr, closure_t comparison, int64_t padded_item_size) { - if (arr->data_refcount || (int64_t)arr->stride != padded_item_size) + if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) Array$compact(arr, padded_item_size); qsort_r(arr->data, arr->length, padded_item_size, comparison.fn, comparison.userdata); @@ -149,14 +192,14 @@ public void Array$sort(array_t *arr, closure_t comparison, int64_t padded_item_s public array_t Array$sorted(array_t arr, closure_t comparison, int64_t padded_item_size) { - arr.data_refcount = 3; - Array$sort(&arr, comparison, padded_item_size); + Array$compact(&arr, padded_item_size); + qsort_r(arr.data, arr.length, padded_item_size, comparison.fn, comparison.userdata); return arr; } public void Array$shuffle(array_t *arr, int64_t padded_item_size) { - if (arr->data_refcount || (int64_t)arr->stride != padded_item_size) + if (arr->data_refcount != 0 || (int64_t)arr->stride != padded_item_size) Array$compact(arr, padded_item_size); char tmp[padded_item_size]; @@ -295,7 +338,7 @@ public array_t Array$by(array_t array, int64_t stride, int64_t padded_item_size) { // In the unlikely event that the stride value would be too large to fit in // a 15-bit integer, fall back to creating a copy of the array: - if (__builtin_expect(array.stride*stride < MIN_STRIDE || array.stride*stride > MAX_STRIDE, 0)) { + if (__builtin_expect(array.stride*stride < ARRAY_MIN_STRIDE || array.stride*stride > ARRAY_MAX_STRIDE, 0)) { void *copy = NULL; int64_t len = (stride < 0 ? array.length / -stride : array.length / stride) + ((array.length % stride) != 0); if (len > 0) { @@ -330,7 +373,7 @@ public array_t Array$reversed(array_t array, int64_t padded_item_size) // 15-bit integer, fall back to Array$by()'s more general method of copying // the array. This should only happen if array.stride is MIN_STRIDE to // begin with (very unlikely). - if (__builtin_expect(-array.stride < MIN_STRIDE || -array.stride > MAX_STRIDE, 0)) + if (__builtin_expect(-array.stride < ARRAY_MIN_STRIDE || -array.stride > ARRAY_MAX_STRIDE, 0)) return Array$by(array, -1, padded_item_size); array_t reversed = array; @@ -529,7 +572,7 @@ public void Array$heap_push(array_t *heap, const void *item, closure_t compariso Array$insert(heap, item, 0, padded_item_size); if (heap->length > 1) { - if (heap->data_refcount > 0) + if (heap->data_refcount != 0) Array$compact(heap, padded_item_size); siftdown(heap, 0, heap->length-1, comparison, padded_item_size); } @@ -546,7 +589,7 @@ public void Array$heap_pop(array_t *heap, closure_t comparison, int64_t padded_i heap->data += heap->stride; --heap->length; } else { - if (heap->data_refcount > 0) + if (heap->data_refcount != 0) Array$compact(heap, padded_item_size); memcpy(heap->data, heap->data + heap->stride*(heap->length-1), padded_item_size); --heap->length; @@ -556,7 +599,7 @@ public void Array$heap_pop(array_t *heap, closure_t comparison, int64_t padded_i public void Array$heapify(array_t *heap, closure_t comparison, int64_t padded_item_size) { - if (heap->data_refcount > 0) + if (heap->data_refcount != 0) Array$compact(heap, padded_item_size); ARRAY_INCREF(*heap); diff --git a/builtins/array.h b/builtins/array.h index 6d5c3015..cefea807 100644 --- a/builtins/array.h +++ b/builtins/array.h @@ -49,8 +49,9 @@ .data=memcpy(is_atomic(x) ? GC_MALLOC_ATOMIC(sizeof(items)) : GC_MALLOC(sizeof(items)), items, sizeof(items)), \ .atomic=is_atomic(x), \ .data_refcount=1}; }) -#define ARRAY_INCREF(arr) (arr).data_refcount |= ((arr).data_refcount << 1) | 1 -#define ARRAY_DECREF(arr) (arr).data_refcount &= 2 +// Array refcounts use a saturating add, where once it's at the max value, it stays there. +#define ARRAY_INCREF(arr) (arr).data_refcount += ((arr).data_refcount < ARRAY_MAX_DATA_REFCOUNT) +#define ARRAY_DECREF(arr) (arr).data_refcount -= ((arr).data_refcount < ARRAY_MAX_DATA_REFCOUNT) #define Array$insert_value(arr, item_expr, index, padded_item_size) ({ __typeof(item_expr) item = item_expr; Array$insert(arr, &item, index, padded_item_size); }) void Array$insert(array_t *arr, const void *item, int64_t index, int64_t padded_item_size); diff --git a/builtins/datatypes.h b/builtins/datatypes.h index 738dc5c3..1b522394 100644 --- a/builtins/datatypes.h +++ b/builtins/datatypes.h @@ -5,14 +5,28 @@ #include <stdint.h> #include <stdbool.h> -#define MIN_STRIDE (INT16_MIN>>1) -#define MAX_STRIDE (INT16_MAX>>1) +#define ARRAY_LENGTH_BITS 42 +#define ARRAY_FREE_BITS 5 +#define ARRAY_REFCOUNT_BITS 4 +#define ARRAY_STRIDE_BITS 12 + +#define MAX_FOR_N_BITS(N) ((1<<(N))-1) +#define ARRAY_MAX_STRIDE MAX_FOR_N_BITS(ARRAY_STRIDE_BITS-1) +#define ARRAY_MIN_STRIDE (~MAX_FOR_N_BITS(ARRAY_STRIDE_BITS-1)) +#define ARRAY_MAX_DATA_REFCOUNT MAX_FOR_N_BITS(ARRAY_REFCOUNT_BITS) +#define ARRAY_MAX_FREE_ENTRIES MAX_FOR_N_BITS(ARRAY_FREE_BITS) + typedef struct { void *data; - int64_t length:42; - uint8_t free:4, data_refcount:2; + // All of the following fields add up to 64 bits, which means that array + // structs can be passed in two 64-bit registers. C will handle doing the + // bit arithmetic to extract the necessary values, which is cheaper than + // spilling onto the stack and needing to retrieve data from the stack. + int64_t length:ARRAY_LENGTH_BITS; + uint8_t free:ARRAY_FREE_BITS; bool atomic:1; - int16_t stride:15; + uint8_t data_refcount:ARRAY_REFCOUNT_BITS; + int16_t stride:ARRAY_STRIDE_BITS; } array_t; typedef struct { @@ -1633,12 +1633,15 @@ CORD compile(env_t *env, ast_t *ast) "})"); } case Array: { + type_t *array_type = get_type(env, ast); + if (padded_type_size(Match(array_type, ArrayType)->item_type) > ARRAY_MAX_STRIDE) + code_err(ast, "This array holds items that take up %ld bytes, but the maximum supported size is %ld bytes. Consider using an array of pointers instead.", + padded_type_size(Match(array_type, ArrayType)->item_type), ARRAY_MAX_STRIDE); + auto array = Match(ast, Array); if (!array->items) return "(array_t){.length=0}"; - type_t *array_type = get_type(env, ast); - int64_t n = 0; for (ast_list_t *item = array->items; item; item = item->next) { ++n; diff --git a/typecheck.c b/typecheck.c index 9e94ea2f..10c5820f 100644 --- a/typecheck.c +++ b/typecheck.c @@ -49,6 +49,9 @@ type_t *parse_type_ast(env_t *env, type_ast_t *ast) if (!item_t) code_err(item_type, "I can't figure out what this type is."); if (has_stack_memory(item_t)) code_err(item_type, "Arrays can't have stack references because the array may outlive the stack frame."); + if (padded_type_size(item_t) > ARRAY_MAX_STRIDE) + code_err(ast, "This array holds items that take up %ld bytes, but the maximum supported size is %ld bytes. Consider using an array of pointers instead.", + padded_type_size(item_t), ARRAY_MAX_STRIDE); return Type(ArrayType, .item_type=item_t); } case TableTypeAST: { |