Tweaks to array implementation, including changing how the bits are

allocated, making more explicit checks for refcounts and max values,
optimizations for certain methods, and adding compile-time errors for
arrays that hold items that are too large.

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 {
diff --git a/compile.c b/compile.c
index 3891f66e..1692d12b 100644
--- a/compile.c
+++ b/compile.c
@@ -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: {