How to become an author
Search
Write a publication
Pull to refresh

Сериализация целочисленных массивов Judy в PHP

Reading time5 min
Views5.4K
PHP*
From sandbox
Как известно, переменная в PHP это не только ценные данные, а целый контейнер zval. А массив таких переменных занимает в памяти чересчур много места.
В PHP есть реализация Judy массивов — быстрых, ассоциативных и потребляющих на порядок меньше памяти. Но, к сожалению, методов сериализации\десериализации для них не существует.

Меня интересовала сериализация только целочисленных массивов, т.е. как и индекс массива, так и его значение только целые числа. Её я и реализовал, добавив необходимые методы в исходный код расширения. Принцип сериализации прост:
Массив ( 200 => 0, 300 => -5000, -100 =>2000 ) превращается в строку
"+c8+0+12c-1388-64+7d0"

Есть два места, где можно взять исходники:

Было выбрано второе. Все изменения сделаны в php_judy.c
Жирным шрифтом показаны добавленные строки.

  1. Заявляем поддержку сериализации:
    /* implements some interface to provide access to judy object as an array */
    zend_class_implements(judy_ce TSRMLS_CC, 1, zend_ce_arrayaccess, zend_ce_iterator);

    zend_class_implements(judy_ce TSRMLS_CC, 1, zend_ce_serializable);

    judy_ce->ce_flags |= ZEND_ACC_FINAL_CLASS;

  2. Объявляем методы:
    PHP_METHOD(judy, memoryUsage);
    PHP_METHOD(judy, serialize);
    PHP_METHOD(judy, unserialize);
    PHP_METHOD(judy, count);
  3. Входные параметры для unserialize:
    ZEND_BEGIN_ARG_INFO_EX(arginfo_judy_unserialize, 0, 0, 1)
    ZEND_ARG_INFO(0,str)
ZEND_END_ARG_INFO()

  4. Описания видимых методов:
    PHP_ME(judy, memoryUsage, NULL, ZEND_ACC_PUBLIC)
    PHP_ME(judy, serialize, NULL, ZEND_ACC_PUBLIC)
    PHP_ME(judy, unserialize, arginfo_judy_unserialize, ZEND_ACC_PUBLIC)
    PHP_ME(judy, count, arginfo_judy_count, ZEND_ACC_PUBLIC)
  5. Сами методы и одна вспомогательная функция:
    PHP_METHOD(judy, serialize)
{
        JUDY_METHOD_GET_OBJECT
        if ( intern->type == TYPE_INT_TO_INT ) {
                long int   index = 0, i = 0, l;
                long int * PValue;
                char * s;
                Word_t idx1 = 0, idx2 = -1, Rc_word;

                JLC(Rc_word, intern->array, idx1, idx2);

                l = 64 + ( Rc_word << 3 );
                s = emalloc ( l );
                if ( s == NULL ) RETURN_NULL();

                JLF ( PValue, intern->array, index );
                while ( PValue != NULL && PValue != PJERR ) {
                        JLG ( PValue, intern->array, index );
                        if ( index < 0 ) {
                                if ( *PValue < 0 ) sprintf ( s+i, "-%x-%x", -index, -*PValue );
                                else sprintf ( s+i, "-%x+%x", -index, *PValue );
                        } else {
                                if ( *PValue < 0 ) sprintf ( s+i, "+%x-%x", index, -*PValue );
                                else sprintf ( s+i, "+%x+%x", index, *PValue );
                        }
                        i += strlen ( s+i );
                        if ( i > l - 50 ) {
                                l <<= 1;
                                s = erealloc ( s, l );
                                if ( s == NULL ) RETURN_NULL();
                        }
                        JLN ( PValue, intern->array, index );
                }
                *(s+i) = 0;
                RETURN_STRING ( s, 0 );
        }
        RETURN_NULL();
}

long int Hex2Int ( char * s, long int * j, long int l ) {
        long int v = 0;
        char sym;
        if ( s[*j] == '+' ) {
                (*j)++;
                sym = s[*j];
                while ( sym != '+' && sym != '-' && *j < l ) {
                        v <<= 4;
                        if (( sym >= '0' ) && ( sym <= '9' )) v += ( sym - '0' );
                        else v += ( sym - 'a' + 10 );
                        (*j)++;
                        sym = s[*j];
                }
        } else {
                (*j)++;
                sym = s[*j];
                while ( sym != '+' && sym != '-' && *j < l ) {
                        v <<= 4;
                        if (( sym >= '0' ) && ( sym <= '9' )) v -= ( sym - '0' );
                        else v -= ( sym - 'a' + 10 );
                        (*j)++;
                        sym = s[*j];
                }
        }
        return v;
}

