From 4638f7b91407c48710007af82a68da0007c820f2 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Wed, 28 Jan 2015 07:43:28 +0300 Subject: Change "foreach" statement behavior (this is just a PoC yet) - "foreach by value" don't relay on internal array/object pointer and doesnt perform array duplication. It just locks it incrementing reference counter. If the original array is modified by some code, the copy on write is performed and "foreach" still work with the old copy. - it makes no difference if array given to "foreach by value" is reference itself - "foreach by reference" still use internal array/object pointer and should work similar to PHP-5. (This id not completely implemented) --- ext/opcache/Optimizer/block_pass.c | 14 +++++++---- ext/opcache/Optimizer/nop_removal.c | 6 +++-- ext/opcache/Optimizer/optimize_temp_vars_5.c | 35 ++++++++-------------------- ext/opcache/Optimizer/pass1_5.c | 6 +++-- ext/opcache/Optimizer/pass3.c | 6 +++-- ext/opcache/Optimizer/zend_optimizer.c | 12 ++++++---- ext/opcache/zend_persist.c | 6 +++-- 7 files changed, 43 insertions(+), 42 deletions(-) (limited to 'ext') diff --git a/ext/opcache/Optimizer/block_pass.c b/ext/opcache/Optimizer/block_pass.c index 7948990f81..3df0faa0ef 100644 --- a/ext/opcache/Optimizer/block_pass.c +++ b/ext/opcache/Optimizer/block_pass.c @@ -166,14 +166,16 @@ static int find_code_blocks(zend_op_array *op_array, zend_cfg *cfg, zend_optimiz case ZEND_JMPNZ: case ZEND_JMPZ_EX: case ZEND_JMPNZ_EX: - case ZEND_FE_RESET: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: case ZEND_NEW: case ZEND_JMP_SET: case ZEND_COALESCE: START_BLOCK_OP(ZEND_OP2(opline).opline_num); START_BLOCK_OP(opno + 1); break; - case ZEND_FE_FETCH: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: START_BLOCK_OP(ZEND_OP2(opline).opline_num); START_BLOCK_OP(opno + 2); break; @@ -293,11 +295,13 @@ static int find_code_blocks(zend_op_array *op_array, zend_cfg *cfg, zend_optimiz case ZEND_JMPNZ: case ZEND_JMPZ_EX: case ZEND_JMPNZ_EX: - case ZEND_FE_RESET: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: case ZEND_NEW: case ZEND_JMP_SET: case ZEND_COALESCE: - case ZEND_FE_FETCH: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: cur_block->op2_to = &blocks[ZEND_OP2(opline).opline_num]; /* break missing intentionally */ default: @@ -619,7 +623,7 @@ static void zend_optimize_block(zend_code_block *block, zend_op_array *op_array, ZEND_OP1_TYPE(VAR_SOURCE(opline->op1)) == IS_CONST && opline->opcode != ZEND_CASE && /* CASE _always_ expects variable */ opline->opcode != ZEND_FETCH_LIST && - opline->opcode != ZEND_FE_RESET && + (opline->opcode != ZEND_FE_RESET_R || opline->opcode != ZEND_FE_RESET_RW) && opline->opcode != ZEND_FREE ) { zend_op *src = VAR_SOURCE(opline->op1); diff --git a/ext/opcache/Optimizer/nop_removal.c b/ext/opcache/Optimizer/nop_removal.c index 0bb8cce17f..dccd010ae4 100644 --- a/ext/opcache/Optimizer/nop_removal.c +++ b/ext/opcache/Optimizer/nop_removal.c @@ -93,8 +93,10 @@ void zend_optimizer_nop_removal(zend_op_array *op_array) case ZEND_JMPNZ: case ZEND_JMPZ_EX: case ZEND_JMPNZ_EX: - case ZEND_FE_FETCH: - case ZEND_FE_RESET: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: case ZEND_NEW: case ZEND_JMP_SET: case ZEND_COALESCE: diff --git a/ext/opcache/Optimizer/optimize_temp_vars_5.c b/ext/opcache/Optimizer/optimize_temp_vars_5.c index 27ba6bad8e..ac5389ed2b 100644 --- a/ext/opcache/Optimizer/optimize_temp_vars_5.c +++ b/ext/opcache/Optimizer/optimize_temp_vars_5.c @@ -66,15 +66,12 @@ void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *c if (ZEND_RESULT_TYPE(opline) & (IS_VAR | IS_TMP_VAR)) { start_of_T[VAR_NUM(ZEND_RESULT(opline).var) - offset] = opline; } - /* special puprose variable to keep HashPointer on VM stack */ + /* special puprose variable to keep HashTable* on VM stack */ if (opline->opcode == ZEND_OP_DATA && - (opline-1)->opcode == ZEND_FE_FETCH && + (opline-1)->opcode == ZEND_FE_FETCH_RW && + (opline-2)->opcode == ZEND_FE_RESET_RW && opline->op1_type == IS_TMP_VAR) { - start_of_T[VAR_NUM(ZEND_OP1(opline).var) - offset] = opline; - if (sizeof(HashPointer) > sizeof(zval)) { - /* Make shure 1 zval is enough for HashPointer (2 must be enough) */ - start_of_T[VAR_NUM(ZEND_OP1(opline).var) + 1 - offset] = opline; - } + start_of_T[VAR_NUM(ZEND_OP1(opline).var) - offset] = opline - 2; } opline--; } @@ -88,25 +85,13 @@ void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *c while (opline >= end) { if ((ZEND_OP1_TYPE(opline) & (IS_VAR | IS_TMP_VAR))) { - /* special puprose variable to keep HashPointer on VM stack */ - if (opline->opcode == ZEND_OP_DATA && - (opline-1)->opcode == ZEND_FE_FETCH && - opline->op1_type == IS_TMP_VAR) { - max++; - ZEND_OP1(opline).var = NUM_VAR(max + offset); - if (sizeof(HashPointer) > sizeof(zval)) { - /* Make shure 1 zval is enough for HashPointer (2 must be enough) */ - max++; - } - } else { - currT = VAR_NUM(ZEND_OP1(opline).var) - offset; - if (!valid_T[currT]) { - GET_AVAILABLE_T(); - map_T[currT] = i; - valid_T[currT] = 1; - } - ZEND_OP1(opline).var = NUM_VAR(map_T[currT] + offset); + currT = VAR_NUM(ZEND_OP1(opline).var) - offset; + if (!valid_T[currT]) { + GET_AVAILABLE_T(); + map_T[currT] = i; + valid_T[currT] = 1; } + ZEND_OP1(opline).var = NUM_VAR(map_T[currT] + offset); } /* Skip OP_DATA */ diff --git a/ext/opcache/Optimizer/pass1_5.c b/ext/opcache/Optimizer/pass1_5.c index 348fcb8efb..341e80501b 100644 --- a/ext/opcache/Optimizer/pass1_5.c +++ b/ext/opcache/Optimizer/pass1_5.c @@ -602,8 +602,10 @@ void zend_optimizer_pass1(zend_op_array *op_array, zend_optimizer_ctx *ctx) case ZEND_JMPNZ: case ZEND_JMPZ_EX: case ZEND_JMPNZ_EX: - case ZEND_FE_RESET: - case ZEND_FE_FETCH: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: case ZEND_NEW: case ZEND_JMP_SET: case ZEND_COALESCE: diff --git a/ext/opcache/Optimizer/pass3.c b/ext/opcache/Optimizer/pass3.c index c3a55b319f..3019b274e9 100644 --- a/ext/opcache/Optimizer/pass3.c +++ b/ext/opcache/Optimizer/pass3.c @@ -328,7 +328,8 @@ continue_jmp_ex_optimization: op->opcode == ZEND_RETURN || op->opcode == ZEND_RETURN_BY_REF || op->opcode == ZEND_FAST_RET || - op->opcode == ZEND_FE_FETCH || + op->opcode == ZEND_FE_FETCH_R || + op->opcode == ZEND_FE_FETCH_RW || op->opcode == ZEND_EXIT) { break; } @@ -363,7 +364,8 @@ continue_jmp_ex_optimization: op->opcode == ZEND_RETURN || op->opcode == ZEND_RETURN_BY_REF || op->opcode == ZEND_FAST_RET || - op->opcode == ZEND_FE_FETCH || + op->opcode == ZEND_FE_FETCH_R || + op->opcode == ZEND_FE_FETCH_RW || op->opcode == ZEND_EXIT) { break; } diff --git a/ext/opcache/Optimizer/zend_optimizer.c b/ext/opcache/Optimizer/zend_optimizer.c index 54063d0ed3..a8506fb078 100644 --- a/ext/opcache/Optimizer/zend_optimizer.c +++ b/ext/opcache/Optimizer/zend_optimizer.c @@ -450,8 +450,10 @@ static void zend_accel_optimize(zend_op_array *op_array, case ZEND_JMP_SET: case ZEND_COALESCE: case ZEND_NEW: - case ZEND_FE_RESET: - case ZEND_FE_FETCH: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: ZEND_PASS_TWO_UNDO_JMP_TARGET(op_array, opline, ZEND_OP2(opline)); break; } @@ -488,8 +490,10 @@ static void zend_accel_optimize(zend_op_array *op_array, case ZEND_JMP_SET: case ZEND_COALESCE: case ZEND_NEW: - case ZEND_FE_RESET: - case ZEND_FE_FETCH: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: ZEND_PASS_TWO_UPDATE_JMP_TARGET(op_array, opline, ZEND_OP2(opline)); break; } diff --git a/ext/opcache/zend_persist.c b/ext/opcache/zend_persist.c index 3d63f96e34..5b32baa64b 100644 --- a/ext/opcache/zend_persist.c +++ b/ext/opcache/zend_persist.c @@ -378,8 +378,10 @@ static void zend_persist_op_array_ex(zend_op_array *op_array, zend_persistent_sc case ZEND_JMP_SET: case ZEND_COALESCE: case ZEND_NEW: - case ZEND_FE_RESET: - case ZEND_FE_FETCH: + case ZEND_FE_RESET_R: + case ZEND_FE_RESET_RW: + case ZEND_FE_FETCH_R: + case ZEND_FE_FETCH_RW: ZEND_OP2(opline).jmp_addr = &new_opcodes[ZEND_OP2(opline).jmp_addr - op_array->opcodes]; break; } -- cgit v1.2.1 From 61e739187391661e2d541947bec25d7dcc4479f3 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Wed, 28 Jan 2015 14:59:54 +0300 Subject: Fixed temporary variable re-allocation pass --- ext/opcache/Optimizer/optimize_temp_vars_5.c | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) (limited to 'ext') diff --git a/ext/opcache/Optimizer/optimize_temp_vars_5.c b/ext/opcache/Optimizer/optimize_temp_vars_5.c index ac5389ed2b..7ff94ddae5 100644 --- a/ext/opcache/Optimizer/optimize_temp_vars_5.c +++ b/ext/opcache/Optimizer/optimize_temp_vars_5.c @@ -69,9 +69,8 @@ void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *c /* special puprose variable to keep HashTable* on VM stack */ if (opline->opcode == ZEND_OP_DATA && (opline-1)->opcode == ZEND_FE_FETCH_RW && - (opline-2)->opcode == ZEND_FE_RESET_RW && opline->op1_type == IS_TMP_VAR) { - start_of_T[VAR_NUM(ZEND_OP1(opline).var) - offset] = opline - 2; + start_of_T[VAR_NUM(ZEND_OP1(opline).var) - offset] = opline; } opline--; } @@ -85,13 +84,21 @@ void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *c while (opline >= end) { if ((ZEND_OP1_TYPE(opline) & (IS_VAR | IS_TMP_VAR))) { - currT = VAR_NUM(ZEND_OP1(opline).var) - offset; - if (!valid_T[currT]) { - GET_AVAILABLE_T(); - map_T[currT] = i; - valid_T[currT] = 1; + /* special puprose variable to keep HashPointer on VM stack */ + if (opline->opcode == ZEND_OP_DATA && + (opline-1)->opcode == ZEND_FE_FETCH_RW && + opline->op1_type == IS_TMP_VAR) { + max++; + ZEND_OP1(opline).var = NUM_VAR(max + offset); + } else { + currT = VAR_NUM(ZEND_OP1(opline).var) - offset; + if (!valid_T[currT]) { + GET_AVAILABLE_T(); + map_T[currT] = i; + valid_T[currT] = 1; + } + ZEND_OP1(opline).var = NUM_VAR(map_T[currT] + offset); } - ZEND_OP1(opline).var = NUM_VAR(map_T[currT] + offset); } /* Skip OP_DATA */ -- cgit v1.2.1 From 15a23b1218b3e38630d677751a975907daa2cd54 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Thu, 29 Jan 2015 21:05:02 +0300 Subject: Reimplement iteration magic with HashTableIterators (see https://wiki.php.net/rfc/php7_foreach#implementation_details) --- ext/opcache/Optimizer/block_pass.c | 6 +++++- ext/opcache/Optimizer/optimize_temp_vars_5.c | 26 ++++++-------------------- ext/opcache/Optimizer/pass2.c | 4 +++- ext/standard/array.c | 8 ++++++++ 4 files changed, 22 insertions(+), 22 deletions(-) (limited to 'ext') diff --git a/ext/opcache/Optimizer/block_pass.c b/ext/opcache/Optimizer/block_pass.c index 3df0faa0ef..4db48944e1 100644 --- a/ext/opcache/Optimizer/block_pass.c +++ b/ext/opcache/Optimizer/block_pass.c @@ -207,12 +207,15 @@ static int find_code_blocks(zend_op_array *op_array, zend_cfg *cfg, zend_optimiz for (i = 0; i< op_array->last_brk_cont; i++) { if (op_array->brk_cont_array[i].start >= 0 && (op_array->opcodes[op_array->brk_cont_array[i].brk].opcode == ZEND_FREE || + op_array->opcodes[op_array->brk_cont_array[i].brk].opcode == ZEND_FE_FREE || op_array->opcodes[op_array->brk_cont_array[i].brk].opcode == ZEND_END_SILENCE)) { int parent = op_array->brk_cont_array[i].parent; while (parent >= 0 && op_array->brk_cont_array[parent].start < 0 && - op_array->opcodes[op_array->brk_cont_array[parent].brk].opcode != ZEND_FREE) { + (op_array->opcodes[op_array->brk_cont_array[parent].brk].opcode != ZEND_FREE || + op_array->opcodes[op_array->brk_cont_array[parent].brk].opcode != ZEND_FE_FREE || + op_array->opcodes[op_array->brk_cont_array[parent].brk].opcode != ZEND_END_SILENCE)) { parent = op_array->brk_cont_array[parent].parent; } op_array->brk_cont_array[i].parent = parent; @@ -227,6 +230,7 @@ static int find_code_blocks(zend_op_array *op_array, zend_cfg *cfg, zend_optimiz for (i = 0; i< op_array->last_brk_cont; i++) { if (op_array->brk_cont_array[i].start >= 0 && (op_array->opcodes[op_array->brk_cont_array[i].brk].opcode == ZEND_FREE || + op_array->opcodes[op_array->brk_cont_array[i].brk].opcode == ZEND_FE_FREE || op_array->opcodes[op_array->brk_cont_array[i].brk].opcode == ZEND_END_SILENCE)) { if (i != j) { op_array->brk_cont_array[j] = op_array->brk_cont_array[i]; diff --git a/ext/opcache/Optimizer/optimize_temp_vars_5.c b/ext/opcache/Optimizer/optimize_temp_vars_5.c index 7ff94ddae5..dc93ce2f4c 100644 --- a/ext/opcache/Optimizer/optimize_temp_vars_5.c +++ b/ext/opcache/Optimizer/optimize_temp_vars_5.c @@ -66,12 +66,6 @@ void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *c if (ZEND_RESULT_TYPE(opline) & (IS_VAR | IS_TMP_VAR)) { start_of_T[VAR_NUM(ZEND_RESULT(opline).var) - offset] = opline; } - /* special puprose variable to keep HashTable* on VM stack */ - if (opline->opcode == ZEND_OP_DATA && - (opline-1)->opcode == ZEND_FE_FETCH_RW && - opline->op1_type == IS_TMP_VAR) { - start_of_T[VAR_NUM(ZEND_OP1(opline).var) - offset] = opline; - } opline--; } @@ -84,21 +78,13 @@ void optimize_temporary_variables(zend_op_array *op_array, zend_optimizer_ctx *c while (opline >= end) { if ((ZEND_OP1_TYPE(opline) & (IS_VAR | IS_TMP_VAR))) { - /* special puprose variable to keep HashPointer on VM stack */ - if (opline->opcode == ZEND_OP_DATA && - (opline-1)->opcode == ZEND_FE_FETCH_RW && - opline->op1_type == IS_TMP_VAR) { - max++; - ZEND_OP1(opline).var = NUM_VAR(max + offset); - } else { - currT = VAR_NUM(ZEND_OP1(opline).var) - offset; - if (!valid_T[currT]) { - GET_AVAILABLE_T(); - map_T[currT] = i; - valid_T[currT] = 1; - } - ZEND_OP1(opline).var = NUM_VAR(map_T[currT] + offset); + currT = VAR_NUM(ZEND_OP1(opline).var) - offset; + if (!valid_T[currT]) { + GET_AVAILABLE_T(); + map_T[currT] = i; + valid_T[currT] = 1; } + ZEND_OP1(opline).var = NUM_VAR(map_T[currT] + offset); } /* Skip OP_DATA */ diff --git a/ext/opcache/Optimizer/pass2.c b/ext/opcache/Optimizer/pass2.c index 5be1e30c9f..b578592493 100644 --- a/ext/opcache/Optimizer/pass2.c +++ b/ext/opcache/Optimizer/pass2.c @@ -203,7 +203,9 @@ void zend_optimizer_pass2(zend_op_array *op_array) jmp_to = &op_array->brk_cont_array[array_offset]; array_offset = jmp_to->parent; if (--nest_levels > 0) { - if (op_array->opcodes[jmp_to->brk].opcode == ZEND_FREE) { + if (op_array->opcodes[jmp_to->brk].opcode == ZEND_FREE || + op_array->opcodes[jmp_to->brk].opcode == ZEND_FE_FREE || + op_array->opcodes[jmp_to->brk].opcode == ZEND_END_SILENCE) { dont_optimize = 1; break; } diff --git a/ext/standard/array.c b/ext/standard/array.c index 966ea0f1f6..397bb88f0b 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -2203,6 +2203,9 @@ PHP_FUNCTION(array_shift) q->key = NULL; ZVAL_COPY_VALUE(&q->val, &p->val); ZVAL_UNDEF(&p->val); + if (idx == Z_ARRVAL_P(stack)->nInternalPointer) { + zend_hash_iterators_update(Z_ARRVAL_P(stack), k); + } } k++; } @@ -2265,9 +2268,14 @@ PHP_FUNCTION(array_unshift) } } ZEND_HASH_FOREACH_END(); + new_hash.nInternalPointer = Z_ARRVAL_P(stack)->nInternalPointer; + new_hash.u.v.nIteratorsCount = Z_ARRVAL_P(stack)->u.v.nIteratorsCount; + Z_ARRVAL_P(stack)->u.v.nIteratorsCount = 0; Z_ARRVAL_P(stack)->pDestructor = NULL; zend_hash_destroy(Z_ARRVAL_P(stack)); *Z_ARRVAL_P(stack) = new_hash; + zend_hash_iterators_update(Z_ARRVAL_P(stack), 0); + zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack)); /* Clean up and return the number of elements in the stack */ RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack))); -- cgit v1.2.1 From 4c5b385ff53ae9f0b52572e98c4db801f56603b0 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 07:56:37 +0300 Subject: More careful iterators update. --- ext/standard/array.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'ext') diff --git a/ext/standard/array.c b/ext/standard/array.c index 397bb88f0b..49c6cd0789 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -2203,9 +2203,7 @@ PHP_FUNCTION(array_shift) q->key = NULL; ZVAL_COPY_VALUE(&q->val, &p->val); ZVAL_UNDEF(&p->val); - if (idx == Z_ARRVAL_P(stack)->nInternalPointer) { - zend_hash_iterators_update(Z_ARRVAL_P(stack), k); - } + zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); } k++; } @@ -2268,14 +2266,13 @@ PHP_FUNCTION(array_unshift) } } ZEND_HASH_FOREACH_END(); - new_hash.nInternalPointer = Z_ARRVAL_P(stack)->nInternalPointer; new_hash.u.v.nIteratorsCount = Z_ARRVAL_P(stack)->u.v.nIteratorsCount; Z_ARRVAL_P(stack)->u.v.nIteratorsCount = 0; Z_ARRVAL_P(stack)->pDestructor = NULL; zend_hash_destroy(Z_ARRVAL_P(stack)); *Z_ARRVAL_P(stack) = new_hash; - zend_hash_iterators_update(Z_ARRVAL_P(stack), 0); zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack)); + zend_hash_iterators_reset(Z_ARRVAL_P(stack)); /* Clean up and return the number of elements in the stack */ RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack))); -- cgit v1.2.1 From cc4b7be41e2e2b9b0d7a3c8e98466b8886692e6e Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 12:24:31 +0300 Subject: Make internal function, operation on array passed by reference, to preserve foreach hash position --- ext/standard/array.c | 137 +++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 100 insertions(+), 37 deletions(-) (limited to 'ext') diff --git a/ext/standard/array.c b/ext/standard/array.c index 49c6cd0789..526c9210c1 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -1877,26 +1877,49 @@ static void php_array_data_shuffle(zval *array) /* {{{ */ hash = Z_ARRVAL_P(array); n_left = n_elems; - if (hash->nNumUsed != hash->nNumOfElements) { - for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { - p = hash->arData + idx; - if (Z_TYPE(p->val) == IS_UNDEF) continue; - if (j != idx) { - hash->arData[j] = *p; + if (EXPECTED(hash->u.v.nIteratorsCount == 0)) { + if (hash->nNumUsed != hash->nNumOfElements) { + for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { + p = hash->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (j != idx) { + hash->arData[j] = *p; + } + j++; } - j++; } - } - while (--n_left) { - rnd_idx = php_rand(); - RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); - if (rnd_idx != n_left) { - temp = hash->arData[n_left]; - hash->arData[n_left] = hash->arData[rnd_idx]; - hash->arData[rnd_idx] = temp; + while (--n_left) { + rnd_idx = php_rand(); + RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); + if (rnd_idx != n_left) { + temp = hash->arData[n_left]; + hash->arData[n_left] = hash->arData[rnd_idx]; + hash->arData[rnd_idx] = temp; + } + } + } else { + if (hash->nNumUsed != hash->nNumOfElements) { + for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { + p = hash->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (j != idx) { + hash->arData[j] = *p; + zend_hash_iterators_update(hash, idx, j); + } + j++; + } + } + while (--n_left) { + rnd_idx = php_rand(); + RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX); + if (rnd_idx != n_left) { + temp = hash->arData[n_left]; + hash->arData[n_left] = hash->arData[rnd_idx]; + hash->arData[rnd_idx] = temp; + zend_hash_iterators_update(hash, rnd_idx, n_left); + } } } - HANDLE_BLOCK_INTERRUPTIONS(); hash->nNumUsed = n_elems; hash->nInternalPointer = 0; @@ -2194,18 +2217,33 @@ PHP_FUNCTION(array_shift) if (Z_ARRVAL_P(stack)->u.flags & HASH_FLAG_PACKED) { uint32_t k = 0; - for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { - p = Z_ARRVAL_P(stack)->arData + idx; - if (Z_TYPE(p->val) == IS_UNDEF) continue; - if (idx != k) { - Bucket *q = Z_ARRVAL_P(stack)->arData + k; - q->h = k; - q->key = NULL; - ZVAL_COPY_VALUE(&q->val, &p->val); - ZVAL_UNDEF(&p->val); - zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + if (EXPECTED(Z_ARRVAL_P(stack)->u.v.nIteratorsCount == 0)) { + for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { + p = Z_ARRVAL_P(stack)->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (idx != k) { + Bucket *q = Z_ARRVAL_P(stack)->arData + k; + q->h = k; + q->key = NULL; + ZVAL_COPY_VALUE(&q->val, &p->val); + ZVAL_UNDEF(&p->val); + } + k++; + } + } else { + for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { + p = Z_ARRVAL_P(stack)->arData + idx; + if (Z_TYPE(p->val) == IS_UNDEF) continue; + if (idx != k) { + Bucket *q = Z_ARRVAL_P(stack)->arData + k; + q->h = k; + q->key = NULL; + ZVAL_COPY_VALUE(&q->val, &p->val); + ZVAL_UNDEF(&p->val); + zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + } + k++; } - k++; } Z_ARRVAL_P(stack)->nNumUsed = k; Z_ARRVAL_P(stack)->nNextFreeElement = k; @@ -2258,21 +2296,46 @@ PHP_FUNCTION(array_unshift) } zend_hash_next_index_insert_new(&new_hash, &args[i]); } - ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { - if (key) { - zend_hash_add_new(&new_hash, key, value); - } else { - zend_hash_next_index_insert_new(&new_hash, value); - } - } ZEND_HASH_FOREACH_END(); + if (EXPECTED(Z_ARRVAL_P(stack)->u.v.nIteratorsCount == 0)) { + ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { + if (key) { + zend_hash_add_new(&new_hash, key, value); + } else { + zend_hash_next_index_insert_new(&new_hash, value); + } + } ZEND_HASH_FOREACH_END(); + } else { + uint32_t old_idx; + uint32_t new_idx = i; - new_hash.u.v.nIteratorsCount = Z_ARRVAL_P(stack)->u.v.nIteratorsCount; + ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { + if (key) { + zend_hash_add_new(&new_hash, key, value); + } else { + zend_hash_next_index_insert_new(&new_hash, value); + } + old_idx = (Bucket*)value - Z_ARRVAL_P(stack)->arData; + zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx); + new_idx++; + } ZEND_HASH_FOREACH_END(); + } + + /* replace HashTable data */ Z_ARRVAL_P(stack)->u.v.nIteratorsCount = 0; Z_ARRVAL_P(stack)->pDestructor = NULL; zend_hash_destroy(Z_ARRVAL_P(stack)); - *Z_ARRVAL_P(stack) = new_hash; + + Z_ARRVAL_P(stack)->u.v.flags = new_hash.u.v.flags; + Z_ARRVAL_P(stack)->nTableSize = new_hash.nTableSize; + Z_ARRVAL_P(stack)->nTableMask = new_hash.nTableMask; + Z_ARRVAL_P(stack)->nNumUsed = new_hash.nNumUsed; + Z_ARRVAL_P(stack)->nNumOfElements = new_hash.nNumOfElements; + Z_ARRVAL_P(stack)->nNextFreeElement = new_hash.nNextFreeElement; + Z_ARRVAL_P(stack)->arData = new_hash.arData; + Z_ARRVAL_P(stack)->arHash = new_hash.arHash; + Z_ARRVAL_P(stack)->pDestructor = new_hash.pDestructor; + zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack)); - zend_hash_iterators_reset(Z_ARRVAL_P(stack)); /* Clean up and return the number of elements in the stack */ RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack))); -- cgit v1.2.1 From 08302c0d6d1cab279b9f2129df03a057baddf2ff Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 14:20:46 +0300 Subject: Make array_splice() to preserve foreach hash position --- ext/standard/array.c | 33 +++++++++++++++++++++++++++------ 1 file changed, 27 insertions(+), 6 deletions(-) (limited to 'ext') diff --git a/ext/standard/array.c b/ext/standard/array.c index 526c9210c1..a7e60899dd 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -1989,7 +1989,6 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re for (pos = 0, idx = 0; pos < offset && idx < in_hash->nNumUsed; idx++) { p = in_hash->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; - pos++; /* Get entry and increase reference count */ entry = &p->val; @@ -1999,6 +1998,10 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + pos++; } /* If hash for removed entries exists, go until offset+length and copy the entries to it */ @@ -2024,10 +2027,12 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } } } else { /* otherwise just skip those entries */ - for ( ; pos < offset + length && idx < in_hash->nNumUsed; idx++) { + int pos2 = pos; + + for ( ; pos2 < offset + length && idx < in_hash->nNumUsed; idx++) { p = in_hash->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; - pos++; + pos2++; if (p->key == NULL) { zend_hash_index_del(in_hash, p->h); } else { @@ -2045,6 +2050,7 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re ZEND_HASH_FOREACH_VAL_IND(replace, entry) { if (Z_REFCOUNTED_P(entry)) Z_ADDREF_P(entry); zend_hash_next_index_insert_new(&out_hash, entry); + pos++; } ZEND_HASH_FOREACH_END(); } @@ -2058,13 +2064,28 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + pos++; } - zend_hash_internal_pointer_reset(&out_hash); - + /* replace HashTable data */ + in_hash->u.v.nIteratorsCount = 0; in_hash->pDestructor = NULL; zend_hash_destroy(in_hash); - *in_hash = out_hash; + + in_hash->u.v.flags = out_hash.u.v.flags; + in_hash->nTableSize = out_hash.nTableSize; + in_hash->nTableMask = out_hash.nTableMask; + in_hash->nNumUsed = out_hash.nNumUsed; + in_hash->nNumOfElements = out_hash.nNumOfElements; + in_hash->nNextFreeElement = out_hash.nNextFreeElement; + in_hash->arData = out_hash.arData; + in_hash->arHash = out_hash.arHash; + in_hash->pDestructor = out_hash.pDestructor; + + zend_hash_internal_pointer_reset(in_hash); } /* }}} */ -- cgit v1.2.1 From 5406f21b11e563069d64045e599693b51c444b63 Mon Sep 17 00:00:00 2001 From: Dmitry Stogov Date: Fri, 30 Jan 2015 18:08:43 +0300 Subject: Reduced alghorithms complexity --- ext/standard/array.c | 36 +++++++++++++++++++++++++++++------- 1 file changed, 29 insertions(+), 7 deletions(-) (limited to 'ext') diff --git a/ext/standard/array.c b/ext/standard/array.c index a7e60899dd..f923ad9e7b 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -1898,13 +1898,18 @@ static void php_array_data_shuffle(zval *array) /* {{{ */ } } } else { + uint32_t iter_pos = zend_hash_iterators_lower_pos(hash, 0); + if (hash->nNumUsed != hash->nNumOfElements) { for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) { p = hash->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; if (j != idx) { hash->arData[j] = *p; - zend_hash_iterators_update(hash, idx, j); + if (idx == iter_pos) { + zend_hash_iterators_update(hash, idx, j); + iter_pos = zend_hash_iterators_lower_pos(hash, iter_pos + 1); + } } j++; } @@ -1964,6 +1969,7 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re uint idx; Bucket *p; /* Pointer to hash bucket */ zval *entry; /* Hash entry */ + uint32_t iter_pos = zend_hash_iterators_lower_pos(in_hash, 0); /* Get number of entries in the input hash */ num_in = zend_hash_num_elements(in_hash); @@ -1998,8 +2004,11 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } - if (idx != pos) { - zend_hash_iterators_update(in_hash, idx, pos); + if (idx == iter_pos) { + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1); } pos++; } @@ -2044,6 +2053,7 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } } } + iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos); /* If there are entries to insert.. */ if (replace) { @@ -2064,8 +2074,11 @@ static void php_splice(HashTable *in_hash, int offset, int length, HashTable *re } else { zend_hash_add_new(&out_hash, p->key, entry); } - if (idx != pos) { - zend_hash_iterators_update(in_hash, idx, pos); + if (idx == iter_pos) { + if (idx != pos) { + zend_hash_iterators_update(in_hash, idx, pos); + } + iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1); } pos++; } @@ -2252,6 +2265,8 @@ PHP_FUNCTION(array_shift) k++; } } else { + uint32_t iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), 0); + for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) { p = Z_ARRVAL_P(stack)->arData + idx; if (Z_TYPE(p->val) == IS_UNDEF) continue; @@ -2261,7 +2276,10 @@ PHP_FUNCTION(array_shift) q->key = NULL; ZVAL_COPY_VALUE(&q->val, &p->val); ZVAL_UNDEF(&p->val); - zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + if (idx == iter_pos) { + zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k); + iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), iter_pos + 1); + } } k++; } @@ -2328,6 +2346,7 @@ PHP_FUNCTION(array_unshift) } else { uint32_t old_idx; uint32_t new_idx = i; + uint32_t iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), 0); ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) { if (key) { @@ -2336,7 +2355,10 @@ PHP_FUNCTION(array_unshift) zend_hash_next_index_insert_new(&new_hash, value); } old_idx = (Bucket*)value - Z_ARRVAL_P(stack)->arData; - zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx); + if (old_idx == iter_pos) { + zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx); + iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), iter_pos + 1); + } new_idx++; } ZEND_HASH_FOREACH_END(); } -- cgit v1.2.1