Kohana Большие и маленькие массивы

accido

Новичок
PHP:
<?php defined('SYSPATH') or die('No direct script access.');

// Include array mapper

define("MAX_ARRAY_SIZE", 500000);

$m = memory_get_usage();

$obj = new ArrayMap( 'V', 'a20', MAX_ARRAY_SIZE);

for($i=0;$i<MAX_ARRAY_SIZE;$i++)

  $obj->attach( $i, sha1(rand()));

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 11.45 MB 
 */

$m = memory_get_usage();

$obj = new ArrayMap( 'V', 'v', MAX_ARRAY_SIZE);

for($i=0;$i<MAX_ARRAY_SIZE;$i++)

  $obj->attach($i,rand());

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 2.86 MB 
 */

$m = memory_get_usage();

$obj = new ArrayMap( 'V', 'V', MAX_ARRAY_SIZE);

for($i=0;$i<MAX_ARRAY_SIZE;$i++)

  $obj->attach($i,$i);

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 3.82 MB ( ~4000000 byte) 
 */

$m = memory_get_usage();

$obj = new ArrayMap( 'V', 'V', MAX_ARRAY_SIZE);

for($i=0;$i<MAX_ARRAY_SIZE/2;$i++)
//half size
  $obj->attach($i,$i);

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 1.91 MB 
 */

$m = memory_get_usage();

$obj = new ArrayMap( MAX_ARRAY_SIZE, 2);

for($i=0;$i<MAX_ARRAY_SIZE;$i++)

  $obj->attach($i,$i);

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 23.26 MB  
 */

$m = memory_get_usage();

$obj = new SplFixedArray(2);

$obj[0] = new SplFixedArray(MAX_ARRAY_SIZE);

$obj[1] = new SplFixedArray(MAX_ARRAY_SIZE);

for($i=0;$i<MAX_ARRAY_SIZE;$i++){

  $obj[0][$i] = $i;

  $obj[1][$i] = $i;

}

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 19.07 MB 
 */

$m = memory_get_usage();

$obj = new SplFixedArray(MAX_ARRAY_SIZE);

for($i=0;$i<MAX_ARRAY_SIZE;$i++){

  $obj[$i] = new SplFixedArray(2);

  $obj[$i][0] = $i;

  $obj[$i][1] = $i;

}

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 132.31 MB 
 */

$m = memory_get_usage();

$obj = array();

$obj[0] = range(1, MAX_ARRAY_SIZE);

$obj[1] = range(1, MAX_ARRAY_SIZE);

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 80.29 MB 
 */

$m = memory_get_usage();

$obj = array();

for($i=0;$i<MAX_ARRAY_SIZE;$i++){

  $obj[$i][0] = $i;

  $obj[$i][1] = $i;

}

echo round((memory_get_usage()-$m)/1024/1024,2) . "\n<br/>\n";

/**
 * result ~ 143.15 MB 
 */
git
Значения в mapaset должны быть уникальные по ключу. Первое значение всегда есть и ключом. Не уникальные значения сохраняются, но получить их проблематично. В случае задания формата значений, используется форматирование pack/unpack функций. Хранение в этом случае обеспечивается в php://memory, но можно прикрутить и другие врапперы потоков. Планируется использовать шаред мемори. В случае хранения в памяти, при сериализации просто отдается бинарный буфер. В случае с шаред мемори можно было бы просто открыть поток и все. Данные сортируются по ключу, можно задать свою функцию сравнения, в случае с не скалярными значениями ключей. К сожалению пришлось использовать пак/анпак, потому что похапе пытается привести все записываемые данные в строки, например целое 11111 в строку "11111". Конечно, это понятно, что не строгая типизация - это круто, но зачем было отказываться от возможности отключения этого наворота в некоторых случаях, когда это действительно нужно.
 

accido

Новичок
Так как в массиве из 500000 элементов выборка идет гарантированно за ~20 операций, то решил добавить реализацию хеша, где выборка уже идет за одну операцию в среднем. Для этого взял алгоритм хеширования d-кукушкой, где d - число хеш-функций из универсального множества. Базовая хеш функция была взята из Java HashMap класса, так как она простая, если же брать хеш-функции типа cityhash, xxhash, murmur то придется подключать их из pecl. При 32 битном хеше класс обходится нормально двумя хеш-функциями при размере 200000, при больших размерах лучше увеличить их число, потому что при 32 битном ключе вероятность коллизии больше 50% уже при 100000 ключах, например в примерах ниже было применено d=4 при 400000 и 800000 ключей, но в принципе, как выяснилось, отрабатывает и при d=2 только используется больше перехеширования. Max load factor выставлен в 0.85 - полет нормальный. Фишка в том еще, что в хеш-функции используется простое кубическое число, так как оно довольно далеко от квадратов, недаром их используют в таких алгоритмах хеширования как sha2. Пробывал другие простые числа, но результат хуже так как они ближе к квадратам. Вот примеры:
PHP:
define('MAX_ARRAY_SIZE', 200000);
$m = memory_get_usage();
$arr = new HashMap( 'V', 'v', MAX_ARRAY_SIZE);
for($i=0;$i<MAX_ARRAY_SIZE;$i++)
  $arr->attach($i, $i);
echo "<br/>" . round( (memory_get_usage() - $m) / 1024 / 1024, 3 ) . "<br/>\n";
Результаты:
200000 - 1,76
400000 - 3,51
800000 - 7,01
Также тут память резервируется сразу и может увеличится, если был достигнут max load facor и возникла коллизия. Сериализация/десериализация устроена просто на копировании бинарной строки плюс маленький заголовок в начале, что конечно быстрее и экономнее чем регулярная сериализация массивов в похапе. Кстати скорость выборки в регулярных массивах похапе сильно зависит от размера и порядка. Примите ко вниманию, что при больших размерах и random-access скорость выборки из регулярных массивов уменьшается на порядок. Соотношение к скорости HashMap на моем старом компе и глючном похапе составило 1х30 в пользу регулярного, но десериализация 50000 пар ключей составила порядка 50 мкс против 120 мс у регулярных массивов.
П.С. репа та же.
 

Adelf

Administrator
Команда форума
зачем???

З.Ы. выигрыш при десериализации - из-за того, что размер указан сразу?
 

accido

Новичок
Это риторический вопрос - не вижу смысла на него Вам отвечать.
З.Ы. выигрыш при десериализации - из-за того, что размер указан сразу?
Просто потому что не происходит распарсивания, коим и является по-настоящему десериализация в похапе, строки с данными. Данные просто копируются в память целиком без переработки, так как они и так в бинарном виде и пригодны для употребления.
 

Adelf

Administrator
Команда форума
вопрос совсем не риторический. зачем вместо решения настоящих проблем придумывать искуственные и решать их?
Реализации быстрых массивов в PHP - бесполезны. По настоящему быстрыми они не будут. Только сишным расширением можно добиться быстроты, если уж так этой быстроты хочется. Но в 99.9999% приложений эта быстрота(массивная) просто не нужна, ибо скорости встроенных массивов PHP(которые весьма и весьма оптимизированы) хватает с лихвой.
 

accido

Новичок
вопрос совсем не риторический. зачем вместо решения настоящих проблем придумывать искуственные и решать их?
Реализации быстрых массивов в PHP - бесполезны. По настоящему быстрыми они не будут. Только сишным расширением можно добиться быстроты, если уж так этой быстроты хочется. Но в 99.9999% приложений эта быстрота(массивная) просто не нужна, ибо скорости встроенных массивов PHP(которые весьма и весьма оптимизированы) хватает с лихвой.
а никто и не говорил, что нужна скорость, а вот размер регулярных массивов в памяти впечатляет, особенно на 64 битных осях
читал, только придется ставить из pecl - мне это не подходит
 

Gas

может по одной?
accido
Ты бы оформил свои наработки, описал плюсы/минусы по сравнению с обычными массивами и judy, тесты выложил, желательно отвязал классы ArrayMap и HashMap от коханы чтоб проще было использовать.
Очень возможно что вполне годная вещь получилась бы.
А без описания всем лениво будет копаться в коде.
Вон по judy на хабре статья была http://habrahabr.ru/company/*****/blog/175085/, тоже можешь описать и донести до более широкой аудитории чем этот форум.
 

accido

Новичок
Та да, надо послать кохану в магазин.:)

А по-поводу джуди есть интересное тестирование ссылка, и там еще использовался не самый быстрый вариант хеш-таблиц.
З.Ы. Что-то у меня сбой в памяти произошел - подумал отвяжусь откоханы, как же я тогда интерефейсы массивов прикручу? :) Почему-то похапе у меня ассоциируется все еще с процедурами, а фреймворки с - ООП .:))
З.З.Ы. В статье на хабре не использовался тест на рандом-хит, а учитывая, что джуди массивы всегда упорядочены, то это, наверное, слишком просто для них.
З.З.З.Ы Учитывая, что регулярные массивы используют список - это тоже слишком просто для них.
 
Сверху