9

O PHP lida com arrays de uma forma diferentes de outras linguagens, aparentemente existe conceitos de hashtable para associar os valores. Como funciona internamente no core da linguagem os arrays?

1

1 Resposta 1

8

O PHP tem algo chamado array associativo e internamente é alguma forma de hashtable mesmo, portanto ele consegue ter chaves esparsas, de tipos diferentes de dados e possui complexidade O(1) para quase todas operações básicas, assim como o array normal. Na verdade essa complexidade é tipicamente O(1), ela pode ser até O(n), mas na prática nem chega perto de acontecer. Obviamente que a chave do índice é calculada por uma função hash padrão da linguagem ou especializada nos tipos primitivos dela.

Na verdade quase tudo na estrutura de dados geral e organização da memória é controla por tabelas de espalhamento (hashtable), de forma análoga com JavaScript, mas isso não é tão visível e tão linear quanto em JS que tudo é um objeto criado em cima de uma hashtable.

Há uma otimização para obter a ordem já que um objeto hashtable puro não pode mostrar dados em uma ordem específica, então há um custo extra de armazenamento para a varredura em ordem funcionar. Veja como é a estrutura atual (se já não mudou), ela tem ponteiros para conseguir manter a ordem de entrada através de uma lista ligada dos buckets:

typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

E o bucket que mostra como é ineficiente (é quase inacreditável o tamanho do desperdício, em arquitetura 64 bits cada entrada ocupa 72 bytes só na tabela, ainda tem custo adicional em cada elemento que é próximo disso):

typedef struct bucket {
    ulong h;
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey;
} Bucket;

De forma geral os valores são alocados bem ineficientemente em PHP, os arrays não poderiam ser diferentes, embora tenha tido um esforço de otimização recentemente.

Por exemplo, descobri que todo valor é armazenado assim:

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;
} zvalue_value;

Coloquei no GitHub para referência futura.

Em 64 bits esta estrutura terá 16 bytes porque o len está aí e não junto da string em si, então qualquer valor que não seja string desperdiçará 8 bytes por causa do alinhamento. Claramente a estrutura foi pensada para 32 bits que desperdiça nada. Então rodar PHP em 64 bits pode ter quase o dobro do consumo de memória que em 32 bits, pra zero ganho. Quem sabe um dia resolvam isso, eles demonstram vontade.

Nem dá para dar tantos detalhes justamente porque o funcionamento interno é detalhe de implementação, e nada impede de passar funcionar de forma bem diferente.

E se tudo isso é estranho para você, sugiro começar estudar um pouco mais de ciência da computação, em especial estrutura de dados. Um pouco de C ajuda entender esses códigos dos internals do PHP.

0

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .