What algorithm does array_sum use in PHP?

Question

what algorithm does array sum uses to make it much faster than some looping through?

Is it prefix sum / suffix sum or something else?

Answer 1

Algorithm is plain: just iterate through array and produce summation of elements. That's it. In terms of algorithm there's nothing more that could be said about it. Obviously, you'll have complexity as O(n) for it.

However, PHP array_sum() is a compiled C code, thus, is will be faster than user-land function. Also, if you're interested in how it works internally, you may check array_sum() implementation:

for (zend_hash_internal_pointer_reset_ex(Z_ARRVAL_P(input), &pos);
    zend_hash_get_current_data_ex(Z_ARRVAL_P(input), (void **)&entry, &pos) == SUCCESS;
    zend_hash_move_forward_ex(Z_ARRVAL_P(input), &pos)
) {
    if (Z_TYPE_PP(entry) == IS_ARRAY || Z_TYPE_PP(entry) == IS_OBJECT) {
        continue;
    }
    entry_n = **entry;
    zval_copy_ctor(&entry_n);
    convert_scalar_to_number(&entry_n TSRMLS_CC);
    fast_add_function(return_value, return_value, &entry_n TSRMLS_CC);
}

(I've left only loop part itself). There's also fast_add_function() asm optimization, you can check out it's implementation here.