PHP builtin function strlen()和count()时间复杂度阅读分析

2017-01-23

翻了下PHP内核的定义，大概心中也有了答案了

count()和strlen()都是O(1)的时间复杂度

试想一下如果strlen()需要O(N)的复杂度那未免也太慢了，字符串长度起来的话服务器不是要直接挂掉吗

这两个函数都是典型的空间换时间的做法

我们可以先看看zvalue的结构：

typedef union _zvalue_value {
   long lval;             /* long value */
   double dval;            /* double value */
   struct {
      char *val;
      int len;
   } str;
   HashTable *ht;          /* hash table value */
   zend_object_value obj;
   zend_ast *ast;
} zvalue_value;

这里用的是一个联合体，当变量类型是string类型的时候附加存储多了一个len的整型变量，显而易见需要取长度直接利用记录值就可以了，自然就是O(1)

对于count()常用的参数类型应该为数组，对于继承Countable的类暂不作讨论

数组实现方式为Hashtable，直接看看他的结构吧

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个数字索引的位置
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

count直接获取nNumOfElements大小，所以也是O(1)

后记补充————————————————

count() 函数的定义在这里

/* {{{ proto int count(mixed var [, int mode])
   Count the number of elements in a variable (usually an array) */
PHP_FUNCTION(count)
{
    zval *array;
    zend_long mode = COUNT_NORMAL;
    zend_long cnt;
    zval *element;
    ZEND_PARSE_PARAMETERS_START(1, 2)
        Z_PARAM_ZVAL(array)
        Z_PARAM_OPTIONAL
        Z_PARAM_LONG(mode)
    ZEND_PARSE_PARAMETERS_END();
    switch (Z_TYPE_P(array)) {
        case IS_NULL:
            php_error_docref(NULL, E_WARNING, "Parameter must be an array or an object that implements Countable");
            RETURN_LONG(0);
            break;
        case IS_ARRAY:
            if (mode != COUNT_RECURSIVE) {
                //类型为数组时调用zend内核函数 zend_array_count()
                cnt = zend_array_count(Z_ARRVAL_P(array));
            } else {
                cnt = php_count_recursive(Z_ARRVAL_P(array));
            }
            RETURN_LONG(cnt);
            break;
        case IS_OBJECT: {
            zval retval;
            /* first, we check if the handler is defined */
            if (Z_OBJ_HT_P(array)->count_elements) {
                RETVAL_LONG(1);
                if (SUCCESS == Z_OBJ_HT(*array)->count_elements(array, &Z_LVAL_P(return_value))) {
                    return;
                }
            }
            /* if not and the object implements Countable we call its count() method */
            if (instanceof_function(Z_OBJCE_P(array), zend_ce_countable)) {
                zend_call_method_with_0_params(array, NULL, NULL, "count", &retval);
                if (Z_TYPE(retval) != IS_UNDEF) {
                    RETVAL_LONG(zval_get_long(&retval));
                    zval_ptr_dtor(&retval);
                }
                return;
            }
            /* If There's no handler and it doesn't implement Countable then add a warning */
            php_error_docref(NULL, E_WARNING, "Parameter must be an array or an object that implements Countable");
            RETURN_LONG(1);
            break;
        }
        default:
            php_error_docref(NULL, E_WARNING, "Parameter must be an array or an object that implements Countable");
            RETURN_LONG(1);
            break;
    }
}

如果没有特别指定mode参数为 COUNT_RECURSIVE 的话（即作遍历），跳转到 zend 的数组计数函数 zend_array_count()

#define zend_hash_num_elements(ht) \
    (ht)->nNumOfElements
...
...
static uint32_t zend_array_recalc_elements(HashTable *ht)
{
    zval *val;
    uint32_t num = ht->nNumOfElements;
    
           ZEND_HASH_FOREACH_VAL(ht, val) {
               if (Z_TYPE_P(val) == IS_INDIRECT) {
                   if (UNEXPECTED(Z_TYPE_P(Z_INDIRECT_P(val)) == IS_UNDEF)) {
                       num--;
                   }
               }
    } ZEND_HASH_FOREACH_END();
    return num;
}
ZEND_API uint32_t zend_array_count(HashTable *ht)
{
    uint32_t num;
    if (UNEXPECTED(ht->u.v.flags & HASH_FLAG_HAS_EMPTY_IND)) {
        num = zend_array_recalc_elements(ht);
        if (UNEXPECTED(ht->nNumOfElements == num)) {
            ht->u.v.flags &= ~HASH_FLAG_HAS_EMPTY_IND;
        }
    } else if (UNEXPECTED(ht == &EG(symbol_table))) {
        num = zend_array_recalc_elements(ht);
    } else {
        num = zend_hash_num_elements(ht);
    }
    return num;
}

IS_REFERENCE：间接 zval 指的就是其真正的值是存储在其他地方的。注意这个 IS_REFERENCE 类型是不同的，间接 zval 是直接指向另外一个 zval 而不是像 zend_reference 结构体一样嵌入 zval。

只有当数组中有 HASH_FLAG_HAS_EMPTY_IND 这个 flag 时（间接zval）才会对数组进行遍历校验，其他情况下都是直接取数组（hash table）里面的 nNumOfElements 的值，答案显而易见了， count() 的时间复杂度就是O(1)