[njs] Array iterators optimizations.
Igor Sysoev
igor at sysoev.ru
Mon Apr 3 12:11:11 UTC 2017
details: http://hg.nginx.org/njs/rev/cee288760080
branches:
changeset: 328:cee288760080
user: Igor Sysoev <igor at sysoev.ru>
date: Sun Apr 02 12:35:11 2017 +0300
description:
Array iterators optimizations.
diffstat:
njs/njs_array.c | 221 +++++++++++++++++++++++++---------------------
njs/test/njs_unit_test.c | 4 +
2 files changed, 122 insertions(+), 103 deletions(-)
diffs (498 lines):
diff -r 8f59eeb8ee2d -r cee288760080 njs/njs_array.c
--- a/njs/njs_array.c Sat Apr 01 15:32:04 2017 +0300
+++ b/njs/njs_array.c Sun Apr 02 12:35:11 2017 +0300
@@ -44,7 +44,7 @@ typedef struct {
*/
njs_value_t retval;
- uint32_t next_index;
+ uint32_t index;
uint32_t length;
} njs_array_iter_t;
@@ -59,7 +59,6 @@ typedef struct {
typedef struct {
njs_array_iter_t iter;
njs_array_t *array;
- uint32_t index;
} njs_array_map_t;
@@ -95,17 +94,20 @@ static njs_ret_t njs_array_prototype_fil
njs_value_t *args, nxt_uint_t nargs, njs_index_t unused);
static njs_ret_t njs_array_prototype_map_continuation(njs_vm_t *vm,
njs_value_t *args, nxt_uint_t nargs, njs_index_t unused);
+static nxt_noinline uint32_t njs_array_prototype_map_index(njs_array_t *array,
+ njs_array_map_t *map);
+static nxt_noinline njs_ret_t njs_array_iterator_args(njs_vm_t *vm,
+ njs_value_t *args, nxt_uint_t nargs);
+static nxt_noinline uint32_t njs_array_iterator_index(njs_array_t *array,
+ njs_array_iter_t *iter);
+static nxt_noinline njs_ret_t njs_array_iterator_apply(njs_vm_t *vm,
+ njs_array_iter_t *iter, njs_value_t *args, nxt_uint_t nargs);
static njs_ret_t njs_array_prototype_reduce_continuation(njs_vm_t *vm,
njs_value_t *args, nxt_uint_t nargs, njs_index_t unused);
static njs_ret_t njs_array_prototype_reduce_right_continuation(njs_vm_t *vm,
njs_value_t *args, nxt_uint_t nargs, njs_index_t unused);
-static nxt_noinline njs_ret_t njs_array_iterator_args(njs_vm_t *vm,
- njs_value_t *args, nxt_uint_t nargs);
-static nxt_noinline uint32_t njs_array_iterator_next(njs_array_t *array,
- uint32_t n, uint32_t length);
-static nxt_noinline njs_ret_t njs_array_iterator_apply(njs_vm_t *vm,
- njs_array_iter_t *iter, njs_value_t *args, nxt_uint_t nargs);
-static uint32_t njs_array_reduce_right_next(njs_array_t *array, uint32_t n);
+static uint32_t njs_array_reduce_right_index(njs_array_t *array,
+ njs_array_iter_t *iter);
static njs_ret_t njs_array_prototype_sort_continuation(njs_vm_t *vm,
njs_value_t *args, nxt_uint_t nargs, njs_index_t unused);
@@ -1222,11 +1224,14 @@ static njs_ret_t
njs_array_prototype_for_each_continuation(njs_vm_t *vm, njs_value_t *args,
nxt_uint_t nargs, njs_index_t unused)
{
+ uint32_t index;
njs_array_iter_t *iter;
iter = njs_vm_continuation(vm);
- if (iter->next_index >= args[0].data.u.array->length) {
+ index = njs_array_iterator_index(args[0].data.u.array, iter);
+
+ if (index == NJS_ARRAY_INVALID_INDEX) {
vm->retval = njs_value_void;
return NXT_OK;
}
@@ -1259,6 +1264,7 @@ static njs_ret_t
njs_array_prototype_some_continuation(njs_vm_t *vm, njs_value_t *args,
nxt_uint_t nargs, njs_index_t unused)
{
+ uint32_t index;
njs_array_iter_t *iter;
const njs_value_t *retval;
@@ -1267,11 +1273,15 @@ njs_array_prototype_some_continuation(nj
if (njs_is_true(&iter->retval)) {
retval = &njs_value_true;
- } else if (iter->next_index >= args[0].data.u.array->length) {
- retval = &njs_value_false;
-
} else {
- return njs_array_iterator_apply(vm, iter, args, nargs);
+ index = njs_array_iterator_index(args[0].data.u.array, iter);
+
+ if (index == NJS_ARRAY_INVALID_INDEX) {
+ retval = &njs_value_false;
+
+ } else {
+ return njs_array_iterator_apply(vm, iter, args, nargs);
+ }
}
vm->retval = *retval;
@@ -1304,6 +1314,7 @@ static njs_ret_t
njs_array_prototype_every_continuation(njs_vm_t *vm, njs_value_t *args,
nxt_uint_t nargs, njs_index_t unused)
{
+ uint32_t index;
njs_array_iter_t *iter;
const njs_value_t *retval;
@@ -1312,11 +1323,15 @@ njs_array_prototype_every_continuation(n
if (!njs_is_true(&iter->retval)) {
retval = &njs_value_false;
- } else if (iter->next_index >= args[0].data.u.array->length) {
- retval = &njs_value_true;
-
} else {
- return njs_array_iterator_apply(vm, iter, args, nargs);
+ index = njs_array_iterator_index(args[0].data.u.array, iter);
+
+ if (index == NJS_ARRAY_INVALID_INDEX) {
+ retval = &njs_value_true;
+
+ } else {
+ return njs_array_iterator_apply(vm, iter, args, nargs);
+ }
}
vm->retval = *retval;
@@ -1417,6 +1432,7 @@ static njs_ret_t
njs_array_prototype_filter_continuation(njs_vm_t *vm, njs_value_t *args,
nxt_uint_t nargs, njs_index_t unused)
{
+ uint32_t index;
nxt_int_t ret;
njs_array_t *array;
njs_array_filter_t *filter;
@@ -1431,8 +1447,9 @@ njs_array_prototype_filter_continuation(
}
array = args[0].data.u.array;
-
- if (filter->iter.next_index >= array->length) {
+ index = njs_array_iterator_index(array, &filter->iter);
+
+ if (index == NJS_ARRAY_INVALID_INDEX) {
vm->retval.data.u.array = filter->array;
vm->retval.type = NJS_ARRAY;
vm->retval.data.truth = 1;
@@ -1441,7 +1458,7 @@ njs_array_prototype_filter_continuation(
}
/* GC: filter->value */
- filter->value = array->start[filter->iter.next_index];
+ filter->value = array->start[index];
return njs_array_iterator_apply(vm, &filter->iter, args, nargs);
}
@@ -1451,10 +1468,7 @@ static njs_ret_t
njs_array_prototype_map(njs_vm_t *vm, njs_value_t *args, nxt_uint_t nargs,
njs_index_t unused)
{
- size_t size;
nxt_int_t ret;
- njs_value_t *value;
- njs_array_t *array;
njs_array_map_t *map;
ret = njs_array_iterator_args(vm, args, nargs);
@@ -1466,39 +1480,31 @@ njs_array_prototype_map(njs_vm_t *vm, nj
map->iter.u.cont.function = njs_array_prototype_map_continuation;
njs_set_invalid(&map->iter.retval);
- array = args[0].data.u.array;
-
- map->array = njs_array_alloc(vm, array->length, 0);
+ map->array = njs_array_alloc(vm, args[0].data.u.array->length, 0);
if (nxt_slow_path(map->array == NULL)) {
return NXT_ERROR;
}
- value = map->array->start;
- size = array->length;
-
- while (size != 0) {
- njs_set_invalid(value);
- value++;
- size--;
- }
-
return njs_array_prototype_map_continuation(vm, args, nargs, unused);
}
-static njs_ret_t
+static nxt_noinline njs_ret_t
njs_array_prototype_map_continuation(njs_vm_t *vm, njs_value_t *args,
nxt_uint_t nargs, njs_index_t unused)
{
+ uint32_t index;
njs_array_map_t *map;
map = njs_vm_continuation(vm);
if (njs_is_valid(&map->iter.retval)) {
- map->array->start[map->index] = map->iter.retval;
+ map->array->start[map->iter.index] = map->iter.retval;
}
- if (map->iter.next_index >= args[0].data.u.array->length) {
+ index = njs_array_prototype_map_index(args[0].data.u.array, map);
+
+ if (index == NJS_ARRAY_INVALID_INDEX) {
vm->retval.data.u.array = map->array;
vm->retval.type = NJS_ARRAY;
vm->retval.data.truth = 1;
@@ -1506,12 +1512,36 @@ njs_array_prototype_map_continuation(njs
return NXT_OK;
}
- map->index = map->iter.next_index;
-
return njs_array_iterator_apply(vm, &map->iter, args, nargs);
}
+static uint32_t
+njs_array_prototype_map_index(njs_array_t *array, njs_array_map_t *map)
+{
+ uint32_t i, length;
+ njs_value_t *start;
+
+ start = map->array->start;
+ length = nxt_min(array->length, map->iter.length);
+
+ for (i = map->iter.index + 1; i < length; i++) {
+ if (njs_is_valid(&array->start[i])) {
+ map->iter.index = i;
+ return i;
+ }
+
+ njs_set_invalid(&start[i]);
+ }
+
+ while (i < map->iter.length) {
+ njs_set_invalid(&start[i++]);
+ }
+
+ return NJS_ARRAY_INVALID_INDEX;
+}
+
+
static njs_ret_t
njs_array_prototype_reduce(njs_vm_t *vm, njs_value_t *args, nxt_uint_t nargs,
njs_index_t unused)
@@ -1534,16 +1564,14 @@ njs_array_prototype_reduce(njs_vm_t *vm,
} else {
array = args[0].data.u.array;
- n = iter->next_index;
-
- if (n >= array->length) {
+ n = njs_array_iterator_index(array, iter);
+
+ if (n == NJS_ARRAY_INVALID_INDEX) {
vm->exception = &njs_exception_type_error;
return NXT_ERROR;
}
iter->retval = array->start[n];
-
- iter->next_index = njs_array_iterator_next(array, n + 1, array->length);
}
return njs_array_prototype_reduce_continuation(vm, args, nargs, unused);
@@ -1560,8 +1588,11 @@ njs_array_prototype_reduce_continuation(
njs_array_iter_t *iter;
iter = njs_vm_continuation(vm);
-
- if (iter->next_index >= args[0].data.u.array->length) {
+ array = args[0].data.u.array;
+
+ n = njs_array_iterator_index(array, iter);
+
+ if (n == NJS_ARRAY_INVALID_INDEX) {
vm->retval = iter->retval;
return NXT_OK;
}
@@ -1571,17 +1602,12 @@ njs_array_prototype_reduce_continuation(
/* GC: array elt, array */
arguments[1] = iter->retval;
- array = args[0].data.u.array;
- n = iter->next_index;
-
arguments[2] = array->start[n];
njs_number_set(&arguments[3], n);
arguments[4] = args[0];
- iter->next_index = njs_array_iterator_next(array, n + 1, iter->length);
-
return njs_function_apply(vm, args[1].data.u.function, arguments, 5,
(njs_index_t) &iter->retval);
}
@@ -1590,15 +1616,13 @@ njs_array_prototype_reduce_continuation(
static nxt_noinline njs_ret_t
njs_array_iterator_args(njs_vm_t *vm, njs_value_t *args, nxt_uint_t nargs)
{
- njs_array_t *array;
njs_array_iter_t *iter;
if (nargs > 1 && njs_is_array(&args[0]) && njs_is_function(&args[1])) {
- array = args[0].data.u.array;
iter = njs_vm_continuation(vm);
- iter->length = array->length;
- iter->next_index = njs_array_iterator_next(array, 0, array->length);
+ iter->length = args[0].data.u.array->length;
+ iter->index = NJS_ARRAY_INVALID_INDEX;
return NXT_OK;
}
@@ -1610,16 +1634,17 @@ njs_array_iterator_args(njs_vm_t *vm, nj
static nxt_noinline uint32_t
-njs_array_iterator_next(njs_array_t *array, uint32_t n, uint32_t length)
+njs_array_iterator_index(njs_array_t *array, njs_array_iter_t *iter)
{
- length = nxt_min(length, array->length);
-
- while (n < length) {
- if (njs_is_valid(&array->start[n])) {
- return n;
+ uint32_t i, length;
+
+ length = nxt_min(array->length, iter->length);
+
+ for (i = iter->index + 1; i < length; i++) {
+ if (njs_is_valid(&array->start[i])) {
+ iter->index = i;
+ return i;
}
-
- n++;
}
return NJS_ARRAY_INVALID_INDEX;
@@ -1630,33 +1655,22 @@ static nxt_noinline njs_ret_t
njs_array_iterator_apply(njs_vm_t *vm, njs_array_iter_t *iter,
njs_value_t *args, nxt_uint_t nargs)
{
- uint32_t n;
- njs_array_t *array;
- njs_value_t arguments[4];
-
- /*
- * The cast "*(njs_value_t *) &" is required by SunC.
- * Simple "(njs_value_t)" does not help.
- */
- arguments[0] = (nargs > 2) ? args[2] : *(njs_value_t *) &njs_value_void;
+ uint32_t n;
+ const njs_value_t *value;
+ njs_value_t arguments[4];
+
/* GC: array elt, array */
- /*
- * All array iterators functions call njs_array_iterator_args()
- * function which set a correct iter->next_index value. A large
- * value of iter->next_index must be checked before calling
- * njs_array_iterator_apply().
- */
- array = args[0].data.u.array;
- n = iter->next_index;
- arguments[1] = array->start[n];
+ value = (nargs > 2) ? &args[2] : &njs_value_void;
+ arguments[0] = *value;
+
+ n = iter->index;
+ arguments[1] = args[0].data.u.array->start[n];
njs_number_set(&arguments[2], n);
arguments[3] = args[0];
- iter->next_index = njs_array_iterator_next(array, n + 1, iter->length);
-
return njs_function_apply(vm, args[1].data.u.function, arguments, 4,
(njs_index_t) &iter->retval);
}
@@ -1667,32 +1681,30 @@ njs_array_prototype_reduce_right(njs_vm_
nxt_uint_t nargs, njs_index_t unused)
{
uint32_t n;
+ njs_ret_t ret;
njs_array_t *array;
njs_array_iter_t *iter;
- if (nargs < 2 || !njs_is_array(&args[0]) || !njs_is_function(&args[1])) {
- goto type_error;
+ ret = njs_array_iterator_args(vm, args, nargs);
+ if (nxt_slow_path(ret != NXT_OK)) {
+ return ret;
}
iter = njs_vm_continuation(vm);
iter->u.cont.function = njs_array_prototype_reduce_right_continuation;
- array = args[0].data.u.array;
- iter->next_index = njs_array_reduce_right_next(array, array->length);
-
if (nargs > 2) {
iter->retval = args[2];
} else {
- n = iter->next_index;
+ array = args[0].data.u.array;
+ n = njs_array_reduce_right_index(array, iter);
if (n == NJS_ARRAY_INVALID_INDEX) {
goto type_error;
}
iter->retval = array->start[n];
-
- iter->next_index = njs_array_reduce_right_next(array, n);
}
return njs_array_prototype_reduce_right_continuation(vm, args, nargs,
@@ -1705,7 +1717,7 @@ type_error:
}
-static njs_ret_t
+static nxt_noinline njs_ret_t
njs_array_prototype_reduce_right_continuation(njs_vm_t *vm, njs_value_t *args,
nxt_uint_t nargs, njs_index_t unused)
{
@@ -1715,8 +1727,11 @@ njs_array_prototype_reduce_right_continu
njs_array_iter_t *iter;
iter = njs_vm_continuation(vm);
-
- if (iter->next_index == NJS_ARRAY_INVALID_INDEX) {
+ array = args[0].data.u.array;
+
+ n = njs_array_reduce_right_index(array, iter);
+
+ if (n == NJS_ARRAY_INVALID_INDEX) {
vm->retval = iter->retval;
return NXT_OK;
}
@@ -1726,29 +1741,29 @@ njs_array_prototype_reduce_right_continu
/* GC: array elt, array */
arguments[1] = iter->retval;
- array = args[0].data.u.array;
- n = iter->next_index;
arguments[2] = array->start[n];
njs_number_set(&arguments[3], n);
arguments[4] = args[0];
- iter->next_index = njs_array_reduce_right_next(array, n);
-
return njs_function_apply(vm, args[1].data.u.function, arguments, 5,
(njs_index_t) &iter->retval);
}
static nxt_noinline uint32_t
-njs_array_reduce_right_next(njs_array_t *array, uint32_t n)
+njs_array_reduce_right_index(njs_array_t *array, njs_array_iter_t *iter)
{
- n = nxt_min(n, array->length) - 1;
+ uint32_t n;
+
+ n = nxt_min(iter->index, array->length) - 1;
while (n != NJS_ARRAY_INVALID_INDEX) {
+
if (njs_is_valid(&array->start[n])) {
- return n;
+ iter->index = n;
+ break;
}
n--;
diff -r 8f59eeb8ee2d -r cee288760080 njs/test/njs_unit_test.c
--- a/njs/test/njs_unit_test.c Sat Apr 01 15:32:04 2017 +0300
+++ b/njs/test/njs_unit_test.c Sun Apr 02 12:35:11 2017 +0300
@@ -2903,6 +2903,10 @@ static njs_unit_test_t njs_test[] =
"a.map(function(v, i, a) { a.pop(); return v + 1 })"),
nxt_string("2,3,4,,,") },
+ { nxt_string("var a = [1,2,3,4,5,6];"
+ "a.map(function(v, i, a) { a.shift(); return v + 1 })"),
+ nxt_string("2,4,6,,,") },
+
{ nxt_string("var a = [];"
"a.reduce(function(p, v, i, a) { return p + v })"),
nxt_string("TypeError") },
More information about the nginx-devel
mailing list