PHP 7 получит в два раза более эффективный Hashtable


Начатый процесс переписывания ядра PHP идет семимильными шагами. Эта статья вольный пересказ поста одного из авторов кода ядра PHP о достигнутых значительных успехах в оптимизации такой структуры данных, как hashtable. Больше технических подробностей под катом.
Простой скрипт, который создает массив из 100000 целых чисел, демонстрирует следующие результаты:

32 bit 64 bit
PHP 5.6 7.37 MiB 13.97 MiB
PHP 7.0 3.00 MiB 4.00 MiB

Код теста

$startMemory = memory_get_usage(); $array = range(1, 100000); echo memory_get_usage() - $startMemory, " bytes\n"; 

PHP 7, как можно видеть, потребляет в 2.5 меньше памяти в 32-х разрядной версии и в 3.5 раза в 64-х разрядной, что согласитесь впечатляет.

Лирическое отступление

В сущности в PHP все массивы это упорядоченные словари (т.е они представляют собой упорядоченный список пар вида ключ-значение), где ассоциирование ключа значению реализовано на основе hashtable. Сделано это для того, чтобы ключами массива могли выступать не только целочисленные типы, а и сложные типы вроде строк. Сам процесс происходит следующим образом — от ключа массива берется хэш, который представлен целым числом. Это целое число используется как индекс в массиве.

Проблема возникает, когда хэширующая функция возвращает одинаковые хэши для разных ключей, то есть возникает коллизия (то, что это действительно происходит легко убедится – количество возможных ключей бесконечно велико, в то время как количество хэшей ограничено размером типа integer).

Существуют два способа борьбы с коллизиями. Первый – отрытая адресация, когда элемент сохраняется с другим индексом, если текущий уже занят, второй – хранить элементы с одинаковым индексом в связном списке. PHP использует второй способ.

Обычно элементы hashtable никак не упорядочены. Но в PHP делая итерацию по массиву, мы получаем элементы именно в том порядке, в котором мы их туда записывали. Это означает, что hashtable должна поддерживать механизм хранения порядка элементов.

Старый механизм работы hashtable

Эта схема наглядно демонстрирует принцип работы hashtable в PHP 5:

Элементы разрешения коллизий на схеме обозначены как buckets (корзина). Для каждой такой «корзины» выделяется память. На картинке не показаны значения, которые хранятся в «корзинах», так как они помещаются в отдельные zval-структуры размером 16 или 24 байта. Также на картинке опущен связный список, который хранит порядок элементов массива. Для массива, который содержит ключи «a», «b», «c» он будет выглядеть так:

Итак, почему старая структура неэффективна в плане производительности и потребляемой памяти?

  • «Корзины» требуют выделения места. Этот процесс довольно медленный и дополнительно требует 8 или 16 байт оверхеда в адресном заголовке. Это не позволяет эффективно использовать память и кэш.
  • Структуры zval для данных также требует выделения места. Проблемы с памятью и оверхом заголовка все те же, что и у «корзины», плюс использование zval обязывает нас хранить указатель на него в каждой «корзине»
  • Два связных списка требуют в сумме 4 указателя на корзину (т.к. списки двунаправленные). Это отнимает у нас еще от 16 до 32 байт. Кроме того, перемещение по связному списку это операция, которая плохо поддается кешированию.

Новая реализация hashtable призвана решить эти недостатки. Структура zval была переписана таким образом, чтобы ее можно было напрямую включать в сложные объекты (например, в вышеупомянутую «корзину»), а сама «корзина» стала выглядеть так:

typedef struct _Bucket { 	zend_ulong        h; 	zend_string      *key; 	zval              val; } Bucket;

То есть «корзина» стала включать в себя хеш h, ключ key и значение val. Целочисленные ключи сохраняются в переменной h (в таком случае хеш и ключ идентичны).
Давайте взглянем на всю структуру целиком:

typedef struct _HashTable { 	uint32_t          nTableSize; 	uint32_t          nTableMask; 	uint32_t          nNumUsed; 	uint32_t          nNumOfElements; 	zend_long         nNextFreeElement; 	Bucket           *arData; 	uint32_t         *arHash; 	dtor_func_t       pDestructor; 	uint32_t          nInternalPointer; 	union { 		struct { 			ZEND_ENDIAN_LOHI_3( 				zend_uchar    flags, 				zend_uchar    nApplyCount, 				uint16_t      reserve) 		} v; 		uint32_t flags; 	} u; } HashTable;

