[njs] Improved iteration over objects indexes in Array functions.
Alexander Borisov
alexander.borisov at nginx.com
Thu Sep 19 07:20:14 UTC 2019
details: https://hg.nginx.org/njs/rev/f516c8332495
branches:
changeset: 1165:f516c8332495
user: Alexander Borisov <alexander.borisov at nginx.com>
date: Thu Sep 19 10:19:02 2019 +0300
description:
Improved iteration over objects indexes in Array functions.
For example, unshift function for object with large length:
var arrayLike = {};
arrayLike.length = 2 ** 53 - 1;
Array.prototype.unshift.call(arrayLike);
diffstat:
src/njs_array.c | 174 ++++++++++++++++++++++++++++++++++++++++++++++-
src/test/njs_unit_test.c | 23 ++++++
2 files changed, 196 insertions(+), 1 deletions(-)
diffs (298 lines):
diff -r 893fc436a363 -r f516c8332495 src/njs_array.c
--- a/src/njs_array.c Thu Sep 19 10:19:02 2019 +0300
+++ b/src/njs_array.c Thu Sep 19 10:19:02 2019 +0300
@@ -8,6 +8,9 @@
#include <njs_main.h>
+#define NJS_ARRAY_LARGE_OBJECT_LENGTH 4096
+
+
typedef struct {
njs_function_t *function;
njs_value_t *argument;
@@ -27,6 +30,7 @@ typedef njs_int_t (*njs_array_iterator_h
static njs_int_t njs_array_prototype_slice_copy(njs_vm_t *vm,
njs_value_t *this, int64_t start, int64_t length);
static njs_value_t *njs_array_copy(njs_value_t *dst, njs_value_t *src);
+static njs_array_t *njs_object_indexes(njs_vm_t *vm, njs_value_t *object);
njs_array_t *
@@ -708,10 +712,11 @@ static njs_int_t
njs_array_prototype_unshift(njs_vm_t *vm, njs_value_t *args, njs_uint_t nargs,
njs_index_t unused)
{
+ double idx;
uint32_t from, to, length;
njs_int_t ret;
njs_uint_t n;
- njs_array_t *array;
+ njs_array_t *array, *keys;
njs_value_t *value, entry, index;
value = njs_arg(args, nargs, 0);
@@ -767,6 +772,38 @@ njs_array_prototype_unshift(njs_vm_t *vm
return NJS_ERROR;
}
+ if (length > NJS_ARRAY_LARGE_OBJECT_LENGTH) {
+ keys = njs_object_indexes(vm, value);
+ if (njs_slow_path(keys == NULL)) {
+ return NJS_ERROR;
+ }
+
+ from = keys->length;
+
+ while (from > 0) {
+ ret = njs_value_property_delete(vm, value, &keys->start[--from],
+ &entry);
+ if (njs_slow_path(ret == NJS_ERROR)) {
+ return ret;
+ }
+
+ if (ret == NJS_OK) {
+ idx = njs_string_to_index(&keys->start[from]);
+
+ njs_uint32_to_string(&index, (uint32_t) idx + nargs - 1);
+
+ ret = njs_value_property_set(vm, value, &index, &entry);
+ if (njs_slow_path(ret == NJS_ERROR)) {
+ return ret;
+ }
+ }
+ }
+
+ length += nargs - 1;
+
+ goto copy;
+ }
+
from = length;
length += n;
to = length;
@@ -791,6 +828,8 @@ njs_array_prototype_unshift(njs_vm_t *vm
}
}
+copy:
+
for (n = 1; n < nargs; n++) {
njs_uint32_to_string(&index, n - 1);
@@ -1199,12 +1238,75 @@ njs_array_prototype_join(njs_vm_t *vm, n
}
+static int
+njs_object_indexes_handler(const void *first, const void *second)
+{
+ double num1, num2;
+ njs_str_t str1, str2;
+ const njs_value_t *val1, *val2;
+
+ val1 = first;
+ val2 = second;
+
+ num1 = njs_string_to_index(val1);
+ num2 = njs_string_to_index(val2);
+
+ if (!isnan(num1) || !isnan(num2)) {
+ if (isnan(num1)) {
+ return 1;
+ }
+
+ if (isnan(num2)) {
+ return -1;
+ }
+
+ return (int) (num1 - num2);
+ }
+
+ njs_string_get(val1, &str1);
+ njs_string_get(val2, &str2);
+
+ return strncmp((const char *) str1.start, (const char *) str2.start,
+ njs_min(str1.length, str2.length));
+}
+
+
+static njs_array_t *
+njs_object_indexes(njs_vm_t *vm, njs_value_t *object)
+{
+ double idx;
+ uint32_t i;
+ njs_array_t *keys;
+
+ keys = njs_value_own_enumerate(vm, object, NJS_ENUM_KEYS, 0);
+ if (njs_slow_path(keys == NULL)) {
+ return NULL;
+ }
+
+ qsort(keys->start, keys->length, sizeof(njs_value_t),
+ njs_object_indexes_handler);
+
+ for (i = 0; i < keys->length; i++) {
+ idx = njs_string_to_index(&keys->start[i]);
+
+ if (isnan(idx)) {
+ keys->length = i;
+ break;
+ }
+ }
+
+ return keys;
+}
+
+
njs_inline njs_int_t
njs_array_iterator(njs_vm_t *vm, njs_array_iterator_args_t *args,
njs_array_iterator_handler_t handler)
{
+ double idx;
uint32_t length, i, from, to;
njs_int_t ret;
+ njs_array_t *keys;
njs_value_t *entry, *value, character, index, string_obj, prop;
njs_object_t *object;
const u_char *p, *end, *pos;
@@ -1306,6 +1408,39 @@ njs_array_iterator(njs_vm_t *vm, njs_arr
process_object:
+ if ((to - from) > NJS_ARRAY_LARGE_OBJECT_LENGTH) {
+ keys = njs_object_indexes(vm, value);
+ if (njs_slow_path(keys == NULL)) {
+ return NJS_ERROR;
+ }
+
+ for (i = 0; i < keys->length; i++) {
+ idx = njs_string_to_index(&keys->start[i]);
+
+ if (idx < from || idx > to) {
+ continue;
+ }
+
+ ret = njs_value_property(vm, value, &keys->start[i], &prop);
+ if (njs_slow_path(ret == NJS_ERROR)) {
+ return ret;
+ }
+
+ if (ret != NJS_DECLINED) {
+ ret = handler(vm, args, &prop, i);
+ if (njs_slow_path(ret != NJS_OK)) {
+ if (ret > 0) {
+ return NJS_DECLINED;
+ }
+
+ return NJS_ERROR;
+ }
+ }
+ }
+
+ return NJS_OK;
+ }
+
for (i = from; i < to; i++) {
njs_uint32_to_string(&index, i);
@@ -1334,8 +1469,10 @@ njs_inline njs_int_t
njs_array_reverse_iterator(njs_vm_t *vm, njs_array_iterator_args_t *args,
njs_array_iterator_handler_t handler)
{
+ double idx;
uint32_t i, from, to, length;
njs_int_t ret;
+ njs_array_t *keys;
njs_value_t *entry, *value, character, index, string_obj, prop;
njs_object_t *object;
const u_char *p, *end, *pos;
@@ -1445,6 +1582,41 @@ njs_array_reverse_iterator(njs_vm_t *vm,
process_object:
+ if ((from - to) > NJS_ARRAY_LARGE_OBJECT_LENGTH) {
+ keys = njs_object_indexes(vm, value);
+ if (njs_slow_path(keys == NULL)) {
+ return NJS_ERROR;
+ }
+
+ i = keys->length;
+
+ while (i > 0) {
+ idx = njs_string_to_index(&keys->start[--i]);
+
+ if (idx < to || idx > from) {
+ continue;
+ }
+
+ ret = njs_value_property(vm, value, &keys->start[i], &prop);
+ if (njs_slow_path(ret == NJS_ERROR)) {
+ return ret;
+ }
+
+ if (ret != NJS_DECLINED) {
+ ret = handler(vm, args, &prop, idx);
+ if (njs_slow_path(ret != NJS_OK)) {
+ if (ret > 0) {
+ return NJS_DECLINED;
+ }
+
+ return NJS_ERROR;
+ }
+ }
+ }
+
+ return NJS_OK;
+ }
+
i = from + 1;
while (i-- > to) {
diff -r 893fc436a363 -r f516c8332495 src/test/njs_unit_test.c
--- a/src/test/njs_unit_test.c Thu Sep 19 10:19:02 2019 +0300
+++ b/src/test/njs_unit_test.c Thu Sep 19 10:19:02 2019 +0300
@@ -4001,6 +4001,12 @@ static njs_unit_test_t njs_test[] =
{ njs_str("var x = {0: 0}; Array.prototype.unshift.call(x); x.length"),
njs_str("0") },
+ { njs_str("var obj = {'10000000': 'x', '10000001': 'y', '10000002': 'z'}; var a = [];"
+ "obj.length = 90000000;"
+ "Array.prototype.unshift.call(obj, 'a', 'b', 'c');"
+ "Array.prototype.forEach.call(obj, (v) => a.push(v)); a"),
+ njs_str("a,b,c,x,y,z")},
+
{ njs_str("var a=[0], n = 64; while(--n) {a.push(n); a.shift()}; a"),
njs_str("1") },
@@ -4156,6 +4162,11 @@ static njs_unit_test_t njs_test[] =
"Array.prototype.lastIndexOf.call(o, 'd')"),
njs_str("3") },
+ { njs_str("var obj = {'10000000': 'x', '10000001': 'y', '10000002': 'z'}; var a = [];"
+ "obj.length = 90000000;"
+ "Array.prototype.lastIndexOf.call(obj, 'y');"),
+ njs_str("10000001")},
+
{ njs_str("[1,2,3,4].includes()"),
njs_str("false") },
@@ -4192,6 +4203,18 @@ static njs_unit_test_t njs_test[] =
"Array.prototype.includes.call(o, 'd')"),
njs_str("true") },
+ { njs_str("var obj = {'0': 'a', '1': 'b', '10000000': 'c', '10000001': 'd', '10000002': 'e'};"
+ "var fromIndex = 1;"
+ "obj.length = 90000000;"
+ "Array.prototype.includes.call(obj, 'c', fromIndex);"),
+ njs_str("true") },
+
+ { njs_str("var obj = {'0': 'a', '1': 'b', '10000000': 'c', '10000001': 'd', '10000002': 'e'};"
+ "var fromIndex = 1;"
+ "obj.length = 90000000;"
+ "Array.prototype.includes.call(obj, 'a', fromIndex);"),
+ njs_str("false") },
+
{ njs_str("var a = []; var s = { sum: 0 };"
"a.forEach(function(v, i, a) { this.sum += v }, s); s.sum"),
njs_str("0") },
More information about the nginx-devel
mailing list