5
\$\begingroup\$

I'm working on a PHP extension in an attempt to learn some C. I've implemented a variation of the internal PHP hashtable, which uses a lookup table and a separate bucket table. The lookup table simply points to the head of the collision chain (an index in the bucket table), and the next index in the chain is embedded in each bucket. Buckets are inserted into the table in insertion order.

#define INVALID_INDEX ((uint32_t) -1)

typedef struct _HBucket {

    zval          key;
    zval          value;  // Collision chain index in here
    zend_ulong    hash;

} HBucket;

typedef struct _HTable {

    HBucket   *buckets;
    uint32_t  *lookup;    
    uint32_t   next;      // Index at which the next bucket will be created
    uint32_t   size;      // Number of actual items in the table
    uint32_t   capacity;  // Power of two size buffer

} HTable;

HBucket *htable_lookup_or_create(HTable *table, zval *key)
{
    HBucket *bucket;
    HBucket *buckets = table->buckets;

    const zend_ulong hash = get_hash(key);

    uint32_t l_index = hash & (table->capacity - 1);  // Lookup index
    uint32_t b_index = table->lookup[l_index];        // Bucket index

    if (b_index == INVALID_INDEX) {

        // Lookup should point to the head of the collision chain,
        // which is where the new entry will be.
        table->lookup[l_index] = table->next;

    } else {

        // Traverse the collision chain...
        for (;;) {

            bucket = &buckets[b_index];

            // If the bucket's key is a match, we've found the bucket.
            if (bucket->hash == hash && is_identical(&bucket->key, key)) {
                return bucket;

            } else {

                // Index of the next bucket in the chain
                uint32_t next = Z_NEXT(bucket->value);

                // Check to see if we're at the end of the chain,
                // and set that bucket's next as the new entry.
                if (next == INVALID_INDEX) {
                    Z_NEXT(bucket->value) = table->next;
                    break;
                }

                b_index = next;
            }
        }
    }

    // Initialize the new bucket
    bucket = &buckets[table->next];

    bucket->hash = hash;
    ZVAL_COPY(&bucket->key, key);
    ZVAL_NULL(&bucket->value);

    // New bucket doesn't have a next
    Z_NEXT(bucket->value) = INVALID_INDEX;

    table->size++;
    table->next++;

    if (table->next == table->capacity) {
        htable_increase_capacity(table);
        return &table->buckets[table->size - 1];  // Address may have changed.
    }

    return bucket;
}

I realise that there are multiple zend macros, but their effects are negligible for the sake of this question. I'd be happy to expand them all if required.

I'm developing on OS X, and I've been profiling adding millions of values to determine where things might be slowing down, and it comes down to this function almost entirely.

Is there anything obvious that I could do or try to improve the performance?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.