«Корзины» хранятся в массиве arData. Этот массив кратен степени двойки и его текущий размер хранится в переменной nTableSize (минимальный размер 8). Реальный размер массива хранится в nNumOfElements. Заметьте, что массив теперь включает в себя все «корзины», вместо того чтобы хранить указатели на них.

Порядок элементов

Массив arData теперь хранит элементы в порядке их вставки. При удалении из массива элемент помечается меткой IS_UNDEF и не учитывается в дальнейшем. То есть при удалении элемент физически остается в массиве пока счетчик занятых ячеек не достигнет размера nTableSize. При достижении этого лимита PHP попытается перестроить массив.
Такой подход позволяет сэкономить 8/16 байт на указателях, по сравнению с PHP 5. Приятным бонусом также будет то, что теперь итерация по массиву будет означать линейное сканирование памяти, что гораздо более эффективно для кеширования, чем обход связного списка.
Единственным недостатком остается неуменьшающийся размер arData, что потенциально может привести к значительному потреблению памяти на массивах в миллионы элементов.

Обход Hashtable

Хэшем заведует функция DJBX33A, которая возвращает 32-х или 64-х битное беззнаковое целое, что слишком много для использования в качестве индекса. Для этого выполняем операцию «И» с хэшем и размером таблицы уменьшенным на единицу и результат записываем в переменную ht->nTableMask. Индекс получаем в результате операции

idx = ht->arHash[hash & ht->nTableMask]

Полученный индекс будет соответствовать первому элементу в массиве коллизий. То есть ht->arData[idx] это первый элемент, который нам нужно проверить. Если хранимый там ключ соответствует требуемому, то заканчиваем поиск. В противном случае следуем к следующему элементу до тех пор пока не найдем искомый или не получим INVALID_IDX, что будет означать что данный ключ не существует.
Прелесть такого подхода заключается в том, что в отличии от PHP 5, нам больше не требуется двусвязный список.

Сжатые и пустые hashtable

PHP использует hashtable для всех массивов. Но в определенных случаях, например, когда ключи массива целые, это не совсем рационально. В PHP 7 для этого применяется сжатие hashtable. Массив arHash в таком случае равен NULL и поиск идет по индексам arData. К сожалению, такая оптимизация применима, только если ключи идут по возрастанию, т.е. для массива [1 => 2, 0 => 1] сжатие применено не будет.

Пустые hashtable это особый случай в PHP 5 и PHP 7. Практика показывает, что пустой массив имеет неплохие шансы таковым и остаться. В этом случае массивы arData/arHash будет проинициализированы только когда первый элмент будет вставлен в hashtable. Для того чтобы избежать костылей и проверок используется следующим прием: пока меньше или равно своему значению по-умолчанию, nTableMask устанавливается в ноль. Это означает, что выражение hash & ht->nTableMask всегда будет равно нулю. В этом случае массив arHash содержит всего один элемент с нулевым индексом, который содержит значение INVALID_IDX. При итерации по массиву мы всегда ищем до первого встреченного значения INVALID_IDX, что в нашем случае будет означать массив нулевого размера, что и требуется от пустого hashtable.

Итог

Все вышеперечисленные оптимизации позволили сократить занимаемый элементом размер с 144 байт в PHP 5 до 36 (32 в случае сжатия) байт в PHP 7. Небольшой недостаток новой реализации – слегка избыточное выделение памяти и отсутствие ускорения, если все значения массива одинаковы. Напомню, что в PHP 5 в этом случае используется всего один zval, так что уменьшение потребление памяти значительное:

Код теста

$startMemory = memory_get_usage(); $array = array_fill(0, 100000, 42); echo memory_get_usage() - $startMemory, " bytes\n"; 

32 bit 64 bit
PHP 5.6 4.70 MiB 9.39 MiB
PHP 7.0 3.00 MiB 4.00 MiB

Несмотря на это, PHP 7 все равно показывает лучшую эффективность.

ссылка на оригинал статьи http://habrahabr.ru/post/247145/

То, что вам нужно* (в сложном 2015)

Эта статья одобрена Григорием bobuk Бакуновым и Чаком Норрисом**


Григорий как бы говорит нам: “01110011 01100101 01100101 00100000 01111001 01101111 01110101 00100000 01101111 01101110 00100000 01110100 01101000 01100101 00100000 01101111 01110100 01101000 01100101 01110010 00100000 01110011 01101001 01100100 01100101“