PHP_METHOD(judy, unserialize)
{
        JUDY_METHOD_GET_OBJECT
        intern->counter = 0;
        intern->type = TYPE_INT_TO_INT;
        intern->array = (Pvoid_t) NULL;

        char * s;
        long int l, j = 0;
        Word_t * PValue, index, value;

        if ( zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "s", &s, &l) == FAILURE) return;
        if ( l < 4 ) return;
        while ( j < l ) {
                index = Hex2Int ( s, &j, l );
                value = Hex2Int ( s, &j, l );
                JLI ( PValue, intern->array, index );
                if ( PValue == NULL || PValue == PJERR ) return;
                *PValue = value;
        }
        return;
}

  6. Компилируем:
    phpize
./configure
make
make install

  7. Не забываем прописать в php.ini
    extension=judy.so

Небольшой тест\бенчмарк

<?php
function InitArray ( &$ar, $init_srand, $max ) {
	srand ( $init_srand );
	for ( $i = -$max; $i < $max; $i++ ) {
		$index = rand ( -$max, $max );
		$value = rand ( -1000, 1000 );
		$ar[$index] = $value;
	}
}

function ShowTime ( $st, $text ) {
	printf ( "$text in %.2f sec.\n", microtime ( true ) - $st );
}

	$init_srand = time ();
	$max = 500000;
	echo "srand = $init_srand, max = $max\n";
	$init_mem = memory_get_usage();
	$st = microtime ( true );
	$a = array ();
	InitArray ( $a, $init_srand, $max );
	ShowTime ( $st, "Initialized std. array" );
	echo "Elements in std. array: " , count ( $a ) , "\n";
	echo "Used memory: " , (memory_get_usage()-$init_mem) , " bytes\n\n";

	$st = microtime ( true );
	$j = new Judy(Judy::INT_TO_INT);
	InitArray ( $j, $init_srand, $max );
	ShowTime ( $st, "Initialized Judy array" );
	echo "Elements in Judy array: " , count ( $j ) , "\n";
	echo "Used memory:  " , $j->memoryUsage() , " bytes\n\n";

	$st = microtime ( true );
	$a_ser = serialize ( $a );
	ShowTime ( $st, "Serialized std. array" );

	$st = microtime ( true );
	$j_ser = serialize ( $j );
	ShowTime ( $st, "Serialized Judy array" );

	echo "Serialized std. length: " , strlen ( $a_ser ) , "\n"; 
	echo "Serialized Judy length: " , strlen ( $j_ser ) , "\n\n"; 

	$st = microtime ( true );
	$a_unser = unserialize ( $a_ser );
	ShowTime ( $st, "Unserialized std. array" );

	$st = microtime ( true );
	$j_unser = unserialize ( $j_ser );
	ShowTime ( $st, "Unserialized Judy array" );

	if (count ( $j_unser ) != count ( $a )) die ( "ERROR: arrays size mismatch\n" );

	foreach ( $a as $index => $value ) {
		if ( $j_unser[$index] != $value ) {
			die ( "ERROR: arrays data mismatch\n" ); 
		}
	}
	echo "OK: std. array and unserialized Judy array are identical\n";
?>


На выходе получаем
srand = 1348822174, max = 500000
Initialized std. array in 0.76 sec.
Elements in std. array: 632067
Used memory: 49703784 bytes

Initialized Judy array in 0.98 sec.
Elements in Judy array: 632067
Used memory:  3247108 bytes

Serialized std. array in 0.33 sec.
Serialized Judy array in 0.18 sec.
Serialized std. length: 9904186
Serialized Judy length: 6061744

Unserialized std. array in 0.13 sec.
Unserialized Judy array in 0.08 sec.
OK: std. array and unserialized Judy array are identical

Пара замечаний
  1. Конечно, Вы можете изменить алгоритм выделения памяти под строку с сериализованными данными.
  2. На данный момент в реализации итератора foreach для Judy есть баг:
    Если в массиве одновременно присутствуют индексы 0 и -1, то foreach входит в бесконечный цикл
    <?php
 $j = new Judy(Judy::INT_TO_INT);
 $j[0] = 456;
 $j[-1] = 123;
 foreach ( $j as $index => $value ) {
 echo "$index $value\n";
 }
 ?>

    Был создан запрос «foreach [0] [-1]». При желании он легко исправляется.


P.S. Этот пост был написан больше года назад — в сентябре 2012 и всё это время валялся в песочнице. Как я сейчас выяснил, на гитхабе реализовали сериализацию в отдельной ветке 3 месяца назад.
So I went ahead and pretty much copied the implementation from the Habr, but dropped negative keys support in the process
.
github.com/orieg/php-judy/issues/13
github.com/tony2001/php-judy/tree/serialize
Tags:
Hubs:
+24
Comments2
13
Karma
0
Rating
@ubx7b8

User

Send message

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr