You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucy.apache.org by nw...@apache.org on 2015/07/14 16:05:51 UTC
[1/6] lucy-clownfish git commit: Rework Vector oversizing
Repository: lucy-clownfish
Updated Branches:
refs/heads/master 6608f2b05 -> 6090c3153
Rework Vector oversizing
Make Vector use its own oversizing logic. Grow buffer by 25%, but at
least four elements. Rework inline functions and error paths to allow
better code generation.
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/5eb638ea
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/5eb638ea
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/5eb638ea
Branch: refs/heads/master
Commit: 5eb638ea8cb975cad2596fd52c21d5f34975684f
Parents: 6608f2b
Author: Nick Wellnhofer <we...@aevum.de>
Authored: Tue Jul 14 12:45:29 2015 +0200
Committer: Nick Wellnhofer <we...@aevum.de>
Committed: Tue Jul 14 13:54:10 2015 +0200
----------------------------------------------------------------------
runtime/core/Clownfish/Vector.c | 73 +++++++++++++++++++++++++++---------
1 file changed, 55 insertions(+), 18 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5eb638ea/runtime/core/Clownfish/Vector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c
index 3f72eea..1108ceb 100644
--- a/runtime/core/Clownfish/Vector.c
+++ b/runtime/core/Clownfish/Vector.c
@@ -27,7 +27,16 @@
#include "Clownfish/Util/SortUtils.h"
static CFISH_INLINE void
-SI_grow_and_oversize(Vector *self, size_t addend1, size_t addend2);
+SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2);
+
+static void
+S_grow_and_oversize(Vector *self, size_t min_size);
+
+static CFISH_INLINE void
+SI_grow(Vector *self, size_t capacity);
+
+static void
+S_overflow_error(void);
Vector*
Vec_new(size_t capacity) {
@@ -80,14 +89,14 @@ Vec_Clone_IMP(Vector *self) {
void
Vec_Push_IMP(Vector *self, Obj *element) {
- SI_grow_and_oversize(self, self->size, 1);
+ SI_add_grow_and_oversize(self, self->size, 1);
self->elems[self->size] = element;
self->size++;
}
void
Vec_Push_All_IMP(Vector *self, Vector *other) {
- SI_grow_and_oversize(self, self->size, other->size);
+ SI_add_grow_and_oversize(self, self->size, other->size);
// Copy and incref.
Obj **dest = self->elems + self->size;
@@ -115,7 +124,7 @@ Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
return;
}
- SI_grow_and_oversize(self, self->size, 1);
+ SI_add_grow_and_oversize(self, self->size, 1);
memmove(self->elems + tick + 1, self->elems + tick,
(self->size - tick) * sizeof(Obj*));
self->elems[tick] = elem;
@@ -124,7 +133,7 @@ Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
void
Vec_Insert_All_IMP(Vector *self, size_t tick, Vector *other) {
- SI_grow_and_oversize(self, tick, other->size);
+ SI_add_grow_and_oversize(self, tick, other->size);
if (tick < self->size) {
memmove(self->elems + tick + other->size, self->elems + tick,
@@ -156,7 +165,7 @@ Vec_Fetch_IMP(Vector *self, size_t num) {
void
Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) {
- SI_grow_and_oversize(self, tick, 1);
+ SI_add_grow_and_oversize(self, tick, 1);
if (tick < self->size) {
DECREF(self->elems[tick]);
}
@@ -171,11 +180,7 @@ Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) {
void
Vec_Grow_IMP(Vector *self, size_t capacity) {
if (capacity > self->cap) {
- if (capacity > SIZE_MAX / sizeof(Obj*)) {
- THROW(ERR, "Vector index overflow");
- }
- self->elems = (Obj**)REALLOCATE(self->elems, capacity * sizeof(Obj*));
- self->cap = capacity;
+ SI_grow(self, capacity);
}
}
@@ -298,16 +303,48 @@ Vec_Slice_IMP(Vector *self, size_t offset, size_t length) {
// Ensure that the vector's capacity is at least (addend1 + addend2).
// If the vector must be grown, oversize the allocation.
+static CFISH_INLINE void
+SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2) {
+ size_t min_size = addend1 + addend2;
+ // Check for overflow.
+ if (min_size < addend1) {
+ S_overflow_error();
+ return;
+ }
+
+ if (min_size > self->cap) {
+ S_grow_and_oversize(self, min_size);
+ }
+}
+
static void
-SI_grow_and_oversize(Vector *self, size_t addend1, size_t addend2) {
- size_t new_size = addend1 + addend2;
+S_grow_and_oversize(Vector *self, size_t min_size) {
+ // Oversize by 25%, but at least four elements.
+ size_t extra = min_size / 4;
+ if (extra < 4) { extra = 4; }
+
+ size_t capacity = min_size + extra;
// Check for overflow.
- if (new_size < addend1) {
- THROW(ERR, "Vector index overflow");
+ if (capacity < min_size) {
+ S_overflow_error();
+ return;
}
- if (new_size > self->cap) {
- size_t capacity = Memory_oversize(new_size, sizeof(Obj*));
- Vec_Grow(self, capacity);
+
+ SI_grow(self, capacity);
+}
+
+static CFISH_INLINE void
+SI_grow(Vector *self, size_t capacity) {
+ if (capacity > SIZE_MAX / sizeof(Obj*)) {
+ S_overflow_error();
+ return;
}
+ self->elems = (Obj**)REALLOCATE(self->elems, capacity * sizeof(Obj*));
+ self->cap = capacity;
+}
+
+static void
+S_overflow_error() {
+ THROW(ERR, "Vector index overflow");
}
[4/6] lucy-clownfish git commit: Helper function to copy array
elements
Posted by nw...@apache.org.
Helper function to copy array elements
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/5b9e3164
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/5b9e3164
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/5b9e3164
Branch: refs/heads/master
Commit: 5b9e31643c53c72b1fb8ddba32fed034102855aa
Parents: 5eb638e
Author: Nick Wellnhofer <we...@aevum.de>
Authored: Tue Jul 14 12:58:03 2015 +0200
Committer: Nick Wellnhofer <we...@aevum.de>
Committed: Tue Jul 14 13:54:13 2015 +0200
----------------------------------------------------------------------
runtime/core/Clownfish/Vector.c | 41 ++++++++++++------------------------
1 file changed, 14 insertions(+), 27 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5b9e3164/runtime/core/Clownfish/Vector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c
index 1108ceb..4cdfa96 100644
--- a/runtime/core/Clownfish/Vector.c
+++ b/runtime/core/Clownfish/Vector.c
@@ -27,6 +27,9 @@
#include "Clownfish/Util/SortUtils.h"
static CFISH_INLINE void
+SI_copy_and_incref(Obj **dst, Obj **src, size_t num);
+
+static CFISH_INLINE void
SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2);
static void
@@ -76,13 +79,7 @@ Vector*
Vec_Clone_IMP(Vector *self) {
Vector *twin = Vec_new(self->size);
twin->size = self->size;
-
- // Copy and incref.
- Obj **elems = self->elems;
- Obj **twin_elems = twin->elems;
- for (size_t i = 0, max = self->size; i < max; i++) {
- twin_elems[i] = INCREF(elems[i]);
- }
+ SI_copy_and_incref(twin->elems, self->elems, self->size);
return twin;
}
@@ -97,14 +94,7 @@ Vec_Push_IMP(Vector *self, Obj *element) {
void
Vec_Push_All_IMP(Vector *self, Vector *other) {
SI_add_grow_and_oversize(self, self->size, other->size);
-
- // Copy and incref.
- Obj **dest = self->elems + self->size;
- Obj **other_elems = other->elems;
- for (size_t i = 0, max = other->size; i < max; i++) {
- dest[i] = INCREF(other_elems[i]);
- }
-
+ SI_copy_and_incref(self->elems + self->size, other->elems, other->size);
self->size += other->size;
}
@@ -144,13 +134,7 @@ Vec_Insert_All_IMP(Vector *self, size_t tick, Vector *other) {
(tick - self->size) * sizeof(Obj*));
}
- // Copy and incref.
- Obj **dest = self->elems + tick;
- Obj **other_elems = other->elems;
- for (size_t i = 0, max = other->size; i < max; i++) {
- dest[i] = INCREF(other_elems[i]);
- }
-
+ SI_copy_and_incref(self->elems + tick, other->elems, other->size);
self->size = tick + other->size;
}
@@ -292,15 +276,18 @@ Vec_Slice_IMP(Vector *self, size_t offset, size_t length) {
// Copy elements.
Vector *slice = Vec_new(length);
slice->size = length;
- Obj **slice_elems = slice->elems;
- Obj **my_elems = self->elems;
- for (size_t i = 0; i < length; i++) {
- slice_elems[i] = INCREF(my_elems[offset + i]);
- }
+ SI_copy_and_incref(slice->elems, self->elems + offset, length);
return slice;
}
+static CFISH_INLINE void
+SI_copy_and_incref(Obj **dst, Obj **src, size_t num) {
+ for (size_t i = 0; i < num; i++) {
+ dst[i] = INCREF(src[i]);
+ }
+}
+
// Ensure that the vector's capacity is at least (addend1 + addend2).
// If the vector must be grown, oversize the allocation.
static CFISH_INLINE void
[3/6] lucy-clownfish git commit: Fix Vec_Insert_All
Posted by nw...@apache.org.
Fix Vec_Insert_All
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/5153beff
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/5153beff
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/5153beff
Branch: refs/heads/master
Commit: 5153beff28d3066da42bdee782875e75168a508c
Parents: cd34607
Author: Nick Wellnhofer <we...@aevum.de>
Authored: Tue Jul 14 13:24:16 2015 +0200
Committer: Nick Wellnhofer <we...@aevum.de>
Committed: Tue Jul 14 13:54:13 2015 +0200
----------------------------------------------------------------------
runtime/core/Clownfish/Test/TestVector.c | 46 ++++++++++++++++++++++++++-
runtime/core/Clownfish/Vector.c | 7 ++--
2 files changed, 49 insertions(+), 4 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5153beff/runtime/core/Clownfish/Test/TestVector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Test/TestVector.c b/runtime/core/Clownfish/Test/TestVector.c
index aad8369..1a72768 100644
--- a/runtime/core/Clownfish/Test/TestVector.c
+++ b/runtime/core/Clownfish/Test/TestVector.c
@@ -179,6 +179,49 @@ test_Push_Pop_Insert(TestBatchRunner *runner) {
}
static void
+test_Insert_All(TestBatchRunner *runner) {
+ size_t i;
+
+ {
+ Vector *dst = Vec_new(20);
+ Vector *src = Vec_new(10);
+ Vector *wanted = Vec_new(30);
+
+ for (i = 0; i < 10; i++) { Vec_Push(dst, (Obj*)Int_new(i)); }
+ for (i = 0; i < 10; i++) { Vec_Push(dst, (Obj*)Int_new(i + 20)); }
+ for (i = 0; i < 10; i++) { Vec_Push(src, (Obj*)Int_new(i + 10)); }
+ for (i = 0; i < 30; i++) { Vec_Push(wanted, (Obj*)Int_new(i)); }
+
+ Vec_Insert_All(dst, 10, src);
+ TEST_TRUE(runner, Vec_Equals(dst, (Obj*)wanted), "Insert_All between");
+
+ DECREF(wanted);
+ DECREF(src);
+ DECREF(dst);
+ }
+
+ {
+ Vector *dst = Vec_new(10);
+ Vector *src = Vec_new(10);
+ Vector *wanted = Vec_new(30);
+
+ for (i = 0; i < 10; i++) { Vec_Push(dst, (Obj*)Int_new(i)); }
+ for (i = 0; i < 10; i++) { Vec_Push(src, (Obj*)Int_new(i + 20)); }
+ for (i = 0; i < 10; i++) { Vec_Push(wanted, (Obj*)Int_new(i)); }
+ for (i = 0; i < 10; i++) {
+ Vec_Store(wanted, i + 20, (Obj*)Int_new(i + 20));
+ }
+
+ Vec_Insert_All(dst, 20, src);
+ TEST_TRUE(runner, Vec_Equals(dst, (Obj*)wanted), "Insert_All after");
+
+ DECREF(wanted);
+ DECREF(src);
+ DECREF(dst);
+ }
+}
+
+static void
test_Delete(TestBatchRunner *runner) {
Vector *wanted = Vec_new(5);
Vector *got = Vec_new(5);
@@ -474,10 +517,11 @@ test_Grow(TestBatchRunner *runner) {
void
TestVector_Run_IMP(TestVector *self, TestBatchRunner *runner) {
- TestBatchRunner_Plan(runner, (TestBatch*)self, 59);
+ TestBatchRunner_Plan(runner, (TestBatch*)self, 61);
test_Equals(runner);
test_Store_Fetch(runner);
test_Push_Pop_Insert(runner);
+ test_Insert_All(runner);
test_Delete(runner);
test_Resize(runner);
test_Excise(runner);
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5153beff/runtime/core/Clownfish/Vector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c
index 7f87fa1..2973e5b 100644
--- a/runtime/core/Clownfish/Vector.c
+++ b/runtime/core/Clownfish/Vector.c
@@ -127,19 +127,20 @@ Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
void
Vec_Insert_All_IMP(Vector *self, size_t tick, Vector *other) {
- SI_add_grow_and_oversize(self, tick, other->size);
-
if (tick < self->size) {
+ SI_add_grow_and_oversize(self, self->size, other->size);
memmove(self->elems + tick + other->size, self->elems + tick,
(self->size - tick) * sizeof(Obj*));
+ self->size += other->size;
}
else {
+ SI_add_grow_and_oversize(self, tick, other->size);
memset(self->elems + self->size, 0,
(tick - self->size) * sizeof(Obj*));
+ self->size = tick + other->size;
}
SI_copy_and_incref(self->elems + tick, other->elems, other->size);
- self->size = tick + other->size;
}
Obj*
[2/6] lucy-clownfish git commit: Reduce code size of Vec_Insert
methods
Posted by nw...@apache.org.
Reduce code size of Vec_Insert methods
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/c91a9e44
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/c91a9e44
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/c91a9e44
Branch: refs/heads/master
Commit: c91a9e44747847a2b58978efb565b1ce04c72696
Parents: 5153bef
Author: Nick Wellnhofer <we...@aevum.de>
Authored: Tue Jul 14 13:53:12 2015 +0200
Committer: Nick Wellnhofer <we...@aevum.de>
Committed: Tue Jul 14 13:54:13 2015 +0200
----------------------------------------------------------------------
runtime/core/Clownfish/Vector.c | 16 ++++++++--------
1 file changed, 8 insertions(+), 8 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/c91a9e44/runtime/core/Clownfish/Vector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c
index 2973e5b..8dbf3cc 100644
--- a/runtime/core/Clownfish/Vector.c
+++ b/runtime/core/Clownfish/Vector.c
@@ -109,38 +109,38 @@ Vec_Pop_IMP(Vector *self) {
void
Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
+ size_t max_tick = tick > self->size ? tick : self->size;
+ SI_add_grow_and_oversize(self, max_tick, 1);
+
if (tick < self->size) {
- SI_add_grow_and_oversize(self, self->size, 1);
memmove(self->elems + tick + 1, self->elems + tick,
(self->size - tick) * sizeof(Obj*));
- self->size++;
}
else {
- SI_add_grow_and_oversize(self, tick, 1);
memset(self->elems + self->size, 0,
(tick - self->size) * sizeof(Obj*));
- self->size = tick + 1;
}
self->elems[tick] = elem;
+ self->size = max_tick + 1;
}
void
Vec_Insert_All_IMP(Vector *self, size_t tick, Vector *other) {
+ size_t max_tick = tick > self->size ? tick : self->size;
+ SI_add_grow_and_oversize(self, max_tick, other->size);
+
if (tick < self->size) {
- SI_add_grow_and_oversize(self, self->size, other->size);
memmove(self->elems + tick + other->size, self->elems + tick,
(self->size - tick) * sizeof(Obj*));
- self->size += other->size;
}
else {
- SI_add_grow_and_oversize(self, tick, other->size);
memset(self->elems + self->size, 0,
(tick - self->size) * sizeof(Obj*));
- self->size = tick + other->size;
}
SI_copy_and_incref(self->elems + tick, other->elems, other->size);
+ self->size = max_tick + other->size;
}
Obj*
[6/6] lucy-clownfish git commit: More rework of Vector oversizing
Posted by nw...@apache.org.
More rework of Vector oversizing
Reduce number of overflow checks. Make sure that array size doesn't
overflow just because of oversizing.
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/6090c315
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/6090c315
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/6090c315
Branch: refs/heads/master
Commit: 6090c3153a0d7680117140e25332e243021e15db
Parents: c91a9e4
Author: Nick Wellnhofer <we...@aevum.de>
Authored: Tue Jul 14 15:17:27 2015 +0200
Committer: Nick Wellnhofer <we...@aevum.de>
Committed: Tue Jul 14 15:25:43 2015 +0200
----------------------------------------------------------------------
runtime/core/Clownfish/Test/TestVector.c | 22 +++++++++----
runtime/core/Clownfish/Vector.c | 47 ++++++++++++---------------
2 files changed, 37 insertions(+), 32 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/6090c315/runtime/core/Clownfish/Test/TestVector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Test/TestVector.c b/runtime/core/Clownfish/Test/TestVector.c
index 1a72768..7b51cb3 100644
--- a/runtime/core/Clownfish/Test/TestVector.c
+++ b/runtime/core/Clownfish/Test/TestVector.c
@@ -21,6 +21,8 @@
#define CFISH_USE_SHORT_NAMES
#define TESTCFISH_USE_SHORT_NAMES
+#define MAX_VECTOR_SIZE (SIZE_MAX / sizeof(Obj*))
+
#include "Clownfish/Test/TestVector.h"
#include "Clownfish/String.h"
@@ -406,7 +408,7 @@ static void
S_overflow_Push(void *context) {
UNUSED_VAR(context);
Vector *array = Vec_new(0);
- array->cap = SIZE_MAX;
+ array->cap = MAX_VECTOR_SIZE;
array->size = array->cap;
Vec_Push(array, (Obj*)CFISH_TRUE);
}
@@ -415,9 +417,7 @@ static void
S_overflow_Insert(void *context) {
UNUSED_VAR(context);
Vector *array = Vec_new(0);
- array->cap = SIZE_MAX;
- array->size = array->cap;
- Vec_Insert(array, 38911, (Obj*)CFISH_TRUE);
+ Vec_Insert(array, SIZE_MAX, (Obj*)CFISH_TRUE);
}
static void
@@ -427,12 +427,20 @@ S_overflow_Push_All(void *context) {
array->cap = 1000000000;
array->size = array->cap;
Vector *other = Vec_new(0);
- other->cap = SIZE_MAX - array->cap + 1;
+ other->cap = MAX_VECTOR_SIZE - array->cap + 1;
other->size = other->cap;
Vec_Push_All(array, other);
}
static void
+S_overflow_Insert_All(void *context) {
+ UNUSED_VAR(context);
+ Vector *array = Vec_new(0);
+ Vector *other = Vec_new(0);
+ Vec_Insert_All(array, SIZE_MAX, other);
+}
+
+static void
S_overflow_Store(void *context) {
UNUSED_VAR(context);
Vector *array = Vec_new(0);
@@ -459,6 +467,8 @@ test_exceptions(TestBatchRunner *runner) {
"Insert throws on overflow");
S_test_exception(runner, S_overflow_Push_All,
"Push_All throws on overflow");
+ S_test_exception(runner, S_overflow_Insert_All,
+ "Insert_All throws on overflow");
S_test_exception(runner, S_overflow_Store,
"Store throws on overflow");
}
@@ -517,7 +527,7 @@ test_Grow(TestBatchRunner *runner) {
void
TestVector_Run_IMP(TestVector *self, TestBatchRunner *runner) {
- TestBatchRunner_Plan(runner, (TestBatch*)self, 61);
+ TestBatchRunner_Plan(runner, (TestBatch*)self, 62);
test_Equals(runner);
test_Store_Fetch(runner);
test_Push_Pop_Insert(runner);
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/6090c315/runtime/core/Clownfish/Vector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c
index 8dbf3cc..18c09d2 100644
--- a/runtime/core/Clownfish/Vector.c
+++ b/runtime/core/Clownfish/Vector.c
@@ -26,18 +26,17 @@
#include "Clownfish/Util/Memory.h"
#include "Clownfish/Util/SortUtils.h"
+#define MAX_VECTOR_SIZE (SIZE_MAX / sizeof(Obj*))
+
static CFISH_INLINE void
SI_copy_and_incref(Obj **dst, Obj **src, size_t num);
static CFISH_INLINE void
-SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2);
+SI_add_grow_and_oversize(Vector *self, size_t size, size_t extra);
static void
S_grow_and_oversize(Vector *self, size_t min_size);
-static CFISH_INLINE void
-SI_grow(Vector *self, size_t capacity);
-
static void
S_overflow_error(void);
@@ -110,7 +109,7 @@ Vec_Pop_IMP(Vector *self) {
void
Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
size_t max_tick = tick > self->size ? tick : self->size;
- SI_add_grow_and_oversize(self, max_tick, 1);
+ SI_add_grow_and_oversize(self, 1, max_tick);
if (tick < self->size) {
memmove(self->elems + tick + 1, self->elems + tick,
@@ -128,7 +127,7 @@ Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
void
Vec_Insert_All_IMP(Vector *self, size_t tick, Vector *other) {
size_t max_tick = tick > self->size ? tick : self->size;
- SI_add_grow_and_oversize(self, max_tick, other->size);
+ SI_add_grow_and_oversize(self, other->size, max_tick);
if (tick < self->size) {
memmove(self->elems + tick + other->size, self->elems + tick,
@@ -158,7 +157,7 @@ Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) {
DECREF(self->elems[tick]);
}
else {
- SI_add_grow_and_oversize(self, tick, 1);
+ SI_add_grow_and_oversize(self, 1, tick);
memset(self->elems + self->size, 0,
(tick - self->size) * sizeof(Obj*));
self->size = tick + 1;
@@ -169,7 +168,12 @@ Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) {
void
Vec_Grow_IMP(Vector *self, size_t capacity) {
if (capacity > self->cap) {
- SI_grow(self, capacity);
+ if (capacity > MAX_VECTOR_SIZE) {
+ S_overflow_error();
+ return;
+ }
+ self->elems = (Obj**)REALLOCATE(self->elems, capacity * sizeof(Obj*));
+ self->cap = capacity;
}
}
@@ -301,22 +305,24 @@ SI_copy_and_incref(Obj **dst, Obj **src, size_t num) {
}
}
-// Ensure that the vector's capacity is at least (addend1 + addend2).
+// Ensure that the vector's capacity is at least (size + extra).
+// Assumes that size <= MAX_VECTOR_SIZE.
// If the vector must be grown, oversize the allocation.
static CFISH_INLINE void
-SI_add_grow_and_oversize(Vector *self, size_t addend1, size_t addend2) {
- size_t min_size = addend1 + addend2;
- // Check for overflow.
- if (min_size < addend1) {
+SI_add_grow_and_oversize(Vector *self, size_t size, size_t extra) {
+ if (extra > MAX_VECTOR_SIZE - size) {
S_overflow_error();
return;
}
+ size_t min_size = size + extra;
if (min_size > self->cap) {
S_grow_and_oversize(self, min_size);
}
}
+// Assumes min_size <= MAX_VECTOR_SIZE.
+// __attribute__((noinline))
static void
S_grow_and_oversize(Vector *self, size_t min_size) {
// Oversize by 25%, but at least four elements.
@@ -324,21 +330,10 @@ S_grow_and_oversize(Vector *self, size_t min_size) {
if (extra < 4) { extra = 4; }
size_t capacity = min_size + extra;
- // Check for overflow.
- if (capacity < min_size) {
- S_overflow_error();
- return;
+ if (capacity > MAX_VECTOR_SIZE) {
+ capacity = MAX_VECTOR_SIZE;
}
- SI_grow(self, capacity);
-}
-
-static CFISH_INLINE void
-SI_grow(Vector *self, size_t capacity) {
- if (capacity > SIZE_MAX / sizeof(Obj*)) {
- S_overflow_error();
- return;
- }
self->elems = (Obj**)REALLOCATE(self->elems, capacity * sizeof(Obj*));
self->cap = capacity;
}
[5/6] lucy-clownfish git commit: Minor optimizations in Vector.c
Posted by nw...@apache.org.
Minor optimizations in Vector.c
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/cd346073
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/cd346073
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/cd346073
Branch: refs/heads/master
Commit: cd3460733a65570c89d3821a80331514431d9602
Parents: 5b9e316
Author: Nick Wellnhofer <we...@aevum.de>
Authored: Tue Jul 14 13:13:31 2015 +0200
Committer: Nick Wellnhofer <we...@aevum.de>
Committed: Tue Jul 14 13:54:13 2015 +0200
----------------------------------------------------------------------
runtime/core/Clownfish/Vector.c | 36 ++++++++++++++++++++++++------------
1 file changed, 24 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/cd346073/runtime/core/Clownfish/Vector.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Vector.c b/runtime/core/Clownfish/Vector.c
index 4cdfa96..7f87fa1 100644
--- a/runtime/core/Clownfish/Vector.c
+++ b/runtime/core/Clownfish/Vector.c
@@ -109,16 +109,20 @@ Vec_Pop_IMP(Vector *self) {
void
Vec_Insert_IMP(Vector *self, size_t tick, Obj *elem) {
- if (tick >= self->size) {
- Vec_Store(self, tick, elem);
- return;
+ if (tick < self->size) {
+ SI_add_grow_and_oversize(self, self->size, 1);
+ memmove(self->elems + tick + 1, self->elems + tick,
+ (self->size - tick) * sizeof(Obj*));
+ self->size++;
+ }
+ else {
+ SI_add_grow_and_oversize(self, tick, 1);
+ memset(self->elems + self->size, 0,
+ (tick - self->size) * sizeof(Obj*));
+ self->size = tick + 1;
}
- SI_add_grow_and_oversize(self, self->size, 1);
- memmove(self->elems + tick + 1, self->elems + tick,
- (self->size - tick) * sizeof(Obj*));
self->elems[tick] = elem;
- self->size++;
}
void
@@ -149,11 +153,11 @@ Vec_Fetch_IMP(Vector *self, size_t num) {
void
Vec_Store_IMP(Vector *self, size_t tick, Obj *elem) {
- SI_add_grow_and_oversize(self, tick, 1);
if (tick < self->size) {
DECREF(self->elems[tick]);
}
else {
+ SI_add_grow_and_oversize(self, tick, 1);
memset(self->elems + self->size, 0,
(tick - self->size) * sizeof(Obj*));
self->size = tick + 1;
@@ -202,10 +206,10 @@ Vec_Clear_IMP(Vector *self) {
void
Vec_Resize_IMP(Vector *self, size_t size) {
if (size < self->size) {
- Vec_Excise(self, size, self->size - size);
+ Vec_Excise_IMP(self, size, self->size - size);
}
else if (size > self->size) {
- Vec_Grow(self, size);
+ Vec_Grow_IMP(self, size);
memset(self->elems + self->size, 0,
(size - self->size) * sizeof(Obj*));
}
@@ -255,8 +259,16 @@ Vec_Equals_IMP(Vector *self, Obj *other) {
for (size_t i = 0, max = self->size; i < max; i++) {
Obj *val = elems[i];
Obj *other_val = twin_elems[i];
- if ((val && !other_val) || (other_val && !val)) { return false; }
- if (val && !Obj_Equals(val, other_val)) { return false; }
+ if (val) {
+ if (!other_val || !Obj_Equals(val, other_val)) {
+ return false;
+ }
+ }
+ else {
+ if (other_val) {
+ return false;
+ }
+ }
}
}
return true;