Вы стопудово прочитали (или, как минимум, видели в лентах) с десяток вангующих статей, но ни одна из них не была написана по материалам выступления “the geekiest geek в России”***

2015 – год фатально разрушенных планов или волшебно возникающих возможностей? Ответов столько же, сколько тех, кто задаёт себе этот вопрос. Ясно только одно – IT проекты имеют больше шансов взлететь, если обратят внимание на то, что рассказал нам Григорий Бакунов.

Гриша готовит выступления про IT-тренды для #tceh уже несколлько лет подряд, и большинство его тезисов сбываются. Вот, например, несколько из тех, что были предсказаны Бобуком и действительно случились в 2014 году.

Курирование контента подбороками и дайджестами в стиле “38 самых-самых попугаев”, которыми в 2011 славился Buzzfeed, в 2014 не использовал только ленивый и на Хабре.

Хотя нет, на Хабре тоже использовали.

Шифрование данных? Ну конечно – Телеграм растёт; интерфейс блокировки гаджетов по отпечатку пальца вводят всё больше производителей; взлетел стартап, использующий сердечный ритм в качестве пароля.

Машинное обучение! О, да! Это словосочетание прочно вошло в стартаперское Bullshit Bingo в этом году. В любой непонятной ситуации – кричи “machine learning!” – и будет тебе счастье. А возможно – даже инвестиции.

Вобщем, Григорий не промахнулся в прошлом году, а значит – ему можно доверять и в этом.

Так что приступим к разбору трендов 2015 года.

Интересно было увидеть результаты работы проектов в тренде прошлого кризиса (2008) – shared economy, который напрямую связан с новым нарастающим трендом года 2015. На его примере Григорий наглядно показал путь развития проекта в сложное время: проект растёт крайне медленно в кризис – ищет нишу, модель монетизации, комплектует команду. Зато потом, когда начинается общий рост экономики – БЭНГ! – и он уже стоит как единорог. Цикл занимает 5-6 лет. Пример? Посмотрите на Airbnb.

Тренд 2015, связанный с феноменом shared economy, на первый взгляд звучит ещё более странно: “дешевле не значит хуже” – и он уже применяется наиболее инновационными игроками. Такими, как Xiaomi. Китайская корпорация, выпускающая топовые гаджеты на андроиде, и уже сейчас входящая в четвёрку по количеству продаваемых устройств, использует модель предзаказа по цене дешевле рыночной.

Что это даёт? Как минимум – тестирование рынка, а на самом деле – возможность избегать кредитования под выпуск нового железа. Ведь когда у тебя заказывают по низкой цене – это не значит, что цена ниже себестоимости, что даёт возможность выпуска бОльших серий и запуска их с уже подтверждённым спросом. Так что, действительно – “дешевле” != “хуже”. Во всяком случае – для китайской корпорации.

Второй тренд немного похож на мнение Капитана О – “борьба с несовершенством мира” – но пример, которым иллюстрировал его Григорий, заставляет крепко задуматься и отказаться от ярлыков и оценочных суждений.

Те, кто пользовался WhatsUp на его заре, помнят, как наглядно этот мессенджер показывал наличие или отсутствие интернета. Именно эта фича и была той, которая решала настоящую проблему многих. Вопрос: “а ловит у меня сейчас 3G?” – решался идеально просто – без всяких дополнительных пинг-тестов. Заметьте – бонусом к этой фиче давался ещё и полноценный мессенджер!

Третий тренд вам точно понравится. Он называется “развлечения”. Кому не нравится развлекаться? И не говорите мне, что вы трудоголики – даже если это так, то значит работа и есть ваше развлечение (я помню, как просыпался по ночам, чтобы загрузить свой Spectrum с кассеты и вписать десяток-другой-третий строк, которые мне приснились). Но в этот раз Григорий говорил не о коде, а о развлечениях в самом широком смысле: смешные ролики, цитаты, котики, а самое главное – мобильные приложения.

Причём, “мобильные приложения” – это совсем не обязательно игры. Приложения стали самостоятельным медиа, которое развлекает нас, даже если их функции сводятся с выбору цвета фона и набору символов – да, он говорил о Secret. Этот маленький анонимайзер ненадолго, но интенсивно развлёк изрядную часть “диджитал тусовки” в конце весны – начале лета 2014.

Смежным с этим трендом является всё большая направленность контента в визуальную сторону. Возможно, у вас нет аккаунта в Фэйсбуке и вы не заметили, как они ввели возможность комментирования “стикерами” (новый подвид emoticons). Григорий отметил, что не удивится, если скоро (он не уточнил когда) интернет превратится в полностью визуальное медиа.

Обратная сторона тренда “развлечения” больно ударит по оптимизаторам человеческих душ и процессов – большинство CRM, to-do листов и прочих тайм менеджеров ждут падения продаж (а вот Танки Онлайн вырастут). В кризис никто не хочет работать больше – больше хотят развлечься и отвлечься. Если только вовремя не изменить коммуникацию.

Если ваш сервис что-то оптимизирует – не говорите, что он “упрощает жизнь” или “делает процессы прозрачными” – всё это тлен или даже хуже для людей, находящихся в стрессе. Скажите лучше, что ваш сервис “оптимизирует расходы”, а ещё лучше – “увеличивает доходы”, и тогда вы сможете выжить и, возможно, немного вырасти в продажах.

Четвёртый и, как я понял, самый любимый тренд Григория – децентрализация. Всего. Вычислений, обмена контентом, создания контента, хранения данных – говорю же – всего.

Примеры были хорошо раскрыты в части Q&A с аудиторией после сольного выступления. Так, выяснилось, что по мнению Гриши (и по здравому рассуждению тоже) уже упомянутый Airbnb просто должен стать децентрализованным сервисом для того, чтобы выжить. Ведь, как известно, этот сервис “банят городами” – то есть запрещают работу на уровне городских администраций. Чтобы побороть эту тенденцию, Airbnb достаточно начать продавать франшизу локальным энтузиастам, которым гораздо проще решать вопросы в родном городе, чем топам Airbnb из своей штаб-квартиры.

Децентрализация тесно переплетается с другим трендом, который был определён как “гиперлокальность”. Хорошим примером служит FireChat – да, то самое скандальное приложение на технологии peer-to-peer-mesh, использование которого открыто пиарили во время “революции зонтиков” в Гонконге.

Другим, гораздо более позитивным примером, неожиданно оказалось наше приложение – #tceh (пока только для зелёных дроидов), смысл которого заключается в знакомстве и общении в рамках конкретного мероприятия и уменьшается (но не исчезает) по мере того, как люди физически отдаляются друг от друга просто потому, что роль его – установление контакта с нужным человеком здесь и сейчас.

Последним (но не по значимости) трендом, раскрытым в выступлении были “ниши”. Думаете банально? Возможно. Но тенденции не обязательно должны быть потрясающими воображение. Они должны быть реальными. А использование ниш – более чем реально – оно спасительно для проекта в кризис.

Надите свою нишу, как это сделал Pinterest, став для начала сервисом обмена рецептами домохозяек. А после того, как освоите её – кризис пойдёт на спад, а вы сможете выстрелить отточенным продуктом в более масштабную аудиторию!

На этом я почти заканчиваю описание сольного выступления Григория. Вы можете оценить мою интерпретацию в комментах после просмотра 25 минут видео, которое стоит того, поскольку Гриша мастерски владеет словом и слушать его, как всегда, приятно и интересно (не мне вам рассказывать – вы же знакомы с Радио-Т).

Если же вы хотите узнать больше – посмотрите видео с вопросами зала и ответами Гриши. Не менее увлекательно!

Из него вы узнаете, например:

— оптимальную модель монетизации в кризис
— почему “русский FireChat” не должен быть связан с политикой
— что останется в интернете будущего: книги или “игровые” форматы
— когда умер тренд “упрощение”
— в чём причина того, что “Microsoft в очередной раз хакнул Apple”
— что убило Zlango
— почему Китай не нуждается в нашем IT (спойлер-намёк: в Китае 36 популярных сторов для андроида)

Спасибо, что дочитали до конца – я увлечённо писал этот текст до 4:04 утра.

Закончить хочу статистическим фактом (из поста) и цитатой (из презентации Григория) – пожеланием для всех нас в Новом Году.

Факт: в 1325 словах этого текста “тренд” используется 13 раз (включая этот).
Цитата: “Будь собой, остальные роли заняты.” Оскар Уайльд

____________________________________

* “То, что вам нужно” (What You Need) называется фантастический рассказ Генри Каттнера и Кэтрин Мур, написанный в 1945 году

** Чак Норрис — мифический персонаж, которому мы посвящаем наши рассылки.

*** (с) Николай ni404 Белоусов

ссылка на оригинал статьи http://habrahabr.ru/company/tceh/blog/247131/